net.von_gagern.martin.confoo.opt
Class Newton

java.lang.Object
  net.von_gagern.martin.confoo.opt.Newton

All Implemented Interfaces:

Runnable

public class Newton
extends Object
implements Runnable

Newton method for Convex Optimization.

This class implements Newton method for convex optimization with backtracking line search. The details can be found in the book Convex Optimization by Boyd and Vanderberghe which is available online.

Since:

1.0

Author:

Martin von Gagern

See Also:

Convex Optimization by Boyd and Vandenberghe

Nested Class Summary

static class

Newton.ExitCondition Enumeration of possible reasons for the termination of an optimization.

Method Summary

no.uib.cipr.matrix.Vector	getArgMin() Get position of critical point.
Newton.ExitCondition	getExitCondition() Get cause for the termination of the most recent optimization.
double	getExitError() Get residual error for exit condition.
static Newton	getInstance(Functional f) Construct new optimizer for given functional.
void	lineSearchParameters(double alpha, double beta, double gamma) Set parameters for backtracking line search.
void	optimize() Find approximatively optimal solution.
void	run() Runnable interface to the optimize method.
void	setEpsilon(Newton.ExitCondition cond, double epsilon) Set error bound for given termination condition.
void	setMaxIterations(int max) Set maximum number of iterations.
void	setNorm(Newton.ExitCondition cond, no.uib.cipr.matrix.Vector.Norm norm) Set the norm used to compare a vector with an error bound.
void	throwInterceptedExceptions() Re-throw exceptions intercepted by run.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

getInstance

public static Newton getInstance(Functional f)

Construct new optimizer for given functional.

Parameters:

f - the functional to be optimized

Returns:

an optimizer for the given functional

optimize

public void optimize()
              throws no.uib.cipr.matrix.sparse.IterativeSolverNotConvergedException

Find approximatively optimal solution.

This is the main method of the optimizer. It uses settings made by previous call to varous configuration methods, and makes its results available to various result access methods.

When this method terminates, the most recent call to setArgument for the underlying functional will have been for the found optimum. Thus the functional itself can be queried to get the optimal value, residual gradient and so on.

Throws:

no.uib.cipr.matrix.sparse.IterativeSolverNotConvergedException - if the Newton step could not be determined, e.g. because the functional is not convex.

See Also:

Functional.setArgument(Vector)

getExitCondition

public Newton.ExitCondition getExitCondition()

Get cause for the termination of the most recent optimization.

Returns:

enum value representing the cause of termination

getExitError

public double getExitError()

Get residual error for exit condition. The meaning of this value depends on the exit condition:

GRADIENT

Norm of the gradient

ESTIMATE

Estimated residual value error

DELTA

Norm of the step in input space

ITERATIONS

Number of iterations actually performed

Returns:

residual error as specified above

See Also:

getExitCondition()

getArgMin

public no.uib.cipr.matrix.Vector getArgMin()

Get position of critical point.

Returns:

the argument that lead to the found solution

setEpsilon

public void setEpsilon(Newton.ExitCondition cond,
                       double epsilon)

Set error bound for given termination condition.

Parameters:

cond - one of GRADIENT, DELTA or ESTIMATE

epsilon - the new bound to be set

Throws:

IllegalArgumentException - for other conditions

setNorm

public void setNorm(Newton.ExitCondition cond,
                    no.uib.cipr.matrix.Vector.Norm norm)

Set the norm used to compare a vector with an error bound.

Parameters:

cond - one of GRADIENT or DELTA

norm - the norm to evaluate for the specified vectors

See Also:

setEpsilon(net.von_gagern.martin.confoo.opt.Newton.ExitCondition, double)

setMaxIterations

public void setMaxIterations(int max)

Set maximum number of iterations.

Parameters:

max - the new maximum number of iterations

See Also:

Newton.ExitCondition.ITERATIONS

lineSearchParameters

public void lineSearchParameters(double alpha,
                                 double beta,
                                 double gamma)

Set parameters for backtracking line search.

Once the Newton step is determined, the actual change in function value at the end of the step is compared with the change predicted by the gradient. The actual difference has to be at least alpha times the predicted difference. Otherwise the step size is reduced by multiplication with beta. The parameter gamma defines a minimal proportion of the original step size; after this has been reached the line search will terminate no matter what.

Parameters:

alpha - factor by which to multiply predicted change. 0 < alpha < 0.5

beta - factor to reduce step size. 0 < beta < 1

gamma - minimum step size factor. 0 <= gamma <= beta

run

public void run()

Runnable interface to the optimize method.

This method allows performing the optimization in a different thread. However, as a run method may not throw any checked exceptions, special care has to be taken to catch these exceptions later on. The main thread that was waiting for the result should call throwInterceptedExceptions to re-throw any exceptions that occurred during execution in a different thread.

Any application not using multiple threads should rather call optimize directly to deal with exceptions more easily.

Specified by:

run in interface Runnable

Throws:

IllegalStateException - if there is an uncleared exception from a previous invocation

See Also:

optimize(), throwInterceptedExceptions()

throwInterceptedExceptions

public void throwInterceptedExceptions()
                                throws no.uib.cipr.matrix.sparse.IterativeSolverNotConvergedException

Re-throw exceptions intercepted by run. This method must be called after every invocation of run in order to clear and re-throw any exceptions which occurred during the execution of optimize.

Throws:

no.uib.cipr.matrix.sparse.IterativeSolverNotConvergedException

See Also:

run()