meshi.optimizers
Class BFGS

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

public class BFGS
extends Minimizer

This class implements a BFGS minimizer according to the scheme in: Numerical Optimization by J. Nocendal & S. J. Wright, Springer 1999, pp 193-201. 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 BFGS 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 BFGS algorithm (specific implementation) -------------------------------------------- 1)To run this minimizer: a) Instantiate this class with the desired minimization parameters. b) Put the initial coordinates in the 'coordinates' variable at the 'energy' class. c) Activate BFGS.run(). d) Check for thrown errors to see if the minimization succeeded. e) The minimized position is in the 'coordinates' variable at the 'energy' class. 2)This implementation creates a matrix (of doubles) whos size is 0.5*(n^2). Where n is the number of variable to minimze. If n is large the memory load might be very great. 3)The inverse Hessian matrix (H) which is symmetric is stored as a linear vector in the following way (to save space): H(1,1:n) followed by H(2,2:n) followed by H(3,3:n) and so on until H(n,n). 4)The BFGS algorithm is generally robust and efficient. With certain energy functions it might, however, become unstable. The algorithm checks for instabilities during the run (the thresholds to some of the instabilities are given by the parameters in the constructor). If such instability is discovered, the algorithm try to recover by changing to steepest descent algorithm for a few steps (kick-start). If this option is activated too much it is a sign of a deeper problem, and an informative error message is thrown. 5)Good default values are given after the parameter name. 6)The initial guess to the Hessian is the unity matrix. Better guesses are possible (see the reference). 7) To test this minimizer you can run the "BFGSTest.java" program which minimize a cluster of 5 Helium atoms using this minimzer. 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 BFGS algorithm ----------------------------------------- - allowedMaxH - (10-100)*n - In some energy function scenerios the inverse Hessian approximation might become unstable and unrealiable, by having huge numbers in the H entries. This paramter sets a upper limit on the matrix H entries. Higher values would lead to a new kick-start. This value should be somewhere in the range (10-100)*n (lower is more conservative). - 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. Parameters specific to the Wolf conditions line search ------------------------------------------------------ The BFGS 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

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

Optimizer.OptimizerStatus

Field Summary

private double[]	A
private double	allowedMaxH
private int	bfgsError
private java.lang.String	bfgsErrorString
private double[][]	bufferCoordinates
private double	c1
private double	c2
private double[][]	coordinates
private static double	DEFAULT_ALLOWED_MAX_H_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_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 double	extendAlphaFactorWolfSearch
private double[]	G
private double[]	H
(package private) double	initStepSteepestDecent
private int	iterationNum
private WolfConditionLineSearch	lineSearch
private double	magnitudeForce
private int	MAX_NUM_VARIABLES
private static int	maxNumEvaluationsWolfSearch
private int	maxNumKickStarts
private int	n
(package private) int	np
private int	numKickStarts
(package private) int	numStepsSteepestDecent
private double[]	P
private double[]	S
private SteepestDecent	steepestDecent
(package private) double	stepSizeExpansionSteepestDecent
(package private) double	stepSizeReductionSteepestDecent
private double[]	X
private double[]	Y

Fields inherited from class meshi.optimizers.Minimizer

MAX_KICKSTARTS, terminator, tolerance

Fields inherited from class meshi.optimizers.Optimizer

energy, maxSteps, optimizerTerminator, reportEvery

Constructor Summary

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

BFGS(TotalEnergy energy, double tolerance, int maxIterations, int reportEvery, double allowedMaxH, int maxNumKickStarts, double c1, double c2, double extendAlphaFactorWolfSearch, int maxNumEvaluationsWolfSearch, int numStepsSteepestDecent, double initStepSteepestDecent, double stepSizeReductionSteepestDecent, double stepSizeExpansionSteepestDecent)

Method Summary

static double	abs(double a)
private void	getParameters(double allowedMaxH, int maxNumKickStarts, double c1, double c2, double extendAlphaFactorWolfSearch, int maxNumEvaluationsWolfSearch, int numStepsSteepestDecent, double initStepSteepestDecent, double stepSizeReductionSteepestDecent, double stepSizeExpansionSteepestDecent)
protected void	init()
private void	initHessian()
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

np

int np

H

private double[] H

P

private double[] P

X

private double[] X

G

private double[] G

S

private double[] S

Y

private double[] Y

A

private double[] A

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

allowedMaxH

private double allowedMaxH

maxNumKickStarts

private int maxNumKickStarts

DEFAULT_ALLOWED_MAX_H_FACTOR

private static final double DEFAULT_ALLOWED_MAX_H_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

c1

private double c1

c2

private double c2

extendAlphaFactorWolfSearch

private double extendAlphaFactorWolfSearch

maxNumEvaluationsWolfSearch

private static 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

MAX_NUM_VARIABLES

private final int MAX_NUM_VARIABLES

See Also:

Constant Field Values

Constructor Detail

BFGS

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

BFGS

public BFGS(TotalEnergy energy,
            double tolerance,
            int maxIterations,
            int reportEvery,
            double allowedMaxH,
            int maxNumKickStarts,
            double c1,
            double c2,
            double extendAlphaFactorWolfSearch,
            int maxNumEvaluationsWolfSearch,
            int numStepsSteepestDecent,
            double initStepSteepestDecent,
            double stepSizeReductionSteepestDecent,
            double stepSizeExpansionSteepestDecent)

Method Detail

getParameters

private void getParameters(double allowedMaxH,
                           int maxNumKickStarts,
                           double c1,
                           double c2,
                           double extendAlphaFactorWolfSearch,
                           int maxNumEvaluationsWolfSearch,
                           int numStepsSteepestDecent,
                           double initStepSteepestDecent,
                           double stepSizeReductionSteepestDecent,
                           double stepSizeExpansionSteepestDecent)

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

initHessian

private void initHessian()

abs

public static double abs(double a)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object