Package ffx.numerics.optimization

Class LBFGS

java.lang.Object

ffx.numerics.optimization.LBFGS

public class LBFGS
extends Object

This class implements the limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm for large-scale multidimensional unconstrained optimization problems.

Since:

1.0

Author:

Michael J. Schnieders
Derived from:
Robert Dodier's Java translation of original FORTRAN code by Jorge Nocedal.
J. Nocedal, "Updating Quasi-Newton Matrices with Limited Storage", Mathematics of Computation, 35, 773-782 (1980)
D. C. Lui and J. Nocedal, "On the Limited Memory BFGS Method for Large Scale Optimization", Mathematical Programming, 45, 503-528 (1989)
J. Nocedal and S. J. Wright, "Numerical Optimization", Springer-Verlag, New York, 1999, Section 9.1

Field Summary

Fields

Modifier and Type	Field	Description
static final double	DEFAULT_ANGLEMAX	The default maximum angle between search direction and gradient.
static final double	DEFAULT_CAPPA	Controls the accuracy of the line search.
static final int	DEFAULT_INTMAX	The default maximum number of interpolations during line search.
static final double	DEFAULT_SLOPEMAX	The default projected gradient above which step size is reduced.
static final double	DEFAULT_STEPMAX	This specifies the default upper bound for the step in the line search.
static final double	DEFAULT_STEPMIN	This specifies the default lower bound for the step in the line search.

Method Summary

Modifier and Type	Method	Description
static int	minimize(int n, int mSave, double[] x, double f, double[] g, double eps, int maxIterations, OptimizationInterface potential, OptimizationListener listener)	This method solves the unconstrained minimization problem
static int	minimize(int n, int mSave, double[] x, double f, double[] g, double eps, OptimizationInterface potential, OptimizationListener listener)	This method solves the unconstrained minimization problem

Methods inherited from class java.lang.Object

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

Field Details

DEFAULT_CAPPA

public static final double DEFAULT_CAPPA

Controls the accuracy of the line search.

If the function and gradient evaluations are inexpensive with respect to the cost of the iteration (which is sometimes the case when solving very large problems) it may be advantageous to set CAPPA to a small value.

A typical small value is 0.1.

Restriction: CAPPA should be greater than 1e-4.

See Also:

• Constant Field Values

DEFAULT_STEPMIN

public static final double DEFAULT_STEPMIN

This specifies the default lower bound for the step in the line search.

The default value of 1.0e-16 does not need to be modified unless the problem is extremely badly scaled (in which case the exponent should be increased).

See Also:

• Constant Field Values

DEFAULT_STEPMAX

public static final double DEFAULT_STEPMAX

This specifies the default upper bound for the step in the line search.

The default value of 5.0e0 does not need to be modified unless the problem is extremely badly scaled (in which case the exponent should be increased).

See Also:

• Constant Field Values

DEFAULT_SLOPEMAX

public static final double DEFAULT_SLOPEMAX

The default projected gradient above which step size is reduced.

See Also:

• Constant Field Values

DEFAULT_ANGLEMAX

public static final double DEFAULT_ANGLEMAX

The default maximum angle between search direction and gradient.

See Also:

• Constant Field Values

DEFAULT_INTMAX

public static final int DEFAULT_INTMAX

The default maximum number of interpolations during line search.

See Also:

• Constant Field Values

Method Details

minimize

public static int minimize(int n,
 int mSave,
 double[] x,
 double f,
 double[] g,
 double eps,
 int maxIterations,
 OptimizationInterface potential,
 @Nullable
 OptimizationListener listener)

This method solves the unconstrained minimization problem

     min f(x),    x = (x1,x2,...,x_n),
 

using the limited-memory BFGS method. The routine is especially effective on problems involving a large number of variables. In a typical iteration of this method an approximation Hk to the inverse of the Hessian is obtained by applying m BFGS updates to a diagonal matrix Hk0, using information from the previous m steps.

The user specifies the number m, which determines the amount of storage required by the routine.

The user is required to calculate the function value f and its gradient g .

The step length is determined at each iteration by means of the line search routine lineSearch, which is a slight modification of the routine CSRCH written by More and Thuente.

Parameters:

n - The number of variables in the minimization problem. Restriction: n > 0 .

mSave - The number of corrections used in the BFGS update. Values of mSave less than 3 are not recommended; large values of mSave will result in excessive computing time. 3 <= mSave <= 7 is recommended.

Restriction: mSave > 0.

x - On initial entry this must be set by the user to the values of the initial estimate of the solution vector. On exit, it contains the values of the variables at the best point found (usually a solution).

f - The value of the function f at the point x.

g - The components of the gradient g at the point x.

eps - Determines the accuracy with which the solution is to be found. The subroutine terminates when G RMS < EPS

maxIterations - Maximum number of optimization steps.

potential - Implements the Potential interface to supply function values and gradients.

listener - Implements the OptimizationListener interface and will be notified after each successful step.

Returns:

status code (0 = success, 1 = max iterations reached, -1 = failed)

Since:

1.0

minimize

public static int minimize(int n,
 int mSave,
 double[] x,
 double f,
 double[] g,
 double eps,
 OptimizationInterface potential,
 OptimizationListener listener)

This method solves the unconstrained minimization problem

     min f(x),    x = (x1,x2,...,x_n),
 

using the limited-memory BFGS method. The routine is especially effective on problems involving a large number of variables. In a typical iteration of this method an approximation Hk to the inverse of the Hessian is obtained by applying m BFGS updates to a diagonal matrix Hk0, using information from the previous m steps.

The user specifies the number m, which determines the amount of storage required by the routine.

The user is required to calculate the function value f and its gradient g .

The step length is determined at each iteration by means of the line search routine lineSearch, which is a slight modification of the routine CSRCH written by More and Thuente.

Parameters:

n - The number of variables in the minimization problem. Restriction: n > 0 .

mSave - The number of corrections used in the BFGS update. Values of mSave less than 3 are not recommended; large values of mSave will result in excessive computing time. 3 <= mSave <= 7 is recommended. * Restriction: mSave > 0.

x - On initial entry this must be set by the user to the values of the initial estimate of the solution vector. On exit, it contains the values of the variables at the best point found (usually a solution).

f - The value of the function f at the point x.

g - The components of the gradient g at the point x.

eps - Determines the accuracy with which the solution is to be found. The subroutine terminates when G RMS < EPS

potential - Implements the Potential interface to supply function values and gradients.

listener - Implements the OptimizationListener interface and will be notified after each successful step.

Returns:

status code (0 = success, -1 = failed)

Since:

1.0