The non-convex Burer-Monteiro approach works on smooth semidefinite programs

Semidefinite programs (SDP's) can be solved in polynomial time by interior point methods, but scalability can be an issue. To address this shortcoming, over a decade ago, Burer and Monteiro proposed to solve SDP's with few equality constraints via rank-restricted, non-convex surrogates. Remarkably, for some applications, local optimization methods seem to converge to global optima of these non-convex surrogates reliably. Although some theory supports this empirical success, a complete explanation of it remains an open question. In this paper, we consider a class of SDP's which includes applications such as max-cut, community detection in the stochastic block model, robust PCA, phase retrieval and synchronization of rotations. We show that the low-rank Burer-Monteiro formulation of SDP's in that class almost never has any spurious local optima.


Introduction
We consider semidefinite programs (SDP's) of the form where C, X = Tr(C ⊤ X), C ∈ S n×n is the symmetric cost matrix, A : S n×n → R m is a linear operator capturing m equality constraints with right hand side b ∈ R m and the variable X is symmetric, positive semidefinite. Interior point methods solve (SDP) in polynomial time (Nesterov, 2004). In practice however, for n beyond a few thousands, such algorithms run out of memory (and time), prompting research for alternative solvers. If (SDP) has a compact search space, then it admits a global optimum of rank at most r, where r(r+1) In general, (P) is non-convex, making it a priori unclear how to solve it globally. Still, the benefits are that it is lower dimensional than (SDP) and has no conic constraint. This has motivated Monteiro (2003, 2005) to try and solve (P) using local optimization methods, with surprisingly good results. They developed theory in support of this observation (details below). About their results, Burer and Monteiro (2005, §3) write (mutatis mutandis): "How large must we take p so that the local minima of (P) are guaranteed to map to global minima of (SDP)? Our theorem asserts that we need only 2 p(p+1) 2 > m (with the important caveat that positive-dimensional faces of (SDP) which are 'flat' with respect to the objective function can harbor non-global local minima)." The caveat-the existence or non-existence of non-global local optima, or their potentially adverse effect for local optimization algorithms-was not further discussed.
In this paper, assuming p(p+1) 2 > m, we show that if the search space of (SDP) is compact and if the search space of (P) is a smooth manifold, then, for almost all cost matrices C, first-and second-order necessary optimality conditions for (P) are also sufficient-an unusual theoretical guarantee in non-convex optimization.
Notice that this is a statement about the optimization problem itself, not about specific algorithms. Interestingly, known algorithms for optimization on manifolds converge to secondorder critical points, 3 regardless of initialization .
For the specified class of SDP's, our result improves on those of (Burer and Monteiro, 2005) in two important ways. Firstly, for almost all C, we formally exclude the existence of spurious local optima. Secondly, we only require the computation of second-order critical points of (P) rather than local optima (which is hard in general (Vavasis, 1991)). Below, we make a statement about computational complexity, and we illustrate the practical efficiency of the proposed methods through numerical experiments.
SDP's which satisfy the compactness and smoothness assumptions occur in a number of applications including Max-Cut, robust PCA, Z 2 -synchronization, community detection, cutnorm approximation, phase synchronization, phase retrieval, synchronization of rotations and the trust-region subproblem-see Section 4 for references.

A simple example: the Max-Cut problem
Given an undirected graph, Max-Cut is the NP-hard problem of clustering the n nodes of this graph in two classes, +1 and −1, such that as many edges as possible join nodes of different signs. If C is the adjacency matrix of the graph, Max-Cut is expressed as max x∈R n 1 4 n i,j=1 Introducing the positive semidefinite matrix X = xx ⊤ , both the cost and the constraints may be expressed linearly in terms of X. Ignoring that X has rank 1 yields the well-known convex relaxation in the form of a semidefinite program (up to an affine transformation of the cost): min X∈S n×n C, X s.t. diag(X) = 1, X 0.
(Max-Cut SDP) If a solution X of this SDP has rank 1, then X = xx ⊤ and x is an optimal cut. In the general case of higher rank X, Goemans and Williamson (1995) exhibited the celebrated rounding scheme to produce approximately optimal cuts (within a ratio of .878) from X. The corresponding Burer-Monteiro rank-restricted, non-convex problem is: The constraint diag(Y Y ⊤ ) = 1 requires each row of Y to have unit norm; that is: Y is a point on the Cartesian product of n unit spheres in R p , which is a smooth manifold. Furthermore, all X feasible for the SDP have identical trace equal to n, so that the search space of the SDP is compact. Thus, our results stated below apply: , for almost all C, even though (Max-Cut BM) is non-convex, any local optimum Y is a global optimum (and so is X = Y Y ⊤ ), and all saddle points have an escape (the Hessian has a negative eigenvalue).
We note that, for p > n/2, the same holds for all C (Boumal, 2015).

Notation
S n×n is the set of real, symmetric matrices of size n. A symmetric matrix X is positive semidefinite (X 0) if and only if u ⊤ Xu ≥ 0 for all u ∈ R n . For matrices A, B, the standard Euclidean inner product is A, B = Tr(A ⊤ B). The associated (Frobenius) norm is A = A, A . Id is the identity operator and I n is the identity matrix of size n.

Main results
Our main result establishes conditions under which first-and second-order necessary optimality conditions for (P) are sufficient for global optimality. Under those conditions, it is a fortiori true that global optima of (P) map to global optima of (SDP), so that local optimization methods on (P) can be used to solve the higher-dimensional, cone-constrained (SDP). We now specify the necessary optimality conditions of (P). Under the assumptions of our main result below (Theorem 2), the search space is a smooth and compact manifold. As such, it can be linearized at each point Y ∈ M by a tangent space, simply by differentiating the constraints (Absil et al., 2008, eq. (3.19)): Endowing the tangent spaces of M with the (restricted) Euclidean metric A, B = Tr(A ⊤ B) turns M into a Riemannian submanifold of R n×p . In general, second-order optimality conditions can be intricate to handle (Ruszczyński, 2006). Fortunately, here, the smoothness of both the search space (1) and the cost function make for straightforward conditions. In spirit, they coincide with the well-known conditions for unconstrained optimization. (Section 5 gives definitions and explicit expressions for the Riemannian gradient and Hessian.) where Hessf (Y ) : T Y M → T Y M is the Riemannian Hessian at Y of f restricted to M (a symmetric linear operator). All local (and global) optima of (P) are second-order critical points.
We can now state our main result. In the theorem statement below, "for almost all C" means the potentially troublesome cost matrices form at most a (Lebesgue) zero-measure subset of S n×n . In particular, given any matrix C ∈ S n×n , perturbing C to C + σW where W is a Wigner random matrix results in an admissible cost matrix with probability 1, for arbitrarily small σ > 0.
Theorem 2. Given constraints A : S n×n → R m , b ∈ R m and p satisfying p(p+1) 2 > m, if (i) the search space of (SDP) is compact; and (ii) the search space of (P) is a smooth manifold, then for almost all cost matrices C ∈ S n×n , any second-order critical point of (P) is globally optimal. Under these conditions, if Y is globally optimal for (P), then the matrix X = Y Y ⊤ is globally optimal for (SDP).
The assumptions are discussed in the next section. The proof-see Section 5-works in two stages, showing that: 1. If Y is rank deficient and satisfies first-and second-order necessary optimality conditions for (P), then it is globally optimal and X = Y Y ⊤ is optimal for (SDP); and 2. If p(p+1) 2 > m, then, for almost all C, every Y which satisfies first-order necessary optimality conditions for (P) is rank-deficient.
The smooth structure of (P) naturally suggests using Riemannian optimization to solve it (Absil et al., 2008;, which is something that was already proposed by Journée et al. (2010) in the same context. Importantly, known algorithms converge to second-order critical points regardless of initialization . We state here a recent computational result to that effect.
Proposition 3. Under the numbered assumptions of Theorem 2, the Riemannian trust-region method (RTR) (Absil et al., 2007) Proof. Apply the main results of  using that f has locally Lipschitz continuous gradient and Hessian in R n×p and M is a compact submanifold of R n×p .
Essentially, each iteration of RTR requires evaluation of one cost and one gradient, a bounded number of Hessian-vector applications, and one projection from R n×p to M. In many important cases, this projection amounts to Gram-Schmidt orthogonalization of small blocks of Y -see Section 4.
Proposition 3 bounds worst-case iteration counts for arbitrary initialization. In practice, a good initialization point may be available, making the local convergence rate of RTR more informative. For RTR, one may expect superlinear or even quadratic local convergence rates near isolated local minimizers (Absil et al., 2007). While minimizers are not isolated in our case (Journée et al., 2010), experiments show a characteristically superlinear local convergence rate in practice (Boumal, 2015). This means high accuracy solutions can be achieved, as demonstrated in Section 6.
Thus, under the conditions of Theorem 2, RTR converges to global optima. In practice, the algorithm returns after a finite number of steps, and only approximate second-order criticality is guaranteed. Hence, it is interesting to bound the optimality gap in terms of the approximation quality. We do not establish such a result for small p. Instead, we give an a posteriori computable optimality gap bound for all p, noting that for p = n + 1 the bound can be controlled a priori. In the following statement, the dependence of M on p is explicit, as M p . The proof is in Section 5.
Theorem 4. Let R < ∞ be the maximal trace of any X feasible for (SDP). For any p such that M p and M p+1 are smooth manifolds and any Y ∈ M p , formỸ = [Y |0 n×1 ] in M p+1 . It holds that If all feasible X have the same trace R and there exists a positive definite feasible X, then the bound simplifies to and it is not necessary to control gradf (Y ) explicitly. If p > n, the bounds hold withỸ = Y .
Corollary 5. Under the assumption of Theorem 4, if p = n + 1 and Y ∈ M satisfies gradf (Y ) ≤ ε g and Hessf (Y ) −ε H Id, then Y is approximately optimal in the sense that For any p, equation (4) also implies the following: That is, for any p, an approximate critical point Y in M p which is far from optimal maps to a comfortably-escapable approximate saddle pointỸ in M p+1 . This suggests an algorithm as follows. For a starting value of p such that M p is a manifold, use RTR to compute an approximate second-order critical point Y . Then, formỸ in M p+1 and test the left-most eigenvalue of Hessf (Ỹ ). 4 If it is close enough to zero, this provides a good bound on the optimality gap. If not, use an (approximate) eigenvector associated to λ min (Hessf (Ỹ )) to escape the approximate saddle point and apply RTR from that new point in M p+1 ; iterate. In the worst-case scenario, p grows to n + 1, at which point all approximate second-order critical points are approximate optima-Theorem 2 suggests p = √ 2m should suffice for C bounded away from a zero-measure set. Such an algorithm already features with less theory and in a less general setting in (Journée et al., 2010) and (Boumal, 2015); in the latter, it is called the Riemannian staircase.

Discussion of the assumptions
Our main result, Theorem 2, comes with geometric assumptions on the search spaces of both (SDP) and (P)-each working with a side assumption-which we now discuss.
The assumption that the search space of (SDP), is compact works in pair with the assumption p(p+1) 2 > m as follows. For (P) to reveal the global optima of (SDP), it is necessary that (SDP) admits a solution of rank at most p. One way to ensure this is via the Pataki-Barvinok theorems (Pataki, 1998;Barvinok, 1995), which state that all extreme points of C have rank r bounded as r(r+1) 2 ≤ m. Extreme points are faces of dimension zero (such as vertices for a cube). When optimizing a linear cost function C, X over a compact convex set C, at least one extreme point is a global optimum (Rockafellar, 1970, Cor. 32.3.2)-this is not true in general if C is not compact. Thus, under the assumptions of Theorem 2, there is a point Y ∈ M such that X = Y Y ⊤ is an optimal extreme point of (SDP); then, of course, Y itself is optimal for (P).
In general, the Pataki-Barvinok bound is tight, in that there exist extreme points of rank up to that upper-bound (rounded down)-see for example (Laurent and Poljak, 1996) for the Max-Cut SDP and (Boumal, 2015) for the Orthogonal-Cut SDP. Let C (the cost matrix) be the negative of such an extreme point. Then, the unique optimum of (SDP) is that extreme point, showing that p(p+1) 2 ≥ m is necessary for (SDP) and (P) to be equivalent for all C. We further require a strict inequality because our proof relies on properties of rank deficient Y 's in M.
The assumption that M (eq. (1)) is a smooth manifold works in pair with the ambition that the result should hold for (almost) all cost matrices C. The starting point is that, for a given non-convex smooth optimization problem-even a quadratically constrained quadratic program-computing local optima is hard in general (Vavasis, 1991). Thus, we wish to restrict our attention to efficiently computable points, such as points which satisfy first-and second-order KKT conditions for (P)-see (Burer and Monteiro, 2003, §2.2) and (Ruszczyński, 2006, §3). This only makes sense if global optima satisfy the latter, that is, if KKT conditions are necessary for optimality. A global optimum Y necessarily satisfies KKT conditions if constraint qualifications (CQ's) hold at Y (Ruszczyński, 2006). The standard CQ's for equality constrained programs are Robinson's conditions or metric regularity (they are here equivalent). They read as follows, assuming Considering almost all C, global optima could, a priori, be almost anywhere in M. To simplify, we require CQ's to hold at all Y 's. This turns out to be a sufficient condition for M to be a smooth manifold of codimension m (Absil et al., 2008, Prop. 3 Once it is decided that M must be a manifold, we can step away from the specific representation of it via the matrices A 1 , . . . , A m and reason about optimality conditions on the manifold directly. Adding redundant constraints would break the CQ's, but not the manifold structure. Hence, stating Theorem 2 in terms of manifolds better captures the role of M than stating it in terms of CQ's. See also (Andreani et al., 2010, Thm. 3.3) for a proof that requiring M to be a manifold around Y is a type of CQ.
Finally, we note that Theorem 2 only applies for almost all C, rather than all C. To justify this restriction, if indeed it is justified, one should exhibit a matrix C that leads to suboptimal second-order critical points while other assumptions are satisfied. We do not have such an example. We do observe that (Max-Cut SDP) on cycles of certain even lengths has a unique solution of rank 1, while the corresponding (Max-Cut BM) with p = 2 has suboptimal local optima (strictly, if we quotient out symmetries). This at least suggests it is not enough, for generic C, to set p just larger than the rank of the solutions of the SDP. (For those same examples, at p = 3, we consistently observe convergence to global optima.)

Examples of smooth SDP's
The canonical examples of SDP's which satisfy the assumptions in Theorem 2 are those where the diagonal blocks of X or their traces are fixed. We note that the algorithms and the theory continue to hold for complex matrices, where the set of Hermitian matrices of size n is treated as a real vector space of dimension n 2 (instead of n(n+1) 2 in the real case) with inner product Their rank-constrained counterparts read as follows (matrix norms are Frobenius norms): The first example has only one constraint: the SDP always admits an optimal rank 1 solution, corresponding to an eigenvector associated to the left-most eigenvalue of C. This generalizes to the trust-region subproblem as well.
For the second example, in the real case, p = 1 forces y i = ±1, allowing to capture combinatorial problems such as Max-Cut (Goemans and Williamson, 1995), Z 2 -synchronization (Javanmard et al., 2015) and community detection in the stochastic block model (Abbe et al., 2016;. The same SDP is central in a formulation of robust PCA (McCoy and Tropp, 2011) and is used to approximate the cut-norm of a matrix (Alon and Naor, 2006). Theorem 2 states that for almost all C, p = √ 2n is sufficient. In the complex case, p = 1 forces |y i | = 1, allowing to capture problems where phases must be recovered; in particular, phase synchronization (Bandeira et al., 2014;Singer, 2011) and phase retrieval via Phase-Cut (Waldspurger et al., 2015). For almost all C, it is then sufficient to set p = ⌊ √ n + 1⌋.
In the third example, Y of size n×p is divided in q slices of size d×p, with p ≥ d. Each slice has orthonormal rows. For p = d, the slices are orthogonal (or unitary) matrices, allowing to capture Orthogonal-Cut (Bandeira et al., 2013) and the related problems of synchronization of rotations (Wang and Singer, 2013) and permutations. Here, it is sufficient for almost all C to let p = d(d + 1)q . SDP's with constraints that are combinations of the above examples can also have the smoothness property; the right-hand sides 1 and I d can be replaced by any positive definite right-hand sides by a change of variables. Another simple rule to check is if the constraint matrices A 1 , . . . , A m ∈ S n×n such that A(X) i = A i , X satisfy A i A j = 0 for all i = j (note that this is stronger than requiring A i , A j = 0), see (Journée et al., 2010).

Proofs and additional lemmas
We start by working out explicit formulas for the Riemannian gradient and Hessian which appear in Proposition 1. Let Proj Y : R n×p → T Y M be the orthogonal projector to the tangent space at Y (eq. (2)), and let be the (Euclidean) gradient and Hessian of the cost function (3). The Riemannian gradient and Hessian of f on M are related to these as follows (see Absil et al., 2008, eqs (3.37), (5.15)): Let us focus on the gradient first. Since gradf (Y ) is a tangent vector at Y (2), 5 and since it is the orthogonal projection of ∇f (Y ) to the tangent space, there exists µ ∈ R m such that where A * : R m → S n×n is the adjoint of A. Indeed, considering symmetric matrices If the A i Y 's are linearly independent as in (7), then µ is the unique solution to this linear system-for KKT points, these are the Lagrange multipliers. In general, µ may not be unique but A * (µ)Y always is, since (13) is the result of an orthogonal projection. Furthermore, contrary to classical KKT conditions, A * (µ)Y is defined for all feasible Y (not only for KKT points) and can be found by solving (13). 6 For ease of exposition, let µ = µ(Y ) = µ(Y Y ⊤ ) be the smallest-norm acceptable µ: this is a well-defined, differentiable function of Y . 7 Using this definition of µ, let First-order critical points then satisfy (using (12)): We note in passing that µ(Y ) is feasible for the dual of (SDP) exactly when S(Y ) 0: Now let us turn to the Hessian of f . Equation (10) requires computation of the differential of gradf (Y ), which is is a symmetric matrix. Because of eq. (14),Ṡ = A * (ν) for some ν ∈ R m . Hence, for any tangent vectorŻ ∈ T Y M (2), we have Ż ,ṠY = Ż Y ⊤ , A * (ν) = A(ŻY ⊤ ), ν = 0:ṠY is orthogonal to the tangent space at Y . Using (10), we find that The second-order condition for Y is that Hessf (Y ) be positive semidefinite on T Y M. Using that Proj Y is a self-adjoint operator, it follows that this condition is equivalent to: We now show that rank-deficient second-order critical points are globally optimal. We obtain this result as a corollary to a more informative statement about optimality gap at approximately second-order critical points (assuming exact rank deficiency). The lemmas also show how S can be used to control the optimality gap at approximate critical points without requiring rank deficiency. This is valid for any p.
Lemma 6. For any Y on the manifold M, if gradf (Y ) ≤ ε g and S(Y ) − ε H 2 I n , then the optimality gap at Y with respect to (SDP) is bounded as where R = max X∈C Tr(X) < ∞ measures the size of the compact set C (6). If I n ∈ im(A * ), the right hand side of (18) simplifies to ε H R. This holds in particular if all X ∈ C have same trace and C has a relative interior point (Slater condition).
Proof. By assumption on S(Y ) (eq. (14)), This holds in particular forX optimal for (SDP). Thus, we may set C,X = f * ; and certainly, Tr(X) ≤ R. Furthermore, Combining the typeset equations and using gradf (Y ) = 2S(Y )Y , we find In general, we do not assume I n ∈ im(A * ) and we get the result by Cauchy-Schwarz on (19) and But if I n ∈ im(A * ), then we show that Y is a normal vector at Y , so that it is orthogonal to gradf (Y ). Formally: there exists ν ∈ R m such that I n = A * (ν), and . This indeed allows to simplify (19).
To conclude, we show that if C has a relative interior point X ′ (that is, A(X ′ ) = b and X ′ ≻ 0) and if Tr(X) is a constant for all X in C, then I n ∈ im(A * ). Indeed, S n×n = im(A * ) ⊕ ker A, so there exist ν ∈ R m and M ∈ ker A such that I n = A * (ν) + M . Thus, for all X in C, This implies that M is orthogonal to all X − X ′ . These span ker A since X ′ is interior. Indeed, for any H ∈ ker A, since X ′ ≻ 0, there exists ε > 0 such that X X ′ + εH 0 and A(X) = b, so that X ∈ C. Hence, M ∈ ker A is orthogonal to ker A. Consequently, M = 0 and I n = A * (ν).
Lemma 7. If Y ∈ M is column rank deficient and Hessf (Y ) −ε H Id, then S(Y ) − ε H 2 I n . Proof. By assumption, there exists z ∈ R p , z = 1 such that Y z = 0. Thus, for any x ∈ R n , we can formẎ = xz ⊤ : it is a tangent vector since YẎ ⊤ = 0 (2). Then, condition (17) combined with the assumption on Hessf (Y ) tells us This holds for all x ∈ R n , hence S − ε H 2 I n as required.
Corollary 8. If Y ∈ M p is a (column) rank-deficient second-order critical point for (P), then it is optimal for (P) and X = Y Y ⊤ is optimal for (SDP). In particular, for p > n, all second-order critical points are optimal.
The first part of this corollary also appears as (Burer and Monteiro, 2003, Prop. 4), where the statement is made about local optima rather than second-order critical points (a weaker result).
At this point, we can already give a short proof of Theorem 4.

Proof of Theorem 4. SinceỸỸ
and gradf (Ỹ ) = gradf (Y ) . SinceỸ has deficient column rank, apply Lemmas 6 and 7. For p > n, there is no need to formỸ as Y necessarily has deficient column rank.
Based on Corollary 8, to establish Theorem 2 it is sufficient to show that, for almost all C, all second-order critical points are rank deficient already for small p. We show that in fact this is true even for first-order critical points. The argument is by dimensionality counting on S n×n : the set of all possible cost matrices C.
Lemma 9. Under the assumptions of Theorem 2, for almost all C, all critical points of (P) are rank deficient.
Proof. Let Y be a critical point for (P). By the first-order conditions (15) and the definition of S (14), there exists µ ∈ R m such that where null denotes the nullity (dimension of the kernel). This first step in the proof is inspired by (Wen and Yin, 2013, Thm. 3). If the right hand side evaluates to ℓ, then there exists ν such that M = C − A * (ν) and null(M ) = ℓ. Writing C = M + A * (ν), we find that where the + is a set-sum and N ℓ denotes the set of symmetric matrices of size n with nullity ℓ. This set has dimension dim N ℓ = n(n + 1) 2 − ℓ(ℓ + 1) 2 , whereas dim im(A * ) = rank(A * ) ≤ m. Assume the right hand side of (20) evaluates to p or more. Then, a fortiori, The set on the right hand side contains all "bad" C's, that is, those for which (20) offers no information about the rank of Y . The dimension of that set is bounded as follows, using that the dimension of a finite union is at most the maximal dimension, and the dimension of a finite sum of sets is at most the sum of the set dimensions: Since C ∈ S n×n lives in a space of dimension n(n+1)
Theorem 2 follows as a corollary of Corollary 8 and Lemma 9.

Numerical experiments
As an example, we run five different solvers on (Max-Cut SDP) with a collection of graphs used in Monteiro, 2003, 2005) known as the Gset. 8 The solvers are as follows, all run in Matlab. The first three are based on a low-rank factorization while the last two are interior point methods (IPM).
Manopt runs the Riemannian Trust-Region method on (Max-Cut BM), via the Manopt toolbox , with p = √ 8n+1 2 and random initialization. The number of inner iterations allowed to solve the trust-region subproblem is 500. The solver returns when 1 2 gradf (Y ) = SY ≤ 10 −6 . Code is in Matlab.
Manopt+ runs the same algorithm as above, but with p increasing from 2 to √ 8n+1 2 in 5 steps. The point Y computed at a lower p is appended with columns of i.i.d. random Gaussian variables with standard deviation 10 −5 and mean 0, then rows are normalized to produce Y + : the initial point for the next value of p. The randomization allows to escape near-saddle points (in practice). Code is in Matlab.
SDPLR runs the original Burer-Monteiro algorithm implemented by its authors (Burer and Monteiro, 2003). Code is in C interfaced through C-mex.
HRVW runs an IPM whose implementation is tailored to (Max-Cut SDP), implemented by its authors (Helmberg et al., 1996). Code is in Matlab.
After the solvers return, we project their answers to the feasible set. Manopt and SDPLR return a matrix Y : it is sufficient to normalize each row to ensure X = Y Y ⊤ is feasible for (Max-Cut SDP) (for Manopt, this step is not necessary). HRVW and CVX return a symmetric matrix X. We compute its Cholesky factorization X = RR ⊤ -if X is not positive semidefinite, we first project using an eigenvalue decomposition. Then, each row of R is normalized so that X = RR ⊤ is feasible for (Max-Cut SDP). Computation time required for these projections is not included in the timings.
We report three metrics for each graph and each solver.
Cut bound: a bound on the maximal cut value (lower is better). If C is the adjacency matrix of the graph and D is the degree matrix, then L = D − C is the Laplacian and max X 1 4 L, X s.t. diag(X) = 1, X 0 is a bound on the maximal cut. Using Lemma 6 applied to (Max-Cut SDP), a candidate optimizer X yields a bound 1 4 L, X − n 4 λ min (S).
λ min (S): by Lemma 6, this is a measure of optimality for X (feasible), where S = C − diag(diag(CX)). It is nonpositive and must be as close to 0 as possible. We compute it using bisection and the Cholesky factorization to ensure accuracy.
Time: computation time in seconds for the solver to run 9 (this excludes time taken to project the solution to the feasible set and to compute the reported metrics.) Based on the results reported in Table 1, we make the following main observations: (i) the Manopt approach (optimization on manifolds, also advocated in (Journée et al., 2010)) consistently reaches high accuracy solutions, being often orders of magnitude more accurate than other methods, as judged from λ min (S); (ii) incremental rank solvers (Manopt+ and SDPLR) are often the fastest solvers for large instances; and (iii) the tailored IPM HRVW is faster and typically more accurate than the IPM called by CVX (which is generic software). The latter point hints that one must be careful in dismissing IPM's based on experiments using generic software, although it remains clear from Table 1 that IPM's scale poorly compared to the low-rank factorization methods tested here. In particular, CVX runs into memory trouble for the larger problem instances reported. 10 To save time, we did not run CVX on the largest graphs.

Conclusions
The Burer-Monteiro approach consists in replacing optimization of a linear function C, X over the convex set {X 0 : A(X) = b} with optimization of the quadratic function CY , Y over the non-convex set {Y ∈ R n×p : A(Y Y ⊤ ) = b}. It was previously known that, if p satisfies p(p+1) statement as to the prevalence of such faces or the risk they pose for local optimization methods. In this paper we showed that, if the set of X's is compact and the set of Y 's is a smooth manifold, and if p(p+1) 2 > m, then for almost all C, the non-convexity of the problem in Y is benign, in that all Y 's which satisfy second-order necessary optimality conditions are in fact globally optimal.
We further reference the Riemannian trust-region method (Absil et al., 2007) to solve the problem in Y , as it is guaranteed to converge from any starting point to a point which satisfies second-order optimality conditions. In addition, for p = n+1, we quantitatively relate approximate satisfaction of second-order conditions to the quality of the approximate solution in terms of its objective value. We note that the 1/ε 3 convergence rate in our results may be pessimistic. Indeed, the numerical experiments clearly show that high accuracy solutions can be computed fast using optimization on manifolds, at least for certain applications.