Theorem 3.8 — the expected violation is at most
ProvedScenarioApproach.Generalization.expected_violation_leConsider the convex scenario program with decision variables, cost , domain , constraint sets , , and probability on , under Assumption 3.4 ( and all convex and closed) and Assumption 3.6 (a unique solution for every number of constraints and every sample). Let be the solution of the program with i.i.d. constraints . Then its violation is integrable and
Equivalently, bounds the probability that the scenario solution computed from samples violates the constraint of a further, independent sample; it is the mean of the Beta distribution that dominates by Theorem 3.7.
Formalization Note The expectation is the Bochner integral of under = Measure.pi (fun _ : Fin N => P); integrability is part of the conclusion, so the bound cannot hold through Lean's convention that a non-integrable function integrates to . No relation between and is assumed, as on the page (the bound exceeds when ). Measurability is assumed as for Theorem 3.7.
import Mathlib import Definitions.Def_ScenarioApproach_Generalization_violation import Definitions.Def_ScenarioApproach_Generalization_scenarioProgram
namespace ScenarioApproach.Generalization
/-- Theorem 3.8 (p. 42): under Assumptions 3.4 and 3.6, `𝔼[V(θ*)] ≤ d / (N + 1)`. The
violation of the scenario solution is integrable and its expectation under `ℙ^N` is at most
`d / (N + 1)`. -/
theorem expected_violation_le
{d N : ℕ} {Δ : Type*} [MeasurableSpace Δ]
(P : MeasureTheory.Measure Δ) [MeasureTheory.IsProbabilityMeasure P]
(c : EuclideanSpace ℝ (Fin d)) (Θ : Set (EuclideanSpace ℝ (Fin d)))
(Θδ : Δ → Set (EuclideanSpace ℝ (Fin d)))
-- Assumption 3.4 (convexity): `Θ` and every `Θ_δ` are convex and closed
(hΘ_convex : Convex ℝ Θ) (hΘ_closed : IsClosed Θ)
(hΘδ_convex : ∀ δ, Convex ℝ (Θδ δ)) (hΘδ_closed : ∀ δ, IsClosed (Θδ δ))
-- Assumption 3.6 (existence and uniqueness), for every `m` and every sample
(hexu : ∀ (m : ℕ) (ω : Fin m → Δ), ∃! θ, IsSolution c Θ Θδ ω θ)
-- measurability, glossed over on p. 33: the constraint relation is jointly measurable
(hmeas : MeasurableSet {p : EuclideanSpace ℝ (Fin d) × Δ | p.1 ∈ Θδ p.2})
-- `θstar ω` is the solution of the scenario program with the `N` sampled constraints `ω`
(θstar : (Fin N → Δ) → EuclideanSpace ℝ (Fin d))
(hθstar : ∀ ω, IsSolution c Θ Θδ ω (θstar ω)) (hθstar_meas : Measurable θstar)
(hd : 1 ≤ d) :
MeasureTheory.Integrable (fun ω => violation P Θδ (θstar ω))
(MeasureTheory.Measure.pi fun _ : Fin N => P) ∧
∫ ω, violation P Θδ (θstar ω) ∂(MeasureTheory.Measure.pi fun _ : Fin N => P) ≤
(d : ℝ) / (N + 1) := by sorry
end ScenarioApproach.Generalization
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.