meshi.optimizers
Class LBFGS

java.lang.Object
  meshi.optimizers.Optimizer
      meshi.optimizers.Minimizer
          meshi.optimizers.LBFGS

public class LBFGS
extends Minimizer

This class implements a LBFGS minimizer according to the scheme in: Numerical Optimization by J. Nocendal & S. J. Wright, Springer 1999, pp 224-226. This class was written by Nir Kalisman as part of the MESHI package Kalisman et al. (2005) Bioinformatics 21:3931-3932 The BFGS algorithm (general) ---------------------------- In Newton minimizers an aproximation to the Hessian of the energy function at position Xk is calculated. Then finding the inverse of that Hessian (Hk), and solving the equation Pk = -Hk*grad(Xk) gives a good search direction Pk. Later, a line search procedure has to determine just how much to go in that direction (producing the scalar alpha_k). The new position is given by: Xk+1 = Xk + alpha_k*Pk.In the LBFGS method the inverse Hessian is not computed explicitly. Instead it is updated each step by the values of Pk and the new gradient. The updating formula is (t - transpose): Hk+1 = (I - Rk*Sk*Ykt)Hk(I - Rk*Yk*Skt) + Rk*Skt*Sk where: Sk = Xk+1 - Xk Yk = grad(Xk+1)-grad(Xk) Rk = 1/(Ykt*Sk) The LBFGS algorithm -------------------------------------------- To make the Light-Memory BFGS, we "cheat" by not maintaining the Hessian matrix. instead we keep a short history of m elements the vectors Yi, Si, and Ri (called curv in the code) as i = k-1..k-1-m. We use a storage (LinkedList) to store up to m last elements, and in case we pass m elements we discard the oldest element and insert the new one at the beginning of the list. We then calculate the search direction Pk using "two-loop recursion" algorithm (approximating Hk*grad(Xk)) directly from the elements we stored. We also approximate the Hk0 to be gamma*I so Hk0*grad is just gamma*grad. gamma is calculated by the algorithm provided (default) or is set to 1 (useGamma=false in the parameters) if so desired. For more detail see the mentioned book. General minimization parameters ------------------------------- - energy - pointer to an TotalEnergy object, where the energy function is. - tolerance - 1e-6 - Minimization stops when the magnitude of the maximal gradient component drops below tolerance. - maxSteps - 1000 - The maximal number of iteration steps allowed - reoprtEvery - 100 - The frequency of the minimization reports. Parameters Specific to the LBFGS algorithm ----------------------------------------- - allowedMaxR - 100*n - In some energy function scenerios the inverse Hessian approximation might become unstable and unrealiable. This paramter sets a upper limit on the curvature Rk. Higher values would lead to a new kick-start. This value should be somewhere in the range 100*n. - maxNumKickStarts - 3 - If the minimzer become unstable for some reason, it could be restarted from the current position. This parameter determined how many times this could happen before the minimization is aborted. - m - 20 - The storage size to use. 3-20 is the recomended value range. - useGamma - true - if to use gamma to get Hk0 (true) or to assume gamma=1 (false) Parameters specific to the Wolf conditions line search ------------------------------------------------------ The LBFGS algorithm requires a step length finder who finds a step length that also satisfies the Wolf conditions. See the help of this specific line search for explaination of what these conditions are. The parameters of this line search are: - c1,c2 - 1e-4,0.9 - The two paramters of the Wolf conditions. Must satisfy: 0

Nested Class Summary

private class

LBFGS.Element

Nested classes/interfaces inherited from class meshi.optimizers.Optimizer

Optimizer.OptimizerStatus

Field Summary

private int	allowedMaxR
(package private) double[]	alpha
(package private) double	beta
private int	bfgsError
private java.lang.String	bfgsErrorString
private double[][]	bufferCoordinates
private double	c1
private double	c2
private double[][]	coordinates
private static int	DEFAULT_ALLOWED_MAX_R_FACTOR
private static double	DEFAULT_C1
private static double	DEFAULT_C2
private static double	DEFAULT_EXTENDED_ALPHA_FACTOR_WOLF_SEARCH
private static double	DEFAULT_INIT_STEP_STEEPEST_DECENT
private static int	DEFAULT_M
private static int	DEFAULT_MAX_NUM_EVALUATIONS_WOLF_SEARCH
private static int	DEFAULT_MAX_NUM_KICK_STARTS
static int	DEFAULT_NUM_STEP_STEEPEST_DECENT
private static double	DEFAULT_STEP_SIZE_EXPENTION_STEEPEST_DECENT
private static double	DEFAULT_STEP_SIZE_REDUCTION_STEEPEST_DECENT
private static boolean	DEFAULT_USE_GAMA
(package private) LBFGS.Element	e
private double	extendAlphaFactorWolfSearch
private double[]	G
(package private) double	gama
(package private) double	initStepSteepestDecent
private int	iterationNum
private WolfConditionLineSearch	lineSearch
private int	m
private double	magnitudeForce
private int	maxNumEvaluationsWolfSearch
private int	maxNumKickStarts
private int	n
private int	numKickStarts
(package private) int	numStepsSteepestDecent
(package private) double[]	Q
(package private) double[]	R
private SteepestDecent	steepestDecent
(package private) double	stepSizeExpansionSteepestDecent
(package private) double	stepSizeReductionSteepestDecent
private java.util.LinkedList<LBFGS.Element>	storage
private boolean	useGama
private double[]	X

Fields inherited from class meshi.optimizers.Minimizer

MAX_KICKSTARTS, terminator, tolerance

Fields inherited from class meshi.optimizers.Optimizer

energy, maxSteps, optimizerTerminator, reportEvery

Constructor Summary

LBFGS(TotalEnergy energy, double tolerance, int maxSteps, int reportEvery)

LBFGS(TotalEnergy energy, double tolerance, int maxSteps, int reportEvery, int allowedMaxR, int maxNumKickStarts, int m, boolean useGama, double c1, double c2, double extendAlphaFactorWolfSearch, int maxNumEvaluationsWolfSearch, int numStepsSteepestDecent, double initStepSteepestDecent, double stepSizeReductionSteepestDecent, double stepSizeExpansionSteepestDecent)

Method Summary

protected void	init()
protected void	kickStart()
protected boolean	minimizationStep()
java.lang.String	toString()

Methods inherited from class meshi.optimizers.Minimizer

run, run

Methods inherited from class meshi.optimizers.Optimizer

energy

Methods inherited from class java.lang.Object

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

Field Detail

steepestDecent

private SteepestDecent steepestDecent

lineSearch

private WolfConditionLineSearch lineSearch

n

private int n

X

private double[] X

G

private double[] G

m

private int m

useGama

private boolean useGama

storage

private java.util.LinkedList<LBFGS.Element> storage

R

double[] R

Q

double[] Q

alpha

double[] alpha

beta

double beta

gama

double gama

e

LBFGS.Element e

coordinates

private double[][] coordinates

bufferCoordinates

private double[][] bufferCoordinates

magnitudeForce

private double magnitudeForce

iterationNum

private int iterationNum

bfgsError

private int bfgsError

bfgsErrorString

private java.lang.String bfgsErrorString

numKickStarts

private int numKickStarts

maxNumKickStarts

private int maxNumKickStarts

allowedMaxR

private int allowedMaxR

DEFAULT_ALLOWED_MAX_R_FACTOR

private static final int DEFAULT_ALLOWED_MAX_R_FACTOR

See Also:

Constant Field Values

DEFAULT_MAX_NUM_KICK_STARTS

private static final int DEFAULT_MAX_NUM_KICK_STARTS

See Also:

Constant Field Values

DEFAULT_USE_GAMA

private static final boolean DEFAULT_USE_GAMA

See Also:

Constant Field Values

DEFAULT_M

private static final int DEFAULT_M

See Also:

Constant Field Values

c1

private double c1

c2

private double c2

extendAlphaFactorWolfSearch

private double extendAlphaFactorWolfSearch

maxNumEvaluationsWolfSearch

private int maxNumEvaluationsWolfSearch

DEFAULT_C1

private static final double DEFAULT_C1

See Also:

Constant Field Values

DEFAULT_C2

private static final double DEFAULT_C2

See Also:

Constant Field Values

DEFAULT_EXTENDED_ALPHA_FACTOR_WOLF_SEARCH

private static final double DEFAULT_EXTENDED_ALPHA_FACTOR_WOLF_SEARCH

See Also:

Constant Field Values

DEFAULT_MAX_NUM_EVALUATIONS_WOLF_SEARCH

private static final int DEFAULT_MAX_NUM_EVALUATIONS_WOLF_SEARCH

See Also:

Constant Field Values

numStepsSteepestDecent

int numStepsSteepestDecent

initStepSteepestDecent

double initStepSteepestDecent

stepSizeReductionSteepestDecent

double stepSizeReductionSteepestDecent

stepSizeExpansionSteepestDecent

double stepSizeExpansionSteepestDecent

DEFAULT_NUM_STEP_STEEPEST_DECENT

public static final int DEFAULT_NUM_STEP_STEEPEST_DECENT

See Also:

Constant Field Values

DEFAULT_INIT_STEP_STEEPEST_DECENT

private static final double DEFAULT_INIT_STEP_STEEPEST_DECENT

See Also:

Constant Field Values

DEFAULT_STEP_SIZE_REDUCTION_STEEPEST_DECENT

private static final double DEFAULT_STEP_SIZE_REDUCTION_STEEPEST_DECENT

See Also:

Constant Field Values

DEFAULT_STEP_SIZE_EXPENTION_STEEPEST_DECENT

private static final double DEFAULT_STEP_SIZE_EXPENTION_STEEPEST_DECENT

See Also:

Constant Field Values

Constructor Detail

LBFGS

public LBFGS(TotalEnergy energy,
             double tolerance,
             int maxSteps,
             int reportEvery)

LBFGS

public LBFGS(TotalEnergy energy,
             double tolerance,
             int maxSteps,
             int reportEvery,
             int allowedMaxR,
             int maxNumKickStarts,
             int m,
             boolean useGama,
             double c1,
             double c2,
             double extendAlphaFactorWolfSearch,
             int maxNumEvaluationsWolfSearch,
             int numStepsSteepestDecent,
             double initStepSteepestDecent,
             double stepSizeReductionSteepestDecent,
             double stepSizeExpansionSteepestDecent)

Method Detail

init

protected void init()
             throws OptimizerException

Specified by:

init in class Minimizer

Throws:

OptimizerException

minimizationStep

protected boolean minimizationStep()
                            throws OptimizerException

Specified by:

minimizationStep in class Minimizer

Throws:

OptimizerException

kickStart

protected void kickStart()
                  throws OptimizerException

Specified by:

kickStart in class Minimizer

Throws:

OptimizerException

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object