Proposition 2.3, (2.8), p. 5 — √N(v̂_N − v*) ⇒ min_{x∈𝒮*} Y(x), Y a centered Gaussian vector with the autocovariance of G(x, W)
ProvedKleywegtSAA.ValueCLT.proposition_2_3Consider the stochastic program of (1.1) over a nonempty finite set , where for every the function is measurable and . Let be an i.i.d. sample of , let
and let be the set of optimal solutions of (1.1).
Proposition 2.3. Suppose that the variances exist for every . Then
where denotes convergence in distribution and is a Gaussian random vector with zero mean and the autocovariance function of : for .
The result gives the first-order asymptotic distribution of the SAA estimator of the optimal value of a discrete stochastic program. When the true problem has several optimal solutions, the limit is the minimum of a correlated Gaussian vector, which has negative mean; so is biased downward at the order .
Formalization Note The limit is any random vector , on any probability space, whose law is the multivariate Gaussian measure on with mean and covariance matrix ; this matrix is positive semidefinite under the variance hypothesis, so the Gaussian law is the genuine one. The vector is indexed by , not by . "The variance exists" is square integrability of , assumed only on as in the Proposition; off only the integrability of (1.1) is assumed. " is -measurable" is read as Borel measurability. The sample is a -indexed sequence of independent random elements, each with the law of the first one.
import Mathlib import Definitions.Def_KleywegtSAA_ValueCLT_Setting
namespace KleywegtSAA.ValueCLT
open MeasureTheory ProbabilityTheory Filter Topology
open Classical in
/-- Kleywegt–Shapiro, Proposition 2.3, (2.8), p. 5: if the variances `σ²(x) = Var G(x, W)` exist
for every `x ∈ S*`, then `√N (v̂_N − v*) ⇒ min_{x ∈ S*} Y(x)`, where `(Y(x))_{x ∈ S*}` is a
centered Gaussian vector with the autocovariance function of `G(x, W)`. -/
theorem proposition_2_3
{X : Type*} (S : Finset X) (hS : S.Nonempty)
{𝒲 : Type*} [MeasurableSpace 𝒲] (G : X → 𝒲 → ℝ) (hG : ∀ x ∈ S, Measurable (G x))
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(W : ℕ → Ω → 𝒲) (hWm : ∀ n, Measurable (W n)) (hind : iIndepFun W P)
(hid : ∀ n, IdentDistrib (W n) (W 0) P P)
(hint : ∀ x ∈ S, Integrable (fun ω => G x (W 0 ω)) P)
(hvar : ∀ x ∈ optSet S hS (KleywegtSAA.ExpRate.trueObj G P W), MemLp (fun ω => G x (W 0 ω)) 2 P) :
∀ {Ω' : Type*} [MeasurableSpace Ω'] (Q : Measure Ω') [IsProbabilityMeasure Q]
(Y : Ω' → EuclideanSpace ℝ (optSet S hS (KleywegtSAA.ExpRate.trueObj G P W))),
HasLaw Y (multivariateGaussian 0 (covMat G P W (optSet S hS (KleywegtSAA.ExpRate.trueObj G P W)))) Q →
TendstoInDistribution
(fun (N : ℕ) ω => Real.sqrt N * (S.inf' hS (KleywegtSAA.ExpRate.sampleObj G W N ω) - S.inf' hS (KleywegtSAA.ExpRate.trueObj G P W)))
atTop
(fun ω' => Finset.univ.inf'
(Finset.univ_nonempty_iff.2 (optSet_nonempty S hS (KleywegtSAA.ExpRate.trueObj G P W)).to_subtype)
(fun x => Y ω' x))
(fun _ => P) Q := by sorry
end KleywegtSAA.ValueCLT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.