Mar, 2017

半定规划方法求解稀疏图的二次分配问题

PDF
TL;DR本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题，采用正半定矩阵进行松弛，并通过聚类来加强松弛，使得计算复杂度和运行时间得到了缩减，可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。
quadratic assignment problemsemidefinite programmingpositive semidefinite matricesaugmented direction method of multipliersspectroscopy
发现论文，激发创造
  • QAP 的 SDP 松弛问题的 ADMM 算法

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

    Dec, 2015

  • 解决二元二次问题的快速半正定方法

    本文介绍了一种针对大规模问题的新型 SDP 公式，具有类似于传统 SDP 公式的松弛界限及较高的计算效率，可用于解决各种应用程序，包括聚类，图像分割，共同分割和注册。

    Apr, 2013

  • 大规模（脑）图匹配的快速近似二次规划

    本文介绍了一种快速的近似二次分配算法（FAQ），能够更高效地在大数据和图值数据上处理 QAP 问题，通过在 C.elegans 连通图匹配案例上的实证表明其优越性。

    Dec, 2011

  • 利用半定松弛和应用程序实现大规模的二值二次规划

    本文提出了一种针对大规模二次二次规划问题的新型 SDP（半定规划）公式，并基于此提出了两种求解方法，即准牛顿法和平滑牛顿法，该方法能有效地解决许多计算机视觉问题，包括聚类、图像分割、共同分割和注册等。

    Nov, 2014

  • 带置换矩阵约束的绝热量子图匹配

    本研究探讨了使用量子计算技术解决三维形状图像匹配问题，提出了将二次受限二进制优化问题映射到量子硬件的几种重构方法，重点考虑获得足够的频谱间隙，以提高在单次运行中测量最优解和有效置换矩阵的概率。在量子计算机 D-Wave 2000Q 上进行实验，结果表明本文提出的置换矩阵约束的重新表述，增加了数值计算的稳健性。该算法有望在未来的量子计算架构上扩展到更高维度，为 3D 计算机视觉和图形问题的解决开辟多个新方向。

    Jul, 2021

  • 利用深度强化学习解决二次分配问题

    通过深度强化学习的方法解决 Quadratic Assignment Problem（QAP）的 Koopmans-Beckman 公式，使用双指针网络（double pointer network）在选择下一个设施放置位置和上一个位置放置设施之间交替，并通过 A2C 算法在一系列合成实例上进行模型训练。在样本外测试中，我们的解决方案与高质量的局部搜索基线相比，平均准确率达到了 97.5%，在 1.2% 的实例中表现优于基线。

    Oct, 2023

  • 通过凸松弛求解图匹配问题

    本文介绍了一种应对图匹配问题的新型凸松弛算法，通过闭合迭代的镜像下降方案，实现了在相关高斯维格纳模型下对应的唯一解高概率收敛，进一步确立了输入矩阵的新充要条件，并将其应用于噪声下的地面实况恢复中。

    Oct, 2023

  • DS++：一种灵活、可扩展且可证明紧密松弛的匹配问题

    该论文提出一种凸二次规划松弛方法，旨在解决与排列相关的优化问题，这种方法比谱松弛和双重随机松弛更加强健且具有相同的可扩展性。

    May, 2017

  • 学习解决方案感知的变压器以高效解决二次分配问题

    利用机器学习的能力，针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案，该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。

    Jun, 2024

  • 正半定规划的更快速、更简单的宽度独立并行算法

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

    Jan, 2012