org.omegahat.Numerics.Optimizers
Class OptimizerAlgorithmBFGS

java.lang.Object
  |
  +--org.omegahat.Numerics.Optimizers.OptimizerAlgorithmBasic
        |
        +--org.omegahat.Numerics.Optimizers.OptimizerAlgorithmBFGS

All Implemented Interfaces:

OptimizerAlgorithm

public class OptimizerAlgorithmBFGS

extends OptimizerAlgorithmBasic

The BFGS method for unconstrained optimization.

This is a quasi-newton method, requiring a model with derivates. It proceeds by developing an approximation to the inverse hessian matrix at the optimum, doing approximate one-dimensional optimizations at each search direction. This matrix, called H below and in most literature, is the key ingredient in this (and other) quasi-newton methods.

The key numerical properties of BFGS are: superlinear convergence for a wide mathematical range of functions provided accurate gradients are available; moderate accuracy in the final H estimate. A true newton method may be better if second derivatives are available and not too expensive, but only if the function is convex or not too far off and the method is made robust. Some other quasi-newton (symmetric rank-1, e.g.) may do a better job of estimating H at the optimum.

Field Summary

protected boolean	debug
protected double	gradientTol The tolerance for convergence, in terms of the norm of the gradient.
protected NumericMatrix	H The estimate of the information (inverse second derivative) matrix.
protected LineSearch	search The object defining the line search strategy for this optimizer algorithm.
protected LineStep	step
protected double	stepSize The default step size for the linear search.

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

arrayClass, arrayTemplate, gradient, hessian, matrixClass, matrixPackage, matrixTemplate, model, modelPointClass, modelPointTemplate, start, state

Constructor Summary

OptimizerAlgorithmBFGS()

Method Summary

boolean	getDebug() Accessor for debug field
double	getGradientTol() Accessor for gradientTol field
NumericMatrix	getH() Accessor for H field
LineSearch	getSearch() Accessor for search field
LineStep	getStep() Accessor for step field
double	getStepSize() Accessor for stepSize field
ModelPoint	initialize(double[] parameters, OptimizerIterator opt) Initialize the model with the specified starting parameter estimates and iterator.
ModelPoint	refine(ModelPoint theta, OptimizerIterator opt) The refine method for the BFGS quasi-Newton algorithm.
boolean	setDebug(boolean value) Accessor for setting debug field
double	setGradientTol(double value) Accessor for setting gradientTol field
NumericMatrix	setH(NumericMatrix value) Accessor for setting H field
LineSearch	setSearch(LineSearch value) Accessor for setting search field
LineStep	setStep(LineStep value) Accessor for setting step field
double	setStepSize(double value) Accessor for setting stepSize field
void	updateH(ModelPointNumericInt prev, LineStep current)

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

getArrayClass, getArrayTemplate, getMatrixClass, getMatrixPackage, getMatrixTemplate, getModel, getModelPointClass, getModelPointTemplate, getStart, getState, hasGradient, hasHessian, initialize, newArray, newMatrix, newModelPoint, setArrayClass, setArrayTemplate, setGradient, setHessian, setMatrixClass, setMatrixPackage, setMatrixPackage, setMatrixPackage, setMatrixTemplate, setModel, setModelPointClass, setModelPointTemplate, setStart, setStart, setState, wrapup

Methods inherited from class java.lang.Object

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

Field Detail

stepSize

protected double stepSize

The default step size for the linear search.

The BFGS algorithm defines this as 1.0, based on the theory that the algorithm tends to a Newton step, which in turn eventually succeeds with a quadratic approximation and unit step size.

To override this initially, set the stepSize property after the initialize method of this object has been called. To override the step size dynamically during iteration, add a listener to the optimizer and have the listener set the stepSize property, via opt.getAlgorithm().setStepSize(step).

H

protected NumericMatrix H

The estimate of the information (inverse second derivative) matrix.

An initial estimate of this matrix is recommended; if nothing else, an estimate by a diagonal matrix of rough estimates of the expected variances of the parameters might help. The default is an identity matrix.

search

protected LineSearch search

The object defining the line search strategy for this optimizer algorithm.

step

protected LineStep step

gradientTol

protected double gradientTol

The tolerance for convergence, in terms of the norm of the gradient.

Its default value is 1e-7. Only values > 0. are allowed, of course, and numbers down around the double-precision relative accuracy (say, < 1e-15) are unlikely to be achieved for most computations.

debug

protected boolean debug

Constructor Detail

OptimizerAlgorithmBFGS

public OptimizerAlgorithmBFGS()

Method Detail

getH

public NumericMatrix getH()

Accessor for H field

setH

public NumericMatrix setH(NumericMatrix value)

Accessor for setting H field

getSearch

public LineSearch getSearch()

Accessor for search field

setSearch

public LineSearch setSearch(LineSearch value)

Accessor for setting search field

getStep

public LineStep getStep()

Accessor for step field

setStep

public LineStep setStep(LineStep value)

Accessor for setting step field

getStepSize

public double getStepSize()

Accessor for stepSize field

setStepSize

public double setStepSize(double value)

Accessor for setting stepSize field

getGradientTol

public double getGradientTol()

Accessor for gradientTol field

setGradientTol

public double setGradientTol(double value)

Accessor for setting gradientTol field

getDebug

public boolean getDebug()

Accessor for debug field

setDebug

public boolean setDebug(boolean value)

Accessor for setting debug field

initialize

public ModelPoint initialize(double[] parameters,
                             OptimizerIterator opt)

Initialize the model with the specified starting parameter estimates and iterator. Generates the H matrix, if not already set up of the correct dimensions, and the step. Sets the H matrix to the identity. The default step has an initial step size of 1.

Overrides:

initialize in class OptimizerAlgorithmBasic

refine

public ModelPoint refine(ModelPoint theta,
                         OptimizerIterator opt)

The refine method for the BFGS quasi-Newton algorithm.

The method is to carry out a line search at the current point, in the direction - H . g, where g is the gradient of the current point. The default line search is from the LineSearchWolfe class. When the line search completes, the matrix H is updated by the updateH method.

updateH

public void updateH(ModelPointNumericInt prev,
                    LineStep current)