Gradient descent · Definition

Wolfe conditions

continuous optimizationgradient descent

Before you start you need to know

When moving along a descent direction, a very small step barely reduces the function and a very large one may not reduce it at all. We need a criterion that rules out both extremes.

Definition

Two inequalities that a line-search step \(\alpha\) must satisfy to guarantee sufficient decrease of the function and that the step is not too short.

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

With \(0<c_1<c_2<1\), the Armijo condition requires \(f\) to decrease by at least a fraction of what the initial slope predicts, and the curvature condition requires the slope at the new point to be at least \(c_2\) times the initial slope. If \(p_k\) is a descent direction, both can hold at once for steps in a nonempty interval.

Take \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\), and \(c_2=0.9\). The two conditions give the acceptable interval \([0.1,\,1.8]\): the step \(\alpha=0.5\) satisfies both, \(\alpha=0.01\) satisfies only Armijo, and \(\alpha=2\) fails Armijo.

A typical mistake is checking only Armijo and accepting tiny steps that barely move, which can make the method converge very slowly. Another is forgetting that \(\nabla f(x_k)^\top p_k\) is negative for a descent direction and getting the signs wrong.

Think about it

Why does the curvature condition alone not ensure that f decreases?

Because it only requires the slope to rise; a large step can satisfy it while increasing f. Armijo rules that out.

Exercises 10

  1. Which condition requires the function to decrease enough relative to its initial value?
  2. Which Wolfe condition prevents the step from being too short?
  3. In the Wolfe conditions, what relation must the constants \(c_1\) and \(c_2\) satisfy?
  4. If a step \(\alpha\) satisfies both Wolfe conditions, what is guaranteed?
  5. What is the name of the variant that bounds the slope at the new point in absolute value?
  6. Let \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\). Does \(\alpha=0.5\) satisfy the Armijo condition?
  7. Let \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\), \(c_2=0.9\). Which condition fails with \(\alpha=2\)?
  8. A step \(\alpha\) that is too short barely changes the gradient. Which Wolfe condition rejects it?
  9. Let \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), \(c_1=0.1\), \(c_2=0.9\). What happens with \(\alpha=0.01\)?
  10. With \(c_2=0.9\), \(f(x)=x^2\), \(x_k=1\), \(p_k=-1\), does the strong Wolfe curvature condition accept the step \(\alpha=1.5\)?

References

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