Algorithm::LBFGS - Perl extension for L-BFGS
use Algorithm::LBFGS;
# create an L-BFGS optimizer
my $o = Algorithm::LBFGS->new;
# f(x) = (x1 - 1)^2 + (x2 + 2)^2
# grad f(x) = (2 * (x1 - 1), 2 * (x2 + 2));
my $eval_cb = sub {
my $x = shift;
my $f = ($x->[0] - 1) * ($x->[0] - 1) + ($x->[1] + 2) * ($x->[1] + 2);
my $g = [ 2 * ($x->[0] - 1), 2 * ($x->[1] + 2) ];
return ($f, $g);
};
my $x0 = [0.0, 0.0]; # initial point
my $x = $o->fmin($eval_cb, $x0); # $x is supposed to be [ 1, -2 ];
L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) is a quasi-Newton
method for unconstrained optimization. This method is especially efficient on
problems involving a large number of variables.
Generally, it solves a problem described as following:
min f(x), x = (x1, x2, ..., xn)
Jorge Nocedal wrote a Fortran 77 version of this algorithm.
<
http://www.ece.northwestern.edu/~nocedal/lbfgs.html>
And, Naoaki Okazaki rewrote it in pure C (liblbfgs).
<
http://www.chokkan.org/software/liblbfgs/index.html>
This module is a Perl port of Naoaki Okazaki's C version.
"new" creates a L-BFGS optimizer with given parameters.
my $o1 = new Algorithm::LBFGS(m => 5);
my $o2 = new Algorithm::LBFGS(m => 3, eps => 1e-6);
my $o3 = new Algorithm::LBFGS;
If no parameter is specified explicitly, their default values are used.
The parameter can be changed after the creation of the optimizer by
"set_param". Also, they can be queryed by "get_param".
Please refer to the "List of Parameters" for details about parameters.
Query the value of a parameter.
my $o = Algorithm::LBFGS->new;
print $o->get_param('epsilon'); # 1e-5
Change the values of one or several parameters.
my $o = Algorithm::LBFGS->new;
$o->set_param(epsilon => 1e-6, m => 7);
The prototype of "fmin" is like
x = fmin(evaluation_cb, x0, progress_cb, user_data)
As the name says, it finds a vector x which minimize the function f(x).
"evaluation_cb" is a ref to the evaluation callback subroutine,
"x0" is the initial point of the optimization algorithm,
"progress_cb" (optional) is a ref to the progress callback
subroutine, and "user_data" (optional) is a piece of extra data that
client program want to pass to both "evaluation_cb" and
"progress_cb".
Client program can use "get_status" to find if any problem occured
during the optimization after their calling "fmin". When the status
is "LBFGS_OK", the returning value "x" (array ref)
contains the optimized variables, otherwise, there may be some problems
occured and the value in the returning "x" is undefined.
evaluation_cb
The ref to the evaluation callback subroutine.
The evaluation callback subroutine is supposed to calculate the function value
and gradient vector at a specified point "x". It is called
automatically by "fmin" when an evaluation is needed.
The client program need to make sure their evaluation callback subroutine has a
prototype like
(f, g) = evaluation_cb(x, step, user_data)
"x" (array ref) is the current values of variables, "step"
is the current step of the line search routine, "user_data" is the
extra user data specified when calling "fmin".
The evaluation callback subroutine is supposed to return both the function value
"f" and the gradient vector "g" (array ref) at current
"x".
x0
The initial point of the optimization algorithm. The final result may depend on
your choice of "x0".
NOTE: The content of "x0" will be modified after calling
"fmin". When the algorithm terminates successfully, the content of
"x0" will be replaced by the optimized variables, otherwise, the
content of "x0" is undefined.
progress_cb
The ref to the progress callback subroutine.
The progress callback subroutine is called by "fmin" at the end of
each iteration, with information of current iteration. It is very useful for a
client program to monitor the optimization progress.
The client program need to make sure their progress callback subroutine has a
prototype like
s = progress_cb(x, g, fx, xnorm, gnorm, step, k, ls, user_data)
"x" (array ref) is the current values of variables. "g"
(array ref) is the current gradient vector. "fx" is the current
function value. "xnorm" and "gnorm" is the L2 norm of
"x" and "g". "step" is the line-search step used
for this iteration. "k" is the iteration count. "ls" is
the number of evaluations in this iteration. "user_data" is the
extra user data specified when calling "fmin".
The progress callback subroutine is supposed to return an indicating value
"s" for "fmin" to decide whether the optimization should
continue or stop. "fmin" continues to the next iteration when
"s=0", otherwise, it terminates with status code
"LBFGSERR_CANCELED".
The client program can also pass string values to "progress_cb", which
means it want to use a predefined progress callback subroutine. There are two
predefined progress callback subroutines, 'verbose' and 'logging'. 'verbose'
just prints out all information of each iteration, while 'logging' logs the
same information in an array ref provided by "user_data".
...
# print out the iterations
fmin($eval_cb, $x0, 'verbose');
# log iterations information in the array ref $log
my $log = [];
fmin($eval_cb, $x0, 'logging', $log);
use Data::Dumper;
print Dumper $log;
user_data
The extra user data. It will be sent to both "evaluation_cb" and
"progress_cb".
Get the status of previous call of "fmin".
...
$o->fmin(...);
# check the status
if ($o->get_status eq 'LBFGS_OK') {
...
}
# print the status out
print $o->get_status;
The status code is a string, which could be one of those in the "List of
Status Codes".
This is a shortcut of saying "get_status" eq "LBFGS_OK".
...
if ($o->fmin(...), $o->status_ok) {
...
}
m
The number of corrections to approximate the inverse hessian matrix.
The L-BFGS algorithm stores the computation results of previous "m"
iterations to approximate the inverse hessian matrix of the current iteration.
This parameter controls the size of the limited memories (corrections). The
default value is 6. Values less than 3 are not recommended. Large values will
result in excessive computing time.
epsilon
Epsilon for convergence test.
This parameter determines the accuracy with which the solution is to be found. A
minimization terminates when
||grad f(x)|| < epsilon * max(1, ||x||)
where ||.|| denotes the Euclidean (L2) norm. The default value is 1e-5.
max_iterations
The maximum number of iterations.
The L-BFGS algorithm terminates an optimization process with
"LBFGSERR_MAXIMUMITERATION" status code when the iteration count
exceedes this parameter. Setting this parameter to zero continues an
optimization process until a convergence or error. The default value is 0.
max_linesearch
The maximum number of trials for the line search.
This parameter controls the number of function and gradients evaluations per
iteration for the line search routine. The default value is 20.
min_step
The minimum step of the line search routine.
The default value is 1e-20. This value need not be modified unless the exponents
are too large for the machine being used, or unless the problem is extremely
badly scaled (in which case the exponents should be increased).
max_step
The maximum step of the line search.
The default value is 1e+20. This value need not be modified unless the exponents
are too large for the machine being used, or unless the problem is extremely
badly scaled (in which case the exponents should be increased).
ftol
A parameter to control the accuracy of the line search routine.
The default value is 1e-4. This parameter should be greater than zero and
smaller than 0.5.
gtol
A parameter to control the accuracy of the line search routine.
The default value is 0.9. If the function and gradient evaluations are
inexpensive with respect to the cost of the iteration (which is sometimes the
case when solving very large problems) it may be advantageous to set this
parameter to a small value. A typical small value is 0.1. This parameter
shuold be greater than the ftol parameter (1e-4) and smaller than 1.0.
xtol
The machine precision for floating-point values.
This parameter must be a positive value set by a client program to estimate the
machine precision. The line search routine will terminate with the status code
("LBFGSERR_ROUNDING_ERROR") if the relative width of the interval of
uncertainty is less than this parameter.
orthantwise_c
Coeefficient for the L1 norm of variables.
This parameter should be set to zero for standard minimization problems. Setting
this parameter to a positive value minimizes the objective function f(x)
combined with the L1 norm |x| of the variables, f(x) + c|x|. This parameter is
the coeefficient for the |x|, i.e., c. As the L1 norm |x| is not
differentiable at zero, the module modify function and gradient evaluations
from a client program suitably; a client program thus have only to return the
function value f(x) and gradients grad f(x) as usual. The default value is
zero.
LBFGS_OK
No error occured.
LBFGSERR_UNKNOWNERROR
Unknown error.
LBFGSERR_LOGICERROR
Logic error.
LBFGSERR_OUTOFMEMORY
Insufficient memory.
LBFGSERR_CANCELED
The minimization process has been canceled.
LBFGSERR_INVALID_N
Invalid number of variables specified.
LBFGSERR_INVALID_N_SSE
Invalid number of variables (for SSE) specified.
LBFGSERR_INVALID_MINSTEP
Invalid parameter "max_step" specified.
LBFGSERR_INVALID_MAXSTEP
Invalid parameter "max_step" specified.
LBFGSERR_INVALID_FTOL
Invalid parameter "ftol" specified.
LBFGSERR_INVALID_GTOL
Invalid parameter "gtol" specified.
LBFGSERR_INVALID_XTOL
Invalid parameter "xtol" specified.
LBFGSERR_INVALID_MAXLINESEARCH
Invalid parameter "max_linesearch" specified.
LBFGSERR_INVALID_ORTHANTWISE
Invalid parameter "orthantwise_c" 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 "min_step".
LBFGSERR_MAXIMUMSTEP
The line-search step became larger than "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 "xtol".
LBFGSERR_INVALIDPARAMETERS
A logic error (negative line-search step) occurred.
LBFGSERR_INCREASEGRADIENT
The current search direction increases the objective function value.
PDL, PDL::Opt::NonLinear
Laye Suen, <
[email protected]>
Copyright (C) 1990, Jorge Nocedal
Copyright (C) 2007, Naoaki Okazaki
Copyright (C) 2008, Laye Suen
This library is distributed under the term of the MIT license.
<
http://opensource.org/licenses/mit-license.php>
- J. Nocedal. Updating Quasi-Newton Matrices with Limited
Storage (1980) , Mathematics of Computation 35, pp. 773-782.
- D.C. Liu and J. Nocedal. On the Limited Memory Method for
Large Scale Optimization (1989), Mathematical Programming B, 45, 3, pp.
503-528.
- Jorge Nocedal's Fortran 77 implementation,
<http://www.ece.northwestern.edu/~nocedal/lbfgs.html>
- Naoaki Okazaki's C implementation (liblbfgs),
<http://www.chokkan.org/software/liblbfgs/index.html>