El método de Newton en optimización

Método para encontrar puntos estacionarios de una función

Comparación del método de descenso de gradiente (verde) y el método de Newton (rojo) para minimizar una función (con pasos pequeños). El método de Newton utiliza información de curvatura (es decir, la segunda derivada) para tomar una ruta más directa.

En cálculo , el método de Newton (también llamado Newton–Raphson ) es un método iterativo para hallar las raíces de una función diferenciable , que son soluciones de la ecuación . Sin embargo, para optimizar una función dos veces diferenciable , nuestro objetivo es hallar las raíces de . Por lo tanto, podemos utilizar el método de Newton en su derivada para hallar soluciones de , también conocidas como puntos críticos de . Estas soluciones pueden ser mínimos, máximos o puntos de silla; consulte la sección "Varias variables" en Punto crítico (matemáticas) y también la sección "Interpretación geométrica" ​​en este artículo. Esto es relevante en la optimización , que tiene como objetivo hallar mínimos (globales) de la función . ${\displaystyle f}$ ${\displaystyle f(x)=0}$ ${\displaystyle f}$ ${\displaystyle f'}$ ${\displaystyle f'}$ ${\displaystyle f'(x)=0}$ ${\displaystyle f}$ ${\displaystyle f}$

El método de Newton

El problema central de la optimización es la minimización de funciones. Consideremos primero el caso de las funciones univariadas, es decir, funciones de una única variable real. Más adelante consideraremos el caso multivariado, más general y de mayor utilidad práctica.

Dada una función dos veces diferenciable , buscamos resolver el problema de optimización ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$

${\displaystyle \min _{x\in \mathbb {R} }f(x).}$

El método de Newton intenta resolver este problema construyendo una secuencia a partir de una estimación inicial (punto de partida) que converge hacia un minimizador de mediante el uso de una secuencia de aproximaciones de Taylor de segundo orden de alrededor de las iteraciones. La expansión de Taylor de segundo orden de f alrededor de es ${\displaystyle \{x_{k}\}}$ ${\displaystyle x_{0}\in \mathbb {R} }$ ${\displaystyle x_{*}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle x_{k}}$

${\displaystyle f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.}$

La siguiente iteración se define de modo que minimice esta aproximación cuadrática en , y estableciendo . Si la segunda derivada es positiva, la aproximación cuadrática es una función convexa de , y su mínimo se puede encontrar estableciendo la derivada en cero. Dado que ${\displaystyle x_{k+1}}$ ${\displaystyle t}$ ${\displaystyle x_{k+1}=x_{k}+t}$ ${\displaystyle t}$

${\displaystyle \displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}$

Se alcanza el mínimo para

${\displaystyle t=-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

Juntando todo, el método de Newton realiza la iteración.

${\displaystyle x_{k+1}=x_{k}+t=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

Interpretación geométrica

La interpretación geométrica del método de Newton es que en cada iteración, equivale a ajustar una parábola al gráfico de en el valor de prueba , que tiene la misma pendiente y curvatura que el gráfico en ese punto, y luego proceder al máximo o mínimo de esa parábola (en dimensiones superiores, esto también puede ser un punto de silla ), vea a continuación. Tenga en cuenta que si resulta ser una función cuadrática, entonces el extremo exacto se encuentra en un solo paso. ${\displaystyle f(x)}$ ${\displaystyle x_{k}}$ ${\displaystyle f}$

Dimensiones superiores

El esquema iterativo anterior se puede generalizar a dimensiones reemplazando la derivada por el gradiente (diferentes autores utilizan notaciones diferentes para el gradiente, incluyendo ), y el recíproco de la segunda derivada por la inversa de la matriz hessiana (diferentes autores utilizan notaciones diferentes para la hessiana, incluyendo ). De este modo se obtiene el esquema iterativo ${\displaystyle d>1}$ ${\displaystyle f'(x)=\nabla f(x)=g_{f}(x)\in \mathbb {R} ^{d}}$ ${\displaystyle f''(x)=\nabla ^{2}f(x)=H_{f}(x)\in \mathbb {R} ^{d\times d}}$

${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k}),\qquad k\geq 0.}$

A menudo, el método de Newton se modifica para incluir un tamaño de paso pequeño en lugar de : ${\displaystyle 0<\gamma \leq 1}$ ${\displaystyle \gamma =1}$

${\displaystyle x_{k+1}=x_{k}-\gamma [f''(x_{k})]^{-1}f'(x_{k}).}$

Esto se hace a menudo para garantizar que las condiciones de Wolfe , o la condición de Armijo , mucho más simple y eficiente , se cumplan en cada paso del método. Para tamaños de paso distintos de 1, el método se conoce a menudo como método de Newton relajado o amortiguado.

Convergencia

Si f es una función fuertemente convexa con hessiano de Lipschitz, entonces, siempre que sea lo suficientemente cercano a , la secuencia generada por el método de Newton convergerá al minimizador (necesariamente único) de cuadráticamente rápido. ^[1] Es decir, ${\displaystyle x_{0}}$ ${\displaystyle x_{*}=\arg \min f(x)}$ ${\displaystyle x_{0},x_{1},x_{2},\dots }$ ${\displaystyle x_{*}}$ ${\displaystyle f}$

${\displaystyle \|x_{k+1}-x_{*}\|\leq {\frac {1}{2}}\|x_{k}-x_{*}\|^{2},\qquad \forall k\geq 0.}$

Calculando la dirección de Newton

Encontrar la inversa de la hessiana en grandes dimensiones para calcular la dirección de Newton puede ser una operación costosa. En tales casos, en lugar de invertir directamente la hessiana, es mejor calcular el vector como solución del sistema de ecuaciones lineales . ${\displaystyle h=-(f''(x_{k}))^{-1}f'(x_{k})}$ ${\displaystyle h}$

${\displaystyle [f''(x_{k})]h=-f'(x_{k})}$

que puede resolverse mediante diversas factorizaciones o aproximadamente (pero con gran precisión) utilizando métodos iterativos . Muchos de estos métodos solo son aplicables a ciertos tipos de ecuaciones, por ejemplo, la factorización de Cholesky y el gradiente conjugado solo funcionarán si es una matriz definida positiva. Si bien esto puede parecer una limitación, a menudo es un indicador útil de que algo salió mal; por ejemplo, si se está abordando un problema de minimización y no es definido positivo, entonces las iteraciones convergen a un punto de silla y no a un mínimo. ${\displaystyle f''(x_{k})}$ ${\displaystyle f''(x_{k})}$

Por otra parte, si se realiza una optimización restringida (por ejemplo, con multiplicadores de Lagrange ), el problema puede convertirse en uno de búsqueda de puntos de silla, en cuyo caso el hessiano será simétrico indefinido y la solución de deberá realizarse con un método que funcione para tal fin, como la variante de la factorización de Cholesky o el método de residuos conjugados . ${\displaystyle x_{k+1}}$ ${\displaystyle LDL^{\top }}$

También existen varios métodos cuasi-Newton , donde se construye una aproximación para el hessiano (o su inverso directamente) a partir de cambios en el gradiente.

Si la hessiana está cerca de una matriz no invertible , la hessiana invertida puede ser numéricamente inestable y la solución puede divergir. En este caso, se han probado ciertas soluciones alternativas en el pasado, que han tenido éxito variable con ciertos problemas. Por ejemplo, se puede modificar la hessiana agregando una matriz de corrección para hacer que sea definida positiva. Un enfoque es diagonalizar la hessiana y elegir de modo que tenga los mismos vectores propios que la hessiana, pero con cada valor propio negativo reemplazado por . ${\displaystyle B_{k}}$ ${\displaystyle f''(x_{k})+B_{k}}$ ${\displaystyle B_{k}}$ ${\displaystyle f''(x_{k})+B_{k}}$ ${\displaystyle \epsilon >0}$

Un enfoque explotado en el algoritmo de Levenberg-Marquardt (que utiliza un hessiano aproximado) es agregar una matriz de identidad escalada al hessiano, , con la escala ajustada en cada iteración según sea necesario. Para hessianos grandes y pequeños, las iteraciones se comportarán como un descenso de gradiente con un tamaño de paso . Esto da como resultado una convergencia más lenta pero más confiable donde el hessiano no proporciona información útil. ${\displaystyle \mu I}$ ${\displaystyle \mu }$ ${\displaystyle 1/\mu }$

Algunas advertencias

El método de Newton, en su versión original, tiene varias salvedades:

1. No funciona si la hessiana no es invertible. Esto se desprende claramente de la propia definición del método de Newton, que exige tomar la inversa de la hessiana.
2. Puede que no converja en absoluto, pero puede entrar en un ciclo con más de un punto. Véase el método de Newton § Análisis de fallos .
3. Puede converger a un punto de silla en lugar de a un mínimo local, consulte la sección "Interpretación geométrica" ​​en este artículo.

Las modificaciones populares del método de Newton, como los métodos cuasi-Newton o el algoritmo de Levenberg-Marquardt mencionado anteriormente, también tienen salvedades:

Por ejemplo, normalmente se requiere que la función de costo sea (fuertemente) convexa y que la hessiana esté globalmente acotada o sea continua en el sentido de Lipschitz; por ejemplo, esto se menciona en la sección "Convergencia" de este artículo. Si se observan los artículos de Levenberg y Marquardt en la referencia del algoritmo Levenberg-Marquardt , que son las fuentes originales del método mencionado, se puede ver que básicamente no hay ningún análisis teórico en el artículo de Levenberg, mientras que el artículo de Marquardt solo analiza una situación local y no prueba un resultado de convergencia global. Se puede comparar con el método de búsqueda de línea de retroceso para el descenso de gradiente, que tiene una buena garantía teórica bajo supuestos más generales, y se puede implementar y funciona bien en problemas prácticos a gran escala como las redes neuronales profundas.

Véase también

• Método de cuasi-Newton
• Descenso de gradiente
• Algoritmo de Gauss-Newton
• Algoritmo de Levenberg-Marquardt
• Región de confianza
• Mejoramiento
• Método Nelder-Mead
• Función autoconcordante : función para la cual el método de Newton tiene una tasa de convergencia global muy buena. ^{[2] : Sec.6.2}

Notas

1. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2.ª ed.). Nueva York: Springer. p. 44. ISBN 0387303030.
2. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .

Referencias

• Avriel, Mordecai (2003). Programación no lineal: análisis y métodos . Dover Publishing. ISBN 0-486-43227-0.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimización numérica: aspectos teóricos y prácticos . Universitext (Segunda edición revisada de la traducción de la edición francesa de 1997). Berlín: Springer-Verlag. doi :10.1007/978-3-540-35447-5. ISBN. 3-540-35445-X.Señor 2265882  .
• Fletcher, Roger (1987). Métodos prácticos de optimización (2.ª ed.). Nueva York: John Wiley & Sons . ISBN 978-0-471-91547-8.
• Givens, Geof H.; Hoeting, Jennifer A. (2013). Computational Statistics . Hoboken, Nueva Jersey: John Wiley & Sons. pp. 24–58. ISBN 978-0-470-53331-4.
• Nocedal, Jorge; Wright, Stephen J. (1999). Optimización numérica . Springer-Verlag. ISBN 0-387-98793-2.
• Kovalev, Dmitry; Mishchenko, Konstantin; Richtárik, Peter (2019). "Métodos Newton estocástico y Newton cúbico con tasas lineales-cuadráticas locales simples". arXiv : 1912.01597 [cs.LG].

Enlaces externos

• Korenblum, Daniel (29 de agosto de 2015). "Visualización de Newton-Raphson (1D)". Bloques . ffe9653768cb80dfc0da.