本文研究带随机约束的在线凸优化问题,提出了一种算法,能够达到预期和高概率的收益掉队和约束违反值等性能保证,并在真实数据中心调度问题上进行了实验验证。
Aug, 2017
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
本文研究在线问题中的线性规划问题,提出了解决混合 packing 和 covering 约束线性规划在线问题的算法,并应用于两个与机器调度和设施定位相关的问题,得到了多项式对数竞争积分解决方案。
Mar, 2012
本研究介绍了一种基于条件梯度算法的优化模型,可用于求解线性优化问题和非线性凸优化问题,并给出了一种基于此算法的在线凸优化算法,具有线性收敛速度和最优的遗憾保证。
Jan, 2013
本文研究了在线鞍点问题和应用,提出了一些算法,包括使用基本对偶方法解决在线鞍点问题以及应用于动态定价、竞拍和众包等问题。
Jun, 2018
通过使用机器学习预测以改善算法的性能,该研究论文介绍了一种针对在线装箱问题的简单的学习增强算法,并展示了该框架在线性规划、背包问题、资源管理效益、吞吐量最大化和网络效用最大化等多个领域的直接应用,同时提出了理解简单黑盒解决方案何时可优化的必要与充分条件的问题。
Jun, 2024
我们提出了一种随机梯度框架,用于解决具有(可能)无限数量的线性包含约束条件的随机复合凸优化问题,而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件,无需矩阵投影,并且通过数值实验表明,我们的算法实现了最先进的实用性能。
Jan, 2019
本文研究具有随机约束的在线凸优化问题,提出了一种新的原始 - 对偶镜像下降算法,其可以在不需要 Slater 条件的情况下达到与先前的方法相似的性能并允许等式约束。
Aug, 2019
研究了在线环境下的通用拟阵约束下的单调子模最大化问题,证明了一大类子模函数在在线凸优化问题中的优化等价性,通过合适的舍入方案,实现了在组合优化中达到次线性后悔的 OCO 算法。同时,该规约也适用于多种不同版本的在线学习问题,包括动态后悔、游走和乐观学习等。
Sep, 2023