L-BFGS
From Wikipedia, the free encyclopedia
L-BFGS and L-BFGS-B are software packages for solving nonlinear optimization problems. They are designed for large-scale applications in which the Hessian matrix is not available or is expensive to compute. To accelerate convergence, the two codes employ a limited-memory quasi-Newton approximation that does not require much storage or computation. L-BFGS stands for "Limited memory BFGS method"; an alternate spelling is LBFGS.
The L-BFGS programs are used to compute the minimum of a function of many variables; they require that the user provide the gradient (but not the Hessian) of the objective function. The main difference between the two codes is that L-BFGS is designed to solve unconstrained problems, while L-BFGS-B can accept bounds on the variables.
'L-BFGS' is used in many applications, such as maximum likelihood estimation for probabilistic models and nonlinear least squares. It was written by Jorge Nocedal. L-BFGS is open source and freely available for educational and commercial uses; it is governed by the "MIT license": http://opensource.org/licenses/mit-license.php
'L-BFGS-B' was developed by Ciyou Zhu, Jorge Nocedal and Richard Byrd; the distribution file was last changed on 02/09/1997. The program was published in ACM Transactions on Mathematical Software; the license is described in http://www.acm.org/pubs/copyright_policy/softwareCRnotice.html
The L-BFGS codes are not capable of solving problems with general constraints (including linear constraints). For these kinds of applications, other software must be used, such as KNITRO.
Translation to Other Languages.
The L-BFGS codes are written in FORTRAN and have been translated to various languages. Following are a few links:
C: http://www.dgp.toronto.edu/~hertzman/courses/csc2521/fall_2004/driver1.C
C++, Delphi, Visual Basic, C#: http://www.alglib.net/optimization/lbfgs.php
Java: http://riso.sourceforge.net/
MATLAB wrapper: http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=9307&objectType=file
Fortran 90: http://plato.asu.edu/ftp/other_software/toms778_f90.tar.gz
C wrapper: http://homepages.inf.ed.ac.uk/s0450736/pmwiki/pmwiki.php/Main/Code
Python: http://www.scipy.org/ SciPy
R: The function 'optim' in the stats package (a core package)
[edit] References
- 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.
- R. H. Byrd, P. Lu and J. Nocedal. A Limited Memory Algorithm for Bound Constrained Optimization (1995), SIAM Journal on Scientific and Statistical Computing, 16, 5, pp. 1190-1208.
- C. Zhu, R. H. Byrd and J. Nocedal. L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization (1997), ACM Transactions on Mathematical Software, Vol 23, Num. 4, pp. 550-560.
