Total conjugate-gradient iteration
DefinitionVectorSpaceOpt_conjugate_gradientconjugate-gradientdefinitionguarded-recursionhilbert-space
For a real inner-product space, IsRealSelfAdjoint Q expresses symmetry of a continuous linear operator, and IsCoerciveBetween Q m M records its lower and upper quadratic bounds. A conjugate-gradient state stores an iterate x, residual r, and direction p. Starting from r₀ = p₀ = b - Q x₀, an active step uses
If p = 0, the state is returned unchanged. Thus conjugateGradientIterate is a total natural-number sequence with explicit exact-termination semantics, and conjugateGradientEnergy records the quadratic error energy used in convergence. The stop/stutter convention is essential for auditing every later denominator.
Definition code
import Mathlib
open Filter Set
open scoped RealInnerProductSpace
namespace VectorSpaceOpt
/-- A real continuous linear operator is self-adjoint when it can be moved across the inner product. -/
def IsRealSelfAdjoint
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
(Q : H →L[ℝ] H) : Prop :=
∀ x y : H, ⟪Q x, y⟫ = ⟪x, Q y⟫
/-- The lower and upper quadratic bounds used throughout §§10.5–10.8. -/
def IsCoerciveBetween
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
(Q : H →L[ℝ] H) (m M : ℝ) : Prop :=
∀ x : H, m * ‖x‖ ^ 2 ≤ ⟪x, Q x⟫ ∧ ⟪x, Q x⟫ ≤ M * ‖x‖ ^ 2
/-- The three vectors carried by one conjugate-gradient iteration. -/
structure ConjugateGradientState (H : Type*) where
x : H
r : H
p : H
/-- One conjugate-gradient step, explicitly stuttering after `p = 0`. -/
noncomputable def conjugateGradientStep
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
(Q : H →L[ℝ] H) (b : H) (s : ConjugateGradientState H) :
ConjugateGradientState H :=
letI := Classical.decEq H
if s.p = 0 then s
else
let alpha : ℝ := ⟪s.r, s.p⟫ / ⟪s.p, Q s.p⟫
let xNext : H := s.x + alpha • s.p
let rNext : H := b - Q xNext
let beta : ℝ := ⟪rNext, Q s.p⟫ / ⟪s.p, Q s.p⟫
{ x := xNext, r := rNext, p := rNext - beta • s.p }
/-- The total conjugate-gradient sequence, with initial direction equal to the initial residual. -/
noncomputable def conjugateGradientIterate
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
(Q : H →L[ℝ] H) (b x₀ : H) (n : ℕ) : ConjugateGradientState H :=
(conjugateGradientStep Q b)^[n]
{ x := x₀, r := b - Q x₀, p := b - Q x₀ }
/-- The quadratic error energy used in the convergence proof. -/
def conjugateGradientEnergy
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
(Q : H →L[ℝ] H) (xStar x : H) : ℝ :=
⟪x - xStar, Q (x - xStar)⟫
end VectorSpaceOptSource
David G. Luenberger, Optimization by Vector Space Methods (Wiley, 1969), Chapter 10, §10.6 and §10.8, definitions and recurrences, printed pp. 290–295 (physical PDF pp. 308–313), with explicit stop/stutter added at the omitted zero-direction boundary. Scan: https://sites.science.oregonstate.edu/~show/old/142_Luenberger.pdf