org.ddogleg.optimization.impl

Class LineSearchMore94

java.lang.Object

org.ddogleg.optimization.impl.LineSearchMore94

All Implemented Interfaces:

java.io.Serializable, IterativeOptimization, LineSearch

public class LineSearchMore94
extends java.lang.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:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
LineSearchMore94()

Method Summary

Modifier and Type	Method and Description
double	getFunction() Function value at the current step
double	getStep() Returns the current approximate solution for the line search
java.lang.String	getWarning() Provides feed back if something went wrong, but still produced a solution.
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.
LineSearchMore94	setConvergence(double ftol, double gtol, double xtol) Configures the line search.
void	setFunction(CoupledDerivative function) Sets the function being optimized.

Methods inherited from class java.lang.Object

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

Constructor Detail

LineSearchMore94

public LineSearchMore94()

Method Detail

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 1e-3

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)

Description copied from interface: LineSearch

Sets the function being optimized.

Specified by:

setFunction in interface LineSearch

Parameters:

function - Line search function and derivative

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

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.

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

getWarning

public java.lang.String getWarning()

Description copied from interface: IterativeOptimization

Provides feed back if something went wrong, but still produced a solution. If there is no message then null is returned. The meaning and type of messages are implementation specific.

Specified by:

getWarning in interface IterativeOptimization

Returns:

Additional info on the computed solution.

getFunction

public double getFunction()

Description copied from interface: LineSearch

Function value at the current step

Specified by:

getFunction 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