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 ]}

An attempt to provide an overview of the various approaches to quasi-Newton methods was made in 1985 in the article “Regular Quasi-Newton Methods.”^[7] Here, a comprehensive class of these methods was developed, a representation of all rank 1 formulas of the so-called symmetric, novelized Huang class, which includes well-known methods such as the Davidon-Fletcher-Powell (DFP), Broyden-Fletcher-Goldfarb-Shanno (BFGS), and Self-Scaling-Variable-Metric (SSVM) methods. Suggestions for further optimization of the solution behavior of quasi-Newton methods are also given. The following class of “regular” (i.e., preferred for use due to special properties) Quasi-Newton update formulas was constructed:

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

with

${\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}}$ positive definite; ${\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}$.

For approximate, sufficiently accurate beam minimization, positive definite ${\displaystyle H_{0}\in \mathbb {R} ^{nxn}}$ and arbitrary ${\displaystyle x_{0}\in \mathbb {R} ^{n}}$, the following applies to these regular methods, which are derived from the above formula:

1) The methods are quasi-Newton methods.

2) The matrices ${\displaystyle H_{i}}$ are positive definite for all iterations. Thus,

${\displaystyle f(x_{i+1})<f(x_{i})}$ applies for all iterations.

3) For all iterations ${\displaystyle i\geq 0}$, we obtain solutions to the minimization problem.

For exact beam minimization and quadratic objective functions, each of these methods also terminates at the minimum point after at most n iteration steps. In particular, the regular quasi-Newton methods have the good properties of both the extended Greenstadt class and the symmetric, extended Huang class with regard to convergence and stability.

It can be assumed that all particularly powerful quasi-Newton methods are regular.

Implementations of quasi-Newton methods are available in many programming languages.

Notable open source implementations include:

• GNU Octave uses a form of BFGS in its fsolve function, with trust region extensions.
• GNU Scientific Library implements the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm.
• ALGLIB implements (L)BFGS in C++ and C#
• R's optim general-purpose optimizer routine uses the BFGS method by using method="BFGS".^[8]
• Scipy.optimize has fmin_bfgs. In the SciPy extension to Python, the scipy.optimize.minimize function includes, among other methods, a BFGS implementation.^[9]

Notable proprietary implementations include:

• Mathematica includes quasi-Newton solvers.^[10]
• The NAG Library contains several routines^[11] for minimizing or maximizing a function^[12] which use quasi-Newton algorithms.
• 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.