Kybernetika 59 no. 3, 392-417, 2023

A penalty ADMM with quantized communication for distributed optimization over multi-agent systems

Chenyang Liu, Xiaohua Dou, Yuan Fan and Songsong ChengDOI: 10.14736/kyb-2023-3-0392

Abstract:

In this paper, we design a distributed penalty ADMM algorithm with quantized communication to solve distributed convex optimization problems over multi-agent systems. Firstly, we introduce a quantization scheme that reduces the bandwidth limitation of multi-agent systems without requiring an encoder or decoder, unlike existing quantized algorithms. This scheme also minimizes the computation burden. Moreover, with the aid of the quantization design, we propose a quantized penalty ADMM to obtain the suboptimal solution. Furthermore, the proposed algorithm converges to the suboptimal solution with an $O(\frac{1}{k})$ convergence rate for general convex objective functions, and with an R-linear rate for strongly convex objective functions.

Keywords:

distributed optimization, quantized communication, alternating direction method of multipliers (ADMM), constrained optimization

Classification:

90C33

paper.pdf

References:

  1. S. A. Alghunaim, E. K. Ryu, K. Yuan and A. H. Sayed: Decentralized proximal gradient algorithms with linear convergence rates. IEEE Trans. Automat. Control 66 (2020), 6, 2787-2794.   DOI:10.1109/TAC.2020.3009363
  2. S. Boyd, D. Persi and L. Xiao: Fastest mixing Markov chain on a graph. SIAM Rev. 46 (2004), 4, 667-689.   DOI:10.1137/S0036144503423264
  3. Z. Chen and S. Liang: Distributed aggregative optimization with quantized communication. Kybernetika 58 (2022), 1, 123-144.   DOI:10.14736/kyb-2022-1-0123
  4. Z. Chen, J. Ma, S. Liang and L. Li: Distributed Nash equilibrium seeking under quantization communication. Automatica 141 (2022), 110318.   DOI:10.1016/j.automatica.2022.110318
  5. S. Cheng, S. Liang, Y. Fan and Y. Hong: Distributed gradient tracking for unbalanced optimization with different constraint sets. IEEE Trans. Automat. Control (2022).   DOI:10.1109/TAC.2022.3192316
  6. T. Dorina, K. Effrosyni, Y. Pu and F. Pascal: Distributed average consensus with quantization refinement. IEEE Trans. Signal Process. 61 (2013), 1, 194-205.   DOI:10.1109/TSP.2012.2223692
  7. L. Jian, J. Hu, J. Wang and K. Shi: Distributed inexact dual consensus ADMM for network resource allocation. Optimal Control Appl. Methods 40 (2019), 6, 1071-1087.   DOI:10.1002/oca.2538
  8. J. Lei, H. Chen and H. Fang: Primal-dual algorithm for distributed constrained optimization. Systems Control Lett. 96 (2016), 110-117.   DOI:10.1016/j.sysconle.2016.07.009
  9. J. Lei, P. Yi, G. Shi and D. O. A. Brian: Distributed algorithms with finite data rates that solve linear equations. SIAM J. Optim. 30 (2020), 2, 1191-1222.   DOI:10.1137/19M1258864
  10. X. Li, G. Feng and L. Xie: Distributed proximal algorithms for multi-agent optimization with coupled inequality constraints. IEEE Trans. Automat. Control 66 (2021), 3, 1223-1230.   DOI:10.1109/TAC.2020.2989282
  11. X. Li, F. Gang and X. Lihua: Distributed proximal point algorithm for constrained optimization over unbalanced graphs. 2019 IEEE 15th International Conference on Control and Automation (ICCA), IEEE, (2019), 824-829.   DOI:10.1109/ICCA.2019.8899938
  12. P. Li, J. Hu, L. Qiu, Y. Zhao and K. G. Bijoy: A distributed economic dispatch strategy for power-water networks. IEEE Trans. Control Network Systems 9 (2022), 1, 356-366.   DOI:10.1109/TCNS.2021.3104103
  13. W. Li, X. Zeng, S. Liang and Y. Hong: Exponentially convergent algorithm design for constrained distributed optimization via nonsmooth approach. IEEE Trans. Automat. Control 67 (2022), 2, 934-940.   DOI:10.1109/TAC.2021.3075666
  14. S. Liang, L. Wang and Y. George: Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity. Automatica 105 (2019), 298-306.   DOI:10.1016/j.automatica.2019.04.004
  15. Y. Liu, G. Wu, Z. Tian and Q. Ling: DQC-ADMM: decentralized dynamic ADMM with quantized and censored communications. IEEE Trans. Neural Networks Learn. Systems 33 (2022), 8, 3290-3304.   DOI:10.1109/TNNLS.2021.3051638
  16. S. Ma: Alternating proximal gradient method for convex minimization. J. Scientific Computing 68 (2016), 2, 546-572.   DOI:10.1007/s10915-015-0150-0
  17. X. Ma, P. Yi and J. Chen: Distributed gradient tracking methods with finite data rates. J. Systems Science Complexity 34 (2021), 5, 1927-1952.   DOI:10.1007/s11424-021-1231-9
  18. S. U. Pillai, S. Torsten and Ch. Seunghun: The Perron-Frobenius theorem: some of its applications. IEEE Signal Process. Magazine 22 (2005), 2, 62-75.   DOI:10.1109/MSP.2005.1406483
  19. Z. Qiu, L. Xie and Y. Hong: Quantized leaderless and leader-following consensus of high-order multi-agent systems with limited data rate. IEEE Trans. Automat. Control 61 (2016), 9, 2432-2447.   DOI:10.1109/TAC.2015.2495579
  20. W. Shi, Q. Ling, K. Yuan, G. Wu and W. Yin: On the linear convergence of the ADMM in decentralized consensus optimization. IEEE Trans. Signal Process. 62 (2014), 7, 1750-1761.   DOI:10.1109/TSP.2014.2304432
  21. C. Wang, S. Xu, D. Yuan, B. Zhang and Z. Zhang: Distributed online convex optimization with a bandit primal-dual mirror descent push-sum algorithm. Neurocomputing 497 (2022), 204-215.   DOI:10.1016/j.neucom.2022.05.024
  22. J. Wang, L. Fu, Y. Gu and T. Li: Convergence of distributed gradient-tracking-based optimization algorithms with random graphs. J. Systems Science Complexity 34 (2021), 4, 1438-1453.   DOI:10.1007/s11424-021-9355-5
  23. Y. Wei, H. Fang, X. Zeng, J. Chen and P. Panos: A smooth double proximal primal-dual algorithm for a class of distributed nonsmooth optimization problems. IEEE Trans. Automat. Control 65 (2020), 4, 1800-1806.   DOI:10.1109/TAC.2019.2936355
  24. X. Xie, Q. Ling, P. Lu, W. Xu and Z. Zhu: Evacuate before too late: distributed backup in inter-DC networks with progressive disasters. IEEE Trans. Parallel Distributed Systems 29 (2018), 5, 1058-1074.   DOI:10.1109/TPDS.2017.2785385
  25. T. Xu and W. Wu: Accelerated ADMM-based fully distributed inverter-based Volt/Var control strategy for active distribution networks. IEEE Trans. Industr. Inform. 16 (2020), 12, 7532-7543.   DOI:10.1109/TII.2020.2966713
  26. P. Yi and Y. Hong: Quantized subgradient algorithm and data-rate analysis for distributed optimization. IEEE Trans. Contro Network Systems 1 (2014), 4, 380-392.   DOI:10.1109/TCNS.2014.2357513
  27. W. Yu, H. Liu, W. Z. Zheng and Y. Zhu: Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs Automatica 134 (2021), 11, 109899.   DOI:10.1016/j.automatica.2021.109899
  28. D. Yuan, Y. Hong, W. C. H. Daniel and S. Xu: Distributed mirror descent for online composite optimization. IEEE Trans. Automat. Control 66 (2021), 2, 714-729.   DOI:10.1109/TAC.2020.2987379
  29. D. Yuan, S. Xu, B. Zhang and L. Rong: Distributed primal-dual stochastic subgradient algorithms for multi-agent optimization under inequality constraints. Int. J. Robust Nonlinear Control 23 (2013), 15, 1846-1868.   DOI:10.1002/rnc.2856
  30. J. Zhang, H. Liu, M.-Ch. S. Anthony, Man-Cho and Q. Ling: A penalty alternating direction method of multipliers for convex composite optimization over decentralized networks. IEEE Trans. Signal Process. 69 (2021), 4282-4295.   DOI:10.1109/TSP.2021.3092347
  31. X. Zhao, P. Yi and L. Li: Distributed policy evaluation via inexact ADMM in multi-agent reinforcement learning. Control Theory Technol. 18 (2020), 4, 362-378.   DOI:10.1007/s11768-020-00007-x
  32. H. Zhou, X. Zeng and Y. Hong: Adaptive exact penalty design for constrained distributed optimization. IEEE Trans. Automat. Control 64 (2019), 11, 4661-4667.   DOI:10.1109/TAC.2019.2902612