Distributed Communication-Sliding Mirror-Descent Algorithm for Nonsmooth Resource Allocation Problem

doi:10.1007/s11424-022-0187-8

Journal of Systems Science and Complexity ›› 2022, Vol. 35 ›› Issue (4): 1244-1261.DOI: 10.1007/s11424-022-0187-8

Previous Articles Next Articles

Distributed Communication-Sliding Mirror-Descent Algorithm for Nonsmooth Resource Allocation Problem

WANG Yinghui¹, TU Zhipeng^2,3, QIN Huashu^2,3

1. School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China;
2. Key Lab of Systems and Control, Academy of Mathematics and Systems Science, Beijing 100190, China;
3. University of Chinese Academy of Sciences, Beijing 100190, China

Received:2020-08-09 Revised:2021-09-14 Online:2022-08-25 Published:2022-08-02
Supported by:
This research was supported by the National Natural Science Foundation of China under Grant Nos. 72101026, 61621063, and the State Key Laboratory of Intelligent Control and Decision of Complex Systems

PDF ( 1 ) Cited

WANG Yinghui, TU Zhipeng, QIN Huashu. Distributed Communication-Sliding Mirror-Descent Algorithm for Nonsmooth Resource Allocation Problem[J]. Journal of Systems Science and Complexity, 2022, 35(4): 1244-1261.

This paper considers a distributed nonsmooth resource allocation problem of minimizing a global convex function formed by a sum of local nonsmooth convex functions with coupled constraints. A distributed communication-efficient mirror-descent algorithm, which can reduce communication rounds between agents over the network, is designed for the distributed resource allocation problem. By employing communication-sliding methods, agents can find a ε-solution in O($\frac{1}{\varepsilon }$) communication rounds while maintaining O($\frac{1}{\varepsilon ^2}$) subgradient evaluations for nonsmooth convex functions. A numerical example is also given to illustrate the effectiveness of the proposed algorithm.

Key words: Distributed resource allocation problem, mirror-descent algorithm, nonsmooth functions

[1] Yi P, Hong Y, and Liu F, Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems, Automatica, 2016, 74: 259-269.
[2] Zeng X, Yi P, and Hong Y, Distributed algorithm for robust resource allocation with polyhedral uncertain allocation parameters, Journal of Systems Science & Complexity, 2018, 31(1): 103-119.
[3] Nedi A, Olshevsky A, and Shi W, Improved convergence rates for distributed resource allocation, 2018 IEEE Conference on Decision and Control (CDC), IEEE, 2018, 172-177.
[4] Wang Y, Tu Z, and Qin H, Distributed stochastic mirror descent algorithm for resource allocation problem, Control Theory and Technology, 2020, 18(4): 339-347.
[5] Zhu M and Martnez S, On distributed convex optimization under inequality and equality constraints, IEEE Transactions on Automatic Control, 2011, 57(1): 151-164.
[6] Zhang J, You K, and Cai K, Distributed dual gradient tracking for resource allocation in unbalanced networks, IEEE Transactions on Signal Processing, 2020, 68: 2186-2198.
[7] Xu J, Zhu S, Soh Y C, et al., A dual splitting approach for distributed resource allocation with regularization, IEEE Transactions on Control of Network Systems, 2018, 6(1): 403-414.
[8] Roth V, The generalized LASSO, IEEE Transactions on Neural Networks, 2004, 15(1): 16-28.
[9] Deng Z, Nian X, and Hu C, Distributed algorithm design for nonsmooth resource allocation problems, IEEE transactions on cybernetics, 2019, 50(7): 3208-3217.
[10] Zhu Y, Wen G, Yu W, et al., Continuous-time distributed proximal gradient algorithms for nonsmooth resource allocation over general digraphs, IEEE Transactions on Network Science and Engineering, 2021, DOI: 10.1109/TNSE.2021.3070398.
[11] Wei Y, Shang C, Fang H, et al. Solving a class of nonsmooth resource allocation problems with directed graphs though distributed smooth multi-proximal algorithms, Automatica, 2022, 136: 110071.
[12] Iiduka H, Distributed optimization for network resource allocation with nonsmooth utility functions, IEEE Transactions on Control of Network Systems, 2018, 6(4): 1354-1365.
[13] Nesterov Y and Shikhman V, Dual subgradient method with averaging for optimal resource allocation, European Journal of Operational Research, 2018, 270(3): 907-916.
[14] Bregman L M, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, 1967, 7(3): 200-217.
[15] Yuan D, Hong Y, Ho D W C, et al., Optimal distributed stochastic mirror descent for strongly convex optimization, Automatica, 2018, 90: 196-203.
[16] Lan G, Lee S, and Zhou Y, Communication-efficient algorithms for decentralized and stochastic optimization, Mathematical Programming, 2020, 180(1): 237-284.
[17] Ouyang Y, Chen Y, Lan G, et al., An accelerated linearized alternating direction method of multipliers, SIAM Journal on Imaging Sciences, 2015, 8(1): 644-681.
[18] Ghadimi S and Lan G, Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework, SIAM Journal on Optimization, 2012, 22(4): 1469-1492.

No related articles found!

Viewed

Full text

Abstract