§3, p. 8 — the optimal value ϑ_k of (3.13) at iteration k is at most the optimal value of the SAA problem
ProvedShapiroSDDP.Convergence.lower_boundlower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sddp
Under the assumptions of the cut-validity statement (finite-valued cost-to-go functions on reachable decisions, valid initial cuts, any run of the SDDP method), let be the optimal value of the first-stage problem (3.13) at iteration ,
If is finite, then
the optimal value (3.7) of the SAA problem.
This is the lower bound reported by the algorithm at each iteration.
Formalization Note is the infimum of the LP (3.13) in epigraph form with the iteration- stage-1 cut set; it is genuine because the hypothesis states that this LP is feasible and bounded below. The optimal value (3.7) is then also a genuine infimum.
Preamble
import Mathlib import Definitions.Def_ShapiroSDDP_Convergence_Model import Definitions.Def_ShapiroSDDP_Convergence_SDDP
Formal statement
namespace ShapiroSDDP.Convergence
/-- §3, p. 8: along every run, the optimal value `ϑ_k` of problem (3.13) at iteration `k`, whenever
it is finite, is at most the optimal value (3.7) of the SAA problem. -/
theorem lower_bound (I : Instance) (hfin : FiniteValued I) (C₀ : (t : ℕ) → Finset (Cut I t))
(hC₀ : ValidInit I C₀) (sol : Oracle I) {M : ℕ} (ω : ℕ → Fin M → Scen I)
(cuts : ℕ → (t : ℕ) → Finset (Cut I t)) (hrun : IsRun I C₀ sol ω cuts) (k : ℕ)
(hk : CutLPFinite I.A₁ I.b₁ (cuts k 1) I.c₁) :
cutLPVal I.A₁ I.b₁ (cuts k 1) I.c₁ ≤ optVal I := by sorry
end ShapiroSDDP.Convergence
Source
Shapiro, Analysis of Stochastic Dual Dynamic Programming Method, Optimization Online 2009/12/2509, p. 8, §3, after (3.13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.