Scalable Semidefinite Programming
Scalable Semidefinite Programming
复制标题
DOI：
10.1137/19m1305045
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
A. Yurtsever;J. Tropp;Olivier Fercoq;Madeleine Udell;V. Cevher
中科院分区：
文献类型：
--
作者：
A. Yurtsever;J. Tropp;Olivier Fercoq;Madeleine Udell;V. Cevher
半定规划（SDP）是凸优化的一个强大框架，在数据科学应用中具有惊人的潜力。本文提出了一个可证明正确的算法，解决大型SDP问题，节省了存储和运算成本。数值实验表明，该方法是有效的一系列应用，包括松弛的MaxCut，抽象相位检索，和二次分配。在笔记本电脑上运行，该算法可以处理矩阵变量超过10 ^{13}$条目的SDP实例。
Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct algorithm for solving large SDP problems by economizing on both the storage and the arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop, the algorithm can handle SDP instances where the matrix variable has over $10^{13}$ entries.