Speaker: Fatma Kılınç-Karzan, Carnegie Mellon University
Date & Time: May 13, 2022, Friday, 16:00
***This is an online seminar. To obtain the event link, please send a message to department.
Title: Exactness and Algorithmic Efficiency in Semidefinite Programming Relaxations
Abstract: Semidefinite programs (SDPs) have been used as a tractable relaxation for many NP-hard problems that naturally arise in operations research, engineering, and computer science. The SDP relaxation is obtained by first reformulating the problem in a lifted space with an additional rank constraint and then dropping the rank constraint. In this talk, we will first study the SDP relaxation for general quadratically constrained quadratic programs, present various exactness concepts related to the SDP relaxation, and discuss conditions guaranteeing such SDP exactness. In particular, this will allow us to identify structural properties of these problems that admit equivalent tractable SDP reformulations. Despite the well-established strength of SDP relaxations, the task of solving an SDP is still considered impractical, especially in modern large-data settings, and precludes their widespread adoption in practice. In the second part of this talk, we will review how we can effectively exploit the exactness properties of SDPs to design storage-optimal accelerated first-order methods (which achieve even linear convergence rates for certain problems). [This is joint work with Alex Wang.]
Bio: Fatma Kılınç-Karzan is the Frank A. and Helen E. Risch Faculty Development Chair and Associate Professor of Operations Research at Tepper School of Business, Carnegie Mellon University. She holds a courtesy appointment at the Department of Computer Science as well. She completed her PhD at Georgia Institute of Technology in 2011 and undergraduate and masters degrees at Middle East Technical University in
2003 and 2005. Her research interests are on foundational theory and algorithms for convex optimization and structured nonconvex optimization, and their applications in optimization under uncertainty, machine learning and business analytics. Her work was the recipient of several best paper awards, including 2015 INFORMS Optimization Society Prize for Young Researchers and 2014 INFORMS JFIG Best Paper Award. Her research has been supported by generous grants from NSF and ONR, including an NSF CAREER Award.