BFGS Algorithm

Optimization · Axiom Academy

Master the most popular quasi-Newton optimization method 1. From Newton to Quasi-Newton Newton's method uses the full Hessian matrix to find optimal directions: But computing the Hessian is expensive! Quasi-Newton methods approximate it instead. The key insight: we can build an approximation B k that improves with each iteration. BFGS updates the inverse Hessian approximation H k using this elegant formula: s k = x k+1 - x k is the step taken y k = ∇f(x k+1 ) - ∇f(x k ) is the gradient change 3. Why BFGS Maintains Positive Definiteness A critical property: if H k is positive definite and s k T y k > 0 , then H k+1 remains positive definite! The curvature condition s k T y k > 0 is automatically satisfied when using line search with the Wolfe conditions. This guarantees descent directions throughout optimization. 4. How the Approximation Improves Watch how the BFGS approximation converges to the true Hessian inverse over iterations: 5. L-BFGS: Limited Memory Version Standard BFGS stores an n × n matrix, which is prohibitive for large problems. L-BFGS solves this by storing only the last m vector pairs s i , y i . L-BFGS uses a two-loop recursion to compute H k ∇f(x k ) without forming the full matrix. With m = 3-20 , it works beautifully for problems with millions of variables! BFGS: Problems with n < 1000 variables where memory is not a concern L-BFGS: Large-scale problems (n > 1000) or when memory is limited

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