Descenso de gradiente · Definición
Búsqueda de línea
Después de elegir una dirección de descenso, falta decidir cuánto avanzar. Un paso mal calibrado puede hacer que el método sea muy lento o que la función deje de disminuir.
Definición
La búsqueda de línea es un procedimiento que elige el tamaño de paso \(\alpha\) a lo largo de una dirección de descenso \(p_k\) para reducir el valor de la función objetivo.
La condición de Armijo exige una reducción suficiente frente a \(f(x_k)\), con \(0<c_1<1\), de modo que el descenso sea proporcional al paso. El retroceso (backtracking) parte de un \(\alpha\) grande y lo multiplica por \(\rho\in(0,1)\) hasta cumplir la condición; como la dirección es de descenso, siempre existe un \(\alpha\) que la cumple.
Tomemos \(f(x)=x^2\), \(x_k=1\) y \(p_k=-2\), con \(c_1=0.5\). Con \(\alpha=1\) el nuevo punto es \(-1\), con \(f=1\), que no baja hasta la cota \(-1\). Con \(\alpha=\tfrac12\) el punto es \(0\), con \(f=0\) y cota \(0\), así que el retroceso acepta \(\alpha=\tfrac12\).
El error típico es exigir el mínimo exacto de \(f\) sobre la recta en cada iteración, lo que cuesta muchas evaluaciones sin mejorar mucho la convergencia. Otro fallo frecuente es usar una dirección que no sea de descenso, con \(\nabla f(x_k)^\top p_k\ge 0\), porque la reducción prometida deja de existir.
Para pensar
Si \(\nabla f(x_k)^\top p_k>0\), ¿puede cumplirse Armijo para algún \(\alpha\) suficientemente pequeño? Razona por qué.
No. Para \(\alpha\) pequeño, \(f(x_k+\alpha p_k)\approx f(x_k)+\alpha\nabla f(x_k)^\top p_k\), que supera la cota \(f(x_k)+c_1\alpha\nabla f(x_k)^\top p_k\) porque \(c_1<1\). Así el retroceso nunca termina.
Ejercicios 10
- ¿Qué exige la condición de Armijo sobre el paso \(\alpha\)?
- ¿Cómo se llama el método que reduce \(\alpha\) multiplicándolo por \(\rho\) hasta cumplir la condición?
- ¿Qué debe cumplir la dirección \(p_k\) para que la búsqueda de línea tenga sentido?
- ¿Qué ocurre si el paso \(\alpha\) es demasiado grande?
- ¿Qué parámetro controla la pendiente mínima exigida en la condición de Armijo?
- Con \(f(x)=x^2\), \(x_k=1\), \(p_k=-2\), \(c_1=0.5\) y \(\rho=0.5\), ¿qué paso acepta el retroceso si arranca en \(\alpha=1\)?
- Con \(f(x)=x^2\), \(x_k=1\), \(p_k=-2\) y \(\alpha=\tfrac12\), ¿cuál es \(x_{k+1}\)?
- Con \(\nabla f(x_k)^\top p_k=-4\), \(c_1=0.25\) y \(\alpha=2\), ¿cuánto vale \(c_1\alpha\nabla f(x_k)^\top p_k\)?
- Con \(f(x)=x^2\), \(x_k=2\), \(p_k=-4\), \(c_1=0.25\), \(\rho=0.5\) y arranque en \(\alpha=1\), ¿qué paso acepta el retroceso?
- ¿Cuál afirmación sobre la búsqueda de línea es falsa?
Después de esto
Referencias
- Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
- Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.