Conjugate gradient and Krylov optimality
ProofAdvanced⏱ 1 hourAdvanced Optimizationconjugate gradientkrylovfinite termination
Problem
For with :
- Show that CG's -th iterate minimises over the Krylov subspace .
- Deduce that CG terminates in at most steps, where is the number of distinct eigenvalues of .
- Explain why a clustered spectrum makes CG fast even when 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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Newton's method is affine invariant | Advanced Optimization | Proof | 30 min | ||
| Local quadratic convergence of Newton's method | Advanced Optimization | Proof | 1 hour | ||
| The BFGS update satisfies the secant condition | Advanced Optimization | Proof | 30 min | ||
| Acceleration as an optimal polynomial | Advanced Optimization | Proof | 1 hour |