The standard (Shor) semidefinite-programming (SDP) relaxation of a general quadratically constrained quadratic program (QCQP) is exact — in the strong sense that the convex hull of the QCQP epigraph coincides with the projected SDP epigraph — under sufficient conditions developed by Wang and Kılınç-Karzan (IPCO 2020; Mathematical Programming 2021), but their fine-grained dimension conditions require the cone Γ\Gamma of convex Lagrange multipliers to be polyhedral, an assumption that is automatic for simultaneously diagonalizable problems. The open questions are: extending convex-hull and objective-value exactness to non-polyhedral Γ\Gamma, deciding whether the sufficient conditions are necessary, and obtaining exactness conditions for SDP relaxations strengthened with Reformulation-Linearization-Technique (RLT) cuts. Later work by the same authors resolved much of the first question at the characterization level — a sufficient condition valid for arbitrary Γ\Gamma, shown necessary and sufficient when the polar cone Γ∘\Gamma^\circ is facially exposed, plus blanket non-polyhedral results when the quadratic eigenvalue multiplicity kk (the Kronecker block-symmetry order of the constraint matrices) satisfies k≥m+2k\ge m+2 — leaving as the surviving open core: necessity without facial exposure (an explicit 2021 conjecture), fine-grained conditions in the low-symmetry non-polyhedral regime (where a known counterexample shows the polyhedral conditions fail), and an exactness theory for strengthened SDP+RLT relaxations.

Background

A quadratically constrained quadratic program (QCQP) minimizes a quadratic objective q0(x)q_0(x) subject to finitely many quadratic constraints qi(x)≤0q_i(x)\le 0, where qi(x)=x⊤Aix+2bi⊤x+ciq_i(x)=x^\top A_i x+2b_i^\top x+c_i with symmetric matrices AiA_i. QCQPs are NP-hard in general and include the trust-region subproblem (minimizing a quadratic over a Euclidean ball), quadratic matrix programs (the matrix-variable analogue of a QCQP, in which the decision variable is a matrix and the objective and constraints are quadratic in it), and many engineering design formulations. Writing the problem in epigraph form defines D:={(x,t):q0(x)≤2t, qi(x)≤0 ∀i}D:=\{(x,t): q_0(x)\le 2t,\ q_i(x)\le 0\ \forall i\} and Opt:=inf⁡{2t:(x,t)∈D}\mathrm{Opt}:=\inf\{2t:(x,t)\in D\}. The standard (Shor) SDP relaxation introduces a matrix variable XX with X⪰xx⊤X\succeq xx^\top (the positive-semidefinite, or PSD, order) replacing products xx⊤xx^\top, and projects the feasible set of the resulting SDP back onto (x,t)(x,t)-space, giving a convex set DSDP⊇DD_{\mathrm{SDP}}\supseteq D and a lower bound OptSDP≤Opt\mathrm{Opt}_{\mathrm{SDP}}\le\mathrm{Opt}. Two exactness notions are studied: objective-value exactness, Opt=OptSDP\mathrm{Opt}=\mathrm{Opt}_{\mathrm{SDP}}, and the stronger convex hull exactness, conv(D)=DSDP\mathrm{conv}(D)=D_{\mathrm{SDP}}, which certifies the relaxation simultaneously for every linear objective over the epigraph.

The analysis of Wang and Kılınç-Karzan proceeds through the dual object Γ:={(γ0,γ)∈R+1+m:A(γ)⪰0}\Gamma:=\{(\gamma_0,\gamma)\in\mathbb{R}^{1+m}_+: A(\gamma)\succeq 0\}, where A(γ):=γ0A0+∑i=1mγiAiA(\gamma):=\gamma_0A_0+\sum_{i=1}^m\gamma_iA_i and b(γ):=γ0b0+∑i=1mγibib(\gamma):=\gamma_0b_0+\sum_{i=1}^m\gamma_ib_i are the aggregated quadratic form and linear term; Γ\Gamma is the closed convex cone of Lagrange multipliers for which the aggregated form is convex (the cone of convex multipliers). Under a mild assumption (primal feasibility together with dual strict feasibility, Assumption 1 of Wang and Kılınç-Karzan), the SDP relaxation is exactly the dual of the Lagrangian dual of the QCQP. When Γ\Gamma is polyhedral — automatic when the constraint matrices are simultaneously diagonalizable, i.e., share a common eigenbasis (SD-QCQPs) — the authors proved conv(D)=DSDP\mathrm{conv}(D)=D_{\mathrm{SDP}} whenever, for every semidefinite face FF of Γ\Gamma (a face on which the aggregated matrices A(γ)A(\gamma) all have a nontrivial nullspace), the common null space V(F):={v:A(γ)v=0 ∀γ∈F}V(F):=\{v: A(\gamma)v=0\ \forall\gamma\in F\} satisfies dim⁡V(F)≥affdim⁡{b(γ):γ∈F}+1\dim V(F)\ge\operatorname{affdim}\{b(\gamma):\gamma\in F\}+1. A corollary uses the quadratic eigenvalue multiplicity kk — the largest integer such that every AiA_i factors as Ik⊗AˉiI_k\otimes\bar A_i, a Kronecker block symmetry measuring how repeated the quadratic forms are: the convex hull result holds if k≥affdim⁡{b(γ):γ∈F}+1k\ge\operatorname{affdim}\{b(\gamma):\gamma\in F\}+1 for every semidefinite face FF. Without polyhedrality, the same authors proved the blanket statements k≥m+2⇒conv(D)=DSDPk\ge m+2\Rightarrow\mathrm{conv}(D)=D_{\mathrm{SDP}} and k≥m+1⇒Opt=OptSDPk\ge m+1\Rightarrow\mathrm{Opt}=\mathrm{Opt}_{\mathrm{SDP}} (the latter for quadratic matrix programs already follows from work of Beck), and constructed a 2-variable, 2-constraint example with k=1k=1 that satisfies the dimension condition above yet has Opt≠OptSDP\mathrm{Opt}\ne\mathrm{Opt}_{\mathrm{SDP}}, showing the fine-grained conditions genuinely use polyhedrality.

A 2024 follow-up by the same authors removed polyhedrality at the characterization level. Let Γ1:={γ∈R+m:A0+∑i=1mγiAi⪰0}\Gamma_1:=\{\gamma\in\mathbb{R}^m_+: A_0+\sum_{i=1}^m\gamma_iA_i\succeq 0\} denote the slice of Γ\Gamma with unit objective weight, and let Γ∘:={y∈R1+m: ⟨y,γ⟩≤0 ∀γ∈Γ}\Gamma^\circ:=\{y\in\mathbb{R}^{1+m}:\ \langle y,\gamma\rangle\le 0\ \forall\gamma\in\Gamma\} denote the polar cone of Γ\Gamma. Their main sufficient condition states that conv(D)=DSDP\mathrm{conv}(D)=D_{\mathrm{SDP}} holds whenever the subspace of rounding directions

R′(x,t):={(x′,t′)∈Rn+1: q(x+αx′)−2(t+αt′) eobj∈span⁡(G(x,t)) ∀α∈R}R'(x,t):=\{(x',t')\in\mathbb{R}^{n+1}:\ q(x+\alpha x')-2(t+\alpha t')\,e_{\mathrm{obj}}\in\operatorname{span}(G(x,t))\ \forall\alpha\in\mathbb{R}\}

is nontrivial at every point of DSDP∖DD_{\mathrm{SDP}}\setminus D, where q(x):=(q0(x),…,qm(x))q(x):=(q_0(x),\dots,q_m(x)), eobje_{\mathrm{obj}} is the first unit vector of R1+m\mathbb{R}^{1+m}, and G(x,t)G(x,t) is the minimal face of Γ∘\Gamma^\circ containing q(x)−2t eobjq(x)-2t\,e_{\mathrm{obj}}; the conditions in this framework are expressed through Γ\Gamma, Γ1\Gamma_1, and Γ∘\Gamma^\circ. Moreover, when Γ∘\Gamma^\circ is facially exposed (every face of the cone is exposed, i.e., obtainable as the minimizer set of a linear functional; this holds for slices of the nonnegative orthant, the second-order cone, and the PSD cone), this condition is also necessary, giving the first necessary-and-sufficient characterization of convex hull exactness even in the diagonal setting. Whether necessity survives without facial exposedness is an open conjecture. The same paper observes that its sufficient condition on the surface requires checking infinitely many systems of infinitely many constraints, although it can be checked in situations where Γ\Gamma is sufficiently simple. In parallel, Wang and Kılınç-Karzan (refs. 1, 2) flagged exactness of strengthened relaxations: the Reformulation-Linearization-Technique (RLT) multiplies constraints pairwise and linearizes the resulting quadratic terms, adding valid inequalities to the SDP (SDP+RLT, or SOC-RLT when the added cuts are second-order-cone representable). Sturm and Zhang showed such a strengthened relaxation describes the convex hull of the trust-region subproblem with one extra linear constraint, and Dey, Muñoz and Serrano showed aggregation-based convex-hull descriptions exist for sets given by three quadratic inequalities but provably break down for four or more; no general exactness theory for strengthened relaxations of general QCQPs exists.

Problem Statement

Without assuming that the cone of convex Lagrange multipliers Γ\Gamma of a QCQP (under the standard primal-feasibility and dual-strict-feasibility assumption) is polyhedral, characterize exactly when the standard SDP relaxation is exact — going beyond the 2024 characterization, which gives sufficiency for arbitrary Γ\Gamma but necessity only under facial exposedness of the polar cone Γ∘\Gamma^\circ — and settle whether the known sufficient conditions are necessary. All components below serve this single objective: delimiting when SDP-based convex relaxations of a general QCQP are exact, beyond the polyhedral multiplier-cone regime in which the current fine-grained theory is confined. The three components are independent.

  1. Necessity without facial exposure. Prove or refute the conjecture of Kılınç-Karzan and Wang (2021) that V(G⊥)=V(G△)V(G^\perp)=V(G^\triangle) for every face GG of the polar cone Γ∘\Gamma^\circ, where G△:=Γ∩G⊥G^\triangle:=\Gamma\cap G^\perp and, as in Kılınç-Karzan and Wang (ref. 4), V(S):={v∈Rn: v⊤A(γ)v=0 ∀γ∈S}V(S):=\{v\in\mathbb{R}^n:\ v^\top A(\gamma)v=0\ \forall\gamma\in S\} is defined by the quadratic-form condition: for S⊆ΓS\subseteq\Gamma (in particular S=G△S=G^\triangle) it coincides with the common null space {v:A(γ)v=0 ∀γ∈S}\{v:A(\gamma)v=0\ \forall\gamma\in S\} of the Background, whereas for S=G⊥S=G^\perp the quadratic-form reading is genuinely weaker, since G⊥∖Γ≠∅G^\perp\setminus\Gamma\neq\varnothing and the aggregated matrices A(γ)A(\gamma) with γ∈G⊥∖Γ\gamma\in G^\perp\setminus\Gamma can be indefinite. The conjecture would make the Wang–Kılınç-Karzan sufficient condition — nontriviality of the rounding-direction subspaces R′(x,t)R'(x,t) over DSDP∖DD_{\mathrm{SDP}}\setminus D — necessary for conv(D)=DSDP\mathrm{conv}(D)=D_{\mathrm{SDP}} for arbitrary Γ\Gamma; a refutation must be an explicit counterexample.

  2. The low-symmetry, non-polyhedral regime. For QCQPs whose Γ\Gamma is not polyhedral and whose quadratic eigenvalue multiplicity lies below the blanket bounds (k<m+2k<m+2 for convex hull exactness, k<m+1k<m+1 for objective-value exactness), determine checkable conditions strictly weaker than k≥m+2k\ge m+2 under which conv(D)=DSDP\mathrm{conv}(D)=D_{\mathrm{SDP}} or Opt=OptSDP\mathrm{Opt}=\mathrm{Opt}_{\mathrm{SDP}} holds; or prove that no condition expressed only through kk and the affine dimensions of the sets {b(γ):γ∈F}\{b(\gamma):\gamma\in F\} over faces FF suffices (the known two-constraint counterexample already rules out direct transfer of the polyhedral conditions).

  3. Strengthened relaxations — explicitly flagged as future research by Wang and Kılınç-Karzan (refs. 1, 2). Give exactness conditions for the SDP relaxation strengthened with RLT-derived inequalities or SOC-RLT cuts, where currently only special structures are understood (trust-region subproblems with one linear constraint, three aggregated quadratic inequalities, box-constrained programs).

References

  1. Alex L. Wang and Fatma Kılınç-Karzan, "On convex hulls of epigraphs of QCQPs", Integer Programming and Combinatorial Optimization (IPCO 2020), Lecture Notes in Computer Science, vol. 12125, pp. 419-432, 2020. DOI: 10.1007/978-3-030-45771-6_32; arXiv:2002.01566. https://arxiv.org/abs/2002.01566
  2. Alex L. Wang and Fatma Kılınç-Karzan, "On the tightness of SDP relaxations of QCQPs", Mathematical Programming 193:33–73, 2021. DOI: 10.1007/s10107-020-01589-9; arXiv:1911.09195. https://arxiv.org/abs/1911.09195
  3. Alex L. Wang and Fatma Kılınç-Karzan, "On semidefinite descriptions for convex hulls of quadratic programs", Operations Research Letters 54:107108, 2024. DOI: 10.1016/j.orl.2024.107108; arXiv:2403.04752. https://arxiv.org/abs/2403.04752
  4. Fatma Kılınç-Karzan and Alex L. Wang, "Exactness in Semidefinite Progam Relaxations of Quadratically Constrained Quadratic Programs: Theory and Applications" [title as registered by the publisher, including its typo "Progam"], Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, pp. 312-345, 2021. DOI: 10.1287/educ.2021.0232; arXiv:2107.06885. https://arxiv.org/abs/2107.06885
  5. C. J. Argue, Fatma Kılınç-Karzan, and Alex L. Wang, "Necessary and Sufficient Conditions for Rank-One-Generated Cones", Mathematics of Operations Research 48(1):100–126, 2023. DOI: 10.1287/moor.2022.1254; arXiv:2007.07433. https://arxiv.org/abs/2007.07433
  6. Santanu S. Dey, Gonzalo Muñoz, and Felipe Serrano, "On Obtaining the Convex Hull of Quadratic Inequalities via Aggregations", SIAM Journal on Optimization 32(2):659–686, 2022. DOI: 10.1137/21m1428583; arXiv:2106.12629. https://arxiv.org/abs/2106.12629
  7. Julia Lindberg and Jose Israel Rodriguez, "Invariants of SDP exactness in quadratic programming", Journal of Symbolic Computation 122:102258, 2024. DOI: 10.1016/j.jsc.2023.102258; arXiv:2211.05645. https://arxiv.org/abs/2211.05645
  8. Alexander Joyce and Boshi Yang, "Convex hull results on quadratic programs with non-intersecting constraints", Mathematical Programming 205:539–558, 2024. DOI: 10.1007/s10107-023-01985-x. https://doi.org/10.1007/s10107-023-01985-x
  9. Naohiko Arima, Sunyoung Kim, and Masakazu Kojima, "Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints", arXiv:2409.07213, 2024. https://arxiv.org/abs/2409.07213
  10. Naohiko Arima, Sunyoung Kim, and Masakazu Kojima, "Further Development in Convex Conic Reformulation of Geometric Nonconvex Conic Optimization Problems", SIAM Journal on Optimization 34(4):3194–3211, 2024. DOI: 10.1137/23m1593346; arXiv:2308.05922. https://arxiv.org/abs/2308.05922
  11. Masakazu Kojima, Sunyoung Kim, and Naohiko Arima, "Extending Exact Convex Relaxations of Quadratically Constrained Quadratic Programs", arXiv:2504.03204, 2025. https://arxiv.org/abs/2504.03204
  12. Amir Beck, "Quadratic Matrix Programming", SIAM Journal on Optimization 17(4):1224–1238, 2007. DOI: 10.1137/05064816x. https://doi.org/10.1137/05064816x
  13. Jos F. Sturm and Shuzhong Zhang, "On Cones of Nonnegative Quadratic Functions", Mathematics of Operations Research 28(2):246–267, 2003. DOI: 10.1287/moor.28.2.246.14485. https://doi.org/10.1287/moor.28.2.246.14485
  14. Alex L. Wang and Fatma Kılınç-Karzan, "A Geometric View of SDP Exactness in QCQPs and its Applications", arXiv:2011.07155, 2020. https://arxiv.org/abs/2011.07155
  15. Yuzhou Qiu and E. Alper Yıldırım, "On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints", Journal of Global Optimization 90:293–322, 2024. DOI: 10.1007/s10898-024-01407-y. https://doi.org/10.1007/s10898-024-01407-y
  16. Xin Chen, "Exactness of the DNN Relaxation for Random Standard Quadratic Programs", arXiv:2605.11456, 2026. https://arxiv.org/abs/2605.11456