Conjugate Gradient vs Steepest Descent (2D)

Projection of a three-variable quadratic bowl: the zig-zag of steepest descent against the A-conjugate steps of conjugate gradient.

Presets

Playback

Problem: the shape of the valley

Start point and line search

Speed

Layers

Model check

The science

What this page shows

Two optimisation algorithms start from the same point on the same quadratic bowl in three variables and race to its minimum. The bowl is f(x) = ½ xT A x with a symmetric positive-definite matrix A = Q diag(λ1, λ2, λ3) QT. Its level sets f = c are ellipsoids whose semi-axes are √(2c/λi) along the eigenvectors, so a large condition number κ = λ3/λ1 means a long, narrow valley. The sliders change κ, the middle eigenvalue, the orientation of the valley, the start point and the accuracy of the line search.

Steepest descent

From x go along -g, where g = A x is the gradient, to the exact minimum along that line: α = gTg / gTA g, x ← x - α g. After an exact line search the new gradient is perpendicular to the old one, so the path zig-zags across a narrow valley. The A-norm of the error ‖e‖A = √(eTA e) shrinks at least as fast as ((κ-1)/(κ+1))k (Kantorovich), and exactly at that rate from the worst-case start u = (λ3, 0, λ1) in the eigenbasis, which the checkbox selects.

Conjugate gradient

CG keeps a search direction p with p0 = -g0, step α = gTg / pTA p, then g ← g + α A p, β = gnewTgnew / gTg, p ← -gnew + β p. The directions are A-conjugate, piTA pj = 0, and the gradients are mutually orthogonal. Each step minimises f over the whole growing subspace spanned by all earlier directions, not just along the last line, so in exact arithmetic CG reaches the minimum in at most as many steps as A has distinct eigenvalues (three here, two if two eigenvalues coincide, which the preset "Repeated eigenvalue" uses). In between it obeys the Chebyshev bound ‖ek‖A ≤ 2((√κ-1)/(√κ+1))k ‖e0‖A, which depends on √κ instead of κ. That is why CG is the method of choice for huge linear systems and for the inner loop of Newton-type optimisers.

Reading the pictures

The blue shells are fixed level sets of f; the amber and cyan shells pass through the current iterates of the two methods. The three coloured rods are the eigenvectors of A (the long red one is the flat direction). Arrows show the direction about to be taken: -g for steepest descent, p for CG. The 2D page projects the three-variable problem onto two eigen-directions, and the opacity of each dot encodes its height in the hidden third direction.

Checks run in the page

1. Steepest descent from the worst-case start contracts the A-norm by exactly (κ-1)/(κ+1) per step. 2. CG reduces the gradient by 108 within the number of distinct eigenvalues. 3. The CG directions are A-conjugate and its gradients orthogonal to better than 10-6. 4. The measured error never exceeds the Kantorovich bound (SD) or the Chebyshev bound (CG). The checks always use an exact line search, whatever the accuracy slider says.

Honest simplifications

The problem is a pure quadratic with its minimum at the origin, so the matrix-vector products are exact and cheap; real problems are non-quadratic (nonlinear CG restarts and uses inexact line searches) and in floating point the conjugacy of long CG runs slowly degrades, which is why large solvers add preconditioning. Here the gradient is recomputed as A x at every step instead of by the usual recurrence, so that the line-search accuracy slider stays well defined. When the slider is not 1 the step is only a fraction of the optimal one, conjugacy is lost and CG falls back toward steepest-descent behaviour; this is a model of an inexact line search, not of a particular library. The marbles, shells and rods are a visual encoding of the numbers, not a physical simulation.

Error in the A-norm against step (dashed: theoretical bounds)
Function value f against step
Size of the gradient against step
Gradient along each eigenvector (solid CG, dashed steepest descent)