Theorem 3.2, p. 12, (3.17) — ∃ β > 0, limsup_N N⁻¹ log P(ℳ_N^c) ≤ −β
ProvedSAARate.Polyhedral.theorem_3_2Assume the conditions of Theorem 2.3:
- the scenario set is finite;
- every is piecewise linear and convex on ;
- is closed, convex and polyhedral;
- the optimal set of the true problem is nonempty and bounded.
Let be an i.i.d. sample from on a probability space , let be the optimal set of the SAA problem , and let
Then there is a constant such that
The probability that the SAA problem fails to return a face of the true optimal set decays exponentially in the sample size. This is the quantitative form of Theorem 2.3, and it explains why small samples already solve finite piecewise linear stochastic programs exactly.
Formalization Note (3.17) is stated in the equivalent form: for every , eventually . This avoids the logarithm of a probability that may be . is not shown to be measurable, so is its outer measure; an upper bound on it is the stronger statement. The complement is of the whole event: empty, or not a face of . The empty set is a face of every set, so nonemptiness is stated explicitly.
import Mathlib import Definitions.Def_SAARate_Polyhedral_Setting open MeasureTheory ProbabilityTheory Filter
namespace SAARate.Polyhedral
/-- Theorem 3.2, p. 12, (3.17): under the assumptions (i)–(iv) of Theorem 2.3 there is `β > 0`
with `limsup_N N⁻¹ log P(ℳ_N^c) ≤ −β`, where `ℳ_N` (3.16) is the event that the SAA optimal set
`A_N` is nonempty and a face of the true optimal set `A`. Stated in ε-form: for every `δ > 0`,
eventually `P(ℳ_N^c) ≤ exp(−(β − δ) N)`, with `P(ℳ_N^c)` the outer measure. -/
theorem theorem_3_2 {m : ℕ} {Ω : Type*} [Fintype Ω] [MeasurableSpace Ω]
[MeasurableSingletonClass Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(h : SAARate.Sharp.E m → Ω → ℝ) (hpl : ∀ ω, IsPLConvex (fun x => h x ω))
(Θ : Set (SAARate.Sharp.E m)) (hΘc : IsClosed Θ) (hΘv : Convex ℝ Θ) (hΘp : IsPolyhedral Θ)
(hA : (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ).Nonempty ∧
Bornology.IsBounded (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ))
{S : Type*} [MeasurableSpace S] (Q : Measure S) [IsProbabilityMeasure Q]
(ω : ℕ → S → Ω) (hω : SAARate.SharpLD.IsIIDSample Q P ω) :
∃ β > 0, ∀ δ > 0, ∀ᶠ N : ℕ in atTop,
Q {s | ¬ ((SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h (fun j => ω j s) N) Θ).Nonempty ∧
IsFace (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ) (SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h (fun j => ω j s) N) Θ))} ≤
ENNReal.ofReal (Real.exp (-(β - δ) * (N : ℝ))) := by sorry
end SAARate.Polyhedral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.