Lemma 4.8, p. 133 — with ρ = 1, the diameter shrinks by a factor φ < 1, depending only on χ and γ, between consecutive contractions
ProvedNelderMeadLD.Rate1D.lemma_4_8Fix and . There is a number , 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 and coefficients to , starting from a nondegenerate ordered initial interval . If iterations are contractions and no iteration strictly between them is a contraction, then the simplex immediately following contraction and the simplex immediately following the next contraction satisfy
This is the per-cycle contraction factor of the move-sequence analysis; Theorem 4.2 follows by chaining these cycles.
Formalization Note. "Depending only on and " is encoded by the quantifier order: is chosen after and before , and . is the simplex at the start of iteration , so the simplex immediately following iteration is .
import Mathlib import Definitions.Def_NelderMeadLD_Conv1D_Algorithm import Definitions.Def_NelderMeadLD_Rate1D_Algorithm
namespace NelderMeadLD.Rate1D
open NelderMeadLD.Conv1D
theorem lemma_4_8 :
∀ χ γ : ℝ, 1 < χ → 0 < γ → γ < 1 →
∃ φ : ℝ, φ < 1 ∧
∀ σ : ℝ, 0 < σ → σ < 1 →
∀ f : ℝ → ℝ, StrictConvexOn ℝ Set.univ f →
(∀ μ : ℝ, Bornology.IsBounded {x | f x ≤ μ}) →
∀ p0 : ℝ × ℝ, IsStart f p0 →
∀ k k' : ℕ, k < k' →
IsContraction (moveAt f χ γ σ p0 k) →
IsContraction (moveAt f χ γ σ p0 k') →
(∀ i : ℕ, k < i → i < k' → ¬ IsContraction (moveAt f χ γ σ p0 i)) →
diam (run f 1 χ γ σ p0 (k' + 1)) ≤ φ * diam (run f 1 χ γ σ p0 (k + 1)) := by sorry
end NelderMeadLD.Rate1D
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.