Theorem 3, dual part — is equivalent to the linear program (4.6)
ProvedPrimalDualLDR.Multistage.theorem_3_duallinear-decision-ruleslinear-programmingmultistagestochastic-programming
Consider the linear multistage stochastic program of §4 with deterministic constraint matrices , , . Assume that has a polyhedral support of the type (2.1), that -a.s. for all , and that is strictly feasible. Assume moreover : , or some row of (a row of below the two rows of (2.1b)) is nonzero. Then the dual linear-decision-rule problem
has the same optimal value as the linear program
where and .
Optimal values are infima in the extended reals. This is the second assertion of Theorem 3. The hypothesis is not in the paper; it is the same repair as in the goal theorem PrimalDualLDR.Multistage.theorem_3, whose formalization note explains that without it the assertion fails for (the cone of Proposition 3 becomes all of ).
Preamble
import Mathlib import Definitions.Def_PrimalDualLDR_Multistage_Basic import Definitions.Def_PrimalDualLDR_Multistage_Setting import Definitions.Def_PrimalDualLDR_Multistage_Problems open MeasureTheory Matrix
Formal statement
namespace PrimalDualLDR.Multistage
/-- Theorem 3 (p. 22), second assertion: assume that `P` has a polyhedral support of the type (2.1),
while `𝔼_t(ξ) = M_t P_t ξ` almost surely, and that `𝓜𝒮𝒫` is strictly feasible. Under the repair
hypothesis `2 ≤ k ∨ Ŵ ≠ 0` (see the goal theorem `theorem_3`), the dual linear-decision-rule problem
`𝓜𝒮𝒫^l` and the linear program (4.6) have the same optimal value. -/
theorem theorem_3_dual (σ : Setting) (hσ : σ.Standing) (hM : σ.LinearCondMean)
(hsf : σ.StrictlyFeasible) (hW : 2 ≤ σ.k ∨ ∃ i : Fin σ.l, 2 ≤ i.val ∧ σ.W i ≠ 0) :
σ.valMSPl = σ.valLP46 := by sorry
end PrimalDualLDR.MultistageSource
Kuhn, Wiesemann, Georghiou, Primal and dual linear decision rules in stochastic and robust optimization, Optimization Online 2009/02/2218, p. 22, Theorem 3 (second assertion: MSP^l is equivalent to (4.6)); derivation pp. 20-22 (Lemmas 2, 3, (4.5)-(4.7)), parallel to the proof of Theorem 1 / (2.8), pp. 7-10