Rank optimality for the Burer-Monteiro factorization
Waldspurger, Irène; Waters, Alden (2020), Rank optimality for the Burer-Monteiro factorization, SIAM Journal on Optimization, 30, 3, p. 2577-2602. 10.1137/19M1255318
TypeArticle accepté pour publication ou publié
Journal nameSIAM Journal on Optimization
SIAM - Society for Industrial and Applied Mathematics
MetadataShow full item record
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Bernoulli Institute for Mathematics and Computer Science and Artificial Intelligence
Abstract (EN)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 [N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs, https://arxiv.org/abs/1804.02008, 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.
Subjects / Keywordssemidefinite programming; Burer-Monteiro factorization
Showing items related by title and author.
Pluchinotta, Irene; Pagano, Alessandro; Giordano, Raffaele; Tsoukiàs, Alexis (2018) Article accepté pour publication ou publié