gov.sandia.cognition.learning.algorithm.minimization.line
Class LineMinimizerDerivativeBased

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<Double,Double,EvaluatorType>
                      extended by gov.sandia.cognition.learning.algorithm.minimization.line.AbstractAnytimeLineMinimizer<DifferentiableUnivariateScalarFunction>
                          extended by gov.sandia.cognition.learning.algorithm.minimization.line.LineMinimizerDerivativeBased
All Implemented Interfaces:
AnytimeAlgorithm<InputOutputPair<Double,Double>>, IterativeAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<DifferentiableUnivariateScalarFunction,InputOutputPair<Double,Double>>, BatchLearner<DifferentiableUnivariateScalarFunction,InputOutputPair<Double,Double>>, FunctionMinimizer<Double,Double,DifferentiableUnivariateScalarFunction>, LineMinimizer<DifferentiableUnivariateScalarFunction>, CloneableSerializable, Serializable, Cloneable

@PublicationReference(author="R. Fletcher",
                      title="Practical Methods of Optimization, Second Edition",
                      type=Book,
                      year=1987,
                      pages={34,39},
                      notes={"Equation 2.6.2 and Equation 2.6.4","Fletcher assumes that the initial slope is negative (WOLOG), and this class automatically adjusts itself to positive-slope guesses."})
public class LineMinimizerDerivativeBased
extends AbstractAnytimeLineMinimizer<DifferentiableUnivariateScalarFunction>

This is an implementation of a line-minimization algorithm proposed by Fletcher that makes extensive use of first-order derivative information. The algorithm is provably correct and has good empirical performance.
According to my test battery, this algorithm performs best using Hermite parabolic interpolators (LineBracketInterpolatorHermiteParabola).
My test battery LineMinimizerTestHarness minimizes over several different functions including cosine and an absolute value of a cubic polynomial. Here are the results in {function_evaluations, gradient_evaluation) pairs.
LineBracketInterpolatorHermiteParabola: cosine=(4.25,3.36), absolute_cubic=(8.09,5.02).
LineBracketInterpolatorHermiteCubic: cosine=(4.27,4.21), absolute_cubic=(7.52,6.55).
LineBracketInterpolatorBrent: cosine=(5.22,3.98), absolute_cubic=(9.44,6.27).

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

Nested Class Summary
 class LineMinimizerDerivativeBased.InternalFunction
          Internal function used to map/remap/unmap the search direction.
 
Field Summary
static double DEFAULT_CURVATURE_CONDITION
          This is a fairly accurate line search, 0.1.
static LineBracketInterpolator<? super DifferentiableUnivariateScalarFunction> DEFAULT_INTERPOLATOR
          Default interpolator to use to create a new candidate point to evaluate
static double DEFAULT_MIN_FUNCTION_VALUE
          Default minimum function value, 0.0.
static double DEFAULT_SLOPE_CONDITION
          This is a fairly accurate line search, 0.01.
protected static double TAU1
          Suggested value given in PMOO=9.0, bottom of p.34, 5.0
protected static double TAU2
          Suggested value given in PMOO=0.05, top of p.36 (given as 0.05 on p.69), 0.1
protected static double TAU3
          Suggested value given in PMOO=0.50, top of p.36, 0.5
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.minimization.line.AbstractAnytimeLineMinimizer
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
LineMinimizerDerivativeBased()
          Default constructor
LineMinimizerDerivativeBased(double minFunctionValue)
          Creates a new instance of LineMinimizerDerivativeBased
LineMinimizerDerivativeBased(LineBracketInterpolator<? super DifferentiableUnivariateScalarFunction> interpolator, double minFunctionValue)
          Creates a new instance of LineMinimizerDerivativeBased
 
Method Summary
 boolean bracketingStep()
          Continues the bracketing phase of the algorithm, which attempts to place a bracket around a known minimum.
 double getMinFunctionValue()
          Getter for minFunctionValue
protected  boolean initializeAlgorithm()
          Called to initialize the learning algorithm's state based on the data that is stored in the data field.
 boolean sectioningStep()
          Continues the sectioning phase of the algorihtm.
 void setMinFunctionValue(double minFunctionValue)
          Setter for minFunctionValue
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.minimization.line.AbstractAnytimeLineMinimizer
cleanupAlgorithm, getBracket, getInitialGuessFunctionValue, getInitialGuessSlope, getInterpolator, isValidBracket, minimizeAlongDirection, setBracket, setData, setInitialGuess, setInitialGuessFunctionValue, setInitialGuessSlope, setInterpolator, setValidBracket, step
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer
getInitialGuess, getResult, getTolerance, setResult, setTolerance
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner
clone, getData, getKeepGoing, learn, 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
getInitialGuess, getTolerance, learn, setTolerance
 
Methods inherited from interface gov.sandia.cognition.util.CloneableSerializable
clone
 
Methods inherited from interface gov.sandia.cognition.algorithm.AnytimeAlgorithm
getMaxIterations, getResult, 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_CURVATURE_CONDITION

public static final double DEFAULT_CURVATURE_CONDITION
This is a fairly accurate line search, 0.1.

See Also:
Constant Field Values

DEFAULT_SLOPE_CONDITION

public static final double DEFAULT_SLOPE_CONDITION
This is a fairly accurate line search, 0.01.

See Also:
Constant Field Values

DEFAULT_INTERPOLATOR

public static final LineBracketInterpolator<? super DifferentiableUnivariateScalarFunction> DEFAULT_INTERPOLATOR
Default interpolator to use to create a new candidate point to evaluate


DEFAULT_MIN_FUNCTION_VALUE

public static final double DEFAULT_MIN_FUNCTION_VALUE
Default minimum function value, 0.0.

See Also:
Constant Field Values

TAU1

protected static final double TAU1
Suggested value given in PMOO=9.0, bottom of p.34, 5.0

See Also:
Constant Field Values

TAU2

protected static final double TAU2
Suggested value given in PMOO=0.05, top of p.36 (given as 0.05 on p.69), 0.1

See Also:
Constant Field Values

TAU3

protected static final double TAU3
Suggested value given in PMOO=0.50, top of p.36, 0.5

See Also:
Constant Field Values
Constructor Detail

LineMinimizerDerivativeBased

public LineMinimizerDerivativeBased()
Default constructor


LineMinimizerDerivativeBased

public LineMinimizerDerivativeBased(double minFunctionValue)
Creates a new instance of LineMinimizerDerivativeBased

Parameters:
minFunctionValue - Direction of the search. Because Fletcher assumes the slope of the initialGuess is less than 0.0, we have to flip around the direction of search if the initial guess has positive slope. Thus, direction=1.0 means that the initial slope was negative, while direction=-1.0 means that the initial slope was positive.

LineMinimizerDerivativeBased

public LineMinimizerDerivativeBased(LineBracketInterpolator<? super DifferentiableUnivariateScalarFunction> interpolator,
                                    double minFunctionValue)
Creates a new instance of LineMinimizerDerivativeBased

Parameters:
interpolator - Type of algorithm to fit data points and find an interpolated minimum to the known points.
minFunctionValue - Direction of the search. Because Fletcher assumes the slope of the initialGuess is less than 0.0, we have to flip around the direction of search if the initial guess has positive slope. Thus, direction=1.0 means that the initial slope was negative, while direction=-1.0 means that the initial slope was positive.
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.

Overrides:
initializeAlgorithm in class AbstractAnytimeLineMinimizer<DifferentiableUnivariateScalarFunction>
Returns:
True if the learning algorithm can be run and false if it cannot.

bracketingStep

public boolean bracketingStep()
Description copied from interface: LineMinimizer
Continues the bracketing phase of the algorithm, which attempts to place a bracket around a known minimum.

Specified by:
bracketingStep in interface LineMinimizer<DifferentiableUnivariateScalarFunction>
Specified by:
bracketingStep in class AbstractAnytimeLineMinimizer<DifferentiableUnivariateScalarFunction>
Returns:
True if a valid bracket has been found, false to continue the bracketing phase of the algorithm.

sectioningStep

public boolean sectioningStep()
Description copied from interface: LineMinimizer
Continues the sectioning phase of the algorihtm. This phase occurs after the bracketing phase and attempts to shrink the size of the bracket (using a LineBracketInterpolator) until sufficient accuracy is attained.

Specified by:
sectioningStep in interface LineMinimizer<DifferentiableUnivariateScalarFunction>
Specified by:
sectioningStep in class AbstractAnytimeLineMinimizer<DifferentiableUnivariateScalarFunction>
Returns:
True that a valid minimum has been found, false to continue sectioning the bracket.

getMinFunctionValue

public double getMinFunctionValue()
Getter for minFunctionValue

Returns:
Minimum value of the target function. In other words, the user will accept a solution less than or equal to minFunctionValue.

setMinFunctionValue

public void setMinFunctionValue(double minFunctionValue)
Setter for minFunctionValue

Parameters:
minFunctionValue - Minimum value of the target function. In other words, the user will accept a solution less than or equal to minFunctionValue.