jsat.math.optimization

Class LBFGS

java.lang.Object

jsat.math.optimization.LBFGS

All Implemented Interfaces:

Optimizer2

public class LBFGS
extends Object
implements Optimizer2

Implementation of the Limited memory variant of BFGS. It uses a history of m items to solve n dimension problems with O(m n) work per iteration.

Author:

Edward Raff

Constructor Summary

Constructors

Constructor and Description
LBFGS() Creates a new L-BFGS optimization object that uses a maximum of 500 iterations and a Backtracking line search.
LBFGS(int m) Creates a new L-BFGS optimization object that uses a maximum of 500 iterations and a Backtracking line search.
LBFGS(int m, int maxIterations, LineSearch lineSearch) Creates a new L-BFGS optimization object

Method Summary

Modifier and Type	Method and Description
LBFGS	clone()
LineSearch	getLineSearch() Returns the line search method used at each iteration
int	getM() Returns the number of history items that will be used
int	getMaximumIterations() Returns the maximum number of iterations to perform
boolean	isInftNormCriterion() Returns whether or not the infinity norm (true) or 2 norm (false) is used to determine convergence.
void	optimize(double tolerance, Vec w, Vec x0, Function f, FunctionVec fp, FunctionVec fpp) Attempts to optimize the given function by finding the value of w that will minimize the value returned by f(w), using w = x0 as an initial starting point.
void	optimize(double tolerance, Vec w, Vec x0, Function f, FunctionVec fp, FunctionVec fpp, ExecutorService ex) Attempts to optimize the given function by finding the value of w that will minimize the value returned by f(w), using w = x0 as an initial starting point.
void	setInftNormCriterion(boolean inftNormCriterion) By default the infinity norm is used to judge convergence.
void	setLineSearch(LineSearch lineSearch) Sets the line search method used at each iteration
void	setM(int m) Sets the number of history items to keep that are used to approximate the Hessian of the problem
void	setMaximumIterations(int iterations) Sets the maximum number of iterations allowed for the optimization method
static void	twoLoopHp(Vec x_grad, List<Double> rho, List<Vec> s, List<Vec> y, Vec q, double[] alphas) See Algorithm 7.4 (L-BFGS two-loop recursion).

Methods inherited from class java.lang.Object

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

Constructor Detail

LBFGS

public LBFGS()

Creates a new L-BFGS optimization object that uses a maximum of 500 iterations and a Backtracking line search. A history of 10 items will be used

LBFGS

public LBFGS(int m)

Creates a new L-BFGS optimization object that uses a maximum of 500 iterations and a Backtracking line search.

Parameters:

m - the number of history items

LBFGS

public LBFGS(int m,
             int maxIterations,
             LineSearch lineSearch)

Creates a new L-BFGS optimization object

Parameters:

m - the number of history items

maxIterations - the maximum number of iterations before stopping

lineSearch - the line search method to use for optimization

Method Detail

twoLoopHp

public static void twoLoopHp(Vec x_grad,
                             List<Double> rho,
                             List<Vec> s,
                             List<Vec> y,
                             Vec q,
                             double[] alphas)

See Algorithm 7.4 (L-BFGS two-loop recursion).

Parameters:

x_grad - the initial value ∇ f_k

rho -

s -

y -

q - the location to store the value of H_k ∇ f_k

alphas - temp space to do work, should be as large as the number of history vectors

optimize

public void optimize(double tolerance,
                     Vec w,
                     Vec x0,
                     Function f,
                     FunctionVec fp,
                     FunctionVec fpp)

Description copied from interface: Optimizer2

Attempts to optimize the given function by finding the value of w that will minimize the value returned by f(w), using w = x₀ as an initial starting point.

Specified by:

optimize in interface Optimizer2

Parameters:

tolerance - the value that the gradient norm must be less than to consider converged

w - the the location to store the final solution

x0 - the initial guess for the solution. This value will not be changed, and intermediate matrices will be created as the same type.

f - the objective function to minimizer

fp - the derivative of the objective function, may be null depending on the optimizer

fpp - the Hessian of the objective function, may be null depending on the optimizer

optimize

public void optimize(double tolerance,
                     Vec w,
                     Vec x0,
                     Function f,
                     FunctionVec fp,
                     FunctionVec fpp,
                     ExecutorService ex)

Description copied from interface: Optimizer2

Attempts to optimize the given function by finding the value of w that will minimize the value returned by f(w), using w = x₀ as an initial starting point.

Specified by:

optimize in interface Optimizer2

Parameters:

tolerance - the value that the gradient norm must be less than to consider converged

w - the the location to store the final solution

x0 - the initial guess for the solution. This value will not be changed, and intermediate matrices will be created as the same type.

f - the objective function to minimizer

fp - the derivative of the objective function, may be null depending on the optimizer

fpp - the Hessian of the objective function, may be null depending on the optimizer

ex - the source of threads for parallel computation, may be null to perform serial computation.

setInftNormCriterion

public void setInftNormCriterion(boolean inftNormCriterion)

By default the infinity norm is used to judge convergence. If set to false, the 2 norm will be used instead.

Parameters:

inftNormCriterion -

isInftNormCriterion

public boolean isInftNormCriterion()

Returns whether or not the infinity norm (true) or 2 norm (false) is used to determine convergence.

Returns:

true if the infinity norm is in use, false for the 2 norm

setM

public void setM(int m)

Sets the number of history items to keep that are used to approximate the Hessian of the problem

Parameters:

m - the number of history items to keep

getM

public int getM()

Returns the number of history items that will be used

Returns:

the number of history items that will be used

setLineSearch

public void setLineSearch(LineSearch lineSearch)

Sets the line search method used at each iteration

Parameters:

lineSearch - the line search method used at each iteration

getLineSearch

public LineSearch getLineSearch()

Returns the line search method used at each iteration

Returns:

the line search method used at each iteration

setMaximumIterations

public void setMaximumIterations(int iterations)

Description copied from interface: Optimizer2

Sets the maximum number of iterations allowed for the optimization method

Specified by:

setMaximumIterations in interface Optimizer2

Parameters:

iterations - the maximum number of iterations to perform

getMaximumIterations

public int getMaximumIterations()

Description copied from interface: Optimizer2

Returns the maximum number of iterations to perform

Specified by:

getMaximumIterations in interface Optimizer2

Returns:

the maximum number of iterations to perform

clone

public LBFGS clone()

Specified by:

clone in interface Optimizer2

Overrides:

clone in class Object