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

Mar, 2018

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

Jun, 2016

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

Jun, 2015

通过将低秩矩阵补全问题重新表述为在投影矩阵的非凸集上的凸问题，并实施一个可证明最优的分离分支限界方案，推导出一类新的收敛松弛方法。数值实验表明，相比现有的收敛松弛方法，我们的新型收敛松弛方法将最优性差距降低了两个数量级。此外，我们展示了我们的分离分支限界方案的性能，并展示了它在解决矩阵完成问题方面的优异表现。

May, 2023

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

Jun, 2017

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

Jul, 2008

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

Feb, 2024

本研究提出一种基于 Grothendieck inequality 的方法，旨在证明随机图上半定规划问题的一致性，可适用于众多的网络随机模型和半定规划问题，并具有普适性。同时通过应用该方法于稀疏网络中的社交圈问题，可利用各种简单和自然的半定规划方案恢复社交圈结构。

Nov, 2014

提出了一种基于低阶多项式、半定规划和张量分解的高效贝叶斯估计问题的元算法，该算法的重点在于尽量紧密（达到添加低阶项的下限），并且通常可以达到统计阈值或猜测的计算阈值。在样本复杂度方面改善了社交网络检测和混合式社交网络模型的恢复保证，并且表明该任务可能需要指数时间。算法的基本策略是计算参数的后验分布的最佳低阶逼近，然后使用一个健壮的张量分解算法从这些近似的后验时刻中恢复参数。

Sep, 2017

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

Mar, 2017