org.omegahat.Numerics.Optimizers
Class LineSearchWolfe

java.lang.Object
  |
  +--org.omegahat.Numerics.Optimizers.LineSearchBasic
        |
        +--org.omegahat.Numerics.Optimizers.LineSearchWolfe

All Implemented Interfaces:

LineSearch

public class LineSearchWolfe

extends LineSearchBasic

a line search algorithm that finds a point with good enough improvement and slope.

Specifically, the point satisfies the ``strong Wolfe'' conditions: the new value at the new point must lie below a line drawn from the original point with chosen slope, and the slope at the new point in the chosen direction must be shallow enough to accept the point as an approximate minimum. Slopes are expressed as fractions of the slope at the original point in the chosen direction (i.e., of the inner product of the gradient and the direction at the original point). The two thresholds are valueTol and slopeTol. See, e.g., Nocedal and Wright, ``Numerical Optimization'', section 3.1. These conditions support some convergence theory for descent direction methods, particularly for quasi-Newton methods.

Field Summary

protected double	expansionFactor The expansion factor allowed on initial expansion steps (default 4.).
protected LineStep	high The current upper bound for the optimum.
protected boolean	interpolatingStage
protected LineStep	low the current lower bound for the optimium.
protected double	maxStep The maximum step length to be taken, as a multiple of the initial step.
protected LineStep	prev the previous step taken in the search.
protected double	slopeTol Tolerance for the slope, default 0.9
protected double	valueTol The tolerance for the function value, default 1.e-4.

Fields inherited from class org.omegahat.Numerics.Optimizers.LineSearchBasic

debug, direction, evaluations, maxEvaluations, origin, state, stepMax, stepMin

Fields inherited from interface org.omegahat.Numerics.Optimizers.LineSearch

CONTINUE, EXCEPTION, SUCCESSFUL, TOO_LARGE, TOO_MANY, TOO_NARROW, TOO_SMALL

Constructor Summary

LineSearchWolfe()
Create an empty object.

LineSearchWolfe(ModelPointNumericInt p)
Create the line search object and initialize its internal data to correspond to the model point.

Method Summary

boolean	continueIteration(LineStep step) Tests whether the search should continue.
LineStep	emergency(LineStep step, java.lang.Error e) An emergency operation, taken when an evaluation generates an error.
protected double	extrapolateStep(LineStep step)
double	getExpansionFactor() Accessor for expansionFactor field
LineStep	getHigh() Accessor for high field
boolean	getInterpolatingStage() Accessor for interpolatingStage field
LineStep	getLow() Accessor for low field
double	getMaxStep() Accessor for maxStep field
LineStep	getPrev() Accessor for prev field
double	getSlopeTol() Accessor for slopeTol field
double	getValueTol() Accessor for valueTol field
LineStep	initialize(ModelPointNumericInt theta, NumericArray p, double step) Initialize the search object, typically with a new direction from the current estimate.
protected boolean	interpolates(double x, double xl, double xh)
protected double	interpolateStep(LineStep step)
void	make(ModelPointNumericInt p) create the internal model points to correspond to the data in p.
protected static double	maxAbs(double a, double b, double c)
LineStep	refineStep(LineStep step) Evaluate a proposed step, and return the proposed next step.
double	setExpansionFactor(double value) Accessor for setting expansionFactor field
protected LineStep	setHigh(LineStep value) Accessor for setting high field
boolean	setInterpolatingStage(boolean value) Accessor for setting interpolatingStage field
protected LineStep	setLow(LineStep value) Accessor for setting low field
double	setMaxStep(double value) Accessor for setting maxStep field
protected LineStep	setPrev(LineStep value) Accessor for setting prev field
double	setSlopeTol(double value) Accessor for setting slopeTol field
double	setValueTol(double value) Accessor for setting valueTol field
boolean	testForInterpolation(LineStep step) Test this step for a valid interpolation, so the algorithm can switch into its interpolating stage.

Methods inherited from class org.omegahat.Numerics.Optimizers.LineSearchBasic

getDebug, getDirection, getEvaluations, getMaxEvaluations, getOrigin, getState, getStepMax, getStepMin, incrementCount, setDebug, setDirection, setEvaluations, setMaxEvaluations, setOrigin, setState, setStepMax, setStepMin

Methods inherited from class java.lang.Object

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

Field Detail

valueTol

protected double valueTol

The tolerance for the function value, default 1.e-4.

slopeTol

protected double slopeTol

Tolerance for the slope, default 0.9

expansionFactor

protected double expansionFactor

The expansion factor allowed on initial expansion steps (default 4.).

maxStep

protected double maxStep

The maximum step length to be taken, as a multiple of the initial step.

The default is 1e20, but how big the bound should be is a difficult question to answer in general. The nasty cases are that the initial step estimate is very much too small or that the function has no lower bound in this direction. In the latter case you are sunk, since the model you posed has no (global) minimum.

prev

protected LineStep prev

the previous step taken in the search.

low

protected LineStep low

the current lower bound for the optimium.

high

protected LineStep high

The current upper bound for the optimum.

interpolatingStage

protected boolean interpolatingStage

Constructor Detail

LineSearchWolfe

public LineSearchWolfe(ModelPointNumericInt p)

Create the line search object and initialize its internal data to correspond to the model point.

LineSearchWolfe

public LineSearchWolfe()

Create an empty object. A call to make will be needed before the search can be carried out.

Method Detail

getValueTol

public double getValueTol()

Accessor for valueTol field

setValueTol

public double setValueTol(double value)

Accessor for setting valueTol field

getSlopeTol

public double getSlopeTol()

Accessor for slopeTol field

setSlopeTol

public double setSlopeTol(double value)

Accessor for setting slopeTol field

getExpansionFactor

public double getExpansionFactor()

Accessor for expansionFactor field

setExpansionFactor

public double setExpansionFactor(double value)

Accessor for setting expansionFactor field

getMaxStep

public double getMaxStep()

Accessor for maxStep field

setMaxStep

public double setMaxStep(double value)

Accessor for setting maxStep field

getPrev

public LineStep getPrev()

Accessor for prev field

setPrev

protected LineStep setPrev(LineStep value)

Accessor for setting prev field

getLow

public LineStep getLow()

Accessor for low field

setLow

protected LineStep setLow(LineStep value)

Accessor for setting low field

getHigh

public LineStep getHigh()

Accessor for high field

setHigh

protected LineStep setHigh(LineStep value)

Accessor for setting high field

getInterpolatingStage

public boolean getInterpolatingStage()

Accessor for interpolatingStage field

setInterpolatingStage

public boolean setInterpolatingStage(boolean value)

Accessor for setting interpolatingStage field

refineStep

public LineStep refineStep(LineStep step)

Evaluate a proposed step, and return the proposed next step.

The convergence field of the step object may be set either by the continueIteration method or by the methods that extrapolate or interpolate (if the proposed new step would violate the constraints on the search).

extrapolateStep

protected double extrapolateStep(LineStep step)

interpolateStep

protected double interpolateStep(LineStep step)

maxAbs

protected static double maxAbs(double a,
                               double b,
                               double c)

interpolates

protected boolean interpolates(double x,
                               double xl,
                               double xh)

testForInterpolation

public boolean testForInterpolation(LineStep step)

Test this step for a valid interpolation, so the algorithm can switch into its interpolating stage.

continueIteration

public boolean continueIteration(LineStep step)

Tests whether the search should continue. If not, sets the internal state to a non-zero value, e.g., SUCCESSFUL in case of numeric convergence by the criterion of the search, or any of a number of states indicating failure.

Overrides:

continueIteration in class LineSearchBasic

initialize

public LineStep initialize(ModelPointNumericInt theta,
                           NumericArray p,
                           double step)

Initialize the search object, typically with a new direction from the current estimate.

If theta is an evaluated model point, it is taken to be the previous step, for computing the interpolations, etc. The interpolatingStage flag is set to false.

Overrides:

initialize in class LineSearchBasic

emergency

public LineStep emergency(LineStep step,
                          java.lang.Error e)

An emergency operation, taken when an evaluation generates an error.

NOT IMPLEMENTED YET!

What happens depends on the stage. In the extrapolation stage, we know that we have taken getEvaluations() expansion steps, so the current step is expansionFactor^(getEvaluations()-1) times the initial step. The previous step succeeded, so we can move back towards that step, searching for a successful point.

An exception in the interpolation phase is more troubling, since it implies a discontinuity in the function in the interval of interpolation. Chances of anything succeeding in this case are not good, but we basically try some alternative interpolations in hopes of hitting a valid interval.

make

public void make(ModelPointNumericInt p)

create the internal model points to correspond to the data in p.