Lemma 3.5, p. 122 — on a strictly convex function Algorithm NM never shrinks
ProvedNelderMeadLD.Dim2.lemma_3_5nelder-meadp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strict-convexity
Let () be strictly convex, i.e. for and (Definition 3.1). Let the coefficients satisfy (2.1) and let be a run of Algorithm NM on from a nondegenerate initial simplex . Then
This is why the shrink coefficient plays no role in the analysis of strictly convex functions.
Formalization Note Strict convexity is StrictConvexOn ℝ Set.univ f. A shrink at iteration means that the case analysis of steps 2–4 applied to ends in step 5.
Preamble
import Mathlib import Definitions.Def_NelderMeadLD_Dim2_Algorithm open Filter Topology
Formal statement
namespace NelderMeadLD.Dim2
theorem lemma_3_5 {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) :
∀ k, ¬ IsShrinkAt f ρ χ γ Δ k := 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. 122, Lemma 3.5 (Definition 3.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.