En cálculo , el método de Newton es un método iterativo para encontrar las raíces de una función diferenciable 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 conocido como el punto crítico (matemáticas) s de F. Estas soluciones pueden ser mínimos, máximos o puntos silla, consulte la sección "Varias variables" en Punto crítico (matemáticas) y también la sección "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 .
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 sola 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 solucionar el problema de optimización
El método de Newton intenta resolver este problema construyendo una secuencia desde 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 de alrededor de las iteraciones. La expansión de Taylor de segundo orden de f alrededor es
La siguiente iteración se define para minimizar esta aproximación cuadrática en y ambientació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
el mínimo se alcanza para
Poniendo todo junto, el método de Newton realiza la iteración
Interpretación geométrica
La interpretación geométrica del método de Newton es que en cada iteración, equivale al ajuste de una parábola a la gráfica de al valor de prueba , teniendo la misma pendiente y curvatura que la gráfica en ese punto, y luego procediendo al máximo o mínimo de esa parábola (en dimensiones más altas, esto también puede ser un punto de silla ), ver más abajo. Tenga en cuenta que siresulta ser una función cuadrática, entonces el extremo exacto se encuentra en un paso. Aplicando esta simple observación a funciones de costo cuadráticas simples, obtenemos un comportamiento diferente del método de Newton:
- Para la función , que tiene un mínimo global en 0, el método de Newton convergerá a 0 después de 1 paso.
- Para la función , que tiene un máximo global en 0, el método de Newton convergerá a 0 después de 1 paso.
Mayores dimensiones
El esquema iterativo anterior se puede generalizar paradimensiones reemplazando la derivada con el gradiente (diferentes autores usan una notación diferente para el gradiente, incluyendo), y el recíproco de la segunda derivada con la inversa de la matriz hessiana (diferentes autores usan notación diferente para la hessiana, incluyendo). Se obtiene así el esquema iterativo
A menudo, el método de Newton se modifica para incluir un tamaño de paso pequeño en vez de :
Esto se hace a menudo para asegurar que las condiciones de Wolfe , o la condición de Armijo mucho más simple y eficiente , se satisfagan 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 generado por el método de Newton convergerá al minimizador (necesariamente único) de cuadráticamente rápido. [1] Es decir,
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 arpillera, es mejor calcular el vectorcomo la solución al sistema de ecuaciones lineales
que puede resolverse mediante varias factorizaciones o aproximadamente (pero con gran precisión) mediante 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 sies 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 yno es positivo definido, entonces las iteraciones están convergiendo a un punto de silla y no a un mínimo.
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 silla, en cuyo caso el hessiano será simétrico indefinido y la solución de tendrá que hacerse con un método que funcione para tal, como el variante de factorización de Cholesky o el método residual conjugado .
También existen varios métodos cuasi-Newton , donde una aproximación para el hessiano (o su inverso directamente) se construye a partir de cambios en el gradiente.
Si el hessiano está cerca de una matriz no invertible , el hessiano invertido puede ser numéricamente inestable y la solución puede divergir. En este caso, en el pasado se han probado algunas soluciones alternativas, que han tenido un éxito variable con ciertos problemas. Se puede, por ejemplo, modificar el arpillera agregando una matriz de corrección para hacer positivo definitivo. Un enfoque es diagonalizar el arpillera y elegir así que eso tiene los mismos autovectores que el hessiano, pero con cada autovalor negativo reemplazado por .
Un enfoque explotado en el algoritmo de Levenberg-Marquardt (que usa 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 grandey pequeño Hessian, 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 Hessian no proporciona información útil.
Algunas advertencias
El método de Newton, en su versión original, tiene varias salvedades:
Primero: no funciona si el Hessian no es invertible. Esto se desprende de la definición misma del método de Newton, que requiere tomar la inversa del hessiano.
Segundo: Puede que no converja en absoluto, pero puede entrar en un ciclo que tenga más de 1 punto. Consulte la sección "Análisis de fallos" en el método de Newton .
Tercero: 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 mencionados anteriormente, también tienen salvedades:
Por ejemplo, generalmente se requiere que la función de costo sea (fuertemente) convexa y el hessiano sea globalmente acotado o Lipschitz continuo, 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 de Levenberg-Marquardt , que son las fuentes originales del método mencionado, se puede ver que básicamente no hay un 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ínea Backtracking para 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.
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 de Nelder-Mead
Notas
- ^ Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Nueva York: Springer. pag. 44. ISBN 0387303030.
Referencias
- Avriel, Mordecai (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.
- Givens, 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, Dmitry; Mishchenko, Konstantin; Richtárik, Peter (2019). "Métodos estocásticos de Newton y Newton cúbico con tasas cuadráticas lineales locales simples". arXiv : 1912.01597 [ cs.LG ].
enlaces externos
- Korenblum, Daniel (29 de agosto de 2015). "Visualización de Newton-Raphson (1D)" . Calcetines azules . ffe9653768cb80dfc0da.