Research on Online Convex Optimization Algorithms With Long-term Constraints Based on Lyapunov Optimization
-
摘要: 围绕带长期约束的在线凸优化问题展开研究. 该问题框架容许瞬时约束违规, 约束仅需在长期累积意义上得到满足. 针对约束违反的刻画, 采用累积约束违反作为评价指标, 该指标可以避免严格满足约束的决策对其它约束违反进行抵消的情况发生, 进而更精准地刻画算法的约束控制效果. 设计了一种基于虚拟队列的李雅普诺夫优化在线算法, 其可实现${\rm{O}}(T^{\max\{c,\; 1-c\}})$的遗憾上界, 以及${\rm{O}}(T^{(1-c)/2})$的累积约束违反上界. 其中, $c \in (0,\; 1)$为用户自由定义的权衡参数. 该算法消除了对约束违反函数$g$上界的依赖, 相较于现有算法拥有更广泛的适用场景. 此外, 当损失函数序列满足强凸性条件时, 该算法可达到${\rm{O}}(\log(T))$的遗憾上界与${\rm{O}}((\log(T))^{1/2})$的累积约束违反上界. 最后, 通过数值仿真实验验证了理论结果的有效性以及算法性能的优越性.Abstract: This paper focuses on online convex optimization with long-term constraints. In this problem setting, constraints can be violated at individual time steps, but are satisfied over the entire time horizon. To characterize constraint violations, we adopt cumulative constraint violation as the performance metric. This metric avoids the situation where strictly feasible decisions offset constraint violations, and thus more accurately reflects the performance of an algorithm. Based on the Lyapunov optimization framework, this paper develops an online optimization algorithm incorporating virtual queues. The algorithm achieves an ${\rm{O}}(T^{\max\{c,\;1-c\}})$ bound for regret and an ${\rm{O}}(T^{(1-c)/2})$ bound for cumulative constraint violation, where $c \in (0,\;1)$ is a user-defined trade-off parameter. This algorithm eliminates the reliance on the upper bound of the constraint violation function, and thus exhibits stronger generality than existing algorithms. Moreover, when the loss function sequence is strongly convex, the algorithm attains an ${\rm{O}}(\log(T))$ bound for regret and an ${\rm{O}}((\log(T))^{1/2})$ bound for cumulative constraint violation. Finally, numerical simulations are presented to demonstrate the validity of the theoretical results and the superior performance of the proposed algorithm.
-
图 1 总轮次已知的在线规划中累积损失的演变
Fig. 1 Evolutions of the cumulative loss in online linear programming with known total rounds
图 2 总轮次已知的在线规划中累积约束违反的演变
Fig. 2 Evolutions of the cumulative constraint violation in online linear programming with known total rounds
图 3 总轮次未知的在线规划中累积损失的演变
Fig. 3 Evolutions of the cumulative loss in online linear programming with unknown total rounds
图 4 总轮次未知的在线规划中累积约束违反的演变
Fig. 4 Evolutions of the cumulative constraint violation in online linear programming with unknown total rounds
图 5 在线二次规划设计下累积损失的演变
Fig. 5 Evolutions of the cumulative loss in online quadratic programming
图 6 在线二次规划设置下累积约束违反的演变
Fig. 6 Evolutions of the cumulative constraint violation in online quadratic programming
表 1 总轮数已知的在线线性规划设置下各个算法的参数
Table 1 Parameters for each algorithm in online linear programming with known total rounds
算法 输入 算法1 $ \alpha_t=\sqrt{T}/2 $, $ \gamma_t=\sqrt{T} $ Yi等(2021) $ \alpha_t=2/\sqrt{T} $, $ \gamma_t=T^{1/4} $ Yuan和Lamperski (2018) $ \sigma=3/10 $, $ \eta=4/(5 \sqrt{T}) $ 
下载: 导出CSV
表 2 总轮数未知的在线线性规划设置下各个算法的参数
Table 2 Parameters for each algorithm in online linear programming with unknown total round
算法 输入 算法1 $ \alpha_t=5/8\sqrt{t} $, $ \gamma_t=5/4\sqrt{t} $ Yi等(2021) $ \alpha_t=2/\sqrt{t} $, $ \gamma_t=t^{1/4} $
下载: 导出CSV
表 3 在线二次规划设置下各个算法的参数
Table 3 Parameters for each algorithm in online quadratic programming
算法 输入 算法1 $ \alpha_t = t / 6 $, $ \gamma_t= 2 t $ Yi等(2021) $ \alpha_t= 6 / t $, $ \gamma_t = \sqrt{t} $ Yuan和Lamperski (2018) $ \theta_t = 4.5 / (t+1) $, $ \eta_t = 3 / (t+1) $
下载: 导出CSV
-
[1] Zinkevich M. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the International Conference on Machine Learning. Washington, DC, USA: AAAI Press, 2003. 928−935 [2] Shalev-Shwartz S, Crammer K, Dekel O, Singer Y. Online passive-aggressive algorithms. In: Proceedings of the International Conference on Neural Information Processing Systems. Cambridge, MA, USA: MIT Press, 2003. 1229−1236 [3] Mairal J, Bach F, Ponce J, Sapiro G. Online dictionary learning for sparse coding. In: Proceedings of the Annual International Conference on Machine Learning. New York, NY, USA: ACM, 2009. 689−696 [4] Hazan E, Agarwal A, Kale S. Logarithmic regret algorithms for online convex optimization. Machine Learning, 2007, 69(2-3): 169−192 doi: 10.1007/s10994-007-5016-8 [5] Goldfarb A, Tucker C. Online display advertising: Targeting and obtrusiveness. Marketing Science, 2011, 30(3): 389−404 doi: 10.1287/mksc.1100.0583 [6] Nonhoff M, Dall'Anese E, Müller M A. Online convex optimization for robust control of constrained dynamical systems. IEEE Transactions on Automatic Control, 2026, 71(6): 3543−3558 doi: 10.1109/TAC.2025.3641731 [7] Cesa-Bianchi N, Long P M, Warmuth M K. Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Transactions on Neural Networks, 1996, 7(3): 604−619 doi: 10.1109/72.501719 [8] Gentile C, Warmuth M K. Linear hinge loss and average margin. In: Proceedings of the International Conference on Neural Information Processing Systems. Cambridge, MA, USA: MIT Press, 1998. 225−231 [9] Gordon G J. Regret bounds for prediction problems[Ph.D. dissertation], Carnegie Mellon University, USA, 1999. [10] Shalev-Shwartz S. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 2012, 4(2): 107−194 doi: 10.1561/2200000018 [11] Jadbabaie A, Rakhlin A, Shahrampour S, Sridharan K. Online optimization: Competing with dynamic comparators. In: Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics. San Diego, CA, USA: PMLR, 2015. 398−406 [12] Hazan E. Introduction to online convex optimization. Foundations and Trends in Optimization, 2016, 2(3-4): 157−325 doi: 10.1561/2400000013 [13] Zhang L J, Lu S Y, Zhou Z H. Adaptive online learning in dynamic environments. In: Proceedings of the Annual Conference on Neural Information Processing Systems. Montreal, Canada: Curran Associates, Inc., 2018. 1330−1340 [14] Zhang L J, Yang T B, Jin R, Zhou Z H. Dynamic regret of strongly adaptive methods. In: Proceedings of the International Conference on Machine Learning. Stockholm, Sweden: PMLR, 2018. 5882−5891 [15] Zhao P, Zhang Y J, Zhang L J, Zhou Z H. Dynamic regret of convex and smooth functions. In: Proceedings of the International Conference on Neural Information Processing Systems. Red Hook, NY, USA: Curran Associates, Inc., 2020. 12510−12520 [16] Lin Y, Shames I, Nešić D. Online convex optimization using coordinate descent algorithms. Automatica, 2024, 165: 111681 doi: 10.1016/j.automatica.2024.111681 [17] Zhang Y, Zhang W, Zhang L, Li H, Mo W. Adaptive online convex optimization: A survey of algorithms, theory, and modern applications. Applied Sciences, 2026, 16(4): Article No. 1739 doi: 10.3390/app16041739 [18] Chen L, Zhou P, Ding X, Xu H, Lui J C S. Differentially private online convex optimization with long-term constraints via gaussian mechanism and virtual queue. IEEE Transactions on Emerging Topics in Computational Intelligence, 2026, 10(1): 952−966 doi: 10.1109/TETCI.2025.3616044 [19] 侯瑞捷, 李修贤, 易新蕾, 洪奕光, 谢立华. 具有反馈延迟分布式在线复合优化的动态遗憾性能. 自动化学报, 2025, 51(4): 835−856 doi: 10.16383/j.aas.c240414Hou Rui-Jie, Li Xiu-Xian, Yi Xin-Lei, Hong Yi-Guang, Xie Li-Hua. Dynamic regret for distributed online composite optimization with delayed feedbacks. Acta Automatica Sinica, 2025, 51(4): 835−856 doi: 10.16383/j.aas.c240414 [20] 张文韬, 张保勇, 袁德明, 徐胜元. 分布式在线鞍点问题的 Bandit 反馈优化算法. 自动化学报, 2025, 51(4): 857−874 doi: 10.16383/j.aas.c240289Zhang Wen-Tao, Zhang Bao-Yong, Yuan De-Ming, Xu Sheng-Yuan. Bandit feedback optimization algorithm for distributed online saddle point problem. Acta Automatica Sinica, 2025, 51(4): 857−874 doi: 10.16383/j.aas.c240289 [21] 熊梦辉, 杨春雨, 赵建国, 张保勇, 袁德明. 基于边缘动态事件触发的在线分布式复合Bandit优化算法. 自动化学报, 2025, 51(8): 1811−1828 doi: 10.16383/j.aas.c250070Xiong Meng-Hui, Yang Chun-Yu, Zhao Jian-Guo, Zhang Bao-Yong, Yuan De-Ming. Edge dynamic event-triggered-based online distributed composite bandit optimization algorithm. Acta Automatica Sinica, 2025, 51(8): 1811−1828 doi: 10.16383/j.aas.c250070 [22] Yi X, Li X, Yang T, Xie L, Hong Y, Chai T, et al. Distributed online convex optimization with time-varying constraints: tighter cumulative constraint violation bounds under Slater’s condition. IEEE Transactions on Automatic Control, 2025, 70(9): 5764−5779 doi: 10.1109/TAC.2025.3547606 [23] 廖岚, 于湛, 袁德明, 张保勇, 徐胜元. 通信受限的双网络零和博弈分布式在线优化. 自动化学报, 2026, 52(1): 108−120 doi: 10.16383/j.aas.c250295Liao Lan, Yu Zhan, Yuan De-Ming, Zhang Bao-Yong, Xu Sheng-Yuan. Distributed online optimization for two-network zero-sum games under communication constraints. Acta Automatica Sinica, 2026, 52(1): 108−120 doi: 10.16383/j.aas.c250295 [24] Liu Y, Qin W, Bao W, Wang J, Guo J, Zhou M. Decentralized online learning with hard constraints: a doubly-bounded queue approach. IEEE Transactions on Networking, 2026, 34: 5239−5254 doi: 10.1109/TON.2026.3690752 [25] 吴庆涛, 朱军龙, 葛泉波, 张明川. 一种基于条件梯度的加速分布式在线学习算法. 自动化学报, 2024, 50(2): 386−402 doi: 10.16383/j.aas.c210830Wu Qing-Tao, Zhu Jun-Long, Ge Quan-Bo, Zhang Ming-Chuan. An accelerated distributed online learning algorithm based on conditional gradient. Acta Automatica Sinica, 2024, 50(2): 386−402 doi: 10.16383/j.aas.c210830 [26] Mahdavi M, Jin R, Yang T. Trading regret for efficiency: Online convex optimization with long term constraints. Journal of Machine Learning Research, 2012, 13(81): 2503−2528 [27] Jenatton R, Huang J, Archambeau C. Adaptive algorithms for online convex optimization with long-term constraints. In: Proceedings of the International Conference on Machine Learning. New York, USA: PMLR, 2016. 402−411 [28] Yuan J, Lamperski A. Online convex optimization for cumulative constraints. In: Proceedings of the Conference on Neural Information Processing Systems. Montréal, Canada: Curran Associates, Inc., 2018. 6140−6149 [29] Muthirayan D, Yuan J, Khargonekar P P. Online convex optimization with long-term constraints for predictable sequences. IEEE Control Systems Letters, 2023, 7: 979−984 doi: 10.1109/LCSYS.2022.3230440 [30] Yu H, Neely M J. A low complexity algorithm with O(√T) regret and O(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 2020, 21(1): 1−24 [31] Yi X L, Li X X, Yang T, Xie L H, Chai T Y, Johansson K H. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In: Proceedings of the International Conference on Machine Learning. Virtual, Online: PMLR, 2021. 11998−12008 [32] Yu H, Neely M J. A simple parallel algorithm with an $O(1/t)$ convergence rate for general convex programs. SIAM Journal on Optimization, 2017, 27(2): 759−783 doi: 10.1137/16M1059011 [33] Neely M J. Stochastic Network Optimization with Application to Communication and Queueing Systems. San Rafael: Morgan & Claypool Publishers, 2010. [34] Sinha A, Vaze R. Optimal algorithms for online convex optimization with adversarial constraints. In: Proceedings of Advances in Neural Information Processing Systems 37. Vancouver, Canada: Curran Associates, Inc., 2024. 41274−41302 -
下载:
计量
- 文章访问数: 16
- HTML全文浏览量: 9
- 被引次数: 0
