Eq. (5.2) — for fully supported problems Theorem 3.7 holds with equality
ProvedScenarioApproach.Generalization.violation_tail_eq_binomial_sum_of_fullySupportedConsider the convex scenario program with decision variables: cost , domain , constraint sets , , and a probability on . Assume
- (Assumption 3.4) and every are convex and closed;
- (Assumption 3.6) for every and every sample the program with these constraints has a unique solution;
- the problem is fully supported (Definition 5.4): for every , with probability 1 the program with i.i.d. constraints has exactly support constraints.
Let , let be the solution of the program with i.i.d. constraints , and its violation. Then for every
So the bound of Theorem 3.7 is attained exactly by fully supported problems: then has the Beta distribution, whatever is.
Formalization Note The book writes the display (5.2) for and states in words that the result of Theorem 3.7 holds with equality for fully supported problems; the general- equality is stated here. The solution is a map θstar : (Fin N → Δ) → EuclideanSpace ℝ (Fin d) with θstar ω the solution for every sample. Measurability, glossed over in the book (p. 33), is assumed as joint measurability of and measurability of θstar. The probability is compared in via ENNReal.ofReal.
import Mathlib import Definitions.Def_ScenarioApproach_Generalization_violation import Definitions.Def_ScenarioApproach_Generalization_scenarioProgram import Definitions.Def_ScenarioApproach_Generalization_supportConstraint
namespace ScenarioApproach.Generalization
/-- Eq. (5.2) and the sentence before §5.2 (p. 58): for fully supported problems the bound of
Theorem 3.7 holds with equality. -/
theorem violation_tail_eq_binomial_sum_of_fullySupported
{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)
(hfs : FullySupported c Θ Θδ P)
(hd : 1 ≤ d) (hN : d ≤ N) (ε : ℝ) (hε0 : 0 ≤ ε) (hε1 : ε ≤ 1) :
MeasureTheory.Measure.pi (fun _ : Fin N => P) {ω | ε < violation P Θδ (θstar ω)} =
ENNReal.ofReal
(∑ i ∈ Finset.range d, (N.choose i : ℝ) * ε ^ i * (1 - ε) ^ (N - i)) := by sorry
end ScenarioApproach.Generalization
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.