Package org.ddogleg.optimization.quasinewton

Class LineSearchFletcher86

java.lang.Object
org.ddogleg.optimization.quasinewton.LineSearchFletcher86
All Implemented Interfaces:
Serializable, IterativeOptimization, LineSearch
public class LineSearchFletcher86 extends Object implements LineSearch

Line search which meets the strong Wolfe line condition. The Wolfe condition stipulates that αk (the step size) should give sufficient decrease in the objective function below. The two parameters 0 < ftol ≤ gtol < 1 determine how stringent the search is. For a full description of optimization parameters see [1].

Wolfe condition
φ(α) ≤ φ(0) + ftol*α*φ'(0)
| φ'(α)| ≤ gtol*|φ'(0)|
where φ is the objective function and φ' is its derivative.

A typical application of using this line search is to find the minimum of an 'N' dimensional function along a line with slope 'p'. In which case φ(α) is defined below:
φ(αk) = f(xk + αk*pk)

[1] R. Fletcher, "Practical Methods of Optimization" 2nd Ed. 1986

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected double
    derivZero
     
    protected double
    fp
     
    protected double
    fprev
     
    protected CoupledDerivative
    function
     
    protected double
    gp
     
    protected double
    gprev
     
    protected double
    stp
     
    protected double
    stprev
     
    protected double
    tolStep
     
    protected double
    valueZero
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    LineSearchFletcher86()
     
    LineSearchFletcher86(double t1, double t2, double t3)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    protected boolean
    bracket()
    Searches for an upper bound.
    protected boolean
    checkSmallStep()
    Checks to see if alpha is changing by a significant amount.
    double
    getFunction()
    Function value at the current step
    double
    getGTol()
    from wolfe condition.
    double
    getStep()
    Returns the current approximate solution for the line search
    void
    init(double funcAtZero, double derivAtZero, double funcAtInit, double initAlpha, double stepMin, double stepMax)
    Initializes and resets the line search.
    protected void
    initializeSearch(double valueZero, double derivZero, double initValue, double initAlpha)
     
    protected double
    interpolate(double boundA, double boundB)
    Use either quadratic of cubic interpolation to guess the minimum.
    boolean
    isConverged()
    Indicates if iteration stopped due to convergence or not.
    boolean
    isUpdated()
    True if the parameter(s) being optimized have been updated
    boolean
    iterate()
    Updates the search.
    protected boolean
    section()
    Using the found bracket for alpha it searches for a better estimate.
    void
    setConvergence(double ftol, double gtol)
    Specify convergence criteria for line search
    void
    setFunction(CoupledDerivative function, double fmin)
    Sets the function being optimized.
    void
    setVerbose(@Nullable PrintStream out, int level)
    If set to a non-null output then extra information will be printed to the specified stream.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • tolStep

      protected double tolStep

    • function

      protected CoupledDerivative function

    • valueZero

      protected double valueZero

    • derivZero

      protected double derivZero

    • stp

      protected double stp

    • fp

      protected double fp

    • gp

      protected double gp

    • stprev

      protected double stprev

    • fprev

      protected double fprev

    • gprev

      protected double gprev

  • Constructor Details

    • LineSearchFletcher86

      public LineSearchFletcher86(double t1, double t2, double t3)
      Parameters:
      t1 - Prevents alpha from growing too large during bracket phase. Try 9
      t2 - Prevents alpha from being too close to bounds during sectioning. Recommend t2 < c2. Try 0.1
      t3 - Prevents alpha from being too close to bounds during sectioning. Try 0.5

    • LineSearchFletcher86

      public LineSearchFletcher86()

  • Method Details

    • setConvergence

      public void setConvergence(double ftol, double gtol)
      Description copied from interface: LineSearch
      Specify convergence criteria for line search
      Specified by:
      setConvergence in interface LineSearch
      Parameters:
      ftol - Controls required reduction in value. Try 1e-4
      gtol - Controls decrease in derivative magnitude. Try 0.9

    • setFunction

      public void setFunction(CoupledDerivative function, double fmin)
      Sets the function being optimized.
      Specified by:
      setFunction in interface LineSearch
      Parameters:
      function - Line search function and derivative
      fmin - Minimum possible function value

    • init

      public void init(double funcAtZero, double derivAtZero, double funcAtInit, double initAlpha, double stepMin, double stepMax)
      Description copied from interface: LineSearch
      Initializes and resets the line search. In some implementations a reasonable minimum and maximum step bound is set here.
      Specified by:
      init in interface LineSearch
      Parameters:
      funcAtZero - Value of f(0)
      derivAtZero - Derivative of at f(0)
      funcAtInit - Value of f at initial value of step: f(step)
      initAlpha - Initial step size
      stepMin - Minimum allowed step.
      stepMax - Maximum allowed step.

    • initializeSearch

      protected void initializeSearch(double valueZero, double derivZero, double initValue, double initAlpha)

    • iterate

      public boolean iterate()

      Updates the search. If the search has terminated true is returned. After the search has terminated invoke IterativeOptimization.isConverged() to see if a solution has been converged to or if it stopped for some other reason.

      NOTE: The optimization parameters might not be modified after iterate() is called. An internal book keeping step might have been done. To see if parameters have changed call IterativeOptimization.isUpdated().

      Specified by:
      iterate in interface IterativeOptimization
      Returns:
      true if it has converged or that no more progress can be made.

    • bracket

      protected boolean bracket()
      Searches for an upper bound.

    • section

      protected boolean section()
      Using the found bracket for alpha it searches for a better estimate.

    • getStep

      public double getStep()
      Description copied from interface: LineSearch
      Returns the current approximate solution for the line search
      Specified by:
      getStep in interface LineSearch
      Returns:
      current solution

    • setVerbose

      public void setVerbose(@Nullable @Nullable PrintStream out, int level)
      Description copied from interface: IterativeOptimization
      If set to a non-null output then extra information will be printed to the specified stream.
      Specified by:
      setVerbose in interface IterativeOptimization
      Parameters:
      out - Stream that is printed to. Set to null to disable
      level - (Future use) Parameter which can be used to specify level of verbose output. Set to zero for now.

    • checkSmallStep

      protected boolean checkSmallStep()
      Checks to see if alpha is changing by a significant amount. If it change is too small it can get stuck in a loop\

    • interpolate

      protected double interpolate(double boundA, double boundB)
      Use either quadratic of cubic interpolation to guess the minimum.

    • isConverged

      public boolean isConverged()
      Description copied from interface: IterativeOptimization
      Indicates if iteration stopped due to convergence or not.
      Specified by:
      isConverged in interface IterativeOptimization
      Returns:
      True if iteration stopped because it converged.

    • getFunction

      public double getFunction()
      Description copied from interface: LineSearch
      Function value at the current step
      Specified by:
      getFunction in interface LineSearch

    • getGTol

      public double getGTol()
      Description copied from interface: LineSearch
      from wolfe condition. Used to estimate max line search step
      Specified by:
      getGTol in interface LineSearch

    • isUpdated

      public boolean isUpdated()
      Description copied from interface: IterativeOptimization
      True if the parameter(s) being optimized have been updated
      Specified by:
      isUpdated in interface IterativeOptimization
      Returns:
      True if parameters have been updated