Verifying feasibility of degenerate semidefinite programs

本文讨论了解决半定规划（SDP）可行性问题的算法方面，也称为线性矩阵不等式（LMI）。由于在某些SDP实例中，所有可行解均具有无理数，因此使用使用有理数的数值求解器只能找到近似解。我们研究以下问题：是否可能使用足够接近某个精确解的近似解来证明给定SDP的可行性？现有方法假设存在有理可行解（并使用诸如舍入和格基约简算法等技术）。我们提出了一种不需要这种假设的替代方法。更具体地说，我们展示了如何构造一组多项式方程系统，其实数解集保证具有隔离的正确解（假设目标精确解是最大秩）。这允许特别地使用实代数几何算法来解决多项式方程组，从而产生SDP的混合（或符号数值）方法。我们在实验中将其与[Henrion，Naldi，Safey El Din; SIAM J. Optim。，2016]中的纯符号方法进行了比较。混合方法能够证明[Henrion，Naldi，Safey El Din; SIAM J. Optim。，2016]无法证明的许多SDP实例的可行性。我们认为我们的方法可能具有其他用途，例如使用数值代数几何方法来细化多项式方程组的近似解。

本文旨在解决半定规划（SDP）中存在无理解的情况下，如何使用近似解证明可行性的问题。

提出一种不需要假设存在有理可行解的新方法，通过构建一个多项式方程组来证明实数解集中存在唯一的正确解。

本文提出的方法可以使用实代数几何算法来解决SDP问题，实验结果表明该方法比之前的方法更有效。此外，该方法也可以用于提高近似解的精度。

近期的相关研究包括Henrion, Naldi, Safey El Din在2016年发表的一篇关于纯符号方法的论文。