凸优化、凸凹博弈的改进切割平面方法及其应用
通过使用标准约减和新技术的混合方法,我们改进了查找凸集中点的运行时间,同时提高了在连续和组合优化中的算法性能,特别是子模规划和半定规划问题。
Aug, 2015
研究了一种用于半定规划问题(SDOs)的切平面方法,证明了该方法基于有界性假设的收敛性。通过将该方法的收敛速度与初始外近似的直径联系起来,我们证明了当使用二阶锥逼近而不是线性逼近时该方法的表现更好。我们将该方法用于提供数千个协变量的稀疏 PCA 问题的边界间隙,并解决了 500x500 矩阵上的核范数问题。
Oct, 2019
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
本文将界定传播程序推广到允许添加任意切割平面约束,包括涉及松弛整数变量的约束,并将其命名为广义界定传播程序 (GCP-CROWN),提高了神经网络验证的效率和 GPU 加速,实现了全面解决 Oval 20 基准和优于当今众多基准的状态表现验证工具在 Oval 21 基准上的效果。
Aug, 2022
算法设计为在欧几里得或单纯形域内最小化 max (f_i (x)),若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数,我们的方法可以在评价复杂度中找到 ε- 近似解,并具有优化性能。
Nov, 2023
该论文介绍了一种多项式时间算法,用于优化无限制的星凸函数,提出了一个随机化算法找到可行域的割面,并强调了该算法的理论吸引力,即在多项式时间算法的范围内引入很多有趣的病态类。
Nov, 2015
聚类是数据科学和机器学习中最基本的工具之一,k-means 聚类是最常见的方法之一。本文研究了低维数据实例的 k-means 问题,并将其表示为结构化的凸分配问题,利用低维结构解决大数据集的问题。该方法结合了全局优化理论的方法来加速处理程序,并提供了性能的数值结果。
Feb, 2024