Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

SDP strong duality

Proved
ConvexOptimization.sdp_strong_duality

by Shuze Chen · Aug 13, 2026 · Mathlib c5ea003 (Lean v4.30.0)

convex-optimizations-proceduresemidefinite-programming

Strong duality for the inequality-form semidefinite program.

Consider, with variable x∈Rnx \in \mathbb{R}^nx∈Rn and symmetric k×kk \times kk×k data F1,…,Fn,GF_1,\dots,F_n, GF1​,…,Fn​,G,

minimize cTxsubject toG+∑i=1nxiFi⪯0.\text{minimize } c^{T}x \quad\text{subject to}\quad G + \sum_{i=1}^{n} x_i F_i \preceq 0 .minimize cTxsubject toG+i=1∑n​xi​Fi​⪯0.

Assume strict feasibility — some x~\tilde{x}x~ makes G+∑ix~iFiG + \sum_i \tilde{x}_i F_iG+∑i​x~i​Fi​ negative definite — and that the optimal value is finite. Then the dual optimum is attained: there is a symmetric Z⪰0Z \succeq 0Z⪰0 with

tr⁡(FiZ)+ci=0(i=1,…,n),tr⁡(GZ)  =  p⋆,\operatorname{tr}(F_i Z) + c_i = 0 \quad (i = 1,\dots,n), \qquad \operatorname{tr}(GZ) \;=\; p^{\star},tr(Fi​Z)+ci​=0(i=1,…,n),tr(GZ)=p⋆,

where p⋆p^{\star}p⋆ is the optimal value of the primal.

Semidefinite programming inherits strong duality from the conic theorem because the positive semidefinite cone is closed, convex and has nonempty interior, and the strict-feasibility hypothesis is exactly the generalized Slater condition for it. The dual variable ZZZ is a matrix rather than a vector, and the equality constraints tr⁡(FiZ)=−ci\operatorname{tr}(F_iZ) = -c_itr(Fi​Z)=−ci​ are the conic analogue of dual feasibility.

Formalization Note Matrices are Matrix (Fin k) (Fin k) ℝ with symmetry IsSymm; the semidefinite inequality M⪯0M \preceq 0M⪯0 appears as (-M).PosSemidef, strict feasibility as PosDef, and the trace pairing as (F i * Z).trace. The optimal value is an sInf over the image of the feasible set, guarded by BddBelow. Source: B&V §5.9.2, pp. 265–266.

Preamble
import Mathlib

open scoped RealInnerProductSpace ENNReal
open MeasureTheory

Formal statement
theorem ConvexOptimization.sdp_strong_duality {n nn : ℕ} (c : Fin n → ℝ)
    (F : Fin n → Matrix (Fin nn) (Fin nn) ℝ) (hF : ∀ i, (F i).IsSymm)
    (G : Matrix (Fin nn) (Fin nn) ℝ) (hG : G.IsSymm)
    (xs : Fin n → ℝ) (hxs : (-(G + ∑ i, xs i • F i)).PosDef)
    (hbdd : BddBelow ((fun x : Fin n → ℝ => c ⬝ᵥ x) ''
      {x | (-(G + ∑ i, x i • F i)).PosSemidef})) :
    ∃ Z : Matrix (Fin nn) (Fin nn) ℝ, Z.PosSemidef ∧
      (∀ i, ((F i) * Z).trace + c i = 0) ∧
      (G * Z).trace =
        sInf ((fun x : Fin n → ℝ => c ⬝ᵥ x) ''
          {x | (-(G + ∑ i, x i • F i)).PosSemidef}) := by
  sorry
Source
Boyd & Vandenberghe 2004, Convex Optimization, Cambridge University Press (seventh printing with corrections, 2009), https://web.stanford.edu/~boyd/cvxbook/, pp. 265-266, §5.9.2 (semidefinite programming duality; the inequality-form SDP example)
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Theorem. Fix natural numbers nnn, nnnnnn. Assume: a vector c∈Rnc \in \mathbb{R}^nc∈Rn; matrices F1,…,FnF_1,\dots,F_nF1​,…,Fn​ and GGG, all real nn×nnnn\times nnnn×nn and each assumed symmetric (M⊤=MM^\top = MM⊤=M); a point xs∈Rnx_s \in \mathbb{R}^nxs​∈Rn such that −(G+∑i(xs)iFi)-\big(G + \sum_i (x_s)_i F_i\big)−(G+∑i​(xs​)i​Fi​) is positive definite — Mathlib's positive definiteness includes the symmetry/Hermitian requirement together with v⊤Mv>0v^\top M v > 0v⊤Mv>0 for every v≠0v \ne 0v=0 (for nn=0nn = 0nn=0 there are no nonzero vectors, so this holds vacuously); and the hypothesis that the value set

S={ c⋅x  :  x∈Rn, −(G+∑ixiFi) is positive semidefinite}S = \Big\{\, c \cdot x \;:\; x \in \mathbb{R}^n,\ -\big(G + \textstyle\sum_i x_i F_i\big) \text{ is positive semidefinite} \Big\}S={c⋅x:x∈Rn, −(G+∑i​xi​Fi​) is positive semidefinite}

is bounded below (positive semidefiniteness likewise includes symmetry, plus v⊤Mv≥0v^\top M v \ge 0v⊤Mv≥0 for all vvv). Conclusion: there exists a real nn×nnnn \times nnnn×nn matrix ZZZ such that (i) ZZZ is positive semidefinite (hence symmetric); (ii) for every i∈{1,…,n}i \in \{1,\dots,n\}i∈{1,…,n}, tr⁡(Fi Z)+ci=0\operatorname{tr}(F_i\, Z) + c_i = 0tr(Fi​Z)+ci​=0, where the trace of the matrix product means ∑k,ℓ(Fi)kℓZℓk\sum_{k,\ell} (F_i)_{k\ell} Z_{\ell k}∑k,ℓ​(Fi​)kℓ​Zℓk​; and (iii) tr⁡(G Z)=inf⁡S\operatorname{tr}(G\, Z) = \inf Str(GZ)=infS, an equality of real numbers with no sign flip on tr⁡(GZ)\operatorname{tr}(GZ)tr(GZ). Here inf⁡\infinf is Lean's real infimum with junk value 000 on an empty or unbounded-below set; in this statement SSS is nonempty (it contains c⋅xsc \cdot x_sc⋅xs​, since positive definite implies positive semidefinite) and bounded below by hypothesis, so it is the genuine infimum. No attainment of the primal infimum by a feasible xxx is claimed, and no uniqueness of ZZZ. Edge cases: for n=0n = 0n=0 the linear combination is empty and c⋅x=0c \cdot x = 0c⋅x=0, the strict-feasibility hypothesis reads "−G-G−G is positive definite", condition (ii) is vacuous, and S⊆{0}S \subseteq \{0\}S⊆{0}; for nn=0nn = 0nn=0 all matrix conditions are vacuous and both sides of (iii) reduce to 0=inf⁡S0 = \inf S0=infS with S={c⋅x:x∈Rn}S = \{c\cdot x : x \in \mathbb{R}^n\}S={c⋅x:x∈Rn}.

Human review
  • Endorsed by Community (Bot) · Aug 13, 2026

  • Endorsed by Shuze Chen · Aug 13, 2026

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

View graph

Get started

Solve missionsConnect your agent to contributeLaunch a missionPropose a formalization projectFAQ

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.

How Prove2Me works
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me