Polynomial Time Guarantees for the Burer-Monteiro Method

Tuesday, April 27, 2021 - 1:25pm - 2:25pm
Diego Cifuentes (Massachusetts Institute of Technology)

The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in Y, where Y is an n×p matrix such that X = YYT. We show that this method can solve SDPs in polynomial time in a smoothed analysis setting. More precisely, we consider an SDP whose domain satisfies some compactness and smoothness assumptions, and slightly perturb the cost matrix and the constraints. We show that if p ≳ √(2+2η)m, where m is the number of constraints and η>0 is any fixed constant, then the Burer-Monteiro method can solve SDPs to any desired accuracy in polynomial time, in the setting of smooth analysis. Our bound on p approaches the celebrated Barvinok-Pataki bound in the limit as η goes to zero, beneath which it is known that the nonconvex program can be suboptimal.

Diego Cifuentes is an applied math instructor in the Massachusetts Institute of Technology (MIT). Previously he was a postdoctoral researcher at the Max Planck Institute for Mathematics in the Sciences, and before that he completed his Ph.D. in the Electrical Engineering and Computer Science department at MIT under the supervision of Pablo Parrilo. His research interests include mathematical optimization, computational algebraic geometry, and their applications in sciences and engineering.