Jun, 2011

通过平坦截断证明拉瑟尔层次的收敛性

PDF
TL;DR本文研究如何对 Lasserre 层次结构的半定松弛进行收敛证明，提出了一种通用的 flat truncation 证书。研究结果表明，Putinar 类型的 Lasserre 层次结构具有有限的收敛性，当且仅当 flat truncation 成立，并且对于 Schmudgen 类型的 Lasserre 层次结构也同样适用；在渐进条件下，Putinar 类型的 Lasserre 层次结构的 flat truncation 是渐进满足的，Schmudgen 类型的 Lasserre 层次结构也是如此；对于雅各比 SDP 松弛的层次结构，flat truncation 总是成立的。同时还讨论了无约束多项式优化问题。
发现论文，激发创造
  • Lasserre 层次法的最优性条件和有限收敛

    研究 Lasserre 层次与非线性规划理论中最优性条件的关系，并证明在一定条件下 Lasserre 层次有有限收敛性，这些最优性条件在局部极小值点成立且在输入数据中一组有限的多项式不为零时，Lasserre 层次具有一般的有限收敛性。

    Jun, 2012

  • 舍入平方和松弛问题

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

    Dec, 2013

  • 拉瑟尔测度法与模拟退火法在多项式优化中的比较

    比较拉瑟尔测度基于多项式优化的上界和模拟退火得到的上界，发现当优化函数为多项式且约束集为凸集时，拉瑟尔层次结构的收敛速度要快于先前在文献中所知晓的。

    Mar, 2017

  • 多项式优化中局部最小值的层次结构

    本研究探讨多项式中局部最小值的等级。为此，我们首先计算 H - 最小值，并构建半定松弛序列来满足一、二阶最优性条件，证明每个构建序列都在一些通用条件下有有限收敛。我们提供了计算所有局部最小值的程序，并在存在等式约束时得到了类似的结果，研究了若干扩展情况。

    Nov, 2013

  • 非对易变量的多项式优化问题的收敛松弛

    本文介绍了一种解决量子理论和量子信息科学中涉及的多项式不等式约束的最优化问题的方法，使用一系列半定规划松弛方法生成一个单调递增的下界序列，并介绍了从相应的半定规划问题的解中提取全局优化器的方法。

    Mar, 2009

  • 非凸 Burer-Monteiro 方法在光滑半定规划中的应用

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

    Jun, 2016

  • 最小化多项式函数

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

    Mar, 2001

  • 通过 Grothendieck 不等式解同步和 MaxCut 问题的 SDP

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

    Mar, 2017

  • 一般值约束满足问题的 SDP 松弛上界

    通过证明各种规约保持 Lasserre SDP 层次的精确可解性，我们展示了支持破坏有限宽度条件的一般值约束语言不能被静态程序快速求解。

    Dec, 2016

  • 一类范约束矩阵问题的可证明 Burer-Monteiro 分解

    本文研究在具有强凸目标的低秩矩阵问题上使用投影梯度下降法。我们利用 Burer-Monteiro 分解方法隐式实现低秩性；这种分解方法引入了目标函数的非凸性。我们着重研究包括半正定（PSD）约束和特定矩阵范数约束在内的约束集。这些标准出现在量子态重构和相位恢复应用程序中。我们表明，非凸投影梯度下降在分解空间中偏爱局部线性收敛。我们通过一个新颖的下降引理建立我们的理论，该引理在不受限制的问题上最近的结果得到了非平凡的扩展。 这种算法称为投影因式梯度下降，简称 ProjFGD，并在量子状态重构和稀疏相位恢复应用程序方面表现出优异性能。

    Jun, 2016