Line Search

Line search chooses how far to move along a descent direction each iteration, turning a direction into a concrete, safely sized step.

Direction versus distance

Most iterative optimizers separate two decisions: which direction to move (given by the gradient, Newton, or quasi-Newton step) and how far to move along it. Line search answers the second question. Given a current point x and a descent direction p, it seeks a step length alpha > 0 that makes phi(alpha) = f(x + alpha p) sufficiently smaller than f(x), then sets the next iterate to x + alpha p.

Exact versus inexact

An exact line search finds the alpha that truly minimizes phi(alpha) along the direction, which is rarely worth the cost. Practical methods use inexact line search: find any step that decreases the objective enough, quickly. The standard is backtracking, which starts from a full step and repeatedly shrinks it by a factor until a sufficient-decrease test passes. This is cheap and robust.

def backtracking(f, grad, x, p, alpha=1.0, c=1e-4, rho=0.5):
    fx = f(x); gx = grad(x)
    slope = gx @ p                       # directional derivative
    while f(x + alpha*p) > fx + c*alpha*slope:  # Armijo test
        alpha *= rho                     # shrink the step
    return alpha

Sufficient decrease

A step that merely decreases the objective is not enough; a sequence of tiny decreases can converge to a non-minimizer. The Armijo condition requires the decrease to be at least a fraction c of what the linear model predicts: f(x + alpha p) <= f(x) + c alpha grad^T p. This rules out steps that are too long relative to the progress they make. A companion curvature condition rules out steps that are too short; together they form the Wolfe conditions.

Why it matters

Line search is what makes quasi-Newton methods such as BFGS reliable: it guarantees enough progress each step to prove global convergence, while letting the method take full Newton-like steps when they are safe. It also underlies trust-region alternatives, which instead bound the step first and then choose a direction. A robust line search is often the difference between an optimizer that converges from any start and one that diverges.