Newton's Method for Minimization

The root-finder aimed at f' — one step solves any quadratic, and no change of coordinates can slow it down.

The idea

Newton's method for minimization finds a minimizer of a smooth convex function, and it is the root-finding Newton's Method aimed at a new target. That method solves $g(x) = 0$ by replacing $g$ with its tangent line at the current point and moving to where the line crosses zero, $x := x - g(x)/g'(x)$. Minimizing a smooth $f$ means solving $f'(x) = 0$, so apply the root-finder to $g = f'$. In $n$ variables $f'$ becomes the gradient $\nabla f$ and $f''$ becomes the Hessian $\nabla^{2}f$.

Definition (Newton step and Newton decrement).

For a twice-differentiable $f$ with $\nabla^{2}f(x) \succ 0$, the Newton step at $x$ and the Newton decrement are $\Delta x_{\text{nt}} = -\nabla^{2}f(x)^{-1}\nabla f(x), \qquad \lambda(x) = \left(\nabla f(x)^{T}\nabla^{2}f(x)^{-1}\nabla f(x)\right)^{1/2}.$ Newton's method for minimization moves from $x$ to $x + \Delta x_{\text{nt}}$ and repeats.

The same step arises from a quadratic model: the quadratic that matches $f$ at $x$ in value, gradient and curvature — the second-order Taylor model — has its minimum exactly one Newton step away. Gradient descent sees only the slope, so a step size must be supplied from outside; Newton's method reads the curvature as well, and the step carries its own length.

Started close enough to the minimizer $x^{\star}$ of a strictly convex $f$, the iterates converge to $x^{\star}$, and they converge quadratically: the number of correct digits roughly doubles at every iteration. On a quadratic $f$ the model equals the function, so a single step lands on $x^{\star}$ exactly.

In practice the step is guarded: far from the minimizer the quadratic model can overreach, so a backtracking line search shortens the step until $f$ decreases enough, and the Newton decrement, with $\tfrac{1}{2}\lambda(x)^{2}$ estimating the gap $f(x) - p^{\star}$, supplies the stopping test.

Algorithm.

Algorithm: Newton's Method (minimization) Input: smooth convex f, starting point x, tolerance ε > 0 Output: x with f(x) within ε of the minimum value 1. solve ∇²f(x) v = -∇f(x) // the Newton step Δx_nt, computed without inverting 2. λ² = -∇f(x)·v // the squared Newton decrement 3. if λ²/2 ≤ ε, return x // λ²/2 estimates the suboptimality gap 4. choose t by backtracking line search // near the optimum it accepts t = 1 5. x = x + t v 6. go to step 1

Ways to work on it

• Walkthrough. Minimize a function by repeatedly jumping to the minimum of its local quadratic model.
• Proof. Prove that a linear change of coordinates cannot change what Newton's method does, unlike gradient descent.
• Practice. Compute Newton steps and decrements for small examples.
• Hardest. Follow the pure and damped iterations on a convex objective and compare their outcomes.

Not sure where to start? Take the ten-question placement test.