Alex L. Wang

On Quadratically Constrained Quadratic Programs and their Semidefinite Program Relaxations Degree Type: Ph.D. in Computer Science
Advisor(s): Fatma Kilinc-Karzan
Graduated: August 2022

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. 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–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 cone 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.

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. Specifically, while the GTRS (the class of QCQPs with a single constraint) is known to have an exact SDP relaxation, the large computational complexity of SDP-based algorithms prevent them from being applied directly to the GTRS. We overcome this barrier by designing FOMs for the GTRS that operate in the original space and possess accelerated linear convergence rates. Perhaps surprisingly, we then show that similar algorithms can be extended to a wider class of SDPs with structured low-rank solutions (e.g., the SDP relaxation of a QCQP or QMP 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. Additional work in Part 2 of this thesis studies various notions of simultaneous diagonalizability of sets of quadratic forms. These new notions, specifically the almost SDC and d-restricted SDC properties, seek to understand when a QCQP can be diagonalized after arbitrarily small perturbations of the QCQP data or the introduction of additional variables. We give complete characterizations of these properties in a few settings.

Thesis Committee:
Fatma Kılınç-Karzen (Chair)
Pravesh Kothari
Ryan O'Donnell
Samuel Burer (University of Iowa)
Levent Tunçel (University of Waterloo)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Quadratically constrained quadratic programs, semidefinite programs, quadratic matrix programs, generalized trust-region subproblem, rank-one generated, simultaneous diagonalizability, first-order methods