More Like this

1. Smoothed analysis of the low-rank approach for smooth semidefinite programs

   Pumir, Thomas; Jelassi, Samy; Boumal, Nicolas (January 2018, Neural Information Processing Systems (NIPS))

   We consider semidefinite programs (SDPs) of size n with equality constraints. In order to overcome scalability issues, Burer and Monteiro proposed a factorized approach based on optimizing over a matrix Y of size nk such that X = Y Y  is the SDP variable. The advantages of such formulation are twofold: the dimension of the optimization variable is reduced, and positive semidefiniteness is naturally enforced. However, optimization in Y is non-convex. In prior work, it has been shown that, when the constraints on the factorized variable regularly define a smooth manifold, provided k is large enough, for almost all cost matrices, all second-order stationary points (SOSPs) are optimal. Importantly, in practice, one can only compute points which approximately satisfy necessary optimality conditions, leading to the question: are such points also approximately optimal? To answer it, under similar assumptions, we use smoothed analysis to show that approximate SOSPs for a randomly perturbed objective function are approximate global optima, with k scaling like the square root of the number of constraints (up to log factors). Moreover, we bound the optimality gap at the approximate solution of the perturbed problem with respect to the original problem. We particularize our results to an SDP relaxation of phase retrieval. 

   more » « less
2. Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form

   Bhojanapalli, Srinadh; Boumal, Nicolas; Jain, Prateek; Netrapalli, Praneeth (January 2018, Proceedings of the 31st Conference On Learning Theory, PMLR)

   Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer–Monteiro factorization approach for solving SDPs. For a large class of SDPs, upon random perturbation of the cost matrix, with high probability, we show that all approximate second-order stationary points are approximate global optima for the penalty formulation of appropriately rank-constrained SDPs, as long as the number of constraints scales sub-quadratically with the desired rank. Our result is based on a simple penalty function formulation of the rank-constrained SDP along with a smoothed analysis to avoid worst-case cost matrices. We particularize our results to two applications, namely, Max-Cut and matrix completion. 

   more » « less
3. Globally Convergent Low Complexity Algorithms for Semidefinite Programming

   https://doi.org/10.1109/CDC45484.2021.9682942  

   Roig-Solvas, Biel; Sznaier, M. (December 2021, 60th IEEE Conf. Decision and Control)

   Semidefinite programs (SDP) are a staple of today’s systems theory, with applications ranging from robust control to systems identification. However, current state-of-the art solution methods have poor scaling properties, and thus are limited to relatively moderate size problems. Recently, several approximations have been proposed where the original SDP is relaxed to a sequence of lower complexity problems (such as linear programs (LPs) or second order cone programs (SOCPs)). While successful in many cases, there is no guarantee that these relaxations converge to the global optimum of the original program. Indeed, examples exists where these relaxations "get stuck" at suboptimal solutions. To circumvent this difficulty in this paper we propose an algorithm to solve SDPs based on solving a sequence of LPs or SOCPs, guaranteed to converge in a finite number of steps to an ε-suboptimal solution of the original problem. We further provide a bound on the number of steps required, as a function of ε and the problem data. 

   more » « less
4. Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps

   https://doi.org/10.1287/moor.2020.1100  

   Gutekunst, Samuel C.; Williamson, David P. (July 2021, Mathematics of Operations Research)

   null (Ed.)

   The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75–91.] present a semidefinite program (SDP) based on permutation matrices and symmetry reduction; they show that it is incomparable to the subtour elimination linear program but generally dominates it on small instances. We provide a family of simplicial TSP instances that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in section 2 of Sotirov [Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds., Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 795–819.]. In contrast, the subtour linear program performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP. 

   more » « less
5. Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering

   https://doi.org/10.1109/CDC40024.2019.9029620  

   Miller, Jared; Zheng, Yang; Roig-Solvas, Biel; Sznaier, Mario; Papachristodoulou, Antonis (December 2019, 2019 IEEE 58th Conference on Decision and Control (CDC))

   Semidefinite programs (SDPs) often arise in relaxations of some NP-hard problems, and if the solution of the SDP obeys certain rank constraints, the relaxation will be tight. Decomposition methods based on chordal sparsity have already been applied to speed up the solution of sparse SDPs, but methods for dealing with rank constraints are underdeveloped. This paper leverages a minimum rank completion result to decompose the rank constraint on a single large matrix into multiple rank constraints on a set of smaller matrices. The re-weighted heuristic is used as a proxy for rank, and the specific form of the heuristic preserves the sparsity pattern between iterations. Implementations of rank-minimized SDPs through interior-point and first-order algorithms are discussed. The problem of subspace clustering is used to demonstrate the computational improvement of the proposed method. 

   more » « less