非凸 Burer-Monteiro 方法在光滑半定规划中的应用
本文采用 Burer-Monteiro 分解方法解决 SDP 问题,考虑约束条件次数随所需最优解的秩呈次二比例增长时,所有的近似局部最优解均为全局最优解,并将这个结果应用于 Max-Cut 和矩阵填充问题。
Mar, 2018
通过引入非凸约束形式并应用 Riemannian trust-region 方法,该论文研究了 MaxCut 和同步问题中的秩约束半定规划,并建立了一个 Grothendieck 型不等式证明局部最大值和危险鞍点都在离全局最大值一个小倍数距离的情况下,SDPs 可以在已知精度内得到解决。
Mar, 2017
为了解决困难的优化问题,使用基于半定规划的凸松弛在很多领域已经很普遍。本文关注同步和社区检测问题,提供理论保证,阐明低秩矩阵启发式方法的显着效率。
Feb, 2016
本文提出了一种称为双协调松弛的方法,将半定规划问题转化为特定的双协调优化问题,并通过高效的交替最小化法求解。该方法在计算机视觉中的应用包括分割、共分割和流形度量学习,相对于现有方法,性能高达 35 倍,同时处理范围更广的半定规划问题。
May, 2016
本文研究在具有强凸目标的低秩矩阵问题上使用投影梯度下降法。我们利用 Burer-Monteiro 分解方法隐式实现低秩性;这种分解方法引入了目标函数的非凸性。我们着重研究包括半正定(PSD)约束和特定矩阵范数约束在内的约束集。这些标准出现在量子态重构和相位恢复应用程序中。我们表明,非凸投影梯度下降在分解空间中偏爱局部线性收敛。我们通过一个新颖的下降引理建立我们的理论,该引理在不受限制的问题上最近的结果得到了非平凡的扩展。 这种算法称为投影因式梯度下降,简称 ProjFGD,并在量子状态重构和稀疏相位恢复应用程序方面表现出优异性能。
Jun, 2016
本研究提出了一种可应用于任何非最小化求解器的鲁棒全局估计通用方法,该方法利用了鲁棒估计与异常值处理之间的 Black-Rangarajan 对偶并结合逐步非凸性与 SDP 解法求解,解决了常规稳健代价函数导致的非凸性问题;本方法应用于点云和网格登记,位姿图优化和基于图像的形状算法中,具有 70-80%异常值鲁棒性,并且比专门的局部求解器更准确和更快。
Sep, 2019
本文提出了一种针对大规模二次二次规划问题的新型 SDP(半定规划)公式,并基于此提出了两种求解方法,即准牛顿法和平滑牛顿法,该方法能有效地解决许多计算机视觉问题,包括聚类、图像分割、共同分割和注册等。
Nov, 2014
基于 Langevin 扩散,提出一种新算法,在球面乘积流形上进行非凸优化和采样,并与 Burer-Monteiro 方法一起,应用于求解具有对角限制的半定规划问题。该算法在有限次迭代中生成 Gibbs 分布,并在 Kullback–Leibler 散度中保证渐进精度,其迭代次数呈多项式级别增长。与结果相结合,我们提供了全局最优性性保证,即使是存在鞍点和局部最小值的问题,算法仍能近似于全局最优解。
Oct, 2020
我们研究了涉及具有凸目标函数(平滑或非平滑)和额外的线性或非线性平滑凸约束的几类非常重要的半定优化问题,这些问题在统计学、机器学习、组合优化和其他领域中非常普遍。我们关注高维和合理设置的情况,在这种情况下,问题具有满足低秩互补条件的低秩解。我们提供了几个理论结果,证明在这些情况下,众所周知的 Extragradient 方法,在在接近最优原始 - 对偶解的位置初始化时,使用低秩奇异值分解(SVD)将收敛到约束优化问题的解,并具有标准收敛速度保证,而不需要在最坏情况下需要计算成本高昂的全秩 SVD。我们的方法得到了使用 Max-Cut 实例数据集进行的数值实验的支持。
Feb, 2024