Understanding the Wolfe Conditions for an Inexact line search

Question

According to Nocedal & Wright's Book Numerical Optimization (2006), the Wolfe's conditions for an inexact line search are, for a descent direction $p$,

Sufficient Decrease: $f(x+\alpha p)\le f(x)+c_1\alpha_k\nabla f(x)^T p$
Curvature Condition: $\nabla f(x+\alpha p)^Tp\ge c_2 \nabla f(x)^T p$
for $0<c_1<c_2<1$

I can see how the sufficient decrease condition states that the function value at the new point $x+\alpha p$ must be under the tangent at $x$. But I'm not sure what the curvature condition is telling me geometrically. Also, why must the relation $c_1<c_2$ be imposed? What does this accomplish, geometrically?

Answer 1

The curvature condition essentially says this: We know that $\nabla f(x)\cdot p < 0$ (because $p$ is a descent direction). So in direction $p$, it goes downhill. Now, we're looking for a minimum, i.e. a point where $\nabla f=0$. That means that we don't want to accept step lengths $x+\alpha p$ where the gradient in direction $p$, i.e., $\nabla f(x+\alpha p) \cdot p$ is still as negative as it is at x. Rather, we want to stop at a place where the gradient is less negative or even positive.

Because the right hand side of the curvature condition is negative, a common variant of the condition is to require $$|\nabla f(x+\alpha p) \cdot p| \le c_2 |\nabla f(x) \cdot p|$$ which I usually find easier to understand.

Understanding this will allow you to easily construct cases where you can't satisfy both conditions unless $c_1<c_2$.