Aug, 2015

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

PDF
TL;DR通过使用标准约减和新技术的混合方法，我们改进了查找凸集中点的运行时间，同时提高了在连续和组合优化中的算法性能，特别是子模规划和半定规划问题。
convex setoracle complexityoptimizationsubmodularsemidefinite programming
发现论文，激发创造
  • 凸优化、凸凹博弈的改进切割平面方法及其应用

    提出了一种新的剪切平面算法，采用多层数据结构来维护杠杆得分，通过随机投影，批量低秩更新，逆维护，多项式插值和快速矩阵乘法的复杂组合来实现，优化了以前算法的依赖性，并在经济学中的许多重要应用中实现了更好的性能。

    Apr, 2020

  • 基于递归割平面法的内存受限凸优化算法

    我们提出了一系列递归割平面算法，用于解决具有受限内存的可行性问题，这些算法可以用于一阶凸优化。

    Jun, 2023

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

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

    Dec, 2015

  • 基于拟阵约束的 k 次次模最大化的快速算法

    应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数，提出逼近算法来最大化满足单调和非单调 k - 次模函数，并提供了关于时间复杂度的结果，同时还介绍了针对总大小约束的快速算法。

    Jul, 2023

  • 半定规划的更快内点方法

    本文介绍一种更快的内点法，用于求解具有变量大小的一般半定规划问题，并解释了算法的运行时间和矩阵乘法的指数和相对精度之间的关系。

    Sep, 2020

  • 子模最大化问题的紧凑组合算法在矩阵约束条件下的应用

    提出了一种基于组合数学的算法，用于求解在一个制约性匹配中的单调子模优化问题，算法具有很高的精度和时间效率。

    Apr, 2012

  • 非凸强凹 Min-Max 优化的复杂度下界

    我们通过使用第一阶 oracle 及条件数，提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界，这既适用于确定性 oracle 也适用于随机 oracle，并提供了各自的下界，并与其他文献的上界进行了比较。

    Apr, 2021

  • 全新的角色扮演加速方法：矩阵游戏和平滑函数的最大化最小化

    算法设计为在欧几里得或单纯形域内最小化 max (f_i (x))，若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数，我们的方法可以在评价复杂度中找到 ε- 近似解，并具有优化性能。

    Nov, 2023

  • 有限和平凡导数光滑优化的复杂性研究

    本文研究了一种优化问题，在多项式朗托泽维奇条件下，通过梯度方法在分布式环境中找到次优解，提出了一个去中心化一阶方法，并给出了相应的下界。

    Feb, 2024

  • 基于核的赌博式凸优化方法

    提出一种新的算法解决在无导数情况下的 $adversarial convex bandit$ 问题，其包含了核方法、伯努利卷积的一般化和新的退火时间表。这个算法在要求多次迭代的场景中可以取得佳效果。

    Jul, 2016