12
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ So, no matter what smooth function $f$ I choose, setting $c_2<c_1$ will result in either the sufficient decrease or curvature condition not being satisfied? $\endgroup$ – Paul Sep 15 '12 at 15:56
  • 1
    $\begingroup$ No, the other way around. If you choose $c_2<c_1$ then there are functions $f(x)$ where one of the two conditions is not satisfied even though you have a descent direction. In such a case, line search wouldn't find a step length. $\endgroup$ – Wolfgang Bangerth Sep 15 '12 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.