Theorem 3.2, p. 589 — with random right-hand side and known dual extreme points, the minimax problem equals the SDP (14)
ProvedMinimaxSLP.RhsSDP.theorem_3_2Consider the risk-averse minimax stochastic linear program with random right-hand side and constant objective ,
where , , and is the class of distributions on with mean and second-moment matrix . Assume:
- is nonempty and bounded (Assumption 1);
- for all ;
- complete recourse, (Assumption 2);
- (Assumption 3 at the constant );
- is symmetric and (Assumption 4);
- are the extreme points of (Assumption 5).
Then the problem is equivalent to the semidefinite program
in the following sense: for every the worst-case expected disutility equals the optimal value of (15); the infimum of over and the infimum of the objective of (14) over its feasible set are the same real number ; and .
The theorem shows that, once the dual extreme points are available, the minimax problem — NP-hard in general (Theorem 3.1) — is a single semidefinite program, jointly in the first-stage decision and the dual multipliers.
Formalization Note The paper's "Assumption i" in the statement is read as Assumption 5 (see the proof's first line). The printed min are read as infima; both infima are asserted to be genuine (IsGLB), and attainment is not claimed. Assumptions 2 and 3 are used in the section-wise reading: complete recourse together with dual feasibility at the single constant (as printed, Assumption 3 "for all " contradicts Assumption 2).
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_WorstCaseVaR_KnownMoments_Basic import Definitions.Def_MinimaxSLP_RhsSDP_Model
namespace MinimaxSLP.RhsSDP
open MeasureTheory Matrix
/-- Theorem 3.2, p. 589 (printed "Assumption i" read as Assumption 5). Under Assumption 1 (`X`
nonempty and bounded), `α_k ≥ 0`, complete recourse (Assumption 2), `{π : W′π ≤ q} ≠ ∅`
(Assumption 3 at the constant `q`), Assumption 4 and Assumption 5, the risk-averse minimax
problem `min_{x ∈ MinimaxSLP.ObjSDP.X} (c′x + Ẑ(x))` with random right-hand side is equivalent to the joint
semidefinite program (14): for every `x ∈ MinimaxSLP.ObjSDP.X`, `Ẑ(x)` equals the optimal value of (15); the
infimum of `c′x + Ẑ(x)` over `X` and the infimum of `c′x + Q · Y + μ′y + y₀` over the feasible
set of (14) are both the real number `Ẑ_SDP`; and `Z = Ẑ_SDP`. -/
theorem theorem_3_2 {m₁ n r d K N : ℕ} [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) ℝ) (q : Fin d → ℝ)
(α β : Fin K → ℝ) (μ : Fin r → ℝ) (Q : Matrix (Fin r) (Fin r) ℝ)
(ps : Fin N → Fin r → ℝ)
(hA1 : (MinimaxSLP.ObjSDP.X A b).Nonempty ∧ Bornology.IsBounded (MinimaxSLP.ObjSDP.X A b))
(hα : ∀ k, 0 ≤ α k)
(hA2 : ∀ z : Fin r → ℝ, ∃ w : Fin d → ℝ, 0 ≤ w ∧ W *ᵥ w = z)
(hA3 : ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(hQ : Q.IsSymm) (hA4 : (Q - Matrix.vecMulVec μ μ).PosDef)
(hA5 : Set.range ps = Set.extremePoints ℝ {π : Fin r → ℝ | Wᵀ *ᵥ π ≤ q}) :
(∀ x ∈ MinimaxSLP.ObjSDP.X A b, Zhat W T q α β μ Q x = ZhatD15 T α β ps μ Q x) ∧
IsGLB (minimaxObj c W T q α β μ Q '' MinimaxSLP.ObjSDP.X A b) (ZhatSDP A b c T α β ps μ Q) ∧
IsGLB (obj14 c μ Q '' feasible14 A b T α β ps) (ZhatSDP A b c T α β ps μ Q) ∧
Zval A b c W T q α β μ Q = ZhatSDP A b c T α β ps μ Q := by sorry
end MinimaxSLP.RhsSDP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.