Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2, p. 589 — with random right-hand side and known dual extreme points, the minimax problem equals the SDP (14)

Proved
MinimaxSLP.RhsSDP.theorem_3_2

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

distributionally-robust-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingstochastic-programming

Consider the risk-averse minimax stochastic linear program with random right-hand side h~\tilde hh~ and constant objective qqq,

Z=min⁡x∈X(c′x+sup⁡P∈PEP[U(Q(h~,x))]),Z=\min_{x\in X}\Big(c'x+\sup_{P\in\mathcal P}\mathbb E_P\big[\mathbb U(\mathcal Q(\tilde h,x))\big]\Big),Z=x∈Xmin​(c′x+P∈Psup​EP​[U(Q(h~,x))]),

where X={x:Ax=b, x≥0}X=\{x : Ax=b,\ x\ge 0\}X={x:Ax=b, x≥0}, Q(h,x)=max⁡{(h−Tx)′p:W′p≤q}\mathcal Q(h,x)=\max\{(h-Tx)'p : W'p\le q\}Q(h,x)=max{(h−Tx)′p:W′p≤q}, U(t)=max⁡k(αkt+βk)\mathbb U(t)=\max_k(\alpha_kt+\beta_k)U(t)=maxk​(αk​t+βk​) and P\mathcal PP is the class of distributions on Rr\mathbb R^rRr with mean μ\muμ and second-moment matrix QQQ. Assume:

  1. XXX is nonempty and bounded (Assumption 1);
  2. αk≥0\alpha_k\ge 0αk​≥0 for all kkk;
  3. complete recourse, {Ww:w≥0}=Rr\{Ww : w\ge 0\}=\mathbb R^r{Ww:w≥0}=Rr (Assumption 2);
  4. {p:W′p≤q}≠∅\{p : W'p\le q\}\neq\emptyset{p:W′p≤q}=∅ (Assumption 3 at the constant qqq);
  5. QQQ is symmetric and Q≻μμ′Q\succ\mu\mu'Q≻μμ′ (Assumption 4);
  6. p1,…,pNp_1,\dots,p_Np1​,…,pN​ are the extreme points of {p:W′p≤q}\{p : W'p\le q\}{p:W′p≤q} (Assumption 5).

Then the problem is equivalent to the semidefinite program

Z^SDP=min⁡x,Y,y,y0 c′x+Q⋅Y+μ′y+y0s.t.(Y12(y−αkpi)12(y−αkpi)′y0+αkpi′Tx−βk)⪰0  ∀k,i,Ax=b, x≥0,(14)\hat Z_{\rm SDP}=\min_{x,Y,y,y_0}\ c'x+Q\cdot Y+\mu'y+y_0\quad\text{s.t.}\quad\begin{pmatrix}Y & \tfrac12(y-\alpha_k p_i)\\ \tfrac12(y-\alpha_k p_i)' & y_0+\alpha_k p_i'Tx-\beta_k\end{pmatrix}\succeq 0\ \ \forall k,i,\qquad Ax=b,\ x\ge 0, \tag{14}Z^SDP​=x,Y,y,y0​min​ c′x+Q⋅Y+μ′y+y0​s.t.(Y21​(y−αk​pi​)′​21​(y−αk​pi​)y0​+αk​pi′​Tx−βk​​)⪰0  ∀k,i,Ax=b, x≥0,(14)

in the following sense: for every x∈Xx\in Xx∈X the worst-case expected disutility Z^(x)\hat Z(x)Z^(x) equals the optimal value of (15); the infimum of c′x+Z^(x)c'x+\hat Z(x)c′x+Z^(x) over XXX and the infimum of the objective of (14) over its feasible set are the same real number Z^SDP\hat Z_{\rm SDP}Z^SDP​; and Z=Z^SDPZ=\hat Z_{\rm SDP}Z=Z^SDP​.

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 qqq (as printed, Assumption 3 "for all qqq" contradicts Assumption 2).

Preamble
import Mathlib
import Definitions.Def_MomentDRO_Conf_Setting
import Definitions.Def_WorstCaseVaR_KnownMoments_Basic
import Definitions.Def_MinimaxSLP_RhsSDP_Model
Formal statement
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
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 589, Theorem 3.2, (14); proof pp. 589–590
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