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 · 90 citations
Mathematics · Engineering · Computer Science · #Advanced Optimization Algorithms Research #Sparse and Compressive Sensing Techniques #Machine Learning and Algorithms

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

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\n 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
• 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\n 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\n 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\n applications in matrix sensing