Line search · aiwiki.page

Line search is a procedure in mathematical optimization that determines how far to move along a chosen direction when updating an approximate solution. It reduces part of a multidimensional minimization problem to a one-dimensional problem, either minimizing the objective function along that direction or finding a step that satisfies specified acceptance conditions. Direction selection and step-size selection are separate components of the surrounding optimization algorithm. (sites.math.washington.edu)

Mathematical formulation

For a differentiable function $f:\mathbb{R}^n\to\mathbb{R}$ , a typical iteration is

x_{k+1}=x_k+\alpha_kp_k,

where $x_k$ is the current point in Euclidean space, $p_k$ is a search direction, and $\alpha_k>0$ is the step size. Define the scalar function

\phi_k(\alpha)=f(x_k+\alpha p_k).

Its derivative, obtained by the chain rule, is

\phi_k'(\alpha)=\nabla f(x_k+\alpha p_k)^\mathsf Tp_k.

A descent direction satisfies $\nabla f(x_k)^\mathsf Tp_k<0$ . This directional derivative condition ensures that sufficiently small positive steps decrease the objective. The quantity $\alpha_k$ is a scalar multiplier, not necessarily the geometric distance traveled: that distance is $\alpha_k\|p_k\|$ . (sites.math.washington.edu)

Exact and inexact searches

An exact line search selects a minimizer of the restricted function:

\alpha_k\in\operatorname*{arg\,min}_{\alpha\geq0} f(x_k+\alpha p_k).

“Exact” describes the mathematical target; numerical implementations ordinarily compute an approximation. An inexact line search instead accepts a step meeting inequalities designed to ensure adequate progress. Solving the scalar problem very accurately can consume substantial computation without proportionately improving the complete optimization process. (stanford.edu)

For the quadratic objective

f(x)=\tfrac12x^\mathsf TAx-b^\mathsf Tx,

with symmetric positive-definite matrix $A$ , differentiation gives the exact step along a descent direction $p$ :

\alpha_*=-\frac{\nabla f(x)^\mathsf Tp}{p^\mathsf TAp}.

This closed-form example illustrates that the line-search problem depends on both the current gradient and curvature along the chosen direction. Exact searches nevertheless do not eliminate the slow, zigzagging behavior that gradient descent can exhibit on elongated quadratic level sets. (stanford.edu)

Sufficient decrease and backtracking

The Armijo condition requires

f(x_k+\alpha p_k) \leq f(x_k)+c_1\alpha\nabla f(x_k)^\mathsf Tp_k, \qquad 0<c_1<1.

It compares the actual objective value with a fraction of the decrease predicted by the local linear model. Because the initial slope is negative, acceptance implies a strict reduction in the objective. However, arbitrarily small steps can satisfy this inequality, so the condition alone does not prevent inefficiently short moves. (sites.math.washington.edu)

Backtracking line search addresses step selection by starting with a positive trial value $\alpha_0$ and repeatedly multiplying it by a fixed factor $0<\rho<1$ until sufficient decrease holds. It accepts the first satisfactory member of

\alpha_0,\ \rho\alpha_0,\ \rho^2\alpha_0,\ldots.

For a differentiable objective and a strict descent direction, backtracking terminates after finitely many reductions in exact arithmetic. The argument follows from the definition of the derivative: sufficiently small steps satisfy the Armijo inequality. Starting with a trial step of one is common, particularly for Newton-type methods. (sites.math.washington.edu)

Wolfe conditions

The Wolfe conditions combine sufficient decrease with a curvature requirement:

\phi_k(\alpha)\leq \phi_k(0)+c_1\alpha\phi_k'(0),

\phi_k'(\alpha)\geq c_2\phi_k'(0), \qquad 0<c_1<c_2<1.

The second inequality rejects steps whose slope remains too close to the initial negative slope, thereby excluding sufficiently small steps. The strong Wolfe conditions replace it with

|\phi_k'(\alpha)|\leq c_2|\phi_k'(0)|,

which also limits a positive slope after passing a minimum along the line. For a continuously differentiable restricted objective that is bounded below, a descent direction admits steps satisfying these conditions. (sites.math.washington.edu)

A Wolfe search may enlarge trial steps before establishing an interval containing acceptable values, then refine that interval. Merely shrinking a trial step is not always sufficient: the curvature condition may require a larger step. Bisection provides one interval-refinement strategy. (sites.math.washington.edu)

Search directions and convergence

Line searches can accompany several direction-generating methods. Gradient descent uses $p_k=-\nabla f(x_k)$ . In Newton’s method, the direction solves

\nabla^2f(x_k)p_k=-\nabla f(x_k),

where $\nabla^2f$ is the Hessian matrix. Newton-like methods replace its inverse with an approximation. Positive definiteness ensures descent when the gradient is nonzero; an indefinite Hessian does not provide that guarantee. (sites.math.washington.edu)

Convergence depends on the interaction between directions, acceptance rules, and objective regularity. Under suitable assumptions, including Lipschitz continuity of the gradient and adequate descent directions, Wolfe-based methods yield stationarity results. In nonconvex problems, stationarity does not establish global optimality. For a differentiable convex function, a zero gradient identifies a global minimizer. Thus “global convergence” in numerical optimization must be distinguished from finding a global minimum of an arbitrary objective. (sites.math.washington.edu)

Computational implementation

Implementations track objective and gradient evaluations because acceptance testing can require several trial points per outer iteration. SciPy’s line_search routine seeks a step satisfying the strong Wolfe conditions, requires a descent direction, and reports evaluation counts. It also permits a maximum step, an iteration limit, and an additional acceptance test. Failure to find an acceptable step is returned explicitly rather than treated as successful optimization. (docs.scipy.org)