Gradient descent · Definition
Line search
After choosing a descent direction, we still need to decide how far to move. A poorly calibrated step can make the method very slow or stop decreasing the function.
Definition
Line search is a procedure that chooses the step size \(\alpha\) along a descent direction \(p_k\) to reduce the value of the objective function.
The Armijo condition demands a sufficient decrease relative to \(f(x_k)\), with \(0<c_1<1\), so that the decrease is proportional to the step. Backtracking starts with a large \(\alpha\) and multiplies it by \(\rho\in(0,1)\) until the condition holds; since the direction is a descent direction, some \(\alpha\) always satisfies it.
Take \(f(x)=x^2\), \(x_k=1\) and \(p_k=-2\), with \(c_1=0.5\). With \(\alpha=1\) the new point is \(-1\), with \(f=1\), which does not drop below the bound \(-1\). With \(\alpha=\tfrac12\) the point is \(0\), with \(f=0\) and bound \(0\), so backtracking accepts \(\alpha=\tfrac12\).
A typical mistake is demanding the exact minimum of \(f\) along the line at every iteration, which costs many evaluations without much gain in convergence. Another common error is using a direction that is not a descent direction, with \(\nabla f(x_k)^\top p_k\ge 0\), because the promised decrease no longer exists.
Think about it
If \(\nabla f(x_k)^\top p_k>0\), can Armijo hold for some sufficiently small \(\alpha\)? Explain why.
No. For small \(\alpha\), \(f(x_k+\alpha p_k)\approx f(x_k)+\alpha\nabla f(x_k)^\top p_k\), which exceeds the bound \(f(x_k)+c_1\alpha\nabla f(x_k)^\top p_k\) because \(c_1<1\). So backtracking never terminates.
Exercises 10
- What does the Armijo condition require of the step \(\alpha\)?
- What is the name of the method that reduces \(\alpha\) by multiplying it by \(\rho\) until the condition holds?
- What must the direction \(p_k\) satisfy for line search to make sense?
- What happens if the step \(\alpha\) is too large?
- Which parameter controls the minimum slope required by the Armijo condition?
- With \(f(x)=x^2\), \(x_k=1\), \(p_k=-2\), \(c_1=0.5\) and \(\rho=0.5\), which step does backtracking accept if it starts at \(\alpha=1\)?
- With \(f(x)=x^2\), \(x_k=1\), \(p_k=-2\) and \(\alpha=\tfrac12\), what is \(x_{k+1}\)?
- With \(\nabla f(x_k)^\top p_k=-4\), \(c_1=0.25\) and \(\alpha=2\), what is \(c_1\alpha\nabla f(x_k)^\top p_k\)?
- With \(f(x)=x^2\), \(x_k=2\), \(p_k=-4\), \(c_1=0.25\), \(\rho=0.5\) and starting at \(\alpha=1\), which step does backtracking accept?
- Which statement about line search is false?
What comes next
References
- Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
- Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.