gov.sandia.cognition.learning.algorithm.minimization

Class FunctionMinimizerPolakRibiere

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.FunctionMinimizerConjugateGradient

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

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

@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

Constructors

Constructor and Description
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

Modifier and Type	Method and Description
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