Kybernetika 58 no. 1, 123-144, 2022

Distributed aggregative optimization with quantized communication

Ziqin Chen and Shu LiangDOI: 10.14736/kyb-2022-1-0123

Abstract:

In this paper, we focus on an aggregative optimization problem under the communication bottleneck. The aggregative optimization is to minimize the sum of local cost functions. Each cost function depends on not only local state variables but also the sum of functions of global state variables. The goal is to solve the aggregative optimization problem through distributed computation and local efficient communication over a network of agents without a central coordinator. Using the variable tracking method to seek the global state variables and the quantization scheme to reduce the communication cost spent in the optimization process, we develop a novel distributed quantized algorithm, called D-QAGT, to track the optimal variables with finite bits communication. Although quantization may lose transmitting information, our algorithm can still achieve the exact optimal solution with linear convergence rate. Simulation experiments on an optimal placement problem is carried out to verify the correctness of the theoretical results.

Keywords:

multi-agent network, linear convergence rate, distributed aggregative optimization, quantized communication

Classification:

90C33, 68W15

paper.pdf

References:

  1. S. Barbarossa, S. Sardellitti and P. D. Lorenzo: Communicating while computing: Distributed mobile cloud computing over 5G heterogeneous networks. IEEE Signal Process. Mag. 31 (2014), 45-55.   DOI:10.1109/MSP.2014.2334709
  2. X. Cao and K. J. R. Liu: Distributed Newton's method for network cost minimization. IEEE Trans. Automat. Control 66 (2021), 1278-1285.   DOI:10.1109/TAC.2020.2989266
  3. S. Cheng and S. Liang: Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate. Kybernetika 56 (2020), 559-577.   DOI:10.14736/kyb-2020-3-0559
  4. J. Chen and A. Sayed: Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Trans. Signal Process. 60 (2012), 4289-4305.   DOI:10.1109/TSP.2012.2198470
  5. Z. Deng and S. Liang: Distributed algorithms for aggregative games of multiple heterogeneous Euler-Lagrange systems. Automatica 99 (2019), 246-252.   DOI:10.1016/j.automatica.2018.10.041
  6. C. De Persis and S. Grammatico: Continuous-time integral dynamics for a class of aggregative games with coupling constraints. IEEE Trans. Automat. Control 65 (2020), 2171-2176.   DOI:10.1109/TAC.2019.2939639
  7. R. A. Horn and C. R Johnson: Matrix Analysis. Cambridge University Press, New York 2012.   CrossRef
  8. D. Jakovetic, J. M. F. Moura and J. Xavier: Linear convergence rate of a class of distributed augmented Lagrangian algorithms. IEEE Trans. Automat. Control 60 (2015), 922-936.   DOI:10.1109/TAC.2014.2363299
  9. Y. Kajiyama, N. Hayashi and S. Takai: Linear convergence of consensus-based quantized optimization for smooth and strongly convex cost functions. IEEE Trans. Automat. Control 66 (2020), 1254-1261.   DOI:10.1109/TAC.2020.2989281
  10. G. Lan, S. Lee and Y. Zhou: Communication-efficient algorithms for decentralized and stochastic optimization. Math. Program. 180 (2020), 237-284.   DOI:10.1007/s10107-018-1355-4
  11. P. Li and J. Hu: A solution strategy for distributed uncertain economic dispatch problems via scenario theory. Control Theory Technol. 19 (2021), 499-506.   DOI:10.1007/s11768-021-00068-6
  12. P. Li, J. Hu, L. Qiu, Y. Zhao and B. Ghosh: A distributed economic dispatch strategy for power-water networks. IEEE Trans. Control Netw. Syst., Early Access (2021).   DOI:10.1109/tcns.2021.3104103
  13. X. Li, L. Xie and Y. Hong: Distributed continuous-time algorithm for a general nonsmooth monotropic optimization problem. Int. J. Robust Nonlinear Control 29 (2019), 3252-3266.   DOI:10.1002/rnc.4547
  14. X. Li, L. Xie and Y. Hong: Distributed aggregative optimization over multi-agent networks. IEEE Trans. Automat. Control. Early Access (2021).   DOI:10.1109/TAC.2021.3095456
  15. J. Ma, X. Yu, L. Liu and G. Feng: Global cooperative output regulation of linear multi-agent systems with limited bandwidth. IEEE Trans. Control Netw. Syst., Early Access (2021).   DOI:10.1109/TCNS.2021.3128500
  16. S. Magnussson, H. Shokri-Ghadikolaei and N. Li: On maintaining linear convergence of distributed learning and optimization under limited communication. IEEE Trans. Signal Process. 68 (2020), 6101-6116.   DOI:10.1109/TSP.2020.3031073
  17. E. J. Msechu and G. B. Giannakis: Sensor-centric data reduction for estimation with WSNs via censoring and quantization. IEEE Trans. Signal Process. 60 (2011), 400-414.   DOI:10.1109/TSP.2011.2171686
  18. A. Nedic: Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Process. Mag. 73 (2020), 92-101.   CrossRef
  19. A. Nedic and A. Ozdaglar: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Autom. Control 54 (2009), 48-61.   DOI:10.1109/TAC.2008.2009515
  20. Y. Pu, M. N. Zeilinger and C. N. Jones: Quantization design for distributed optimization. IEEE Trans. Automat. Control 62 (2016), 2107-2120.   DOI:10.1109/TAC.2016.2600597
  21. W. Ren and R. W. Beard: Distributed consensus in multi-vehicle cooperative control. Springer, London 2008.   CrossRef
  22. W. Shi, Q. Ling, G. Wu and W. Yin: EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25 (2015), 944--966.   DOI:10.1137/14096668X
  23. E. Tardos and V. V. Vazirani: Basic solution concepts and computational issues. Algorithmic Game Theory (2007), 3-28.   DOI:10.1017/cbo9780511800481.003
  24. X. Wang, Z. Deng, S. Ma and D. Xian: Event-triggered design for multi-agent optimal consensus of Euler-Lagrangian systems. Kybernetika 53 (2017), 179-194.   DOI:10.14736/kyb-2017-1-0179
  25. Y. Wang, P. Lin and H. Qin: Distributed classification learning based on nonlinear vector support machines for switching networks. Kybernetika 53 (2017), 595-611.   DOI:10.14736/kyb-2017-4-0595
  26. J. Xu, S. Zhu, Y. C. Soh and L. Xie: A Bregman splitting scheme for distributed optimization over networks. IEEE Trans. Automat. Control 63 (2018), 3809-3824.   DOI:10.1109/TAC.2018.2805260
  27. P. Yi and Y. Hong: Quantized subgradient algorithm and data-rate analysis for distributed optimization. IEEE Trans. Control Netw. Syst. 1 (2014), 380-392.   DOI:10.1109/TCNS.2014.2357513
  28. P. Yi, Y. Hong and F. Liu: Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and its application to economic dispatch of power systems. Automatica 74 (2016), 259-269.   DOI:10.1016/j.automatica.2016.08.007
  29. D. Yuan, Y. Hong, D. Ho and G. Jiang: Optimal distributed stochastic mirror descent for strongly convex optimization. Automatica 90 (2018), 196-203.   DOI:10.1016/j.automatica.2017.12.053
  30. X. Zhang, J. Liu, Z. Zhu and E. S. Bentley: Compressed distributed gradient descent: Communication-efficient consensus over networks. In: Proc. IEEE Conf. Comput. Commun. 2019, 2431-2439.   DOI:10.1109/infocom.2019.8737489
  31. S. Zhu, M. Hong and B. Chen: Quantized consensus ADMM for multi-agent distributed optimization. In: Proc. IEEE Int. Conf. Acoust., Speech Signal Process 2016, pp. 4134-4138.   DOI:10.1109/icassp.2016.7472455