Conjugate Gradient Method

Optimization · Axiom Academy

LESSON Conjugate Gradient Method An efficient algorithm for solving quadratic optimization problems that converges in n steps without zig-zagging Two vectors p and q are A-conjugate (or conjugate with respect to matrix A) if they satisfy: This means the vectors are orthogonal in the inner product space defined by A. For a quadratic function f(x) = (1/2)x T Ax - b T x, searching along A-conjugate directions ensures that minimizing in one direction doesn't interfere with the minimization achieved in previous directions. 2. Why Steepest Descent Zig-Zags Steepest descent moves in the direction of the negative gradient -∇f(x) = b - Ax, which is the direction of steepest decrease. However, consecutive gradient directions are orthogonal to each other, causing the algorithm to zig-zag back and forth. The Conjugate Gradient method avoids this by choosing directions that are A-conjugate rather than merely orthogonal. This ensures we never revisit the same subspace twice. 3. The Conjugate Gradient Update The CG algorithm builds A-conjugate search directions iteratively. Starting with the initial gradient direction p 0 = r 0 = b - Ax 0 , each new direction is constructed by adding a correction to the current residual: The coefficient β k is chosen to ensure A-conjugacy: p k+1 T Ap k = 0. The most common formula is the Fletcher-Reeves form: Initialize: x 0 , compute r 0 = b - Ax 0 , set p 0 = r 0 Step size: α k = (r k T r k ) / (p k T Ap k ) New residual: r k+1 = r k - α k Ap k

This is the written version of the interactive lesson above. See the full Optimization course.