Jun, 2017

混合方法：带对角线约束半定规划的低秩坐标下降算法

PDF
TL;DR本文提出了一种低秩坐标下降方法，用于结构半定规划，该方法是极其简单易于实现的，没有自由参数，并且通常比现有技术的优化性能提高一个数量级或更好的性能。我们证明该算法是严格下降的，收敛到一个临界点，并且对于足够秩的情况，所有非最优临界点都是不稳定的。此外，我们证明了通过选择合适的步长，该算法几乎可以在局部线性速率下以随机初始化收敛到半定规划的全局最优解，这是第一个证明在不做任何假设的情况下，在球形流形上达到全局最优的低秩半定规划方法。我们将算法应用于两个相关领域：解决最大割半定松弛和解决最大可满足性松弛（我们还简要考虑了其他应用，如学习单词嵌入）。在所有设置中，我们都在各个方面展示了比现有技术的实质性改进，从而扩大了可以使用半定规划方法解决的问题范围和规模。
发现论文，激发创造
  • 一个用于半正定矩阵块对角约束优化的 Riemannian 低秩方法

    提出了一种新的算法来解决优化问题，该算法针对平滑函数和受限 X 的正半定和对角块小标识矩阵的约束。该算法利用该问题的低秩解和黎曼流形上的光滑优化问题的秩约束版本的事实，并比较该算法与成熟软件的优势。

    Jun, 2015

  • 低秩外梯度方法用于可扩展半定规划优化

    我们研究了涉及具有凸目标函数（平滑或非平滑）和额外的线性或非线性平滑凸约束的几类非常重要的半定优化问题，这些问题在统计学、机器学习、组合优化和其他领域中非常普遍。我们关注高维和合理设置的情况，在这种情况下，问题具有满足低秩互补条件的低秩解。我们提供了几个理论结果，证明在这些情况下，众所周知的 Extragradient 方法，在在接近最优原始 - 对偶解的位置初始化时，使用低秩奇异值分解（SVD）将收敛到约束优化问题的解，并具有标准收敛速度保证，而不需要在最坏情况下需要计算成本高昂的全秩 SVD。我们的方法得到了使用 Max-Cut 实例数据集进行的数值实验的支持。

    Feb, 2024

  • 半定凸问题的低秩优化

    提出了一种基于对称半正定矩阵变量 X 进行定义的非线性凸程序的求解算法，该算法基于因数分解 X=YY^T，其中 Y 的列数确定 X 的秩。该因式分解唤起了将原问题重新表述为特定商流形上的优化的几何，并得出了二阶优化方法。此外，文章提供了一些关于分解秩的条件以确保与原始问题的等价性。该算法的效率在图的最大切割和稀疏主成分分析问题上得到了说明。

    Jul, 2008

  • 一种收敛的梯度下降算法，用于基于随机线性测量的秩降和半定规划

    本研究提出了一种基于梯度下降的简单、可扩展、快速的算法来优化处理秩最小化问题及其相关的半定规划问题。通过对一个秩为 r 和条件数为 κ 的正半定 n x n 矩阵进行 O (r³κ²n log n) 次随机测量，我们证明了该方法可线性收敛于全局最优解。

    Jun, 2015

  • 关于半定规划中同步和社区检测问题的低秩方法

    为了解决困难的优化问题，使用基于半定规划的凸松弛在很多领域已经很普遍。本文关注同步和社区检测问题，提供理论保证，阐明低秩矩阵启发式方法的显着效率。

    Feb, 2016

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

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

    Mar, 2018

  • 凸半定规划的混合算法

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

    Jun, 2012

  • 利用半正定规划对稀疏 PCA 进行直接求解

    研究在 Frobenius-norm 意义下，将正半定对称矩阵近似为一个秩为一的矩阵，其特征向量的基数有一个上限的问题以及其在协方差矩阵分解到稀疏因子等领域中的应用，提出了一个基于半定规划的方法，并讲解了 Nesterov's 平滑最小化技术在直接稀疏 PCA 方法中的应用。

    Jun, 2004

  • 用低秩半定规划解决 MAX2SAT 问题

    本文提出了一种将搜索方法与半定规划方法相结合的算法，其用于解决 MAX2SAT 问题。文中称，使用这种方法能够显著提高问题的解决速度，并在一些问题上取得了 order of magnitude 级别的速度提升。

    Dec, 2018

  • 使用半定规划进行多点云的全局配准

    本文提出将最小二乘问题转化为凸性的半定规划问题，通过刚体变换及刚体理论来稳定恢复解，同时实验证明该方法在噪声较大时表现显著优于谱松弛法和流形优化方法。

    Jun, 2013