L-BFGS

L-BFGS y L-BFGS-B son dos métodos de optimización quasi-Newton de funciones con un gran número de parámetros o de una gran complejidad. Se trata de un método que hace un uso limitado de la memoria (usa mucha menos memoria que otros algoritmos para el mismo problema); L-BFGS viene de BFGS de memoria limitada. Permite obtener el mínimo de una función. Únicamente necesita la función y su gradiente, pero no la matriz Hessiana. L-BFGS, desarrollado por Jorge Nocedal es capaz de resolver funciones sin restricciones, mientras que la variante L-BFGS-B (Jorge Nocedal y Richard Byrd) puede resolver funciones con restricciones simples (del tipo $l_i<x_i<u_i$, siendo $x_i$ la variable i-ésima y $l_i$ y $u_i$ los límites inferior y superior de esa variable) en sus parámetros.

Para cada iteración el algoritmo busca una aproximación de la matriz Hessiana, concretamente de su inversa. Si la función tiene N variables, la matriz Hessiana tiene $N^2$ elementos. Si N es grande, el tiempo necesario para calcular toda la matriz de forma exacta puede ser prohibitivo. Es por esto que se busca una aproximación.

Implementaciones

La implementación original fue escrita en Fortran:

• [1]; Distribución L-BFGS para Unix/Linux (contiene código fuente, makefile y manual de usuario)
• [2]; Distribución L-BFGS-B para Unix/Linux (contiene código fuente, makefile y manual de usuario)

Implementaciones en otros lenguajes:

• [3], en C
• [4], en C
• [5], en C++, Visual Basic, Delphi y C#
• M1QN3 en Fortran
• [6], en Java
• [7] Plantilla:Wayback, en Matlab

Referencias

• J. Ch. Gilbert, C. Lemaréchal (1989). Some numerical experiments with variable-storage quasi-Newton algorithms. Mathematical Programming 45, 407-435.
• 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.

Enlaces externos

• Jorge Nocedal
• Richard Byrd