Line Search Methods

Optimization · Axiom Academy

Finding optimal step sizes along search directions for efficient optimization Starting from a point x k , we have a search direction p k . The line search problem is to find a step size that minimizes the function along the ray. We're solving a one-dimensional optimization problem: finding the best to minimize f(x k + p k ). 2. Exact vs. Inexact Line Search Exact line search finds the precise minimum along the search direction. While theoretically optimal, it's computationally expensive and often unnecessary. Inexact line search (like backtracking) finds a "good enough" step size that satisfies certain conditions. This is much more practical and is what's used in modern optimization algorithms. The Wolfe conditions provide a mathematical framework for accepting a step size in inexact line search. They consist of two parts: Sufficient Decrease (Armijo condition): Ensures the function value decreases enough. The new value should be below a linear approximation. Curvature Condition: Ensures we don't take steps that are too small. The slope at the new point should be less steep than at the start. Backtracking is a simple, practical inexact line search method. It starts with a large step size and repeatedly reduces it (typically by multiplying by 0.5 or 0.8) until the sufficient decrease condition is satisfied. This approach is efficient because it evaluates the function at only a few points and quickly finds an acceptable step size.

This is the written version of the interactive lesson above. See the full Optimization course.