2021 Virtual INFORMS Optimization Society Conference
Tuesday, March 30, 11am-12noon EDT
Speaker: Fatma Kılınç-Karzan, CMU
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 family of tractable convex relaxations. In this talk, we will study the standard semidefinite program (SDP) relaxation for general QCQPs and examine when this relaxation is exact. By analyzing the "geometry" of the SDP relaxation, we will give both sufficient conditions and necessary conditions for different types of "exactness" conditions, and discuss a number of implications of these results for various applications.
This is joint work with Alex L. Wang and C.J. Argue.
