§3, pp. 7–8 — the constructed planes are cutting planes: 𝔔_{t+1} ≤ 𝒬̃_{t+1} and Q̲̃_{t+1,j} ≤ Q̃_{t+1,j} along every run
ProvedShapiroSDDP.Convergence.cut_validConsider the SAA problem with finite-valued cost-to-go functions on reachable decisions, valid initial cut sets , any oracle, and any run of the SDDP method (any forward samples and any choice of basic optimal dual solutions). Then for every iteration and every stage :
- every cut of the stage- set at iteration is a cutting plane of on reachable decisions:
so that there; 2. for every reachable , every outcome of stage and every feasible of the stage- problem, the point is feasible for the stage- problem with the iteration- cuts. Hence the optimal value of the problem with cuts is at most , and .
The paper notes that from on the constructed planes are supporting planes of but may be only cutting planes of . This statement is the "cutting plane" half of that remark, and it is the basis of the lower bound and of the convergence argument.
Formalization Note The cost-to-go values are evaluated only at reachable decisions, where they are genuine infima. Conclusion 2 avoids the infimum of the problem with cuts by exhibiting a feasible point of objective . No sampling hypothesis, (A1) or oracle property is needed.
import Mathlib import Definitions.Def_ShapiroSDDP_Convergence_Model import Definitions.Def_ShapiroSDDP_Convergence_SDDP
namespace ShapiroSDDP.Convergence
/-- §3, pp. 7–8: along every run of the SDDP method, every cut of every iteration is a cutting
plane of the SAA cost-to-go on reachable decisions, `α + βᵀ x ≤ 𝒬̃_{t+1}(x)`, so `𝔔_{t+1} ≤ 𝒬̃_{t+1}`;
and for every reachable `x_t`, outcome `j` and feasible `y` of the stage-`(t+1)` problem, the point
`(y, 𝒬̃_{t+2}(y))` is feasible for the stage-`(t+1)` problem with cuts, so that
`Q̲̃_{t+1,j}(x_t) ≤ Q̃_{t+1,j}(x_t)`. -/
theorem cut_valid (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 t, 1 ≤ t → t + 1 ≤ I.T → ∀ a ∈ cuts k t, ∀ x ∈ Reach I t, cutEval a x ≤ V I t x) ∧
∀ k t, 1 ≤ t → t + 1 ≤ I.T → ∀ x ∈ Reach I t, ∀ j : Fin (I.N (t + 1)),
∀ y ∈ Feas I t x j,
(y, V I (t + 1) y) ∈ CutLPFeas (I.A t j) (rhs I t x j) (cuts k (t + 1)) := by sorry
end ShapiroSDDP.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.