C library of Limited memory BFGS (L-BFGS). More...

#include <iostream>
#include <Eigen/Dense>
#include <solver/interface/NlpDescription.hpp>

Include dependency graph for LbfgsSolver.hpp:

This graph shows which files directly or indirectly include this file:

Classes
struct	solver::lbfgs_parameter_t
	L-BFGS optimization parameters. More...

class	solver::LbfgsSolver

Typedefs
typedef double(*	solver::lbfgs_evaluate_t) (void instance, const double x, double *g, const int n, const double step)
	Callback interface to provide objective function and gradient evaluations. More...

typedef int(*	solver::lbfgs_progress_t) (void instance, const double x, const double *g, const double fx, const double xnorm, const double gnorm, const double step, int n, int k, int ls)
	Callback interface to receive the progress of the optimization process. More...

Enumerations
enum	{ solver::LBFGS_SUCCESS = 0, LBFGS_STOP, solver::LBFGS_ALREADY_MINIMIZED, solver::LBFGSERR_UNKNOWNERROR = -1024, solver::LBFGSERR_LOGICERROR, solver::LBFGSERR_OUTOFMEMORY, solver::LBFGSERR_INVALID_N, solver::LBFGSERR_INVALID_EPSILON, solver::LBFGSERR_INVALID_TESTPERIOD, solver::LBFGSERR_INVALID_DELTA, solver::LBFGSERR_INVALID_LINESEARCH, solver::LBFGSERR_INVALID_MINSTEP, solver::LBFGSERR_INVALID_MAXSTEP, solver::LBFGSERR_INVALID_FTOL, solver::LBFGSERR_INVALID_WOLFE, solver::LBFGSERR_INVALID_GTOL, solver::LBFGSERR_INVALID_XTOL, solver::LBFGSERR_INVALID_MAXLINESEARCH, solver::LBFGSERR_INVALID_ORTHANTWISE, solver::LBFGSERR_INVALID_ORTHANTWISE_START, solver::LBFGSERR_INVALID_ORTHANTWISE_END, solver::LBFGSERR_OUTOFINTERVAL, solver::LBFGSERR_INCORRECT_TMINMAX, solver::LBFGSERR_ROUNDING_ERROR, solver::LBFGSERR_MINIMUMSTEP, solver::LBFGSERR_MAXIMUMSTEP, solver::LBFGSERR_MAXIMUMLINESEARCH, solver::LBFGSERR_MAXIMUMITERATION, solver::LBFGSERR_WIDTHTOOSMALL, solver::LBFGSERR_INVALIDPARAMETERS, solver::LBFGSERR_INCREASEGRADIENT }
	Return values of lbfgs(). More...

enum	{ solver::LBFGS_LINESEARCH_DEFAULT = 0, solver::LBFGS_LINESEARCH_MORETHUENTE = 0, solver::LBFGS_LINESEARCH_BACKTRACKING_ARMIJO = 1, solver::LBFGS_LINESEARCH_BACKTRACKING = 2, solver::LBFGS_LINESEARCH_BACKTRACKING_WOLFE = 2, solver::LBFGS_LINESEARCH_BACKTRACKING_STRONG_WOLFE = 3 }
	Line search algorithms. More...

Functions
int	solver::lbfgs (int n, double x, double ptr_fx, lbfgs_evaluate_t proc_evaluate, lbfgs_progress_t proc_progress, void instance, lbfgs_parameter_t param)
	Start a L-BFGS optimization. More...

void	solver::lbfgs_parameter_init (lbfgs_parameter_t *param)
	Initialize L-BFGS parameters to the default values. More...

double *	solver::lbfgs_malloc (int n)
	Allocate an array for variables. More...

void	solver::lbfgs_free (double *x)
	Free an array of variables. More...

Detailed Description

C library of Limited memory BFGS (L-BFGS).

Author: Jorge Nocedal

License:: License BSD-3-Clause

Copyright: 1990, Jorge Nocedal; 2007-2010 Naoaki Okazaki

Date: 2019-10-06 All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Typedef Documentation

typedef double(* solver::lbfgs_evaluate_t) (void *instance, const double *x, double *g, const int n, const double step)

Callback interface to provide objective function and gradient evaluations.

The lbfgs() function call this function to obtain the values of objective function and its gradients when needed. A client program must implement this function to evaluate the values of the objective function and its gradients, given current values of variables.

Parameters

instance	The user data sent for lbfgs() function by the client.
x	The current values of variables.
g	The gradient vector. The callback function must compute the gradient values for the current variables.
n	The number of variables.
step	The current step of the line search routine.

Return values

double The value of the objective function for the current variables.

typedef int(* solver::lbfgs_progress_t) (void *instance, const double *x, const double *g, const double fx, const double xnorm, const double gnorm, const double step, int n, int k, int ls)

Callback interface to receive the progress of the optimization process.

The lbfgs() function call this function for each iteration. Implementing this function, a client program can store or display the current progress of the optimization process.

Parameters

instance	The user data sent for lbfgs() function by the client.
x	The current values of variables.
g	The current gradient values of variables.
fx	The current value of the objective function.
xnorm	The Euclidean norm of the variables.
gnorm	The Euclidean norm of the gradients.
step	The line-search step used for this iteration.
n	The number of variables.
k	The iteration count.
ls	The number of evaluations called for this iteration.

Return values

int	Zero to continue the optimization process. Returning a non-zero value will cancel the optimization process.

Enumeration Type Documentation

anonymous enum

Return values of lbfgs().

Roughly speaking, a negative value indicates an error.

Enumerator
LBFGS_SUCCESS	L-BFGS reaches convergence.
LBFGS_ALREADY_MINIMIZED	The initial variables already minimize the objective function.
LBFGSERR_UNKNOWNERROR	Unknown error.
LBFGSERR_LOGICERROR	Logic error.
LBFGSERR_OUTOFMEMORY	Insufficient memory.
LBFGSERR_INVALID_N	Invalid number of variables specified.
LBFGSERR_INVALID_EPSILON	Invalid parameter lbfgs_parameter_t::epsilon specified.
LBFGSERR_INVALID_TESTPERIOD	Invalid parameter lbfgs_parameter_t::past specified.
LBFGSERR_INVALID_DELTA	Invalid parameter lbfgs_parameter_t::delta specified.
LBFGSERR_INVALID_LINESEARCH	Invalid parameter lbfgs_parameter_t::linesearch specified.
LBFGSERR_INVALID_MINSTEP	Invalid parameter lbfgs_parameter_t::max_step specified.
LBFGSERR_INVALID_MAXSTEP	Invalid parameter lbfgs_parameter_t::max_step specified.
LBFGSERR_INVALID_FTOL	Invalid parameter lbfgs_parameter_t::ftol specified.
LBFGSERR_INVALID_WOLFE	Invalid parameter lbfgs_parameter_t::wolfe specified.
LBFGSERR_INVALID_GTOL	Invalid parameter lbfgs_parameter_t::gtol specified.
LBFGSERR_INVALID_XTOL	Invalid parameter lbfgs_parameter_t::xtol specified.
LBFGSERR_INVALID_MAXLINESEARCH	Invalid parameter lbfgs_parameter_t::max_linesearch specified.
LBFGSERR_INVALID_ORTHANTWISE	Invalid parameter lbfgs_parameter_t::orthantwise_c specified.
LBFGSERR_INVALID_ORTHANTWISE_START	Invalid parameter lbfgs_parameter_t::orthantwise_start specified.
LBFGSERR_INVALID_ORTHANTWISE_END	Invalid parameter lbfgs_parameter_t::orthantwise_end specified.
LBFGSERR_OUTOFINTERVAL	The line-search step went out of the interval of uncertainty.
LBFGSERR_INCORRECT_TMINMAX	A logic error occurred; alternatively, the interval of uncertainty became too small.
LBFGSERR_ROUNDING_ERROR	A rounding error occurred; alternatively, no line-search step satisfies the sufficient decrease and curvature conditions.
LBFGSERR_MINIMUMSTEP	The line-search step became smaller than lbfgs_parameter_t::min_step.
LBFGSERR_MAXIMUMSTEP	The line-search step became larger than lbfgs_parameter_t::max_step.
LBFGSERR_MAXIMUMLINESEARCH	The line-search routine reaches the maximum number of evaluations.
LBFGSERR_MAXIMUMITERATION	The algorithm routine reaches the maximum number of iterations.
LBFGSERR_WIDTHTOOSMALL	Relative width of the interval of uncertainty is at most lbfgs_parameter_t::xtol.
LBFGSERR_INVALIDPARAMETERS	A logic error (negative line-search step) occurred.
LBFGSERR_INCREASEGRADIENT	The current search direction increases the objective function value.

anonymous enum

Line search algorithms.

Enumerator
LBFGS_LINESEARCH_DEFAULT	The default algorithm (MoreThuente method).
LBFGS_LINESEARCH_MORETHUENTE	MoreThuente method proposd by More and Thuente.
LBFGS_LINESEARCH_BACKTRACKING_ARMIJO	Backtracking method with the Armijo condition. The backtracking method finds the step length such that it satisfies the sufficient decrease (Armijo) condition, f(x + a * d) <= f(x) + lbfgs_parameter_t::ftol * a * g(x)^T d, where x is the current point, d is the current search direction, and a is the step length.
LBFGS_LINESEARCH_BACKTRACKING	The backtracking method with the defualt (regular Wolfe) condition.
LBFGS_LINESEARCH_BACKTRACKING_WOLFE	Backtracking method with regular Wolfe condition. The backtracking method finds the step length such that it satisfies both the Armijo condition (LBFGS_LINESEARCH_BACKTRACKING_ARMIJO) and the curvature condition, g(x + a * d)^T d >= lbfgs_parameter_t::wolfe * g(x)^T d, where x is the current point, d is the current search direction, and a is the step length.
LBFGS_LINESEARCH_BACKTRACKING_STRONG_WOLFE	Backtracking method with strong Wolfe condition. The backtracking method finds the step length such that it satisfies both the Armijo condition (LBFGS_LINESEARCH_BACKTRACKING_ARMIJO) and the following condition, \|g(x + a * d)^T d\| <= lbfgs_parameter_t::wolfe * \|g(x)^T d\|, where x is the current point, d is the current search direction, and a is the step length.

Function Documentation

int solver::lbfgs	(	int	n,
		double *	x,
		double *	ptr_fx,
		lbfgs_evaluate_t	proc_evaluate,
		lbfgs_progress_t	proc_progress,
		void *	instance,
		lbfgs_parameter_t *	param
	)

Start a L-BFGS optimization.

Parameters

n	The number of variables.
x	The array of variables. A client program can set default values for the optimization and receive the optimization result through this array. This array must be allocated by ::lbfgs_malloc function for libLBFGS built with SSE/SSE2 optimization routine enabled. The library built without SSE/SSE2 optimization does not have such a requirement.
ptr_fx	The pointer to the variable that receives the final value of the objective function for the variables. This argument can be set to `NULL` if the final value of the objective function is unnecessary.
proc_evaluate	The callback function to provide function and gradient evaluations given a current values of variables. A client program must implement a callback function compatible with lbfgs_evaluate_t and pass the pointer to the callback function.
proc_progress	The callback function to receive the progress (the number of iterations, the current value of the objective function) of the minimization process. This argument can be set to `NULL` if a progress report is unnecessary.
instance	A user data for the client program. The callback functions will receive the value of this argument.
param	The pointer to a structure representing parameters for L-BFGS optimization. A client program can set this parameter to `NULL` to use the default parameters. Call lbfgs_parameter_init() function to fill a structure with the default values.

Return values

int	The status code. This function returns zero if the minimization process terminates without an error. A non-zero value indicates an error.

void solver::lbfgs_free ( double * x )

Free an array of variables.

Parameters

x	The array of variables allocated by ::lbfgs_malloc function.

double * solver::lbfgs_malloc ( int n )

Allocate an array for variables.

This function allocates an array of variables for the convenience of ::lbfgs function; the function has a requreiemt for a variable array when libLBFGS is built with SSE/SSE2 optimization routines. A user does not have to use this function for libLBFGS built without SSE/SSE2 optimization.

Parameters

n	The number of variables.

void solver::lbfgs_parameter_init ( lbfgs_parameter_t * param )

Initialize L-BFGS parameters to the default values.

Call this function to fill a parameter structure with the default values and overwrite parameter values if necessary.

Parameters

param The pointer to the parameter structure.

Classes

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

Enumeration Type Documentation

Function Documentation