NIPSJul, 2014

向量排列问题的排序网络松弛

PDF
TL;DR本文介绍了 Goemans (2010) 的构造方法，使用其构造的 permutahedron 凸包作为优化问题的松弛形式可以将变量和约束的数量从 Θ(n^2) 减少到 Θ(nlogn)。我们将其应用于 2-SUM 问题的凸优化形式中，并引入了一种更简单的正则化方案。经实验证明，使用该方案可以获得与 Fogel 等人 (2013) 相似的结果，并且计算时间更短。
发现论文，激发创造
  • 置换多面体上的贪心在线优化

    本文研究了一个基于凸多面体的赌博游戏，并提出了一种算法，它结合了 2013 年 Ailon 的最新算法和 2009 年 Cesa-Bianchi et al 的算法，以实现在线优化，总时间复杂度为 O（n^3T），其中 n 是顶点数和 T 是时间区间，这算法能够使遗憾达到 O (n^（3/2）* 根号 T)。

    Dec, 2013

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

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

    Mar, 2009

  • 最小化多项式函数

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

    Mar, 2001

  • 使用 Birkhoff 多面体的黎曼结构进行概率置换同步

    本研究提出了一种使用 Birkhoff Polytope 的 Riemannian geometry 和 Markov Random Field 模型进行多图匹配的同步算法，可在较短时间内获得较高的匹配准确性和可靠的置信度 / 不确定度估计。

    Apr, 2019

  • 低秩优化的新视角

    本文介绍了一种基于矩阵透视函数的低秩问题的新方法，该方法通过特征向量的正交投影来获得矩阵上简单低秩集的凸包，从而获得了一种可靠的矩阵透视重构技术，并将其应用于多种低秩问题中，最终实现了半正定约束的优化。

    May, 2021

  • 一种更快的切平面方法及其对组合优化和凸优化的影响

    通过使用标准约减和新技术的混合方法，我们改进了查找凸集中点的运行时间，同时提高了在连续和组合优化中的算法性能，特别是子模规划和半定规划问题。

    Aug, 2015

  • 置换空间上的贝叶斯优化

    本研究针对基于贝叶斯优化的排列空间问题，提出了两种算法：BOPS-T 和 BOPS-H。两种算法均采用了高斯过程模型，BOPS-T 采用 Kendall 核函数和可处理的采集函数优化方法，BOPS-H 采用 Mallow 核函数和启发式搜索方法来优化期望改进采集函数。理论分析和实验表明，这两种算法在人工和实际基准测试中均优于同类问题的最先进的 BO 算法。

    Dec, 2021

  • 论最大体积单纯形和子行列式

    本论文提出了一种多项式时间复杂度下可以近似求解凸包中体积最大值的算法，近似比可以达到 $O (log d)^{d/2}$。此外，本文也展示了此问题的不可近似性，除非 $P=NP$。类似的结果也适用于矩阵行列式的最大值问题。

    Jun, 2014

  • 近似凯拉特多利容度问题的严格界限及其扩展

    本文提出了一种快速算法来处理凸多面体中点的问题，并在此基础上对子模函数最小化和 SVM 训练提供了新算法。

    Dec, 2015

  • 组合优化中多面体的指数下界

    我们通过量子通信协议和半定规划重述线性规划，证明了不存在一个与旅行商多面体投影相等的多项式大小的线性规划。此结论同样适用于割多面体和稳定集多面体。

    Nov, 2011