Skip to content
nonconvexcard

Conjugate gradient and Krylov optimality

ProofAdvanced⏱ 1 hourAdvanced Optimizationconjugate gradientkrylovfinite termination

Problem

For f(x)=12x⊤Ax−b⊤xf(x)=\tfrac12x^\top Ax - b^\top x with A≻0A\succ0:

  1. Show that CG's tt-th iterate minimises ff over the Krylov subspace x0+Kt=x0+span⁡{r0,Ar0,…,At−1r0}x_0 + \mathcal K_t = x_0 + \operatorname{span}\{r_0,Ar_0,\dots,A^{t-1}r_0\}.
  2. Deduce that CG terminates in at most mm steps, where mm is the number of distinct eigenvalues of AA.
  3. Explain why a clustered spectrum makes CG fast even when κ\kappa is large.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Newton's method is affine invariantAdvanced OptimizationProofIntermediate30 min
Local quadratic convergence of Newton's methodAdvanced OptimizationProofAdvanced1 hour
The BFGS update satisfies the secant conditionAdvanced OptimizationProofAdvanced30 min
Acceleration as an optimal polynomialAdvanced OptimizationProofGraduate1 hour