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. Si las restricciones son complejas otros métodos, como KNITRO, deben ser usados.

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.

Algoritmo

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], 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