Proof of Theorem 3.3, p. 590 — every P ∈ 𝒫 gives a feasible point of (16) of equal value, so Ẑ(x) ≤ Ẑ_DD(x)
ProvedMinimaxSLP.RhsExtremal.Zhat_le_ZhatDDdualitymoment-problemp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Under Assumptions 2, 3 (at the constant ) and 5, and , fix . For every distribution (mean , second-moment matrix ):
- is -integrable;
- there is a feasible point of (16) whose objective value equals .
Moreover the objective of (16) is bounded above on its feasible set, and
In the paper the feasible point is formed from the probabilities of the events " attains " and the corresponding conditional first and second moments of . This is the upper half of the sandwich that proves Theorem 3.3.
Formalization Note The printed and are real sSups; the stronger per-distribution statement (items 1–2) and the bound on (16) make the inequality independent of junk values. Ties in the argmax are the prover's to break.
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_RhsExtremal_Model
Formal statement
namespace MinimaxSLP.RhsExtremal
open MeasureTheory Matrix
/-- Proof of Theorem 3.3, p. 590: every `P ∈ 𝒫` makes `𝕌(𝒬(·, x))` integrable and yields a
feasible point of (16) whose objective value equals `E_P[𝕌(𝒬(h̃, x))]` (the conditional moments
of `h̃` on the cells where the pair `(k, i)` attains the maximum); the objective of (16) is
bounded above on its feasible set; hence `Ẑ(x) = sup_{P ∈ 𝒫} E_P[𝕌(𝒬(h̃, x))] ≤ Ẑ_DD(x)`. -/
theorem Zhat_le_ZhatDD {r d n K N : ℕ} [NeZero K]
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (q : Fin d → ℝ)
(α β : Fin K → ℝ) (ps : Fin N → Fin r → ℝ) (μ : Fin r → ℝ) (Q : Matrix (Fin r) (Fin r) ℝ)
(hα : ∀ k, 0 ≤ α k)
(hA2 : ∀ z : Fin r → ℝ, ∃ w : Fin d → ℝ, 0 ≤ w ∧ W *ᵥ w = z)
(hA3 : ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(hA5 : Set.range ps = Set.extremePoints ℝ {π : Fin r → ℝ | Wᵀ *ᵥ π ≤ q})
(x : Fin n → ℝ) :
(∀ P ∈ MinimaxSLP.ObjSDP.momentClass μ Q,
Integrable (fun h => MinimaxSLP.ObjSDP.disutility α β (MinimaxSLP.RhsSDP.Qval W T q h x)) P ∧
∃ s ∈ feasible16 K N μ Q,
obj16 T α β ps x s = ∫ h, MinimaxSLP.ObjSDP.disutility α β (MinimaxSLP.RhsSDP.Qval W T q h x) ∂P) ∧
BddAbove (obj16 T α β ps x '' feasible16 K N μ Q) ∧
MinimaxSLP.RhsSDP.Zhat W T q α β μ Q x ≤ ZhatDD T α β ps μ Q x := by sorry
end MinimaxSLP.RhsExtremal
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 590, proof of Theorem 3.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.