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

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.FunctionMinimizerConjugateGradient
                          extended by gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerPolakRibiere
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=83,notes="Equation 4.1.12"),@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={423,424},notes="Section 10.6",url="http://www.nrbook.com/a/bookcpdf.php")})
public class FunctionMinimizerPolakRibiere
extends FunctionMinimizerConjugateGradient

This is an implementation of the Polack-Ribiere conjugate gradient minimization procedure. This is an unconstrained nonlinear optimization technique that uses first-order derivative (gradient) information to determine the direction of exact line searches. This algorithm is generally considered to be inferior to BFGS, but does not store an NxN Hessian inverse. Thus, if you have many inputs (N), then the conjugate gradient minimization may be better than BFGS for your problem. But try BFGS first.

The Polack-Ribiere CG variant used to be considered the best out there, though I've run across a CG variant of Liu-Storey that appears to be slightly better. In my experience, they both perform about equally, with Liu-Storey slightly better. But try both before settling on one.

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

Field Summary
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerConjugateGradient
DEFAULT_LINE_MINIMIZER, DEFAULT_MAX_ITERATIONS, DEFAULT_TOLERANCE, lineFunction
 
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
FunctionMinimizerPolakRibiere()
          Creates a new instance of FunctionMinimizerPolakRibiere
FunctionMinimizerPolakRibiere(LineMinimizer<?> lineMinimizer)
          Creates a new instance of FunctionMinimizerPolakRibiere
FunctionMinimizerPolakRibiere(LineMinimizer<?> lineMinimizer, Vector initialGuess, double tolerance, int maxIterations)
          Creates a new instance of FunctionMinimizerConjugateGradient
 
Method Summary
protected  double computeScaleFactor(Vector gradientCurrent, Vector gradientPrevious)
          Computes the conjugate gradient parameter for the particular update scheme.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerConjugateGradient
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

FunctionMinimizerPolakRibiere

public FunctionMinimizerPolakRibiere()
Creates a new instance of FunctionMinimizerPolakRibiere


FunctionMinimizerPolakRibiere

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

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

FunctionMinimizerPolakRibiere

public FunctionMinimizerPolakRibiere(LineMinimizer<?> lineMinimizer,
                                     Vector initialGuess,
                                     double tolerance,
                                     int maxIterations)
Creates a new instance of FunctionMinimizerConjugateGradient

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

computeScaleFactor

protected double computeScaleFactor(Vector gradientCurrent,
                                    Vector gradientPrevious)
Description copied from class: FunctionMinimizerConjugateGradient
Computes the conjugate gradient parameter for the particular update scheme.

Specified by:
computeScaleFactor in class FunctionMinimizerConjugateGradient
Parameters:
gradientCurrent - Gradient at the current evaluation point
gradientPrevious - Gradient at the previous evaluation point
Returns:
"beta" scale factor