Proof of Theorem 2.4, p. 211 — if g meets every eigenspace of H and exact CG ends with r = 0, then H is positive definite
ProvedTruncNewton.NegCurv.pd_of_cg_residual_zeroLet be a symmetric linear operator on and , and run the TNCG minor iteration (Steps 1–4, p. 194) with , producing directions and residuals . Suppose that is not orthogonal to any eigenspace of , i.e. for every eigenvalue of there is with and . Suppose further that for some the curvature test (2.1) with passes at every iteration up to ,
and that the iteration then ends with zero residual, (the test (2.2) with ). Then is positive definite:
This is the first sentence of the proof of Theorem 2.4, obtained there from Theorem A.5 together with (A.2) and (A.5); it says that exact CG can only end with at a non-convex point when misses some eigenspace.
Formalization Note "" is encoded as after CG steps whose curvature was positive at every step, which is exactly the exit through (2.2) with at iteration . symmetric is the paper's standing setting ( is a Hessian).
import Mathlib import Definitions.Def_TruncNewton_NegCurv_Setting
namespace TruncNewton.NegCurv
theorem pd_of_cg_residual_zero {n : ℕ}
(H : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hH : IsSelfAdjoint H)
(g : EuclideanSpace ℝ (Fin n))
(hg : ∀ μ : ℝ, (∃ v, v ≠ 0 ∧ H v = μ • v) → ∃ v, H v = μ • v ∧ inner ℝ g v ≠ 0)
(i : ℕ) (hcurv : ∀ j ≤ i, 0 < inner ℝ ((cg H g j).d) (H (cg H g j).d))
(hr : (cg H g (i + 1)).r = 0) :
∀ v, v ≠ 0 → 0 < inner ℝ v (H v) := by sorry
end TruncNewton.NegCurv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.