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
Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
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
- PAR ID:
- 10176075
- Date Published:
- Journal Name:
- 2019 IEEE 58th Conference on Decision and Control (CDC)
- Page Range / eLocation ID:
- 4916 to 4921
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper considers the relationship between semidefinite programs (SDPs), matrix rank, and maximum cuts of graphs. Utilizing complementary slackness conditions for SDPs, we investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank n-1 . Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs.more » « less
-
more » « less
Abstract In this paper, we show the important roles of sharp minima and strong minima for robust recovery. We also obtain several characterizations of sharp minima for convex regularized optimization problems. Our characterizations are quantitative and verifiable especially for the case of decomposable norm regularized problems including sparsity, group-sparsity and low-rank convex problems. For group-sparsity optimization problems, we show that a unique solution is a strong solution and obtains quantitative characterizations for solution uniqueness.
-
The minimum-gain eigenvalue assignment/pole placement problem (MGEAP) is a classical problem in LTI systems with static state feedback. In this paper, we study the MGEAP when the state feedback has arbitrary sparsity constraints. We formulate the sparse MGEAP problem as an equality-constrained optimization problem and present an analytical characterization of its locally optimal solution in terms of eigenvector matrices of the closed loop system. This result is used to provide a geometric interpretation of the solution of the non-sparse MGEAP, thereby providing additional insights for this classical problem. Further, we develop an iterative projected gradient descent algorithm to obtain local solutions for the sparse MGEAP using a parametrization based on the Sylvester equation. We present a heuristic algorithm to compute the projections, which also provides a novel method to solve the sparse EAP. Also, a relaxed version of the sparse MGEAP is presented and an algorithm is developed to obtain approximately sparse local solutions to the MGEAP. Finally, numerical studies are presented to compare the properties of the algorithms, which suggest that the proposed projecmore » « less
-
Tensor decomposition on big data has attracted significant attention recently. Among the most popular methods is a class of algorithms that leverages compression in order to reduce the size of the tensor and potentially parallelize computations. A fundamental requirement for such methods to work properly is that the low-rank tensor structure is retained upon compression. In lieu of efficient and realistic means of computing and studying the effects of compression on the low rank of a tensor, we study the effects of compression on the core consistency; a widely used heuristic that has been used as a proxy for estimating that low rank. We provide theoretical analysis, where we identify sufficient conditions for the compression such that the core consistency is preserved, and we conduct extensive experiments that validate our analysis. Further, we explore popular compression schemes and how they affect the core consistency.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CDC40024.2019.9029620
