§2.2, p. 5 — √N[min_{x∈𝒮*} ĝ_N(x) − v*] = min_{x∈𝒮*}{√N[ĝ_N(x) − g(x)]}
ProvedKleywegtSAA.ValueCLT.sqrt_mul_minOnOpt_subp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximationstochastic-programming
Let be a nonempty finite set, the true objective, , the set of minimizers of , and the sample average function. Since for every , for every sample size and every realization of the sample
The identity expresses the centred and scaled minimum over as a continuous function (the minimum) of the vector of scaled deviations , , to which the central limit theorem applies.
Formalization Note This is a deterministic identity: no measurability, integrability or independence is assumed. It holds for every , including the junk case where both sides are .
Preamble
import Mathlib import Definitions.Def_KleywegtSAA_ValueCLT_Setting
Formal statement
namespace KleywegtSAA.ValueCLT
open MeasureTheory ProbabilityTheory Filter Topology
/-- Kleywegt–Shapiro, §2.2, p. 5: since `v* = g(x)` for every `x ∈ S*`,
`√N [min_{x ∈ S*} ĝ_N(x) − v*] = min_{x ∈ S*} {√N [ĝ_N(x) − g(x)]}`. -/
theorem sqrt_mul_minOnOpt_sub
{X : Type*} (S : Finset X) (hS : S.Nonempty)
{𝒲 : Type*} (G : X → 𝒲 → ℝ)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) (W : ℕ → Ω → 𝒲) :
∀ (N : ℕ) (ω : Ω),
Real.sqrt N * (minOnOpt S hS G P W N ω - S.inf' hS (KleywegtSAA.ExpRate.trueObj G P W)) =
(optSet S hS (KleywegtSAA.ExpRate.trueObj G P W)).inf' (optSet_nonempty S hS (KleywegtSAA.ExpRate.trueObj G P W))
(fun x => Real.sqrt N * (KleywegtSAA.ExpRate.sampleObj G W N ω x - KleywegtSAA.ExpRate.trueObj G P W x)) := by sorry
end KleywegtSAA.ValueCLT
Source
Kleywegt & Shapiro, The sample average approximation method for stochastic discrete optimization, preprint (two-author version, sha256 56657748…), p. 5, §2.2, proof of Proposition 2.3, the display following "Furthermore, since v* = g(x) for any x ∈ 𝒮*"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.