Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs

DOI10.1007/s10107-021-01686-3zbMath1505.65213arXiv1807.04428OpenAlexW3190812686MaRDI QIDQ2089773

Murat A. Erdogdu, Pablo A. Parrilo, Nuri Denizcan Vanli, Asuman Ozdaglar

Publication date: 24 October 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programminglarge-scale optimizationnon-convex optimizationcoordinate descentBurer-Monteiro method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Convex programming (90C25) Nonconvex programming, global optimization (90C26)

Uses Software

• SDPLR
• Manopt

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
• A coordinate gradient descent method for nonsmooth separable minimization
• Problems of distance geometry and convex properties of quadratic maps
• Complementarity and nondegeneracy in semidefinite programming
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Semidefinite programming relaxations for semialgebraic problems
• A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices
• Randomness and permutations in coordinate descent methods
• Trust-region methods on Riemannian manifolds
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Local minima and convergence in low-rank semidefinite programming
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• Manopt, a Matlab toolbox for optimization on manifolds
• Phase transitions in semidefinite relaxations
• Low-Rank Optimization on the Cone of Positive Semidefinite Matrices
• The Positive Semidefinite Grothendieck Problem with Rank Constraint
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Degenerate Nonlinear Programming with a Quadratic Growth Condition
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Semidefinite Programming
• Second-order Sufficiency and Quadratic Growth for Nonisolated Minima