Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs

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 × 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 nonconvex 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 nonconvexity, 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. © 2019 Wiley Periodicals, Inc.     

An Accelerated First-Order Method for Non-convex Optimization on Manifolds

We describe the first gradient methods on Riemannian manifolds to achieve accelerated rates in the non-convex case. Under Lipschitz assumptions on the Riemannian gradient and Hessian of the cost function, these methods find approximate first-order critical points faster than regular gradient descent. A randomized version also finds approximate second-order critical points. Both the algorithms and their analyses build extensively on existing work in the Euclidean case. The basic operation consists in running the Euclidean accelerated gradient descent method (appropriately safe-guarded against non-convexity) in the current tangent space, then moving back to the manifold and repeating. This requires lifting the cost function from the manifold to the tangent space, which can be done for example through the Riemannian exponential map. For this approach to succeed, the lifted cost function (called the pullback) must retain certain Lipschitz properties. As a contribution of independent interest, we prove precise claims to that effect, with explicit constants. Those claims are affected by the Riemannian curvature of the manifold, which in turn affects the worst-case complexity bounds for our optimization algorithms.

     

Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Motivated by stochastic 0–1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: \(P = \big \{(w,x)\in \mathbb {R}\times \left\{ 0,1\right\} ^N: w \le f(a'x + d), b'x \le B\big \}\) where N is a positive integer, \(f:\mathbb {R}\mapsto \mathbb {R}\) is a concave function, \(a, b \in \mathbb {R}^N\) are nonnegative vectors, d is a real number and B is a positive real number. We propose a family of inequalities for the convex hull of P by exploiting submodularity of the function \(f(a'x + d)\) over \(\{0,1\}^N\) and the knapsack constraint \(b'x \le B\). Computational effectiveness of the proposed inequalities within a branch-and-cut framework is illustrated using instances of an expected utility capital budgeting problem.     

Adaptive regularization with cubics on manifolds

Mathematical Programming - Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the trust-region method, its iterations can be thought of as...     

Matrix probing: A randomized preconditioner for the wave-equation Hessian

This paper considers the problem of approximating the inverse of the wave-equation Hessian, also called normal operator, in seismology and other types of wave-based imaging. An expansion scheme for the pseudodifferential symbol of the inverse Hessian is set up. The coefficients in this expansion are found via least-squares fitting from a certain number of applications of the normal operator on adequate randomized trial functions built in curvelet space. It is found that the number of parameters that can be fitted increases with the amount of information present in the trial functions, with high probability. Once an approximate inverse Hessian is available, application to an image of the model can be done in very low complexity. Numerical experiments show that randomized operator fitting offers a compelling preconditioner for the linearized seismic inversion problem.     

Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy

Mathematical Programming - We consider the problem of provably finding a stationary point of a smooth function to be minimized on the variety of bounded-rank matrices. This turns out to be...