论文标题
一类半决赛程序的加速一阶方法
Accelerated first-order methods for a class of semidefinite programs
论文作者
论文摘要
本文介绍了一种新的存储 - 最佳一阶方法（FOM），CERTSDP，用于求解一类特殊的半芬特程序（SDP）以高精度。我们考虑的SDP类别（确切的QMP样SDP）的特征是低级别解决方案，对SDP溶液限制对小子空间的限制的先验知识以及标准的规则性假设（例如严格互补）。至关重要的是，我们展示了如何使用严格互补性证书来构建一个低维的强凸极小问题，其优化器与SDP优化器的分解相吻合。从算法的角度来看，我们展示了如何构建必要的证书以及如何有效地解决最小值问题。我们的理论结果伴随着初步数值实验，这表明CERTSDP在大型稀疏精确QMP样SDP上的当前最新方法明显优于当前的最新方法。
This paper introduces a new storage-optimal first-order method (FOM), CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs, is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a certificate of strict complementarity to construct a low-dimensional strongly convex minimax problem whose optimizer coincides with a factorization of the SDP optimizer. From an algorithmic standpoint, we show how to construct the necessary certificate and how to solve the minimax problem efficiently. We accompany our theoretical results with preliminary numerical experiments suggesting that CertSDP significantly outperforms current state-of-the-art methods on large sparse exact QMP-like SDPs.
