§2, p. 4 — the optimal values C^k_t of [AP^k_t] are nondecreasing in k
ProvedSDDPConv.Doasa.monotonicityConsider any run of the batched cutting-plane scheme (covering DOASA and DOASA-N) on an instance satisfying (A4). Since cuts are added from one iteration to the next and none is removed, the optimal values of the approximate problems are nondecreasing: for every iteration ,
for every reachable stage- decision and every outcome . For both sides equal .
Monotonicity is the elementary fact behind every lower-bound argument for cutting-plane methods: the lower bounds can only improve.
Formalization Note The paper states the inequality for every ; we state it on reachable states, where (A4) makes the approximate problems feasible and bounded (elsewhere the values are junk). The validity of the initial cuts and the oracle specification are not needed. Lean iteration is the paper's iteration .
import Mathlib import Definitions.Def_SDDPConv_Doasa_Model import Definitions.Def_SDDPConv_Doasa_Cuts import Definitions.Def_SDDPConv_Doasa_Run
namespace SDDPConv.Doasa
/-- §2, p. 4: since cuts are only added, the optimal values of the approximate problems are
nondecreasing from one iteration to the next, at every reachable state and outcome. -/
theorem monotonicity (I : Instance) (hA4 : A4 I) (L : ℕ → ℝ) (sol : Oracle I)
(F : ℕ → List (Scen I)) (S : ℕ → Scen I → (t : ℕ) → Finset (Fin (I.q t)))
(cuts : ℕ → (t : ℕ) → List (Cut I t)) (D : ℕ → (t : ℕ) → Set (Dual I t))
(hrun : IsBatchRun I L sol F S cuts D) (k : ℕ) :
apVal I 1 (cutset I cuts k 1) I.b₁ ≤ apVal I 1 (cutset I cuts (k + 1) 1) I.b₁ ∧
∀ s, 1 ≤ s → s + 1 ≤ I.T → ∀ x ∈ Reach I s, ∀ i : Fin (I.q (s + 1)),
apVal I (s + 1) (cutset I cuts k (s + 1)) (rhs I s x i) ≤
apVal I (s + 1) (cutset I cuts (k + 1) (s + 1)) (rhs I s x i) := by sorry
end SDDPConv.Doasa
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.