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

By S. Burer, Renato D. C. Monteiro. Mathematical programming, 2003

1,054 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/0eb4bbd57275644738916a1603f3ff7f9ae0d74e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Convex optimization under inexact first-order information (2009, methodology): “More recently, it has been used by the convex programming community to develop specialized first-order methods for solving large-scale semidefinite programming problems (see, for example, Burer and Monteiro [11, 12], Jarre and Rendl [23], Zhao et al. [78]), due to its lower iteration-cost compared t”
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization (2007, methodology): “SDPLR and the method of multipliers For general semidefinite programming problems, Burer and Monteiro have developed in [8, 9] a nonlinear programming approach that relies on a low-rank factorization of the matrix decision variable.”
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage (2017, methodology): “We apply several algorithms, including a moderate number of iterations of CGM, SketchyCGM with rank parameter r = 1, the Burer–Monteiro method [6, 22], and Wirtinger flow [9].”
Social Recommendation Using Low-Rank Semidefinite Program (2011, methodology): “10 is solved by the augmented Lagrangian method proposed in (Burer and Monteiro 2003; Burer and Choi 2006), which is a nonlinear method using BFGS optimization.”
Online Robust PCA via Stochastic Optimization (2013, background): “Such nuclear norm factorization is developed in [3] and well established in recent works [20, 19].”
Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming (2011, methodology): “The latter termination criterion is used when comparing the variant of Nesterov’s method with Burer and Monteiro’s low-rank method which, being a primal-only method, generates only x and a dual estimate y based on x. 5.2 Comparisons of three first-order methods for LP In this subsection, we compare ”
Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, background): “As discussed in Section 4.2, there is a rich literature which studies global optimality of nonconvex low-rank factorization formulations such as the Burer-Monteiro factorization in the overparametrized regime [5, 15–17].”
Experimental robustness of Fourier Ptychography phase retrieval algorithms (2015, methodology): “This new problem is then solved effectively using the augmented Lagrangian multiplier, by modifying the original cost function [26,27]”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “We have also left out several important nonconvex problems and methods in order to stay focused, including but not limited to (1) blind calibration and finding sparse vectors in a subspace [203]–[205]; (2) tensor completion, decomposition and mixture models [140], [206]–[209]; (3) parameter recovery”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “The proof of theorem is inspired by a line of literature started by Pataki (1998; 2000); Burer and Monteiro (2003); Boumal et al. (2016).”
Global Optimality of Local Search for Low Rank Matrix Recovery (2016, methodology): “The seminal work of Burer and Monteiro [3] proposed low-rank factorized optimization for SDPs, and showed that for extremely high rank r > √ m (number of constraints), an Augmented Lagrangian method converges asymptotically to the optimum.”
Implicit Regularization in Deep Matrix Factorization (2019, background): “The literature on matrix factorization for low-rank matrix recovery is far too broad to cover here — we refer to [10] for a recent survey, while mentioning that the technique is oftentimes attributed to [8].”
A Nonlinear Optimization Approach to H2-Optimal Modeling and Control (2013, methodology): “This type of parametrization have, with success, been used in, for example, Burer and Monteiro [2003] for semidefinite programs.”
Generalized Low Rank Models (2014, background): “However, a theoretical analysis of optimality conditions for rank-constrained semidefinite programs [20] has led to a few algorithms for semidefinite programming based on matrix factorization [19, 1, 70] which guarantee global optimality and converge quickly if the global solution to the problem is ”
Implicit Regularization in Matrix Factorization (2017, background): “This is not surprising since with large enough d this non-convex problem has no spurious local minima [4, 9] and gradient descent converges almost surely to a global optima [12]; there has also been recent work establishing conditions for global convergence for low d [3, 7].”
Statistical properties of community structure in large social and information networks (2008, background): “Here we will discuss the well-known spectral lower bound [33] on the conductance of cuts of arbitrary balance, and a related SDP-based lower bound [28] on the conductance of any cut that divides the graph into two pieces of equal volume.”