Proof of Theorem 2.2, p. 586 — the semidefinite program (9) has an optimal solution
ProvedMinimaxSLP.ObjExtremal.dual9_attainedattainmentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let , assume , Assumption 3 ( for all ), for all , and Assumption 4 ( symmetric, ). Then the maximization problem (9),
has an optimal solution: there is a feasible whose objective value is at least that of every feasible point.
The proof of Theorem 2.2 starts from such an optimal solution; the paper takes its existence for granted.
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_ObjExtremal_Model open MeasureTheory Matrix Filter Topology
Formal statement
namespace MinimaxSLP.ObjExtremal
/-- Proof of Theorem 2.2 (p. 586): the dual problem (9) has an optimal solution
`(V_k, v_k, v_k0, p_k)_{k}`, i.e. a feasible point whose objective value is the largest. -/
theorem dual9_attained {m₁ n r d K : ℕ} [NeZero K]
(A : Matrix (Fin m₁) (Fin n) ℝ) (b : Fin m₁ → ℝ)
(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) ℝ)
(hQ : Q.IsSymm) (hA4 : (Q - Matrix.vecMulVec μ μ).PosDef)
(hA3 : ∀ q : Fin d → ℝ, ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(x : Fin n → ℝ) (hx : x ∈ MinimaxSLP.ObjSDP.X A b) (hrec : (MinimaxSLP.ObjSDP.recourseSet W T h x).Nonempty) :
∃ s ∈ feasible9 W α μ Q, ∀ s' ∈ feasible9 W α μ Q, obj9 T h β x s' ≤ obj9 T h β x s := by sorry
end MinimaxSLP.ObjExtremal
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 586, proof of Theorem 2.2 (first sentence)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.