Quasi-Newton Methods

Optimization · Axiom Academy

Achieving Newton-like convergence without computing the Hessian directly 1. The Motivation: Newton Without the Cost Newton's method uses second-order information (the Hessian matrix) to achieve quadratic convergence, but computing and inverting the Hessian is computationally expensive, requiring O(n³) operations per iteration. The key insight: What if we could approximate the Hessian using only gradient information and update this approximation cheaply at each iteration? Quasi-Newton methods replace H k -1 with an approximation B k -1 that's easier to compute and update. 2. Building the Hessian Approximation Instead of computing the true Hessian at each iteration, quasi-Newton methods maintain an approximation matrix B k that mimics the Hessian's behavior. This approximation is updated using only first-order information (gradients) from previous iterations, making each step much cheaper than full Newton's method. The fundamental constraint that quasi-Newton methods satisfy is the secant equation , which ensures the approximation B k+1 correctly captures the curvature along the most recent search direction. Let s k = x k+1 - x k be the step taken, and y k = ∇f(x k+1 ) - ∇f(x k ) be the change in gradient. The secant equation requires:

This is the written version of the interactive lesson above. See the full Optimization course.