Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
βŒ•
Log in
← Formalpedia

Theorem 7, p. 29 β€” if the quadratic eigenvalue multiplicity satisfies k β‰₯ m + 2, then conv(π’Ÿ) = π’Ÿ_SDP

Proved
QCQPTightness.MultHull.theorem_7

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

convex-hullp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qcqpquadratic-eigenvalue-multiplicitysdp-relaxation

Consider a QCQP (1) in NNN variables with mβ‰₯1m\ge1mβ‰₯1 constraints, qi(x)=x⊀Aix+2bi⊀x+ciq_i(x) = x^\top A_ix + 2b_i^\top x + c_iqi​(x)=x⊀Ai​x+2biβŠ€β€‹x+ci​, its epigraph D\mathcal DD (2) and the projected epigraph DSDP\mathcal D_{\mathrm{SDP}}DSDP​ (4) of its Shor SDP relaxation. Suppose Assumption 1 holds: the QCQP is feasible and some Ξ³βˆ—βˆˆRm\gamma^*\in\mathbb R^mΞ³βˆ—βˆˆRm with Ξ³iβˆ—β‰₯0\gamma^*_i\ge 0Ξ³iβˆ—β€‹β‰₯0 for i∈[ ⁣[mI] ⁣]i\in[\![m_I]\!]i∈[[mI​]] has A0+βˆ‘iΞ³iβˆ—Ai≻0A_0+\sum_i\gamma^*_iA_i\succ0A0​+βˆ‘i​γiβˆ—β€‹Ai​≻0. If the quadratic eigenvalue multiplicity kkk (the largest kkk with Ai=IkβŠ—AiA_i = I_k\otimes\mathbb A_iAi​=Ikβ€‹βŠ—Ai​ for all i∈[ ⁣[0,m] ⁣]i\in[\![0,m]\!]i∈[[0,m]], Definition 3) satisfies kβ‰₯m+2k\ge m+2kβ‰₯m+2, then

conv⁑(D)=DSDP.\operatorname{conv}(\mathcal D) = \mathcal D_{\mathrm{SDP}} .conv(D)=DSDP​.

Unlike Theorems 1 and 2 of the paper, this result needs neither the polyhedrality of Ξ“\GammaΞ“ (Assumption 3) nor the attainment Assumption 2: enough block symmetry in the quadratic forms alone forces the Shor relaxation to describe the convex hull of the epigraph exactly.

Formalization Note Constraint indices are shifted to {0,…,mβˆ’1}\{0,\dots,m-1\}{0,…,mβˆ’1}, with the first mIm_ImI​ being inequalities. conv⁑\operatorname{conv}conv is Mathlib's convexHull in RNΓ—R\mathbb R^N\times\mathbb RRNΓ—R. The multiplicity enters as IsQuadEigMult k (the largest admissible kkk), exactly as on the page; for N=0N = 0N=0 no such kkk exists and the statement is vacuous, a degenerate case the paper does not consider.

Preamble
import Mathlib
import Definitions.Def_QCQPTightness_MultHull_QCQP
import Definitions.Def_QCQPTightness_MultHull_Mult
Formal statement
namespace QCQPTightness.MultHull

open Matrix

theorem theorem_7 {N m : β„•} (P : QCQP N m) (hm : 1 ≀ m) (h1 : P.Assumption1)
    (k : β„•) (hk : P.IsQuadEigMult k) (hkm : m + 2 ≀ k) :
    convexHull ℝ P.D = P.DSDP := by sorry

end QCQPTightness.MultHull
Source
arXiv:1911.09195v3, Theorem 7, p. 29
Human review
  • Endorsed by Shuze Chen Β· Oct 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 Β· Oct 10, 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 paper
SKILL.mdTourFAQContactTerms
Β© 2026 Prove2Me