Rank optimality for the Burer-Monteiro factorization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Optimization Année : 2020

Rank optimality for the Burer-Monteiro factorization

Résumé

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 [2018] 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.
Fichier principal
Vignette du fichier
matrices.pdf (566.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01958814 , version 1 (18-12-2018)

Identifiants

Citer

Irène Waldspurger, Alden Waters. Rank optimality for the Burer-Monteiro factorization. SIAM Journal on Optimization, 2020, 30 (3), pp.2577-2602. ⟨10.1137/19M1255318⟩. ⟨hal-01958814⟩
187 Consultations
82 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More