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

Theorem 8, p. 30 β€” if the quadratic eigenvalue multiplicity satisfies k β‰₯ m + 1, then conv(π’Ÿ ∩ H) = π’Ÿ_SDP ∩ H and Opt = Opt_SDP

Proved
QCQPTightness.MultTight.theorem_8

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

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

Consider a QCQP inf⁑{q0(x):qi(x)≀0Β (i∈[ ⁣[mI] ⁣]),Β qi(x)=0Β (i∈[ ⁣[mI+1,m] ⁣])}\inf\{q_0(x) : q_i(x)\le 0\ (i\in[\![m_I]\!]),\ q_i(x)=0\ (i\in[\![m_I+1,m]\!])\}inf{q0​(x):qi​(x)≀0Β (i∈[[mI​]]),Β qi​(x)=0Β (i∈[[mI​+1,m]])} with mβ‰₯1m\ge 1mβ‰₯1 constraints, epigraph D\mathcal DD, and Shor SDP relaxation with optimal value OptSDP\mathrm{Opt}_{\mathrm{SDP}}OptSDP​ and projected epigraph DSDP\mathcal D_{\mathrm{SDP}}DSDP​. Suppose Assumption 1 holds: the QCQP is feasible and some Ξ³βˆ—\gamma^*Ξ³βˆ— with Ξ³iβˆ—β‰₯0\gamma^*_i\ge 0Ξ³iβˆ—β€‹β‰₯0 on the inequality constraints has A0+βˆ‘iΞ³iβˆ—Ai≻0A_0+\sum_i\gamma^*_iA_i\succ 0A0​+βˆ‘i​γiβˆ—β€‹Ai​≻0. Define the hyperplane

H={(x,t)∈RN+1:2t=OptSDP}.H = \{(x,t)\in\mathbb R^{N+1} : 2t = \mathrm{Opt}_{\mathrm{SDP}}\}.H={(x,t)∈RN+1:2t=OptSDP​}.

If the quadratic eigenvalue multiplicity kkk of the QCQP (Definition 3) satisfies kβ‰₯m+1k\ge m+1kβ‰₯m+1, then

conv⁑(D∩H)=DSDP∩HandOpt=OptSDP.\operatorname{conv}(\mathcal D\cap H) = \mathcal D_{\mathrm{SDP}}\cap H\qquad\text{and}\qquad \mathrm{Opt}=\mathrm{Opt}_{\mathrm{SDP}}.conv(D∩H)=DSDPβ€‹βˆ©HandOpt=OptSDP​.

The theorem says that, with one copy of symmetry fewer than Theorem 7 requires, the SDP relaxation is still exact in value and its optimal face is the convex hull of the QCQP's optimal epigraph points.

Formalization Note Opt\mathrm{Opt}Opt and OptSDP\mathrm{Opt}_{\mathrm{SDP}}OptSDP​ are EReal infima, and HHH is defined from the EReal value, so the value identity is stated as a separate conjunct. The quadratic eigenvalue multiplicity is the largest kkk (IsGreatest), as in Definition 3. Constraints are indexed by Fin m with inequalities first.

Preamble
import Mathlib
import Definitions.Def_QCQPTightness_MultTight_QCQP
import Definitions.Def_QCQPTightness_MultTight_Mult
import Definitions.Def_QCQPTightness_MultTight_Kron
Formal statement
namespace QCQPTightness.MultTight

open QCQP Matrix

/-- Theorem 8 (arXiv:1911.09195v3, p. 30; restated p. 35): under Assumption 1, with
`H = {(x, t) : 2t = Opt_SDP}`, if the quadratic eigenvalue multiplicity `k` satisfies
`k β‰₯ m + 1`, then `conv(π’Ÿ ∩ H) = π’Ÿ_SDP ∩ H`, and `Opt = Opt_SDP`. -/
theorem theorem_8 {N m : β„•} (P : QCQP N m) (hm : 1 ≀ m) (h1 : P.Assumption1)
    (k : β„•) (hk : P.IsQuadEigMult k) (hkm : m + 1 ≀ k) :
    convexHull ℝ (P.D ∩ P.hyperplaneH) = P.DSDP ∩ P.hyperplaneH ∧ P.Opt = P.OptSDP := by sorry

end QCQPTightness.MultTight
Source
arXiv:1911.09195v3, Theorem 8, p. 30 (restated and proved in App. B, pp. 35–36)
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