Newton's method for optimization
/ NOO-tun /
Steepest descent feels only the slope, like walking downhill in fog with no sense of how the valley curves. Newton's method also feels the CURVATURE: by knowing not just which way is downhill but how the ground bends, it can aim straight at the bottom of a local bowl in one bold leap. Where gradient descent crawls and zig-zags, Newton — when it works — converges blazingly fast.
The idea is to model the function near x_k by its second-order Taylor expansion (a quadratic bowl) and jump to the bottom of that bowl. The quadratic is m(p) = f(x_k) + grad f(x_k)^T p + (1/2) p^T H_k p, where H_k is the Hessian (curvature) matrix. Its minimizer is found by setting the model's gradient to zero, giving the Newton step H_k p = -grad f(x_k), so p = -H_k^{-1} grad f(x_k), and x_{k+1} = x_k + p (often with a line-search step length for safety). Note this is just Newton's method for solving the equation grad f(x) = 0 — the first-order optimality condition — applied to a vector function. Near a local minimum with a positive-definite Hessian, the error SQUARES each step: this is quadratic convergence, doubling the number of correct digits per iteration, so it reaches full double precision in a handful of steps.
The catches are real and worth stating plainly. First, you need the Hessian and must solve an n-by-n linear system each step — about O(n^3) work and O(n^2) storage — which is prohibitive when n is large (this is why quasi-Newton and L-BFGS exist). Second, the fast convergence is only LOCAL: far from a minimum, or when the Hessian is not positive definite (near a saddle or maximum), the raw Newton step can point uphill, overshoot wildly, or converge to the wrong kind of stationary point. Practical 'safeguarded' Newton therefore modifies the Hessian to be positive definite and adds a line search or trust region, trading some of the raw speed for global reliability.
Minimize f(x) = x^4 - 3x^2 + 2 from x_0 = 2. Here f'(x) = 4x^3 - 6x, f''(x) = 12x^2 - 6, and the Newton step is x_{k+1} = x_k - f'(x_k)/f''(x_k). From 2 it leaps to about 1.30, then 1.05, then 1.0001, then essentially the exact minimizer sqrt(3/2) = 1.2247... wait — it homes in on the true minimum with the error roughly squaring each step.
Use curvature to jump to a quadratic model's floor — error squares each step.
Quadratic convergence is LOCAL and conditional: it holds only near a minimum with a positive-definite Hessian and a decent starting guess. Far away, or near a saddle, a raw Newton step can ascend or diverge — which is why it must be safeguarded with a modified Hessian and a line search or trust region.