Kybernetika 56 no. 3, 559-577, 2020

Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate

Songsong Cheng and Shu LiangDOI: 10.14736/kyb-2020-3-0559

Abstract:

Distributed optimization over unbalanced graphs is an important problem in multi-agent systems. Most of literatures, by introducing some auxiliary variables, utilize the Push-Sum scheme to handle the widespread unbalance graph with row or column stochastic matrix only. But the introduced auxiliary dynamics bring more calculation and communication tasks. In this paper, based on the in-degree and out-degree information of each agent, we propose an innovative distributed optimization algorithm to reduce the calculation and communication complexity of the conventional Push-Sum scheme. Furthermore, with the aid of small gain theory, we prove the linear convergence rate of the proposed algorithm.

Keywords:

multi-agent systems, distributed optimization, unbalanced graph, small gain theory, linear convergence rate

Classification:

90C33, 68W15

References:

  1. K. Cai and H. Ishii: Average consensus on general strongly connected digraphs. Automatica 48 (2012), 2750-2761.   DOI:10.1016/j.automatica.2012.08.003
  2. T. Chang, A. Nedić and A. Scaglione: Distributed constrained optimization by consensus-based primal-dual perturbation method. IEEE Trans. Automat. Control 59 (2014), 1524-1538.   DOI:10.1109/TAC.2014.2308612
  3. C. Chen, R. Chan, S. Ma and J. Yang: Inertial proximal {ADMM} for linearly constrained separable convex optimization. SIAM J. Imaging Sci. 8 (2015), 2239-2267.   DOI:10.1137/15100463X
  4. A. Dominguez-Garcia and C. Hadjicostis: Distributed matrix scaling and application to average consensus in directed graphs. IEEE Trans. Automat. Control 58 (2013), 667-681.   DOI:10.1109/TAC.2012.2219953
  5. J. Duchi, A. Agarwal and M. Wainwright: Dual averaging for distributed optimization: {C}onvergence analysis and network scaling. IEEE Trans. Automat. Control 57 (2012), 592-606.   DOI:10.1109/TAC.2011.2161027
  6. B. Gharesifard and J. Cortés: Distributed strategies for generating weight-balanced and doubly stochastic digraphs. Europ. J. Control 18 (2012), 539-557.   DOI:10.3166/EJC.18.539-557
  7. B. Gharesifard, J. Cortés and Jorge: Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Trans. Automat. Control 59 (2014), 781-786.   DOI:10.1109/TAC.2013.2278132
  8. H. Loh: On a class of directed graphswith an application to traffic-flow problems. Oper. Res. 18 (1970), 87-94.   DOI:10.1287/opre.18.1.87
  9. H. Halabian: Distributed Resource Allocation Optimization in {5G} Virtualized Networks. IEEE J. Selected Areas Commun. 37 (2019), 627-642.   DOI:10.1109/JSAC.2019.2894305
  10. L. Jian, J. Hu, J. W. 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
  11. L. Jian, Y. Zhao, J. Hu and P. Li: Distributed inexact consensus-based ADMM method for multi-agent unconstrained optimization problem. IEEE Access 7 (2019), 1, 79311-79319.   DOI:10.1109/ACCESS.2019.2923269
  12. D. Kempe, A. Dobra and J. Gehrke: Gossip-based computation of aggregate information. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (2003), 482-491.   DOI:10.1109/SFCS.2003.1238221
  13. S. Liang, X. Zeng and Y. Hong: Distributed nonsmooth optimization with coupled inequality constraints via modified lagrangian function. IEEE Trans. Automat. Control 63 (2018), 1753-1759.   DOI:10.1109/TAC.2017.2752001
  14. S. Liang, L. Wang and G. Yin: Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs. Automatica 101 (2019), 175-181.   DOI:10.1016/j.automatica.2018.11.056
  15. S. Liang, L. Wang and G. Yin: Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity    CrossRef
  16. P. Lin, Peng, Y. Wang, H. Qi and Y. Hong: Distributed consensus-based K-means algorithm in switching multi-agent networks    CrossRef
  17. S. Liu, Z. Qiu and L. Xie: Convergence rate analysis of distributed optimization with projected subgradient algorithm. Automatica 83 (2017), 162-169.   DOI:10.1016/j.automatica.2017.06.011
  18. A. Nedić and A. Ozdaglar: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control. 54 (2009), 48-61.   DOI:10.1109/TAC.2008.2009515
  19. A. Nedić, A. Ozdaglar and P. A. Parrilo: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control. 55 (2010), 922-938.   DOI:10.1109/TAC.2010.2041686
  20. A. Nedić and A. Olshevsky: Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Trans. Automat. Control 61 (2016), 3936-3947.   DOI:10.1109/TAC.2016.2529285
  21. A. Nedić, A. Olshevsky and W. Shi: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J. Optim. 27 (2017), 2597-2633.   DOI:10.1137/16M1084316
  22. G. Shi, B. D. Anderson and U. Helmke: Network flows that solve linear equations. IEEE Trans. Automat. Control. 62 (2017), 2659-2674.   DOI:10.1109/TAC.2016.2612819
  23. W. Shi, Q. Ling, G. Wu and W. Yin: Extra: {A}n exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25 (2015), 944-966.   DOI:10.1137/14096668X
  24. K. I. Tsianos, S. Lawlor and M. G. Rabbat: Push-sum distributed dual averaging for convex optimization. In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) 2012, pp. 5453-5458.   DOI:10.1109/CDC.2012.6426375
  25. K. I. Tsianos and M. G. Rabbat: Distributed dual averaging for convex optimization under communication delays. In: 2012 American Control Conference (ACC) 2012, pp. 1067-1072.   DOI:10.1109/ACC.2012.6315289
  26. C. Xi and U. A. Khan: On the linear convergence of distributed optimization over directed graphs. arXiv preprint arXiv:1510.02149 (2015).   CrossRef
  27. C. Xi and U. A. Khan: Distributed subgradient projection algorithm over directed graphs. IEEE Trans. Automat. Control 62 (2017), 3986-3992.   DOI:10.1109/TAC.2016.2615066
  28. R. Xin, C. Xi and U. A. Khan: Distributed Subgradient Projection Algorithm over Directed Graphs: Alternate Proof. arXiv preprint arXiv:1706.07707 (2017).   CrossRef
  29. R. Xin, C. Xi and U. A. Khan: {FROST}-{F}ast row-stochastic optimization with uncoordinated step-sizes. EURASIP J. Advances Signal Process. 1 (2019), 1-14.   DOI:10.1186/s13634-018-0596-y
  30. T. Yang, J. George, J. Qin, X. Yi and J. Wu: Distributed finite-time least squares solver for network linear equations. arXiv preprint arXiv:1810.00156(2018).   CrossRef
  31. P. Yi, Y. Hong, F. and 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
  32. D. Yuan, A. Proutiere and G. Shi: Distributed Online Linear Regression. arXiv preprint arXiv:1902.04774.   CrossRef
  33. X. Zeng, P. Yi and Y. Hong: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2017), 5227-5233.   DOI:10.1109/TAC.2016.2628807