PaperlayerView exact revision on arXiv

Source-linked AI summary

Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs

Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira

arXiv:1804.02008v2math.OCcs.NAmath.NA

TL;DR

Large SDPs can be difficult to solve directly, motivating factorization despite its non-convexity. The paper studies when smoothness and conditions on rank, compactness, and cost make optimality conditions for the factorized problem sufficient for global optimality.

  • Problem

    Direct SDP methods can run out of memory and time for large n, while factorization introduces a non-convex problem whose guarantees depend on its assumptions.

    Source: §1 · p. 2

  • Method

    The paper analyzes the geometry of the factorized feasible set and uses smooth-manifold optimality conditions, rank bounds, and face geometry to establish global and approximate optimality guarantees.

    Source: Contributions · p. 3, §3 · p. 11, §6 · p. 22

  • Results

    Under Assumption 1.1 and extra conditions on p, compactness, and the cost matrix, the factorization is safe despite non-convexity.

    Source: §7 · p. 23

  • Takeaways & Limitations

    The paper identifies settings where necessary optimality conditions for the factorized problem suffice for global optimality, while noting that approximate guarantees at ranks well below n remain an open practical question.

    Source: §7 · p. 23

    Theorem 1.4 may need to exclude a zero-measure set of cost matrices, and whether that exclusion is necessary remains unresolved.

    Source: §6 · p. 22

Abstract

from arXiv · show

We consider semidefinite programs (SDPs) with equality constraints. The variable to be optimized is a positive semidefinite matrix $X$ of size $n$. Following the Burer--Monteiro approach, we optimize a factor $Y$ of size $n \times p$ instead, such that $X = YY^T$. This ensures positive semidefiniteness at no cost and can reduce the dimension of the problem if $p$ is small, but results in a non-convex optimization problem with a quadratic cost function and quadratic equality constraints in $Y$. In this paper, we show that if the set of constraints on $Y$ regularly defines a smooth manifold, then, despite non-convexity, first- and second-order necessary optimality conditions are also sufficient, provided $p$ is large enough. For smaller values of $p$, we show a similar result holds for almost all (linear) cost functions. Under those conditions, a global optimum $Y$ maps to a global optimum $X = YY^T$ of the SDP. We deduce old and new consequences for SDP relaxations of the generalized eigenvector problem, the trust-region subproblem and quadratic optimization over several spheres, as well as for the Max-Cut and Orthogonal-Cut SDPs which are common relaxations in stochastic block modeling and synchronization of rotations.

1 Introduction

The paper studies equality-constrained SDPs and the Burer–Monteiro factorization, which replaces a positive-semidefinite matrix variable with a lower-dimensional factor. This can ease computation, but makes the problem non-convex and leaves open when local solutions are globally valid.

1 Introduction

  • Interior-point methods can run out of memory and time for SDPs with n beyond a few thousand, motivating alternative solvers.For compact feasible sets, an optimum has rank at most r when r(r+1)/2 ≤ m, so restricting to rank p with p(p+1)/2 ≥ m preserves the optimal value.Source: §1 · p. 2
  • Factoring X = YY^T enforces positive semidefiniteness and can lower dimension, but yields a non-convex quadratically constrained quadratic program.The factor Y has size n × p.Source: §1 · p. 2
  • Burer and Monteiro used local optimization for the factorized problem and reported surprisingly good results, but the non-convexity leaves its solvability unclear a priori.Their cited guarantee requires p(p+1)/2 > m and has a caveat involving flat positive-dimensional faces.Source: §1 · p. 2
  • The earlier caveat about non-global local optima and their possible adverse effect on local algorithms was not further discussed, and its mildness is hard to gauge because the feasible set can have a continuum of faces.The paper frames this as an unresolved issue about the caveat's practical scope.Source: §1 · p. 2

Contributions

The paper identifies conditions under which first- and second-order optimality conditions for the non-convex factorized problem certify global optimality. Its results include generic-cost guarantees at smaller ranks, all-cost guarantees under stronger conditions, and implications for approximate critical points.

Contributions

  • Assumption 1.1 makes the factorized feasible set a smooth manifold by requiring constraint gradients to be linearly independent or to span a constant-dimensional space nearby.The dimension m′ of the span is independent of the feasible factor, and is the same across ranks where the assumption holds.Source: Contributions · p. 3
  • For almost any cost matrix, if p(p+1)/2 > rankA and Assumption 1.1 holds, first- and second-order necessary conditions certify global optimality of Y and X = YY^T.The proof first shows that rank-deficient second-order critical points are globally optimal, then shows that almost all cost matrices force first-order critical points to be column-rank deficient under the rank bound.Source: Contributions · p. 3
  • With compact C and Assumption 1.1 at p = n+1, approximate first- and second-order conditions yield approximate global optimality for every cost matrix.The guarantee concerns the attained cost value.Source: Contributions · p. 4
  • Theorem 1.4 may leave a zero-measure subset of cost matrices unresolved, whereas Theorem 1.5 applies to every cost matrix but requires a large p.The paper leaves open whether excluding that zero-measure set is necessary for Theorem 1.4.Source: Contributions · p. 4
  • For second-order critical points, rank deficiency guarantees global optimality; a full-rank point is also globally optimal when its associated face has dimension below the stated threshold.The threshold is 2 − m′ + p; combining this face-dimension result with bounds on feasible-set faces gives all-cost guarantees for some p < n.Source: Contributions · p. 4
  • The results have implications for several SDP applications, including the trust-region subproblem, Max-Cut, and Orthogonal-Cut.The paper also highlights the open question of whether approximate second-order critical points are approximately optimal for p well below n.Source: Contributions · p. 4

Notation

The notation section fixes the matrix and operator conventions used in the paper.

Notation

  • S_n×n denotes real symmetric n × n matrices, and X is positive semidefinite exactly when u^T X u ≥ 0 for every u in R^n.The matrix inner product is ⟨A,B⟩ = Tr(A^T B).Source: Notation · p. 4
  • Compactness of C ensures a minimum is attained in (P), and hence second-order critical points exist.Source: Notation · p. 4
  • The adjoint A* maps ν to ν₁A₁ + ··· + νₘAₘ; the passage states that m′ ≤ m is defined in Assumption 1.1.Source: Notation · p. 5

2 Geometry and optimality conditions

The paper develops the geometry and optimality conditions of both the factorized non-convex problem and its convex SDP. A shared certificate links critical points of the factorized problem to global optima of the SDP.

2.1 For the non-convex problem (P)

  • Under Assumption 1.1, the feasible factor set is a submanifold of dimension np − m′, and its tangent space is obtained by linearizing the equality constraints.The tangent space's normal space is spanned by the matrices A_iY.Source: §2.1 · p. 5
  • The Riemannian gradient is the projection of the Euclidean gradient onto the tangent space, while second-order criticality requires a positive-semidefinite Riemannian Hessian.All local and global minima of (P) satisfy second-order criticality.Source: §2.1 · pp. 6–7

2.2 For the convex problem (SDP)

  • For compact C, an optimum occurs at an extreme point, and the rank of an extreme point is bounded using the number of constraints.The dimension of a face containing X is characterized through the kernel of L_X, whose rank is at most m′.Source: §2.2 · p. 8
  • A positive-semidefinite certificate S with ⟨S,X⟩ = 0 proves that feasible X is optimal for (SDP).The paper's certificate has the form S = C − A*(ν).Source: §2.2 · p. 8
  • If Y is critical for (P) and its certificate S is positive semidefinite, then X = YY^T is globally optimal for (SDP), and Y is globally optimal for (P).Criticality gives SY = 0, hence ⟨S,YY^T⟩ = 0, allowing the SDP certificate to apply.Source: §2.2 · p. 9

3 Optimality of second-order critical points

The section shows when second-order criticality of the factorized problem certifies global optimality of both the factor and its SDP matrix. Its guarantees depend on rank, cost-function genericity, and the dimension of the face containing the matrix.

3 Optimality of second-order critical points

  • A rank-deficient second-order critical point has a positive semidefinite certificate matrix and is globally optimal for both the factorized problem and the SDP.The certificate is S(Y) ⪰ 0.Source: §3 · p. 9
  • If p ≥ n, every second-order critical point is globally optimal for both the factorized problem and the SDP.For p > n, points are necessarily column-rank deficient; for p = n, the result also covers full-rank points.Source: §3 · p. 10
  • For almost all cost matrices, when the stated rank condition holds, every critical point is column-rank deficient.The section establishes the generic rank-deficiency result by dimensionality counting.Source: §3 · pp. 10–11
  • A full-rank second-order critical point is globally optimal when its face has dimension below Δ + p; suboptimality requires dimension at least Δ + p.In the suboptimal case, the cost function must also be constant over that face.Source: §3 · pp. 12–13

4 Near optimality of near second-order critical points

The section relates approximate second-order criticality to bounded optimality gaps for the SDP. With compact feasibility and p = n + 1, satisfying approximate first- and second-order conditions guarantees approximate global optimality for any cost matrix.

4 Near optimality of near second-order critical points

  • The Riemannian trust-region method is described as converging to second-order critical points regardless of initialization.The cited convergence result motivates using such methods for the factorized problem.Source: §4 · p. 13
  • The optimality gap is bounded using gradient and curvature tolerances and the feasible set's trace bound R; with constant trace and a positive-definite feasible point, the bound uses ε_H R.The section defines R as the maximum trace over feasible SDP matrices.Source: §4 · p. 14
  • Extending Y to [Y|0] preserves its matrix YY^T, while a far-from-optimal approximate critical point maps to an approximately escapable saddle in the larger factor space.The theorem assumes the manifold regularity condition for both p and p + 1.Source: §4 · p. 15
  • With compact feasibility and p = n + 1, approximate first- and second-order criticality guarantees approximate global optimality for any cost matrix.The conditions bound the gradient norm and the Hessian's negative curvature.Source: §4 · pp. 15–16

5 Applications

The applications test the general guarantees by analyzing each problem’s constraint geometry and the faces of its SDP feasible set. They yield all-cost or almost-all-cost global-optimality guarantees for generalized eigenvalue, trust-region, sphere, and cut problems.

5.1 Generalized eigenvalue SDP

  • The generalized eigenvalue SDP is tight at rank one, and every second-order critical point of its factorization is globally optimal for any cost matrix, even at p=1.The facial-structure argument strengthens the almost-all-cost guarantee to all costs and all p≥1.Source: §5.1 · pp. 16–17

5.2 Trust-region subproblem SDP

  • For p≥2, every second-order critical point of the trust-region factorization is globally optimal for all problem data; at p=1, suboptimal critical points may occur.When p=2 and the factor has rank two, an optimal rank-one endpoint can be recovered by solving two scalar equations.Source: §5.2 · pp. 18–19

5.3 Optimization over several spheres

  • For optimization over k spheres, p≥max(2,k) guarantees globality for every cost matrix; the homogeneous variant has the same guarantee when p≥k.For the non-homogeneous problem, the paper also gives an almost-all-cost guarantee at a smaller, incompletely specified rank threshold.Source: §5.3 · pp. 19–20

5.4 Max-Cut and Orthogonal-Cut SDP

  • At sufficiently large rank, every second-order critical point is globally optimal for Orthogonal-Cut, including Max-Cut when d=1.A separate guarantee holds for almost all cost matrices at a rank threshold stated in the paper’s corollary.Source: §5.4 · p. 21

6 Discussion of the assumptions

The discussion explains the regularity and compactness assumptions behind the guarantees and identifies unresolved scope questions. In particular, it remains unclear whether the generic-cost theorem must exclude a zero-measure set of costs.

6 Discussion of the assumptions

  • Constraint qualifications make KKT conditions necessary at global optima; requiring them throughout the factorized feasible set leads to the paper’s regularity assumption.With linearly independent constraint matrices, that assumption holds exactly when every feasible SDP matrix is primal non-degenerate.Source: §6 · pp. 22–23
  • Compactness guarantees an SDP optimum and an extreme-point optimum with rank bounded by the constraint count; the paper says the rank bound is essentially optimal.The authors suggest compactness might be relaxed if candidate global optima remain bounded.Source: §6 · p. 22
  • It remains unresolved whether the generic-cost theorem must exclude a zero-measure set of cost matrices.The trust-region example requires such exclusions for an intermediate lemma, yet its excluded costs do not produce suboptimal second-order critical points in that example.Source: §6 · p. 22
  • For linearly independent constraint matrices, primal non-degeneracy at every feasible point is equivalent to the paper’s smoothness condition.Primal non-degeneracy is defined by the sum of the matrix-rank tangent space and the constraint operator’s kernel spanning all symmetric matrices.Source: §6 · p. 23

7 Conclusions and perspectives

The paper identifies conditions under which Burer–Monteiro factorization is safe despite non-convexity. It leaves relaxing those assumptions and understanding approximate second-order points at smaller p as open directions.

7 Conclusions and perspectives

  • Under Assumption 1.1 and additional conditions on p, compactness, and the cost matrix, Burer–Monteiro factorization is safe despite non-convexity.The paper identifies relaxing these assumptions as a direction for future research.Source: §7 · p. 23
  • Whether approximate second-order critical points are approximately optimal for p well below n remains an open practical question.The paper points to smoothed analysis as one possible direction, while noting that early work leaves room for improvement.Source: §7 · p. 23
  • Determining whether the assumptions can be relaxed is identified as a future research direction.Source: §7 · p. 23

Appendix A: Consequences and properties of Assumption 1.1

The appendices connect Assumption 1.1 to smoothness and describe how it behaves across factor dimensions. They also characterize the face containing a factored feasible point through perturbations of its factor.

Appendix A: Consequences and properties of Assumption 1.1

  • Assumption 1.1a makes the constraint differential full rank on M, while Assumption 1.1b gives it constant rank in a neighborhood, establishing smoothness of M.The differential rank is the dimension of the span of {A1Y,...,AmY}.Source: Appendix A · p. 23
  • The proof of Proposition 1.3 treats smaller nonempty factor dimensions and, when p=n, dimensions above n by representing factors with zero-padded columns.Source: Appendix A · pp. 23–24

Appendix B: The facial structure of C

  • The face containing X=YY^T consists of feasible perturbations of the form X+YAY^T, with symmetric A constrained by positive semidefiniteness and the linear constraints.The proof identifies the perturbation condition as L_X(A)=0.Source: Appendix B · p. 24

Appendix C: Faces of the Ortho-Cut SDP

For the Ortho-Cut SDP, the appendix bounds the dimension of a face by counting independent constraints on a factor-space matrix. A construction shows the bound is essentially tight, with an explicit dimension when d divides p.

Appendix C: Faces of the Ortho-Cut SDP

  • The proof selects rows that span the factor and forms a constraint subset T from slice constraints involving selected rows.It then counts the subset to show it contains enough independent constraints.Source: Appendix C · p. 25
  • The selected constraint matrices are linearly independent because their expansions occupy disjoint basis subsets across slices.Source: Appendix C · p. 25
  • At least p(d+1)/2 independent constraints act on A, yielding an upper bound on the face dimension; when d divides p, a construction attains the stated dimension.The construction gives dimF_YY^T = p(p+1)/2 − p(d+1)/2.Source: Appendix C · p. 26

Appendix D: Equivalence of global non-degeneracy and smoothness

The appendix shows that global primal non-degeneracy is equivalent to Assumption 1.1a. The equivalence follows by comparing linear dependence among constraint matrices projected onto the range of X with dependence among their products with Y.

Appendix D: Equivalence of global non-degeneracy and smoothness

  • The proof uses that span(Y)=span(Q1), where Q1 spans the positive-eigenvalue range of X, to transfer the dependence test between Y and X.Source: Appendix D · p. 26
  • For the dependence test, primal non-degeneracy is expressed as linear independence of the projected constraint matrices Bk.Source: Appendix D · p. 26
  • At each feasible X=YY^T, primal non-degeneracy is equivalent to linear independence of {A1Y,...,AmY}, making global primal non-degeneracy equivalent to Assumption 1.1a.Source: Appendix D · p. 26
Loading 1804.02008v2…