论文标题
全球收敛性LP和基于SOCP的算法，用于半决赛编程
A Globally Convergent LP and SOCP-based algorithm for Semidefinite Programming
论文作者
论文摘要
半决赛程序（SDP）是数值优化中最通用的框架之一，它是许多锥形程序的概括，也是NP-HARD组合问题的放松。他们的主要缺点是他们的计算和内存复杂性，这对通过现成的SDP求解器解决的问题的大小设定了实际限制。为了避免这一事实，已经提出了许多算法来利用特定问题的结构并提高这些问题实例的SDP的可扩展性。然而，对于通用Case dps而言，进展并不那么陡峭。在本文中，以艾哈迈迪和霍尔的较早结果的激励，我们表明，通过执行一系列计算较少的线性或二阶锥体程序，可以将一般的SDP求解到$ε$ - 最佳性。此外，我们还提供了实现$ε$最佳性所需的迭代次数。使用随机SDP和SDPLIB数据集中的众所周知的问题来说明这些结果。
Semidefinite programs (SDP) are one of the most versatile frameworks in numerical optimization, serving as generalizations of many conic programs and as relaxations of NP-hard combinatorial problems. Their main drawback is their computational and memory complexity, which sets a practical limit to the size of problems solvable by off-the-shelf SDP solvers. To circumvent this fact, many algorithms have been proposed to exploit the structure of particular problems and increase the scalability of SDPs for those problem instances. Progress has been less steep, however, for general-case SDPs. In this paper, motivated by earlier results by Ahmadi and Hall, we show that a general SDP can be solved to $ε$-optimality, in polynomial time, by performing a sequence of less computationally demanding Linear or Second Order Cone programs. In addition, we provide a bound on the number of iterations required to achieve $ε$-optimality. These results are illustrated using random SDPs and well-known problems from the SDPLib dataset.
