Computer Science Thesis Oral
Virtual Representation - ET - Remote Access - Zoom
ALEX LIHENG WANG , Ph.D. StudentComputer Science DepartmentCarnegie Mellon University
On Semidefinite Program Relaxations of Quadratically Constrained Quadratic Programs
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. Quadratic matrix programs (QMPs) are a related class of optimization problems where the quadratic objective and constraints in the class of QCQPs are replaced by quadratic matrix functions. Both QCQPs and QMPs are frequently encountered in practice and arise naturally in diverse areas of operations research, computer science, and engineering. One may regard QMPs as QCQPs with additional structure. Although QCQPs are NP-hard to solve in general, they admit a natural convex relaxation via the standard (Shor) semidefinite program (SDP) relaxation. The research in this thesis is guided by two fundamental questions related to the SDP relaxation of a general QCQP: (1) What structures within a QCQP ensure that its SDP relaxation is accurate? And, (2) What structures within a QCQP allow its SDP relaxation to be solved efficiently? These two questions comprise the two parts of this thesis. In contrast to prior work on SDP relaxations of QCQPs (which has focused largely on approximation guarantees), Part 1 of this thesis asks when exactness occurs in the SDP relaxation of a QCQP. In this direction, we develop a framework for understanding various forms of exactness: (i) objective value exactness, (ii) convex hull exactness, and (iii) the rank-one generated (ROG) property. Part 2 of this thesis seeks to develop new methods for solving large-scale QCQPs and their SDP relaxations efficiently. In this direction, we develop new first-order methods (FOMs) for solving the generalized trust-region subproblem (GTRS) and a broader class of SDPs with exactness properties. These FOMs work in the space of the low-rank factorization of the matrix variable and completely avoid storing full matrix variables. In this way, this thesis provides new efficient FOMs for solving QCQPs and QMPs that can be applied whenever the SDP relaxation is known to be exact. Thesis Committee: Fatma Kılınç-Karzan (Chair) Pravesh Kothari Ryan O’Donnell Samuel Burer (University of Iowa) Levent Tunçel (University of Waterloo) Zoom Participation. See announcement.
For More Information: