Definition
A line search is an iterative algorithmic technique used in numerical optimization to find an acceptable step size that sufficiently reduces a given objective function along a specified search direction. It determines how far to move from the current iterate toward a proposed direction before evaluating the function again.
Overview
Line search methods are a core component of many gradient‑based optimization algorithms, such as gradient descent, Newton’s method, quasi‑Newton methods (e.g., BFGS, L‑BFGS), and conjugate‑gradient techniques. After computing a descent direction $p_k$ at iteration $k$, the algorithm seeks a scalar step length $\alpha_k > 0$ that minimizes or adequately decreases the one‑dimensional function
$$ \phi(\alpha) = f(x_k + \alpha p_k), $$
where $f$ is the objective function and $x_k$ is the current point. The line search can be exact, aiming to solve $\min_{\alpha \ge 0}\phi(\alpha)$, or inexact, employing criteria that guarantee sufficient decrease and curvature while avoiding the computational cost of a full minimization.
Etymology/Origin
The term combines the geometric notion of a “line” in the search space—representing all points of the form $x_k + \alpha p_k$ for scalar $\alpha$—with “search,” indicating the process of locating an optimal step length. The concept developed alongside early calculus‑based optimization methods in the mid‑20th century, particularly within the field of operations research and numerical analysis. Formalized notions such as the Wolfe and Armijo conditions appeared in the 1960s and 1970s.
Characteristics
| Feature | Description |
|---|---|
| Purpose | Determine an appropriate step size $\alpha_k$ that improves the objective function while maintaining algorithmic stability. |
| Exact vs. Inexact | Exact line searches solve the one‑dimensional minimization problem to high precision; inexact searches satisfy conditions (e.g., Armijo, Wolfe, Goldstein) that guarantee sufficient progress. |
| Common Criteria |
|
| abla f(x_k)^\top p_k$. |
|
| abla f(x_k + \alpha p_k)^\top p_k \ge c_2 | |
| abla f(x_k)^\top p_k$. |
|
| abla f(x_k + \alpha p_k)^\top p_k | \le c_2 |
| abla f(x_k)^\top p_k | $. |
| Algorithms | Backtracking (iteratively reducing $\alpha$ until conditions hold), Brent’s method, golden‑section search, and more sophisticated interpolation‑based techniques. |
| Complexity | Inexact line searches typically require a few function and gradient evaluations per iteration, offering a favorable trade‑off between computational cost and convergence speed. |
| Convergence Guarantees | When combined with descent directions satisfying appropriate curvature properties, line search methods ensure global convergence to a stationary point under standard assumptions (e.g., Lipschitz continuity of the gradient). |
| Limitations | Exact line searches can be computationally expensive for high‑dimensional problems; inexact methods may yield suboptimal step sizes if criteria are too lax or if the objective function is ill‑conditioned. |
Related Topics
- Gradient descent – a fundamental optimization algorithm that commonly employs a line search to adapt its step size.
- Newton’s method – uses second‑order information; line searches are often incorporated to improve global convergence.
- Quasi‑Newton methods – such as BFGS and L‑BFGS, which rely heavily on line search strategies.
- Conjugate gradient method – a direction‑finding algorithm in which line searches determine the optimal step along conjugate directions.
- Armijo rule, Wolfe conditions, Goldstein conditions – specific criteria used to assess the suitability of a step length.
- Optimization theory – the broader mathematical field encompassing line search techniques.
- Backtracking line search – a simple, widely used inexact line search algorithm.
Line searches remain a vital tool in both theoretical analyses of optimization algorithms and practical implementations across scientific computing, machine learning, and engineering design.