Rank optimality for the Burer-Monteiro factorization
From MaRDI portal
Publication:4971016
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.
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
Cites work
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- A geometric analysis of phase retrieval
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Exact Recovery in the Stochastic Block Model
- Global rates of convergence for nonconvex optimization on manifolds
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Implementation of a primal-dual method for SDP on a shared memory parallel architecture
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Laplacian eigenvalues and the maximum cut problem
- Local minima and convergence in low-rank semidefinite programming
- Low-rank optimization on the cone of positive semidefinite matrices
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- 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
- Smooth minimization of non-smooth functions
- The non-convex geometry of low-rank matrix optimization
Cited in
(19)- On the simplicity and conditioning of low rank semidefinite programs
- An equivalence between critical points for rank constraints versus low-rank factorizations
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
- Global minimization of polynomial integral functionals
- Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
- Scalable semidefinite programming
- Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
- Linear Programming on the Stiefel Manifold
- Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
- An optimal-storage approach to semidefinite programming using approximate complementarity
- Exploiting constant trace property in large-scale polynomial optimization
- SNIG property of matrix low-rank factorization model
- Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Memory-efficient structured convex optimization via extreme point sampling
- Improved performance guarantees for orthogonal group synchronization via generalized power method
- Riemannian Langevin algorithm for solving semidefinite programs
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Accelerated first-order methods for a class of semidefinite programs
- On the Burer-Monteiro method for general semidefinite programs
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)
