-

 

 

 




Optimization Online





 

Exactness in SDP relaxations of QCQPs: Theory and applications

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

Abstract: Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in general, they admit a natural convex relaxation via the standard (Shor) semidefinite program (SDP) relaxation. In this tutorial, we will study the SDP relaxation for general QCQPs, present various exactness concepts related to this relaxation and discuss conditions guaranteeing such SDP exactness. In particular, we will define and examine three notions of SDP exactness: (i) objective value exactness---the condition that the optimal value of the QCQP and the optimal value of its SDP relaxation coincide, (ii) convex hull exactness---the condition that the convex hull of the QCQP epigraph coincides with the (projected) SDP epigraph, and (iii) the rank-one generated (ROG) property---the condition that a particular conic subset of the positive semidefinite matrices related to a given QCQP is generated by its rank-one matrices. Our analysis for objective value exactness and convex hull exactness stems from a geometric treatment of the projected SDP relaxation and crucially considers how the objective function interacts with the constraints. The ROG property complements these results by offering a sufficient condition for both objective value exactness and convex hull exactness which is oblivious to the objective function. By analyzing the geometry of the associated sets, we will give a variety of sufficient conditions for these exactness conditions and discuss settings where these sufficient conditions are additionally necessary. Throughout, we will highlight implications of our results for a number of example applications.

Keywords: Quadratically constrained quadratic program; Semidefinite program; Exactness

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

Category 2: Global Optimization (Theory )

Citation:

Download: [PDF]

Entry Submitted: 07/14/2021
Entry Accepted: 07/14/2021
Entry Last Modified: 07/14/2021

Modify/Update this entry


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

 

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