gov.sandia.cognition.learning.algorithm.minimization
Class FunctionMinimizerBFGS

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
          extended by gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>
              extended by gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<EvaluatorType,InputOutputPair<InputType,OutputType>>
                  extended by gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer<Vector,Double,DifferentiableEvaluator<? super Vector,Double,Vector>>
                      extended by gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerQuasiNewton
                          extended by gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerBFGS
All Implemented Interfaces:
AnytimeAlgorithm<InputOutputPair<Vector,Double>>, IterativeAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<DifferentiableEvaluator<? super Vector,Double,Vector>,InputOutputPair<Vector,Double>>, BatchLearner<DifferentiableEvaluator<? super Vector,Double,Vector>,InputOutputPair<Vector,Double>>, FunctionMinimizer<Vector,Double,DifferentiableEvaluator<? super Vector,Double,Vector>>, CloneableSerializable, Serializable, Cloneable

@PublicationReferences(references={@PublicationReference(author="R. Fletcher",title="Practical Methods of Optimization, Second Edition",type=Book,year=1987,pages=55,notes="Section 3.2, Equation 3.2.12"),@PublicationReference(author="Wikipedia",title="BFGS method",type=WebPage,year=2008,url="http://en.wikipedia.org/wiki/BFGS_method"),@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={428,429},notes="Section 10.7",url="http://www.nrbook.com/a/bookcpdf.php")})
public class FunctionMinimizerBFGS
extends FunctionMinimizerQuasiNewton

Implementation of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) Quasi-Newton nonlinear minimization algorithm. This algorithm is generally considered to be the most effective/efficient unconstrained nonlinear optimization algorithm out there. It does, however, require the derivative of the function to optimize. Furthermore, it requires the storage of an approximation of the Hessian inverse (BFGS does not invert any matrix, it merely approximates the inverse explicitly... clever, eh?), which is an N-by-N matrix, where N is the size of the input space.

In practice, one can use approximated Jacobians with BFGS with good convergence results, so one can use, for example, GradientDescendableApproximator (when used for parameter cost minimization) when exact gradients are not available. Using approximated Jacobian tends, to slow down BFGS by a factor of about ~3, but it appears to generally outperform derivative-free minimization techniques, like Powell's direction-set method. Also, BFGS appears to outperform Leveberg-Marquardt estimation for parameter estimation, in my experience.

Again, just to recap: BFGS appears to be the method of choice when minimizing against a cost function (using exact or approximated Jacobians).

Note that there is a reduced-memory implementation of BFGS, called L-BFGS, that reduces the memory needed to store the Hessian inverse. We have not yet implemented this.

Since:
2.0
Author:
Kevin R. Dixon
See Also:
Serialized Form

Field Summary
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerQuasiNewton
DEFAULT_LINE_MINIMIZER, DEFAULT_MAX_ITERATIONS, DEFAULT_TOLERANCE
 
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
FunctionMinimizerBFGS()
          Creates a new instance of FunctionMinimizerBFGS
FunctionMinimizerBFGS(LineMinimizer<?> lineMinimizer)
          Creates a new instance of FunctionMinimizerBFGS
FunctionMinimizerBFGS(LineMinimizer<?> lineMinimizer, Vector initialGuess, double tolerance, int maxIterations)
          Creates a new instance of FunctionMinimizerBFGS
 
Method Summary
static boolean BFGSupdateRule(Matrix hessianInverse, Vector delta, Vector gamma, double tolerance)
          BFGS Quasi-Newton update rule
 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.FunctionMinimizerQuasiNewton
cleanupAlgorithm, getLineMinimizer, initializeAlgorithm, setLineMinimizer, step
 
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
 

Constructor Detail

FunctionMinimizerBFGS

public FunctionMinimizerBFGS()
Creates a new instance of FunctionMinimizerBFGS


FunctionMinimizerBFGS

public FunctionMinimizerBFGS(LineMinimizer<?> lineMinimizer)
Creates a new instance of FunctionMinimizerBFGS

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

FunctionMinimizerBFGS

public FunctionMinimizerBFGS(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

updateHessianInverse

public boolean updateHessianInverse(Matrix hessianInverse,
                                    Vector delta,
                                    Vector gamma)
Description copied from class: FunctionMinimizerQuasiNewton
The step that makes BFGS/DFP/SR1 different from each other. This embodies the specific Quasi-Newton update step

Specified by:
updateHessianInverse in class FunctionMinimizerQuasiNewton
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.)

BFGSupdateRule

@PublicationReference(author="R. Fletcher",
                      title="Practical Methods of Optimization, Second Edition",
                      type=Book,
                      year=1987,
                      pages=55,
                      notes="Section 3.2, Equation 3.2.12")
public static boolean BFGSupdateRule(Matrix hessianInverse,
                                                                                           Vector delta,
                                                                                           Vector gamma,
                                                                                           double tolerance)
BFGS Quasi-Newton update rule

Parameters:
hessianInverse - Current Hessian inverse estimate, will be modified
delta - Change in x-axis
gamma - Change in gradient
tolerance - Tolerance of the algorithm
Returns:
true if update, false otherwise