Package org.ddogleg.optimization.quasinewton

Class LineSearchMore94

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

Line search algorithm that provides a guaranteed sufficient decrease according to the Wolfe condition. This is the same algorithm by Minpack-2 [2]. The logic in the code below is based off of [2] but the original paper [1] was being looked at too.

Wolfe condition
φ(α) ≤ φ(0) + ftol*αφ'(0)
|φ'(α)| ≤ gtol*|φ'(0)|
where ftol and gtol determine the precision needed to terminate the search..

This is basically a "cleaned up" version of the code from:. MINPACK-2 Project. November 1993.
Argonne National Laboratory and University of Minnesota.
Brett M. Averick, Richard G. Carter, and Jorge J. More'.

Permission has been given by Jorge Moré (after he emerged from underwater) to redistribute csrch on July 8th 2012 via e-mail.

[1] Jorge J. More and David J. Thuente, "Line Search Algorithms with Guaranteed Sufficient Decrease" ACM Transactions of Mathematical Software, Vol 20 , No. 3, September 1994, Pages 286-307
[2] MINPACK-2 source code http://ftp.mcs.anl.gov/pub/MINPACK-2/csrch/

See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    LineSearchMore94()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    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 stepInit, double stepMin, double stepMax)
    Initializes and resets the line search.
    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.
    void
    setConvergence(double ftol, double gtol)
    Specify convergence criteria for line search
    LineSearchMore94
    setConvergence(double ftol, double gtol, double xtol)
    Configures the 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.
    void
    setVerbose(@Nullable PrintStream out, @Nullable Set<String> configuration)
    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

  • Constructor Details

    • LineSearchMore94

      public LineSearchMore94()

  • Method Details

    • setConvergence

      public LineSearchMore94 setConvergence(double ftol, double gtol, double xtol)
      Configures the line search.
      Parameters:
      ftol - Tolerance for sufficient decrease. ftol > 0. Smaller value for loose tolerance. Try 1e-4
      gtol - Tolerance for curvature condition. gtol ≥ 0. Larger value for loose tolerance. Try 0.9
      xtol - Relative tolerance for acceptable step. xtol ≥ 0. Larger value for loose tolerance. Try 1e-4.
      Returns:
      Reference to this class to allow for command chaining.

    • setFunction

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

    • 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 - Tolerance for sufficient decrease. ftol > 0. Smaller value for loose tolerance. Try 1e-4
      gtol - Tolerance for curvature condition. gtol ≥ 0. Larger value for loose tolerance. Try 0.9

    • init

      public void init(double funcAtZero, double derivAtZero, double funcAtInit, double stepInit, 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)
      stepInit - Initial step size
      stepMin - Minimum allowed step.
      stepMax - Maximum allowed step.

    • iterate

      public boolean iterate() throws OptimizationException
      Description copied from interface: IterativeOptimization

      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 bookkeeping 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.
      Throws:
      OptimizationException

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

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

    • setVerbose

      public void setVerbose(@Nullable @Nullable PrintStream out, @Nullable @Nullable Set<String> configuration)
      Description copied from interface: VerbosePrint
      If set to a non-null output then extra information will be printed to the specified stream.
      Specified by:
      setVerbose in interface VerbosePrint
      Parameters:
      out - Stream that is printed to. Set to null to disable
      configuration - (Future use) Set which specifies flags that can be used to turn on and off different output

    • 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

    • 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