BFGS against gradient descent on the Rosenbrock valley

Adam Zettel · September 25, 2026 · written with an agent

H_{k + 1} = (I - ρ s y^{T}) H_{k} (I - ρ y s^{T}) + ρ s s^{T}, ρ = \frac{1}{y ^{T} s}

Both methods start at $(- 1.2, 1)$ on Rosenbrock's function and use the same backtracking line search; they differ only in the direction they search along. BFGS is within $1 0^{- 9}$ of the minimum at $(1, 1)$ after 35 iterations and has a zero gradient to $1 0^{- 12}$ after 36. Gradient descent takes 22,962 iterations to get within $1 0^{- 9}$ , and near the minimum it gains a factor of only 0.99919 per step, close to $(κ - 1) / (κ + 1)$ for the Hessian's condition number $κ = 2508$ .

Open in the workbench Download .vivOutputs below are from the site build’s run; Run all runs it again in your browser.

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

Rosenbrock's function

f (x, y) = (1 - x)^{2} + 100 (y - x^{2})^{2}

is a standard test for minimizers. Its minimum is $f = 0$ at $(1, 1)$ , at the end of a long, curved valley along the parabola $y = x^{2}$ . The floor of the valley is nearly flat and the walls are steep, so the downhill direction points mostly at the opposite wall, not along the valley toward the minimum.

Both methods here step from $x$ to $x + t d$ for a direction $d$ . They choose $t$ the same way: try $t = 1$ , and halve it until the step lowers $f$ by at least $1 0^{- 4}$ times what the slope at $x$ predicts (the Armijo condition, $f (x + t d) \leq f (x) + 1 0^{- 4} t \nabla f \cdot d$ ). Gradient descent takes $d = - \nabla f$ . BFGS takes $d = - H \nabla f$ , where $H$ is its running estimate of the inverse of the Hessian, the matrix of second derivatives.

The reference is a Python twin of the same algorithm (posts/refs/bfgs-against-gradient-descent-on-rosenbrock.py, output beside it). For comparison it also runs scipy.optimize.minimize(method="BFGS"), which uses a different line search (one that enforces the Wolfe conditions); it stops after 35 iterations at the same minimum.

Printed

24.2

[-215.6, -88]

Tests 1 of 1 pass

f is 24.2 at the start and 0 at (1, 1), where the gradient is zero (passes)

Gradient descent

Gradient descent goes downhill, and on this function downhill is across the valley. Once it reaches the floor, each step overshoots a little onto the far wall, and the step that corrects it moves only slightly along the valley.

There is one exception here. For its first 30 iterations it zigzags on the floor near $(- 1, 1)$ , where the floor is almost level and the downhill direction points almost straight along $+ x$ . At iteration 30 the line search accepts $t = 1/2$ , and one step of length 1.85 carries it from $(- 0.985, 0.971)$ to $(0.868, 0.904)$ , on the floor near the other end. The valley bends, and the straight step cuts across the bend, through ground where $f$ is about 89; the Armijo test only compares $f$ where the step lands ( $2.28$ ) with where it started ( $3.94$ ). No other step is longer than 0.23. After it, gradient descent is 0.16 from the minimum and needs 22,931 more iterations.

The cell runs it until it is within $1 0^{- 9}$ of $(1, 1)$ , keeping every iterate for the figures.

Printed

gd_iters: 22962

gd_1e3: 5932

gd_1e6: 14446

jump: [30, 1.85475]

[-0.985159, 0.971205, 0.86839, 0.904409]

Tests 2 of 2 pass

the longest gradient-descent step is at iteration 30, t = 1/2 and 1.85 long, landing where the Python twin's does (passes)
gradient descent needs 22,962 iterations to get within 1e-9, as the Python twin does (passes)

Why it is that slow

Near the minimum $f$ is close to a quadratic, with Hessian $(802 - 400 - 400 200)$ . Its eigenvalues are 1001.6 and 0.399: the valley is 2508 times steeper across than along (kappa). A step size small enough not to be thrown up the steep wall (it must stay under $2/1001.6$ ) shrinks the error along the valley by only a factor of about $1 - 0.399 t$ per step. The best any fixed step can do on this quadratic is to shrink the error by $(κ - 1) / (κ + 1)$ per step, with $κ = 2508$ the ratio of the two eigenvalues: 0.99920. From $1 0^{- 6}$ to $1 0^{- 9}$ gradient descent gains 0.99919 per step, within 2% of that rate in the logarithm.

Printed

hess_eigs: [0.399361, 1001.6]

kappa: 2508.01

best_rate: 0.999203

gd_rate: 0.999189

Tests 2 of 2 pass

the Hessian at (1, 1) has eigenvalues 0.399 and 1001.6, condition number 2508 (numpy agrees) (passes)
near the minimum gradient descent gains 0.99919 a step, within 2% of (kappa-1)/(kappa+1) in the log (passes)

BFGS

BFGS keeps a 2 by 2 matrix $H$ , starting from the identity, so its first step is a gradient step. After each step it knows two new vectors: the step $s = x_{k + 1} - x_{k}$ and the change in gradient $y = \nabla f_{k + 1} - \nabla f_{k}$ . For a quadratic with Hessian $B$ , $y = B s$ . BFGS changes $H$ by the smallest amount (a rank-two update, the formula under the title) that makes the new $H$ satisfy $H y = s$ , the one equation about the inverse Hessian this step has measured. It skips the update when $y \cdot s \leq 1 0^{- 14}$ , which would make $H$ lose positive definiteness.

As $H$ approaches the true inverse Hessian, $- H \nabla f$ approaches Newton's step, the line search accepts $t = 1$ , and convergence becomes superlinear: the ratio of successive errors goes to zero instead of settling at a constant. Here it is 0.305 at iteration 31, between 0.013 and 0.033 for the next three, and $1.1 \times 1 0^{- 4}$ at iteration 35. The last five errors match the Python twin's to the last bit.

Printed

bfgs_iters: 36

bfgs_1e9: 35

8.9509e-16

ratios: [0.142218, 0.304735, 0.0158501, 0.0322082, 0.0136759, 0.000107483]

Tests 4 of 4 pass

BFGS is within 1e-9 of (1, 1) after 35 iterations and has |grad f| < 1e-12 after 36 (passes)
the last errors are the Python twin's, bit for bit (passes)
the error ratio falls from 0.3 to 1e-4 over the last iterations, so convergence is superlinear (passes)
over those last iterations the line search takes the full step, t = 1 (passes)

The paths

The first figure draws both paths over three level curves of $f$ (at 1, 5, and 24.2, the level through the start) and the valley floor $y = x^{2}$ . Gradient descent's line shows its first 20 iterates, then every 200th: the long straight segment is the jump across the bend, and each later point stands for 200 small zigzags near $(1, 1)$ . BFGS lands on the floor and follows the curve of the valley around to the minimum.

The second figure is the distance to $(1, 1)$ against the iteration number, both on log axes. Gradient descent's line bends down only slowly, a constant factor per step. BFGS's plunges in its last few steps.

f = 1f = 5f = 24.2gradient descentBFGS

gradient descentBFGS