Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.4, p. 197 — with ηₖ = ε = 0, exact CG meets dᵢᵀHdᵢ ≤ 0 unless g is orthogonal to the nonpositive eigenspaces of H

Proved
TruncNewton.NegCurv.theorem_2_4

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

conjugate-gradienteigenspacenegative-curvaturep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1truncated-newton

Let HHH be a symmetric linear operator on Rn\mathbb{R}^nRn (the Hessian H(xk)H(x_k)H(xk​) at a major iterate) and g∈Rng\in\mathbb{R}^ng∈Rn (the gradient g(xk)g(x_k)g(xk​)). Run the TNCG minor iteration (Steps 1–4, p. 194) with ηk=ε=0\eta_k=\varepsilon=0ηk​=ε=0 in (2.1) and (2.2): the curvature test is diTHdi≤0d_i^{\mathsf T}Hd_i\le0diT​Hdi​≤0 and the truncation test is ri+1=0r_{i+1}=0ri+1​=0.

Theorem 2.4. If HHH is not positive definite, then

  1. either the minor iteration reaches some iteration iii (no test fired at any earlier iteration) with
diTHdi≤0,d_i^{\mathsf T}Hd_i\le 0,diT​Hdi​≤0,

i.e. it exits through (2.1) at iii; 2. or ggg is orthogonal to the eigenspaces of HHH corresponding to the nonpositive eigenvalues: gTv=0g^{\mathsf T}v=0gTv=0 whenever Hv=μvHv=\mu vHv=μv with μ≤0\mu\le0μ≤0.

The theorem justifies using the direction of negative curvature did_idi​ to move away from stationary points that are not local minimizers: exact CG detects nonpositive curvature except in the rare case in which ggg has no component along a nonpositive eigenspace.

Formalization Note The page's theorem is about H(xk)H(x_k)H(xk​) and g(xk)g(x_k)g(xk​) at an iterate of the TNCG run, but uses nothing about the objective or the run, and every symmetric HHH and every ggg 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) HHH and vector ggg. The first alternative requires that iteration iii is actually reached (no earlier exit): a bare "diTHdi≤0d_i^{\mathsf T}Hd_i\le0diT​Hdi​≤0 for some iii" over the unstopped recursion would be trivially true after a zero residual, where the recursion continues with d=0d=0d=0. For μ\muμ that is not an eigenvalue only v=0v=0v=0 satisfies Hv=μvHv=\mu vHv=μv, so the second alternative quantifies over all μ≤0\mu\le0μ≤0 without an eigenvalue predicate.

Preamble
import Mathlib
import Definitions.Def_TruncNewton_NegCurv_Setting
Formal statement
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
Source
Dembo and Steihaug, Truncated-Newton algorithms for large-scale unconstrained optimization, Math. Programming 26 (1983), p. 197, Theorem 2.4
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me