EXACTNESS AND ALGORITHMIC EFFICIENCY FOR SEMIDEFINITE PROGRAMMING RELAXATIONS
Abstract
The effort seeks to extend theoretical and algorithmic tools from the class of semidefinite programs (SDPs) that are convex to more effectively solve the general, but difficult, class of quadratically constrained quadratic programs (QCQPs). QCQPs are a fundamental class of nonconvex optimization problems that naturally arise in operations research, engineering, and computer science. They model such considerations as yes/no decisions that represent logical choices, nonlinearities that describe risk relations, sparsity requirements on vectors, and low-rank requirements on matrices. Since QCQPs are NP-hard, they are amongst the most difficult problems to solve. Notably, the standard (Shor) SDP relaxation offers a natural tractable convex relaxation for QCQPs. Several papers have studied the approximation quality of the SDP relaxation, and recent papers complement this literature by examining the question of when exactness occurs in such a relaxation. However, this literature so far has either studied the most stringent notion of exactness on specialized problems or has examined the strength of only the most basic (Shor) SDP relaxation in settings with restrictive assumptions. Moreover, the task of solving an SDP is still considered impractical, especially in modern large-data settings, and precludes the widespread adoption in practice. This impractical solving presents a pressing need for cheap iterative methods for SDPs. The goal of the project is to establish a foundational theory for exactness of more advanced yet still low-complexity SDP relaxations, novel paradigms to gradually and dynamically improve SDP relaxations, and new algorithmic methods for efficiently obtaining solutions to them. This goal will be achieved via two major thrusts. The first thrust will work towards building a systematic rigorous treatment of conditions for various and broader notions of exactness (optimizer, objective value, convex hull, rank-k property) in more general and advanced SDP relaxations, and will design principled frameworks to improve SDP relaxations iteratively in a structured way. The advancements from this thrust will also contribute to the development of exact convex hull descriptions (in the original space of variables) of certain key structures arising in other settings such as a variety of optimization under uncertainty models, signal processing, and machine learning. The second thrust, by effectively exploiting the exactness properties of SDPs, will design efficient and accurate specialized first-order methods that operate in the original space of the underlying nonconvex problem and achieve state-of-the-art theoretical convergence rates. The resulting algorithms will be extensively tested on practical problems to assess the computational benefits. Collectively, these developments will be instrumental in advancing the theory of SDP relaxations by guiding the design of algorithmic features that effectively trade-off relaxation quality and computational tractability, and advance the ability to solve the underlying nonconvex QCQPs.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 20, 2023
- Source ID
- FA95502210365
Entities
People
- Fatma Kilinc-Karzan
Organizations
- Air Force Office of Scientific Research
- Carnegie Mellon University
- United States Air Force