Descenso de gradiente · Definición

Condiciones de Wolfe

optimización continuadescenso de gradiente

Antes de empezar necesitas conocer

Al avanzar en una dirección de descenso, un paso muy pequeño apenas reduce la función y uno muy grande puede no reducirla. Hace falta un criterio que descarte ambos extremos.

Definición

Son dos desigualdades que un paso \(\alpha\) de búsqueda de línea debe cumplir para asegurar un decrecimiento suficiente de la función y que el paso no sea demasiado corto.

\[f(x_k+\alpha p_k)\le f(x_k)+c_1\alpha\nabla f(x_k)^\top p_k\]

Con \(0<c_1<c_2<1\), la condición de Armijo exige que \(f\) baje al menos una fracción de lo que predice la pendiente inicial, y la de curvatura exige que la pendiente en el nuevo punto sea al menos \(c_2\) veces la inicial. Si \(p_k\) es dirección de descenso, ambas pueden cumplirse a la vez para los pasos de un intervalo no vacío.

Tomemos \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\) y \(c_2=0.9\). Las dos condiciones dan el intervalo aceptable \([0.1,\,1.8]\): el paso \(\alpha=0.5\) lo cumple, \(\alpha=0.01\) solo cumple Armijo y \(\alpha=2\) no cumple Armijo.

Un error típico es verificar solo Armijo y aceptar pasos muy pequeños que apenas avanzan, lo que puede hacer que el método tarde mucho en converger. Otro es olvidar que \(\nabla f(x_k)^\top p_k\) es negativo en una dirección de descenso, y evaluar mal los signos.

Para pensar

¿Por qué la condición de curvatura sola no asegura que f baje?

Porque solo exige que la pendiente suba; un paso grande puede cumplirla y aumentar f. Armijo descarta ese caso.

Ejercicios 10

  1. ¿Qué condición exige que la función baje lo suficiente respecto a su valor inicial?
  2. ¿Qué condición de Wolfe impide que el paso sea demasiado corto?
  3. En las condiciones de Wolfe, ¿qué relación deben cumplir las constantes \(c_1\) y \(c_2\)?
  4. Si un paso \(\alpha\) cumple ambas condiciones de Wolfe, ¿qué se garantiza?
  5. ¿Cómo se llama la variante que acota en valor absoluto la pendiente en el nuevo punto?
  6. Sea \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\). ¿Cumple \(\alpha=0.5\) la condición de Armijo?
  7. Sea \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\), \(c_2=0.9\). ¿Qué condición falla con \(\alpha=2\)?
  8. Un paso \(\alpha\) demasiado corto apenas cambia el gradiente. ¿Qué condición de Wolfe lo descarta?
  9. Sea \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\), \(c_2=0.9\). ¿Qué ocurre con \(\alpha=0.01\)?
  10. Con \(c_2=0.9\), \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), ¿acepta la condición de Wolfe fuerte el paso \(\alpha=1.5\)?

Referencias

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.