§2.1, (2.3), p. 3 — α(ε) = min_{x∈𝒮∖𝒮^ε} g(x) − v* − ε > 0
ProvedKleywegtSAA.ExpRate.alpha_posp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximationwell-conditioning
Let be a nonempty finite set, any function, , and . Let and suppose is nonempty. Then
The number measures how well the -optimal solutions are separated from the rest; it is the margin that the sample average must resolve.
Formalization Note The statement holds for any real function on , so it is stated without probability. When the paper's is a minimum over the empty set and is undefined; the nonemptiness of is therefore a hypothesis.
Preamble
import Mathlib import Definitions.Def_KleywegtSAA_ExpRate_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace KleywegtSAA.ExpRate
/-- (2.3), p. 3: for `ε ≥ 0`, if `S \ S^ε` is nonempty then
`α(ε) = min_{x ∈ S \ S^ε} g(x) − v* − ε > 0`. Stated for an arbitrary real function `g` on `S`. -/
theorem alpha_pos {X : Type*} (S : Finset X) (hS : S.Nonempty) (g : X → ℝ)
(ε : ℝ) (hε : 0 ≤ ε) (hne : (nonOptSet S hS g ε).Nonempty) :
0 < alpha S hS g ε hne := by sorry
end KleywegtSAA.ExpRate
Source
Kleywegt & Shapiro, The sample average approximation method for stochastic discrete optimization, preprint (two-author version, sha256 56657748…), p. 3, (2.3) and the sentence after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.