Optimization

Line Search Methods

Given a descent direction, choose a step length that sufficiently decreases the objective, guaranteeing global convergence.

Direction then distance

Many optimizers work in two stages: pick a descent direction d (from gradient descent, Newton, or quasi-Newton), then choose a step length a > 0 along it. The line search selects a so the new point x + a*d genuinely reduces the objective. A poor step length can stall or diverge even with a good direction.

The Wolfe conditions

A step length is acceptable if it satisfies two conditions. The Armijo (sufficient decrease) condition requires f(x + a d) <= f(x) + c1 * a * grad^T d, ensuring real progress. The curvature condition requires grad(x + a d)^T d >= c2 * grad^T d, preventing steps that are too short. Typical constants are c1 = 1e-4 and c2 = 0.9.

Backtracking

Start with a trial step (often 1 for Newton and quasi-Newton).
If the Armijo condition fails, multiply the step by a factor (e.g. 0.5).
Repeat until sufficient decrease is achieved.

Exact versus inexact

An exact line search minimizes f along the direction, which is expensive and rarely worth it. Inexact line searches that merely satisfy the Wolfe conditions are far cheaper and sufficient for fast convergence. Quasi-Newton methods specifically require the curvature condition to maintain a positive-definite Hessian estimate.

Global convergence

Zoutendijk's theorem shows that any method combining descent directions bounded away from orthogonality to the gradient with a Wolfe line search converges to a stationary point. This makes line search the standard mechanism for globalizing Newton, quasi-Newton, and conjugate-gradient methods.

python

def backtrack(f, grad, x, d, a=1.0, c1=1e-4, rho=0.5):
    fx = f(x); gd = grad(x) @ d
    while f(x + a*d) > fx + c1*a*gd:
        a *= rho
    return a

Line search is the reliability layer that turns a fast local method into a globally convergent solver for design optimization.