Theorem 8, p. 30 β if the quadratic eigenvalue multiplicity satisfies k β₯ m + 1, then conv(π β© H) = π_SDP β© H and Opt = Opt_SDP
ProvedQCQPTightness.MultTight.theorem_8Consider a QCQP with constraints, epigraph , and Shor SDP relaxation with optimal value and projected epigraph . Suppose Assumption 1 holds: the QCQP is feasible and some with on the inequality constraints has . Define the hyperplane
If the quadratic eigenvalue multiplicity of the QCQP (Definition 3) satisfies , then
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 and are EReal infima, and is defined from the EReal value, so the value identity is stated as a separate conjunct. The quadratic eigenvalue multiplicity is the largest (IsGreatest), as in Definition 3. Constraints are indexed by Fin m with inequalities first.
import Mathlib import Definitions.Def_QCQPTightness_MultTight_QCQP import Definitions.Def_QCQPTightness_MultTight_Mult import Definitions.Def_QCQPTightness_MultTight_Kron
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.