Theorem 4.1 — the separate integrated chance constraint is polyhedral for finite discrete
ProvedKallMayerSLP.ICC.theorem_4_1convexityintegrated-chance-constraintsp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1polyhedrastochastic-programming
Let have the finite discrete distribution (4.7), with realizations and probabilities , , and put , , . For , the set is polyhedral, and
For the sum is . So the constraint is a system of proper linear inequalities, which is the representation used in dual decomposition.
Formalization Note is the expectation against the law (4.7), not a sum by definition. "Polyhedral" means a finite intersection of closed half-spaces of , possibly with zero coefficient vectors, via the published IsPolyhedron.
Differences from the source:
- generalization: ξ with realizations in ℝʳ, t(ξ), h(ξ) affine in ξ (1.2) → Ξ any measurable space with measurable singletons, t, h arbitrary functions, atoms not required distinct; reason: the book says (1.2) is not used in the chapter; Ξ = ℝʳ with its Borel sets gives the book's case
- encoding: 𝒦 ⊂ 𝒩 over subsets of {1, …, N} → 𝒦 : Finset (Fin N), all subsets including ∅ and the whole set; reason: the book includes 𝒦 = ∅ with empty sum 0 (p.153); 0-based indices; same instances
Preamble
import Mathlib import Definitions.Def_VanderbeiLP_StrictComp_Polyhedron import Definitions.Def_KallMayerSLP_ICC_K import Definitions.Def_KallMayerSLP_ICC_discreteLaw open MeasureTheory Matrix
Formal statement
namespace KallMayerSLP.ICC
/-- **Theorem 4.1 (separate integrated chance constraints, finite discrete distribution).**
Kall & Mayer, *Stochastic Linear Programming* (2005), Chapter 2, Theorem 4.1 and (4.12), p.152
(PDF 162). For `γ ≥ 0`, `S(γ) = {x | K(x) ≤ γ}` is a polyhedral set, and
`{x | K(x) ≤ γ} = ⋂_{𝒦 ⊂ 𝒩} {x | Σ_{k∈𝒦} p_k (tᵏx − hᵏ) ≤ γ}`.
**Formalization Note.** `ξ` has the law (4.7), `tᵏ = t(ξ̂ᵏ)`, `hᵏ = h(ξ̂ᵏ)`. `K` is the expectation
against that law, not a sum by definition. `𝒦` runs over all subsets of `𝒩` including `∅`, where
the sum is `0` (p.153). `MeasurableSingletonClass Ξ` holds for the book's `Ξ ⊂ ℝʳ` with the Borel
σ-algebra; it makes every function integrable against the law. -/
theorem theorem_4_1 {Ξ : Type*} [MeasurableSpace Ξ] [MeasurableSingletonClass Ξ] {N n : ℕ}
(p : Fin N → ℝ) (ξhat : Fin N → Ξ) (hp : ∀ k, 0 < p k) (hsum : ∑ k, p k = 1)
(t : Ξ → Fin n → ℝ) (h : Ξ → ℝ) (γ : ℝ) (hγ : 0 ≤ γ) :
VanderbeiLP.StrictComp.IsPolyhedron {x | K (discreteLaw p ξhat) t h x ≤ γ} ∧
{x | K (discreteLaw p ξhat) t h x ≤ γ} =
⋂ 𝒦 : Finset (Fin N), {x | ∑ k ∈ 𝒦, p k * (t (ξhat k) ⬝ᵥ x - h (ξhat k)) ≤ γ} := by sorry
end KallMayerSLP.ICC
Source
Kall & Mayer, Stochastic Linear Programming (2005), Chapter 2, Theorem 4.1 and (4.12), p.152 (PDF 162)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.