Optimization Online


On the tightness of SDP relaxations of QCQPs

Alex L. Wang (alw1***at***cs.cmu.edu)
Fatma Kilinc-Karzan (fkilinc***at***andrew.cmu.edu)

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 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.

Keywords: Quadratically constrained quadratic program, Semidefinite program, Lagrange function, Convex hull

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Global Optimization (Theory )


Download: [PDF]

Entry Submitted: 11/20/2019
Entry Accepted: 11/20/2019
Entry Last Modified: 11/13/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society