Proof of Proposition 3.1, p. 10 β finitely many realizations of π_t and of first-stage solutions; the approximations stabilize
ProvedShapiroSDDP.Convergence.finite_approxcutting-planefinitenessp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sddp
Fix the SAA data, the initial cut sets , the oracle and the number of forward scenarios per iteration, and consider all runs of the SDDP method (all forward samples, all choices of basic optimal dual solutions). Then:
- for every stage , only finitely many different cut sets occur as the stage- set of some run at some iteration; hence only finitely many different approximations arise;
- only finitely many different first-stage solutions of (3.13) arise;
- along every run, the cut sets are eventually constant: there is an iteration such that the cut sets of all stages at every iteration equal those at iteration .
The paper uses item 3 when it says "Since the total number of different realizations of functions is finite" (p. 11): cut sets only grow inside a finite universe.
Formalization Note The first-stage solutions are those returned by the deterministic oracle for the stage-1 cut sets. Stages outside never change.
Preamble
import Mathlib import Definitions.Def_ShapiroSDDP_Convergence_Model import Definitions.Def_ShapiroSDDP_Convergence_SDDP
Formal statement
namespace ShapiroSDDP.Convergence
/-- Proof of Proposition 3.1, pp. 10β11: with basic optimal dual solutions, the approximations
`π_t` and the first-stage solutions generated by the method range over finite sets. For fixed data,
initial cuts, oracle and number `M` of forward scenarios, (1) for every stage `t` the set of cut
sets `cuts k t` occurring in any run, at any iteration, for any forward samples, is finite; (2) the
set of first-stage solutions they produce is finite; and (3) along every run the cut sets are
eventually constant. -/
theorem finite_approx (I : Instance) (Cβ : (t : β) β Finset (Cut I t)) (sol : Oracle I) (M : β) :
(β t, {C : Finset (Cut I t) | β (Ο : β β Fin M β Scen I) (cuts : β β (t : β) β Finset (Cut I t))
(k : β), IsRun I Cβ sol Ο cuts β§ cuts k t = C}.Finite) β§
{x : Fin (I.n 1) β β | β (Ο : β β Fin M β Scen I)
(cuts : β β (t : β) β Finset (Cut I t)) (k : β),
IsRun I Cβ sol Ο cuts β§ x = sol.first (cuts k 1)}.Finite β§
β (Ο : β β Fin M β Scen I) (cuts : β β (t : β) β Finset (Cut I t)),
IsRun I Cβ sol Ο cuts β β K, β k, K β€ k β cuts k = cuts K := 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, first paragraph; p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.