Método de cuasi-Newton

Algoritmo de optimización

En el análisis numérico , un método cuasi-Newton es un método numérico iterativo utilizado para encontrar ceros o para encontrar máximos y mínimos locales de funciones a través de una fórmula de recurrencia iterativa muy similar a la del método de Newton , excepto que se utilizan aproximaciones de las derivadas de las funciones en lugar de derivadas exactas. El método de Newton requiere la matriz jacobiana de todas las derivadas parciales de una función multivariada cuando se utiliza para buscar ceros o la matriz hessiana cuando se utiliza para encontrar extremos . Los métodos cuasi-Newton, por otro lado, se pueden utilizar cuando las matrices jacobianas o las matrices hessianas no están disponibles o no son prácticas para calcular en cada iteración.

Algunos métodos iterativos que se reducen al método de Newton, como la programación cuadrática secuencial , también pueden considerarse métodos cuasi-Newton.

Búsqueda de ceros: búsqueda de raíces

El método de Newton para encontrar ceros de una función de múltiples variables está dado por , donde es la inversa izquierda de la matriz jacobiana de evaluada para . ${\displaystyle g}$ ${\displaystyle x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})}$ ${\displaystyle [J_{g}(x_{n})]^{-1}}$ ${\displaystyle J_{g}(x_{n})}$ ${\displaystyle g}$ ${\displaystyle x_{n}}$

Estrictamente hablando, cualquier método que reemplace el jacobiano exacto con una aproximación es un método cuasi-Newton. ^[1] Por ejemplo, el método de la cuerda (donde se reemplaza por para todas las iteraciones) es un ejemplo simple. Los métodos que se dan a continuación para la optimización se refieren a una subclase importante de los métodos cuasi-Newton, los métodos secantes . ^[2] ${\displaystyle J_{g}(x_{n})}$ ${\displaystyle J_{g}(x_{n})}$ ${\displaystyle J_{g}(x_{0})}$

El uso de métodos desarrollados para encontrar extremos con el fin de encontrar ceros no siempre es una buena idea, ya que la mayoría de los métodos utilizados para encontrar extremos requieren que la matriz que se utiliza sea simétrica. Si bien esto es válido en el contexto de la búsqueda de extremos, rara vez se cumple cuando se buscan ceros. Los métodos "buenos" y "malos" de Broyden son dos métodos que se utilizan comúnmente para encontrar extremos y que también se pueden aplicar para encontrar ceros. Otros métodos que se pueden utilizar son el método de actualización de columnas, el método de actualización de columnas inversa, el método de mínimos cuadrados cuasi-Newton y el método de mínimos cuadrados inversos cuasi-Newton.

Más recientemente, se han aplicado métodos cuasi-Newton para encontrar la solución de múltiples sistemas acoplados de ecuaciones (por ejemplo, problemas de interacción fluido-estructura o problemas de interacción en física). Permiten encontrar la solución resolviendo cada sistema constituyente por separado (lo que es más simple que el sistema global) de manera cíclica e iterativa hasta que se encuentra la solución del sistema global. ^{[2] [3]}

Búsqueda de extremos: optimización

La búsqueda de un mínimo o máximo de una función escalar está estrechamente relacionada con la búsqueda de los ceros del gradiente de esa función. Por lo tanto, los métodos cuasi-Newton se pueden aplicar fácilmente para encontrar los extremos de una función. En otras palabras, si es el gradiente de , entonces la búsqueda de los ceros de la función vectorial corresponde a la búsqueda de los extremos de la función escalar ; el jacobiano de ahora se convierte en el hessiano de . La principal diferencia es que la matriz hessiana es una matriz simétrica , a diferencia del jacobiano cuando se buscan ceros. La mayoría de los métodos cuasi-Newton utilizados en optimización explotan esta simetría. ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$

En optimización , los métodos cuasi-Newton (un caso especial de los métodos de métrica variable ) son algoritmos para encontrar máximos y mínimos locales de funciones . Los métodos cuasi-Newton para optimización se basan en el método de Newton para encontrar los puntos estacionarios de una función, puntos donde el gradiente es 0. El método de Newton supone que la función puede aproximarse localmente como una cuadrática en la región alrededor del óptimo, y utiliza las derivadas primera y segunda para encontrar el punto estacionario. En dimensiones superiores, el método de Newton utiliza el gradiente y la matriz hessiana de derivadas segundas de la función a minimizar.

En los métodos cuasi-Newton, no es necesario calcular la matriz hessiana. La hessiana se actualiza analizando vectores de gradiente sucesivos. Los métodos cuasi-Newton son una generalización del método secante para encontrar la raíz de la primera derivada en problemas multidimensionales. En múltiples dimensiones, la ecuación secante está subdeterminada y los métodos cuasi-Newton difieren en cómo restringen la solución, generalmente agregando una simple actualización de bajo rango a la estimación actual de la hessiana.

El primer algoritmo cuasi-Newton fue propuesto por William C. Davidon , un físico que trabajaba en el Laboratorio Nacional de Argonne . Desarrolló el primer algoritmo cuasi-Newton en 1959: la fórmula de actualización DFP , que luego fue popularizada por Fletcher y Powell en 1963, pero que rara vez se usa en la actualidad. Los algoritmos cuasi-Newton más comunes actualmente son la fórmula SR1 (para "rango uno simétrico"), el método BHHH , el método BFGS (sugerido independientemente por Broyden, Fletcher, Goldfarb y Shanno, en 1970) y su extensión de baja memoria L-BFGS . La clase de Broyden es una combinación lineal de los métodos DFP y BFGS.

La fórmula SR1 no garantiza que la matriz de actualización mantenga una definición positiva y se puede utilizar para problemas indefinidos. El método de Broyden no requiere que la matriz de actualización sea simétrica y se utiliza para encontrar la raíz de un sistema general de ecuaciones (en lugar del gradiente) actualizando el jacobiano (en lugar del hessiano).

Una de las principales ventajas de los métodos cuasi-Newton sobre el método de Newton es que no es necesario invertir la matriz hessiana (o, en el caso de los métodos cuasi-Newton, su aproximación) . El método de Newton y sus derivados, como los métodos de puntos interiores , requieren que se invierta la matriz hessiana, lo que normalmente se implementa resolviendo un sistema de ecuaciones lineales y suele ser bastante costoso. Por el contrario, los métodos cuasi-Newton suelen generar una estimación de directamente. ${\displaystyle B}$ ${\displaystyle B^{-1}}$

Al igual que en el método de Newton , se utiliza una aproximación de segundo orden para hallar el mínimo de una función . La serie de Taylor de alrededor de una iteración es ${\displaystyle f(x)}$ ${\displaystyle f(x)}$

${\displaystyle f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{\mathrm {T} }\,\Delta x+{\frac {1}{2}}\Delta x^{\mathrm {T} }B\,\Delta x,}$

donde ( ) es el gradiente , y una aproximación a la matriz hessiana . ^[4] El gradiente de esta aproximación (con respecto a ) es ${\displaystyle \nabla f}$ ${\displaystyle B}$ ${\displaystyle \Delta x}$

${\displaystyle \nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\,\Delta x,}$

y establecer este gradiente en cero (que es el objetivo de la optimización) proporciona el paso de Newton:

${\displaystyle \Delta x=-B^{-1}\nabla f(x_{k}).}$

Se elige la aproximación hessiana para satisfacer ${\displaystyle B}$

${\displaystyle \nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\,\Delta x,}$

que se llama ecuación secante (la serie de Taylor del gradiente en sí). En más de una dimensión está subdeterminada . En una dimensión, resolver y aplicar el paso de Newton con el valor actualizado es equivalente al método de la secante . Los diversos métodos cuasi-Newton difieren en su elección de la solución a la ecuación secante (en una dimensión, todas las variantes son equivalentes). La mayoría de los métodos (pero con excepciones, como el método de Broyden ) buscan una solución simétrica ( ); además, las variantes enumeradas a continuación pueden estar motivadas por la búsqueda de una actualización que sea lo más cercana posible a en alguna norma ; es decir, , donde es alguna matriz definida positiva que define la norma. Un valor inicial aproximado suele ser suficiente para lograr una convergencia rápida, aunque no hay una estrategia general para elegir . ^[5] Nótese que debe ser definida positiva. La incógnita se actualiza aplicando el paso de Newton calculado utilizando la matriz hessiana aproximada actual : ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B^{T}=B}$ ${\displaystyle B_{k+1}}$ ${\displaystyle B_{k}}$ ${\displaystyle B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}}$ ${\displaystyle V}$ ${\displaystyle B_{0}=\beta I}$ ${\displaystyle \beta }$ ${\displaystyle B_{0}}$ ${\displaystyle x_{k}}$ ${\displaystyle B_{k}}$

• ${\displaystyle \Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k})}$, con elegido para satisfacer las condiciones de Wolfe ; ${\displaystyle \alpha }$
• ${\displaystyle x_{k+1}=x_{k}+\Delta x_{k}}$;
• El gradiente calculado en el nuevo punto , y ${\displaystyle \nabla f(x_{k+1})}$

${\displaystyle y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})}$

se utiliza para actualizar el hessiano aproximado , o directamente su inverso utilizando la fórmula de Sherman-Morrison . ${\displaystyle B_{k+1}}$ ${\displaystyle H_{k+1}=B_{k+1}^{-1}}$

• Una propiedad clave de las actualizaciones BFGS y DFP es que si es positiva-definida y se elige para satisfacer las condiciones de Wolfe, entonces también es positiva-definida. ${\displaystyle B_{k}}$ ${\displaystyle \alpha _{k}}$ ${\displaystyle B_{k+1}}$

Las fórmulas de actualización más populares son:

Otros métodos son el método de Pearson, el método de McCormick, el método Powell symmetrical Broyden (PSB) y el método de Greenstadt. ^[2] Estas actualizaciones recursivas de matriz de bajo rango también se pueden representar como una matriz inicial más una corrección de bajo rango. Esta es la representación compacta cuasi-Newton , que es particularmente efectiva para problemas restringidos y/o grandes.

Relación con la inversión de matrices

Cuando es una función cuadrática convexa con hessiano positivo definido , se esperaría que las matrices generadas por un método cuasi-Newton converjan al hessiano inverso . Este es de hecho el caso para la clase de métodos cuasi-Newton basados ​​en actualizaciones de cambio mínimo. ^[6] ${\displaystyle f}$ ${\displaystyle B}$ ${\displaystyle H_{k}}$ ${\displaystyle H=B^{-1}}$

Implementaciones notables

Las implementaciones de métodos cuasi-Newton están disponibles en muchos lenguajes de programación.

Las implementaciones de código abierto notables incluyen:

• GNU Octave utiliza una forma de BFGS en su fsolvefunción, con extensiones de región de confianza .
• La biblioteca científica GNU implementa el algoritmo Broyden-Fletcher-Goldfarb-Shanno ( BFGS ).
• ALGLIB implementa (L)BFGS en C++ y C#
• optimLa rutina optimizadora de propósito general de R utiliza el método BFGSmethod="BFGS" mediante el uso de . ^[7]
• Scipy .optimize tiene fmin_bfgs. En la extensión SciPy para Python , la scipy.optimize.minimizefunción incluye, entre otros métodos, una implementación de BFGS . ^[8]

Las implementaciones propietarias notables incluyen:

• Mathematica incluye solucionadores cuasi-Newton. ^[9]
• La biblioteca NAG contiene varias rutinas ^[10] para minimizar o maximizar una función ^[11] que utilizan algoritmos cuasi-Newton.
• En la caja de herramientas de optimización de MATLAB , la fminuncfunción utiliza (entre otros métodos) el método cuasi-Newton BFGS . ^[12] Muchos de los métodos restringidos de la caja de herramientas de optimización utilizan BFGS y la variante L-BFGS . ^[13]

Véase también

• Método BFGS
  • L-BFGS
  • BÚHO-QN
• El método de Broyden
• Fórmula de actualización de DFP
• El método de Newton
• El método de Newton en optimización
• Fórmula SR1
• Representación compacta cuasi-Newton

Referencias

1. Broyden, CG (1972). "Métodos cuasi-newtonianos". En Murray, W. (ed.). Métodos numéricos para optimización sin restricciones . Londres: Academic Press. págs. 87-106. ISBN. 0-12-512250-0.
2. Haelterman, Rob (2009). "Estudio analítico del método de mínimos cuadrados Quasi-Newton para problemas de interacción". Tesis doctoral, Universidad de Ghent . Consultado el 14 de agosto de 2014 .
3. Rob Haelterman; Dirk Van Eester; Daan Verleyen (2015). "Aceleración de la solución de un modelo de física dentro de un tokamak utilizando el método de actualización de columnas (inversa)". Revista de Matemática Computacional y Aplicada . 279 : 133–144. doi : 10.1016/j.cam.2014.11.005 .
4. "Introducción al teorema de Taylor para funciones multivariables - Math Insight". mathinsight.org . Consultado el 11 de noviembre de 2021 .
5. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica . Nueva York: Springer. pp. 142. ISBN. 0-387-98793-2.
6. Robert Mansel Gower; Peter Richtarik (2015). "Las actualizaciones aleatorias de quasi-Newton son algoritmos de inversión de matrices convergentes lineales". arXiv : 1602.01768 [math.NA].
7. "Función optima - RDocumentation". www.rdocumentation.org . Consultado el 21 de febrero de 2022 .
8. "Scipy.optimize.minimize — Manual de SciPy v1.7.1".
9. "Optimización sin restricciones: métodos para la minimización local: documentación del lenguaje Wolfram". reference.wolfram.com . Consultado el 21 de febrero de 2022 .
10. The Numerical Algorithms Group. "Índice de palabras clave: Quasi-Newton". Manual de la biblioteca NAG, Mark 23. Consultado el 9 de febrero de 2012 .
11. The Numerical Algorithms Group. "E04 – Minimizar o maximizar una función" (PDF) . Manual de la biblioteca NAG, Mark 23 . Consultado el 9 de febrero de 2012 .
12. "Encuentre el mínimo de una función multivariable sin restricciones - MATLAB fminunc".
13. "Algoritmos de optimización no lineal restringida - MATLAB y Simulink". www.mathworks.com . Consultado el 21 de febrero de 2022 .

Lectura adicional

• Bonnans, JF; Gilbert, J. Ch.; Lemaréchal, C .; Sagastizábal, CA (2006). Optimización numérica: aspectos teóricos y numéricos (segunda edición). Springer. ISBN 3-540-35445-X.
• Fletcher, Roger (1987), Métodos prácticos de optimización (2.ª ed.), Nueva York: John Wiley & Sons , ISBN 978-0-471-91547-8.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Métodos cuasi-newtonianos". Optimización numérica . Nueva York: Springer. pp. 192–221. ISBN. 0-387-98793-2.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.9. Métodos métricos variables o cuasi-newtonianos en multidimensiones". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Scales, LE (1985). Introducción a la optimización no lineal. Nueva York: MacMillan. pp. 84–106. ISBN 0-333-32552-4.