Jul, 2015

使用优化获得宽度无关、并行、简单、更快的正定半定规划求解器

PDF
TL;DR本文针对包装和覆盖半正定程序（或正半定规划）的近似求解，研究了多对数深度算法的设计，并提出了一种基于优化框架的简单算法，其正确性基于 Lieb-Thirring 不等式的新矩阵不等式和梯度截断技术的随机变体。
发现论文，激发创造
  • 正半定规划的更快速、更简单的宽度独立并行算法

    本文研究了正半定规划的近似算法，提出了一种简单的 NC 并行算法，其迭代次数为 O (1/ϵ³ log³ n)，总工作量近似为因子分解中非零条目数的线性级别。

    Jan, 2012

  • 追踪有界 SDP 的非最优界限为 SDPLR + 提供了更快和可扩展的低秩 SDP 求解器

    通过低秩分解和子优度界限优化，加速计算并节省存储成本，实现可扩展的半正定规划求解器。

    Jun, 2024

  • 半定规划的更快内点方法

    本文介绍一种更快的内点法，用于求解具有变量大小的一般半定规划问题，并解释了算法的运行时间和矩阵乘法的指数和相对精度之间的关系。

    Sep, 2020

  • 通过 Grothendieck 不等式解同步和 MaxCut 问题的 SDP

    通过引入非凸约束形式并应用 Riemannian trust-region 方法，该论文研究了 MaxCut 和同步问题中的秩约束半定规划，并建立了一个 Grothendieck 型不等式证明局部最大值和危险鞍点都在离全局最大值一个小倍数距离的情况下，SDPs 可以在已知精度内得到解决。

    Mar, 2017

  • 半定最优化问题的多面体和二阶圆锥分解

    研究了一种用于半定规划问题（SDOs）的切平面方法，证明了该方法基于有界性假设的收敛性。通过将该方法的收敛速度与初始外近似的直径联系起来，我们证明了当使用二阶锥逼近而不是线性逼近时该方法的表现更好。我们将该方法用于提供数千个协变量的稀疏 PCA 问题的边界间隙，并解决了 500x500 矩阵上的核范数问题。

    Oct, 2019

  • 混合装箱和覆盖线性规划的更快的宽度相关算法

    本文提出了基于面积凸性的混合装箱问题 LP 的宽度相关算法并进一步将其应用于最密子图问题中，实现了比宽度独立算法更高的精度。

    Sep, 2019

  • 正半定格罗滕迪克问题的秩约束

    本文设计了一个多项式时间逼近算法以解决正半定 Grothendieck 问题，得到了逼近比例，并证明了该逼近比例是最优的。作者也提出了一种改进的算法，并应用它来解决 Laplacian 矩阵的情况。

    Oct, 2009

  • 半定规划层次结构在图模型推断中的应用

    本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。

    Sep, 2017

  • 最小化多项式函数

    比较多元多项式函数全局优化算法，证明了使用具有半定规划的平方和松弛技术比代数方法更有效，并为实数代数几何中的广泛计算问题提供了可能性。

    Mar, 2001

  • QAP 的 SDP 松弛问题的 ADMM 算法

    本文提出使用 ADMM 算法来解决 SDP 松弛问题，该方法具有低成本迭代、获取低秩解的方式以及简单添加切平面约束的优点，在与目前最佳算法比较中表现出出色的鲁棒性、效率和改进的结果。

    Dec, 2015