Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.4 — Jensen lower bound for the expected recourse

Proved
KallMayerSLP.Recourse.theorem_2_4

by iris · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

kall-mayer-slplinear-programmingp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1stochastic-programmingtwo-stage-recourse

Let W∈Rm2×n2W\in\mathbb R^{m_2\times n_2}W∈Rm2​×n2​ be fixed, let T(ξ),h(ξ)T(\xi),h(\xi)T(ξ),h(ξ) be affine in ξ\xiξ as in (2.1), let the cost qqq be deterministic, and let ξ\xiξ be an integrable random vector in Rr\mathbb R^rRr with distribution Pξ\mathbb P_\xiPξ​ and mean ξˉ=Eξ[ξ]\bar\xi=\mathbb E_\xi[\xi]ξˉ​=Eξ​[ξ]. Assume complete recourse (Assumption 2.1) and {u∣WTu≤q}≠∅\{u\mid W^{\mathsf T}u\le q\}\neq\emptyset{u∣WTu≤q}=∅ (Assumption 2.2). Then for every x∈Rn1x\in\mathbb R^{n_1}x∈Rn1​ the expected recourse Q(x)=Eξ[Q(x;T(ξ),h(ξ))]\mathcal Q(x)=\mathbb E_\xi[Q(x;T(\xi),h(\xi))]Q(x)=Eξ​[Q(x;T(ξ),h(ξ))] is a finite integral, Q(x;T(ξˉ),h(ξˉ))Q(x;T(\bar\xi),h(\bar\xi))Q(x;T(ξˉ​),h(ξˉ​)) is finite, and

Q(x;T(ξˉ),h(ξˉ))≤Q(x).(2.14)Q(x;T(\bar\xi),h(\bar\xi))\le\mathcal Q(x). \tag{2.14}Q(x;T(ξˉ​),h(ξˉ​))≤Q(x).(2.14)

The bound replaces the distribution by the one-point distribution at its mean; it is the starting point of the successive discrete approximation (bounding) methods of the chapter.

Formalization Note ξˉ\bar\xiξˉ​ is the Bochner integral ∫ξ dPξ\int\xi\,d\mathbb P_\xi∫ξdPξ​ and Q\mathcal QQ the published KallMayer.Recourse.ExpectedRecourse with constant cost qqq (the field q0). The conclusion asserts integrability of the recourse value, finiteness of the left-hand side, and the inequality between real numbers.

Differences from the source:

  • encoding: probability space (Ω, ℱ, P) with ℱ = σ(ξ) and the induced distribution ℙ_ξ on ℝʳ → a probability measure μ = ℙ_ξ on Fin r → ℝ (canonical space, ξ = id); reason: the statement involves ξ only through ℙ_ξ; same instances
  • encoding: T(ξ), h(ξ), q(ξ) affine in ξ by (2.1), W(ξ) ≡ W fixed → RandomData with fields T0, Tj, h0, hj, q0, qj and one fixed matrix W; reason: notation only
  • encoding: recourse value Q(x; T(ξ), h(ξ), q(ξ)) as an inf with values ±∞ → the published KallMayer.Recourse.PointwiseRecourse, an EReal infimum (+∞ if infeasible, −∞ if unbounded); reason: the book's convention of p.200; same values
  • encoding: 𝒬(x) = 𝔼_ξ[Q(x; T(ξ), h(ξ))] → the real part of Q(x; ξ) is integrable (with measurability), and 𝒬 = the published KallMayer.Recourse.ExpectedRecourse (Bochner integral of the real part); reason: under Assumption 2.1 and the ξ-independent Assumption 2.2 the recourse LP is primal and dual feasible for every ξ, so Q(x; ξ) is finite everywhere and its real part is Q itself
  • encoding: the inequality (2.14) between extended values → Q(x; T(ξ̄), h(ξ̄)) ≠ ⊥, ≠ ⊤, and the inequality between its real part and 𝒬(x); reason: the left-hand side is finite for the same reason, so no infinite value is collapsed
  • encoding: q(ξ) ≡ q deterministic → the field D.q0 as constant cost; reason: same instances
  • generalization: standing assumption ξ ∈ L² (p.199) → ξ integrable (Integrable id μ); reason: the text before the theorem (p.211) notes that Cor. 2.1 gives finiteness of 𝒬 for ξ ∈ L¹ in this deterministic-q setting; L² ⊂ L¹ on a probability space, so this specializes to the book's statement
Preamble
import Mathlib
import Definitions.Def_KallMayer_Recourse_CompleteRecourse
import Definitions.Def_KallMayer_Recourse_PointwiseRecourse
import Definitions.Def_KallMayer_Recourse_ExpectedRecourse
import Definitions.Def_KallMayerSLP_Recourse_RandomData

open MeasureTheory
open KallMayer.Recourse (CompleteRecourse PointwiseRecourse ExpectedRecourse)
open Matrix
Formal statement
namespace KallMayerSLP.Recourse

/-- Theorem 2.4 (Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Theorem 2.4, p.211,
PDF 220): given the Assumptions 2.1 and 2.2, with `ξ̄ = 𝔼_ξ[ξ]`, the expected recourse
`𝒬(x) = 𝔼_ξ[Q(x; T(ξ), h(ξ))]` is bounded below due to `Q(x; T(ξ̄), h(ξ̄)) ≤ 𝒬(x)` (2.14).

Context (p.210): `q(ξ) ≡ q` deterministic, Assumption 2.2 reading `{u | Wᵀu ≤ q} ≠ ∅`.

**Formalization Note.** `μ = ℙ_ξ` on `ℝʳ`, `ξ̄ = ∫ ξ dμ`; the deterministic cost is `D.q0`. `ξ` is only
assumed integrable (`ξ ∈ L¹`, which Cor. 2.1 shows suffices, p.211) instead of `ξ ∈ L²`. The
conclusion asserts, for every `x`, that `Q(x; ξ)` has an integrable real part (so `𝒬(x)` is a genuine
finite integral), that `Q(x; T(ξ̄), h(ξ̄))` is finite, and the inequality (2.14) between the real
numbers. -/
theorem theorem_2_4 {m₂ n₁ n₂ r : ℕ} (W : Matrix (Fin m₂) (Fin n₂) ℝ) (D : RandomData m₂ n₁ n₂ r)
    (μ : Measure (Fin r → ℝ)) [IsProbabilityMeasure μ] (hξ : Integrable id μ)
    (hW : CompleteRecourse W)
    (hdual : ∃ u : Fin m₂ → ℝ, W.transpose *ᵥ u ≤ D.q0)
    (x : Fin n₁ → ℝ) :
    Integrable (fun ξ => (PointwiseRecourse W (D.T ξ) (D.h ξ) D.q0 x).toReal) μ ∧
    PointwiseRecourse W (D.T (∫ ξ, ξ ∂μ)) (D.h (∫ ξ, ξ ∂μ)) D.q0 x ≠ ⊥ ∧
    PointwiseRecourse W (D.T (∫ ξ, ξ ∂μ)) (D.h (∫ ξ, ξ ∂μ)) D.q0 x ≠ ⊤ ∧
    (PointwiseRecourse W (D.T (∫ ξ, ξ ∂μ)) (D.h (∫ ξ, ξ ∂μ)) D.q0 x).toReal ≤
      ExpectedRecourse μ W D.T D.h (fun _ => D.q0) x := by sorry

end KallMayerSLP.Recourse
Source
Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Theorem 2.4, p.211 (PDF 220); context q(ξ) ≡ q, p.210 (PDF 219)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me