Método cuasi-Newton

En análisis numérico , un método cuasi-Newton es un método numérico iterativo que se utiliza para encontrar ceros o máximos y mínimos locales de funciones mediante una fórmula de recurrencia iterativa muy similar a la del método de Newton , con la diferencia de que utiliza 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 jacobiana o hessiana no están disponibles o su cálculo en cada iteración resulta impracticable.

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-Newtonianos.

Método de Newton para encontrar los ceros de una función.${\displaystyle g}$de múltiples variables viene dado por${\displaystyle x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})}$, dónde${\displaystyle [J_{g}(x_{n})]^{-1}}$es la inversa derecha 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 cuerdas (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 presentan a continuación para la optimización se refieren a una subclase importante de los métodos cuasi-Newton, los métodos secantes . ^{[ 2 ]}

Utilizar métodos desarrollados para encontrar extremos con el fin de encontrar ceros no siempre es una buena idea, ya que la mayoría de estos métodos requieren que la matriz empleada sea simétrica. Si bien esto se cumple en el contexto de la búsqueda de extremos, rara vez se cumple al buscar ceros. Los métodos "bueno" y "malo" de Broyden son dos métodos comúnmente utilizados para encontrar extremos que también pueden aplicarse 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). Estos métodos permiten encontrar la solución resolviendo cada sistema constituyente por separado (lo cual es más sencillo que el sistema global) de forma cíclica e iterativa hasta hallar la solución del sistema global. ^{[ 2 ] [ 3 ]}

La búsqueda de un mínimo o un 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${\displaystyle g}$es el gradiente de${\displaystyle f}$, luego buscando los ceros de la función vectorial${\displaystyle g}$corresponde a la búsqueda de los extremos de la función escalar${\displaystyle f}$; el jacobino de${\displaystyle g}$ahora se convierte en el Hessiano de${\displaystyle f}$La principal diferencia radica en que la matriz hessiana es simétrica , a diferencia de la matriz jacobiana, cuando se buscan ceros . La mayoría de los métodos cuasi-Newton utilizados en optimización aprovechan esta simetría.

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 . Estos métodos se basan en el método de Newton para hallar los puntos estacionarios de una función, es decir, aquellos donde el gradiente es cero. El método de Newton asume que la función puede aproximarse localmente como una cuadrática en la región cercana al ó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 las segundas derivadas de la función que se desea minimizar.

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

El primer algoritmo cuasi-Newton fue propuesto por William C. Davidon , físico del Laboratorio Nacional Argonne . Desarrolló la fórmula de actualización DFP en 1959 , popularizada posteriormente por Fletcher y Powell en 1963, aunque hoy en día se usa con poca frecuencia. Los algoritmos cuasi-Newton más comunes son la fórmula SR1 (de "rango uno simétrico"), el método BHHH , el método BFGS (propuesto 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 sea definida positiva y puede utilizarse para problemas indefinidos. El método de Broyden no requiere que la matriz de actualización sea simétrica y se utiliza para hallar 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 hessiana (o, en el caso de los métodos cuasi-Newton, su aproximación)${\displaystyle B}$no necesita ser invertido. El método de Newton y sus derivados, como los métodos de punto interior , requieren que el hessiano sea invertido, lo que normalmente se implementa resolviendo un sistema de ecuaciones lineales y suele ser bastante costoso. En contraste, los métodos cuasi-Newton generalmente generan una estimación de${\displaystyle B^{-1}}$directamente.

Al igual que en el método de Newton , se utiliza 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,}$

dónde (${\displaystyle \nabla f}$) es el gradiente y${\displaystyle B}$una aproximación a la matriz hessiana . ^{[ 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 al establecer este gradiente en cero (que es el objetivo de la optimización) se obtiene el paso de Newton:

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

La aproximación hessiana${\displaystyle B}$se elige para satisfacer

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

que se denomina ecuación secante (la serie de Taylor del gradiente mismo). En más de una dimensión${\displaystyle B}$está subdeterminado . Usando${\displaystyle n}$Serían suficientes secantes diferentes para determinar${\displaystyle B}$, pero es equivalente a calcular una matriz hessiana de diferencias finitas. En una dimensión, resolver para${\displaystyle B}$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 de la 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 pueden estar motivadas por encontrar una actualización.${\displaystyle B_{k+1}}$que sea lo más cercano posible a${\displaystyle B_{k}}$en alguna norma ; es decir,${\displaystyle B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}}$, dónde${\displaystyle V}$es una matriz definida positiva que define la norma. Un valor inicial aproximado${\displaystyle B_{0}=\beta I}$suele ser suficiente para lograr una convergencia rápida, aunque no existe una estrategia general para elegir.${\displaystyle \beta }$. ^{[ 5 ]} Nótese que${\displaystyle B_{0}}$debe ser positivo-definido. Lo desconocido${\displaystyle x_{k}}$se actualiza aplicando el paso de Newton calculado utilizando la matriz hessiana 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 matriz hessiana 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 definida positiva y${\displaystyle \alpha _{k}}$se elige para satisfacer las condiciones de Wolfe, entonces${\displaystyle B_{k+1}}$También es definida positiva.

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 de Broyden simétrico de Powell (PSB) y el método de Greenstadt. ^{[ 2 ]} Estas actualizaciones recursivas de matrices de bajo rango también pueden representarse como una matriz inicial más una corrección de bajo rango. Esta es la representación cuasi-Newton compacta , que es particularmente efectiva para problemas con restricciones y/o de gran tamaño.

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

^{En 1985, en el artículo “Métodos cuasi-Newton regulares” [ 7 ]} , se intentó ofrecer una visión general de los diversos enfoques de los métodos cuasi-Newton. En este artículo, se desarrolló una clase integral de estos métodos, una representación de todas las fórmulas de rango 1 de la denominada clase simétrica y novelizada de Huang, que incluye métodos bien conocidos como los de Davidon-Fletcher-Powell (DFP), Broyden-Fletcher-Goldfarb-Shanno (BFGS) y métrica de variables autoescalables (SSVM). También se ofrecen sugerencias para optimizar aún más el comportamiento de la solución de los métodos cuasi-Newton. Se construyó la siguiente clase de fórmulas de actualización cuasi-Newton “regulares” (es decir, preferidas para su uso debido a propiedades especiales):

${\displaystyle H_{i+1}:=B(H_{i},p_{i},q_{i},\theta _{i},r_{i},\rho _{i})}$

con

${\displaystyle B(H,p,q,\theta ,r,\rho )=rH+{{\rho \sigma +r\tau \theta } \over \sigma ^{2}}pp^{T}+r{{(\theta -1)} \over \tau }Hqq^{T}H-{{r\theta } \over \sigma }(pq^{T}H+Hqp^{T});}$

${\displaystyle H\in \mathbb {R} ^{nxn}}$positivo definido;${\displaystyle p,q\in \mathbb {R} ^{n};\epsilon =p^{T}H^{-1}p;}$

${\displaystyle \sigma =p^{T}q;\tau =q^{T}Hq;\theta ,r,\rho \in \mathbb {R} ;r>0;\rho \sigma >0;}$

${\displaystyle \theta [\epsilon \tau -\sigma ^{2}]>-\sigma ^{2};r\tau [\rho \sigma +\theta (r\tau -\rho \sigma )]\geq 0}$.

Para una minimización de haz aproximada y suficientemente precisa, definida positiva${\displaystyle H_{0}\in \mathbb {R} ^{nxn}}$y arbitrario${\displaystyle x_{0}\in \mathbb {R} ^{n}}$, lo siguiente se aplica a estos métodos regulares, que se derivan de la fórmula anterior:

1) Los métodos son métodos cuasi-Newton.

2) Las matrices${\displaystyle H_{i}}$son definidas positivas para todas las iteraciones. Por lo tanto,

${\displaystyle f(x_{i+1})<f(x_{i})}$Se aplica a todas las iteraciones.

3) Para todas las iteraciones${\displaystyle i\geq 0}$, obtenemos soluciones al problema de minimización.

Para la minimización exacta del haz y las funciones objetivo cuadráticas, cada uno de estos métodos también finaliza en el punto mínimo tras un máximo de n iteraciones. En particular, los métodos cuasi-Newton regulares poseen las buenas propiedades tanto de la clase Greenstadt extendida como de la clase Huang extendida simétrica en lo que respecta a la convergencia y la estabilidad.

Se puede suponer que todos los métodos cuasi-Newton particularmente potentes son regulares.

Existen implementaciones de métodos cuasi-Newton en muchos lenguajes de programación.

Entre las implementaciones de código abierto más destacadas se incluyen:

• GNU Octave utiliza una forma de BFGS en su fsolvefuncionamiento, 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 de optimización de propósito general de R utiliza el método BFGSmethod="BFGS" mediante el uso de . ^{[ 8 ]}
• 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 . ^{[ 9 ]}

Entre las implementaciones propietarias más destacadas se incluyen:

• Mathematica incluye solucionadores cuasi-Newton. ^{[ 10 ]}
• La biblioteca NAG contiene varias rutinas ^{[ 11 ]} para minimizar o maximizar una función ^{[ 12 ]} 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 . ^{[ 13 ]} Muchos de los métodos restringidos de la caja de herramientas de optimización utilizan BFGS y la variante L-BFGS . ^{[ 14 ]}

• 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-Newton» . Optimización numérica . Nueva York: Springer. págs. 192–221 . ISBN  0-387-98793-2.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Sección 10.9. Métodos cuasi-Newton o de métrica variable en multidimensiones» . Numerical Recipes: The Art of Scientific Computing (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. págs. 84–106 . ISBN  0-333-32552-4.