Theorem 2.4 (Kall), p.100 — is convex for when the smallest probability is unique
ProvedKallMayerSLP.ProbConstr.theorem_2_4chance-constraintsp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1probability-constraintsstochastic-programming
Let have the finite discrete distribution given by the realization tableau with for all and , and let . Let and assume that the minimum is attained only at . Let
be the second smallest probability. Then the feasible set is convex for every
This sharpens Marti's Theorem 2.3, whose threshold is larger: under a unique smallest probability, the joint probability constraint defines a convex set already at all levels above .
Formalization Note Uniqueness of the minimizer is the hypothesis for all ; the index attains the minimum over , which forces .
Differences from the source:
- generalization: T(ξ), h(ξ) affine in ξ (Notations, p.ix) → T(ξ), h(ξ) arbitrary functions of the realization; reason: only their values at the atoms ξ̂^i enter, and affine data are a special case
- encoding: ξ with the finite discrete distribution of the tableau (2.15), indices 1, …, N → τ : RealizationTableau N r with law Σ_i p_i δ_{ξ̂^i}, indices Fin N; reason: the same law; atoms are allowed to coincide, as in the book's tableau
- encoding: "p_{i₀} = min_{i∈I} p_i is uniquely determined; p_{i₁} = min_{i∈I∖{i₀}} p_i" → hypotheses ∀ i ≠ i₀, p_{i₀} < p_i; i₁ ≠ i₀; ∀ i ≠ i₀, p_{i₁} ≤ p_i; reason: the same conditions; i₁ ≠ i₀ makes N ≥ 2, which the minimum over I∖{i₀} needs (paper.md reading 7)
Preamble
import Mathlib import Definitions.Def_KallMayerSLP_ProbConstr_feasibleSet import Definitions.Def_KallMayerSLP_ProbConstr_RealizationTableau_measure
Formal statement
namespace KallMayerSLP.ProbConstr
/-- **Theorem 2.4** (Kall 1976). Let `p_{i₀} = min_{i∈I} p_i` and assume that `p_{i₀}` is uniquely
determined. Let `p_{i₁} = min_{i∈I∖{i₀}} p_i`. Then `B(α)` is convex for `α > 1 − p_{i₁}`.
Kall & Mayer 2005, Chapter 2, Theorem 2.4, p.100 (PDF 110) (proof cited: Kall [134]).
**Formalization Note.** `ξ` has the finite discrete distribution of the realization tableau (2.15)
(`τ.measure = Σ_i p_i · dirac(ξ̂^i)`, `p_i > 0`, `Σ p_i = 1`), indices `Fin N` for `1, …, N`. The data
`T(ξ)`, `h(ξ)` are arbitrary functions of the realization (the book's affine data are a special
case); only their values at the atoms matter. "`p_{i₀}` is the uniquely determined minimum" is
`∀ i ≠ i₀, p_{i₀} < p_i`; `i₁ ≠ i₀` attains the minimum over `I ∖ {i₀}`, so `N ≥ 2` (needed for
`p_{i₁}` to exist). Every real `α > 1 − p_{i₁}`. -/
theorem theorem_2_4 {N r m n : ℕ} (τ : RealizationTableau N r)
(T : (Fin r → ℝ) → Matrix (Fin m) (Fin n) ℝ) (h : (Fin r → ℝ) → Fin m → ℝ) (i₀ i₁ : Fin N) (hi₀ : ∀ i, i ≠ i₀ → τ.p i₀ < τ.p i)
(hi₁ : i₁ ≠ i₀) (hi₁min : ∀ i, i ≠ i₀ → τ.p i₁ ≤ τ.p i) (α : ℝ)
(hα : 1 - τ.p i₁ < α) :
Convex ℝ (feasibleSet τ.measure T h α) := by sorry
end KallMayerSLP.ProbConstr
Source
Kall & Mayer, Stochastic Linear Programming: Models, Theory, and Computation (Kluwer/Springer 2005), Chapter 2, Chapter 2, §2.2, Theorem 2.4 (Kall 1976), p.100 (PDF 110)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.