§3.1, p. 10 — a problem of the form (3.13)/(3.14) with finite optimal value has an optimal solution
ProvedShapiroSDDP.Convergence.attainmentattainmentcutting-planelinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , , and let be a finite set of affine functions . Consider the linear program
which is problem (3.13) or (3.14) written with the epigraph variable of the convex piecewise linear approximation . If this problem has a finite optimal value, that is, it is feasible and its objective is bounded below on the feasible set, then it has an optimal solution .
This is the step that turns assumption (A1) into the existence of the forward decisions (3.13)–(3.14) used by the algorithm.
Formalization Note "Finite optimal value" is stated as feasibility plus a lower bound on the objective, not through an infimum.
Preamble
import Mathlib import Definitions.Def_ShapiroSDDP_Convergence_Model import Definitions.Def_ShapiroSDDP_Convergence_SDDP
Formal statement
namespace ShapiroSDDP.Convergence
/-- §3.1, p. 10: a linear program of the form (3.13)/(3.14), i.e. minimize `cᵀ y + θ` subject to
`A y = h`, `y ≥ 0` and `θ ≥ α + βᵀ y` for each cut `(α, β)` of a finite set `C`, that has a finite
optimal value (feasible, objective bounded below) has an optimal solution. -/
theorem attainment {n m : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (h : Fin m → ℝ)
(C : Finset (ℝ × (Fin n → ℝ))) (c : Fin n → ℝ) (hfin : CutLPFinite A h C c) :
∃ p, IsCutLPOpt A h C c p := by sorry
end ShapiroSDDP.Convergence
Source
Shapiro, Analysis of Stochastic Dual Dynamic Programming Method, Optimization Online 2009/12/2509, p. 10, §3.1, after (A1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.