mlpack::optimization::L_BFGS< FunctionType > Class Template Reference

The generic L-BFGS optimizer, which uses a back-tracking line search algorithm to minimize a function. More...

Inheritance diagram for mlpack::optimization::L_BFGS< FunctionType >:
Inheritance graph
[legend]
Collaboration diagram for mlpack::optimization::L_BFGS< FunctionType >:
Collaboration graph
[legend]

List of all members.

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.
double & ArmijoConstant ()
 Modify the Armijo condition constant.
double ArmijoConstant () const
 Get the Armijo condition constant.
FunctionType & Function ()
 Modify the function that is being optimized.
const FunctionType & Function () const
 Return the function that is being optimized.
size_t & MaxIterations ()
 Modify the maximum number of iterations.
size_t MaxIterations () const
 Get the maximum number of iterations.
size_t & MaxLineSearchTrials ()
 Modify the maximum number of line search trials.
size_t MaxLineSearchTrials () const
 Get the maximum number of line search trials.
double & MaxStep ()
 Modify the maximum line search step size.
double MaxStep () const
 Return the maximum line search step size.
double & MinGradientNorm ()
 Modify the minimum gradient norm.
double MinGradientNorm () const
 Get the minimum gradient norm.
const std::pair< arma::mat,
double > & 
MinPointIterate () const
 Return the point where the lowest function value has been found.
double & MinStep ()
 Modify the minimum line search step size.
double MinStep () const
 Return the minimum line search step size.
size_t & NumBasis ()
 Modify the memory size.
size_t NumBasis () const
 Get the memory size.
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).
double Optimize (arma::mat &iterate)
 Use L-BFGS to optimize the given function, starting at the given iterate point and finding the minimum.
double & Wolfe ()
 Modify the Wolfe parameter.
double Wolfe () const
 Get the Wolfe parameter.

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.
double Evaluate (const arma::mat &iterate)
 Evaluate the function at the given iterate point and store the result if it is a new minimum.
bool GradientNormTooSmall (const arma::mat &gradient)
 Check to make sure that the norm of the gradient is not smaller than 1e-5.
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.
void SearchDirection (const arma::mat &gradient, const size_t iterationNum, const double scalingFactor, arma::mat &searchDirection)
 Find the L-BFGS search direction.
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.

Private Attributes

double armijoConstant
 Parameter for determining the Armijo condition.
FunctionType & function
 Internal reference to the function we are optimizing.
size_t maxIterations
 Maximum number of iterations.
size_t maxLineSearchTrials
 Maximum number of trials for the line search.
double maxStep
 Maximum step of the line search.
double minGradientNorm
 Minimum gradient norm required to continue the optimization.
std::pair< arma::mat, double > minPointIterate
 Best point found so far.
double minStep
 Minimum step of the line search.
arma::mat newIterateTmp
 Position of the new iterate.
size_t numBasis
 Size of memory for this L-BFGS optimizer.
arma::cube s
 Stores all the s matrices in memory.
double wolfe
 Parameter for detecting the Wolfe condition.
arma::cube y
 Stores all the y matrices in memory.

Detailed Description

template<typename FunctionType>
class mlpack::optimization::L_BFGS< FunctionType >

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:

Definition at line 44 of file lbfgs.hpp.


Constructor & Destructor Documentation

template<typename FunctionType>
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.

Parameters:
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.

Member Function Documentation

template<typename FunctionType>
double& mlpack::optimization::L_BFGS< FunctionType >::ArmijoConstant (  )  [inline]

Modify the Armijo condition constant.

Definition at line 130 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::ArmijoConstant (  )  const [inline]

Get the Armijo condition constant.

Definition at line 128 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::ChooseScalingFactor ( const size_t  iterationNum,
const arma::mat &  gradient 
) [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).

Returns:
The calculated scaling factor.
template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::Evaluate ( const arma::mat &  iterate  )  [private]

Evaluate the function at the given iterate point and store the result if it is a new minimum.

Returns:
The value of the function.
template<typename FunctionType>
FunctionType& mlpack::optimization::L_BFGS< FunctionType >::Function (  )  [inline]

Modify the function that is being optimized.

Definition at line 115 of file lbfgs.hpp.

template<typename FunctionType>
const FunctionType& mlpack::optimization::L_BFGS< FunctionType >::Function (  )  const [inline]

Return the function that is being optimized.

Definition at line 113 of file lbfgs.hpp.

template<typename FunctionType>
bool mlpack::optimization::L_BFGS< FunctionType >::GradientNormTooSmall ( const arma::mat &  gradient  )  [private]

Check to make sure that the norm of the gradient is not smaller than 1e-5.

Currently that value is not configurable.

Returns:
(norm < minGradientNorm).
template<typename FunctionType>
bool mlpack::optimization::L_BFGS< FunctionType >::LineSearch ( double &  functionValue,
arma::mat &  iterate,
arma::mat &  gradient,
const arma::mat &  searchDirection 
) [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.

Parameters:
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
Returns:
false if no step size is suitable, true otherwise.
template<typename FunctionType>
size_t& mlpack::optimization::L_BFGS< FunctionType >::MaxIterations (  )  [inline]

Modify the maximum number of iterations.

Definition at line 125 of file lbfgs.hpp.

template<typename FunctionType>
size_t mlpack::optimization::L_BFGS< FunctionType >::MaxIterations (  )  const [inline]

Get the maximum number of iterations.

Definition at line 123 of file lbfgs.hpp.

template<typename FunctionType>
size_t& mlpack::optimization::L_BFGS< FunctionType >::MaxLineSearchTrials (  )  [inline]

Modify the maximum number of line search trials.

Definition at line 145 of file lbfgs.hpp.

template<typename FunctionType>
size_t mlpack::optimization::L_BFGS< FunctionType >::MaxLineSearchTrials (  )  const [inline]

Get the maximum number of line search trials.

Definition at line 143 of file lbfgs.hpp.

template<typename FunctionType>
double& mlpack::optimization::L_BFGS< FunctionType >::MaxStep (  )  [inline]

Modify the maximum line search step size.

Definition at line 155 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::MaxStep (  )  const [inline]

Return the maximum line search step size.

Definition at line 153 of file lbfgs.hpp.

template<typename FunctionType>
double& mlpack::optimization::L_BFGS< FunctionType >::MinGradientNorm (  )  [inline]

Modify the minimum gradient norm.

Definition at line 140 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::MinGradientNorm (  )  const [inline]

Get the minimum gradient norm.

Definition at line 138 of file lbfgs.hpp.

template<typename FunctionType>
const std::pair<arma::mat, double>& mlpack::optimization::L_BFGS< FunctionType >::MinPointIterate (  )  const

Return the point where the lowest function value has been found.

Returns:
arma::vec representing the point and a double with the function value at that point.
template<typename FunctionType>
double& mlpack::optimization::L_BFGS< FunctionType >::MinStep (  )  [inline]

Modify the minimum line search step size.

Definition at line 150 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::MinStep (  )  const [inline]

Return the minimum line search step size.

Definition at line 148 of file lbfgs.hpp.

template<typename FunctionType>
size_t& mlpack::optimization::L_BFGS< FunctionType >::NumBasis (  )  [inline]

Modify the memory size.

Definition at line 120 of file lbfgs.hpp.

template<typename FunctionType>
size_t mlpack::optimization::L_BFGS< FunctionType >::NumBasis (  )  const [inline]

Get the memory size.

Definition at line 118 of file lbfgs.hpp.

template<typename FunctionType>
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.

Parameters:
iterate Starting point (will be modified).
maxIterations Maximum number of iterations (0 specifies no limit).
Returns:
Objective value of the final point.
template<typename FunctionType>
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.

Parameters:
iterate Starting point (will be modified).
Returns:
Objective value of the final point.
template<typename FunctionType>
void mlpack::optimization::L_BFGS< FunctionType >::SearchDirection ( const arma::mat &  gradient,
const size_t  iterationNum,
const double  scalingFactor,
arma::mat &  searchDirection 
) [private]

Find the L-BFGS search direction.

Parameters:
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
template<typename FunctionType>
void mlpack::optimization::L_BFGS< FunctionType >::UpdateBasisSet ( const size_t  iterationNum,
const arma::mat &  iterate,
const arma::mat &  oldIterate,
const arma::mat &  gradient,
const arma::mat &  oldGradient 
) [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.

Parameters:
iterationNum Iteration number
iterate Current point
oldIterate Point at last iteration
gradient Gradient at current point (iterate)
oldGradient Gradient at last iteration point (oldIterate)
template<typename FunctionType>
double& mlpack::optimization::L_BFGS< FunctionType >::Wolfe (  )  [inline]

Modify the Wolfe parameter.

Definition at line 135 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::Wolfe (  )  const [inline]

Get the Wolfe parameter.

Definition at line 133 of file lbfgs.hpp.


Member Data Documentation

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::armijoConstant [private]

Parameter for determining the Armijo condition.

Definition at line 173 of file lbfgs.hpp.

Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< LRSDP > >::ArmijoConstant().

template<typename FunctionType>
FunctionType& mlpack::optimization::L_BFGS< FunctionType >::function [private]

Internal reference to the function we are optimizing.

Definition at line 159 of file lbfgs.hpp.

template<typename FunctionType>
size_t mlpack::optimization::L_BFGS< FunctionType >::maxIterations [private]

Maximum number of iterations.

Definition at line 171 of file lbfgs.hpp.

template<typename FunctionType>
size_t mlpack::optimization::L_BFGS< FunctionType >::maxLineSearchTrials [private]

Maximum number of trials for the line search.

Definition at line 179 of file lbfgs.hpp.

Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< LRSDP > >::MaxLineSearchTrials().

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::maxStep [private]

Maximum step of the line search.

Definition at line 183 of file lbfgs.hpp.

Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< LRSDP > >::MaxStep().

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::minGradientNorm [private]

Minimum gradient norm required to continue the optimization.

Definition at line 177 of file lbfgs.hpp.

Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< LRSDP > >::MinGradientNorm().

template<typename FunctionType>
std::pair<arma::mat, double> mlpack::optimization::L_BFGS< FunctionType >::minPointIterate [private]

Best point found so far.

Definition at line 186 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::minStep [private]

Minimum step of the line search.

Definition at line 181 of file lbfgs.hpp.

Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< LRSDP > >::MinStep().

template<typename FunctionType>
arma::mat mlpack::optimization::L_BFGS< FunctionType >::newIterateTmp [private]

Position of the new iterate.

Definition at line 162 of file lbfgs.hpp.

template<typename FunctionType>
size_t mlpack::optimization::L_BFGS< FunctionType >::numBasis [private]

Size of memory for this L-BFGS optimizer.

Definition at line 169 of file lbfgs.hpp.

Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< LRSDP > >::NumBasis().

template<typename FunctionType>
arma::cube mlpack::optimization::L_BFGS< FunctionType >::s [private]

Stores all the s matrices in memory.

Definition at line 164 of file lbfgs.hpp.

template<typename FunctionType>
double mlpack::optimization::L_BFGS< FunctionType >::wolfe [private]

Parameter for detecting the Wolfe condition.

Definition at line 175 of file lbfgs.hpp.

Referenced by mlpack::optimization::L_BFGS< AugLagrangianFunction< LRSDP > >::Wolfe().

template<typename FunctionType>
arma::cube mlpack::optimization::L_BFGS< FunctionType >::y [private]

Stores all the y matrices in memory.

Definition at line 166 of file lbfgs.hpp.


The documentation for this class was generated from the following file:

Generated on 29 Sep 2016 for MLPACK by  doxygen 1.6.1