Mar, 2017

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

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

    本文研究了一类包括最大割、随机块模型社区检测、鲁棒 PCA、相位恢复和旋转同步等应用的半定规划 SDP，表明以 Burer-Monteiro 公式为代表的低秩 SDP 几乎从不具有虚假的局部最优解。

    Jun, 2016

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

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

    Oct, 2009

  • 二次罚函数半定规划低秩解的平滑分析

    本文采用 Burer-Monteiro 分解方法解决 SDP 问题，考虑约束条件次数随所需最优解的秩呈次二比例增长时，所有的近似局部最优解均为全局最优解，并将这个结果应用于 Max-Cut 和矩阵填充问题。

    Mar, 2018

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

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

    Jun, 2024

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

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

    Sep, 2020

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

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

    Sep, 2017

  • 在正交群和幺正群上近似求解 Little Grothendieck 问题

    本文主要研究了 Grothendieck 问题的一种自然扩展，即在正交群上的小 Grothendieck 问题。通过基于半定规划的算法来解决，我们提出了一种名为正交切割（Orthogonal-Cut）的近似算法，并展示其最大近似比为常数。这种方法可以自然地扩展到复值情况，同时也可以用于 Procrustes 问题的近似。

    Aug, 2013

  • 半定规划多参考序列比对

    该研究提供了一种基于半定规划松弛的多参考点对齐问题的最大似然估计的近似算法，并在应用中表现良好，并提供了稳定性保证。

    Aug, 2013

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

    本文针对包装和覆盖半正定程序（或正半定规划）的近似求解，研究了多对数深度算法的设计，并提出了一种基于优化框架的简单算法，其正确性基于 Lieb-Thirring 不等式的新矩阵不等式和梯度截断技术的随机变体。

    Jul, 2015

  • 半定松弛中的相变

    这篇论文主要探讨了应用于信号处理、数据挖掘和机器学习中的统计推理问题，当数据的维度很高时，常常导致较难处理的组合优化问题。文中提出了通过构建这些组合优化问题的凸松弛来解决问题的热门思想。其中，半定规划松弛是该家族中最有力的方法之一，并且出人意料地适用于形如矩阵或图形的数据问题。作者对几个经典的半定规划松弛模型进行了研究，尤其是适用于图同步和网络中的社区检测等统计问题的模型。通过将这些优化问题映射到带有向量自旋的统计力学模型中，使用统计力学中的非严谨技术来描述相应的相变，以期阐明半定规划松弛在高维统计问题中解决问题的有效性。

    Nov, 2015