半定规划的更快内点方法
提出一种量子内点法,可用于 SDPs 和 LPs,可以提供多项式速度优于最佳已知的经典 SDP 解算器和内点基 LP 解算器,为量子优化和机器学习应用的开发铺平道路。
Aug, 2018
本文研究了正半定规划的近似算法,提出了一种简单的 NC 并行算法,其迭代次数为 O (1/ϵ³ log³ n),总工作量近似为因子分解中非零条目数的线性级别。
Jan, 2012
本文针对包装和覆盖半正定程序(或正半定规划)的近似求解,研究了多对数深度算法的设计,并提出了一种基于优化框架的简单算法,其正确性基于 Lieb-Thirring 不等式的新矩阵不等式和梯度截断技术的随机变体。
Jul, 2015
本文设计了一个多项式时间逼近算法以解决正半定 Grothendieck 问题,得到了逼近比例,并证明了该逼近比例是最优的。作者也提出了一种改进的算法,并应用它来解决 Laplacian 矩阵的情况。
Oct, 2009
通过引入非凸约束形式并应用 Riemannian trust-region 方法,该论文研究了 MaxCut 和同步问题中的秩约束半定规划,并建立了一个 Grothendieck 型不等式证明局部最大值和危险鞍点都在离全局最大值一个小倍数距离的情况下,SDPs 可以在已知精度内得到解决。
Mar, 2017
本文采用 Burer-Monteiro 分解方法解决 SDP 问题,考虑约束条件次数随所需最优解的秩呈次二比例增长时,所有的近似局部最优解均为全局最优解,并将这个结果应用于 Max-Cut 和矩阵填充问题。
Mar, 2018
本文研究了一类包括最大割、随机块模型社区检测、鲁棒 PCA、相位恢复和旋转同步等应用的半定规划 SDP,表明以 Burer-Monteiro 公式为代表的低秩 SDP 几乎从不具有虚假的局部最优解。
Jun, 2016
通过使用标准约减和新技术的混合方法,我们改进了查找凸集中点的运行时间,同时提高了在连续和组合优化中的算法性能,特别是子模规划和半定规划问题。
Aug, 2015
通过使用对数障碍项而不是二次惩罚项和神经网络的优化问题解决方案,实现了优化问题的解决方案,结果表明其效果与基于二次规划任务损失的公式以及 SPO 方法一样好,甚至更好。
Oct, 2020