Proof of Theorem 2, p. 8 — liminf_n P(μ_x̂ ≤ G_n(x̂) + z_α s_n(x*_n)/√n) ≥ Φ((1 − ε)z_α) when α ≤ 1/2
ProvedSolutionQuality.SRP.theorem2_eps_boundcentral-limit-theoremconfidence-intervalp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-programming
Assume (A1)–(A3), let , let be i.i.d. as , and let be optimal solutions of (SP). Let and let satisfy . Let and assume . Then for every ,
where is the standard normal distribution function, is the optimality gap, is the gap estimator (2) and .
This is the central estimate of the proof of Theorem 2; letting gives the coverage bound in the case .
Formalization Note. The proof's "suppose " is not a hypothesis: it is implied by (if then is the minimum). is any real with cdf (gaussianReal 0 1) zα = 1 - α. Probabilities are in (ℝ≥0∞), where liminf has no junk value; enters through ENNReal.ofReal.
Preamble
import Mathlib import Definitions.Def_SolutionQuality_SRP_Setting
Formal statement
namespace SolutionQuality.SRP
open MeasureTheory ProbabilityTheory Filter
theorem theorem2_eps_bound {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 μ ξ)
(xhat : E d) (hxhat : xhat ∈ X)
(xn : ℕ → Ω → E d) (hxn : IsSAAMinimizerSeq P f X ξ xn)
(α : ℝ) (hα0 : 0 < α) (hα1 : α < 1)
(zα : ℝ) (hzα : cdf (gaussianReal 0 1) zα = 1 - α)
(xmin : E d)
(hxmin : xmin ∈ optSet μ f X ∧ ∀ x ∈ optSet μ f X, gapVar μ f xhat xmin ≤ gapVar μ f xhat x)
(hσ : 0 < gapVar μ f xhat xmin) (hαhalf : α ≤ 1 / 2)
(ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1) :
ENNReal.ofReal (cdf (gaussianReal 0 1) ((1 - ε) * zα)) ≤
liminf (fun n : ℕ => P {ω | optGap μ f X xhat ≤
gapEstimate f X xhat (fun i => ξ i ω) n +
zα * Real.sqrt (sampleVar f xhat (fun i => ξ i ω) n (xn n ω)) / Real.sqrt n}) atTop := by sorry
end SolutionQuality.SRP
Source
Bayraksan & Morton, Assessing Solution Quality in Stochastic Programs, preprint (January 26, 2005), pp. 7–8, proof of Theorem 2, (7)–(9) and the display after (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.