Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
โ† Formalpedia

Theorem 3 โ€” in multistage programs, ๐“œ๐’ฎ๐’ซ^u and ๐“œ๐’ฎ๐’ซ^l are equivalent to the linear programs (4.2) and (4.6)

Proved
PrimalDualLDR.Multistage.theorem_3

by mikedeng1 ยท Oct 7, 2026 ยท Mathlib 0df444a (Lean v4.33.1)

linear-decision-ruleslinear-programmingmultistagep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-programming

Consider a linear multistage stochastic program MSP\mathcal{MSP}MSP (p. 18): over TTT stages, minimize E(โˆ‘tct(ฮพt)โŠคxt(ฮพt))\mathbb E\big(\sum_t c_t(\xi^t)^\top x_t(\xi^t)\big)E(โˆ‘tโ€‹ctโ€‹(ฮพt)โŠคxtโ€‹(ฮพt)) over non-anticipative rules xtโˆˆLkt,nt2x_t \in \mathcal L^2_{k^t,n_t}xtโ€‹โˆˆLkt,ntโ€‹2โ€‹ subject to Et(โˆ‘sAtsxs(ฮพs))โ‰คbt(ฮพt)\mathbb E_t\big(\sum_s A_{ts}x_s(\xi^s)\big) \le b_t(\xi^t)Etโ€‹(โˆ‘sโ€‹Atsโ€‹xsโ€‹(ฮพs))โ‰คbtโ€‹(ฮพt) P\mathbb PP-a.s., with deterministic constraint matrices AtsA_{ts}Atsโ€‹, ct(ฮพt)=CtPtฮพc_t(\xi^t) = C_tP_t\xictโ€‹(ฮพt)=Ctโ€‹Ptโ€‹ฮพ and bt(ฮพt)=BtPtฮพb_t(\xi^t) = B_tP_t\xibtโ€‹(ฮพt)=Btโ€‹Ptโ€‹ฮพ.

Assume that P\mathbb PP has a polyhedral support ฮž={ฮพ:Wฮพโ‰ฅh}\Xi = \{\xi : W\xi \ge h\}ฮž={ฮพ:Wฮพโ‰ฅh} of the type (2.1) โ€” nonempty, bounded, spanning Rk\mathbb R^kRk, with W,hW, hW,h of the form (2.1b) and k1=1k_1 = 1k1โ€‹=1 โ€” while

Et(ฮพ)=MtPtฮพP-a.s.ย forย someย MtโˆˆRkร—kt,ย tโˆˆT.\mathbb E_t(\xi) = M_tP_t\xi \quad \mathbb P\text{-a.s. for some } M_t \in \mathbb R^{k\times k^t},\ t \in \mathbb T.Etโ€‹(ฮพ)=Mtโ€‹Ptโ€‹ฮพP-a.s.ย forย someย Mtโ€‹โˆˆRkร—kt,ย tโˆˆT.

If MSP\mathcal{MSP}MSP is strictly feasible, then MSPu\mathcal{MSP}^uMSPu and MSPl\mathcal{MSP}^lMSPl are equivalent to the linear programs (4.2) and (4.6), respectively; the second equivalence is stated under the condition (โ‹†)(\star)(โ‹†): kโ‰ฅ2k \ge 2kโ‰ฅ2, or some row of W^\hat WW^ is nonzero (see the Formalization Note):

val(MSPu)=val(4.2)and(โ‹†)โ€…โ€ŠโŸนโ€…โ€Šval(MSPl)=val(4.6).\mathrm{val}(\mathcal{MSP}^u) = \mathrm{val}(4.2) \qquad\text{and}\qquad (\star) \implies \mathrm{val}(\mathcal{MSP}^l) = \mathrm{val}(4.6).val(MSPu)=val(4.2)and(โ‹†)โŸนval(MSPl)=val(4.6).

Since MSPu\mathcal{MSP}^uMSPu is a conservative and MSPl\mathcal{MSP}^lMSPl a progressive approximation of MSP\mathcal{MSP}MSP, the two linear programs bracket the optimal value of the multistage program, and both are of size polynomial in the problem dimensions.

Formalization Note "Equivalent" is formalized as equality of optimal values, each the infimum of the objective over the feasible set in the extended reals (+โˆž+\infty+โˆž when infeasible, โˆ’โˆž-\inftyโˆ’โˆž when unbounded). The matrices MtM_tMtโ€‹ are data of the setting and the hypothesis states that they give the conditional mean; this is equivalent to the paper's "for some MtM_tMtโ€‹", since the problems depend on MtM_tMtโ€‹ only through MtPtฮพM_tP_t\xiMtโ€‹Ptโ€‹ฮพ on ฮž\Xiฮž. Strict feasibility of MSP\mathcal{MSP}MSP, which ยง4 does not define, is the analogue of (2.9) for the standard form (4.1): slacks bounded below by some ฮต>0\varepsilon > 0ฮต>0. The equality constraint of MSPl\mathcal{MSP}^lMSPl is in the corrected reading in which โˆ‘s\sum_sโˆ‘sโ€‹ covers only Atsxs(ฮพs)A_{ts}x_s(\xi^s)Atsโ€‹xsโ€‹(ฮพs). The final sentence of the printed theorem (the linear programs have polynomial size and are efficiently solvable) is informal and not formalized. The hypothesis (โ‹†)(\star)(โ‹†) on the second equality is a repair and is not in the paper (the first equality is stated without it, as printed): for k=1k = 1k=1 the support is ฮž={1}\Xi = \{1\}ฮž={1}, and if WWW has no nonzero row besides the two rows of (2.1b), the cone K={z:(Wโˆ’he1โŠค)zโ‰ฅ0}\mathcal K = \{z : (W - he_1^\top)z \ge 0\}K={z:(Wโˆ’he1โŠคโ€‹)zโ‰ฅ0} of Proposition 3 is all of R\mathbb RR while KP=[0,โˆž)\mathcal K_{\mathbb P} = [0,\infty)KPโ€‹=[0,โˆž), so Proposition 3 and the second equality fail. For instance T=1T = 1T=1, n1=m1=1n_1 = m_1 = 1n1โ€‹=m1โ€‹=1, A11=1A_{11} = 1A11โ€‹=1, B1=0B_1 = 0B1โ€‹=0, C1=โˆ’1C_1 = -1C1โ€‹=โˆ’1 is strictly feasible, MSPl\mathcal{MSP}^lMSPl has value 000, and (4.6) is unbounded below. For kโ‰ฅ2k \ge 2kโ‰ฅ2 the spanning support has at least two points and the omitted constraint e1โŠคzโ‰ฅ0e_1^\top z \ge 0e1โŠคโ€‹zโ‰ฅ0 is implied by (Wโˆ’he1โŠค)zโ‰ฅ0(W - he_1^\top)z \ge 0(Wโˆ’he1โŠคโ€‹)zโ‰ฅ0, as the paper's argument (p. 8) needs; for k=1k = 1k=1 with a nonzero row w^\hat ww^ of W^\hat WW^ (then w^>0\hat w > 0w^>0, as ฮž={1}\Xi = \{1\}ฮž={1} is nonempty), K=[0,โˆž)=KP\mathcal K = [0,\infty) = \mathcal K_{\mathbb P}K=[0,โˆž)=KPโ€‹ as well. So (โ‹†)(\star)(โ‹†) excludes exactly the case in which the printed statement fails.

Preamble
import Mathlib
import Definitions.Def_PrimalDualLDR_Multistage_Basic
import Definitions.Def_PrimalDualLDR_Multistage_Setting
import Definitions.Def_PrimalDualLDR_Multistage_Problems

open MeasureTheory Matrix
Formal statement
namespace PrimalDualLDR.Multistage

/-- Theorem 3 (p. 22): assume that `P` has a polyhedral support of the type (2.1), while
`๐”ผ_t(ฮพ) = M_t P_t ฮพ` almost surely for the matrices `M_t โˆˆ โ„^{k ร— k^t}`, `t โˆˆ ๐•‹`. If `๐“œ๐’ฎ๐’ซ` (which has
deterministic constraint matrices `A_ts` by construction) is strictly feasible, then `๐“œ๐’ฎ๐’ซ^u` and
`๐“œ๐’ฎ๐’ซ^l` are equivalent to the linear programs (4.2) and (4.6), respectively: their optimal values
coincide. The hypothesis on the second equality (`2 โ‰ค k`, or some row of `ลด` below (2.1b) is nonzero)
is not in the paper: for `k = 1` (so `ฮž = {1}`) and `W` with zero rows below (2.1b), the cone `๐’ฆ` of
Proposition 3 is all of `โ„` while `๐’ฆ_โ„™ = [0, โˆž)`, and the second equality fails (e.g. `T = 1`, `A = 1`,
`B = 0`, `C = -1`: `๐“œ๐’ฎ๐’ซ^l` has value `0`, (4.6) is unbounded below). The hypothesis excludes exactly
that case. The first equality is stated without it, as printed. -/
theorem theorem_3 (ฯƒ : Setting) (hฯƒ : ฯƒ.Standing) (hM : ฯƒ.LinearCondMean)
    (hsf : ฯƒ.StrictlyFeasible) :
    ฯƒ.valMSPu = ฯƒ.valLP42 โˆง
      ((2 โ‰ค ฯƒ.k โˆจ โˆƒ i : Fin ฯƒ.l, 2 โ‰ค i.val โˆง ฯƒ.W i โ‰  0) โ†’ ฯƒ.valMSPl = ฯƒ.valLP46) := by sorry

end PrimalDualLDR.Multistage
Source
Kuhn, Wiesemann, Georghiou, Primal and dual linear decision rules in stochastic and robust optimization, Optimization Online 2009/02/2218, p. 22, Theorem 3
Human review
  • Endorsed by Shuze Chen ยท Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 ยท Oct 7, 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