NAME
   Algorithm::LBFGS - Perl extension for L-BFGS

SYNOPSIS
     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 ];

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

 get_param
   Query the value of a parameter.

      my $o = Algorithm::LBFGS->new;
      print $o->get_param('epsilon'); # 1e-5

 set_param
   Change the values of one or several parameters.

      my $o = Algorithm::LBFGS->new;
      $o->set_param(epsilon => 1e-6, m => 7);

 fmin
   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_status
   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".

 status_ok
   This is a shortcut of saying "get_status" eq "LBFGS_OK".

     ...

     if ($o->fmin(...), $o->status_ok) {
         ...
     }

 List of Parameters
  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.

 List of Status Codes
  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.

SEE ALSO
   PDL, PDL::Opt::NonLinear

AUTHOR
   Laye Suen, <[email protected]>

COPYRIGHT AND LICENSE
   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>

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

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.