Title: Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDP
| Speaker: | Sina Rezazadeh |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
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.