Proof of Proposition 3.1, p. 10 — a policy satisfying the DP optimality conditions (3.18) is optimal for the SAA problem
ProvedShapiroSDDP.Convergence.dp_implies_optimaldynamic-programmingmultistagesddpstochastic-programming
Consider the SAA of a multistage linear stochastic program with stages, whose cost-to-go functions are finite valued on reachable decisions. Let , , be an implementable policy that satisfies the dynamic programming optimality conditions (3.18) on every scenario:
with and . Then is an optimal policy of the SAA problem: it is feasible, and its expected cost (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.ConvergenceSource
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))