CAREER: Semidefinite Programming (SDP) Extended Formulations

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This Faculty Early Career Development (CAREER) Program grant will explore the power of Semidefinite Optimization problems. This broad class of optimization problems is fundamental to solving many real-world problems in engineering and computer science as well as pivotal in analyzing the theoretical performance of algorithms. Approaches based on semidefinite optimization often provide superior algorithms yet at the same time the power of semidefinite optimization problems is only partially understood. The leitmotif of this grant is: How best to exploit the power of semidefinite optimization problems? This grant will relate the structure of optimization problems to their representability as semidefinite optimization problems and explore new ways of solving large semidefinite programs efficiently. Moreover, it will relate semidefinite optimization to the weaker but more easily solvable class of so called linear optimization problems. Understanding the power of semidefinite optimization problems will advance both our understanding of theoretical computational complexity as well as practical feasibility of solving semidefinite optimization problems. As such the results will positively impact both society and the U.S. economy. The tightly integrated educational program will broaden the involvement of under-represented groups and enhance engineering education. The expressive power of semidefinite programs will be studied in the natural framework of extended formulations, which is a unified way of denoting optimization problems. Extended formulations have been highly successful for linear programming, answering long standing open problems. However very little is known about the more general and significantly more complex semidefinite case. A major aspect of this CAREER grant is to study both the construction of small semidefinite extended formulations, as well as strong lower bounding techniques, potentially allowing for efficient approximations of hard combinatorial optimization problems. Structured extended formulations derived from hierarchies have proven to be powerful however it is not well-understood when they can be outperformed by more general formulations. Closely related to these aspects is the question regarding the relation between semidefinite extended formulations and linear extended formulations. While linear programs can be solved rather efficiently for largest scale instances, semidefinite programs are notoriously hard to solve in practice, so that it can be desirable to solve a linear approximation instead. It is known that this is not possible in general, however for large classes of problems of interest linear programming based approximation might provide sufficient guarantees and identifying sufficient conditions is part of this grant.