Lemma 4.1, pp. 124–125 — strictly convex f on ℝ: up–down–up brackets x_min; f increases beyond x_min; f continuous
ProvedNelderMeadLD.Conv1D.lemma_4_1nelder-meadp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strict-convexity
Let be strictly convex, and let be a minimizer of (necessarily unique). For reals write for the open interval with endpoints and and for the closed one, whichever endpoint is larger.
- If are three distinct points with , then
- If and , then for all ,
- is continuous.
The first part says that an "up–down–up" pattern of values brackets the minimizer; the second that strictly increases along the ray leaving the minimizer's side of . Both are used repeatedly in the one-dimensional analysis of the Nelder–Mead method.
Formalization Note Part 2 adds : at both points coincide and the strict inequality fails; the page's presupposes two endpoints. The page's lemma does not use bounded level sets, and none is assumed; the minimizer is a hypothesis, as in the lemma.
Preamble
import Mathlib import Definitions.Def_NelderMeadLD_Conv1D_Algorithm open Filter Topology
Formal statement
namespace NelderMeadLD.Conv1D
theorem lemma_4_1 (f : ℝ → ℝ) (hf : StrictConvexOn ℝ Set.univ f)
(xmin : ℝ) (hmin : ∀ y, f xmin ≤ f y) :
(∀ y1 y2 y3 : ℝ, y1 ≠ y2 → y2 ≠ y3 → y1 ≠ y3 →
min y1 y3 < y2 → y2 < max y1 y3 → f y2 ≤ f y1 → f y2 ≤ f y3 →
min y1 y3 < xmin ∧ xmin < max y1 y3) ∧
(∀ y1 y2 : ℝ, y1 ≠ y2 → xmin ∈ Set.uIcc y1 y2 →
∀ ξ1 ξ2 : ℝ, 1 ≤ ξ1 → ξ1 < ξ2 →
f (y2 + ξ1 * (y1 - y2)) < f (y2 + ξ2 * (y1 - y2))) ∧
Continuous f := 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), pp. 124–125, Lemma 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.