Optimization

Quasi-Newton Methods

Approximate the Hessian from successive gradients, capturing curvature without ever computing second derivatives.

The idea

Newton's method converges fast but needs the Hessian, which is expensive to form and invert. Quasi-Newton methods build an approximation of the Hessian (or its inverse) using only gradient differences between iterations. They recover most of Newton's fast convergence at a fraction of the cost per step.

The secant condition

Kronos motion — training from sim

Over one step, define s = x_{k+1} - x_k and y = grad f(x_{k+1}) - grad f(x_k). A good Hessian approximation B should satisfy the secant equation B s = y, mimicking how the true Hessian relates changes in position to changes in gradient. Quasi-Newton updates enforce this while keeping B symmetric and positive definite.

Common updates

BFGS: the most widely used rank-two update, robust and self-correcting.
DFP: an earlier rank-two update, historically important.
SR1: a rank-one update that can better capture indefinite curvature but needs safeguards.
L-BFGS: a limited-memory version for high dimensions.

Superlinear convergence

Quasi-Newton methods converge superlinearly: faster than the linear rate of gradient descent but not quite the quadratic rate of Newton. Crucially, each step costs only O(n^2) (or O(n) for limited-memory variants) instead of O(n^3), because no linear system with a fresh Hessian is solved.

Practical use

Combined with a line search satisfying the Wolfe conditions, BFGS is a reliable default for smooth unconstrained problems of moderate size. For very large problems, L-BFGS stores only a few vectors and scales to millions of variables, making it a common choice for training and for scientific inverse problems.

python

from scipy.optimize import minimize
res = minimize(f, x0, jac=grad, method='BFGS')

Quasi-Newton solvers are the practical default when gradients are available but Hessians are too costly, as in large simulation-based design problems.