On semidefinite descriptions for convex hulls of quadratic programs

Abstract

Quadratically constrained quadratic programs (QCQPs) are a highly expressive class of nonconvex optimization problems. While QCQPs are NP-hard in general, they admit a natural convex relaxation via the standard semidefinite program (SDP) relaxation. In this paper we study when the convex hull of the epigraph of a QCQP coincides with the projected epigraph of the SDP relaxation. We present a sufficient condition for convex hull exactness and show that this condition is further necessary under an additional geometric assumption. The sufficient condition is based on geometric properties of $\hat{I}“$, the cone of convex Lagrange multipliers, and its relatives $\hat{I}{“}_1$ and $\hat{I}{“}^{\circ }$.

This paper is a significant rewrite of arXiv:2011.07155 [math.OC] and contains both new content and rewritten content