Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.1 — the aggregated problem (3.14) gives a lower bound on (3.10)

Proved
KallMayerSLP.Multistage.lemma_3_1

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

multistage-stochastic-programmingp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1scenario-treestochastic-linear-programming

Let problem (3.10) satisfy Assumption 3.2: only the right-hand sides are random and affine in ζt\zeta_tζt​, the ξt\xi_tξt​ are bounded within intervals Ξt\Xi^tΞt and stochastically independent, and the AttA_{tt}Att​ are complete fixed recourse matrices. Then for any subfiltration F^\widehat{\mathcal F}F constructed as on p.261, that is, for any scenario tree with its partitions of the Ξt\Xi^tΞt, the optimal value of the aggregated problem

min⁡∑m∈NpmctmTxms.t.∑m∈H(n)Atntmxm=btn(ζ^n)  ∀n∈N,xm≥0  ∀m∈N\min\sum_{m\in\mathcal N}p_mc_{t_m}^{\mathsf T}x_m\quad\text{s.t.}\quad\sum_{m\in\mathcal H(n)}A_{t_nt_m}x_m=b_{t_n}(\widehat\zeta^n)\ \ \forall n\in\mathcal N,\quad x_m\ge0\ \ \forall m\in\mathcal Nminm∈N∑​pm​ctm​T​xm​s.t.m∈H(n)∑​Atn​tm​​xm​=btn​​(ζ​n)  ∀n∈N,xm​≥0  ∀m∈N

is a lower bound of the optimum in (3.10).

This is the multistage counterpart of the Jensen lower bound of two-stage programs: replacing the distribution by the conditional means on the cells of any partition tree turns a problem over decision functions into a finite linear program with no larger value. Example 3.1 shows that the conclusion fails without independence.

Formalization Note The distributions are arbitrary, subject to Assumption 3.2; there is no finiteness restriction. Both optimal values are infima in the extended reals, so infeasible and unbounded problems are covered.

Differences from the source:

  • reading: Assumption 3.2: the A_tt complete fixed recourse matrices ∀t → complete recourse of A_tt for t = 2, …, T; reason: A_11 is not a recourse matrix, and the book's Example 3.1 calls a problem with a non-complete first stage complete fixed recourse; this is the weaker hypothesis, so the statement implies the ∀t one
  • generalization: supp ℙ_{ξ_t} ⊆ Ξ^t → ξ_t ∈ Ξ^t almost surely; reason: the support inclusion implies the almost sure one, and they agree for closed Ξ^t, so the statement specializes to the source
  • encoding: subfiltration ℱ̂ constructed as on p.261 → a ScenarioTree; reason: the tree with its partitions is the data of that construction
  • encoding: stage 1 written apart from stages 2, …, T → one formula for t = 1, …, T, with the one-point state space Hist r 1; reason: the same constraints and objective; x_1 and b_1 are deterministic
  • encoding: min → infimum in EReal; reason: +∞ on infeasible and -∞ on unbounded problems; the book assumes neither case away
  • generalization: a partition of Ξ^{ν+1} into subintervals, |C_n| = r_n ≥ 1 → ScenarioTree, whose cells may be empty (a node may then have no child when Ξ^{ν+1} is empty); reason: every tree of p.261 is a ScenarioTree, so the statement specializes to the book's trees
  • encoding: ξ̄^n_t = 𝔼[ξ_t | ξ_t ∈ Ξ^t_n], undefined on a P-null cell → xiBar = 0 on a P-null cell (Lean's 0⁻¹ = 0); reason: such a node and its descendants have p_n = 0, and their constraints are solvable by complete recourse of A_tt (t ≥ 2), so no value of (3.14) depends on the choice
Preamble
import Mathlib
import Definitions.Def_KallMayerSLP_Multistage_Assumption32
import Definitions.Def_KallMayerSLP_Multistage_value
import Definitions.Def_KallMayerSLP_Multistage_aggValue
Formal statement
namespace KallMayerSLP.Multistage

open MeasureTheory

/-- **Chapter 3, Lemma 3.1** (Kall & Mayer, *Stochastic Linear Programming* (2005), Chapter 3,
Lemma 3.1, p.263, PDF 272): "Let problem (3.10) satisfy Assumption 3.2. Then for any subfiltration
`ℱ̂` constructed as above, the optimal value of the aggregated problem (3.14) is a lower bound of the
optimum in (3.10)."

**Formalization Note.** A subfiltration constructed as on p.261 is a `ScenarioTree`. The
distributions are arbitrary, subject to Assumption 3.2. Both optimal values are infima in `EReal`
(see `value`, `aggValue`), so the statement also covers infeasible and unbounded problems. -/
theorem lemma_3_1 {D : MSLP} {Ω : Type*} [MeasurableSpace Ω] {P : Measure Ω}
    [IsProbabilityMeasure P] {ξ : ∀ t, Ω → Fin (D.r t) → ℝ} {Ξ : ∀ t, Set (Fin (D.r t) → ℝ)}
    (hA : Assumption32 D P ξ Ξ) (𝒯 : ScenarioTree D Ξ) :
    aggValue 𝒯 P ξ ≤ value D P ξ := by sorry

end KallMayerSLP.Multistage
Source
Kall & Mayer, Stochastic Linear Programming: Models, Theory, and Computation (Kluwer/Springer 2005), Chapter 3, Lemma 3.1, p.263 (PDF 272)
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