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

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

@PublicationReference(author={"Y. Liu","C. Storey"},
                      title="Efficient generalized conjugate gradient algorithms, Part 1: theory",
                      type=Journal,
                      publication="Journal of Optimization Theory and Applications",
                      pages={129,137},
                      year=1991,
                      notes={"I\'ve seen independent analyses that indicate that this is the most efficient CG algorithm out there.","For example, http://www.ici.ro/camo/neculai/cg.ppt"})
public class FunctionMinimizerLiuStorey
extends FunctionMinimizerConjugateGradient

This is an implementation of the Liu-Storey 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 Liu-Storey CG variant is considered often superior to the CG variant of Polack-Ribiere. In my experience, they both perform about equally, with Liu-Storey slightly better. But try both before settling on one.

Since:
2.1
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
FunctionMinimizerLiuStorey()
          Creates a new instance of FunctionMinimizerLiuStorey
FunctionMinimizerLiuStorey(LineMinimizer<?> lineMinimizer)
          Creates a new instance of FunctionMinimizerLiuStorey
FunctionMinimizerLiuStorey(LineMinimizer<?> lineMinimizer, Vector initialGuess, double tolerance, int maxIterations)
          Creates a new instance of FunctionMinimizerLiuStorey
 
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

FunctionMinimizerLiuStorey

public FunctionMinimizerLiuStorey()
Creates a new instance of FunctionMinimizerLiuStorey


FunctionMinimizerLiuStorey

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

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

FunctionMinimizerLiuStorey

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

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