Proof of Proposition 1, p. 6 — f̄_n(x) → Ef(x, ξ̃) uniformly on X, w.p.1
ProvedSolutionQuality.SRP.fbar_tendstoUniformlyOnp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximationstochastic-programminguniform-law-of-large-numbers
Assume (A1)–(A3), and let be i.i.d. as . Then, with probability one, the sample mean functions converge to the expected cost uniformly on :
This uniform strong law of large numbers is the engine behind every consistency statement of the paper: it yields convergence of optimal values (Proposition 1 (i)) and of optimal solutions (Proposition 1 (ii)). The paper quotes it from Rubinstein and Shapiro, Lemma A1.
Formalization Note. The candidate and the minimizers play no role and are not hypotheses. is assumed measurable for each (the paper's " is a random variable"). Uniform convergence on is Mathlib's TendstoUniformlyOn.
Preamble
import Mathlib import Definitions.Def_SolutionQuality_SRP_Setting
Formal statement
namespace SolutionQuality.SRP
open MeasureTheory ProbabilityTheory Filter
theorem fbar_tendstoUniformlyOn {d : ℕ} {Ξ : Type*} [MeasurableSpace Ξ]
(μ : Measure Ξ) [IsProbabilityMeasure μ]
(f : E d → Ξ → ℝ) (hfm : ∀ x, Measurable (f x))
(X : Set (E d)) (hA : Assumptions μ f X)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(ξ : ℕ → Ω → Ξ) (hξ : IsIIDSample P μ ξ) :
∀ᵐ ω ∂P, TendstoUniformlyOn (fun n x => sampleMean f (fun i => ξ i ω) n x)
(expectedCost μ f) atTop X := by sorry
end SolutionQuality.SRP
Source
Bayraksan & Morton, Assessing Solution Quality in Stochastic Programs, preprint (January 26, 2005), p. 6, proof of Proposition 1, second sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.