Métodos de segundo orden · Definición
Método de Newton en optimización
Antes de empezar necesitas conocer
Descenso de gradiente usa solo primeras derivadas y avanza con pasos fijos o ajustados. El método de Newton incorpora curvatura para elegir un paso más informado.
Definición
El método de Newton para optimización es un algoritmo iterativo que busca un punto crítico de una función diferenciable \(f:\mathbb{R}^n\to\mathbb{R}\) usando el gradiente \(\nabla f\) y la hessiana \(H_f\).
Si la hessiana \(H_f(x_k)\) es definida positiva, el paso de Newton es la solución del modelo cuadrático de segundo orden de \(f\) alrededor de \(x_k\). Cerca de un mínimo con hessiana invertible, la convergencia es cuadrática, lo que significa que el número de cifras correctas se duplica aproximadamente en cada iteración.
Considera \(f(x,y)=x^2+4y^2\) con \(x_0=(2,1)\). Su gradiente es \((2x,8y)\) y su hessiana es \(\mathrm{diag}(2,8)\), así que un solo paso lleva a \((0,0)\), el mínimo global.
Un error típico es calcular \(H_f^{-1}\nabla f\) como \(\nabla f\,/\,H_f\) elemento a elemento o olvidar el signo negativo. Además, aplicar el método sin verificar que la hessiana sea definida positiva puede dirigir la iteración hacia un máximo o un punto silla.
Para pensar
¿Por qué el paso de Newton no necesita un tamaño de paso fijo como el descenso de gradiente en el caso cuadrático?
Porque la hessiana escala cada componente por su curvatura, así que el paso ya tiene la longitud correcta y lleva al mínimo en una iteración.
Ejercicios 10
- ¿Cuál es la fórmula de iteración del método de Newton para minimizar \(f:\mathbb{R}^n\to\mathbb{R}\)?
- ¿Qué condición sobre la hessiana garantiza que el paso de Newton sea una dirección de descenso?
- Si la hessiana es la matriz identidad en todo punto, ¿a qué se reduce el paso de Newton?
- ¿Qué tipo de convergencia tiene el método de Newton cerca de un mínimo con hessiana invertible?
- ¿Qué objeto se debe calcular en cada iteración del método de Newton además del gradiente?
- Para \(f(x,y)=x^2+2y^2\) en \((1,1)\), calcula el paso de Newton \(p=-H_f^{-1}\nabla f\).
- Para \(f(x,y)=x^4+y^2\) en \((1,2)\), ¿cuál es el paso de Newton en la coordenada \(x\)?
- Para \(f(x)=e^x-2x\) en \(\mathbb{R}\), ¿cuál es \(x_1\) desde \(x_0=0\)?
- Para \(f(x,y)=x^2+xy+y^2-3x\), calcula el paso de Newton desde \((0,0)\) y verifica que el punto obtenido es el mínimo.
- Para \(f(x,y)=x^3-3x+y^2\), ¿qué ocurre si se aplica el paso de Newton desde \((0,1)\)? Usa la hessiana \(\mathrm{diag}(6x,2)\).
Referencias
- Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
- Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.