AI4OPT Seminar Series

Date: Thursday, January 26, 2023

Time: Noon – 1:00 pm

Location: Instructional Center 115 (Scale Up Room) - (759 Ferst Dr, Atlanta, GA 30318)

Join Virtually: https://gatech.zoom.us/j/99381428980

Speaker: Fatma Kılınç-Karzan


Title: Accelerated First-order Methods for a Class of Semidefinite Programs

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. 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 this talk, we will review how we can effectively exploit the exactness properties of SDPs to design storage-optimal accelerated first-order methods. We will particularly focus on the class of SDPs characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. For such SDP problems, we will show how a certificate of strict complementarity can be used to construct a low-dimensional strongly convex minimax problem whose optimizer coincides with a factorization of the SDP optimizer. We will then suggest efficient algorithms to construct the necessary certificate and solve the resulting minimax problem with theoretical convergence guarantees. This is joint work with Alex Wang.



Bio: Fatma Kılınç-Karzan is an associate professor of operations research in the Tepper School of Business at Carnegie Mellon University. Kılınç-Karzanholds a courtesy appointment at the Department of Computer Science and completed her Ph.D. at Georgia Tech (2011). Her research interests are machine learning and business analytics, and foundational theory and algorithms for convex optimization and structured nonconvex optimization and their applications in optimization under uncertainty. She is 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, ONR, and AFOSR, including an NSF CAREER Award. Kılınç-Karzanholds is a member of the Mathematical Optimization Society Council and serves on the editorial board of several journals including Operations Research, Mathematical Programming, SIAM Journal on Optimization, Mathematics of Operations Research, INFORMS Journal on Computing, and Optimization Methods and Software.

Lunch will be served at the seminar. So, please stop by 15 minutes before the seminar to pick up lunch.

To receive AI4OPT seminar announcements, please sign up to our mailing list. at https://lists.isye.gatech.edu/mailman/listinfo/ai4opt-seminars.



Past seminars can be found at https://www.ai4opt.org/seminars/past-seminars.