§3.1, p. 10 — with basic optimal solutions, the number of cutting planes of the form (3.17) is finite
ProvedShapiroSDDP.Convergence.finite_cutsFix a stage and a finite set of cuts of stage (the current ). Then there is a finite set of affine functions of , not depending on the trial point, with the following property: for every trial decision and every choice, for each outcome , of a basic optimal solution of the dual of the stage- problem
the cutting plane (3.17) built from these duals at ,
belongs to .
It is the finiteness statement on which the finite convergence of the method rests.
Formalization Note The set is required not to depend on ; the dual feasible regions do not depend on , only their objectives do. Finiteness is of cuts for a fixed next-stage cut set , not of dual solutions overall, since the number of dual variables grows with .
import Mathlib import Definitions.Def_ShapiroSDDP_Convergence_Model import Definitions.Def_ShapiroSDDP_Convergence_SDDP
namespace ShapiroSDDP.Convergence
/-- §3.1, p. 10: when basic optimal dual solutions are used, only finitely many cutting planes
(3.17) can arise. For a stage `1 ≤ t ≤ T − 1` and a fixed cut set `D` of stage `t + 1` there is a
finite set `F` of cuts, not depending on the trial point, containing the cut (3.17) computed at
every trial point `x̄` from every choice of basic optimal dual solutions of the `N_{t+1}`
stage-`(t+1)` problems at `x̄` with the cut set `D`. -/
theorem finite_cuts (I : Instance) (t : ℕ) (ht : 1 ≤ t) (ht' : t + 1 ≤ I.T)
(D : Finset (Cut I (t + 1))) :
∃ F : Finset (Cut I t), ∀ (x : Fin (I.n t) → ℝ)
(d : Fin (I.N (t + 1)) → CutDual (I.m (t + 1)) D),
(∀ j, IsBasicOptDual (I.A t j) (rhs I t x j) D (I.c t j) (d j)) →
cutAt I t x D d ∈ F := by sorry
end ShapiroSDDP.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.