Método de Newton

Matemática · Lección 17

L3 From scratch Fase F1 Libro MML §7.1 Prereqs Descenso de gradiente · Hessiana y Taylor

Objetivo

Al terminar esta lección se puede:

  1. Definir el paso del método de Newton y demostrar que es el minimizador exacto del modelo cuadrático de Taylor.
  2. Demostrar que en una cuadrática converge en un solo paso desde cualquier arranque, sin que el número de condición intervenga.
  3. Demostrar que cerca del óptimo la convergencia es cuadrática: el número de dígitos correctos se duplica en cada paso.
  4. Explicar por qué el método falla cuando la hessiana no es definida positiva, y cómo lo arregla el Newton regularizado.

De dónde viene

  • Matemática 16: el descenso de gradiente y su tasa (\kappa-1)/(\kappa+1). Esta lección existe porque esa tasa es mala cuando \kappa es grande.
  • Matemática 14: el modelo cuadrático de Taylor (Definición 14.4) y la condición de segundo orden. El paso de Newton es «minimizar el modelo en lugar de la función».
  • Matemática 15: la convexidad estricta, que es lo que hace único al minimizador del modelo.
  • Matemática 12: el criterio espectral, que decide si el modelo tiene mínimo o no lo tiene.

Para qué sirve después

  • Matemática 18: las condiciones KKT se resuelven con una variante de Newton sobre el sistema que forman.
  • Estadística 8: la regresión logística se ajusta por Newton, donde el método tiene nombre propio —iteratively reweighted least squares— y la hessiana se conoce en forma cerrada.
  • Estadística 9 y 14: la inversa de la hessiana de la log-verosimilitud en el óptimo es la matriz de covarianza asintótica del estimador, así que Newton entrega de paso los errores estándar.

Notación

Símbolo Se lee Significado
H_k = H_f(x_k) hache sub ka La hessiana evaluada en el punto actual
m(h) eme de hache El modelo cuadrático de Taylor alrededor de x_k
e_k = x_k-x^\star error en el paso ka La distancia al minimizador
\mu mu El menor eigenvalor de la hessiana en el óptimo; también el regularizador
L ele La constante de Lipschitz de la hessiana
t te El factor de amortiguación, t\in(0,1]

1. Minimizar el modelo en vez de la función

Definición 17.1 (paso de Newton). Si H_k=H_f(x_k) es invertible, el método de Newton genera x_{k+1} = x_k - H_k^{-1}\,\nabla f(x_k).

El descenso de gradiente usa solo el término lineal del desarrollo de Taylor y compensa con un paso \eta elegido a mano. Newton usa además el término cuadrático, y entonces el paso ya no hace falta elegirlo: lo fija la propia hessiana.

Proposición 17.2 (Newton minimiza el modelo). Sea m(h)=f(x_k)+\nabla f(x_k)\cdot h+\tfrac12h^\top H_kh el modelo cuadrático de la Definición 14.4. Si H_k es definida positiva, m tiene un único minimizador, y es h^\star = -H_k^{-1}\nabla f(x_k), es decir, exactamente el paso de la Definición 17.1.

Demostración. La hessiana de m respecto a h es H_k en todo punto —el Ejercicio 2 de la lección 14—, y es definida positiva por hipótesis. Por la Proposición 15.4, m es convexa, y por ser H_k definida positiva lo es estrictamente, así que la Proposición 15.6 da a lo sumo un minimizador. Por la Proposición 14.7 ese minimizador ha de ser un punto crítico, y \nabla m(h) = \nabla f(x_k) + H_kh = 0 \quad\Longleftrightarrow\quad h = -H_k^{-1}\nabla f(x_k), donde la inversa existe porque los eigenvalores son positivos. Ese punto crítico existe y es único, luego es el minimizador. ∎

De la Proposición 17.2 salen las dos caras del método. La buena: si el modelo se parece a la función, el paso cae cerca del óptimo. La mala: si H_k no es definida positiva, el modelo no tiene mínimo y el paso resuelve un problema que no es el que se quería resolver.

Proposición 17.3 (una cuadrática se resuelve en un paso). Sea f(x)=\tfrac12x^\top Ax-b^\top x con A simétrica definida positiva y x^\star=A^{-1}b. Entonces, desde cualquier x_0, x_1 = x^\star.

Demostración. Aquí \nabla f(x)=Ax-b y H_f(x)=A en todo punto, de modo que x_1 = x_0 - A^{-1}(Ax_0-b) = x_0 - x_0 + A^{-1}b = A^{-1}b = x^\star. \;\;[\blacksquare]

Compárese con la Proposición 16.5: sobre el mismo problema, el descenso de gradiente necesita del orden de \kappa iteraciones y Newton necesita una, siempre. El número de condición desaparece porque H^{-1} deshace exactamente el estiramiento que \kappa mide.

Con \kappa=5000 el descenso necesita 77\,652 iteraciones para llegar a una tolerancia que Newton cruza en una. Del error de Newton solo se afirma que queda por debajo de 10^{-13}: es del tamaño del épsilon de máquina, y sus dígitos cambian de una versión de la biblioteca a otra, así que citarlos sería citar ruido.

2. Cerca del óptimo, los dígitos se duplican

Proposición 17.4 (convergencia cuadrática local). Sea x^\star un punto crítico con H_f(x^\star) definida positiva de menor eigenvalor \mu>0, y sea H_f Lipschitz de constante L en un entorno de x^\star. Entonces existen \delta>0 y C>0 tales que, si \|e_k\|<\delta, \|e_{k+1}\| \;\le\; C\,\|e_k\|^2, \qquad\text{con } C\approx\frac{L}{2\mu}.

Demostración. Restando x^\star en la Definición 17.1 y sacando H_k^{-1} factor común, e_{k+1} = e_k - H_k^{-1}\nabla f(x_k) = H_k^{-1}\big[H_ke_k-\nabla f(x_k)\big]. Como \nabla f(x^\star)=0, el teorema fundamental del cálculo aplicado a t\mapsto\nabla f(x^\star+te_k) da \nabla f(x_k) = \int_0^1 H_f(x^\star+te_k)\,e_k\,dt, de donde H_ke_k-\nabla f(x_k) = \int_0^1\big[H_f(x_k)-H_f(x^\star+te_k)\big]e_k\,dt. El punto x^\star+te_k dista de x_k exactamente (1-t)\|e_k\|, así que por la hipótesis de Lipschitz la norma del corchete no pasa de L(1-t)\|e_k\| y \big\|H_ke_k-\nabla f(x_k)\big\| \;\le\; \int_0^1 L(1-t)\|e_k\|^2\,dt = \frac{L}{2}\,\|e_k\|^2. Falta acotar H_k^{-1}. Por la Proposición 12.4, para una matriz simétrica definida positiva la norma de la inversa es el recíproco del menor eigenvalor; y como las segundas parciales son continuas, ese menor eigenvalor está cerca de \mu si x_k está cerca de x^\star: tomando \delta bastante pequeño se puede asegurar que pasa de \mu/2. Juntando las dos cotas, \|e_{k+1}\| \;\le\; \frac{1}{\mu/2}\cdot\frac{L}{2}\|e_k\|^2 = \frac{L}{\mu}\|e_k\|^2, que es la forma anunciada con C=L/\mu; cuando x_k está tan cerca que H_k es prácticamente H_f(x^\star), la constante baja hasta L/2\mu. ∎

Elevar al cuadrado el error significa duplicar los dígitos correctos en cada paso: de tres decimales a seis, y de seis a doce. Esa es la diferencia de fondo con el descenso de gradiente de la Proposición 16.5, que multiplica el error por un factor fijo y por tanto gana siempre el mismo número de dígitos por paso.

La columna de la derecha se queda entre 0{,}13 y 0{,}20 en lugar de crecer, que es lo que afirma la Proposición 17.4. La izquierda cuenta la historia: 3{,}5, luego 1{,}7, luego 0{,}55, y a partir de ahí 0{,}049, 3\cdot10^{-4}, 1{,}3\cdot10^{-8} y precisión de máquina. Los tres primeros pasos son lentos porque el arranque está lejos; los tres últimos son el régimen cuadrático.

3. Lejos del óptimo el método se pierde

La Proposición 17.2 pide que H_k sea definida positiva. Cuando no lo es, el modelo cuadrático no tiene mínimo y resolver \nabla m=0 localiza un máximo o una silla del modelo. El método sigue dando un paso, pero ese paso ya no significa lo que se quería.

Desde (0{,}9,\,0{,}9) —donde la hessiana sí es definida positiva— Newton encuentra el mínimo. Desde los otros dos arranques termina en la silla, con f=0 en lugar de -2, y desde el tercero además sube en algún paso. El método converge, pero a un punto crítico que no es un mínimo: anular el gradiente es lo único que Newton persigue de verdad.

Definición 17.5 (Newton regularizado y amortiguado). Con \mu\ge0 el menor valor que hace H_k+\mu I definida positiva y t\in(0,1] un factor de amortiguación, x_{k+1} = x_k - t\,\big(H_k+\mu I\big)^{-1}\nabla f(x_k).

Los dos ingredientes arreglan cosas distintas. El regularizador \mu garantiza, por el criterio espectral de la Proposición 12.4, que la matriz sea definida positiva y que por tanto la Proposición 17.2 vuelva a aplicarse: el paso apunta al mínimo de un modelo que sí lo tiene. La amortiguación t se recorta a la mitad hasta que la función baje de verdad, lo que la Proposición 16.2 garantiza que ocurre con t suficientemente pequeño. Con \mu=0 y t=1 se recupera la Definición 17.1.

Los tres arranques que antes se repartían entre la silla y el mínimo ahora llegan los tres a un mínimo con f=-2. El precio es que cerca del óptimo, donde \mu=0 y t=1, el método vuelve a ser Newton puro y conserva la convergencia cuadrática; lejos, se comporta como un descenso con paso corto.

Ejercicios

Ejercicio 1 — El mismo paso, dos problemas distintos

Newton para hallar raíces resuelve f(x)=0 con x_{k+1}=x_k-f(x_k)/f'(x_k); Newton para optimizar resuelve f'(x)=0. Comprobar que el segundo es el primero aplicado a la derivada, y que los dos duplican dígitos.

Ejercicio 2 — Cuándo conviene cada método

Newton necesita muchísimos menos pasos, pero cada paso resuelve un sistema n\times n: del orden de n^3/3 operaciones, contra las 2n^2 de un producto matriz-vector. Encontrar dónde está el cruce.

En los cuatro casos medidos gana Newton. El cruce está en n=6\cdot(\text{pasos del descenso}): con \kappa=10 hace falta n por encima de unos 650 para que convenga el descenso, y con \kappa=1000 habría que llegar a n\approx68\,000. Por eso en dimensión moderada y problemas mal condicionados Newton es la opción, y en dimensión muy alta —donde ni la hessiana cabe en memoria— no lo es.

Reto

En proyectos/notebooks/F1-retos.ipynb, sección Mat 17:

  1. Implementar newton(f, grad, hess, x0) con regularización y amortiguación como en la Definición 17.5, registrando en cada paso \mu, t y el menor eigenvalor. Correrlo sobre x^4-4xy+y^4 desde una rejilla de arranques y dibujar de qué color es la cuenca de cada mínimo.
  2. Reproducir la tabla de la Proposición 17.4 con una función de tres variables y verificar que \|e_{k+1}\|/\|e_k\|^2 se estabiliza en un número cercano a L/2\mu, estimando L por diferencias de hessianas.
  3. Implementar Newton con hessiana aproximada por diferencias finitas del gradiente y medir cuántos dígitos se pierden frente a la hessiana exacta. Anotar en 50-Errores/ a partir de qué paso de diferenciación la convergencia cuadrática se degrada a lineal.

Del libro

Mathematics for Machine Learning trata la optimización continua en §7.1 Optimization Using Gradient Descent, donde presenta el descenso de gradiente y menciona los métodos que usan información de segundo orden. El libro tiene copyright y no es descargable desde el entorno en que se escribió esta página, así que se cita número y título y no se le atribuye ninguna frase.

Preguntas para leer §7.1 con lápiz:

  1. La sección trata el descenso de gradiente con paso fijo, cuya tasa depende del número de condición. Con la Proposición 17.3, ¿por qué multiplicar por H^{-1} elimina esa dependencia, y qué relación tiene eso con reescalar las coordenadas para que las curvas de nivel sean circunferencias?
  2. Los métodos cuasi-Newton —BFGS y L-BFGS— aproximan H^{-1} sin calcularla. Con el Ejercicio 2, ¿por qué esa aproximación es interesante justo en el régimen donde Newton pierde, y qué coste por iteración habría que conseguir para ganarle al descenso?
  3. Con la Proposición 17.2, ¿qué le pasa al paso de Newton si la hessiana es definida positiva pero está mal condicionada? Distinguir entre que el paso apunte mal y que su cálculo pierda precisión.

Para el Cerebro

Nota nueva en 10-Conceptos/metodo-de-newton.md, enlazada a [[descenso-de-gradiente]], [[hessiana]] y [[convexidad]]. Conviene rehacer a mano la Proposición 17.2: el paso de Newton no se postula, se deduce de minimizar el modelo cuadrático, y ese único argumento explica a la vez por qué funciona cerca del óptimo y por qué falla lejos.

¿Cuál es el paso de Newton?::x_{k+1} = x_k − H_k⁻¹∇f(x_k)
¿De dónde sale ese paso?::De minimizar el modelo cuadrático de Taylor: ∇m(h) = ∇f + Hh = 0
¿Qué hipótesis necesita?::Que la hessiana sea definida positiva; si no, el modelo no tiene mínimo
¿Cuántos pasos necesita en una cuadrática?::Uno, desde cualquier arranque y sea cual sea κ
¿Por qué desaparece el número de condición?::Porque H⁻¹ deshace exactamente el estiramiento que κ mide
¿Qué es la convergencia cuadrática?::‖e_{k+1}‖ ≤ C‖e_k‖²: el número de dígitos correctos se duplica cada paso
¿Cuánto vale esa constante C?::Del orden de L/2μ, con L el Lipschitz de la hessiana y μ su menor eigenvalor en el óptimo
¿Qué persigue Newton en realidad?::Anular el gradiente; puede converger a una silla y no al mínimo
¿Qué hace el regularizador μ?::Sumar μI para que H+μI sea definida positiva y el modelo vuelva a tener mínimo
¿Qué hace la amortiguación t?::Recortar el paso hasta que la función baje de verdad
¿Cuándo conviene Newton y cuándo el descenso?::Newton en dimensión moderada o mal condicionado; el descenso cuando n supera unas 6 veces los pasos que necesitaría

Fuentes

Lo que esta página demuestra sola. Las Proposiciones 17.2, 17.3 y 17.4 se demuestran aquí a partir del modelo cuadrático de la lección 14, de la convexidad estricta de la 15 y del criterio espectral de la 12. Se comprueban además numéricamente: que un paso de Newton resuelve una cuadrática con error por debajo de 10^{-13} para \kappa igual a 2, 50 y 5000, frente a las 22, 648 y 77 652 iteraciones que necesita el descenso de gradiente para una tolerancia fija de 10^{-10}; la convergencia cuadrática con la razón \|e_k\|/\|e_{k-1}\|^2 estable entre 0{,}13 y 0{,}20 mientras el error cae de 3{,}5 a precisión de máquina en seis pasos; que desde dos de tres arranques Newton puro termina en la silla de x^4-4xy+y^4 con f=0 en lugar de -2, y que desde uno de ellos sube en algún paso; que la versión regularizada y amortiguada lleva los tres arranques a un mínimo verdadero; la equivalencia entre Newton para raíces y Newton para optimizar; y el cruce de coste total en n=6\cdot(\text{pasos del descenso}). Los dos visuales se contrastaron antes de publicarse contra las fórmulas en todo el rango de sus controles.

Lo que se usa de otras lecciones sin repetir. El modelo cuadrático y que su hessiana es constante son la Definición 14.4 y el Ejercicio 2 de la lección 14. La condición necesaria de primer orden es la Proposición 14.7. Que hessiana definida positiva implica convexidad estricta y minimizador único son las Proposiciones 15.4 y 15.6. Que la norma de la inversa de una simétrica definida positiva es el recíproco de su menor eigenvalor sale de la Proposición 12.4. El paso óptimo 2/(\lambda_1+\lambda_n) y la tasa (\kappa-1)/(\kappa+1) con que se compara son la Proposición 16.5, y que un paso corto siempre baja es la 16.2.

Lo que se enuncia sin demostrar. El teorema fundamental del cálculo en forma vectorial, usado en la Proposición 17.4 para escribir \nabla f(x_k) como integral de hessianas. En la misma demostración se usa la desigualdad de la norma de una integral sin justificarla, y se afirma que el menor eigenvalor de H_k pasa de \mu/2 cerca de x^\star apelando a la continuidad sin precisar el \delta. La convergencia global del Newton regularizado de la Definición 17.5 se comprueba en tres arranques pero no se demuestra.

Lo que viene de los libros.

  • Mathematics for Machine Learning (Deisenroth, Faisal & Ong, Cambridge University Press, 2020), §7.1 Optimization Using Gradient Descent — citada por número y título, sin transcribir texto.

Lo que es mío, no del libro. Presentar el paso de Newton como consecuencia de la Proposición 17.2 en lugar de como una fórmula dada, para que el fallo de la sección 3 se lea como la misma proposición aplicada donde su hipótesis no vale. La celda que mide el fallo con tres arranques del ejemplo de la lección 14, incluida la comprobación de que el método sube en algún paso. Y el cálculo del cruce de coste dentro de la propia celda, en lugar de afirmarlo: la regla n=6\cdot\text{pasos} sale de igualar n^3/3 con 2n^2 por iteración.

Índices verificados el 12-09-2026 contra el índice publicado del PDF oficial.

→ Siguiente: Multiplicadores de Lagrange y condiciones KKT