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.

The L-BFGS algorithm is a quasi-Newton method that approximates the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm using a limited amount of computer memory. It is particularly well suited for optimization problems with a large number of variables.

The algorithm works by storing a sparse representation of the approximate inverse Hessian matrix, using only a few vectors that represent the approximation implicitly. Unlike the original BFGS method, L-BFGS stores only a few vectors that represent the approximation implicitly, which makes it particularly well suited for problems with many variables.

This implementation uses a line search procedure to ensure sufficient decrease in the objective function and to maintain positive definiteness of the Hessian approximation.

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 mSave, which determines the amount of storage required by the routine. This is the number of previous steps that will be used to approximate the Hessian. Larger values of mSave can lead to better convergence but require more memory and computation per iteration.

The algorithm works as follows:

1. Initialize with the current point, function value, and gradient
2. Compute a search direction using the L-BFGS approximation of the inverse Hessian
3. Perform a line search along this direction to find a new point with sufficient decrease in the function value
4. Update the L-BFGS approximation using the new point and gradient
5. Repeat until convergence or maximum iterations reached

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. This ensures that the function value decreases sufficiently and that the Hessian approximation remains positive definite.

Parameters:

n - The number of variables in the minimization problem. Must be positive.

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. Must be non-negative. If mSave is 0, the method will use steepest descent.

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). The array must have length at least n.

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

g - The components of the gradient g at the point x. On exit, it contains the gradient at the final point. The array must have length at least n.

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

maxIterations - Maximum number of optimization steps. Must be positive.

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

listener - Implements the OptimizationListener interface and will be notified after each successful step. Can be null, in which case progress will be logged but no callbacks will be made.

Returns:

status code:

• 0 = success (convergence achieved)
• 1 = maximum iterations reached without convergence
• -1 = optimization failed (e.g., line search failure, invalid inputs)

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