En optimización numérica , el algoritmo Broyden-Fletcher-Goldfarb-Shanno ( BFGS ) es un método iterativo para resolver problemas de optimización no lineal sin restricciones . [1] Al igual que el relacionado método Davidon-Fletcher-Powell , BFGS determina la dirección de descenso por el preacondicionamiento de la gradiente con información curvatura. Lo hace mejorando gradualmente una aproximación a la matriz hessiana de la función de pérdida, obtenido solo a partir de evaluaciones de gradiente (o evaluaciones de gradiente aproximadas) mediante un método secante generalizado . [2]
Dado que las actualizaciones de la matriz de curvatura BFGS no requieren inversión de matriz , su complejidad computacional es solo, en comparación con en el método de Newton . También es de uso común L-BFGS , que es una versión de memoria limitada de BFGS que es particularmente adecuada para problemas con un gran número de variables (por ejemplo,> 1000). La variante BFGS-B maneja restricciones de caja simples. [3]
El algoritmo lleva el nombre de Charles George Broyden , Roger Fletcher , Donald Goldfarb y David Shanno . [4] [5] [6] [7]
Razón fundamental
El problema de optimización es minimizar , dónde es un vector en , y es una función escalar diferenciable. No hay restricciones sobre los valores que puede tomar.
El algoritmo comienza en una estimación inicial del valor óptimo. y procede de forma iterativa para obtener una mejor estimación en cada etapa.
La dirección de búsqueda p k en la etapa k viene dada por la solución del análogo de la ecuación de Newton:
dónde es una aproximación a la matriz de Hesse , que se actualiza iterativamente en cada etapa, yes el gradiente de la función evaluada en x k . Luego se usa una búsqueda de línea en la dirección p k para encontrar el siguiente punto x k +1 minimizando sobre el escalar
La condición de cuasi-Newton impuesta a la actualización de es
Dejar y , luego satisface , que es la ecuación secante. La condición de curvatura debería estar satisfecho por para ser definida positiva, lo cual se puede verificar multiplicando previamente la ecuación secante con . Si la función no es muy convexa, entonces la condición debe cumplirse explícitamente.
En lugar de requerir la matriz hessiana completa en el punto para ser calculado como , el hessiano aproximado en la etapa k se actualiza mediante la adición de dos matrices:
Ambas cosas y son matrices simétricas de rango uno, pero su suma es una matriz de actualización de rango dos. La matriz de actualización de BFGS y DFP se diferencia de su predecesora por una matriz de rango dos. Otro método de rango uno más simple se conoce como método simétrico de rango uno , que no garantiza la definición positiva . Para mantener la simetría y la definición positiva de, el formulario de actualización se puede elegir como . Imponiendo la condición secante,. Elegir y , podemos obtener: [8]
Finalmente, sustituimos y dentro y obtener la ecuación de actualización de :
Algoritmo
De una suposición inicial y una matriz de Hesse aproximada los siguientes pasos se repiten como converge a la solución:
- Obtener una dirección resolviendo .
- Realice una optimización unidimensional ( búsqueda de líneas ) para encontrar un tamaño de paso aceptableen la dirección encontrada en el primer paso. Si se realiza una búsqueda de línea exacta, entonces. En la prctica, una bsqueda de lnea inexacta suele ser suficiente, con unsatisfaciendo las condiciones de Wolfe .
- Colocar y actualizar .
- .
- .
denota la función objetivo a minimizar. La convergencia se puede verificar observando la norma del gradiente,. Sise inicializa con , el primer paso será equivalente a un descenso de gradiente , pero los pasos posteriores son cada vez más refinados por, la aproximación al hessiano.
El primer paso del algoritmo se lleva a cabo utilizando la inversa de la matriz. , que se puede obtener de manera eficiente aplicando la fórmula de Sherman-Morrison al paso 5 del algoritmo, dando
Esto se puede calcular de manera eficiente sin matrices temporales, reconociendo que es simétrico, y que y son escalares, usando una expansión como
En problemas de estimación estadística (como máxima verosimilitud o inferencia bayesiana), los intervalos creíbles o los intervalos de confianza para la solución se pueden estimar a partir de la inversa de la matriz hessiana final [ cita requerida ] . Sin embargo, estas cantidades están técnicamente definidas por la verdadera matriz de Hesse, y la aproximación BFGS puede no converger a la verdadera matriz de Hesse. [9]
Implementaciones notables
- El software de optimización no lineal a gran escala Artelys Knitro implementa, entre otros, algoritmos BFGS y L-BFGS.
- El GSL implementa BFGS como gsl_multimin_fdfminimizer_vector_bfgs2. [10]
- En MATLAB Optimization Toolbox , la función fminunc [11] usa BFGS con búsqueda de línea cúbica cuando el tamaño del problema se establece en "escala media". [12]
- En R , el algoritmo BFGS (y la versión L-BFGS-B que permite restricciones de caja) se implementa como una opción de la función base optim (). [13]
- En SciPy , la función scipy.optimize.fmin_bfgs implementa BFGS. [14] También es posible ejecutar BFGS usando cualquiera de los algoritmos L-BFGS configurando el parámetro L en un número muy grande.
Ver también
- Algoritmo BHHH
- Fórmula de Davidon-Fletcher-Powell
- Descenso de gradiente
- L-BFGS
- Algoritmo de Levenberg-Marquardt
- Método de Nelder-Mead
- Búsqueda de patrones (optimización)
- Métodos cuasi-Newton
- Rango uno simétrico
Referencias
- ^ Fletcher, Roger (1987), Métodos prácticos de optimización (2.a ed.), Nueva York: John Wiley & Sons , ISBN 978-0-471-91547-8
- ^ Dennis, JE, Jr .; Schnabel, Robert B. (1983), "Métodos secantes para la minimización sin restricciones" , Métodos numéricos para la optimización sin restricciones y ecuaciones no lineales , Englewood Cliffs, Nueva Jersey: Prentice-Hall, págs. 194-215, ISBN 0-13-627216-9
- ^ Byrd, Richard H .; Lu, Peihuang; Nocedal, Jorge; Zhu, Ciyou (1995), "A Limited Memory Algorithm for Bound Constrained Optimization" , SIAM Journal on Scientific Computing , 16 (5): 1190–1208, CiteSeerX 10.1.1.645.5814 , doi : 10.1137 / 0916069
- ^ Broyden, CG (1970), "La convergencia de una clase de algoritmos de minimización de doble rango", Revista del Instituto de Matemáticas y sus Aplicaciones , 6 : 76–90, doi : 10.1093 / imamat / 6.1.76
- ^ Fletcher, R. (1970), "A New Approach to Variable Metric Algorithms", Computer Journal , 13 (3): 317–322, doi : 10.1093 / comjnl / 13.3.317
- ^ Goldfarb, D. (1970), "A Family of Variable Metric Updates Derived by Variational Means", Mathematics of Computation , 24 (109): 23-26, doi : 10.1090 / S0025-5718-1970-0258249-6
- ^ Shanno, David F. (julio de 1970), "Condicionamiento de métodos cuasi-Newton para la minimización de funciones", Mathematics of Computation , 24 (111): 647–656, doi : 10.1090 / S0025-5718-1970-0274029-X , MR 0274029
- ^ Fletcher, Roger (1987), Métodos prácticos de optimización (2a ed.), Nueva York: John Wiley & Sons , ISBN 978-0-471-91547-8
- ^ Ge, Ren-pu; Powell, MJD (1983). "La convergencia de matrices métricas variables en optimización ilimitada". Programación matemática . 27 (2). 123. doi : 10.1007 / BF02591941 . S2CID 8113073 .
- ^ "Biblioteca científica GNU - documentación GSL 2.6" . www.gnu.org . Consultado el 22 de noviembre de 2020 .
- ^ "Encontrar el mínimo de función multivariable no restringida - MATLAB fminunc" . www.mathworks.com . Consultado el 22 de noviembre de 2020 .
- ^ "Optimización no lineal sin restricciones: ejemplos y algoritmos de optimización (Optimization Toolbox ™)" . 2010-10-28. Archivado desde el original el 28 de octubre de 2010 . Consultado el 22 de noviembre de 2020 .
- ^ "R: Optimización de propósito general" . stat.ethz.ch . Consultado el 22 de noviembre de 2020 .
- ^ "scipy.optimize.fmin_bfgs - Guía de referencia de SciPy v1.5.4" . docs.scipy.org . Consultado el 22 de noviembre de 2020 .
Otras lecturas
- Avriel, Mordecai (2003), Programación no lineal: análisis y métodos , Dover Publishing, ISBN 978-0-486-43227-4
- Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006), "Métodos Newtonianos", Optimización numérica: aspectos teóricos y prácticos (Segunda ed.), Berlín: Springer, págs. 51–66, ISBN 3-540-35445-X
- Fletcher, Roger (1987), Métodos prácticos de optimización (2a ed.), Nueva York: John Wiley & Sons , ISBN 978-0-471-91547-8
- Luenberger, David G .; Ye, Yinyu (2008), Programación lineal y no lineal , Serie internacional en Investigación de operaciones y ciencia de la gestión, 116 (Tercera ed.), Nueva York: Springer, págs. Xiv + 546, ISBN 978-0-387-74502-2, MR 2423726
- Kelley, CT (1999), Métodos iterativos para la optimización , Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas, págs. 71–86, ISBN 0-89871-433-8
- Nocedal, Jorge; Wright, Stephen J. (2006), Optimización numérica (2.a ed.), Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-30303-1