The Conjugate Gradient Method

Gradient descent on a long, narrow valley zig-zags badly: each step points straight downhill from where you stand, but on an elongated bowl "straight downhill" keeps overcorrecting side to side instead of heading toward the true minimum, so progress is painfully slow. You could fix this with Newton's method, which uses full curvature information, but that requires an expensive Hessian. The conjugate gradient method finds a middle ground: it never computes the Hessian, yet it avoids the zig-zag by being smarter about which direction to search next.

An analogy: not retracing your steps

Imagine hiking down a long, narrow ravine by always choosing the current steepest-downhill direction. You'll swing back and forth across the ravine's width, wasting most of your motion correcting a mistake you just made, rather than progressing along its length. A smarter hiker remembers the direction of her last few moves and deliberately chooses each new direction so it doesn't undo the progress those earlier moves already made along the ravine's length — she never has to "re-fix" the same component of her position twice. That's the core idea of conjugacy: each new search direction is chosen to be independent, in a precise mathematical sense, of the directions already used.

The method, one symbol at a time

For a quadratic function $f(x) = \tfrac{1}{2} x^T A x - b^T x$ (where $A$ is a symmetric positive-definite matrix describing curvature), the method builds a sequence of search directions $d_0, d_1, d_2, \dots$ that are $A$-conjugate, meaning $d_i^T A \, d_j = 0$ for $i \neq j$. In plain English, this is a generalized notion of "at right angles" adapted to the shape of the bowl $A$ describes, rather than plain geometric right angles. At each step the algorithm moves along the current direction $d_k$ by the exact optimal amount, then picks the next direction $d_{k+1}$ by combining the new gradient with the previous direction:

$$d_{k+1} = -\nabla f(x_{k+1}) + \beta_k \, d_k ,$$

where $\beta_k$ is a scalar chosen (by one of a few standard formulas) to enforce conjugacy with $d_k$. In words: move in the steepest-descent direction, but corrected by a fraction of the previous direction so as not to disturb the progress that direction already made. The remarkable result: for an $n$-dimensional quadratic problem, this process finds the exact minimum in at most $n$ steps — a hard guarantee gradient descent never gives.

Worked example 1: a simple two-dimensional quadratic

Minimize $f(x,y) = x^2 + 10y^2$ (a narrow elongated bowl, since $y$ is penalized ten times more steeply), starting at $(x_0, y_0) = (10, 1)$. Plain gradient descent zig-zags across the narrow $y$-direction for dozens of iterations. Conjugate gradient, in contrast, is guaranteed to find the exact minimum $(0,0)$ in at most 2 steps, since this is a 2-dimensional quadratic problem — its first step moves in the steepest direction, and its second step, chosen to be $A$-conjugate to the first, lands exactly on the minimum rather than merely getting closer.

Worked example 2: solving a linear system via CG

Conjugate gradient is also the standard way to solve large sparse linear systems $Ax = b$, since solving $Ax=b$ is equivalent to minimizing $f(x) = \tfrac{1}{2}x^TAx - b^Tx$. Suppose $A = \begin{pmatrix} 4 & 1 \\ 1 & 3 \end{pmatrix}$ and $b = (1, 2)$, starting at $x_0 = (0,0)$. The initial gradient (residual) is $r_0 = b - Ax_0 = (1, 2)$, so the first direction is $d_0 = (1,2)$. Stepping optimally along $d_0$ and then computing a conjugate second direction $d_1$ takes the solver to the exact solution $x^\star = (1/11, 7/11) \approx (0.091, 0.636)$ in exactly 2 steps, matching the theoretical guarantee for a 2×2 system — no matrix inversion was ever performed, only matrix-vector products, which is why CG scales to problems with millions of variables where forming $A^{-1}$ directly would be infeasible.

Try a narrow, elongated bowl and compare the zig-zagging steepest-descent path against a conjugate-direction path: watch how the conjugate path corrects course only once and lands exactly on the minimum instead of oscillating.

What this means in practice

Conjugate gradient is the workhorse for large-scale quadratic and near-quadratic problems: solving covariance-weighted least-squares in portfolio optimization, large sparse linear systems from PDE-based pricing grids, and as an inner solver inside more complex optimizers. Its appeal is that it needs no Hessian, no matrix inversion, and only a handful of vector operations per step, yet it inherits much of Newton's finite-step guarantee for quadratic problems.