Theorem 2.1, p. 583 — with random objective, the risk-averse minimax problem (2) equals the semidefinite program (7)
ProvedMinimaxSLP.ObjSDP.theorem_2_1Consider the two-stage minimax problem (2) with random objective and constant right-hand side :
where , , with , and is the class of distributions with mean and second-moment matrix . Assume:
- is nonempty and bounded (Assumption 1);
- for every ;
- for every (Assumption 3);
- is symmetric and (Assumption 4).
Then equals the optimal value of the semidefinite program
both values being finite (the objective values of (2) are bounded below with greatest lower bound , those of (7) with greatest lower bound ), and . Moreover, for every the worst-case expected disutility equals the optimal value of the semidefinite program (8) obtained from (7) by fixing .
The theorem reduces a minimax stochastic linear program over an infinite-dimensional set of distributions to a single semidefinite program whose size is polynomial in , , and .
Formalization Note Assumption 2 (complete recourse) and Assumption 3 for all , as printed on p. 582, cannot both hold when ; the proof of Theorem 2.1 uses Assumption 3 for all and only the nonemptiness of for , which replaces Assumption 2 here. The printed minima are read as infima; attainment is not claimed. Distributions are measures with finite second moments rather than densities. The per- identity is the content of the last line of the paper's proof (" for all ").
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_ObjSDP_Model open MeasureTheory Matrix
namespace MinimaxSLP.ObjSDP
/-- Theorem 2.1 (p. 583): under Assumption 1, relatively complete recourse on `X` (in place of
Assumption 2, see the mission notes), Assumption 3 for all `q` and Assumption 4, the risk-averse
minimax problem (2) with random objective `q̃` and constant right-hand side `h` is equivalent to
the semidefinite program (7): both optimal values are genuine infima and `Z = Z_SDP`; moreover,
for every `x ∈ X`, `Z(x)` equals the optimal value of (8). -/
theorem theorem_2_1 {m₁ n r d K : ℕ} [NeZero K]
(A : Matrix (Fin m₁) (Fin n) ℝ) (b : Fin m₁ → ℝ) (c : Fin n → ℝ)
(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) ℝ)
(hA1 : (X A b).Nonempty ∧ Bornology.IsBounded (X A b))
(hrec : ∀ x ∈ X A b, (recourseSet W T h x).Nonempty)
(hA3 : ∀ q : Fin d → ℝ, ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(hQ : Q.IsSymm) (hA4 : (Q - Matrix.vecMulVec μ μ).PosDef) :
IsGLB (firstStageValues A b c W T h α β μ Q) (Z A b c W T h α β μ Q) ∧
IsGLB (values7 A b c W T h α β μ Q) (ZSDP A b c W T h α β μ Q) ∧
Z A b c W T h α β μ Q = ZSDP A b c W T h α β μ Q ∧
∀ x ∈ X A b, Zx W T h α β μ Q x = ZD8 W T h α β μ Q x := by sorry
end MinimaxSLP.ObjSDP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.