El método de Newton en optimización.

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 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 dos veces diferenciable f para encontrar las raíces de la derivada (soluciones de f ′(x) = 0), también conocidos como puntos críticos de f. Estas soluciones pueden ser mínimos, máximos o puntos silla; ver sección "Varias variables" en Punto crítico (matemáticas) y también en la sección "Interpretación geométrica" en este articulo. 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 ú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 diferente f:R→ → R{displaystyle f:mathbb {R} to mathbb {R}, buscamos resolver el problema de optimización

minx▪ ▪ Rf()x).{displaystyle min _{xin mathbb {R}f(x). }

El método de Newton intenta resolver este problema construyendo una secuencia {}xk}{displaystyle {x_{k}}} de una suposición inicial (punto de inicio) x0▪ ▪ R{displaystyle x_{0}in mathbb {R} que converge hacia un minimizador xAlternativa Alternativa {displaystyle x_{*} de f{displaystyle f} usando una secuencia de aproximaciones de Taylor de segundo orden f{displaystyle f} alrededor de los iterates. La expansión de Taylor de segundo orden f alrededor xk{displaystyle x_{k} es

f()xk+t).. f()xk)+f.()xk)t+12f.()xk)t2.{displaystyle f(x_{k}+t)approx f(x_{k})+f'(x_{k})t+{frac {1}{2}f''(x_{k})t^{2}.}

El próximo itinerario xk+1{displaystyle x_{k+1}} se define para minimizar esta aproximación cuadrática en t{displaystyle t}, y configuración xk+1=xk+t{displaystyle x_{k+1}=x_{k}+t}. Si el segundo derivado es positivo, la aproximación cuadrática es una función convexa de t{displaystyle t}, y su mínimo se puede encontrar estableciendo el derivado a cero. Desde

0=ddt()f()xk)+f.()xk)t+12f.()xk)t2)=f.()xk)+f.()xk)t,{displaystyle displaystyle 0={frac {rm {}{fn} {fnMicrosoft} {fnMicrosoft}} {fnMicrosoft}}} {fn}}} {fn}}} {fn}}} {fn}}}} {fn}}} {fnf}}}}}} {fnfnfn}}}}}}}}}}}}} {\\\\\\\fn}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\\\\\\\\\\\\\\\\\\\\\\ {d}t}}left(f(x_{k})+f'(x_{k})t+{frac {1}{2}f'(x_{k})t^{2}right)=f'(x_{k})t,}

el mínimo se alcanza para

t=− − f.()xk)f.()xk).{displaystyle t=-{frac {f'(x_{k}{f'''(x_{k}}}}}

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

xk+1=xk+t=xk− − f.()xk)f.()xk).{displaystyle ¿Qué?

Interpretación geométrica

La interpretación geométrica del método de Newton es que en cada iteración, equivale a la fijación de una parabola al gráfico de f()x){displaystyle f(x)} en el valor de prueba xk{displaystyle x_{k}, teniendo la misma pendiente y curvatura que el gráfico en ese momento, y luego proceder al máximo o mínimo de esa parabola (en dimensiones superiores, esto también puede ser un punto de silla), ver abajo. Note que si f{displaystyle f} sucede que Ser una función cuadrática, entonces el extremum exacto se encuentra en un paso.

Dimensiones superiores

El esquema iterativo anterior puede generalizarse 1}" xmlns="http://www.w3.org/1998/Math/MathML">d■1{displaystyle d confiar1}1}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f3dc6d8c61675b7e83b9bba7a236569af521f6a" style="vertical-align: -0.338ex; width:5.477ex; height:2.176ex;"/> dimensiones reemplazando el derivado por el gradiente (los diferentes autores utilizan diferentes notaciones para el gradiente, incluyendo f.()x)=Silencio Silencio f()x)=gf()x)▪ ▪ Rd{displaystyle f'(x)=nabla f(x)=g_{f}(x)in mathbb {R} ^{d}), y el recíproco del segundo derivado con el inverso de la matriz hesiana (los diferentes autores utilizan diferentes notación para el Hessian, incluyendo f.()x)=Silencio Silencio 2f()x)=Hf()x)▪ ▪ Rd× × d{displaystyle f'''(x)=nabla ^{2}f(x)=H_{f}(x)in mathbb {R} ^{dtimes d}). Uno obtiene así el esquema iterativo

xk+1=xk− − [f.()xk)]− − 1f.()xk),k≥ ≥ 0.{displaystyle x_{k+1}=x_{k}-[f''(x_{k}]^{-1}f'(x_{k}),qquad kgeq 0.}

A menudo el método de Newton se modifica para incluir un pequeño tamaño de paso <math alttext="{displaystyle 00c)γ γ ≤ ≤ 1{displaystyle 0 realizadasgammaleq 1}<img alt="{displaystyle 0 en lugar de γ γ =1{displaystyle gamma =1}:

xk+1=xk− − γ γ [f.()xk)]− − 1f.()xk).{displaystyle x_{k+1}=x_{k}-gamma [f'''(x_{k}]^{-1}f'(x_{k}).}

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

Implementación de algoritmos básicos en Python

desde mecanografía importación Lista, Tuple, Callableimportación numposo como npdef newton()x: np.ndarray, f: Callable, gf: Callable, h: Callable, lr=0,01, lr_decr=0.999, maxiter=100, tol=0,001) - No. Tuple[np.ndarray, Lista[np.ndarray] int]: " Aplica el método de Newton para encontrar el mínimo de una función multidimensional, utilizando el criterio de actualización:  x_k+1 = x_k - lr * inverse(hf(x)) * gf(x), para la iteración k-th. Args: x (np.ndarray): Un array que representa el punto inicial donde comienza el algoritmo. f (Llamable): Función objetiva para minimizar. gf (Callable): Gradiente de la función objetiva. hf (llamable): Hessian de la función objetiva. lr (float, opcional): Tasa de aprendizaje inicial. Default es 0.01. lr_decr (float, opcional): Factor de declive para la tasa de aprendizaje. La culpa es de 0.999. maxiter (int, opcional): Número máximo de iteraciones. La culpa es de 100. tol (float, opcional): Tolerancia para la norma gradiente que determina la convergencia. Default es 0.001. Devoluciones: Tuple[np.ndarray, List[np.ndarray], int]: Un tuple con tres elementos: - El punto mínimo aproximado. - Una lista de puntos intermedios (arrayas) calculados durante la optimización. - El número de iteraciones realizadas. Ejemplo:  # Define una función cuadrática de 2 dimensiones: f(x, y) = x^2 + 2y^2 def objective_function(x): x[0] ** 2 + 2 * x[1] ** 2 # Define el gradiente de la función objetiva: f'(x, y) = [2x, 4y] def gradient_function(x): retorno np.array([2 * x[0], 4 * x[1]) # Define el hesiano de la función objetiva: f''(x, y) = [[2, 0], [0, 4] def hessian_function(x): ([2, 0], [0, 4]]) # Punto inicial para la optimización inicial_punto = np.array([3.0, 2.0]) # Apply the Newton's method for optimization resultado, intermedio_puntos, iteraciones = newton(initial_point, objective_function, gradient_function, hessian_function) " puntos = [x] Niebla = 0 gradiente = gf()x) hessian = h()x)  mientras Niebla c) maxiter y np.linalg.norma()gradiente) >= tol:  x = x - lr * np.#()np.linalg.inv()hessian), gradiente) # Multiplicación de matriz usando np.dot(m1, m2) lr *= lr_decr # Actualización de la tasa de aprendizaje: tk+1 = tk * ρ, con ρ siendo el factor de decaimiento. puntos.apéndice()x) Niebla += 1 gradiente = gf()x) hessian = h()x) Regreso x, puntos, Niebla

Convergencia

Si f es una fuerte función convexa con Lipschitz Hessian, entonces siempre que x0{displaystyle x_{0} es lo suficientemente cerca xAlternativa Alternativa =arg⁡ ⁡ minf()x){displaystyle x_{*}=arg min f(x)}, la secuencia x0,x1,x2,...... {displaystyle x_{0},x_{1},x_{2},dots } generado por el método de Newton convergerá al minimizador (necesariamente único) xAlternativa Alternativa {displaystyle x_{*} de f{displaystyle f} cuadráticamente rápido. Eso es,

.. xk+1− − xAlternativa Alternativa.. ≤ ≤ 12.. xk− − xAlternativa Alternativa.. 2,О О k≥ ≥ 0.{displaystyle "Perfecto" {fnMicroc {1}{2}fnx_{k}-x_{*}fnción}qquad forall kgeq 0.}

Calcular la dirección de Newton

Encontrar el inverso del hesiano en altas dimensiones para calcular la dirección de Newton h=− − ()f.()xk))− − 1f.()xk){displaystyle h=-(f''(x_{k})}{-1}f'(x_{k})} puede ser una operación costosa. En tales casos, en lugar de invertir directamente el Hessian, es mejor calcular el vector h{displaystyle h} como solución al sistema de ecuaciones lineales

[f.()xk)]h=− − f.()xk){displaystyle [f'''(x_{k}]h=-f'(x_{k}

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

Por otro lado, si se realiza una optimización limitada (por ejemplo, con multiplicadores de Lagrange), el problema puede convertirse en uno de los puntos de montura, en cuyo caso el Hessian será simétrico indefinido y la solución xk+1{displaystyle x_{k+1}} tendrá que hacerse con un método que funcionará para tales, como el LDL⊤ ⊤ {displaystyle LDL^{top } variante de la factorización Cholesky o el método conjugado residual.

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

Si el Hessian está cerca de una matriz no invertible, el Hessian invertido puede ser numéricamente inestable y la solución puede divergir. En este caso, se han intentado en el pasado ciertas soluciones de trabajo, que han variado el éxito con ciertos problemas. Uno puede, por ejemplo, modificar el Hessian añadiendo una matriz de corrección Bk{displaystyle B_{k} para hacer f.()xk)+Bk{displaystyle f'(x_{k})+B_{k} positivo definido. Un enfoque es diagonalizar el Hessian y elegir Bk{displaystyle B_{k} así f.()xk)+Bk{displaystyle f'(x_{k})+B_{k} tiene los mismos eigenvectores que el Hessian, pero con cada eigenvalue negativo reemplazado por 0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle epsilon }0}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;"/>.

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

Algunas cavernas

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

1. No funciona si el Hessian no es invertible. Esto está claro desde la definición misma del método de Newton, que requiere tomar el inverso del Hessian.
2. Puede no converger en absoluto, pero puede entrar en un ciclo con más de 1 punto. Vea la sección "Análisis de fallas" en el método de Newton.
3. Puede converger a un punto de sillín en vez de a un mínimo local, ver la sección "Igualidad 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 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" en este articulo. 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.