Lemma 4.3, p. 126 — with ρχ ≥ 1 the proximity property (4.4) is preserved from iteration k to k + 1
ProvedNelderMeadLD.Conv1D.lemma_4_3convergencenelder-meadp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strict-convexity
Let be strictly convex with bounded level sets and minimizer . Let the parameters satisfy (2.1) and , and let be the one-dimensional Nelder–Mead run from a nondegenerate, ordered initial interval. Define
and say that the proximity property holds at iteration if
the interval with these endpoints, open at and closed at the other end. Then, if the proximity property holds at iteration , it holds at iteration .
Combined with Lemma 4.2 it shows that, once bracketed, the minimizer stays within a fixed multiple of the current diameter of the best vertex.
Formalization Note The orientation of is independent of the order of the endpoints, as on p. 124 of the paper.
Preamble
import Mathlib import Definitions.Def_NelderMeadLD_Conv1D_Algorithm open Filter Topology
Formal statement
namespace NelderMeadLD.Conv1D
theorem lemma_4_3 (f : ℝ → ℝ) (hf : StrictConvexOn ℝ Set.univ f)
(hlev : ∀ μ : ℝ, Bornology.IsBounded {x | f x ≤ μ})
(xmin : ℝ) (hmin : ∀ y, f xmin ≤ f y)
(ρ χ γ σ : ℝ) (hpar : ParamsOK ρ χ γ σ)
(p0 : ℝ × ℝ) (h0 : IsStart f p0)
(hρχ : 1 ≤ ρ * χ) :
∀ k : ℕ, Proximity ρ χ γ xmin (run f ρ χ γ σ p0 k) →
Proximity ρ χ γ xmin (run f ρ χ γ σ p0 (k + 1)) := by sorry
end NelderMeadLD.Conv1D
Source
Lagarias, Reeds, Wright & Wright, Convergence properties of the Nelder–Mead simplex method in low dimensions, SIAM J. Optim. 9 (1998), p. 126, Lemma 4.3, (4.3), (4.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.