Continuous Optimization Seminar - Sina Rezazadeh

Title: Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDP

Abstract: Burer and Monteiro in 2003 proposed a nonlinear algorithm for solving semidefinite programs. They replace the psd constraint with a low-rank factorization, turning the problem into a non-convex formulation. Then to solve the non-convex problem, they suggested an augmented Lagrangian based algorithm for it. 

Seeking some faster algorithm for some prevalent semidefinite programs,   e.g. Max-Cut, EDM etc. applicable to large scale SDPs,  P. Parrilo et al. prove a convergence rate for the block-coordinate maximization (BCM) algorithm for the Burer and Monteiro reformulation. 

In this talk, I will go through the proofs in P.Parillo et al paper, title as above. Their paper has appeared in ICML 2018.