Sparse PSD approximation of the PSD cone
Sparse PSD approximation of the PSD cone
复制标题
PSD 锥体的稀疏 PSD 近似
DOI：
10.1007/s10107-020-01578-y
复制
发表时间：
2020
影响因子：
2.7
通讯作者：
Sun, Shengding
中科院分区：
文献类型：
--
作者：
Blekherman, Grigoriy;Dey, Santanu S.;Molinaro, Marco;Sun, Shengding
虽然半定规划（SDP）问题在理论上是多项式可解的，但在实践中通常很难解决大型SDP实例。解决这个问题的一种方法是放松全局正半定性（PSD）约束，只对较小的主子阵强制PSD性，我们称之为稀疏SDP松弛。令人惊讶的是，根据经验观察到，在某些情况下，这种方法似乎产生接近原始SDP的最佳目标函数值的边界。在本文中，我们正式尝试从理论角度比较稀疏SDP松弛与原始SDP的强度。为了简化这个问题，我们得到了一个与数据无关的版本，在这里我们比较了SDP锥和PSD闭包的大小，PSD闭包是一个在所有主要子矩阵上强制PSD性的矩阵锥。特别是，我们调查的问题有多远的单位Frobenius范数矩阵的PSD封闭可以从SDP锥。我们提供了两个无与伦比的上限，这个最远的距离作为kandn的函数。我们还提供了匹配的下界，这表明，上界是紧在一个常数在不同的政权ofkandn。除了线性代数技术，我们广泛使用概率方法来达到这些界限。其中一个下界是通过观察PSD闭包中的矩阵和满足限制等距性质的矩阵之间的连接而获得的。
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 smallerprincipal submatrices—we call this thesparse 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-PSD closure, which is the cone of matrices where PSD-ness is enforced on allprincipal submatrices. In particular, we investigate the question of how far a matrix of unit Frobenius norm in the-PSD closure can be from the SDP cone. We provide two incomparable upper bounds on this farthest distance as a function ofkandn. We also provide matching lower bounds, which show that the upper bounds are tight within a constant in different regimes ofkandn. 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-PSD closure and matrices satisfying the restricted isometry property.
登录
查看更多内容
具有稀疏不等式的近似多面体
影响因子：
2.7
作者：
Santanu S. Dey;M. Molinaro;Qianyi Wang
通讯作者：
Qianyi Wang
二项分布中的平均值、中位数和众数
DOI：
--
发表时间：
1980
期刊：
影响因子：
--
作者：
R. Kaas;J. Buhrman
通讯作者：
J. Buhrman
影响因子：
2.7
作者：
E. Amaldi;Stefano Coniglio;Stefano Gualandi
通讯作者：
Stefano Gualandi
关于有界系数或稀疏约束的整数规划的大小
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Christopher Hojny;Hendrik Lüthen;M. Pfetsch
通讯作者：
M. Pfetsch
提升和投影切割面的稀疏性
DOI：
--
发表时间：
2012
期刊：
OR
影响因子：
--
作者：
Matthias Walter
通讯作者：
Matthias Walter