org.ddogleg.optimization.impl

Class LineSearchFletcher86

java.lang.Object

org.ddogleg.optimization.impl.LineSearchFletcher86

All Implemented Interfaces:

java.io.Serializable, IterativeOptimization, LineSearch

public class LineSearchFletcher86
extends java.lang.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(x_k + α_k*p_k)

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

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
LineSearchFletcher86(double ftol, double gtol, double fmin, double t1, double t2, double t3)

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 initAlpha, 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	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

LineSearchFletcher86

public LineSearchFletcher86(double ftol,
                            double gtol,
                            double fmin,
                            double t1,
                            double t2,
                            double t3)

Parameters:

ftol - Controls required reduction in value. Try 1e-4

gtol - Controls decrease in derivative magnitude. Try 0.9

fmin - Minimum acceptable value of f(x). zero for least squares.

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

Method Detail

setFunction

public void setFunction(CoupledDerivative function)

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

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.

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.

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

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