Lemma 3.1, p. 120 — nondegeneracy is preserved; vol(Δₖ₊₁) = |τ| vol(Δₖ) after a step of type τ, = σⁿ vol(Δₖ) after a shrink
ProvedNelderMeadLD.Dim2.lemma_3_1nelder-meadp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplex-volume
Let the coefficients satisfy (2.1), let () be arbitrary, and let be a run of Algorithm NM on from a nondegenerate initial simplex . Then
- every simplex is nondegenerate;
- after a nonshrink iteration of type (the coefficient of the accepted point),
- after a shrink iteration, .
In particular a reflection with preserves volume, which the proof of Theorem 5.2 uses.
Formalization Note with the edge matrix (2.10). The type of iteration is tau ρ χ γ (move f ρ χ γ (Δ k)), i.e. , , or ; note that an expansion attempt whose expansion point is rejected accepts and has type .
Preamble
import Mathlib import Definitions.Def_NelderMeadLD_Dim2_Algorithm open Filter Topology
Formal statement
namespace NelderMeadLD.Dim2
theorem lemma_3_1 {n : ℕ} [NeZero n] (f : E n → ℝ) (ρ χ γ σ : ℝ) (hpar : NelderMeadLD.Conv1D.ParamsOK ρ χ γ σ)
(Δ : ℕ → Fin (n + 1) → E n) (hrun : IsNMRun f ρ χ γ σ Δ) (hnd : Nondegenerate (Δ 0)) :
(∀ k, Nondegenerate (Δ k)) ∧
(∀ k, ¬ IsShrinkAt f ρ χ γ Δ k →
vol (Δ (k + 1)) = |tau ρ χ γ (move f ρ χ γ (Δ k))| * vol (Δ k)) ∧
(∀ k, IsShrinkAt f ρ χ γ Δ k → vol (Δ (k + 1)) = σ ^ n * vol (Δ 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. 120, Lemma 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.