Proof of Theorem 2.1, p. 583 — the Sion exchange
ProvedMinimaxSLP.ObjSDP.sion_exchangeconvex-analysisminimaxp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a nonempty bounded recourse set, let , and (in the paper , ), and put
Then, with values in the extended reals,
and the maximum on the right is attained at some .
This is the application of Sion's minimax theorem in the proof of Theorem 2.1: is convex in because and affine in , and is compact and convex.
Formalization Note The values are taken in EReal, because when is not in the range of . The supremum over is written as an EReal supremum, and its attainment on the right is stated explicitly.
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_ObjSDP_Model open MeasureTheory Matrix
Formal statement
namespace MinimaxSLP.ObjSDP
/-- Proof of Theorem 2.1 (p. 583), the Sion step: for `Y ⪰ 0`, `a = α_k ≥ 0` (any real `a`
works) and a nonempty bounded recourse set `X(x)`, with
`g(q, w) = q′Yq + q′y + y₀ − a q′w − b`,
`inf_{q ∈ ℝ^d} max_{w ∈ X(x)} g(q, w) = max_{w ∈ X(x)} inf_{q ∈ ℝ^d} g(q, w)`,
and the outer maximum on the right is attained. Values are taken in `EReal`, because
`inf_q g(q, w)` is `−∞` for some `w`. -/
theorem sion_exchange {n r d : ℕ}
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (h : Fin r → ℝ)
(x : Fin n → ℝ) (hrec : (recourseSet W T h x).Nonempty)
(hbdd : Bornology.IsBounded (recourseSet W T h x))
(Y : Matrix (Fin d) (Fin d) ℝ) (hY : Y.PosSemidef) (y : Fin d → ℝ) (y₀ a b : ℝ) :
(⨅ q : Fin d → ℝ, ⨆ w ∈ recourseSet W T h x,
((q ⬝ᵥ (Y *ᵥ q) + q ⬝ᵥ y + y₀ - a * (q ⬝ᵥ w) - b : ℝ) : EReal)) =
(⨆ w ∈ recourseSet W T h x, ⨅ q : Fin d → ℝ,
((q ⬝ᵥ (Y *ᵥ q) + q ⬝ᵥ y + y₀ - a * (q ⬝ᵥ w) - b : ℝ) : EReal)) ∧
∃ w₀ ∈ recourseSet W T h x,
(⨅ q : Fin d → ℝ, ((q ⬝ᵥ (Y *ᵥ q) + q ⬝ᵥ y + y₀ - a * (q ⬝ᵥ w₀) - b : ℝ) : EReal)) =
⨆ w ∈ recourseSet W T h x, ⨅ q : Fin d → ℝ,
((q ⬝ᵥ (Y *ᵥ q) + q ⬝ᵥ y + y₀ - a * (q ⬝ᵥ w) - b : ℝ) : EReal) := by sorry
end MinimaxSLP.ObjSDP
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 583, proof of Theorem 2.1 (Sion minimax step, citing Sion [25])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.