a line search

You have decided which way to walk downhill — now: how far? Take a baby step and you barely move; take a giant leap and you may sail clean over the valley and end up higher than you started. A line search is the act of choosing the step length: once a descent direction is fixed, you slide along that single line and pick a distance that genuinely lowers the function by a worthwhile amount.

Concretely, the descent method sets x_{k+1} = x_k + alpha p_k, where p_k is the chosen direction and alpha > 0 is the step length to determine. Walking along the line freezes the multi-dimensional problem into a one-variable function phi(alpha) = f(x_k + alpha p_k), and the line search minimizes (or sufficiently reduces) phi over alpha > 0. An EXACT line search finds the alpha that truly minimizes phi — usually too expensive and unnecessary. In practice one does an INEXACT line search: accept any alpha that decreases f 'enough'. The workhorse is backtracking — start with a generous trial step (say alpha = 1, the natural Newton step), and while the decrease is insufficient, shrink alpha by a factor (alpha <- 0.5 * alpha) until a sufficient-decrease test (the Armijo condition) passes. This costs only a few extra function evaluations per iteration.

Line search and the trust-region method are the two great strategies for controlling step length, and a sound line search is what makes a descent method provably converge rather than oscillate or stall. The honest point is what 'enough decrease' means: simply requiring f to drop is not safe — you could take ever-tinier steps that decrease forever yet never reach the minimum. The Armijo (sufficient-decrease) condition demands the drop be at least a fixed fraction of what the slope predicts, and pairing it with a curvature condition gives the full Wolfe conditions, which rule out steps that are too short as well as too long.