论文标题
重新访问频谱束方法：原始偶（子）线性收敛速率
Revisiting Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Rates
论文作者
论文摘要
Helmberg和Rendl提出的光谱捆绑捆绑方法已确立，用于解决大规模半际计划（SDP），这要归功于其在迭代计算复杂性的较低情况下和强大的实践表现。在本文中，我们重新访问了这种经典方法，显示其仅在很强的二元性下，就原始和双重SDP而言，达到了透明性收敛速率，可以补充先前的原始双重收敛保证。此外，如果（1）在结构上，SDP允许严格的互补性，并且（2）算法从算法上捕获了最佳解决方案的等级，则我们显示了该方法的速度至线性收敛。这种互补和低级结构在许多现代和古典应用中都普遍存在。线性收敛结果是通过特征值近似引理建立的，这可能具有独立的关注。从数值上讲，我们证实了我们的理论发现，即对于现代和古典应用，在这些条件下，光谱束方法会加快。最后，我们表明，光谱束方法与最近的矩阵草图技术相结合，能够在几分钟内解决数十亿个决策变量的SDP。
The spectral bundle method proposed by Helmberg and Rendl is well established for solving large-scale semidefinite programs (SDP) thanks to its low per iteration computational complexity and strong practical performance. In this paper, we revisit this classic method showing it achieves sublinear convergence rates in terms of both primal and dual SDPs under merely strong duality, complementing previous guarantees on primal-dual convergence. Moreover, we show the method speeds up to linear convergence if (1) structurally, the SDP admits strict complementarity, and (2) algorithmically, the bundle method captures the rank of the optimal solutions. Such complementary and low rank structure is prevalent in many modern and classical applications. The linear convergent result is established via an eigenvalue approximation lemma which might be of independent interest. Numerically, we confirm our theoretical findings that the spectral bundle method, for modern and classical applications, speeds up under these conditions. Finally, we show that the spectral bundle method combined with a recent matrix sketching technique is able to solve an SDP with billions of decision variables in a matter of minutes.
