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

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include <algorithm>
#include <solver/optimizer/LbfgsSolver.hpp>

Include dependency graph for LbfgsSolver.cpp:

Classes
struct	solver::tag_callback_data

struct	solver::tag_iteration_data

Macros
#define	max2(a, b) ((a) >= (b) ? (a) : (b))

#define	max3(a, b, c) max2(max2((a), (b)), (c));

#define	USES_MINIMIZER double a, d, gamma, theta, p, q, r, s;
	Define the local variables for computing minimizers.

#define	CUBIC_MINIMIZER(cm, u, fu, du, v, fv, dv)
	Find a minimizer of an interpolated cubic function. More...

#define	CUBIC_MINIMIZER2(cm, u, fu, du, v, fv, dv, xmin, xmax)
	Find a minimizer of an interpolated cubic function. More...

#define	QUARD_MINIMIZER(qm, u, fu, du, v, fv)
	Find a minimizer of an interpolated quadratic function. More...

#define	QUARD_MINIMIZER2(qm, u, du, v, dv)
	Find a minimizer of an interpolated quadratic function. More...

Typedefs
typedef struct tag_callback_data	solver::callback_data_t

typedef struct tag_iteration_data	solver::iteration_data_t

typedef int(*	solver::line_search_proc) (int n, double x, double f, double g, double s, double stp, const double xp, const double gp, double wa, callback_data_t cd, const lbfgs_parameter_t param)

Functions
static void *	solver::vecalloc (size_t size)

static void	solver::vecfree (void *memblock)

static void	solver::veccpy (double y, const double x, const int n)

static void	solver::vecncpy (double y, const double x, const int n)

static void	solver::vecadd (double y, const double x, const double c, const int n)

static void	solver::vecdiff (double z, const double x, const double *y, const int n)

static void	solver::vecscale (double *y, const double c, const int n)

static void	solver::vecdot (double s, const double x, const double *y, const int n)

static void	solver::vec2norm (double s, const double x, const int n)

static void	solver::vec2norminv (double s, const double x, const int n)

static int	solver::line_search_backtracking (int n, double x, double f, double g, double s, double stp, const double xp, const double gp, double wa, callback_data_t cd, const lbfgs_parameter_t param)

static int	solver::line_search_morethuente (int n, double x, double f, double g, double s, double stp, const double xp, const double gp, double wa, callback_data_t cd, const lbfgs_parameter_t param)

static int	solver::update_trial_interval (double x, double fx, double dx, double y, double fy, double dy, double t, double ft, double dt, const double tmin, const double tmax, int brackt)
	Update a safeguarded trial value and interval for line search. More...

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

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

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

Variables
static const lbfgs_parameter_t	solver::_defparam

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.

Macro Definition Documentation

#define CUBIC_MINIMIZER	(	cm,
		u,
		fu,
		du,
		v,
		fv,
		dv
	)

Value:

d = (v) - (u); \
    theta = ((fu) - (fv)) * 3 / d + (du) + (dv); \
    p = fabs(theta); \
    q = fabs(du); \
    r = fabs(dv); \
    s = max3(p, q, r); \
    a = theta / s; \
    gamma = s * sqrt(a * a - ((du) / s) * ((dv) / s)); \
    if ((v) < (u)) gamma = -gamma; \
    p = gamma - (du) + theta; \
    q = gamma - (du) + gamma + (dv); \
    r = p / q; \
    (cm) = (u) + r * d;

Find a minimizer of an interpolated cubic function.

Parameters

cm	The minimizer of the interpolated cubic.
u	The value of one point, u.
fu	The value of f(u).
du	The value of f'(u).
v	The value of another point, v.
fv	The value of f(v).
du	The value of f'(v).

#define CUBIC_MINIMIZER2	(	cm,
		u,
		fu,
		du,
		v,
		fv,
		dv,
		xmin,
		xmax
	)

Value:

d = (v) - (u); \
    theta = ((fu) - (fv)) * 3 / d + (du) + (dv); \
    p = fabs(theta); \
    q = fabs(du); \
    r = fabs(dv); \
    s = max3(p, q, r); \
    a = theta / s; \
    gamma = s * sqrt(max2(0, a * a - ((du) / s) * ((dv) / s))); \
    if ((u) < (v)) gamma = -gamma; \
    p = gamma - (dv) + theta; \
    q = gamma - (dv) + gamma + (du); \
    r = p / q; \
    if (r < 0. && gamma != 0.) { \
        (cm) = (v) - r * d; \
    } else if (a < 0) { \
        (cm) = (xmax); \
    } else { \
        (cm) = (xmin); \
    }

Find a minimizer of an interpolated cubic function.

Parameters

cm	The minimizer of the interpolated cubic.
u	The value of one point, u.
fu	The value of f(u).
du	The value of f'(u).
v	The value of another point, v.
fv	The value of f(v).
du	The value of f'(v).
xmin	The maximum value.
xmin	The minimum value.

#define QUARD_MINIMIZER	(	qm,
		u,
		fu,
		du,
		v,
		fv
	)

Value:

a = (v) - (u); \

(qm) = (u) + (du) / (((fu) - (fv)) / a + (du)) / 2 * a;

Find a minimizer of an interpolated quadratic function.

Parameters

qm	The minimizer of the interpolated quadratic.
u	The value of one point, u.
fu	The value of f(u).
du	The value of f'(u).
v	The value of another point, v.
fv	The value of f(v).

#define QUARD_MINIMIZER2	(	qm,
		u,
		du,
		v,
		dv
	)

Value:

a = (u) - (v); \

(qm) = (v) + (dv) / ((dv) - (du)) * a;

Find a minimizer of an interpolated quadratic function.

Parameters

qm	The minimizer of the interpolated quadratic.
u	The value of one point, u.
du	The value of f'(u).
v	The value of another point, v.
dv	The value of f'(v).

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.

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.

static int solver::update_trial_interval	(	double *	x,
		double *	fx,
		double *	dx,
		double *	y,
		double *	fy,
		double *	dy,
		double *	t,
		double *	ft,
		double *	dt,
		const double	tmin,
		const double	tmax,
		int *	brackt
	)

static

Update a safeguarded trial value and interval for line search.

The parameter x represents the step with the least function value. The parameter t represents the current step. This function assumes that the derivative at the point of x in the direction of the step. If the bracket is set to true, the minimizer has been bracketed in an interval of uncertainty with endpoints between x and y.

Parameters

x	The pointer to the value of one endpoint.
fx	The pointer to the value of f(x).
dx	The pointer to the value of f'(x).
y	The pointer to the value of another endpoint.
fy	The pointer to the value of f(y).
dy	The pointer to the value of f'(y).
t	The pointer to the value of the trial value, t.
ft	The pointer to the value of f(t).
dt	The pointer to the value of f'(t).
tmin	The minimum value for the trial value, t.
tmax	The maximum value for the trial value, t.
brackt	The pointer to the predicate if the trial value is bracketed.

Return values

int	Status value. Zero indicates a normal termination.

See also: Jorge J. More and David J. Thuente. Line search algorithm with guaranteed sufficient decrease. ACM Transactions on Mathematical Software (TOMS), Vol 20, No 3, pp. 286-307, 1994.

Variable Documentation

const lbfgs_parameter_t solver::_defparam

static

Initial value:

= {
    6, 1e-5, 0, 1e-5,
    0, LBFGS_LINESEARCH_DEFAULT, 40,
    1e-20, 1e20, 1e-4, 0.9, 0.9, 1.0e-16
  }

Classes

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

Function Documentation

Variable Documentation