Lemma 3.3, p. 121 — f bounded below: f₁ converges; nonshrink steps decrease values; limits f*ᵢ exist and are ordered after the last shrink; vertices converge if only shrinks
ProvedNelderMeadLD.Dim2.lemma_3_3Let () be bounded below, let the coefficients satisfy (2.1), and let be a run of Algorithm NM on from a nondegenerate initial simplex . Write . Then:
- the sequence converges;
- at every nonshrink iteration ,
with strict inequality for at least one ; 3. if no shrink occurs from iteration on, then there are numbers such that (i) for every , (ii) for every and every , and (iii) ; 4. if every iteration from on is a shrink, then all vertices converge to one common point.
These are the basic monotonicity and convergence facts on which the analysis of limiting vertex values rests.
Formalization Note "Finitely many shrink (resp. nonshrink) iterations" is written as the existence of after which none occurs. Part 3(ii) is printed "for all "; it is false when a shrink precedes , because a shrink can raise vertex values. A counterexample with , , : , , , otherwise, start ; iteration 0 shrinks to and afterwards . The statement therefore asserts (ii) for , which is what the later proofs use. Vertex is 0-based index .
import Mathlib import Definitions.Def_NelderMeadLD_Dim2_Algorithm open Filter Topology
namespace NelderMeadLD.Dim2
theorem lemma_3_3 {n : ℕ} [NeZero n] (f : E n → ℝ) (ρ χ γ σ : ℝ) (hpar : NelderMeadLD.Conv1D.ParamsOK ρ χ γ σ)
(Δ : ℕ → Fin (n + 1) → E n) (hrun : IsNMRun f ρ χ γ σ Δ) (hnd : Nondegenerate (Δ 0))
(hbdd : BddBelow (Set.range f)) :
(∃ L : ℝ, Tendsto (fun k => f (Δ k 0)) atTop (𝓝 L)) ∧
(∀ k, ¬ IsShrinkAt f ρ χ γ Δ k →
(∀ i, f (Δ (k + 1) i) ≤ f (Δ k i)) ∧ ∃ i, f (Δ (k + 1) i) < f (Δ k i)) ∧
(∀ K₀ : ℕ, (∀ k ≥ K₀, ¬ IsShrinkAt f ρ χ γ Δ k) →
∃ fstar : Fin (n + 1) → ℝ,
(∀ i, Tendsto (fun k => f (Δ k i)) atTop (𝓝 (fstar i))) ∧
(∀ i, ∀ k ≥ K₀, fstar i ≤ f (Δ k i)) ∧
Monotone fstar) ∧
(∀ K₀ : ℕ, (∀ k ≥ K₀, IsShrinkAt f ρ χ γ Δ k) →
∃ p : E n, ∀ i, Tendsto (fun k => Δ k i) atTop (𝓝 p)) := by sorry
end NelderMeadLD.Dim2
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.