Lemma 4.6, p. 131 — with ρ = 1: at most r* = ⌈χ − 1⌉ consecutive reflections, and no expansion right after a reflection
ProvedNelderMeadLD.Rate1D.lemma_4_6direct-searchnelder-meadp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strict-convexity
Let be strictly convex with bounded level sets, and apply the one-dimensional Nelder–Mead method with reflection coefficient , expansion coefficient , contraction coefficient and shrink coefficient , starting from a nondegenerate ordered initial interval . Let
Then:
- the number of consecutive reflections is at most : there is no such that iterations are all reflections;
- the iteration immediately following a reflection is never an expansion.
These two facts restrict which move sequences the method can produce in dimension 1 with , and are the first ingredients of the paper's M-step linear convergence result (Theorem 4.2).
Formalization Note. is substituted into the algorithm. The standing conditions (2.1) are carried as a hypothesis; with they reduce to , , . is the natural-number ceiling ⌈χ − 1⌉₊, equal to the paper's value for .
Preamble
import Mathlib import Definitions.Def_NelderMeadLD_Conv1D_Algorithm import Definitions.Def_NelderMeadLD_Rate1D_Algorithm
Formal statement
namespace NelderMeadLD.Rate1D
open NelderMeadLD.Conv1D
theorem lemma_4_6 (χ γ σ : ℝ) (hpar : ParamsOK 1 χ γ σ)
(f : ℝ → ℝ) (hf : StrictConvexOn ℝ Set.univ f)
(hlev : ∀ μ : ℝ, Bornology.IsBounded {x | f x ≤ μ})
(p0 : ℝ × ℝ) (h0 : IsStart f p0) :
(∀ k : ℕ, ¬ ∀ i < rStar χ + 1, moveAt f χ γ σ p0 (k + i) = Move.reflect) ∧
(∀ k : ℕ, moveAt f χ γ σ p0 k = Move.reflect →
moveAt f χ γ σ p0 (k + 1) ≠ Move.expand) := by sorry
end NelderMeadLD.Rate1D
Source
Lagarias, Reeds, Wright & Wright, Convergence properties of the Nelder–Mead simplex method in low dimensions, SIAM J. Optim. 9 (1998), p. 131, Lemma 4.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.