A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

2003/02/01 by Samuel Burer, Renato D.C. Monteiro, Renato D. C. Monteiro · 835 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Algorithm #Artificial intelligence #Combinatorics #Computer science #Convergence (economics) #Discrete mathematics #Equivalence (formal languages) #Factorization #Large margin nearest neighbor #Linear programming #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Nonlinear programming #Nonlinear system #Positive-definite matrix #Quadratic programming #Quadratically constrained quadratic program #Rank (graph theory) #Semidefinite embedding #Semidefinite programming #Sparse and Compressive Sensing Techniques #Trust region #Variable (mathematics)

paper · doi:10.1007/s10107-002-0352-8

published in Mathematical Programming 95(2), 329-357 (Springer Science+Business Media)

openalex publication_date 2003/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Cited by

• Local Minima and Convergence in Low-Rank Semidefinite Programming
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Efficiently Simulable Pauli Correlation Encoding
• Rank-Adaptive Matrix-Free Atomic Quantum State Tomography
• Stability of Low-Rank Implicit Regularization in Perturbed Deep Matrix Factorization
• A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs
• Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization
• Efficient Low-Rank Semidefinite Programming with Robust Loss Functions
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Using Negative Curvature in Solving Nonlinear Programs
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• On the Convergence Rate of LoRA Gradient Descent
• Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent
• Exact and Stable Recovery of Rotations for Robust Synchronization
• A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal
• Optimal Solutions for Sparse Principal Component Analysis
• Super-Resolution mmWave Channel Estimation using Atomic Norm Minimization
• Semidefinite Relaxations for Best Rank-1 Tensor Approximations
• An Information-Minimal Geometry for Qubit-Efficient Optimization
• Convex semidefinite tensor optimization and quantum entanglement
• Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training
• Incremental Methods for Weakly Convex Optimization
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization
• Iteration complexity of first-order augmented Lagrangian methods for convex conic programming
• Flexible numerical optimization with ensmallen
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Leveraging Diversity and Sparsity in Blind Deconvolution
• Binary Matrix Completion Using Unobserved Entries
• On the computational and statistical complexity of over-parameterized matrix sensing
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Low-rank optimization with trace norm penalty
• An equivalence between critical points for rank constraints versus low-rank factorizations
• An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Optimization in Theory and Practice
• A hybrid combinatorial-continuous strategy for solving molecular distance geometry problems
• Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing
• Rethinking PCA Through Duality
• Heuristic Bundle Upper Bound Based Polyhedral Bundle Method for Semidefinite Programming
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Multi-target Position and Velocity Estimation Using OFDM Communication Signals
• Implicit Regularization in Deep Matrix Factorization
• Robust PCA by Manifold Optimization
• A combinatorial approach to Ramana's exact dual for semidefinite programming
• Tightness of SDP and Burer-Monteiro Factorization for Phase Synchronization in High-Noise Regime
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• Bilinear Bandits with Low-rank Structure
• R3MC: A Riemannian three-factor algorithm for low-rank matrix completion
• Single-Snapshot Gridless 2D-DoA Estimation for UCAs: A Joint Optimization Approach
• Scalable Second-order Riemannian Optimization for K-means Clustering
• Learning Isometric Separation Maps
• Learning Tensors in Reproducing Kernel Hilbert Spaces with Multilinear Spectral Penalties
• Cognitive Beamforming for Multiple Secondary Data Streams With Individual SNR Constraints
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• Category-Level Object Shape and Pose Estimation in Less Than a Millisecond
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Convex Optimization without Projection Steps
• Low-rank matrix completion by Riemannian optimization---extended version
• Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
• Warm-Starting PCE for Traveling Salesman Problem
• Convex relaxations of structured matrix factorizations
• An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs
• ADMM for Multiaffine Constrained Optimization
• Use of MAX-CUT for Ramsey Arrowing of Triangles
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Extreme MRI: Large-Scale Volumetric Dynamic Imaging from Continuous Non-Gated Acquisitions
• From Blind deconvolution to Blind Super-Resolution through convex programming
• A Hybrid Algorithm for Convex Semidefinite Optimization
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• How Well Do Local Algorithms Solve Semidefinite Programs?
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• Inference in Graphical Models via Semidefinite Programming Hierarchies
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Exact and Heuristic Algorithms for Constrained Biclustering
• Gaussian mixture layers for neural networks
• The Minimum-Rank Gram Matrix Completion via Modified Fixed Point Continuation Method
• Sensor network localization has a benign landscape after low-dimensional relaxation
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates
• Memory-Efficient Approximation Algorithms for Max-k-Cut and Correlation Clustering
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
• Regularization Methods for SDP Relaxations in Large Scale Polynomial Optimization
• Overcoming barriers to scalability in variational quantum Monte Carlo
• On approximate quantum error correction for symmetric noise
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
• Exploiting Simultaneous Low-Rank and Sparsity in Delay-Angular Domain for Millimeter-Wave/Terahertz Wideband Massive Access
• A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Tensor Train Quantum State Tomography using Compressed Sensing
• Efficient Semidefinite Branch-and-Cut for MAP-MRF Inference
• Matrix Completion has No Spurious Local Minimum
• Blind Deconvolution using Convex Programming
• Adaptive Consensus ADMM for Distributed Optimization
• A Decomposition Augmented Lagrangian Method for Low-rank Semidefinite Programming
• Fast entropy-regularized SDP relaxations for permutation synchronization
• Adaptive ADMM with Spectral Penalty Parameter Selection
• Robust spectral compressive sensing via vanilla gradient descent
• A Brief Introduction to Manifold Optimization
• Rigorous Maximum Likelihood Estimation for Quantum States
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
• Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Nonconvex Robust Low-rank Matrix Recovery
• A Convex Relaxation for Weakly Supervised Classifiers
• Linear Discriminant Analysis with Gradient Optimization
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• A Newton Augmented Lagrangian Method for Symmetric Cone Programming with Complexity Analysis
• Learning Robust Representations for Computer Vision
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• A Graph Decomposition motivated by the Geometry of Randomized Rounding
• Cine cone beam CT reconstruction using low-rank matrix factorization: algorithm and a proof-of-princple study
• Identifiability Conditions for Multi-channel Blind Deconvolution with Short Filters
• An efficient nonconvex reformulation of stagewise convex optimization problems
• PoLAR: Polar-Decomposed Low-Rank Adapter Representation
• Angular Synchronization by Eigenvectors and Semidefinite Programming
• An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• One Rank at a Time: Cascading Error Dynamics in Sequential Learning
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• Solving ptychography with a convex relaxation
• Riemannian Direct Trajectory Optimization of Rigid Bodies on Matrix Lie Groups
• 1-Bit Matrix Completion under Exact Low-Rank Constraint
• Moment Relaxations for Data-Driven Wasserstein Distributionally Robust Optimization
• Simultaneous Phase Retrieval and Blind Deconvolution via Convex Programming
• A Super-Resolution Framework for Tensor Decomposition
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
• New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
• Dropping Convexity for Faster Semi-definite Optimization
• cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming
• Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
• On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization
• Non-Negative Matrix Factorization, Convexity and Isometry
• Factorization Approach for Low-complexity Matrix Completion Problems:\n Exponential Number of Spurious Solutions and Failure of Gradient Methods
• Provable Exactness for Asymmetric Low-Rank SDP Learning
• Burer-Monteiro factorizability of nuclear norm regularized optimization
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-Łojasiewicz Inequality
• Low-Rank Adaptation Redux for Large Models
• Nonconvex Linear System Identification with Minimal State Representation
• A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Unsupervised Learning of Image Manifolds by Semidefinite Programming
• Fast Nonconvex SDP Solvers for Large-scale Power System State Estimation
• Positive Semidefinite Matrix Factorization: A Connection With Phase Retrieval and Affine Rank Minimization
• Low-rank semidefinite programming for the MAX2SAT problem
• An efficient primal dual semismooth Newton method for semidefinite programming
• Higher Order Generalization Error for First Order Discretization of Langevin Diffusion
• Variational approach for the electronic structure calculation on the second-order reduced density matrices and the N-representability problem
• A Unified Framework for Sample Complexity of Structured Quantum State Tomography under Noisy Observations
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Experimental quantum compressed sensing for a seven-qubit system
• Multichannel myopic deconvolution in underwater acoustic channels via low-rank recovery. [europepmc]
• A Low-Rank Method for Characterizing High-Level Neural Computations. [europepmc]
• A Relaxed Interior Point Method for Low-Rank Semidefinite Programming Problems with Applications to Matrix Completion. [europepmc]
• Saliency-Aided Online RPCA for Moving Target Detection in Infrared Maritime Scenarios. [europepmc]
• Evolving scientific discovery by unifying data and background knowledge with AI Hilbert. [europepmc]
• Semidefinite programming for manipulating acoustic traps in real time (SMART). [europepmc]
• A Robust 3D Registration Method via Simultaneous Inlier Identification and Model Estimation. [europepmc]