Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs

DOI10.1002/CPA.21830MaRDI QIDQ5114191zbMATH OpenOpenAlexWikidataFDO

Authors Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira

Publication date 21 June 2020

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.02008

zbMATH Keywords

nonconvex optimization problem, smooth manifold, gobal optimum

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26)

Abstract: We consider semidefinite programs (SDPs) with equality constraints. The variable to be optimized is a positive semidefinite matrix $X$ of size $n$. Following the Burer--Monteiro approach, we optimize a factor $Y$ of size $nimesp$ instead, such that $X=Y{Y}^T$. This ensures positive semidefiniteness at no cost and can reduce the dimension of the problem if $p$ is small, but results in a non-convex optimization problem with a quadratic cost function and quadratic equality constraints in $Y$. In this paper, we show that if the set of constraints on $Y$ regularly defines a smooth manifold, then, despite non-convexity, first- and second-order necessary optimality conditions are also sufficient, provided $p$ is large enough. For smaller values of $p$, we show a similar result holds for almost all (linear) cost functions. Under those conditions, a global optimum $Y$ maps to a global optimum $X=Y{Y}^T$ of the SDP. We deduce old and new consequences for SDP relaxations of the generalized eigenvector problem, the trust-region subproblem and quadratic optimization over several spheres, as well as for the Max-Cut and Orthogonal-Cut SDPs which are common relaxations in stochastic block modeling and synchronization of rotations.

Recommendations

• On the Burer-Monteiro method for general semidefinite programs
• Rank optimality for the Burer-Monteiro factorization
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• Local minima and convergence in low-rank semidefinite programming
• Low-rank optimization on the cone of positive semidefinite matrices

Cited in

(49)

• Using negative curvature in solving nonlinear programs
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Adaptive regularization with cubics on manifolds
• On the Burer-Monteiro method for general semidefinite programs
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• Sums of squares and quadratic persistence on real projective varieties
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• A brief introduction to manifold optimization
• A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion
• Provable accelerated gradient method for nonconvex low rank optimization
• A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids
• A hybrid Riemannian conjugate gradient method for nonconvex optimization problems
• Nonconvex phase synchronization
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
• Robust PCA by manifold optimization
• Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
• Detecting communities is hard (and counting them is even harder)
• Rank optimality for the Burer-Monteiro factorization
• Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• On the simplicity and conditioning of low rank semidefinite programs
• Spurious valleys in one-hidden-layer neural network optimization landscapes
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• An entropy-regularized ADMM for binary quadratic programming
• An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
• Solving trust region subproblems using Riemannian optimization
• A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Solving graph equipartition SDPs on an algebraic variety
• Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
• An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
• Max-Cut via Kuramoto-Type Oscillators
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
• Linear Programming on the Stiefel Manifold
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• A feasible method for general convex low-rank SDP problems
• Global minimization of polynomial integral functionals
• Riemannian Langevin algorithm for solving semidefinite programs
• The effect of smooth parametrizations on nonconvex optimization landscapes
• Nonconvex landscapes for \(\mathbf{Z}_2\) synchronization and graph clustering are benign near exact recovery thresholds
• Improved global guarantees for the nonconvex Burer-Monteiro factorization via rank overparameterization
• Riemannian trust-region methods for strict saddle functions with complexity guarantees
• Complexity of chordal conversion for sparse semidefinite programs with small treewidth
• Solving low-rank semidefinite programs via manifold optimization
• Riemannian optimization using three different metrics for Hermitian PSD fixed-rank constraints
• Generalized orthogonal Procrustes problem under arbitrary adversaries
• Local geometry determines global landscape in low-rank factorization for synchronization
• The augmented Lagrangian methods: overview and recent advances

This page was built for publication: Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114191)