Mar, 2024

受容积管理启发的带有记忆和切换成本的在线非凸优化问题

PDF
TL;DR在线非凸优化问题通过调节活动服务器的数量来最小化任务集的流动时间（总延迟），但改变活动服务器数量需要支付切换成本。研究中考虑了每个任务每次只能由一个固定速度的服务器处理，并且比起通常的在线凸优化（OCO）问题，所考虑的目标函数是非凸的，而且关键是它在每个时间点都依赖于所有过去的决策而不仅仅是当前的决策。针对最坏情况和随机输入，提出了竞争性算法。
发现论文，激发创造
  • 具有长期约束的随机网络资源分配的在线优化

    本文研究了一个在线资源预订问题，通过一个由两个计算节点组成的通信网络，在有限时间内最小化整体预订成本，并且保持累计违规与运输成本在一定预算限制下的在线重复博弈，提出了一个在线鞍点算法来解决该问题。

    May, 2023

  • 一种动态网络资源分配的在线凸优化方法

    该论文探讨了在线凸优化涉及敌对损失函数和敌对约束的情况，开发了一种修改的在线鞍点（MOSP）方案，并在动态网络资源分配任务中进行了应用，证明了其相对于梯度方法的性能优势。

    Jan, 2017

  • 追逐长期约束的凸函数

    我们研究了一类带有长期约束的在线度量问题，该问题涉及在线玩家在度量空间中进行决策以同时最小化击中成本和度量确定的切换成本。我们设计了特定实例的最优竞争性和学习增强算法，并进一步在数值实验中证明了我们提出的算法的良好性能。

    Feb, 2024

  • 在线转换与切换成本：鲁棒和学习增强算法

    介绍并研究了涉及能源和可持续发展领域的新兴问题的在线转换与切换成本，通过引入在线玩家尝试在固定时间范围内购买（或销售）资产的问题，我们提出了基于阈值的竞争（鲁棒）算法来优化解决该问题，同时还提出了利用不可信黑盒建议（例如机器学习模型的预测）的学习增强算法，以在平均情况下显著提高性能并保证最坏情况下的竞争性能，并通过碳感知的电动汽车充电案例研究对所提出的算法进行了实证评估，结果显示相对基准方法，我们的算法显著改进了该问题的解决方法。

    Oct, 2023

  • 使用预测和非凸损失的在线优化

    本文提出了两个有效的充分条件来解决在线非凸优化和运动成本问题，并得出了算法 SFHC 的竞争比率，并且还为运动和击打成本提供了竞争比率结果。

    Nov, 2019

  • 在线库存问题：在线凸优化中超越 i.i.d. 设置

    研究了多产品库存控制问题，提出了 MaxCOSD 在线算法，可实现对非 i.i.d 需求和有状态动态的问题进行有效控制。

    Jul, 2023

  • 具有切换成本和延迟梯度的在线凸优化

    在线凸优化问题中，我们考虑带有二次和线性切换成本的有限信息环境下的问题，通过使用关于先前目标函数的梯度信息，我们提出了在线多梯度下降算法 (Online Multiple Gradient Descent, OMGD)，并证明了其在二次切换成本的 OCO 问题的竞争比为至多 4 (L + 5) + (16 (L + 5))/μ。对于有界信息环境中的在线算法，其竞争比的上界和下界分别为 max {Ω(L), Ω(L/√μ)}。此外，还证明了 OMGD 算法实现了有限信息环境下的动态最优（按顺序）遗憾，并且对于线性切换成本，OMGD 算法的竞争比的上界取决于问题实例的路径长度、平方路径长度以及 L、μ，并且被证明是任何在线算法能够达到的最佳竞争比。因此，我们得出结论，在有限信息环境中，二次和线性切换成本的最优竞争比基本上是不同的。

    Oct, 2023

  • 在线凸优化：同时为所有分段确定最佳切换遗憾

    在线凸优化中，我们介绍了一种出人意料地高效且同时在所有可能分割上实现渐进最优切换遗憾的算法，该算法在时间复杂度和空间复杂度上都取得了对数级的效果，同时对比序列变化的速率也获得了新的界限。

    May, 2024

  • 在线随机凸规划的快速算法

    本文介绍了在线随机凸规划问题，提出了针对此问题的快速算法，并在这些算法中使用了原始对偶算法，实现了最优竞争比率和接近最优的后悔保证。

    Oct, 2014

  • 网络资源分配的在线优化及与强化学习技术的比较

    我们在本文中解决了一种带有任务转移的在线网络资源分配问题，提出了基于指数加权方法的随机在线算法，证明了该算法具有次线性时间后悔，通过对人工数据进行性能测试并与强化学习方法进行比较表明我们的方法优于后者。

    Nov, 2023