p. 584 — the dual (6) is reformulated as the semidefinite program (8)
ProvedMinimaxSLP.ObjSDP.dual6_eq_dual8dualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let , , satisfy Assumption 3 ( for every ), let for all , and let have a nonempty recourse set . Then the set of objective values over the feasible points of the dual (6) equals the set of objective values over the feasible points of
In particular equals the optimal value of (8), and one is attained exactly when the other is.
This is the reformulation of the second-stage dual as a polynomial-sized semidefinite program; optimizing over as well gives (7).
Formalization Note The identity is stated for the sets of objective values (which gives the equality of the infima ZD and ZD8 as a second conjunct), so it holds without any assumption on the moments .
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_ObjSDP_Model open MeasureTheory Matrix
Formal statement
namespace MinimaxSLP.ObjSDP
/-- p. 584: the dual (6) can be reformulated as the semidefinite program (8). The two programs
have the same set of objective values, hence the same optimal value `Z_D(x)`, attained in one iff
attained in the other. -/
theorem dual6_eq_dual8 {n r d K : ℕ} [NeZero K]
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (h : Fin r → ℝ)
(α β : Fin K → ℝ) (hα : ∀ k, 0 ≤ α k)
(μ : Fin d → ℝ) (Q : Matrix (Fin d) (Fin d) ℝ)
(hA3 : ∀ q : Fin d → ℝ, ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(x : Fin n → ℝ) (hrec : (recourseSet W T h x).Nonempty) :
dualValues6 W T h α β μ Q x = dualValues8 W T h α β μ Q x ∧
ZD W T h α β μ Q x = ZD8 W T h α β μ Q x := by sorry
end MinimaxSLP.ObjSDP
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 584, (8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.