Conjugacy of active CG directions
ProvedVectorSpaceOpt.cg_directions_conjugate_until_stopconjugate-gradientinvariantpre-terminationq-orthogonality
Run the total conjugate-gradient iteration for a self-adjoint operator with a positive coercivity bound. Fix an index n and assume every stored direction through step n is nonzero, so the run has not yet entered its stuttering state. Then any two distinct active directions with indices i < j ≤ n are orthogonal in the Q inner product:
This is the central invariant established in the first half of §10.8, Theorem 1. Its premise makes the algorithm's termination boundary explicit. The result can feed the general conjugate-directions theorem or be reused directly to establish residual orthogonality and finite-dimensional exact termination.
Preamble
import Definitions.Def_VectorSpaceOpt_conjugate_gradient open scoped RealInnerProductSpace
Formal statement
namespace VectorSpaceOpt
/-- The conjugacy invariant proved in §10.8 before the convergence estimate. -/
theorem cg_directions_conjugate_until_stop
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
(Q : H →L[ℝ] H) (b x₀ : H) (m M : ℝ) (hm : 0 < m)
(hself : IsRealSelfAdjoint Q) (hbounds : IsCoerciveBetween Q m M) :
∀ n : ℕ,
(∀ k ≤ n, (conjugateGradientIterate Q b x₀ k).p ≠ 0) →
∀ i j, i < j → j ≤ n →
⟪(conjugateGradientIterate Q b x₀ i).p,
Q ((conjugateGradientIterate Q b x₀ j).p)⟫ = 0 := by
sorry
end VectorSpaceOptSource
David G. Luenberger, Optimization by Vector Space Methods (Wiley, 1969), Chapter 10, §10.8, proof of Theorem 1, printed p. 295 (physical PDF p. 313), restricted explicitly to pre-termination iterates. Scan: https://sites.science.oregonstate.edu/~show/old/142_Luenberger.pdf