Rank optimality for the Burer-Monteiro factorization
From MaRDI portal
Publication:4971016
DOI10.1137/19M1255318zbMATH Open1451.90114arXiv1812.03046MaRDI QIDQ4971016FDOQ4971016
Authors: Irène Waldspurger, Alden Waters 
Publication date: 8 October 2020
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: When solving large scale semidefinite programs that admit a low-rank solution, an efficient heuristic is the Burer-Monteiro factorization: instead of optimizing over the full matrix, one optimizes over its low-rank factors. This reduces the number of variables to optimize, but destroys the convexity of the problem, thus possibly introducing spurious second-order critical points. The article [Boumal, Voroninski, and Bandeira, 2018] shows that when the size of the factors is of the order of the square root of the number of linear constraints, this does not happen: for almost any cost matrix, second-order critical points are global solutions. In this article, we show that this result is essentially tight: for smaller values of the size, second-order critical points are not generically optimal, even when the global solution is rank 1.
Full work available at URL: https://arxiv.org/abs/1812.03046
Recommendations
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- On the Burer-Monteiro method for general semidefinite programs
- An equivalence between critical points for rank constraints versus low-rank factorizations
- The non-convex geometry of low-rank matrix optimization
- Local minima and convergence in low-rank semidefinite programming
Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Smooth minimization of non-smooth functions
- Title not available (Why is that?)
- Exact Recovery in the Stochastic Block Model
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Local minima and convergence in low-rank semidefinite programming
- Laplacian eigenvalues and the maximum cut problem
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Phase recovery, MaxCut and complex semidefinite programming
- Semidefinite programming and integer programming
- Low-rank optimization on the cone of positive semidefinite matrices
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- Implementation of a primal-dual method for SDP on a shared memory parallel architecture
- Global rates of convergence for nonconvex optimization on manifolds
- The non-convex geometry of low-rank matrix optimization
- A geometric analysis of phase retrieval
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
Cited In (19)
- SNIG property of matrix low-rank factorization model
- Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Global minimization of polynomial integral functionals
- Exploiting constant trace property in large-scale polynomial optimization
- On the simplicity and conditioning of low rank semidefinite programs
- Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
- Improved performance guarantees for orthogonal group synchronization via generalized power method
- Riemannian Langevin algorithm for solving semidefinite programs
- On the Burer-Monteiro method for general semidefinite programs
- An equivalence between critical points for rank constraints versus low-rank factorizations
- Linear Programming on the Stiefel Manifold
- Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
- Scalable semidefinite programming
- Accelerated first-order methods for a class of semidefinite programs
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Memory-efficient structured convex optimization via extreme point sampling
- Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
- An optimal-storage approach to semidefinite programming using approximate complementarity
Uses Software
This page was built for publication: Rank optimality for the Burer-Monteiro factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4971016)
