Caltech Young Investigators Lecture

Monday April 10, 2023 4:00 PM

A Faster Interior-Point Method for Semidefinite Programs

Speaker: Swati Padmanabhan, University of Washington, Seattle
Location: Annenberg 105


Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. We present a faster interior point method to solve generic SDPs with variable size n × n and m constraints in time

O(√n(mn2 + mω + nω) log(1/δ))

where ω is the exponent of matrix multiplication and δ is the relative accuracy. In the predominant case of mn, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method. Our algorithm's runtime can be naturally interpreted as follows: O(√n log(1/δ)) is the number of iterations needed for our interior point method, mn2 is the input size, and mω + nω is the time to invert the Hessian and slack matrix in each iteration. These constitute natural barriers to further improving the runtime of interior point methods for solving generic SDPs.


Swati is a final-year Ph.D. student at the University of Washington, Seattle, where she is advised by Prof. Yin Tat Lee. Her research focuses on developing provably efficient algorithms for structured classes of optimization problems including semidefinite programs, nonsmooth problems (convex and nonconvex), problems in applied linear algebra, and online resource-allocation. Prior to pursuing her Ph.D., she studied Electronics Engineering and worked as a signal processing engineer in the hardware electronics industry.

This lecture is part of the Young Investigators Lecture Series sponsored by the Caltech Division of Engineering & Applied Science.

Series Caltech Young Investigators Lecture Series

Contact: Diana Bohler