Laboratory for Interactive Optimization and Learning


SDP Extended


On the power and limitations semidefinite programs

How best to exploit the power of semidefinite optimization problems.

SDP Extended Formulations.

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.

NSF-funded research


PI Sebastian Pokutta