Proof of Theorem 2.1, p. 583 — holds iff some works for every
ProvedMinimaxSLP.ObjSDP.constraint_iffminimaxp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semi-infinite-programming
Let , , satisfy Assumption 3 ( for every ), let have a nonempty recourse set , and fix a piece with . For a symmetric , and , the constraint
is equivalent to
The left side quantifies "for all , there is a " (through the minimum defining ); the right side has one for all . This exchange of quantifiers is what turns the semi-infinite dual (6) into the finite semidefinite program (8).
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_ObjSDP_Model open MeasureTheory Matrix
Formal statement
namespace MinimaxSLP.ObjSDP
/-- Proof of Theorem 2.1 (p. 583): for `Y` symmetric and `α_k ≥ 0`, the constraint `(𝒞_k)`
`∀ q ∈ ℝ^d, q′Yq + q′y + y₀ ≥ α_k 𝒬(q, x) + β_k` is equivalent to
`∃ w_k ∈ X(x), ∀ q ∈ ℝ^d, q′Yq + q′y + y₀ − α_k q′w_k − β_k ≥ 0`. -/
theorem constraint_iff {n r d K : ℕ}
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (h : Fin r → ℝ)
(α β : Fin K → ℝ) (k : Fin K) (hαk : 0 ≤ α k)
(hA3 : ∀ q : Fin d → ℝ, ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(x : Fin n → ℝ) (hrec : (recourseSet W T h x).Nonempty)
(Y : Matrix (Fin d) (Fin d) ℝ) (hY : Y.IsSymm) (y : Fin d → ℝ) (y₀ : ℝ) :
(∀ q : Fin d → ℝ, α k * Qval W T h q x + β k ≤ q ⬝ᵥ (Y *ᵥ q) + q ⬝ᵥ y + y₀) ↔
∃ w ∈ recourseSet W T h x, ∀ q : Fin d → ℝ,
0 ≤ q ⬝ᵥ (Y *ᵥ q) + q ⬝ᵥ y + y₀ - α k * (q ⬝ᵥ w) - β k := 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. 583, proof of Theorem 2.1 ("Thus the constraint (𝒞_k) is equivalent to the following constraint")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.