Conjugate-gradient convergence
ProvedVectorSpaceOpt.conjugate_gradient_convergesconjugate-gradienthilbert-spacenorm-convergencestop-stutter
Let be a real Hilbert space and let be self-adjoint with constants satisfying
for every . For any right-hand side and initial point , there is a unique solution of , and the iterate component of the guarded conjugate-gradient sequence satisfies
The convergence is in the norm topology of . The sequence performs Luenberger's recurrence while its direction is nonzero and stutters once a zero direction certifies exact solution. This capstone is §10.8, Theorem 1 with all inherited coercivity hypotheses repeated and its undefined post-termination boundary repaired.
Preamble
import Definitions.Def_VectorSpaceOpt_conjugate_gradient open Filter
Formal statement
namespace VectorSpaceOpt
/-- Luenberger, Chapter 10, §10.8, Theorem 1, with total stop/stutter semantics. -/
theorem conjugate_gradient_converges
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(Q : H →L[ℝ] H) (b x₀ : H) (m M : ℝ)
(hm : 0 < m) (hmM : m ≤ M)
(hself : IsRealSelfAdjoint Q) (hbounds : IsCoerciveBetween Q m M) :
∃ xStar : H, Q xStar = b ∧
(∀ y : H, Q y = b → y = xStar) ∧
Tendsto (fun n => (conjugateGradientIterate Q b x₀ n).x) atTop (nhds xStar) := by
sorry
end VectorSpaceOptSource
David G. Luenberger, Optimization by Vector Space Methods (Wiley, 1969), Chapter 10, §10.8, Theorem 1, printed pp. 294–296 (physical PDF pp. 312–314), with explicit stop/stutter semantics at zero direction. Scan: https://sites.science.oregonstate.edu/~show/old/142_Luenberger.pdf