Método cuasi-Newton

Los métodos cuasi-Newton son métodos que se utilizan para encontrar ceros o máximos y mínimos locales de funciones, como una alternativa al método de Newton. Se pueden usar si el jacobiano o el hessiano no están disponibles o son demasiado costosos de calcular en cada iteración. El método de Newton "completo" requiere el jacobiano para buscar ceros, o el hessiano para encontrar extremos.

Buscar ceros: búsqueda de raíz

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

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

Usar 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 usados ​​para encontrar extremos requieren que la matriz que se usa sea simétrica. Si bien esto se cumple en el contexto de la búsqueda de extremos, rara vez se cumple cuando se buscan ceros. Los métodos "bueno" y "malo" de Broyden son dos métodos comúnmente usados ​​para encontrar extremos que también se pueden aplicar para encontrar ceros. Otros métodos que pueden ser utilizados son el método de columna de actualización , el método de columna de actualización inversa , el Newton cuasi método de mínimos cuadrados y la cuasi-Newton inversa método de mínimos cuadrados .

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 (que es más simple que el sistema global) de forma cíclica e iterativa hasta encontrar la solución del sistema global. ^{[2] [3]}

Buscar extrema: optimización

La búsqueda de un mínimo o máximo de una función con valores escalares no es otra cosa que la búsqueda de los ceros del gradiente de esa función. Por lo tanto, los métodos de cuasi-Newton se pueden aplicar fácilmente para encontrar los extremos de una función. En otras palabras, si${\displaystyle g}$ es el gradiente de ${\displaystyle f}$, luego busca los ceros de la función con valores vectoriales ${\displaystyle g}$ corresponde a la búsqueda de los extremos de la función escalar ${\displaystyle f}$; el jacobiano de${\displaystyle g}$ ahora se convierte en el arpillera de ${\displaystyle f}$. La principal diferencia es que la matriz de Hesse es una matriz simétrica , a diferencia de la jacobiana cuando se buscan ceros . La mayoría de los métodos cuasi-Newton utilizados en la optimización aprovechan esta propiedad.

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

En los métodos cuasi-Newton, no es necesario calcular la matriz de Hesse. En su lugar, el hessian se actualiza analizando sucesivos vectores de gradiente. Los métodos cuasi-Newton son una generalización del método secante para encontrar la raíz de la primera derivada para problemas multidimensionales. En múltiples dimensiones la ecuación secante es bajo-determinado , y métodos cuasi-Newton se diferencian en la forma en que limitan la solución, típicamente mediante la adición de una actualización de un sencillo de bajo rango a la estimación actual de la Hessian.

El primer algoritmo cuasi-Newton fue propuesto por William C. Davidon , un físico que trabaja en el Laboratorio Nacional Argonne . Desarrolló el primer algoritmo cuasi-Newton en 1959: la fórmula de actualización de 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 son actualmente la fórmula SR1 (para "rango uno simétrico"), el método BHHH , el método BFGS generalizado (sugerido independientemente por Broyden, Fletcher, Goldfarb y Shanno, en 1970), y su bajo -extensión de 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 usa 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 la matriz de Hesse (o, en el caso de los métodos cuasi-Newton, su aproximación)${\displaystyle B}$no necesita invertirse. El método de Newton y sus derivados, como los métodos de puntos interiores , requieren que se invierta el hessiano, lo que generalmente se implementa resolviendo un sistema de ecuaciones lineales y, a menudo, es bastante costoso. Por el contrario, los métodos cuasi-Newton suelen generar una estimación de${\displaystyle B^{-1}}$ directamente.

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

${\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 (${\displaystyle \nabla f}$) es el gradiente , y${\displaystyle B}$una aproximación a la matriz de Hesse . ^[4] El gradiente de esta aproximación (con respecto a${\displaystyle \Delta x}$) es

${\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}).}$

La aproximación de Hesse ${\displaystyle B}$ es elegido para satisfacer

${\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${\displaystyle B}$está indeterminado . En una dimensión, resolviendo${\displaystyle B}$y aplicar el paso de Newton con el valor actualizado es equivalente al método de la secante . Los diversos métodos de cuasi-Newton difieren en la elección de la solución de 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 (${\displaystyle B^{T}=B}$); Además, las variantes que se enumeran a continuación se pueden motivar al encontrar una actualización${\displaystyle B_{k+1}}$ que está lo más cerca posible de ${\displaystyle B_{k}}$en alguna norma ; eso es,${\displaystyle B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}}$, donde ${\displaystyle V}$es una matriz positiva-definida que define la norma. Un valor inicial aproximado${\displaystyle B_{0}=\beta I}$ a menudo es suficiente para lograr una rápida convergencia, aunque no existe una estrategia general para elegir ${\displaystyle \beta }$. ^[5] Tenga en cuenta que${\displaystyle B_{0}}$debe ser positivo-definido. El desconocido${\displaystyle x_{k}}$ se actualiza aplicando el paso de Newton calculado utilizando la matriz de Hesse aproximada actual ${\displaystyle B_{k}}$:

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

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

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

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

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

Método	${\displaystyle \displaystyle B_{k+1}=}$	${\displaystyle H_{k+1}=B_{k+1}^{-1}=}$
BFGS	${\displaystyle B_{k}+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }B_{k}\,\Delta x_{k}}}}$	${\displaystyle \left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}}$
Broyden	${\displaystyle B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{\mathrm {T} }\,\Delta x_{k}}}\,\Delta x_{k}^{\mathrm {T} }}$	${\displaystyle H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})\Delta x_{k}^{\mathrm {T} }H_{k}}{\Delta x_{k}^{\mathrm {T} }H_{k}\,y_{k}}}}$
Familia Broyden	${\displaystyle (1-\varphi _{k})B_{k+1}^{\text{BFGS}}+\varphi _{k}B_{k+1}^{\text{DFP}},\quad \varphi \in [0,1]}$
DFP	${\displaystyle \left(I-{\frac {y_{k}\,\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}}$	${\displaystyle H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }\,y_{k}}}-{\frac {H_{k}y_{k}y_{k}^{\mathrm {T} }H_{k}}{y_{k}^{\mathrm {T} }H_{k}y_{k}}}}$
SR1	${\displaystyle B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }}{(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }\,\Delta x_{k}}}}$	${\displaystyle H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }}{(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }y_{k}}}}$

Otros métodos son el método de Pearson, el método de McCormick, el método de Broyden simétrico de Powell (PSB) y el método de Greenstadt. ^[2]

Relación con la inversión de la matriz

Cuándo ${\displaystyle f}$ es una función cuadrática convexa con hessiana definida positiva ${\displaystyle B}$, uno esperaría las matrices ${\displaystyle H_{k}}$ generado por un método cuasi-Newton para converger a la inversa hessiana ${\displaystyle H=B^{-1}}$. De hecho, este es el caso de la clase de métodos cuasi-Newton basados ​​en actualizaciones con el mínimo de cambios. ^[6]

Implementaciones notables

Las implementaciones de métodos cuasi-Newton están disponibles en muchos lenguajes de programación. Las implementaciones 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 ).

• Mathematica incluye solucionadores de cuasi-Newton. ^[7]
• La biblioteca NAG contiene varias rutinas ^[8] para minimizar o maximizar una función ^[9] 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 de BFGS . ^[10] Muchos de los métodos restringidos de la caja de herramientas Optimización utilizan BFGS y la variante L-BFGS . ^[11]
• La optimrutina del optimizador de propósito general de R usa el método BFGS usando method="BFGS". ^[12]
• 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 BFGS . ^[13]

Ver también

• Método BFGS
  • L-BFGS
  • OWL-QN
• El método de Broyden
• Fórmula de actualización de DFP
• Método de Newton
• El método de Newton en optimización
• Fórmula SR1

Referencias

1. Broyden, CG (1972). "Métodos cuasi-Newton". En Murray, W. (ed.). Métodos numéricos para la 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 Cuasi-Newton de mínimos cuadrados para problemas de interacción" . Tesis doctoral, Universidad de Gante . Consultado el 14 de agosto de 2014 .
3. Rob Haelterman, Dirk Van Eester, Daan Verleyen (2015). "Acelerando la solución de un modelo de física dentro de un tokamak usando el Método de Actualización de Columna (Inversa)" . Revista de Matemática Computacional y Aplicada . 279 : 133-144. doi : 10.1016 / j.cam.2014.11.005 .
4. https://mathinsight.org/taylors_theorem_multivariable_introduction
5. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica . Nueva York: Springer. págs.  142 . ISBN 0-387-98793-2.
6. Robert Mansel Gower; Peter Richtarik (2015). "Las actualizaciones de cuasi-Newton aleatorias son algoritmos de inversión de matriz convergente lineal". arXiv : 1602.01768 [ math.NA ].
7. http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html
8. El grupo de algoritmos numéricos. "Índice de palabras clave: Cuasi-Newton" . Manual de la biblioteca NAG, Mark 23 . Consultado el 9 de febrero de 2012 .
9. El grupo de algoritmos numéricos. "E04 - Minimizar o maximizar una función" (PDF) . Manual de la biblioteca NAG, Mark 23 . Consultado el 9 de febrero de 2012 .
10. http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html
11. http://www.mathworks.com/help/toolbox/optim/ug/brnoxzl.html
12. [1]
13. http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

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 ed.). Saltador. 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.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Métodos cuasi-Newton" . Optimización numérica . Nueva York: Springer. págs. 192-221. ISBN 0-387-98793-2.
• Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.9. Métodos métricos variables o cuasi-Newton en dimensiones múltiples" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Escalas, LE (1985). Introducción a la optimización no lineal . Nueva York: MacMillan. págs. 84-106. ISBN 0-333-32552-4.