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.

Short Bio:

Fatma Kılınç-Karzan is the Frank A. and Helen E. Risch Faculty Development Chair and Associate Professor of Operations Research at Tepper School of Business, Carnegie Mellon University. She holds a courtesy appointment at the Department of Computer Science as well.  She completed her PhD at the H. Milton Stewart School of Industrial and Systems Engineering 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 2015 INFORMS Optimization Society Prize for Young Researchers and 2014 INFORMS JFIG Best Paper Award. Her research has been supported by generous grants from NSF and ONR, including an NSF CAREER Award.