Exactness in SDP Relaxations of Quadratically Constrained Quadratic Programs
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 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.
Bio
Fatma Kilinc-Karzan is the Frank A. and Helen E. Risch Faculty Development Chair and Associate Professor of Operations Research at the Tepper School of Business, Carnegie Mellon University. She completed her Ph.D. at Georgia Institute of Technology in 2011. Her research interests are on foundational theory and algorithms for convex optimization and structured nonconvex optimization, and their applications in optimization under uncertainty, machine learning, and business analytics. Her work was the recipient of several best paper awards, including the 2014 INFORMS JFIG Best Paper Award. Her research has been supported by generous grants from NSF and ONR, including an NSF CAREER Award.
