Proof of Theorem 2.2, p. 587 — an optimal solution of (9) whose blocks have or vanish
ProvedMinimaxSLP.ObjExtremal.zero_weight_reductionextremal-distributionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let , assume , Assumption 3, for all and Assumption 4. Let be an optimal solution of (9). Then there is another feasible point of (9) with the same objective value (hence also optimal) and the same weights, for all , such that for every either
In particular, writing (the same set for both solutions),
This reduces the construction of the extremal distributions of Theorem 2.2 to the case where every block that is used has positive weight .
Formalization Note The paper's construction sets for and leaves unchanged, noting for . Here is required for the zero blocks; it gives the same objective value, by that identity.
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. 587): from an optimal solution of (9) one obtains an optimal
solution with the same objective value in which every block either has `v_k0 > 0` or is entirely
zero (`V_k = 0`, `v_k = 0`, `v_k0 = 0`, `p_k = 0`), and the weights `v_k0` are those of the
given solution; so with `L = {k : v_k0 = 0}` the blocks with `k ∉ L` alone sum to
`( Q μ ; μ′ 1 )`. -/
theorem zero_weight_reduction {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 : (Fin K → Matrix (Fin d) (Fin d) ℝ) × (Fin K → Fin d → ℝ) × (Fin K → ℝ) ×
(Fin K → Fin r → ℝ))
(hs : s ∈ feasible9 W α μ Q)
(hopt : ∀ s' ∈ feasible9 W α μ Q, obj9 T h β x s' ≤ obj9 T h β x s) :
∃ s' ∈ feasible9 W α μ Q, obj9 T h β x s' = obj9 T h β x s ∧
(∀ k, s'.2.2.1 k = s.2.2.1 k) ∧
∀ k, 0 < s'.2.2.1 k ∨
(s'.1 k = 0 ∧ s'.2.1 k = 0 ∧ s'.2.2.1 k = 0 ∧ s'.2.2.2 k = 0) := 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. 587, proof of Theorem 2.2 (the case v_k0 = 0 for k ∈ L)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.