El método de Newton en optimización.

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

Una comparación del 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 encontrar las raíces de una función derivable F , que son soluciones de la ecuación F ( x ) = 0 . Como tal, el método de Newton se puede aplicar a la derivada f ′ de una función f dos veces diferenciable para encontrar las raíces de la derivada (soluciones de f ′( x ) = 0 ), también conocidas como puntos críticos de f . Estas soluciones pueden ser mínimos, máximos o puntos silla; ver el apartado "Varias variables" en Punto crítico (matemáticas) y también el apartado "Interpretación geométrica" ​​de este artículo. Esto es relevante en la optimización , que tiene como objetivo encontrar mínimos (globales) de la función f .

El método de Newton

El problema central de la optimización es la minimización de funciones. Consideremos primero el caso de funciones univariadas, es decir, funciones de una única variable real. Más adelante consideraremos el caso multivariado, más general y más útil en la 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 suposición inicial (punto de partida) que converge hacia un minimizador de mediante el uso de una secuencia de aproximaciones de Taylor de segundo orden alrededor de las iteraciones. La expansión de Taylor de segundo orden de f alrededor 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 para minimizar esta aproximación cuadrática en y configuración . 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. Desde ${\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,}$

el mínimo se alcanza 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 a la gráfica de en el valor de prueba , teniendo la misma pendiente y curvatura que la gráfica en ese punto, y luego procediendo al máximo o al mínimo. de esa parábola (en dimensiones superiores, esto también puede ser un punto de silla ), ver más abajo. 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 con el gradiente (diferentes autores usan notación diferente para el gradiente, incluido ), y el recíproco de la segunda derivada con la inversa de la matriz de Hesse (diferentes autores usan notación diferente para el hessiano, incluido ). Se obtiene así 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 a menudo se hace 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 a menudo se denomina método de Newton relajado o amortiguado.

Convergencia

Si f es una función fuertemente convexa con Lipschitz Hessian, entonces, siempre que esté lo suficientemente cerca de , 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.}$

Calcular la dirección de Newton

Encontrar la inversa del hessiano en dimensiones altas para calcular la dirección de Newton puede ser una operación costosa. En tales casos, en lugar de invertir directamente el hessiano, 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 varias 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, suele ser un indicador útil de que algo salió mal; por ejemplo, si se aborda 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 otro lado, si se realiza una optimización restringida (por ejemplo, con multiplicadores de Lagrange ), el problema puede convertirse en uno de búsqueda del punto de silla, en cuyo caso el hessiano será simétrico indefinido y la solución de deberá realizarse con un método que funcionará para ello, como la variante de factorización de Cholesky o el método residual conjugado . ${\displaystyle x_{k+1}}$ ${\displaystyle LDL^{\top }}$

También existen varios métodos cuasi-Newton , en los que se construye una aproximación del hessiano (o su inversa 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 en el pasado, que han tenido éxito variable con ciertos problemas. Se puede, por ejemplo, modificar el hessiano añadiendo una matriz de corrección para que sea positivo y definido. Un enfoque es diagonalizar el hessiano y elegirlo para que tenga los mismos vectores propios que el hessiano, 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 Hessian grande y pequeño, las iteraciones se comportarán como un descenso de gradiente con tamaño de paso . Esto da como resultado una convergencia más lenta pero más confiable cuando 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 el hessiano no es invertible. Esto se desprende claramente de la definición misma del método de Newton, que requiere tomar la inversa del hessiano.
2. Puede que no converja en absoluto, pero puede entrar en un ciclo que tenga más de 1 punto. Ver 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" ​​de este artículo.

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

Por ejemplo, generalmente se requiere que la función de costos sea (fuertemente) convexa y que la hessiana esté globalmente acotada o sea continua de Lipschitz; por ejemplo, esto se menciona en la sección "Convergencia" de este artículo. Si uno mira los artículos de Levenberg y Marquardt en la referencia del algoritmo de 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 sólo 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íneas de retroceso para el descenso de gradiente, que tiene una buena garantía teórica bajo supuestos más generales y puede implementarse y funciona bien en problemas prácticos a gran escala, como las redes neuronales profundas.

Ver también

• Método 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] : Sección 6.2}

Notas

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

Referencias

• Avriel, Mardoqueo (2003). Programación no lineal: análisis y métodos . Publicación de Dover. 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.
• Dados, Geof H.; Hoeting, Jennifer A. (2013). Estadística Computacional . Hoboken, Nueva Jersey: John Wiley & Sons. págs. 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, Dmitri; Mishchenko, Konstantin; Richtárik, Peter (2019). "Métodos estocásticos de Newton 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.