Theorem 4.2, p. 130 — in dimension 1 with ρ = 1, diam(Δ_{k+M}) ≤ ½ diam(Δ_k) for all k ≥ K, M depending only on χ and γ
ProvedNelderMeadLD.Rate1D.theorem_4_2Fix an expansion coefficient and a contraction coefficient . There is an integer , depending only on and , with the following property.
Let , let be strictly convex with bounded level sets, and apply the one-dimensional Nelder–Mead method with reflection coefficient and coefficients to , starting from a nondegenerate ordered initial interval . Then the iteration index of Lemma 4.2 exists — that is, there is a first iteration with — and
Here is the interval at iteration , , and is the value of at the expansion point . The theorem says that, once the minimizer is bracketed, the Nelder–Mead interval converges M-step linearly, with a step count that does not depend on or on the initial interval.
Formalization Note. " depending only on and " is encoded by the quantifier order: is chosen after and before , and . The page presupposes the index of Lemma 4.2; here its existence is part of the conclusion, so the statement cannot hold vacuously for a run that is never bracketed. This makes the item slightly stronger than the printed sentence (the existence is Lemma 4.2, proved in the paper). The shrink coefficient is a parameter of the algorithm and satisfies (2.1); it does not otherwise enter.
import Mathlib import Definitions.Def_NelderMeadLD_Conv1D_Algorithm import Definitions.Def_NelderMeadLD_Rate1D_Algorithm
namespace NelderMeadLD.Rate1D
open NelderMeadLD.Conv1D
theorem theorem_4_2 :
∀ χ γ : ℝ, 1 < χ → 0 < γ → γ < 1 →
∃ M : ℕ,
∀ σ : ℝ, 0 < σ → σ < 1 →
∀ f : ℝ → ℝ, StrictConvexOn ℝ Set.univ f →
(∀ μ : ℝ, Bornology.IsBounded {x | f x ≤ μ}) →
∀ p0 : ℝ × ℝ, IsStart f p0 →
∃ K : ℕ, FirstBracket f χ γ σ p0 K ∧
∀ k : ℕ, K ≤ k →
diam (run f 1 χ γ σ p0 (k + M)) ≤ 1 / 2 * diam (run f 1 χ γ σ p0 k) := by sorry
end NelderMeadLD.Rate1D
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.