An Echelon Form of Weakly Infeasible Semidefinite Programs and Bad Projections of the psd Cone
An Echelon Form of Weakly Infeasible Semidefinite Programs and Bad Projections of the psd Cone
复制标题
弱不可行半定规划的梯形形式和 psd 锥体的不良投影
DOI：
10.1007/s10208-022-09552-0
复制
发表时间：
2022
影响因子：
3
通讯作者：
Touzov, Aleksandr
中科院分区：
文献类型：
--
作者：
Pataki, Gábor;Touzov, Aleksandr
弱不可行半定规划(SDP)没有可行解，但存在违反约束条件任意小的近似解。这些SDP是不适定的，在数值上往往是不可解的。它们还与将半正定矩阵的锥映射到非闭集的“坏”线性投影密切相关。我们描述了一个简单的弱不可行SDP的梯形形式，它具有以下性质：(I)它是通过初等行运算和同余变换得到的；(Ii)它使弱不可行变得明显；(Iii)它允许我们通过一个初等组合算法来构造任何弱不可行SDP或糟糕的线性投影。基于我们的梯队形式，我们生成了一个计算非常困难的SDP库。最后，我们证明了文献中的一些SDP是我们的梯形形式，例如，由最小化Motzkin著名多项式的平方和松弛得到的SDP。
A weakly infeasible semidefinite program (SDP) has no feasible solution, but it has approximate solutions whose constraint violation is arbitrarily small. These SDPs are ill-posed and numerically often unsolvable. They are also closely related to “bad” linear projections that map the cone of positive semidefinite matrices to a nonclosed set. We describe a simple echelon form of weakly infeasible SDPs with the following properties: (i) it is obtained by elementary row operations and congruence transformations, (ii) it makes weak infeasibility evident, and (iii) it permits us to construct any weakly infeasible SDP or bad linear projection by an elementary combinatorial algorithm. Based on our echelon form, we generate a library of computationally very difficult SDPs. Finally, we show that some SDPs in the literature are in our echelon form, for example, the SDP from the sum-of-squares relaxation of minimizing Motzkin’s famous polynomial.