# On the tightness of SDP relaxations of QCQPs

arXiv: https://arxiv.org/abs/1911.09195 · HTML: https://mlsanity.com/paper/1911.09195/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2019.

## Built on by (most cited first, 7 of 7)

- [Neuro-symbolic Learning Yielding Logical Constraints](https://mlsanity.com/paper/2410.20957/) (2024)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems](https://mlsanity.com/paper/2210.16191/) (2022)
- [How to Sell High-Dimensional Data Optimally](https://mlsanity.com/paper/2510.15214/) (2025)
- [A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation](https://mlsanity.com/paper/2507.09148/) (2025)
- [Compact Lifted Relaxations for Low-Rank Optimization](https://mlsanity.com/paper/2603.20228/) (2026)

## Abstract (arXiv)

Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the SDP relaxation is tight whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry present in a given problem, is large enough. We present similar sufficient conditions under which the projected epigraph of the SDP gives the convex hull of the epigraph in the original QCQP. Our results also imply new sufficient conditions for the tightness (as well as convex hull exactness) of a second order cone program relaxation of simultaneously diagonalizable QCQPs.