On convex hulls of epigraphs of QCQPs

2020/02/04 by Wang, Alex L., Kilinc-Karzan, Fatma
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2002.01566

Abstract

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 sufficient conditions for a convex hull result that immediately implies that 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 convex hull result holds whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry present in a given problem, is large enough. 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.

Related

• On the tightness of SDP relaxations of QCQPs
• On semidefinite descriptions for convex hulls of quadratic programs
• Exactness in SDP relaxations of QCQPs: Theory and applications
• A Geometric View of SDP Exactness in QCQPs and its Applications
• The convex hull of a quadratic constraint over a polytope