Proof of Proposition 3.1, pp. 10–11 — a policy is optimal for the SAA problem iff it satisfies the DP conditions (3.18)
ProvedShapiroSDDP.Convergence.optimal_iff_dpAssume the SAA cost-to-go functions are finite valued on reachable decisions. Let , , be an implementable policy of the SAA problem. Then the policy is optimal, that is feasible with minimal expected cost
among all feasible implementable policies, if and only if the dynamic programming optimality conditions
hold for and every scenario of the SAA problem, where at stage 1 the constraint is (the paper's convention ) and .
The paper recalls this as a classical result (p. 6 and p. 10); in the proof of Proposition 3.1 it reduces optimality of the forward policy to (3.18).
Formalization Note Optimality is defined by expected cost, so this equivalence is not definitional. Since every scenario has positive probability , (3.18) must hold on every scenario, not only almost surely.
import Mathlib import Definitions.Def_ShapiroSDDP_Convergence_Model
namespace ShapiroSDDP.Convergence
/-- Proof of Proposition 3.1, pp. 10–11 (and §3, p. 6): with finite-valued cost-to-go functions, an
implementable policy of the SAA problem is optimal (minimal expected cost (3.15) among feasible
implementable policies) if and only if it satisfies the dynamic programming optimality conditions
(3.18) at every stage and on every scenario. -/
theorem optimal_iff_dp (I : Instance) (hfin : FiniteValued I) (pol : Policy I)
(hpol : IsImplementable I pol) :
IsOptimalPolicy I pol ↔ DPOptimal I pol := by sorry
end ShapiroSDDP.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.