Convergence along complete conjugate directions
ProvedVectorSpaceOpt.conjugate_directions_convergeconjugate-directionsconvergencedense-spanorthogonality
Let Q be self-adjoint and coercively bounded on a real Hilbert space, and let xStar solve Q xStar = b. Suppose p n is a sequence of nonzero, pairwise Q-orthogonal directions whose closed linear span is the whole space. Define residuals r n = b - Q (x n) and take each next iterate by exact minimization along p n, using the displayed scalar ratio in §10.6. Then
This is Luenberger's method-of-conjugate-directions theorem. Explicit nonzeroness prevents hidden zero denominators, while density is the completeness hypothesis that converts all finite orthogonality relations into norm convergence.
Preamble
import Definitions.Def_VectorSpaceOpt_conjugate_gradient open Filter Set open scoped RealInnerProductSpace
Formal statement
namespace VectorSpaceOpt
/-- Luenberger, Chapter 10, §10.6, Theorem 1. -/
theorem conjugate_directions_converge
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(Q : H →L[ℝ] H) (b xStar : H) (m M : ℝ) (hm : 0 < m)
(hself : IsRealSelfAdjoint Q) (hbounds : IsCoerciveBetween Q m M)
(hxStar : Q xStar = b) (p x r : ℕ → H)
(hpne : ∀ n, p n ≠ 0)
(hconj : ∀ i j, i ≠ j → ⟪p i, Q (p j)⟫ = 0)
(hdense : closure ((Submodule.span ℝ (Set.range p) : Submodule ℝ H) : Set H) = Set.univ)
(hres : ∀ n, r n = b - Q (x n))
(hstep : ∀ n,
x (n + 1) = x n + (⟪p n, r n⟫ / ⟪p n, Q (p n)⟫) • p n) :
(∀ n k, k < n → ⟪r n, p k⟫ = 0) ∧ Tendsto x atTop (nhds xStar) := by
sorry
end VectorSpaceOptSource
David G. Luenberger, Optimization by Vector Space Methods (Wiley, 1969), Chapter 10, §10.6, Theorem 1, printed pp. 291–292 (physical PDF pp. 309–310). Scan: https://sites.science.oregonstate.edu/~show/old/142_Luenberger.pdf