Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, primal part — MSPu\mathcal{MSP}^uMSPu is equivalent to the linear program (4.2)

Proved
PrimalDualLDR.Multistage.theorem_3_primal

by tianyipeng · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-decision-ruleslinear-programmingmultistagestochastic-programming

Consider the linear multistage stochastic program MSP\mathcal{MSP}MSP of §4 with deterministic constraint matrices AtsA_{ts}Ats​, right-hand sides bt(ξt)=BtPtξb_t(\xi^t) = B_tP_t\xibt​(ξt)=Bt​Pt​ξ and costs ct(ξt)=CtPtξc_t(\xi^t) = C_tP_t\xict​(ξt)=Ct​Pt​ξ, and 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). Fix matrices Mt∈Rk×ktM_t \in \mathbb R^{k\times k^t}Mt​∈Rk×kt.

The primal linear-decision-rule problem

MSPu:min⁡∑tTr⁡(PtMPt⊤Ct⊤Xt)  s.t.  ∑sAtsXsPsMtPtξ+StPtξ=BtPtξ,  StPtξ≥0  P-a.s. ∀t\mathcal{MSP}^u:\quad \min \sum_t \operatorname{Tr}(P_tMP_t^\top C_t^\top X_t)\ \text{ s.t. }\ \sum_s A_{ts}X_sP_sM_tP_t\xi + S_tP_t\xi = B_tP_t\xi,\ \ S_tP_t\xi \ge 0\ \ \mathbb P\text{-a.s.}\ \forall tMSPu:mint∑​Tr(Pt​MPt⊤​Ct⊤​Xt​)  s.t.  s∑​Ats​Xs​Ps​Mt​Pt​ξ+St​Pt​ξ=Bt​Pt​ξ,  St​Pt​ξ≥0  P-a.s. ∀t

has the same optimal value as the linear program

(4.2):min⁡∑tTr⁡(PtMPt⊤Ct⊤Xt)  s.t.  ∑sAtsXsPsMtPt+ΛtW=BtPt,  Λth≥0,  Λt≥0  ∀t.(4.2):\quad \min \sum_t \operatorname{Tr}(P_tMP_t^\top C_t^\top X_t)\ \text{ s.t. }\ \sum_s A_{ts}X_sP_sM_tP_t + \Lambda_tW = B_tP_t,\ \ \Lambda_th \ge 0,\ \ \Lambda_t \ge 0\ \ \forall t.(4.2):mint∑​Tr(Pt​MPt⊤​Ct⊤​Xt​)  s.t.  s∑​Ats​Xs​Ps​Mt​Pt​+Λt​W=Bt​Pt​,  Λt​h≥0,  Λt​≥0  ∀t.

Optimal values are infima in the extended reals (+∞+\infty+∞ if infeasible, −∞-\infty−∞ if unbounded). This is the first assertion of Theorem 3; it needs only the support assumptions (the conditional-mean and strict-feasibility hypotheses of Theorem 3 are not used, so they are omitted, which makes the statement slightly stronger). The proof is the robust-counterpart argument of §2: an almost surely nonnegative linear function is nonnegative on the support Ξ\XiΞ, and by the affine Farkas lemma this is equivalent to the existence of the multipliers Λt\Lambda_tΛt​.

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), first assertion: if `P` has a polyhedral support of the type (2.1) (the
standing assumptions of §4), then the primal linear-decision-rule problem `𝓜𝒮𝒫^u` and the linear
program (4.2) have the same optimal value. Only the standing assumptions are needed for this half;
the linear-conditional-mean and strict-feasibility hypotheses of Theorem 3 are not used. -/
theorem theorem_3_primal (σ : Setting) (hσ : σ.Standing) :
    σ.valMSPu = σ.valLP42 := 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 (first assertion: MSP^u is equivalent to (4.2)); the argument parallels Theorem 1 / (2.3), pp. 5-6

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