Local minima and convergence in low-rank semidefinite programming

DOI10.1007/s10107-004-0564-1zbMath1099.90040OpenAlexW2138505091MaRDI QIDQ2487849

Samuel Burer, Renato D. C. Monteiro

Publication date: 8 August 2005

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

Full work available at URL: https://doi.org/10.1007/s10107-004-0564-1

zbMATH Keywords

Combinatorial optimizationNumerical experimentsNonlinear programmingSemidefinite programmingAugmented LagrangianLow-rank matricesVector programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items

Structure methods for solving the nearest correlation matrix problem, Sketched learning for image denoising, Simultaneous Phase Retrieval and Blind Deconvolution via Convex Programming, Compressive Learning for Patch-Based Image Denoising, Scalable Low-Rank Representation, Computing the nearest low-rank correlation matrix by a simplified SQP algorithm, Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems, A second-order cone cutting surface method: Complexity and application, Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation, Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints, Finding graph embeddings by incremental low-rank semidefinite programming, An extension of the angular synchronization problem to the heterogeneous setting, Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods, Non-convex low-rank representation combined with rank-one matrix sum for subspace clustering, Parallel stochastic gradient algorithms for large-scale matrix completion, Unnamed Item, Solving large-scale semidefinite programs in parallel, Bounds for the quadratic assignment problem using the bundle method, Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method, A novel method for a class of structured low-rank minimizations with equality constraint, A strengthened Barvinok-Pataki bound on SDP rank, Optimality conditions for nonlinear semidefinite programming via squared slack variables, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, Completely positive factorization by a Riemannian smoothing method, Efficient joint object matching via linear programming, Alternating direction augmented Lagrangian methods for semidefinite programming, An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs, Fast certifiable relative pose estimation with gravity prior, Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, Normal Cones Intersection Rule and Optimality Analysis for Low-Rank Matrix Optimization with Affine Manifolds, A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees, A unified approach to synchronization problems over subgroups of the orthogonal group, Solving graph equipartition SDPs on an algebraic variety, Using negative curvature in solving nonlinear programs, Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization, Max-Cut via Kuramoto-Type Oscillators, Stochastic heavy ball, Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method, Low-Rank Univariate Sum of Squares Has No Spurious Local Minima, Guarantees for Spontaneous Synchronization on Random Geometric Graphs, An implementable proximal point algorithmic framework for nuclear norm minimization, Two proposals for robust PCA using semidefinite programming, A brief introduction to manifold optimization, Optimization for deep learning: an overview, A guide to conic optimisation and its applications, Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation, A feasible filter method for the nearest low-rank correlation matrix problem, A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion, ADMM for the SDP relaxation of the QAP, A class of multilevel structured low-rank approximation arising in material processing, Unnamed Item, Adapting Regularized Low-Rank Models for Parallel Architectures, Robust bilinear factorization with missing and grossly corrupted observations, An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity, Fixed point and Bregman iterative methods for matrix rank minimization, A class of semidefinite programs with rank-one solutions, Online optimization for max-norm regularization, First-order semidefinite programming for the two-electron treatment of many-electron atoms and molecules, Quartic first-order methods for low-rank minimization, Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach, Iteration-complexity of first-order augmented Lagrangian methods for convex programming, Block Coordinate Descent Methods for Semidefinite Programming, The State-of-the-Art in Conic Optimization Software, Adaptive regularization with cubics on manifolds, Flexible low-rank statistical modeling with missing data and side information, Using a factored dual in augmented Lagrangian methods for semidefinite programming, On the Burer-Monteiro method for general semidefinite programs, Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception, Quotient Geometry with Simple Geodesics for the Manifold of Fixed-Rank Positive-Semidefinite Matrices, Nonconvex Robust Low-Rank Matrix Recovery, Rank Optimality for the Burer--Monteiro Factorization, Optimality Conditions for Problems over Symmetric Cones and a Simple Augmented Lagrangian Method, Provable accelerated gradient method for nonconvex low rank optimization, Computational enhancements in low-rank semidefinite programming, Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably, On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization, Generalized Conditional Gradient for Sparse Estimation, A Proximal Operator for Multispectral Phase Retrieval Problems, Unnamed Item, Active Subspace: Toward Scalable Low-Rank Learning, Scalable Semidefinite Programming, Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs

Uses Software

• QAPLIB
• SDPLR

Cites Work

• Unnamed Item
• QAPLIB-A quadratic assignment problem library
• Bounds for the quadratic assignment problem using the bundle method
• A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming
• Semidefinite programming relaxations for the quadratic assignment problem
• Recent advances in the solution of quadratic assignment problems
• First- and second-order methods for semidefinite programming
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• The cut polytope and the Boolean quadric polytope
• Cones of diagonally dominant matrices
• Solving a class of semidefinite programs via nonlinear programming
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• Solving Some Large Scale Semidefinite Programs via the Conjugate Residual Method
• Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
• Matrix Analysis
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Primal--Dual Path-Following Algorithms for Semidefinite Programming
• On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
• Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
• A Spectral Bundle Method for Semidefinite Programming
• Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
• An Interior-Point Method for Semidefinite Programming
• Convex Analysis