MLPACK
1.0.8
|
The generic L-BFGS optimizer, which uses a back-tracking line search algorithm to minimize a function. More...
Public Member Functions | |
L_BFGS (FunctionType &function, const size_t numBasis=5, const size_t maxIterations=0, const double armijoConstant=1e-4, const double wolfe=0.9, const double minGradientNorm=1e-10, const size_t maxLineSearchTrials=50, const double minStep=1e-20, const double maxStep=1e20) | |
Initialize the L-BFGS object. More... | |
double | ArmijoConstant () const |
Get the Armijo condition constant. More... | |
double & | ArmijoConstant () |
Modify the Armijo condition constant. More... | |
const FunctionType & | Function () const |
Return the function that is being optimized. More... | |
FunctionType & | Function () |
Modify the function that is being optimized. More... | |
size_t | MaxIterations () const |
Get the maximum number of iterations. More... | |
size_t & | MaxIterations () |
Modify the maximum number of iterations. More... | |
size_t | MaxLineSearchTrials () const |
Get the maximum number of line search trials. More... | |
size_t & | MaxLineSearchTrials () |
Modify the maximum number of line search trials. More... | |
double | MaxStep () const |
Return the maximum line search step size. More... | |
double & | MaxStep () |
Modify the maximum line search step size. More... | |
double | MinGradientNorm () const |
Get the minimum gradient norm. More... | |
double & | MinGradientNorm () |
Modify the minimum gradient norm. More... | |
const std::pair< arma::mat, double > & | MinPointIterate () const |
Return the point where the lowest function value has been found. More... | |
double | MinStep () const |
Return the minimum line search step size. More... | |
double & | MinStep () |
Modify the minimum line search step size. More... | |
size_t | NumBasis () const |
Get the memory size. More... | |
size_t & | NumBasis () |
Modify the memory size. More... | |
double | Optimize (arma::mat &iterate) |
Use L-BFGS to optimize the given function, starting at the given iterate point and finding the minimum. More... | |
double | Optimize (arma::mat &iterate, const size_t maxIterations) |
Use L-BFGS to optimize (minimize) the given function, starting at the given iterate point, and performing no more than the given maximum number of iterations (the class variable maxIterations is ignored for this run, but not modified). More... | |
double | Wolfe () const |
Get the Wolfe parameter. More... | |
double & | Wolfe () |
Modify the Wolfe parameter. More... | |
Private Member Functions | |
double | ChooseScalingFactor (const size_t iterationNum, const arma::mat &gradient) |
Calculate the scaling factor, gamma, which is used to scale the Hessian approximation matrix. More... | |
double | Evaluate (const arma::mat &iterate) |
Evaluate the function at the given iterate point and store the result if it is a new minimum. More... | |
bool | GradientNormTooSmall (const arma::mat &gradient) |
Check to make sure that the norm of the gradient is not smaller than 1e-5. More... | |
bool | LineSearch (double &functionValue, arma::mat &iterate, arma::mat &gradient, const arma::mat &searchDirection) |
Perform a back-tracking line search along the search direction to calculate a step size satisfying the Wolfe conditions. More... | |
void | SearchDirection (const arma::mat &gradient, const size_t iterationNum, const double scalingFactor, arma::mat &searchDirection) |
Find the L-BFGS search direction. More... | |
void | UpdateBasisSet (const size_t iterationNum, const arma::mat &iterate, const arma::mat &oldIterate, const arma::mat &gradient, const arma::mat &oldGradient) |
Update the y and s matrices, which store the differences between the iterate and old iterate and the differences between the gradient and the old gradient, respectively. More... | |
Private Attributes | |
double | armijoConstant |
Parameter for determining the Armijo condition. More... | |
FunctionType & | function |
Internal reference to the function we are optimizing. More... | |
size_t | maxIterations |
Maximum number of iterations. More... | |
size_t | maxLineSearchTrials |
Maximum number of trials for the line search. More... | |
double | maxStep |
Maximum step of the line search. More... | |
double | minGradientNorm |
Minimum gradient norm required to continue the optimization. More... | |
std::pair< arma::mat, double > | minPointIterate |
Best point found so far. More... | |
double | minStep |
Minimum step of the line search. More... | |
arma::mat | newIterateTmp |
Position of the new iterate. More... | |
size_t | numBasis |
Size of memory for this L-BFGS optimizer. More... | |
arma::cube | s |
Stores all the s matrices in memory. More... | |
double | wolfe |
Parameter for detecting the Wolfe condition. More... | |
arma::cube | y |
Stores all the y matrices in memory. More... | |
The generic L-BFGS optimizer, which uses a back-tracking line search algorithm to minimize a function.
The parameters for the algorithm (number of memory points, maximum step size, and so forth) are all configurable via either the constructor or standalone modifier functions. A function which can be optimized by this class must implement the following methods:
mlpack::optimization::L_BFGS< FunctionType >::L_BFGS | ( | FunctionType & | function, |
const size_t | numBasis = 5 , |
||
const size_t | maxIterations = 0 , |
||
const double | armijoConstant = 1e-4 , |
||
const double | wolfe = 0.9 , |
||
const double | minGradientNorm = 1e-10 , |
||
const size_t | maxLineSearchTrials = 50 , |
||
const double | minStep = 1e-20 , |
||
const double | maxStep = 1e20 |
||
) |
Initialize the L-BFGS object.
Store a reference to the function we will be optimizing and set the size of the memory for the algorithm. There are many parameters that can be set for the optimization, but default values are given for each of them.
function | Instance of function to be optimized. |
numBasis | Number of memory points to be stored (default 5). |
maxIterations | Maximum number of iterations for the optimization (default 0 – may run indefinitely). |
armijoConstant | Controls the accuracy of the line search routine for determining the Armijo condition. |
wolfe | Parameter for detecting the Wolfe condition. |
minGradientNorm | Minimum gradient norm required to continue the optimization. |
maxLineSearchTrials | The maximum number of trials for the line search (before giving up). |
minStep | The minimum step of the line search. |
maxStep | The maximum step of the line search. |
|
inline |
|
inline |
|
private |
Calculate the scaling factor, gamma, which is used to scale the Hessian approximation matrix.
See method M3 in Section 4 of Liu and Nocedal (1989).
|
private |
Evaluate the function at the given iterate point and store the result if it is a new minimum.
|
inline |
|
inline |
|
private |
Check to make sure that the norm of the gradient is not smaller than 1e-5.
Currently that value is not configurable.
|
private |
Perform a back-tracking line search along the search direction to calculate a step size satisfying the Wolfe conditions.
The parameter iterate will be modified if the method is successful.
functionValue | Value of the function at the initial point |
iterate | The initial point to begin the line search from |
gradient | The gradient at the initial point |
searchDirection | A vector specifying the search direction |
stepSize | Variable the calculated step size will be stored in |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
const std::pair<arma::mat, double>& mlpack::optimization::L_BFGS< FunctionType >::MinPointIterate | ( | ) | const |
Return the point where the lowest function value has been found.
|
inline |
|
inline |
|
inline |
|
inline |
double mlpack::optimization::L_BFGS< FunctionType >::Optimize | ( | arma::mat & | iterate | ) |
Use L-BFGS to optimize the given function, starting at the given iterate point and finding the minimum.
The maximum number of iterations is set in the constructor (or with MaxIterations()). Alternately, another overload is provided which takes a maximum number of iterations as a parameter. The given starting point will be modified to store the finishing point of the algorithm, and the final objective value is returned.
iterate | Starting point (will be modified). |
double mlpack::optimization::L_BFGS< FunctionType >::Optimize | ( | arma::mat & | iterate, |
const size_t | maxIterations | ||
) |
Use L-BFGS to optimize (minimize) the given function, starting at the given iterate point, and performing no more than the given maximum number of iterations (the class variable maxIterations is ignored for this run, but not modified).
The given starting point will be modified to store the finishing point of the algorithm, and the final objective value is returned.
iterate | Starting point (will be modified). |
maxIterations | Maximum number of iterations (0 specifies no limit). |
|
private |
Find the L-BFGS search direction.
gradient | The gradient at the current point |
iteration_num | The iteration number |
scaling_factor | Scaling factor to use (see ChooseScalingFactor_()) |
search_direction | Vector to store search direction in |
|
private |
Update the y and s matrices, which store the differences between the iterate and old iterate and the differences between the gradient and the old gradient, respectively.
iterationNum | Iteration number |
iterate | Current point |
oldIterate | Point at last iteration |
gradient | Gradient at current point (iterate) |
oldGradient | Gradient at last iteration point (oldIterate) |
|
inline |
|
inline |
|
private |
Parameter for determining the Armijo condition.
Definition at line 173 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::ArmijoConstant().
|
private |
|
private |
Maximum number of iterations.
Definition at line 171 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::MaxIterations().
|
private |
Maximum number of trials for the line search.
Definition at line 179 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::MaxLineSearchTrials().
|
private |
Maximum step of the line search.
Definition at line 183 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::MaxStep().
|
private |
Minimum gradient norm required to continue the optimization.
Definition at line 177 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::MinGradientNorm().
|
private |
|
private |
Minimum step of the line search.
Definition at line 181 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::MinStep().
|
private |
|
private |
Size of memory for this L-BFGS optimizer.
Definition at line 169 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::NumBasis().
|
private |
|
private |
Parameter for detecting the Wolfe condition.
Definition at line 175 of file lbfgs.hpp.
Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< mlpack::optimization::LRSDP > >::Wolfe().
|
private |