Jun, 2017

DSOS 和 SDSOS 优化：比完全平方和和半定性优化更易处理的替代方法

PDF
TL;DR本文介绍了 DSOS 和 SDSOS 最优化算法作为线性规划和二阶锥规划的替代方法，以允许一个在计算时间与解决方案质量之间进行权衡的选择，并且用多个应用领域的数值实验表明，我们可以在目前传统的平方和算法难以实现的规模上处理问题。
发现论文，激发创造
  • 平方和证明及其应用于最优算法问题的探索

    该研究讨论了最近发现的唯一游戏猜想与和平方方法之间的联系，并探讨了和平方方法在解决许多计算问题时提供新保证的潜力，同时还可能驳回 UGC。

    Apr, 2014

  • TSSOS：一种利用项稀疏性的 Moment-SOS 层次

    本文介绍了一个新的半定编程松弛分层方法，可利用输入多项式的项（或单项式）稀疏性，包括使用在一个迭代过程中生成的与原始数据中的术语相关的邻接图的连通分量的完成得到的块对角矩阵。该框架应用于计算多项式优化问题的下界。

    Dec, 2019

  • Sparse-BSOS：具有稀疏性的大规模多项式优化有界次 SOS 层次结构

    本文提出了一种稀疏版本的有界次数 SOS 层次结构 BSOS，适用于多项式优化问题，特别针对结构稀疏模式问题。当稀疏模式满足运行交替性质时，这种具有固定大小的半定规划的稀疏 - BSOS 层次结构会收敛于原问题的全局最优解。此外，对于 SOS - 凸问题类，在层次结构的第一步就会出现有限收敛，就像在密集版本中一样。

    Jul, 2016

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

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

    Oct, 2019

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

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

    Sep, 2017

  • 三维环境与平方和多项式几何

    运用代数学方法，本文研究了利用函数多项式下水平集进行三维空间推理的问题，包括两个基本半代数凸集之间互相包含的相关计算、相交的两个半代数凸集之间的分离、多个半代数集合与一个凸集的紧凑包含等，并且我们将这些任务的求解转化为小型半定规划并进行了实验验证。

    Nov, 2016

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

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

    May, 2017

  • 舍入平方和松弛问题

    通过转换一个分布映射算法为一个近似解，我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法，并应用于 3 个已知问题的改进，分别是：低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。

    Dec, 2013

  • 最小化多项式函数

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

    Mar, 2001

  • 凸半定规划的混合算法

    提出了一种用于最优化正半定矩阵锥上凸光滑函数的混合算法，可以用于解决各种机器学习问题，并且在三个机器学习问题上的实验结果表明，该方法优于现有算法。

    Jun, 2012