Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, p. 4 — the optimal values C^k_t of [AP^k_t] are nondecreasing in k

Proved
SDDPConv.Doasa.monotonicity

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

benders-cutsmonotonicityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sddp

Consider any run of the batched cutting-plane scheme (covering DOASA and DOASA-N) on an instance satisfying (A4). Since cuts are added from one iteration to the next and none is removed, the optimal values of the approximate problems are nondecreasing: for every iteration kkk,

C1k+1 ≥ C1k,Ctk+1(xt−1,ωti) ≥ Ctk(xt−1,ωti)(t=2,…,T),C^{k+1}_1\ \ge\ C^k_1,\qquad C^{k+1}_t(x_{t-1},\omega_{ti})\ \ge\ C^k_t(x_{t-1},\omega_{ti})\quad(t=2,\dots,T),C1k+1​ ≥ C1k​,Ctk+1​(xt−1​,ωti​) ≥ Ctk​(xt−1​,ωti​)(t=2,…,T),

for every reachable stage-(t−1)(t-1)(t−1) decision xt−1x_{t-1}xt−1​ and every outcome ωti\omega_{ti}ωti​. For t=Tt=Tt=T both sides equal QT(xT−1,ωTi)Q_T(x_{T-1},\omega_{Ti})QT​(xT−1​,ωTi​).

Monotonicity is the elementary fact behind every lower-bound argument for cutting-plane methods: the lower bounds C1kC^k_1C1k​ can only improve.

Formalization Note The paper states the inequality for every xt−1x_{t-1}xt−1​; we state it on reachable states, where (A4) makes the approximate problems feasible and bounded (elsewhere the values are junk). The validity of the initial cuts and the oracle specification are not needed. Lean iteration kkk is the paper's iteration k+1k+1k+1.

Preamble
import Mathlib
import Definitions.Def_SDDPConv_Doasa_Model
import Definitions.Def_SDDPConv_Doasa_Cuts
import Definitions.Def_SDDPConv_Doasa_Run
Formal statement
namespace SDDPConv.Doasa

/-- §2, p. 4: since cuts are only added, the optimal values of the approximate problems are
nondecreasing from one iteration to the next, at every reachable state and outcome. -/
theorem monotonicity (I : Instance) (hA4 : A4 I) (L : ℕ → ℝ) (sol : Oracle I)
    (F : ℕ → List (Scen I)) (S : ℕ → Scen I → (t : ℕ) → Finset (Fin (I.q t)))
    (cuts : ℕ → (t : ℕ) → List (Cut I t)) (D : ℕ → (t : ℕ) → Set (Dual I t))
    (hrun : IsBatchRun I L sol F S cuts D) (k : ℕ) :
    apVal I 1 (cutset I cuts k 1) I.b₁ ≤ apVal I 1 (cutset I cuts (k + 1) 1) I.b₁ ∧
      ∀ s, 1 ≤ s → s + 1 ≤ I.T → ∀ x ∈ Reach I s, ∀ i : Fin (I.q (s + 1)),
        apVal I (s + 1) (cutset I cuts k (s + 1)) (rhs I s x i) ≤
          apVal I (s + 1) (cutset I cuts (k + 1) (s + 1)) (rhs I s x i) := by sorry

end SDDPConv.Doasa
Source
Philpott & Guan, On the convergence of stochastic dual dynamic programming and related methods, authors' manuscript v24 (2008-02-25), p. 4, §2, monotonicity of the optimal values of [AP^k_t]
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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