#include <lbfgs.h>
Public Member Functions | |
| minimizer () | |
| Default constructor. Some members are not initialized! | |
| minimizer (SizeType n, SizeType m=5, SizeType maxfev=20, FloatType gtol=FloatType(0.9), FloatType xtol=FloatType(1.e-16), FloatType stpmin=FloatType(1.e-20), FloatType stpmax=FloatType(1.e20)) | |
| Constructor. | |
| SizeType | n () const |
| Number of free parameters (as passed to the constructor). | |
| SizeType | m () const |
| Number of corrections kept (as passed to the constructor). | |
| SizeType | maxfev () const |
| Maximum number of evaluations of the objective function per line search (as passed to the constructor). | |
| FloatType | gtol () const |
| Control of the accuracy of the line search. (as passed to the constructor). | |
| FloatType | xtol () const |
| Estimate of the machine precision (as passed to the constructor). | |
| FloatType | stpmin () const |
| Lower bound for the step in the line search. (as passed to the constructor). | |
| FloatType | stpmax () const |
| Upper bound for the step in the line search. (as passed to the constructor). | |
| bool | requests_f_and_g () const |
| Status indicator for reverse communication. | |
| bool | requests_diag () const |
| Status indicator for reverse communication. | |
| SizeType | iter () const |
| Number of iterations so far. | |
| SizeType | nfun () const |
| Total number of evaluations of the objective function so far. | |
| FloatType | euclidean_norm (const FloatType *a) const |
| Norm of gradient given gradient array of length n(). | |
| FloatType | stp () const |
| Current stepsize. | |
| bool | run (FloatType *x, FloatType f, const FloatType *g) |
| Execution of one step of the minimization. | |
| bool | run (FloatType *x, FloatType f, const FloatType *g, const FloatType *diag) |
| Execution of one step of the minimization. | |
This class 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 (parameter diag in the run() function) 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 member functions requests_f_and_g(), requests_diag(). If neither requests_f_and_g() nor requests_diag() is true the user should check for convergence (using class traditional_convergence_test or any other custom test). If the convergence test is negative, the minimizer may be called again for the next iteration.
The steplength (stp()) 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.
Fatal errors cause error exceptions to be thrown. The generic class error is sub-classed (e.g. class error_line_search_failed) to facilitate granular error handling.
A note on performance: Using Compaq Fortran V5.4 and Compaq C++ V6.5, the C++ implementation is about 15% slower than the Fortran implementation.
| minimizer | ( | SizeType | n, | |
| SizeType | m = 5, |
|||
| SizeType | maxfev = 20, |
|||
| FloatType | gtol = FloatType(0.9), |
|||
| FloatType | xtol = FloatType(1.e-16), |
|||
| FloatType | stpmin = FloatType(1.e-20), |
|||
| FloatType | stpmax = FloatType(1.e20) | |||
| ) | [inline, explicit] |
Constructor.
| 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. | |
| maxfev | Maximum number of function evaluations per line search. Termination occurs when the number of evaluations of the objective function is at least maxfev by the end of an iteration. | |
| gtol | Controls the accuracy of the line search. 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 gtol to a small value. A typical small value is 0.1. Restriction: gtol should be greater than 1e-4. | |
| 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. | |
| stpmin | Specifies the lower bound for the step in the line search. The default value is 1e-20. This value need not be modified unless the exponent is too large for the machine being used, or unless the problem is extremely badly scaled (in which case the exponent should be increased). | |
| stpmax | specifies the upper bound for the step in the line search. The default value is 1e20. This value need not be modified unless the exponent is too large for the machine being used, or unless the problem is extremely badly scaled (in which case the exponent should be increased). |
| bool requests_f_and_g | ( | ) | const [inline] |
Status indicator for reverse communication.
true if the run() function returns to request evaluation of the objective function (f) and gradients (g) for the current point (x). To continue the minimization the run() function is called again with the updated values for f and g.
See also: requests_diag()
| bool requests_diag | ( | ) | const [inline] |
Status indicator for reverse communication.
true if the run() function returns to request evaluation of the diagonal matrix (diag) for the current point (x). To continue the minimization the run() function is called again with the updated values for diag.
See also: requests_f_and_g()
| SizeType iter | ( | ) | const [inline] |
Number of iterations so far.
Note that one iteration may involve multiple evaluations of the objective function.
See also: nfun()
| SizeType nfun | ( | ) | const [inline] |
Total number of evaluations of the objective function so far.
The total number of function evaluations increases by the number of evaluations required for the line search. The total is only increased after a successful line search.
See also: iter()
| bool run | ( | FloatType * | x, | |
| FloatType | f, | |||
| const FloatType * | g | |||
| ) | [inline] |
Execution of one step of the minimization.
| x | On initial entry this must be set by the user to the values of the initial estimate of the solution vector. | |
| f | Before initial entry or on re-entry under the control of requests_f_and_g(), f must be set by the user to contain the value of the objective function at the current point x. | |
| g | Before initial entry or on re-entry under the control of requests_f_and_g(), g must be set by the user to contain the components of the gradient at the current point x. |
true if either requests_f_and_g() or requests_diag() is true. Otherwise the user should check for convergence (e.g. using class traditional_convergence_test) and call the run() function again to continue the minimization. If the return value is false the user should not update f, g or diag (other overload) before calling the run() function again.
Note that x is always modified by the run() function. Depending on the situation it can therefore be necessary to evaluate the objective function one more time after the minimization is terminated.
| bool run | ( | FloatType * | x, | |
| FloatType | f, | |||
| const FloatType * | g, | |||
| const FloatType * | diag | |||
| ) | [inline] |
Execution of one step of the minimization.
| x | See other overload. | |
| f | See other overload. | |
| g | See other overload. | |
| diag | On initial entry or on re-entry under the control of requests_diag(), diag must be set by the user to contain the values of the diagonal matrix Hk0. The routine will return at each iteration of the algorithm with requests_diag() set to true. |
diag must be positive.
1.5.6