Theorem 2.2, p. 585 — distributions in asymptotically achieve
ProvedMinimaxSLP.ObjExtremal.theorem_2_2Consider the two-stage minimax stochastic linear program with random objective , first-stage region , recourse set , second-stage cost , disutility with , and moment class of distributions on with mean and second-moment matrix . Assume , Assumption 3 ( for every ) and Assumption 4 ( symmetric, ).
Theorem 2.2. For an arbitrary :
- there is a sequence of distributions in with
- the three optimal values are finite and genuine: is the supremum of the values , ; is the infimum of the objective of the dual (6) over its (nonempty) feasible set; and is the supremum of the objective of the semidefinite program (9) over its (nonempty) feasible set;
- they coincide:
The theorem identifies the worst-case expected disutility with the value of a semidefinite program whose optimal solution encodes the conditional moments of near-extremal distributions; the paper builds these distributions explicitly as mixtures of point masses and rare Gaussian perturbations.
Formalization Note Part 1 on its own is a property of every finite supremum, so the content of the theorem is in parts 2 and 3. Distributions are probability measures with finite second moments rather than densities. Assumptions 2 and 3 of the paper contradict each other as printed when ; this statement uses what §2's proofs use: Assumption 3 for all and nonempty recourse sets in place of complete recourse. Assumption 1 (boundedness of ) is not used and is omitted. The printed max of (9) is attained (a separate milestone); here is its supremum.
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_ObjExtremal_Model open MeasureTheory Matrix Filter Topology
namespace MinimaxSLP.ObjExtremal
/-- Theorem 2.2 (p. 585): for every `x ∈ MinimaxSLP.ObjSDP.X` there is a sequence of distributions in `𝒫` whose
expected disutilities converge to the optimal value `Z(x) = Z_D(x) = Z_DD(x)`. All three optimal
values are genuine (least upper bound of the primal values, greatest lower bound of the values of
(6), least upper bound of the values of (9)) and coincide. -/
theorem theorem_2_2 {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) :
(∃ P : ℕ → Measure (Fin d → ℝ), (∀ j, P j ∈ MinimaxSLP.ObjSDP.momentClass μ Q) ∧
Tendsto (fun j => ∫ q, MinimaxSLP.ObjSDP.disutility α β (MinimaxSLP.ObjSDP.Qval W T h q x) ∂(P j)) atTop
(𝓝 (MinimaxSLP.ObjSDP.Zx W T h α β μ Q x))) ∧
IsLUB (MinimaxSLP.ObjSDP.primalValues W T h α β μ Q x) (MinimaxSLP.ObjSDP.Zx W T h α β μ Q x) ∧
IsGLB (MinimaxSLP.ObjSDP.dualValues6 W T h α β μ Q x) (MinimaxSLP.ObjSDP.ZD W T h α β μ Q x) ∧
IsLUB (dualValues9 W T h α β μ Q x) (ZDD W T h α β μ Q x) ∧
MinimaxSLP.ObjSDP.Zx W T h α β μ Q x = MinimaxSLP.ObjSDP.ZD W T h α β μ Q x ∧
MinimaxSLP.ObjSDP.ZD W T h α β μ Q x = ZDD W T h α β μ Q x := by sorry
end MinimaxSLP.ObjExtremal
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.