| Tanl Linguistic Pipeline |
Functions | |
| void | mcstep (double &stx, double &fx, double &dx, double &sty, double &fy, double &dy, double &stp, double fp, double dp, bool &brackt, double stpmin, double stpmax, int &info) |
| void | mcsrch (int n, double *x, double f, double *g, double *s, double &stp, const double ftol, const double xtol, const int maxfev, int &info, int &nfev, double *wa) |
| Minimize a function along a search direction. | |
| void | minimize (int n, int m, double *x, double f, double *g, bool diagco, double *diag, int *iprint, double eps, double xtol, double *w, int &iflag, int &niter, int &nfun) |
| This subroutine solves the unconstrained minimization problem. | |
This class contains code for the limited-memory Broyden-Fletcher-Goldfarb-Shanno (LBFGS) algorithm for large-scale multidimensional unconstrained minimization problems. This file is a translation of Fortran code written by Jorge Nocedal.
This code is derived from the Fortran program lbfgs.f. The C++ translation was effected mostly mechanically, with some manual clean-up; in particular, array indices start at 0 instead of 1. Most of the comments from the Fortran code have been pasted in here as well.
Here's some information on the original LBFGS Fortran source code, available at http://www.netlib.org/opt/lbfgs_um.shar. This info is taken verbatim from the Netlib blurb on the Fortran source.
file opt/lbfgs_um.shar for unconstrained optimization problems alg limited memory BFGS method by J. Nocedal contact nocedal@eecs.nwu.edu ref D. C. Liu and J. Nocedal, ``On the limited memory BFGS method for , large scale optimization methods'' Mathematical Programming 45 , (1989), pp. 503-528. , (Postscript file of this paper is available via anonymous ftp , to eecs.nwu.edu in the directory pub/lbfgs/lbfgs_um.)
| void LBFGS::mcsrch | ( | int | n, | |
| double * | x, | |||
| double | f, | |||
| double * | g, | |||
| double * | s, | |||
| double & | stp, | |||
| const double | ftol, | |||
| const double | xtol, | |||
| const int | maxfev, | |||
| int & | info, | |||
| int & | nfev, | |||
| double * | wa | |||
| ) |
Minimize a function along a search direction.
This code is a C++ translation of the function MCSRCH from lbfgs.f, which in turn is a slight modification of the subroutine CSRCH of More' and Thuente. This function, in turn, calls mcstep.
The C++ translation was effected mostly mechanically, with some manual clean-up; in particular, array indices start at 0 instead of 1. Most of the comments from the Fortran code have been pasted in here as well.
The purpose of mcsrch is to find a step which satisfies a sufficient decrease condition and a curvature condition.
At each stage this function updates an interval of uncertainty with endpoints stx and sty. The interval of uncertainty is initially chosen so that it contains a minimizer of the modified function
f(x+stp*s) - f(x) - ftol*stp*(gradf(x)'s).
If a step is obtained for which the modified function has a nonpositive function value and nonnegative derivative, then the interval of uncertainty is chosen so that it contains a minimizer of f(x+stp*s).
The algorithm is designed to find a step which satisfies the sufficient decrease condition
f(x+stp*s) <= f(X) + ftol*stp*(gradf(x)'s),
and the curvature condition
abs(gradf(x+stp*s)'s)) <= gtol*abs(gradf(x)'s).
If ftol is less than gtol and if, for example, the function is bounded below, then there is always a step which satisfies both conditions. If no step can be found which satisfies both conditions, then the algorithm usually stops when rounding errors prevent further progress. In this case stp only satisfies the sufficient decrease condition.
| n | The number of variables. | |
| x | On entry this contains the base point for the line search. On exit it contains x + stp*s. | |
| f | On entry this contains the value of the objective function at x. On exit it contains the value of the objective function at x + stp*s. | |
| g | On entry this contains the gradient of the objective function at x. On exit it contains the gradient at x + stp*s. | |
| s | The search direction. | |
| stp | On entry this contains an initial estimate of a satifactory step length. On exit stp contains the final estimate. | |
| ftol | Tolerance for the sufficient decrease condition. | |
| xtol | Termination occurs when the relative width of the interval of uncertainty is at most xtol. | |
| maxfev | Termination occurs when the number of evaluations of the objective function is at least maxfev by the end of an iteration. | |
| info | This is an output variable, which can have these values:
| |
| nfev | On exit, this is set to the number of function evaluations. | |
| wa | Temporary storage array, of length n. |
| void LBFGS::minimize | ( | int | n, | |
| int | m, | |||
| double * | x, | |||
| double | f, | |||
| double * | g, | |||
| bool | diagco, | |||
| double * | diag, | |||
| int * | iprint, | |||
| double | eps, | |||
| double | xtol, | |||
| double * | w, | |||
| int & | iflag, | |||
| int & | niter, | |||
| int & | nfun | |||
| ) |
This subroutine solves the unconstrained minimization problem.
min f(x), x = (x1,x2,...,x_n),
using the limited-memory BFGS method. The routine is especially effective on problems involving a large number of variables. In a typical iteration of this method an approximation Hk to the inverse of the Hessian is obtained by applying m BFGS updates to a diagonal matrix Hk0, using information from the previous M steps. The user specifies the number m, which determines the amount of storage required by the routine. The user may also provide the diagonal matrices Hk0 if not satisfied with the default choice. The algorithm is described in "On the limited memory BFGS method
for large scale optimization", by D. Liu and J. Nocedal, Mathematical Programming B 45 (1989) 503-528.
The user is required to calculate the function value f and its gradient g. In order to allow the user complete control over these computations, reverse communication is used. The routine must be called repeatedly under the control of the parameter iflag.
The steplength is determined at each iteration by means of the line search routine mcsrch, which is a slight modification of the routine CSRCH written by More' and Thuente.
The only variables that are machine-dependent are xtol, stpmin and stpmax.
Progress messages are printed to cerr, and non-fatal error messages are printed to cerr. Fatal errors return error codes, as listed below.
| n | The number of variables in the minimization problem. Restriction: n > 0. | |
| m | The number of corrections used in the BFGS update. Values of m less than 3 are not recommended; large values of m will result in excessive computing time. 3 <= m <= 7 is recommended. Restriction: m > 0. | |
| x | On initial entry this must be set by the user to the values of the initial estimate of the solution vector. On exit with iflag = 0, it contains the values of the variables at the best point found (usually a solution). | |
| f | Before initial entry and on a re-entry with iflag = 1, it must be set by the user to contain the value of the function f at the point x. | |
| g | Before initial entry and on a re-entry with iflag = 1, it must be set by the user to contain the components of the gradient g at the point x. | |
| diagco | Set this to true if the user wishes to provide the diagonal matrix Hk0 at each iteration. Otherwise it should be set to false in which case lbfgs will use a default value described below. If diagco is set to true the routine will return at each iteration of the algorithm with iflag = 2, and the diagonal matrix Hk0 must be provided in the array diag. | |
| diag | If diagco = true, then on initial entry or on re-entry with iflag = 2, diag must be set by the user to contain the values of the diagonal matrix Hk0. Restriction: all elements of diag must be positive. | |
| iprint | Specifies output generated by lbfgs. iprint[0] specifies the frequency of the output:
|
iprint[1] specifies the type of output generated:
iprint[1] = 0: iteration count, number of function evaluations, function value, norm of the gradient, and steplength, iprint[1] = 1: same as iprint[1]=0, plus vector of variables and gradient vector at the initial point, iprint[1] = 2: same as iprint[1]=1, plus vector of variables, iprint[1] = 3: same as iprint[1]=2, plus gradient vector. | eps | Determines the accuracy with which the solution is to be found. The subroutine terminates when
||G|| < EPS max(1,||X||),
where | |
| xtol | An estimate of the machine precision (e.g. 10e-16 on a SUN station 3/60). The line search routine will terminate if the relative width of the interval of uncertainty is less than xtol. | |
| iflag | This must be set to 0 on initial entry to lbfgs. A return with iflag < 0 indicates an error, and iflag = 0 indicates that the routine has terminated without detecting errors. On a return with iflag = 1, the user must evaluate the function f and gradient g. On a return with iflag = 2, the user must provide the diagonal matrix Hk0. |
The following negative values of iflag, detecting an error, are possible:
iflag = -1 The line search routine mcsrch failed. One of the following messages is printed: xtol. iflag = -2 The i-th diagonal element of the diagonal inverse Hessian approximation, given in DIAG, is not positive. iflag = -3 Improper input parameters for LBFGS (n or m are not positive).