LSLOpt  1.0
Classes | Typedefs | Enumerations | Functions
LSLOpt Namespace Reference

BFGS optimizations. More...

Classes

struct  DebugProblem
 Debug wrapper for any problem. More...
 
struct  NoOutput
 NoOutput struct. More...
 
struct  OptimizationParameters
 Parameters for limited step length BFGS algorithm. More...
 
struct  OptimizationResult
 The optimization result. More...
 
struct  OstreamOutput
 Class for the output to an std::ostream. More...
 
struct  scalar_traits
 Traits for scalar values. More...
 
struct  scalar_traits< double >
 Scalar for double values. More...
 

Typedefs

template<typename Scalar >
using Vector = Eigen::Matrix< Scalar, Eigen::Dynamic, 1 >
 Vector type used. More...
 
template<typename Scalar >
using Matrix = Eigen::Matrix< Scalar, Eigen::Dynamic, Eigen::Dynamic >
 Matrix type used. More...
 
template<typename Scalar >
using DiagonalMatrix = Eigen::DiagonalMatrix< Scalar, Eigen::Dynamic, Eigen::Dynamic >
 Diagonal matrix type used. More...
 

Enumerations

enum  Linesearch { Linesearch::Backtracking }
 Line search algorithm. More...
 
enum  Alpha0Policy { Constant, Alpha0Policy::ConstantScaling, Alpha0Policy::Interpolation }
 Selection of initial step length alpha0. More...
 
enum  Status : int {
  GeneralFailure = -256, Status::InvalidMaximumValue = -129, Status::LineSearchFailed = -128, Status::LineSearchMinimum = -127,
  Status::LineSearchMaxIterations = -126, Status::WrongSearchDirection = -125, Status::InvalidBounds = -124, Status::Converged = 0,
  Status::Success = 0, Status::MaxIterations = 1, Status::MinChange = 2, Status::MinusInfinity = 3,
  Status::MinValue = 4, Status::XGradChange = 5, Status::Running = 256
}
 Status of the optimizer. More...
 
enum  OutputLevel {
  Nothing, OutputLevel::Error, OutputLevel::Warning, OutputLevel::Status,
  OutputLevel::Debug
}
 The output level for filtering. More...
 

Functions

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > lsl_bfgs (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform a BFGS optimization with identification of the maximum step length (LSL-BFGS). More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > bfgs (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform a BFGS optimization without identification of the maximum step length (BFGS). More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > lsl_bfgs_b (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform a BFGS optimization with box constraints and identification of the maximum step length (LSL-BFGS-B). More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > bfgs_b (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform a BFGS optimization with box constraints and without identification of the maximum step length (BFGS-B). More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > lsl_gd (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform a gradient descent optimization with identification of the maximum step length. More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > gd (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform a gradient descent optimization without identification of the maximum step length. More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > lsl_lbfgs (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform an L-BFGS optimization with identification of the maximum step length (LSL-L-BFGS). More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > lbfgs (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform an L-BFGS optimization without identification of the maximum step length (L-BFGS). More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > lsl_lbfgs_b (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform an L-BFGS optimization with box constraints and identification of the maximum step length (LSL-L-BFGS-B). More...
 
template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult< Scalar > lbfgs_b (Problem &problem, const Vector< Scalar > &x0, const OptimizationParameters< Scalar > &params, OutputFunction &output_function=OutputFunction())
 Perform an L-BFGS optimization with box constraints and without identification of the maximum step length (L-BFGS-B). More...
 
template<typename Scalar >
OptimizationParameters< Scalar > getOptimizationParameters ()
 Get optimization parameters for this type. More...
 
template<>
OptimizationParameters< double > getOptimizationParameters< double > ()
 Default optimization parameters for double.
 
std::ostream & operator<< (std::ostream &os, const Status &status)
 Output of Status on std::ostream. More...
 
std::ostream & operator<< (std::ostream &os, const OutputLevel &level)
 Output operator for textual level output. More...
 
template<typename OutputFunction >
bool is_output_enabled (OutputFunction &output_function, OutputLevel curr_level, decltype(output_function.output_level) *=nullptr)
 
bool is_output_enabled (...)
 Catch-all function.
 

Detailed Description

BFGS optimizations.

L-BFGS-B optimizations.

L-BFGS optimizations.

Gradient descent optimizations.

BFGS-B optimizations.

This file contains functions for the optimization using the BFGS algorithm with and without the limitation of step lengths.

Warning
These functions are not suited for large-scale optimization.

This file contains functions for the optimization with box constraints using the BFGS-B algorithm with and without the limitation of step lengths.

Warning
These functions are not suited for large-scale optimization.

This file contains functions for the optimization using the gradient descent algorithm with and without the limitation of step lengths.

Warning
These functions are used for comparison only, the various BFGS implementations are usually far superior.

This file contains functions for the optimization using the L-BFGS algorithm with and without the limitation of step lengths.

This file contains functions for the optimization using the L-BFGS-B algorithm with and without the limitation of step lengths.

Typedef Documentation

◆ DiagonalMatrix

template<typename Scalar >
using LSLOpt::DiagonalMatrix = typedef Eigen::DiagonalMatrix<Scalar, Eigen::Dynamic, Eigen::Dynamic>

Diagonal matrix type used.

Template Parameters
ScalarThe scalar type of the coefficients.

This is a diagonal matrix (an Eigen::DiagonalMatrix).

◆ Matrix

template<typename Scalar >
using LSLOpt::Matrix = typedef Eigen::Matrix<Scalar, Eigen::Dynamic, Eigen::Dynamic>

Matrix type used.

Template Parameters
ScalarThe scalar type of the coefficients.

This is a matrix (an Eigen::Matrix).

◆ Vector

template<typename Scalar >
using LSLOpt::Vector = typedef Eigen::Matrix<Scalar, Eigen::Dynamic, 1>

Vector type used.

Template Parameters
ScalarThe scalar type of the coefficients.

This is a column vector (an Eigen::Matrix).

Enumeration Type Documentation

◆ Alpha0Policy

enum LSLOpt::Alpha0Policy
strong

Selection of initial step length alpha0.

Enumerator
ConstantScaling 

use max alpha from algorithm (or 1.0)

Interpolation 

scale old alpha by phi'_{k-1}(0) / phi'_{k}(0)

◆ Linesearch

enum LSLOpt::Linesearch
strong

Line search algorithm.

Enumerator
Backtracking 

Armijo backtracking.

◆ OutputLevel

enum LSLOpt::OutputLevel
strong

The output level for filtering.

Enumerator
Error 

not output

Warning 

show fatal errors

Status 

show warnings

Debug 

show status messages

◆ Status

enum LSLOpt::Status : int
strong

Status of the optimizer.

Non-negative values indicate success or regular termination.

Negative values indicate failures.

Enumerator
InvalidMaximumValue 

general failure

LineSearchFailed 

no valid max alpha obtained

LineSearchMinimum 

general line search failure

LineSearchMaxIterations 

step length too small

WrongSearchDirection 

maximum number of line search iterations reached

InvalidBounds 

optimizer going uphill, probably wrong gradient!

Converged 

the bounds are invalid

Success 

optimization converged

MaxIterations 

optimization successful, the same as Converged

MinChange 

maximum number of iterations reached

MinusInfinity 

objective function doesn't change anymore

MinValue 

function reached minus infinity

XGradChange 

function value reached stopping value

Running 

the gradient or the parameters don't change anymore

Function Documentation

◆ bfgs()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::bfgs ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform a BFGS optimization without identification of the maximum step length (BFGS).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a BFGS minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point as well as the maximum allowed step length at a given point and a given direction:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

Warning
This is a BFGS implementation (NOT L-BFGS) and therefore not suited for large optimization problems.
Note
This is a convenience function to perform a standard BFGS without maximum step length identification.

◆ bfgs_b()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::bfgs_b ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform a BFGS optimization with box constraints and without identification of the maximum step length (BFGS-B).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a BFGS minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point as well as the maximum allowed step length at a given point and a given direction and the upper and lower bounds on the parameters:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

const Vector<Scalar>& lower_bounds();

const Vector<Scalar>& upper_bounds();

Warning
This is a BFGS implementation (NOT L-BFGS) and therefore not suited for large optimization problems.
Note
This is a convenience function to perform a standard BFGS-B without maximum step length identification.

Byrd, R.H., Lu, P., Nocedal, J., Zhu, C. A Limited Memory Algorithm for Bound Constrained Optimization.

  1. SIAM Journal of Scientific and Statistical Computing. 16(5). 1190-1208.

◆ gd()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::gd ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform a gradient descent optimization without identification of the maximum step length.

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a gradient descent minimization of the given objective function.

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point as well as the maximum allowed step length at a given point and a given direction:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

Note
This is a convenience function to perform a standard gradient descent without maximum step length identification.

◆ getOptimizationParameters()

template<typename Scalar >
OptimizationParameters<Scalar> LSLOpt::getOptimizationParameters ( )

Get optimization parameters for this type.

Template Parameters
ScalarType of scalar values.

◆ is_output_enabled()

template<typename OutputFunction >
bool LSLOpt::is_output_enabled ( OutputFunction &  output_function,
OutputLevel  curr_level,
decltype(output_function.output_level) *  = nullptr 
)

Check if the output function is activated at this level. This uses SFINAE, i.e. if the output_function does not provide the output_level attribute, this function is not used.

Parameters
output_functionThe output function.
curr_levelCurrent leve of message.

◆ lbfgs()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::lbfgs ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform an L-BFGS optimization without identification of the maximum step length (L-BFGS).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a L-BFGS minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point as well as the maximum allowed step length at a given point and a given direction:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

Note
This is a L-BFGS implementation and therefore suited for large optimization problems.
This is a convenience function to perform a standard L-BFGS without maximum step length identification.

◆ lbfgs_b()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::lbfgs_b ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform an L-BFGS optimization with box constraints and without identification of the maximum step length (L-BFGS-B).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a L-BFGS-B minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point as well as the maximum allowed step length at a given point and a given direction and the upper and lower bounds on the parameters:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

const Vector<Scalar>& lower_bounds();

const Vector<Scalar>& upper_bounds();

Note
This is a L-BFGS-B implementation and therefore suited for large optimization problems.
This is a convenience function to perform a standard L-BFGS-B without maximum step length identification.

Byrd, R.H., Lu, P., Nocedal, J., Zhu, C. A Limited Memory Algorithm for Bound Constrained Optimization.

  1. SIAM Journal of Scientific and Statistical Computing. 16(5). 1190-1208.

Morales, J.L, Nocedal, J. L-BFGS-B: Remark on Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization.

  1. ACM Transactions on Mathematical Software. 38(1). 7:1-7:4.

◆ lsl_bfgs()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::lsl_bfgs ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform a BFGS optimization with identification of the maximum step length (LSL-BFGS).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a BFGS minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point, the initially allowed step length at a given point and a given direction as well as a function checking if a change from one point to the other is acceptable:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

Scalar initial_step_length(const Vector<Scalar>& x, const Vector<Scalar>& p);

Scalar change_acceptable(const Vector<Scalar>& x, const Vector<Scalar>& xp); (should return a value <= 0.0 if the change is acceptable, > 0.0 otherwise).

Warning
This is a BFGS implementation (NOT L-BFGS) and therefore not suited for large optimization problems.

◆ lsl_bfgs_b()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::lsl_bfgs_b ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform a BFGS optimization with box constraints and identification of the maximum step length (LSL-BFGS-B).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a BFGS-B minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point, the initially allowed step length at a given point and a given direction as well as a function checking if a change from one point to the other is acceptable and the upper and lower bounds on the parameters:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

Scalar initial_step_length(const Vector<Scalar>& x, const Vector<Scalar>& p);

Scalar change_acceptable(const Vector<Scalar>& x, const Vector<Scalar>& xp); (should return a value <= 0.0 if the change is acceptable, > 0.0 otherwise).

const Vector<Scalar>& lower_bounds();

const Vector<Scalar>& upper_bounds();

Warning
This is a BFGS-B implementation (NOT L-BFGS) and therefore not suited for large optimization problems.

Byrd, R.H., Lu, P., Nocedal, J., Zhu, C. A Limited Memory Algorithm for Bound Constrained Optimization.

  1. SIAM Journal of Scientific and Statistical Computing. 16(5). 1190-1208.

◆ lsl_gd()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::lsl_gd ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform a gradient descent optimization with identification of the maximum step length.

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a gradient descent minimization of the given objective function.

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point, the initially allowed step length at a given point and a given direction as well as a function checking if a change from one point to the other is acceptable:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

double initial_step_length(const Eigen::VectorXd& x, const Eigen::VectorXd& p);

bool is_change_acceptable(const Eigen::VectorXd& x, const Eigen::VectorXd& xp);

◆ lsl_lbfgs()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::lsl_lbfgs ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform an L-BFGS optimization with identification of the maximum step length (LSL-L-BFGS).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a L-BFGS minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point, the initially allowed step length at a given point and a given direction as well as a function checking if a change from one point to the other is acceptable:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

Scalar initial_step_length(const Vector<Scalar>& x, const Vector<Scalar>& p);

Scalar change_acceptable(const Vector<Scalar>& x, const Vector<Scalar>& xp); (should return a value <= 0.0 if the change is acceptable, > 0.0 otherwise).

Note
This is a L-BFGS implementation and therefore suited for large optimization problems.

◆ lsl_lbfgs_b()

template<typename Problem , typename Scalar , typename OutputFunction = NoOutput>
OptimizationResult<Scalar> LSLOpt::lsl_lbfgs_b ( Problem &  problem,
const Vector< Scalar > &  x0,
const OptimizationParameters< Scalar > &  params,
OutputFunction &  output_function = OutputFunction() 
)

Perform an L-BFGS optimization with box constraints and identification of the maximum step length (LSL-L-BFGS-B).

Parameters
problemObjective function to minimize.
x0Starting point for optimization.
paramsBFGS parameters.
output_functionFunction for output of status and error messages.

This performs a L-BFGS-B minimization of the given objective function. Internally, it uses an backtracking line search and uses a damped update strategy to ensure the positive definiteness of the Hessian approximation (and it's inverse).

The problem must provide the following functions, calculating the value at a given point, the gradient at a given point, the initially allowed step length at a given point and a given direction as well as a function checking if a change from one point to the other is acceptable and the upper and lower bounds on the parameters:

Scalar value(const Vector<Scalar>& x);

Vector<Scalar> gradient(const Vector<Scalar>& x);

Scalar initial_step_length(const Vector<Scalar>& x, const Vector<Scalar>& p);

Scalar change_acceptable(const Vector<Scalar>& x, const Vector<Scalar>& xp); (should return a value <= 0.0 if the change is acceptable, > 0.0 otherwise).

const Vector<Scalar>& lower_bounds();

const Vector<Scalar>& upper_bounds();

Note
This is a L-BFGS-B implementation and therefore suited for large optimization problems.

Byrd, R.H., Lu, P., Nocedal, J., Zhu, C. A Limited Memory Algorithm for Bound Constrained Optimization.

  1. SIAM Journal of Scientific and Statistical Computing. 16(5). 1190-1208.

Morales, J.L, Nocedal, J. L-BFGS-B: Remark on Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization.

  1. ACM Transactions on Mathematical Software. 38(1). 7:1-7:4.

◆ operator<<() [1/2]

std::ostream& LSLOpt::operator<< ( std::ostream &  os,
const OutputLevel level 
)
inline

Output operator for textual level output.

Parameters
osOutput stream.
levelThe output leve.
Returns
The output stream.

◆ operator<<() [2/2]

std::ostream& LSLOpt::operator<< ( std::ostream &  os,
const Status status 
)
inline

Output of Status on std::ostream.

Parameters
osOutput stream.
statusStatus to output.
Returns
The output stream os.