Line Search Methods

Why This Matters

Gradient descent tells you which direction to move (negative gradient) but not how far. If you step too far, you overshoot and the objective increases. If you step too little, convergence is painfully slow. Line search methods automate step size selection with provable guarantees: the objective decreases enough at each step to ensure convergence.

Every practical optimizer. L-BFGS, conjugate gradient, Newton's method. relies on a line search to select step sizes. Getting this right is essential.

Mental Model

You are standing on a hilly landscape and you know the downhill direction. But how far should you walk before stopping? Walk too far and you end up climbing again. Walk too little and it takes forever to reach the valley.

Line search says: walk until you have descended "enough" (Armijo condition), and optionally until the slope has flattened "enough" (Wolfe condition). Backtracking is the simplest strategy: try a big step, and if it does not satisfy the condition, halve it and try again.

Formal Setup and Notation

We want to minimize $f: \mathbb{R}^d \to \mathbb{R}$ where $f$ is smooth. At iteration $k$, we have a descent direction $p_k$ (e.g., $p_k = -\nabla f(x_k)$) and we want to choose a step size $\alpha_k > 0$:

$x_{k+1} = x_k + \alpha_k p_k$

Definition

Armijo (Sufficient Decrease) Condition

The step size $\alpha$ satisfies the Armijo condition with parameter $c_1 \in (0, 1)$ if:

$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T p_k$

The right side is a linear approximation of $f$ along $p_k$ with slope reduced by $c_1$. Typical choice: $c_1 = 10^{-4}$. This ensures the objective decreases by at least a fraction of what the linear model predicts.

Definition

Curvature (Wolfe) Condition

The step size $\alpha$ satisfies the curvature condition with parameter $c_2 \in (c_1, 1)$ if:

$\nabla f(x_k + \alpha p_k)^T p_k \geq c_2 \nabla f(x_k)^T p_k$

This prevents $\alpha$ from being too small: it requires that the slope at the new point has decreased sufficiently compared to the slope at the starting point. Typical choice: $c_2 = 0.9$ for Newton/quasi-Newton, $c_2 = 0.1$ for conjugate gradient.

Definition

Wolfe Conditions

A step size satisfying both the Armijo condition and the curvature condition is said to satisfy the Wolfe conditions. The strong Wolfe conditions replace the curvature condition with $|\nabla f(x_k + \alpha p_k)^T p_k| \leq c_2 |\nabla f(x_k)^T p_k|$, which also prevents the step from being too large.

Core Definitions

Backtracking line search is the simplest method to find a step size satisfying the Armijo condition:

1. Start with $\alpha = \alpha_0$ (e.g., $\alpha_0 = 1$)
2. While $f(x_k + \alpha p_k) > f(x_k) + c_1 \alpha \nabla f(x_k)^T p_k$: set $\alpha \leftarrow \rho \alpha$ where $\rho \in (0, 1)$ (e.g., $\rho = 0.5$)
3. Return $\alpha$

This always terminates because the Armijo condition holds for all sufficiently small $\alpha > 0$ (by Taylor expansion).

Exact line search finds $\alpha^* = \arg\min_{\alpha > 0} f(x_k + \alpha p_k)$. This is rarely used in practice because: (a) it requires solving a one-dimensional optimization problem at each step, and (b) inexact line search with Wolfe conditions gives the same convergence guarantees for much less work.

Main Theorems

Theorem

Convergence of Gradient Descent with Backtracking

Statement

Gradient descent with backtracking line search (Armijo condition, parameter $c_1 \in (0,1)$, contraction factor $\rho \in (0,1)$) satisfies:

$\min_{k=0,\ldots,K-1} \|\nabla f(x_k)\|^2 \leq \frac{f(x_0) - f^*}{K \cdot c_1 \cdot \min(\alpha_0, \rho/L)}$

In particular, $\|\nabla f(x_k)\| \to 0$ as $k \to \infty$.

Intuition

The Armijo condition guarantees that each step makes enough progress. The backtracking ensures the step size is never too large (we shrink until Armijo holds) and never too small (we stop shrinking as soon as Armijo holds). The minimum step size is at least $\rho / L$, ensuring bounded progress. Over $K$ iterations, at least one gradient must be small.

Proof Sketch

At each iteration, the Armijo condition gives $f(x_k) - f(x_{k+1}) \geq c_1 \alpha_k \|\nabla f(x_k)\|^2$. The backtracking ensures $\alpha_k \geq \rho/L$ (if the initial step was rejected, the accepted step is at least $\rho$ times the threshold $1/L$). Summing over iterations: $f(x_0) - f^* \geq c_1 \min(\alpha_0, \rho/L) \sum_{k=0}^{K-1} \|\nabla f(x_k)\|^2$. Divide both sides by $K$ and take the minimum.

Why It Matters

This shows gradient descent converges to a stationary point without knowing the Lipschitz constant $L$ in advance. The backtracking line search automatically adapts the step size. You only need $f$ to be smooth and bounded below.

Failure Mode

This guarantees convergence to a stationary point, not a global minimum. For nonconvex $f$, the algorithm may converge to a saddle point or local minimum. Also, if the initial step size $\alpha_0$ is too small, the algorithm wastes iterations not taking advantage of possible larger steps.

Canonical Examples

Example

Backtracking on a quadratic

For $f(x) = \frac{1}{2}x^TAx - b^Tx$ with $A$ positive definite, the gradient is $\nabla f(x) = Ax - b$ and $L = \lambda_{\max}(A)$. With $\alpha_0 = 1$ and $\rho = 0.5$, backtracking accepts $\alpha = 1$ whenever the condition number is moderate. For ill-conditioned problems, it may need a few halvings to find an acceptable step.

Common Confusions

Watch Out

Armijo alone is not enough for quasi-Newton methods

The Armijo condition alone allows step sizes that are too small. For quasi-Newton methods (like L-BFGS), you also need the curvature condition (Wolfe conditions) to ensure that the approximate Hessian update is well-defined. Without the curvature condition, the quasi-Newton updates can degenerate.

Watch Out

Exact line search is not better in general

Exact line search gives the smallest possible value along the search direction, but this does not necessarily lead to the fewest total iterations. For quadratics, exact line search with steepest descent produces zigzagging. The Wolfe conditions are sufficient for convergence and much cheaper.

Summary

• Armijo condition: $f(x + \alpha p) \leq f(x) + c_1 \alpha \nabla f(x)^T p$
• Wolfe adds curvature: gradient at new point is flatter than at old point
• Backtracking: start big, shrink by factor $\rho$ until Armijo holds
• Step size too large: objective increases. Too small: slow convergence
• Backtracking line search does not require knowing $L$

Exercises

ExerciseCore

Problem

For $f(x) = x^4$, $x_0 = 2$, direction $p = -f'(x_0) = -32$, and $c_1 = 10^{-4}$: does the step size $\alpha = 1$ satisfy the Armijo condition?

Hint

Reveal Solution

ExerciseAdvanced

Problem

Prove that for any $c_1 \in (0,1)$ and any descent direction $p_k$ (with $\nabla f(x_k)^T p_k < 0$), the Armijo condition is satisfied for all sufficiently small $\alpha > 0$.

Hint

Reveal Solution

References

Canonical:

• Nocedal & Wright, Numerical Optimization (2006), Chapter 3
• Armijo, "Minimization of Functions Having Lipschitz Continuous First Partial Derivatives" (1966)

Current:

• Boyd & Vandenberghe, Convex Optimization (2004), Section 9.2

• Hastie, Tibshirani, Friedman, The Elements of Statistical Learning (2009)

Next Topics

The natural next steps from line search methods:

• Proximal gradient methods: line search for composite objectives
• Quasi-Newton methods: using curvature information with Wolfe conditions