A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
From MaRDI portal
Publication:1411644
DOI10.1007/s10107-002-0352-8zbMath1030.90077OpenAlexW2143075842MaRDI QIDQ1411644
Samuel Burer, Renato D. C. Monteiro
Publication date: 29 October 2003
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-002-0352-8
Related Items
Exploiting low-rank structure in semidefinite programming by approximate operator splitting, Orientation estimation of cryo-EM images using projected gradient descent method, Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA, Simultaneous Phase Retrieval and Blind Deconvolution via Convex Programming, Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming, Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints, An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems, Positive Semi-definite Embedding for Dimensionality Reduction and Out-of-Sample Extensions, Column $\ell_{2,0}$-Norm Regularized Factorization Model of Low-Rank Matrix Recovery and Its Computation, Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method, Cutting Plane Generation through Sparse Principal Component Analysis, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, A new perspective on low-rank optimization, A hierarchy of spectral relaxations for polynomial optimization, Kronecker Product Approximation of Operators in Spectral Norm via Alternating SDP, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, The sampling complexity on nonconvex sparse phase retrieval problem, An entropy-regularized ADMM for binary quadratic programming, An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming, 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, A preconditioned iterative interior point approach to the conic bundle subproblem, Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization, Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints, Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming, 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, Computation of Sum of Squares Polynomials from Data Points, Guarantees for Spontaneous Synchronization on Random Geometric Graphs, Clustering heterogeneous financial networks, Linear Programming on the Stiefel Manifold, An Equivalence between Critical Points for Rank Constraints Versus Low-Rank Factorizations, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, Mahalanobis Distance Learning for Person Re-identification, Memory-Efficient Structured Convex Optimization via Extreme Point Sampling, On the Simplicity and Conditioning of Low Rank Semidefinite Programs, An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity, The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems, First-order semidefinite programming for the two-electron treatment of many-electron atoms and molecules, Iteration-complexity of first-order augmented Lagrangian methods for convex programming, ADMM for multiaffine constrained optimization, Principal Component Analysis by Optimization of Symmetric Functions has no Spurious Local Optima, Nonconvex Robust Low-Rank Matrix Recovery, Optimality Conditions for Problems over Symmetric Cones and a Simple Augmented Lagrangian Method, Adaptive Low-Nonnegative-Rank Approximation for State Aggregation of Markov Chains, 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, Blind Deconvolution by a Steepest Descent Algorithm on a Quotient Manifold, Covariate Regularized Community Detection in Sparse Graphs, Scalable Semidefinite Programming, Binary Component Decomposition Part I: The Positive-Semidefinite Case, Global Registration of Multiple Point Clouds Using Semidefinite Programming, Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion, Low rank matrix recovery with adversarial sparse noise*, Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization, Sums of squares and quadratic persistence on real projective varieties, A block coordinate descent method for sensor network localization, Low tubal rank tensor recovery using the Bürer-Monteiro factorisation approach. Application to optical coherence tomography, Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems, Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, On the tightness of SDP relaxations of QCQPs, Matrix Relaxations in Combinatorial Optimization, 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, Obtaining Tighter Relaxations of Mathematical Programs with Complementarity Constraints, Kernel based support vector machine via semidefinite programming: application to medical diagnosis, Finding graph embeddings by incremental low-rank semidefinite programming, On verified numerical computations in convex programming, Implementation of a primal-dual method for SDP on a shared memory parallel architecture, A continuation algorithm for max-cut problem, A boundary point method to solve semidefinite programs, A note on semidefinite programming relaxations for polynomial optimization over a single sphere, A trust region method for solving semidefinite programs, Unnamed Item, Solving maximum-entropy sampling problems using factored masks, Semidefinite programming relaxations for graph coloring and maximal clique problems, On the solution of large-scale SDP problems by the modified barrier method using iterative solvers, Large-scale semidefinite programming via a saddle point mirror-prox algorithm, Solving large-scale semidefinite programs in parallel, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, Solving \(k\)-cluster problems to optimality with semidefinite programming, A strengthened Barvinok-Pataki bound on SDP rank, Optimality conditions for nonlinear semidefinite programming via squared slack variables, SDP-based branch-and-bound for non-convex quadratic integer optimization, Angular synchronization by eigenvectors and semidefinite programming, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Unconstrained formulation of standard quadratic optimization problems, Convergence Results for Projected Line-Search Methods on Varieties of Low-Rank Matrices Via Łojasiewicz Inequality, Alternating direction augmented Lagrangian methods for semidefinite programming, 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, Using negative curvature in solving nonlinear programs, Phase transitions in semidefinite relaxations, An implementable proximal point algorithmic framework for nuclear norm minimization, A global exact penalty for rank-constrained optimization problem and applications, A matrix nonconvex relaxation approach to unconstrained binary polynomial programs, Lower bounds for finding stationary points I, Two proposals for robust PCA using semidefinite programming, A brief introduction to manifold optimization, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, The spherical constraint in Boolean quadratic programs, A look at robustness and stability of \(\ell_1\)-versus \(\ell_0\)-regularization: discussion of papers by Bertsimas et al. and Hastie et al., Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem, A semidefinite programming approach to the hypergraph minimum bisection problem, \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM, A multilevel analysis of the Lasserre hierarchy, Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation, A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion, A semidefinite programming-based heuristic for graph coloring, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), On semidefinite relaxations for the block model, Visualizing network communities with a semi-definite programming method, Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems, Fixed point and Bregman iterative methods for matrix rank minimization, A parallel interior point decomposition algorithm for block angular semidefinite programs, Local minima and convergence in low-rank semidefinite programming, A class of semidefinite programs with rank-one solutions, Lagrangian smoothing heuristics for Max-cut, A feasible method for optimization with orthogonality constraints, Simple algorithms for optimization on Riemannian manifolds with constraints, An augmented Lagrangian approach for sparse principal component analysis, Scalable incremental nonconvex optimization approach for phase retrieval, A survey on conic relaxations of optimal power flow problem, Riemannian Preconditioning, Algorithms for positive semidefinite factorization, Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach, Semidefinite programming relaxations and algebraic optimization in control, Block Coordinate Descent Methods for Semidefinite Programming, The State-of-the-Art in Conic Optimization Software, Computational Approaches to Max-Cut, Efficient semidefinite branch-and-cut for MAP-MRF inference, Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs, Using a factored dual in augmented Lagrangian methods for semidefinite programming, Low-rank factorization for rank minimization with nonconvex regularizers, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems, On the Burer-Monteiro method for general semidefinite programs, Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception, Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization, Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers, Rank Optimality for the Burer--Monteiro Factorization, Provable accelerated gradient method for nonconvex low rank optimization, SDPLR, Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion, Unnamed Item, A Convex Relaxation to Compute the Nearest Structured Rank Deficient Matrix, Improved row-by-row method for binary quadratic optimization problems, Non-convex exact community recovery in stochastic block model, Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs, A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids, Unnamed Item, Primal–dual first-order methods for a class of cone programming, Proof methods for robust low-rank matrix recovery
Uses Software
