A Globally Convergent LP and SOCP-based algorithm for Semidefinite Programming

A Globally Convergent LP and SOCP-based algorithm for Semidefinite Programming
复制标题

基于全局收敛LP和SOCP的半定规划算法

DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
M. Sznaier
M. Sznaier
中科院分区：
--
文献类型：
--
作者：
Biel Roig;M. Sznaier

文献摘要

被引文献

相似文献

半定规划（SDP）是数值优化中最通用的框架之一，作为许多圆锥规划的推广和NP-难组合问题的松弛。它们的主要缺点是它们的计算和内存复杂性，这对现成的SDP求解器可解决的问题的大小设置了实际限制。为了规避这一事实，已经提出了许多算法来利用特定问题的结构，并增加这些问题实例的SDP的可扩展性。然而，一般情况下的服务提供点的进展并不那么陡峭。在本文中，由艾哈迈迪和霍尔早期的结果的动机，我们表明，一般SDP可以解决$-最优，在多项式时间内，通过执行一系列计算要求不高的线性或二阶锥程序。此外，我们提供了一个约束上的迭代次数需要达到$-最优。这些结果使用随机SDPs和来自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 $epsilon$-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 $epsilon$-optimality. These results are illustrated using random SDPs and well-known problems from the SDPLib dataset.