Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Proposition 3.1, p. 10 — a policy satisfying the DP optimality conditions (3.18) is optimal for the SAA problem

Proved
ShapiroSDDP.Convergence.dp_implies_optimal

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

dynamic-programmingmultistagesddpstochastic-programming

Consider the SAA of a multistage linear stochastic program with T≥2T\ge2T≥2 stages, whose cost-to-go functions Q~t+1\widetilde{\mathcal Q}_{t+1}Q​t+1​ are finite valued on reachable decisions. Let xˉt=xˉt(ξ~[t])\bar x_t=\bar x_t(\tilde\xi_{[t]})xˉt​=xˉt​(ξ~​[t]​), t=1,…,Tt=1,\dots,Tt=1,…,T, be an implementable policy that satisfies the dynamic programming optimality conditions (3.18) on every scenario:

xˉt(ξ~[t])∈arg⁡min⁡xt{c~t⊤xt+Q~t+1(xt): B~txˉt−1(ξ~[t−1])+A~txt=b~t, xt≥0},t=1,…,T,\bar x_t(\tilde\xi_{[t]})\in\arg\min_{x_t}\big\{\tilde c_t^\top x_t+\widetilde{\mathcal Q}_{t+1}(x_t):\ \tilde B_t\bar x_{t-1}(\tilde\xi_{[t-1]})+\tilde A_tx_t=\tilde b_t,\ x_t\ge0\big\},\qquad t=1,\dots,T,xˉt​(ξ~​[t]​)∈argxt​min​{c~t⊤​xt​+Q​t+1​(xt​): B~t​xˉt−1​(ξ~​[t−1]​)+A~t​xt​=b~t​, xt​≥0},t=1,…,T,

with B~1=0\tilde B_1=0B~1​=0 and Q~T+1≡0\widetilde{\mathcal Q}_{T+1}\equiv0Q​T+1​≡0. Then xˉ\bar xxˉ is an optimal policy of the SAA problem: it is feasible, and its expected cost 1N∑s∑t=1Tc~t(s)⊤xˉt(s)\frac1N\sum_{s}\sum_{t=1}^T\tilde c_t(s)^\top\bar x_t(s)N1​∑s​∑t=1T​c~t​(s)⊤xˉt​(s) (3.15) is at most the expected cost of every feasible implementable policy.

This is the "if" direction of the equivalence "a policy is optimal for the SAA problem iff (3.18) holds", which the proof of Proposition 3.1 uses to conclude that the forward-step policy is optimal once the cutting-plane approximations are exact along all forward paths.

Preamble
import Mathlib
import Definitions.Def_ShapiroSDDP_Convergence_Model
Formal statement
namespace ShapiroSDDP.Convergence

/-- Proof of Proposition 3.1, p. 10 (sufficiency half of the dynamic programming optimality
conditions (3.18)): with finite-valued cost-to-go functions, an implementable policy that satisfies
(3.18) at every stage and on every scenario of the SAA problem is optimal, i.e. it is feasible and
its expected cost (3.15) is at most that of every feasible implementable policy. -/
theorem dp_implies_optimal (I : Instance) (hfin : FiniteValued I) (pol : Policy I)
    (hpol : IsImplementable I pol) (hdp : DPOptimal I pol) : IsOptimalPolicy I pol := by sorry

end ShapiroSDDP.Convergence
Source
Shapiro, Analysis of Stochastic Dual Dynamic Programming Method, Optimization Online 2009/12/2509, p. 10, proof of Proposition 3.1 (sufficiency of the dynamic programming optimality conditions (3.18))

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