Quasi-Newton Methods and BFGS

Newton's method converges fast because it uses curvature (the Hessian) to jump straight toward a minimum, but computing that curvature exactly is expensive — for a model with a thousand parameters, the Hessian is a million-entry matrix that must be built and inverted at every step. Most real optimization problems (calibrating a pricing model, fitting a machine-learning model) can't afford that. Quasi-Newton methods ask: can we get almost all of Newton's speed while only ever using the gradient, which is far cheaper to compute?

An analogy: learning the terrain by walking it

A cartographer surveying a valley could measure the exact curvature everywhere with precise instruments (expensive, like the true Hessian) — or she could simply walk the valley, noting how the slope changes from each step to the next, and gradually build up a good mental picture of the terrain's shape purely from that sequence of slope readings. She never measures curvature directly, but after enough steps her mental map becomes almost as good as an exact survey. Quasi-Newton methods do exactly this: they build an approximation to the curvature purely from the history of gradients observed along the way.

The method, one symbol at a time

Let $\nabla f(x_k)$ be the gradient at step $k$, and let $B_k$ be the current approximation to the Hessian (starting simple, often the identity matrix). The quasi-Newton step is

$$x_{k+1} = x_k - B_k^{-1} \nabla f(x_k) ,$$

which looks exactly like Newton's method — the only difference is $B_k$ is a built-up estimate, not the true Hessian. After taking the step, the key move is the update rule: using the change in position $s_k = x_{k+1} - x_k$ and the change in gradient $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$, the algorithm refines $B_k$ into $B_{k+1}$ so that it correctly predicts how much the gradient changed for that particular step. BFGS (named for Broyden, Fletcher, Goldfarb, and Shanno, who each derived it independently) is the most widely used update rule; in plain English, it nudges the curvature estimate just enough to be consistent with the most recent observed slope change, while disturbing the rest of the estimate as little as possible.

Worked example 1: building a 1-D curvature estimate

In one dimension the "Hessian" is just a number (the second derivative). Suppose at $x_0 = 0$ the gradient is $f'(0) = -12$, and we start with the naive curvature guess $B_0 = 1$ (since we have no information yet). The step is $x_1 = 0 - (-12)/1 = 12$ — clearly too far, since the true curvature is larger than 1. Suppose the true gradient at $x_1 = 12$ turns out to be $f'(12) = 60$. The observed change is $s_0 = 12 - 0 = 12$ and $y_0 = 60 - (-12) = 72$. The secant condition that any quasi-Newton update must satisfy is $B_1 s_0 = y_0$, giving $B_1 = 72 / 12 = 6$ — matching the true curvature of $f(x) = 3x^2 - 12x + 7$ from the Newton's-method example exactly, after just one correction.

Worked example 2: calibrating a two-parameter model

A quant is calibrating a two-parameter volatility model to match five market option prices by minimizing squared pricing error. Computing the exact 2×2 Hessian at every iteration requires evaluating the pricing model many extra times to get second derivatives numerically. Using BFGS instead, the optimizer starts with $B_0$ as the identity matrix (i.e., assumes gradient descent behavior initially) and, after each of the first few steps, updates $B_k$ using only the gradient of the squared-error objective (which the pricer already computes cheaply). By iteration 5–6, the approximated curvature has converged close enough to the true Hessian that step sizes and directions behave almost identically to full Newton's method — but the calibration used only gradient evaluations throughout, roughly 5–10x fewer model evaluations than computing exact Hessians at each step would have needed.

Compare a fixed-step gradient path against a curvature-adapting path on the same bowl-shaped loss: notice how the adaptive path's steps get longer in flat directions and shorter in steep ones as it "learns" the shape, converging in far fewer iterations.

What this means in practice

BFGS and its low-memory variant L-BFGS are the default optimizers behind most model calibration and maximum-likelihood fitting in quant finance and machine learning — they're what runs under the hood when a library function just says "minimize." L-BFGS in particular never stores the full $B_k$ matrix at all, only a handful of recent $(s_k, y_k)$ pairs, making it usable even when there are millions of parameters.