Theorem 2.4, p. 197 — with ηₖ = ε = 0, exact CG meets dᵢᵀHdᵢ ≤ 0 unless g is orthogonal to the nonpositive eigenspaces of H
ProvedTruncNewton.NegCurv.theorem_2_4Let be a symmetric linear operator on (the Hessian at a major iterate) and (the gradient ). Run the TNCG minor iteration (Steps 1–4, p. 194) with in (2.1) and (2.2): the curvature test is and the truncation test is .
Theorem 2.4. If is not positive definite, then
- either the minor iteration reaches some iteration (no test fired at any earlier iteration) with
i.e. it exits through (2.1) at ; 2. or is orthogonal to the eigenspaces of corresponding to the nonpositive eigenvalues: whenever with .
The theorem justifies using the direction of negative curvature to move away from stationary points that are not local minimizers: exact CG detects nonpositive curvature except in the rare case in which has no component along a nonpositive eigenspace.
Formalization Note The page's theorem is about and at an iterate of the TNCG run, but uses nothing about the objective or the run, and every symmetric and every occur as Hessian and gradient at a point of an admissible objective (a quadratic, modified far away so that its level sets are bounded). The statement is therefore made for an arbitrary symmetric (self-adjoint) and vector . The first alternative requires that iteration is actually reached (no earlier exit): a bare " for some " over the unstopped recursion would be trivially true after a zero residual, where the recursion continues with . For that is not an eigenvalue only satisfies , so the second alternative quantifies over all without an eigenvalue predicate.
import Mathlib import Definitions.Def_TruncNewton_NegCurv_Setting
namespace TruncNewton.NegCurv
theorem theorem_2_4 {n : ℕ}
(H : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hH : IsSelfAdjoint H)
(g : EuclideanSpace ℝ (Fin n))
(hnpd : ¬ ∀ v, v ≠ 0 → 0 < inner ℝ v (H v)) :
(∃ i, ExitsVia21 H g 0 0 i) ∨
(∀ μ : ℝ, μ ≤ 0 → ∀ v, H v = μ • v → inner ℝ g v = 0) := by sorry
end TruncNewton.NegCurv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.