Rank optimality for the Burer-Monteiro factorization
Waldspurger, Irène; Waters, Alden (2018), Rank optimality for the Burer-Monteiro factorization. https://basepub.dauphine.fr/handle/123456789/18675
TypeDocument de travail / Working paper
External document linkhttps://hal.archives-ouvertes.fr/hal-01958814
Cahier de recherche CEREMADE, Université Paris-Dauphine
Series titleCahier de recherche CEREMADE, Université Paris-Dauphine
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, a very efficient heuristic is the Burer-Monteiro factorization: Instead of optimizing over the full matrix, one optimizes over its low-rank factors. This strongly reduces the number of variables to optimize, but destroys the convexity of the problem, thus possibly introducing spurious second-order critical points which can prevent local optimization algorithms from finding the solution. Boumal, Voroninski, and Bandeira  have recently shown 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 considering only semidefinite programs with a rank 1 solution.
Subjects / KeywordsBurer-Monteiro factorization; Rank
Showing items related by title and author.
Pluchinotta, Irene; Pagano, Alessandro; Giordano, Raffaele; Tsoukiàs, Alexis (2018) Article accepté pour publication ou publié