Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization

doi:10.1007/s40305-023-00496-y

Journal of the Operations Research Society of China ›› 2025, Vol. 13 ›› Issue (2): 364-392.doi: 10.1007/s40305-023-00496-y

收稿日期:2022-12-14 修回日期:2023-05-10 出版日期:2025-06-30 发布日期:2025-07-07
作者简介:Hao-Yang Liu,E-mail:hyliu@mail.dlut.edu.cn;Li-Wei Zhang,E-mail:lwzhang@dlut.edu.cn

Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization

Hao-Yang Liu, Xian-Tao Xiao, Li-Wei Zhang

School of Mathematical Sciences, Dalian University of Technology, Dalian 116023, Liaoning, China

Received:2022-12-14 Revised:2023-05-10 Online:2025-06-30 Published:2025-07-07
Contact: Xian-Tao Xiao E-mail:xtxiao@dlut.edu.cn
Supported by:
This work was supported in part by the National Key R&D Program of China (No. 2022YFA1004000) and the National Natural Science Foundation of China (Nos. 11971089 and 12271076).

摘要/Abstract

Abstract: In this paper, we consider online convex optimization (OCO) with time-varying loss and constraint functions. Specifically, the decision-maker chooses sequential decisions based only on past information; meantime, the loss and constraint functions are revealed over time. We first develop a class of model-based augmented Lagrangian methods (MALM) for time-varying functional constrained OCO (without feedback delay). Under standard assumptions, we establish sublinear regret and sublinear constraint violation of MALM. Furthermore, we extend MALM to deal with time-varying functional constrained OCO with delayed feedback, in which the feedback information of loss and constraint functions is revealed to decision-maker with delays. Without additional assumptions, we also establish sublinear regret and sublinear constraint violation for the delayed version of MALM. Finally, numerical results for several examples of constrained OCO including online network resource allocation, online logistic regression and online quadratically constrained quadratical program are presented to demonstrate the efficiency of the proposed algorithms.

Key words: Online convex optimization, Time-varying constraints, Augmented Lagrangian, Regret, Constraint violation

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 364-392.

Hao-Yang Liu, Xian-Tao Xiao, Li-Wei Zhang. Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization[J]. Journal of the Operations Research Society of China, 2025, 13(2): 364-392.

参考文献

[1] Shalev-Shwartz, S.: Online learning and online convex optimization. Found. Trends^® Mach. Learn. 4(2), 107-194 (2011)
[2] Hazan, E.: Introduction to online convex optimization. Found. Trends^® Optim. 2(3-4), 157-325 (2015)
[3] Hoi, S.C.H., Sahoo, D., Lu, J., Zhao, P.: Online learning: a comprehensive survey. Neurocomputing 459, 249-289 (2021)
[4] Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning, pp. 928-935 (2003)
[5] Hazan, E., Agarwal, A., Kale, S.: Logarithmic regret algorithms for online convex optimization. Mach. Learn. 69, 169-192 (2007)
[6] Dixit, R., Bedi, A.S., Tripathi, R., Rajawat, K.: Online learning with inexact proximal online gradient descent algorithms. IEEE Trans. Signal Process. 67(5), 1338-1352 (2019)
[7] Mahdavi, M., Jin, R., Yang, T.: Trading regret for efficiency: online convex optimization with long term constraints. J. Mach. Learn. Res. 13, 2503-2528 (2012)
[8] 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. J. Mach. Learn. Res. 21, 1-24 (2020)
[9] Mannor, S., Tsitsiklis, J.N., Yu, J.Y.: Online learning with sample path constraints. J. Mach. Learn. Res. 10, 569-590 (2009)
[10] Paternain, S., Ribeiro, A.: Online learning of feasible strategies in unknown environments. IEEE Trans. Automat. Control 62(6), 2807-2822 (2017)
[11] Chen, T., Ling, Q., Giannakis, G.B.: An online convex optimization approach to proactive network resource allocation. IEEE Trans. Signal Process. 65(24), 6350-6364 (2017)
[12] Neely, M.J., Yu, H.: Online convex optimization with time-varying constraints. arXiv:1702.04783 (2017)
[13] Cao, X., Liu, K.J.R.: Online convex optimization with time-varying constraints and bandit feedback. IEEE Trans. Automat. Control 64(7), 2665-2680 (2019)
[14] Zhang, Y., Dall’Anese, E., Hong, M.: Online proximal-ADMM for time-varying constrained convex optimization. IEEE Trans. Signal Inform. Process. Netw. 7, 144-155 (2021)
[15] Fazlyab, M., Paternain, S., Preciado, V.M., Ribeiro, A.: Prediction-correction interior-point method for time-varying convex optimization. IEEE Trans. Automat. Control 63(7), 1973-1986 (2018)
[16] Cao, X., Başar, T.: Decentralized online convex optimization based on signs of relative states. Automatica J. IFAC 129, 109676-13 (2021)
[17] Yi, X., Li, X., Yang, T., Xie, L., Chai, T., Johansson, K.H.: Distributed bandit online convex optimization with time-varying coupled inequality constraints. IEEE Trans. Automat. Control 66(10), 4620-4635 (2021)
[18] Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97-116 (1976)
[19] Zhao, X.-Y., Sun, D., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737-1765 (2010)
[20] Chatzipanagiotis, N., Dentcheva, D., Zavlanos, M.M.: An augmented Lagrangian method for distributed optimization. Math. Program. 152(1-2, Ser. A), 405-434 (2015)
[21] Chatzipanagiotis, N., Zavlanos, M.M.: A distributed algorithm for convex constrained optimization under noise. IEEE Trans. Automat. Control 61(9), 2496-2511 (2016)
[22] Moradian, H., Kia, S.S.: Cluster-based distributed augmented Lagrangian algorithm for a class of constrained convex optimization problems. Automatica J. IFAC 129, 109608 (2021)
[23] Zhang, L., Zhang, Y., Wu, J., Xiao, X.: Solving stochastic optimization with expectation constraints efficiently by a stochastic augmented Lagrangian-type algorithm. INFORMS J. Comput. 34(6), 2989-3006 (2022)
[24] Zinkevich, M., Langford, J., Smola, A.: Slow learners are fast. In: Advances in Neural Information Processing Systems, vol. 22, pp. 2331-2339 (2009)
[25] Joulani, P., Gyorgy, A., Szepesvari, C.: Online learning under delayed feedback. In: Proceedings of Machine Learning Research, vol. 28, pp. 1453-1461. PMLR, Atlanta (2013)
[26] Pan, W., Shi, G., Lin, Y., Wierman, A.: Online optimization with feedback delay and nonlinear switching cost. Proc. ACM Meas. Anal. Comput. Syst. 6(1), 1-34 (2022)
[27] Cao, X., Zhang, J., Poor, H.V.: Constrained online convex optimization with feedback delays. IEEE Trans. Automat. Control 66(11), 5049-5064 (2021)
[28] Asi, H., Duchi, J.C.: Stochastic (approximate) proximal point methods: convergence, optimality, and adaptivity. SIAM J. Optim. 29(3), 2257-2290 (2019)
[29] Liakopoulos, N., Destounis, A., Paschos, G., Spyropoulos, T., Mertikopoulos, P.: Cautious regret minimization: online optimization with long-term budget constraints. In: Proceedings of the 36th International Conference on Machine Learning, vol. 97, pp. 3944-3952 (2019)
[30] Bernstein, A., Dall’Anese, E., Simonetto, A.: Online primal-dual methods with measurement feedback for time-varying convex optimization. IEEE Trans. Signal Process. 67(8), 1978-1991 (2019)
[31] Zhang, L., Liu, H., Xiao, X.: Regrets of proximal method of multipliers for online non-convex optimization with long term constraints. J. Glob. Optim. 85(1), 61-80 (2023)
[32] Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http://cvxr.com/cvx (2014)
[33] Yi, X., Li, X., Xie, L., Johansson, K.H.: Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Trans. Signal Process. 68, 731-746 (2020)
[34] Cao, X., Başar, T.: Decentralized online convex optimization with event-triggered communications. IEEE Trans. Signal Process. 69, 284-299 (2021)
[35] Wang, C., Xu, S.: Distributed online constrained optimization with feedback delays. IEEE Trans. Neural Netw. Learn Syst. (2023). Online first
[36] Liu, P., Lu, K., Xiao, F., Wei, B., Zheng, Y.: Online distributed learning for aggregative games with feedback delays. IEEE Trans. Automat. Control (2023). https://doi.org/10.1109/TAC.2023.3237781

Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价