Recipe

Run conjugate gradient descent

Use when: you're minimizing a quadratic f(x)=\tfrac12x^\top Ax-b^\top x (or applying the same update rules to a general nonlinear f) and want directions that never undo an earlier step's progress

Goal: a sequence of iterates that reaches the exact minimizer in at most n steps on a quadratic, using only gradient (residual) evaluations

Taught in Conjugate gradient descent

1. 1

   At the current point x^{(k)}, compute r_k=b-Ax^{(k)}, equivalently r_k=-\nabla f(x^{(k)}). This is the same downhill direction plain gradient descent would use, before any conjugacy correction.

   Example

   For A=\begin{bmatrix}3&1\\1&2\end{bmatrix}, b=(4,3), x^{(0)}=(0,0): r_0=b-Ax^{(0)}=(4,3).

   Why: r_k=\mathbf 0 exactly at the minimizer, so recomputing it each iteration detects convergence and supplies the ingredient every later formula in the cycle uses.

2. 2

   If k=0, there's no earlier direction to correct, so d_0=r_0 directly. Otherwise compute \beta_{k-1}=\dfrac{r_k^\top r_k}{r_{k-1}^\top r_{k-1}} and set d_k=r_k+\beta_{k-1}d_{k-1} — the current residual plus a fraction of the previous direction.

   Example

   \beta_0=\dfrac{r_1^\top r_1}{r_0^\top r_0}\approx\dfrac{0.0772}{25}\approx0.00309; d_1=r_1+\beta_0d_0\approx(-0.1667,0.2222)+0.00309(4,3)\approx(-0.1543,0.2315).

   • k=0, no previous direction exists — set d_0=r_0 and skip the \beta blend.
   • k\ge1, a previous direction d_{k-1} exists — compute \beta_{k-1} from the two residual norms and blend it into d_{k-1}.

   Why: this is exactly what makes d_k A-conjugate to every earlier direction, so the line search along it can't undo progress already banked along d_0,\dots,d_{k-1}.

3. 3

   Set \alpha_k=\dfrac{r_k^\top r_k}{d_k^\top Ad_k} — the exact minimizer along d_k for a quadratic, no bracketing search needed.

   Example

   Ad_0=(15,10), so d_0^\top Ad_0=4(15)+3(10)=90; \alpha_0=\dfrac{25}{90}\approx0.2778.

   Why: this is the closed-form 1D minimizer of the quadratic restricted to the line x^{(k)}+\alpha d_k, found by setting the derivative with respect to \alpha to zero.

4. 4

   Set x^{(k+1)}=x^{(k)}+\alpha_kd_k.

   Example

   x^{(1)}=(0,0)+0.2778(4,3)\approx(1.1111,0.8333).

   Why: this is the actual progress the whole cycle exists to produce — every earlier step this cycle only computed a direction and a distance to move.

5. 5

   Set r_{k+1}=r_k-\alpha_kAd_k. If r_{k+1}\approx\mathbf 0, or n steps have already run on an n-dimensional quadratic, stop — x^{(k+1)} is the exact minimizer. Otherwise increment k and return to Step 1.

   Example

   r_1=r_0-\alpha_0Ad_0\approx(4,3)-0.2778(15,10)\approx(-0.1667,0.2222) — not yet \mathbf 0, so continue.

   Why: for a genuinely quadratic objective this loop is guaranteed to reach the exact minimizer in at most n steps, so checking against n is itself informative, not just a safety net.