gov.sandia.cognition.learning.algorithm.minimization

Class FunctionMinimizerQuasiNewton

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>

gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<EvaluatorType,InputOutputPair<InputType,OutputType>>

gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer<Vector,java.lang.Double,DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>>

gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerQuasiNewton

All Implemented Interfaces:

AnytimeAlgorithm<InputOutputPair<Vector,java.lang.Double>>, IterativeAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.Double>>, BatchLearner<DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.Double>>, FunctionMinimizer<Vector,java.lang.Double,DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>>, CloneableSerializable, java.io.Serializable, java.lang.Cloneable

Direct Known Subclasses:

FunctionMinimizerBFGS, FunctionMinimizerDFP

@PublicationReference(author="R. Fletcher",title="Practical Methods of Optimization, Second Edition",type=Book,year=1987,pages={49,57},notes="Section 3.2") @PublicationReference(author="Wikipedia",title="Quasi-Newton method",type=WebPage,year=2008,url="http://en.wikipedia.org/wiki/Quasi-Newton_methods") @PublicationReference(author={"William H. Press","Saul A. Teukolsky","William T. Vetterling","Brian P. Flannery"},title="Numerical Recipes in C, Second Edition",type=Book,year=1992,pages={425,430},notes="Section 10.7",url="http://www.nrbook.com/a/bookcpdf.php")
public abstract class FunctionMinimizerQuasiNewton
extends AbstractAnytimeFunctionMinimizer<Vector,java.lang.Double,DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>>

This is an abstract implementation of the Quasi-Newton minimization method, sometimes called "Variable-Metric methods." This family of minimization algorithms uses first-order gradient information to find a locally minimum to a scalar function. Quasi-Newton methods perform this minimization by creating an estimate of the inverse of the Hessian to compute a new search direction. A line search yields the next point from which to estimate the function curvature (that is, the estimate of the Hessian inverse). Please note: Quasi-Newton algorithms estimate the INVERSE of the Hessian and never actually invert/solve for a matrix, making them extremely fast.

It is generally agreed that Quasi-Newton methods are the fastest minimization algorithms that use one first-order gradient information. In particular, the BFGS update formula to the Quasi-Newton algorithm (FunctionMinimizerBFGS) is generally regarded as the fastest unconstrained optimizer out there, and is my method of choice. However, all Quasi-Newton methods require storage of the inverse Hessian, which can become quite large. If you cannot store the inverse Hessian estimate in memory, then I would recommend using the Liu-Storey Conjugate Gradient algorithm instead (FunctionMinimizerLiuStorey).

Generally speaking, Quasi-Newton methods require first-order gradient information. If you do not have access to gradients, then I would recommend using automatic finite-difference approximations over the derivative-free minimization algorithms.

Since:

2.1

Author:

Kevin R. Dixon

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static LineMinimizer<?>	DEFAULT_LINE_MINIMIZER Default line minimization algorithm, LineMinimizerDerivativeBased
static int	DEFAULT_MAX_ITERATIONS Default maximum number of iterations before stopping, 1000
static double	DEFAULT_TOLERANCE Default tolerance, 1.0E-5

Fields inherited from class gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer

initialGuess, result, tolerance

Fields inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner

data, keepGoing

Fields inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm

maxIterations

Fields inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

DEFAULT_ITERATION, iteration

Constructor Summary

Constructors

Constructor and Description
FunctionMinimizerQuasiNewton(LineMinimizer<?> lineMinimizer, Vector initialGuess, double tolerance, int maxIterations) Creates a new instance of FunctionMinimizerBFGS

Method Summary

Modifier and Type	Method and Description
protected void	cleanupAlgorithm() Called to clean up the learning algorithm's state after learning has finished.
LineMinimizer<?>	getLineMinimizer() Getter for lineMinimizer
protected boolean	initializeAlgorithm() Called to initialize the learning algorithm's state based on the data that is stored in the data field.
void	setLineMinimizer(LineMinimizer<?> lineMinimizer) Setter for lineMinimizer
protected boolean	step() Called to take a single step of the learning algorithm.
protected abstract boolean	updateHessianInverse(Matrix hessianInverse, Vector delta, Vector gamma) The step that makes BFGS/DFP/SR1 different from each other.

Methods inherited from class gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer

getInitialGuess, getResult, getTolerance, setInitialGuess, setResult, setTolerance

Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner

clone, getData, getKeepGoing, learn, setData, setKeepGoing, stop

Methods inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm

getMaxIterations, isResultValid, setMaxIterations

Methods inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

addIterativeAlgorithmListener, fireAlgorithmEnded, fireAlgorithmStarted, fireStepEnded, fireStepStarted, getIteration, getListeners, removeIterativeAlgorithmListener, setIteration, setListeners

Methods inherited from class java.lang.Object

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

Methods inherited from interface gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizer

learn

Methods inherited from interface gov.sandia.cognition.util.CloneableSerializable

clone

Methods inherited from interface gov.sandia.cognition.algorithm.AnytimeAlgorithm

getMaxIterations, setMaxIterations

Methods inherited from interface gov.sandia.cognition.algorithm.IterativeAlgorithm

addIterativeAlgorithmListener, getIteration, removeIterativeAlgorithmListener

Methods inherited from interface gov.sandia.cognition.algorithm.StoppableAlgorithm

isResultValid, stop

Field Detail

DEFAULT_MAX_ITERATIONS

public static final int DEFAULT_MAX_ITERATIONS

Default maximum number of iterations before stopping, 1000

See Also:

Constant Field Values

DEFAULT_TOLERANCE

public static final double DEFAULT_TOLERANCE

Default tolerance, 1.0E-5

See Also:

Constant Field Values

DEFAULT_LINE_MINIMIZER

public static final LineMinimizer<?> DEFAULT_LINE_MINIMIZER

Default line minimization algorithm, LineMinimizerDerivativeBased

Constructor Detail

FunctionMinimizerQuasiNewton

public FunctionMinimizerQuasiNewton(LineMinimizer<?> lineMinimizer,
                                    Vector initialGuess,
                                    double tolerance,
                                    int maxIterations)

Creates a new instance of FunctionMinimizerBFGS

Parameters:

initialGuess - Initial guess about the minimum of the method

tolerance - Tolerance of the minimization algorithm, must be >= 0.0, typically ~1e-10

lineMinimizer - Work-horse algorithm that minimizes the function along a direction

maxIterations - Maximum number of iterations, must be >0, typically ~100

Method Detail

initializeAlgorithm

protected boolean initializeAlgorithm()

Description copied from class: AbstractAnytimeBatchLearner

Called to initialize the learning algorithm's state based on the data that is stored in the data field. The return value indicates if the algorithm can be run or not based on the initialization.

Specified by:

initializeAlgorithm in class AbstractAnytimeBatchLearner<DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.Double>>

Returns:

True if the learning algorithm can be run and false if it cannot.

step

protected boolean step()

Description copied from class: AbstractAnytimeBatchLearner

Called to take a single step of the learning algorithm.

Specified by:

step in class AbstractAnytimeBatchLearner<DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.Double>>

Returns:

True if another step can be taken and false it the algorithm should halt.

updateHessianInverse

protected abstract boolean updateHessianInverse(Matrix hessianInverse,
                                                Vector delta,
                                                Vector gamma)

The step that makes BFGS/DFP/SR1 different from each other. This embodies the specific Quasi-Newton update step

Parameters:

hessianInverse - Current estimate of the Hessian inverse. Must be modified!

delta - Change in the search points (xnew-xold)

gamma - Change in the gradients (gnew-gold)

Returns:

True if Hessian was modified, false otherwise (due to numerical instability, etc.)

cleanupAlgorithm

protected void cleanupAlgorithm()

Description copied from class: AbstractAnytimeBatchLearner

Called to clean up the learning algorithm's state after learning has finished.

Specified by:

cleanupAlgorithm in class AbstractAnytimeBatchLearner<DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.Double>>

getLineMinimizer

public LineMinimizer<?> getLineMinimizer()

Getter for lineMinimizer

Returns:

Work-horse algorithm that minimizes the function along a direction

setLineMinimizer

public void setLineMinimizer(LineMinimizer<?> lineMinimizer)

Setter for lineMinimizer

Parameters:

lineMinimizer - Work-horse algorithm that minimizes the function along a direction