Sparse PSD approximation of the PSD cone
- PDF / 437,221 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 208 Views
Series A
Sparse PSD approximation of the PSD cone Grigoriy Blekherman1 · Santanu S. Dey1 · Marco Molinaro2 · Shengding Sun1 Received: 7 February 2020 / Accepted: 7 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k × k principal submatrices—we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objective function value of the original SDP. In this paper, we formally attempt to compare the strength of the sparse SDP relaxation vis-à-vis the original SDP from a theoretical perspective. In order to simplify the question, we arrive at a data independent version of it, where we compare the sizes of SDP cone and the k-PSD closure, which is the cone of matrices where PSD-ness is enforced on all k × k principal submatrices. In particular, we investigate the question of how far a matrix of unit Frobenius norm in the k-PSD closure can be from the SDP cone. We provide two incomparable upper bounds on this farthest distance as a function of k and n. We also provide matching lower bounds, which show that the upper bounds are tight within a constant in different regimes of k and n. Other than linear algebra techniques, we extensively use probabilistic methods to arrive at these bounds. One of the lower bounds is obtained by observing a connection between matrices in the k-PSD closure and matrices satisfying the restricted isometry property. Mathematics Subject Classification 15A42 · 15B48 · 15B57 · 90C22
B
Shengding Sun [email protected]
1
Georgia Institute of Technology, Atlanta, USA
2
PUC-Rio, Rio de Janeiro, Brazil
123
G. Blekherman et al.
1 Introduction 1.1 Motivation Semidefinite programming (SDP) relaxations are an important tool to provide dual bounds for many discrete and continuous non-convex optimization problems [35]. These SDP relaxations have the form min C, X s.t. Ai , X ≤ bi ∀i ∈ {1, . . . , m} n, X ∈ S+
(1)
n denotes where C and the Ai ’s are n × n matrices, M, N := i, j Mi j Ni j , and S+ the cone of n × n symmetric positive semidefinite (PSD) matrices: n = {X ∈ Rn×n | X = X T , x X x ≥ 0, ∀x ∈ Rn }. S+
In practice, it is often computationally challenging to solve large-scale instances n . One technique to address this of SDPs due to the global PSD constraint X ∈ S+ issue is to consider a further relaxation that replaces the PSD cone by a larger one n . In particular, one can enforce PSD-ness on (some or all) smaller k × k § ⊇ S+ principal submatrices of X , i.e., we consider the problem min C, X s.t. Ai , X ≤ bi ∀i ∈ {1, . . . , m} k. selected k × k principal submatrices of X ∈ S+
(2)
We call such a relax
Data Loading...
