Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.2, p. 585 — distributions in P\mathcal PP asymptotically achieve Z(x)=ZD(x)=ZDD(x)Z(x)=Z_D(x)=Z_{DD}(x)Z(x)=ZD​(x)=ZDD​(x)

Proved
MinimaxSLP.ObjExtremal.theorem_2_2

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributionally-robust-optimizationextremal-distributionmoment-problemp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming

Consider the two-stage minimax stochastic linear program with random objective q~\tilde qq~​, first-stage region XXX, recourse set X(x)={w≥0:Ww=h−Tx}X(x)=\{w\ge0 : Ww=h-Tx\}X(x)={w≥0:Ww=h−Tx}, second-stage cost Q(q,x)=min⁡w∈X(x)q′w\mathcal Q(q,x)=\min_{w\in X(x)}q'wQ(q,x)=minw∈X(x)​q′w, disutility U(t)=max⁡k(αkt+βk)\mathbb U(t)=\max_k(\alpha_kt+\beta_k)U(t)=maxk​(αk​t+βk​) with αk≥0\alpha_k\ge0αk​≥0, and moment class P\mathcal PP of distributions on Rd\mathbb R^dRd with mean μ\muμ and second-moment matrix QQQ. Assume X(x)≠∅X(x)\neq\emptysetX(x)=∅, Assumption 3 ({p:W′p≤q}≠∅\{p : W'p\le q\}\neq\emptyset{p:W′p≤q}=∅ for every q∈Rdq\in\mathbb R^dq∈Rd) and Assumption 4 (QQQ symmetric, Q−μμ′≻0Q-\mu\mu'\succ0Q−μμ′≻0).

Theorem 2.2. For an arbitrary x∈Xx\in Xx∈X:

  1. there is a sequence (Pj)j≥1(P_j)_{j\ge1}(Pj​)j≥1​ of distributions in P\mathcal PP with
lim⁡j→∞EPj[U(Q(q~,x))]=Z(x);\lim_{j\to\infty}\mathbb E_{P_j}\big[\mathbb U(\mathcal Q(\tilde q,x))\big]=Z(x);j→∞lim​EPj​​[U(Q(q~​,x))]=Z(x);
  1. the three optimal values are finite and genuine: Z(x)Z(x)Z(x) is the supremum of the values EP[U(Q(q~,x))]\mathbb E_P[\mathbb U(\mathcal Q(\tilde q,x))]EP​[U(Q(q~​,x))], P∈PP\in\mathcal PP∈P; ZD(x)Z_D(x)ZD​(x) is the infimum of the objective of the dual (6) over its (nonempty) feasible set; and ZDD(x)Z_{DD}(x)ZDD​(x) is the supremum of the objective of the semidefinite program (9) over its (nonempty) feasible set;
  2. they coincide:
Z(x)=ZD(x)=ZDD(x).Z(x)=Z_D(x)=Z_{DD}(x).Z(x)=ZD​(x)=ZDD​(x).

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 r≥1r\ge1r≥1; this statement uses what §2's proofs use: Assumption 3 for all qqq and nonempty recourse sets X(x)X(x)X(x) in place of complete recourse. Assumption 1 (boundedness of XXX) is not used and is omitted. The printed max of (9) is attained (a separate milestone); here ZDD(x)Z_{DD}(x)ZDD​(x) is its supremum.

Preamble
import Mathlib
import Definitions.Def_MomentDRO_Conf_Setting
import Definitions.Def_MinimaxSLP_ObjExtremal_Model

open MeasureTheory Matrix Filter Topology
Formal statement
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
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 585, Theorem 2.2 (proof pp. 586–587)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me