L-BFGS
De Wikipedia, la enciclopedia libre
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 li < xi < ui, siendo xi la variable i-ésima y li y ui 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 N2 elementos. Si N es grande, el tiempo necesario para calcular toda la matriz de forma excata puede ser prohibitivo. Es por esto que se busca una aproximación.
Tabla de contenidos |
[editar] Algoritmo
[editar] 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:
[editar] Referencias
- 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.
