Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.2 — with Property (*), more than half of the steps in some block of Δ iterates exceed λ, beyond every index

Proved
NonlinCG.PropStar.lemma_4_2

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

conjugate-gradientnonlinear-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let fff satisfy Assumptions 2.1 at the starting point x1x_1x1​ and let (xk,dk,βk,αk)(x_k, d_k, \beta_k, \alpha_k)(xk​,dk​,βk​,αk​) be a run of the conjugate gradient iteration (1.2)–(1.3) with a line search such that

  1. all iterates stay in the level set: xk∈Lx_k \in \mathcal Lxk​∈L for all k≥1k \ge 1k≥1 (4.4);
  2. the Zoutendijk condition (2.7) holds;
  3. the sufficient descent condition ⟨gk,dk⟩≤−σ3∥gk∥2\langle g_k, d_k\rangle \le -\sigma_3\|g_k\|^2⟨gk​,dk​⟩≤−σ3​∥gk​∥2 holds for all k≥1k \ge 1k≥1 (4.1), with 0<σ3≤10 < \sigma_3 \le 10<σ3​≤1.

Assume the method has Property (*), and that ∥gk∥≥γ>0\|g_k\| \ge \gamma > 0∥gk​∥≥γ>0 for all k≥1k \ge 1k≥1 (4.3). Then there exists λ>0\lambda > 0λ>0 such that for every Δ∈N∗\Delta \in \mathbb N^*Δ∈N∗ and every index k0k_0k0​ there is an index k≥k0k \ge k_0k≥k0​ with

∣Kk,Δλ∣>Δ2,|\mathcal K^\lambda_{k,\Delta}| > \frac{\Delta}{2},∣Kk,Δλ​∣>2Δ​,

where Kk,Δλ\mathcal K^\lambda_{k,\Delta}Kk,Δλ​ is the set of indices iii with k≤i≤k+Δ−1k \le i \le k+\Delta-1k≤i≤k+Δ−1, i≥2i \ge 2i≥2 and ∥si−1∥=∥xi−xi−1∥>λ\|s_{i-1}\| = \|x_i - x_{i-1}\| > \lambda∥si−1​∥=∥xi​−xi−1​∥>λ.

In words: beyond any point, some block of Δ\DeltaΔ consecutive iterates contains more than Δ/2\Delta/2Δ/2 steps longer than λ\lambdaλ, and λ\lambdaλ does not depend on Δ\DeltaΔ. This is the second ingredient of the proof of Theorem 4.3. No sign condition on βk\beta_kβk​ is assumed. As with Lemma 4.1, the hypotheses are steps of a proof by contradiction and may be unsatisfiable on every actual run.

Formalization Note Global continuous differentiability of fff (the paper's "fff is smooth", (1.1)) is assumed in addition to Assumptions 2.1. ∣Kk,Δλ∣>Δ/2|\mathcal K^\lambda_{k,\Delta}| > \Delta/2∣Kk,Δλ​∣>Δ/2 is written in natural numbers as Δ<2∣Kk,Δλ∣\Delta < 2|\mathcal K^\lambda_{k,\Delta}|Δ<2∣Kk,Δλ​∣. The quantifier order is the paper's: λ\lambdaλ is chosen first, then Δ\DeltaΔ and k0k_0k0​ are arbitrary.

Preamble
import Mathlib
import Definitions.Def_NonlinCG_PropStar_Setting
Formal statement
namespace NonlinCG.PropStar

/-- Lemma 4.2 (p. 14). Under Assumptions 2.1, for a run of (1.2)–(1.3) with a line search
satisfying (4.4), the Zoutendijk condition (2.7) and the sufficient descent condition (4.1), with
Property (*), and with (4.3), there is `λ > 0` such that for every `Δ ≥ 1` and every index `k₀`
some `k ≥ k₀` has `|𝒦^λ_{k,Δ}| > Δ/2`. No sign condition on `β_k` is assumed. -/
theorem lemma_4_2 {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
    [FiniteDimensional ℝ E]
    (f : E → ℝ) (hf : ContDiff ℝ 1 f) (β α : ℕ → ℝ) (x d : ℕ → E) (σ₃ : ℝ)
    (hA : NonlinCG.FRBound.Assumptions21 f (x 1)) (hrun : NonlinCG.FRBound.IsCGRun f β α x d)
    (hL : ∀ k ≥ 1, x k ∈ NonlinCG.FRBound.levelSet f (x 1))
    (hZ : NonlinCG.FRBound.ZoutendijkCondition f x d)
    (hσ₃ : 0 < σ₃ ∧ σ₃ ≤ 1) (hD : SufficientDescent f σ₃ x d)
    (hP : PropertyStar f β x)
    (h43 : ∃ γ > 0, ∀ k ≥ 1, γ ≤ ‖NonlinCG.FRBound.g f x k‖) :
    ∃ lam > 0, ∀ Δ : ℕ, 1 ≤ Δ → ∀ k₀ : ℕ, ∃ k ≥ k₀, Δ < 2 * (Kset lam x k Δ).card := by sorry

end NonlinCG.PropStar
Source
Gilbert & Nocedal, Global convergence properties of conjugate gradient methods for optimization, INRIA Rapport de Recherche 1268 (June 1990), HAL inria-00075291v1, p. 14, Lemma 4.2; 𝒦^λ_{k,Δ} on p. 14; (4.4) on p. 11
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