Newton's Method with Backtracking Line Search

Controls

Newton steps

Armijo parameter $c$ Backtracking factor $\tau$ Function

Newton's method with backtracking line search

Newton's method for minimization uses the Newton direction $d_n = -f'(x_n)/f''(x_n)$ and updates:

$$x_{n+1} = x_n + \alpha_n \, d_n = x_n - \alpha_n \frac{f'(x_n)}{f''(x_n)}$$

With $\alpha_n = 1$ this recovers the standard Newton step. However, far from the minimum the full Newton step can overshoot. Backtracking line search selects $\alpha_n$ automatically to guarantee sufficient decrease.

The Armijo condition

For a general descent direction $d_n$, the Armijo condition requires:

$$f(x_n + \alpha\, d_n) \;\leq\; f(x_n) + c\,\alpha\, f'(x_n)\,d_n$$

Substituting the Newton direction $d_n = -f'(x_n)/f''(x_n)$ gives:

$$f\!\left(x_n - \alpha\frac{f'(x_n)}{f''(x_n)}\right) \;\leq\; f(x_n) - c\,\alpha\,\frac{[f'(x_n)]^2}{f''(x_n)}$$

Here $c \in (0,1)$ is a small constant (typically $c = 10^{-4}$ in practice; larger values are used here to make the effect visible).

The backtracking algorithm

Starting from $\alpha = 1$ (the full Newton step), the step is repeatedly shrunk by a factor $\tau \in (0,1)$ until the Armijo condition is satisfied:

Set $\alpha \leftarrow 1$.
If $f(x_n - \alpha f'(x_n)/f''(x_n)) \leq f(x_n) - c\,\alpha\,[f'(x_n)]^2/f''(x_n)$, accept $\alpha$.
Otherwise set $\alpha \leftarrow \tau\alpha$ and go to step 2.

The plot shows: the function $f(x)$ (blue); the tangent line at $x_n$ (gray dashed); the orange dashed line marking the Armijo RHS threshold $f(x_n) - c\,\alpha\,[f'(x_n)]^2/f''(x_n)$ for the accepted step size. The Armijo condition is satisfied when the function value lies at or below the orange line. Rejected trial steps (from the last iteration) are shown as faded red crosses × on the curve; the accepted step is the solid red dot. The vertical black dashed lines mark successive iterates $x_0, x_1, \ldots$

Use the +/− buttons and sliders to observe how a larger $c$ makes the condition stricter (requiring more backtracking), and how a smaller $\tau$ shrinks the step more aggressively.