PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira

arXiv:1606.04970v3math.OCmath.NA

TL;DR

SDP interior-point methods can face scalability limits, motivating low-rank non-convex Burer–Monteiro formulations whose global behavior was not fully explained. The paper analyzes a broad class under rank, compactness, and smoothness assumptions, and shows that almost all cost matrices yield no spurious local optima; second-order critical points are globally optimal.

  • Problem

    Interior-point methods may not scale to large SDPs, while the observed global behavior of low-rank non-convex formulations lacked a complete theoretical explanation.

  • Method

    The paper studies rank-restricted factorizations X = Y Y^⊤ for SDPs with p(p+1)/2 ≥ m, assuming compact search spaces and a regularly defined smooth manifold.

  • Results

    For almost all cost matrices C, first- and second-order necessary conditions for the low-rank problem are sufficient for global optimality, and the mapped SDP solution is globally optimal.

  • Takeaways & Limitations

    The result formally excludes spurious local optima for the specified class of SDPs and requires computing second-order critical points rather than local optima.

  • Takeaways & Limitations

    The guarantees rely on compactness and regular smooth-manifold assumptions for the search spaces, and the discussion notes these assumptions as scope conditions.

Abstract

from arXiv · show

Semidefinite programs (SDPs) 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 SDPs 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 SDPs 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 SDPs in that class almost never has any spurious local optima.

1 Introduction

The paper studies low-rank, non-convex Burer–Monteiro formulations of SDPs, motivated by scalability limits of interior-point methods and unresolved concerns about spurious local optima. Under rank, compactness, and smoothness conditions, it shows that generic second-order critical points are globally optimal, covering several applications.

  • Motivation: Interior-point methods solve SDPs in polynomial time, but can exceed memory and time limits when n grows beyond a few thousand.
  • Burer–Monteiro formulation: Factoring X = Y Y^⊤ with p(p+1)/2 ≥ m preserves the globally optimal value while producing a lower-dimensional problem without conic constraints.Compact SDPs admit a global optimum of sufficiently low rank, enabling this restriction.
  • Main result: The paper resolves the caveat that the rank-restricted non-convex problem might contain non-global local optima by excluding spurious local optima for almost all cost matrices C.
  • Main result: If Y satisfies first- and second-order necessary optimality conditions, then Y and X = Y Y^⊤ are global optima under the stated rank, compactness, and smooth-manifold assumptions.Thus, second-order necessary conditions are sufficient for global optimality in this setting.
  • Algorithmic relevance: The result concerns the optimization problem rather than a particular algorithm, while manifold methods are reported to converge to second-order critical points regardless of initialization.
  • Applications: The theory applies to SDPs arising in Max-Cut, robust PCA, synchronization, community detection, phase retrieval, and related applications.

2 Main results

The paper shows that, under geometric and rank conditions, first- and second-order critical points of the low-rank formulation are globally optimal, generically in the cost matrix. Riemannian optimization and rank-lifting procedures provide computational routes to such points and to a posteriori optimality guarantees.

  • Main theorem: If p(p+1)/2 > m and the stated compactness and smooth-manifold assumptions hold, then for almost all C every second-order critical point is globally optimal.A globally optimal Y maps to an SDP optimum X = YY^⊤.
  • Main theorem: The proof combines global optimality of rank-deficient second-order critical points with the result that, generically in C, every first-order critical point is rank-deficient.This second step formally excludes spurious local optima for almost all cost matrices.
  • Algorithms: Riemannian trust-region methods converge to approximate second-order critical points from arbitrary initialization under the theorem’s assumptions.Each iteration uses cost and gradient evaluations, Hessian-vector applications, and projection onto the manifold.
  • Algorithms: The Riemannian staircase increases p when needed, escaping approximate saddles until an optimality-gap bound certifies approximate optimality; in the worst case, p reaches n + 1.For p = n + 1, approximate second-order critical points are approximately optimal for any C under Theorem 4’s assumptions.

3 Discussion of the assumptions

The assumptions ensure that low-rank factorization preserves an SDP optimum and that the factorized feasible set is a smooth manifold. The rank threshold is essentially necessary for equivalence across all cost matrices, while the theorem itself is generic in C.

  • Assumptions: Compactness of the SDP feasible set and p(p+1)/2 > m ensure that an optimal SDP solution can be represented at rank at most p.The argument uses the Pataki–Barvinok rank bound and existence of an optimal extreme point.
  • Assumptions: The strict rank inequality is required because the proof relies on rank-deficient points in the factorized manifold.The non-strict condition p(p+1)/2 ≥ m is necessary for equivalence for all C.
  • Assumptions: Constraint qualifications require A_1Y, ..., A_mY to be linearly independent for every feasible Y, making the factorized search space a smooth embedded manifold.Under these conditions, tangent vectors satisfy the differentiated constraints.
  • Scope: The theorem applies to almost all cost matrices C, excluding at most a Lebesgue zero-measure set, rather than guaranteeing the result for every C.The paper does not provide an example satisfying the other assumptions with a suboptimal second-order critical point.
  • Scope: For certain even cycles, the Max-Cut SDP has a unique rank-1 solution while the p = 2 factorization has suboptimal local optima; p = 3 consistently converges globally in those examples.This suggests that choosing p just above the SDP solution rank is not generally sufficient.

4 Examples of smooth SDPs

The paper presents several smooth SDP families whose rank-restricted formulations capture problems including synchronization, phase recovery, and combinatorial optimization.

  • Fixed diagonal blocks or traces provide canonical examples satisfying the theorem’s smoothness assumptions.The theory also extends to complex Hermitian matrices and positive definite right-hand sides after a change of variables.
  • The sphere example has one constraint and always admits an optimal rank-1 SDP solution given by a left-most eigenvector of C.This example also generalizes to the trust-region subproblem.
  • For p = 1 in the real case, product-of-spheres constraints restrict each y_i to ±1, covering Max-Cut, Z2-synchronization, and community detection.The same SDP formulation also appears in robust PCA and cut-norm approximation.
  • For p = 1 in the complex case, |y_i| = 1 models phase recovery, including phase synchronization and Phase-Cut phase retrieval.
  • Block-structured factors with orthonormal rows model Orthogonal-Cut, synchronization of rotations, and synchronization of permutations.When p = d, the slices are orthogonal or unitary matrices.

5 Conclusions

The paper studies when low-rank Burer–Monteiro optimization preserves SDP optima and shows that, under smoothness and rank conditions, its non-convexity is benign for almost all cost matrices.

  • The Burer–Monteiro approach replaces linear optimization over a compact PSD feasible set with quadratic optimization over factors satisfying A(YYᵀ) = b.
  • When p(p+1)/2 ≥ m, the factorized and convex SDPs have the same global optimum.
  • When p(p+1)/2 > m and the factor space is a regularly defined smooth manifold, almost every C has no non-global second-order critical points.
  • Riemannian trust-region methods are cited as converging from any initialization to second-order points, connecting the theory to optimization procedures.For p = n + 1, approximate second-order conditions imply approximate global optimality.
  • Extending the theory to inequality constraints or equality constraints violating smoothness assumptions remains a future direction.The paper suggests augmented-Lagrangian penalties as one possible approach.

A Proofs and additional lemmas

The appendix derives Riemannian first- and second-order conditions, relates them to the dual certificate S(Y), and proves global optimality for rank-deficient critical points.

  • The Riemannian gradient and Hessian are obtained by projecting Euclidean derivatives onto the tangent space of the feasible manifold.
  • Under linear independence of the constraint directions, the multiplier μ(Y) is uniquely defined for every feasible Y by a linear system and varies differentiably with Y.
  • The matrix S(Y) is a dual certificate: S(Y) ⪰ 0 exactly characterizes dual feasibility for μ(Y).
  • Approximate first- and second-order conditions bound the SDP optimality gap through the nearly positive semidefinite certificate S(Y), with simplification under additional trace assumptions.
  • If Y is column-rank deficient, approximate second-order criticality implies S(Y) ⪰ −ε_H I.A null vector of Y generates tangent directions that establish this matrix inequality.
  • Every rank-deficient second-order critical point is globally optimal for both the factorized problem and the SDP; in particular, this holds for all second-order points when p > n.
  • A dimension-counting argument shows that, for almost all C, all critical points are rank deficient when p(p+1)/2 > m.Combining this lemma with the rank-deficient optimality result yields the main theorem.

B Numerical experiments

Numerical experiments on Max-Cut compare low-rank manifold solvers with interior-point methods, evaluating accuracy, cut bounds, and computation time.

  • Five Matlab solvers are tested on Gset graphs: three low-rank factorization methods and two interior-point methods.
  • Manopt uses a Riemannian trust-region method with fixed rank p and random initialization, while Manopt+ increases p incrementally.Manopt+ perturbs newly added columns with small Gaussian noise to escape near-saddle points in practice.
  • Solver outputs are projected or normalized to produce feasible Max-Cut SDP solutions before metrics are computed.
  • The experiments report cut bounds, λmin(S), and computation time for each graph and solver.λmin(S) measures optimality for the feasible candidate X and should be as close to zero as possible.
  • Manopt consistently reaches highly accurate solutions, incremental-rank solvers are often fastest on large instances, and HRVW generally outperforms CVX among IPMs.

C Numerical experiments: results

The experiments compare Manopt, incremental-rank solvers, and interior-point methods on graph instances. Manopt attains consistently high accuracy, while incremental-rank and tailored interior-point methods often offer speed advantages.

  • Graph experiments: Across the listed graphs, several methods attain the same cut bound while differing substantially in λmin(S) and runtime.For example, Graph 50 reports cut bound 5988.2 for all five methods, while runtimes range from 5.0 s to 318.4 s.
  • Graph experiments: For Graph 67, Manopt, Manopt+, SDPLR, and HRVW report cut bound 7744.4, with runtimes of 816.4 s, 339.0 s, 267.3 s, and 2005.4 s, respectively.CVX has no reported result for this instance.

D Regularity assumption

The paper corrected its regularity assumption because manifold smoothness alone does not justify the tangent-space identity used in the proofs. The revised condition requires linearly independent constraint gradients at every feasible point.

  • Correction: The original theorems incorrectly inferred the tangent space from the assumption that the factorized search space M is a manifold.The correction explains that manifold structure alone is insufficient for the stated identity.
  • Correction: Manifold smoothness guarantees only that TY M is included in the linearized constraint set, not that the two sets are equal in general.The paper gives an example where M is a manifold but the equality fails.
  • Strengthened assumption: The revised theorems require the constraint gradients A1Y, . . . , AmY to be linearly independent for every Y in M.This is the strengthened constraint qualification used to restore the tangent-space characterization.
  • Strengthened assumption: Under this condition, M is a smooth embedded submanifold of dimension np−m, and the tangent-space characterization follows.The condition makes Φ(Y)=A(YY⊤)−b full rank on M.
  • Counterexample: A degenerate compact example shows that M can remain a smooth manifold while the linearized constraint space has the wrong dimension.For p=1, the manifold has dimension 0 and TY M={0}, while the candidate linearized space differs; for p=2, M is a circle and the dimensions also disagree.
Loading 1606.04970v3…