Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.6, p. 123 — strictly convex, bounded below, ργ < 1: f*ₙ = f*ₙ₊₁, and (n ≥ 2) xₙ changes infinitely often

Proved
NelderMeadLD.Dim2.lemma_3_6

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

convergencenelder-meadp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strict-convexity

Let f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R (n≥1n\ge1n≥1) be strictly convex and bounded below, let the coefficients satisfy (2.1) and in addition

ργ<1,\rho\gamma<1,ργ<1,

and let (Δk)(\Delta_k)(Δk​) be a run of Algorithm NM on fff from a nondegenerate initial simplex. Then

  1. the next-worst and worst vertex values have a common limit: fn∗=fn+1∗f_n^*=f_{n+1}^*fn∗​=fn+1∗​;
  2. if n≥2n\ge2n≥2, there are infinitely many iterations kkk with xn(k+1)≠xn(k)x_n^{(k+1)}\ne x_n^{(k)}xn(k+1)​=xn(k)​.

The lemma is the input to Lemma 5.1, where it guarantees that the next-worst vertex of a triangle keeps moving.

Formalization Note xnx_nxn​ is 0-based index n−1n-1n−1 (nextWorst n), xn+1x_{n+1}xn+1​ is Fin.last n. Part 1 asserts the existence of a common limit LLL of fn(k)f_n^{(k)}fn(k)​ and fn+1(k)f_{n+1}^{(k)}fn+1(k)​. The paper's statement does not name the start; its proof uses Lemma 3.4, which assumes a nondegenerate start, so that hypothesis is kept. Part 2 is restricted to n≥2n\ge2n≥2: for n=1n=1n=1 the next-worst vertex is the best vertex, and the printed claim is false (take f(x)=x2f(x)=x^2f(x)=x2, ρ=1\rho=1ρ=1, γ=12\gamma=\tfrac12γ=21​, start (0,1)(0,1)(0,1): every iteration is an accepted inside contraction and x1(k)=0x_1^{(k)}=0x1(k)​=0 for all kkk); the proof's contradiction uses the strict inequality f(xˉ)<f(xn)f(\bar x)<f(x_n)f(xˉ)<f(xn​), which the paper notes holds only for n>1n>1n>1. The paper applies the lemma with n=2n=2n=2.

Preamble
import Mathlib
import Definitions.Def_NelderMeadLD_Dim2_Algorithm
open Filter Topology
Formal statement
namespace NelderMeadLD.Dim2

theorem lemma_3_6 {n : ℕ} [NeZero n] (f : E n → ℝ) (ρ χ γ σ : ℝ) (hpar : NelderMeadLD.Conv1D.ParamsOK ρ χ γ σ)
    (Δ : ℕ → Fin (n + 1) → E n) (hrun : IsNMRun f ρ χ γ σ Δ) (hnd : Nondegenerate (Δ 0))
    (hf : StrictConvexOn ℝ Set.univ f) (hbdd : BddBelow (Set.range f)) (hργ : ρ * γ < 1) :
    (∃ L : ℝ, Tendsto (fun k => f (Δ k (nextWorst n))) atTop (𝓝 L) ∧
      Tendsto (fun k => f (Δ k (Fin.last n))) atTop (𝓝 L)) ∧
    (2 ≤ n → ∀ N : ℕ, ∃ k ≥ N, Δ (k + 1) (nextWorst n) ≠ Δ k (nextWorst n)) := by sorry

end NelderMeadLD.Dim2
Source
Lagarias, Reeds, Wright & Wright, Convergence properties of the Nelder–Mead simplex method in low dimensions, SIAM J. Optim. 9 (1998), p. 123, Lemma 3.6
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