A Primal-Dual Framework for Symmetric Cone Programming

本文介绍了一种用于解决对称锥规划（Symmetric Cone Programs，SCP）的原始-对偶算法框架，这是一种通用的优化模型，统一和扩展了线性、二阶锥（Second-Order Cone，SOCP）和半定规划（Semidefinite Programming，SDP）。我们的工作推广了Arora和Kale介绍的SDP原始-对偶框架，利用了对称锥的乘法权重更新方法（Multiplicative Weights Update method，MWU）的最新扩展。超越现有工作，我们的框架可以处理SOCP和混合SCP，具有近乎线性的时间复杂度，并且可以有效地并行化。为了说明我们框架的有效性，我们将其用于开发两个几何优化问题的近似算法：最小包围球问题和支持向量机问题。我们的理论分析表明，这两个算法计算近似解的运行时间几乎是线性的，并且随着输入规模的增加，其并行深度呈对数多项式级别增长。我们将我们的算法与CGAL以及应用于这些问题的内点求解器进行比较。实验表明，我们的算法在CPU上实现时非常高效，并且在GPU上并行化时可以实现大幅加速，使我们能够解决这些问题的大规模实例。

本文旨在引入一种原始-对偶算法框架，用于解决对称锥规划（SCP）问题，这是一个统一和扩展了线性规划、二阶锥规划（SOCP）和半定规划（SDP）的多功能优化模型。作者试图解决SCP问题的求解效率和可扩展性问题。

本文提出了一种原始-对偶算法框架，用于解决SCP问题，该框架可以处理SOCP和混合SCP问题，并具有近乎线性的时间复杂度和有效的并行性。作者还使用该框架开发了两个近似算法，用于解决几何优化问题：最小包围球问题和支持向量机问题。

本文的亮点包括：1.提出了一种原始-对偶算法框架，可以解决SCP问题，具有高效性和可扩展性；2.开发了两个近似算法用于解决几何优化问题，该算法在实践中表现出高效性；3.作者进行了大量实验，证明了算法的有效性和可扩展性。

最近在这个领域中，还有一些相关的研究，例如Arora和Kale提出的SDP的原始-对偶框架。