  


Polynomial time guarantees for the BurerMonteiro method
Diego Cifuentes(diegcifmit.edu) Abstract: The BurerMonteiro method is one of the most widely used techniques for solving largescale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in $Y$, where $Y$ is an $n \times p$ matrix such that $X = Y Y^T$. In this paper, we show that this method can solve SDPs in polynomial time in an 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 \gtrsim \sqrt{2(1+\eta)m}$, where $m$ is the number of constraints and $\eta>0$ is any fixed constant, then the BurerMonteiro method can solve SDPs to any desired accuracy in polynomial time, in the setting of smooth analysis. Our bound on $p$ approaches the celebrated BarvinokPataki bound in the limit as $\eta$ goes to zero, beneath which it is known that the nonconvex program can be suboptimal. Previous analyses were unable to give polynomial time guarantees for the BurerMonteiro method, since they either assumed that the criticality conditions are satisfied exactly, or ignored the nontrivial problem of computing an approximately feasible solution. We address the first problem through a novel connection with tubular neighborhoods of algebraic varieties. For the feasibility problem we consider a least squares formulation, and provide the first guarantees that do not rely on the restricted isometry property. Keywords: Semidefinite programming, BurerMonteiro, Low rank factorization Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: arXiv:1912.01745 Download: [PDF] Entry Submitted: 12/04/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  