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

Songsong Cheng; Shu Liang

Kybernetika (2020)

  • Volume: 56, Issue: 3, page 559-577
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Cheng, Songsong, and Liang, Shu. "Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate." Kybernetika 56.3 (2020): 559-577. <http://eudml.org/doc/297233>.

@article{Cheng2020,
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.},
author = {Cheng, Songsong, Liang, Shu},
journal = {Kybernetika},
keywords = {multi-agent systems; distributed optimization; unbalanced graph; small gain theory; linear convergence rate},
language = {eng},
number = {3},
pages = {559-577},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate},
url = {http://eudml.org/doc/297233},
volume = {56},
year = {2020},
}

TY - JOUR
AU - Cheng, Songsong
AU - Liang, Shu
TI - Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate
JO - Kybernetika
PY - 2020
PB - Institute of Information Theory and Automation AS CR
VL - 56
IS - 3
SP - 559
EP - 577
AB - 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.
LA - eng
KW - multi-agent systems; distributed optimization; unbalanced graph; small gain theory; linear convergence rate
UR - http://eudml.org/doc/297233
ER -

References

top
  1. Cai, K., Ishii, H., 10.1016/j.automatica.2012.08.003, Automatica 48 (2012), 2750-2761. Zbl1252.93004MR2981359DOI10.1016/j.automatica.2012.08.003
  2. Chang, T., Nedić, A., Scaglione, A., 10.1109/TAC.2014.2308612, IEEE Trans. Automat. Control 59 (2014), 1524-1538. MR3225227DOI10.1109/TAC.2014.2308612
  3. Chen, C., Chan, R., Ma, S., Yang, J., 10.1137/15100463X, SIAM J. Imaging Sci. 8 (2015), 2239-2267. MR3404682DOI10.1137/15100463X
  4. Dominguez-Garcia, A., Hadjicostis, C., 10.1109/TAC.2012.2219953, IEEE Trans. Automat. Control 58 (2013), 667-681. MR3029463DOI10.1109/TAC.2012.2219953
  5. Duchi, J., Agarwal, A., Wainwright, M., 10.1109/TAC.2011.2161027, IEEE Trans. Automat. Control 57 (2012), 592-606. MR2932818DOI10.1109/TAC.2011.2161027
  6. Gharesifard, B., Cortés, J., 10.3166/EJC.18.539-557, Europ. J. Control 18 (2012), 539-557. MR3086897DOI10.3166/EJC.18.539-557
  7. Gharesifard, B., Cortés, J., Jorge, 10.1109/TAC.2013.2278132, IEEE Trans. Automat. Control 59 (2014), 781-786. MR3188487DOI10.1109/TAC.2013.2278132
  8. Loh, H., 10.1287/opre.18.1.87, Oper. Res. 18 (1970), 87-94. MR0265219DOI10.1287/opre.18.1.87
  9. Halabian, H., 10.1109/JSAC.2019.2894305, IEEE J. Selected Areas Commun. 37 (2019), 627-642. DOI10.1109/JSAC.2019.2894305
  10. Jian, L., Hu, J., Wang, J. W., Shi, K., 10.1002/oca.2538, Optimal Control, Appl. Methods 40 (2019), 6, 1071-1087. MR4028355DOI10.1002/oca.2538
  11. Jian, L., Zhao, Y., Hu, J., Li, P., 10.1109/ACCESS.2019.2923269, IEEE Access 7 (2019), 1, 79311-79319. DOI10.1109/ACCESS.2019.2923269
  12. Kempe, D., Dobra, A., Gehrke, J., 10.1109/SFCS.2003.1238221, 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (2003), 482-491. DOI10.1109/SFCS.2003.1238221
  13. Liang, S., Zeng, X., Hong, Y., 10.1109/TAC.2017.2752001, IEEE Trans. Automat. Control 63 (2018), 1753-1759. MR3807659DOI10.1109/TAC.2017.2752001
  14. Liang, S., Wang, L., Yin, G., 10.1016/j.automatica.2018.11.056, Automatica 101 (2019), 175-181. MR3891993DOI10.1016/j.automatica.2018.11.056
  15. Liang, S., Wang, L., Yin, G., Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity 
  16. Lin, P., Peng, Wang, Y., Qi, H., Hong, Y., Distributed consensus-based K-means algorithm in switching multi-agent networks 
  17. Liu, S., Qiu, Z., Xie, L., 10.1016/j.automatica.2017.06.011, Automatica 83 (2017), 162-169. MR3680426DOI10.1016/j.automatica.2017.06.011
  18. Nedić, A., Ozdaglar, A., 10.1109/TAC.2008.2009515, IEEE Trans. Automat. Control. 54 (2009), 48-61. MR2478070DOI10.1109/TAC.2008.2009515
  19. Nedić, A., Ozdaglar, A., Parrilo, P. A., 10.1109/TAC.2010.2041686, IEEE Trans. Automat. Control. 55 (2010), 922-938. MR2654432DOI10.1109/TAC.2010.2041686
  20. Nedić, A., Olshevsky, A., 10.1109/TAC.2016.2529285, IEEE Trans. Automat. Control 61 (2016), 3936-3947. MR3582505DOI10.1109/TAC.2016.2529285
  21. Nedić, A., Olshevsky, A., Shi, W., 10.1137/16M1084316, SIAM J. Optim. 27 (2017), 2597-2633. MR3738851DOI10.1137/16M1084316
  22. Shi, G., Anderson, B. D., Helmke, U., 10.1109/TAC.2016.2612819, IEEE Trans. Automat. Control. 62 (2017), 2659-2674. MR3660554DOI10.1109/TAC.2016.2612819
  23. Shi, W., Ling, Q., Wu, G., Yin, W., 10.1137/14096668X, SIAM J. Optim. 25 (2015), 944-966. MR3343366DOI10.1137/14096668X
  24. Tsianos, K. I., Lawlor, S., Rabbat, M. G., 10.1109/CDC.2012.6426375, In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) 2012, pp. 5453-5458. DOI10.1109/CDC.2012.6426375
  25. Tsianos, K. I., Rabbat, M. G., 10.1109/ACC.2012.6315289, In: 2012 American Control Conference (ACC) 2012, pp. 1067-1072. DOI10.1109/ACC.2012.6315289
  26. Xi, C., Khan, U. A., On the linear convergence of distributed optimization over directed graphs., arXiv preprint arXiv:1510.02149 (2015). 
  27. Xi, C., Khan, U. A., 10.1109/TAC.2016.2615066, IEEE Trans. Automat. Control 62 (2017), 3986-3992. MR3684332DOI10.1109/TAC.2016.2615066
  28. Xin, R., Xi, C., Khan, U. A., Distributed Subgradient Projection Algorithm over Directed Graphs: Alternate Proof., arXiv preprint arXiv:1706.07707 (2017). MR3684332
  29. Xin, R., Xi, C., Khan, U. A., 10.1186/s13634-018-0596-y, EURASIP J. Advances Signal Process. 1 (2019), 1-14. DOI10.1186/s13634-018-0596-y
  30. Yang, T., George, J., Qin, J., Yi, X., Wu, J., Distributed finite-time least squares solver for network linear equations., arXiv preprint arXiv:1810.00156(2018). MR4047486
  31. Yi, P., Hong, Y., F., Liu, 10.1016/j.automatica.2016.08.007, Automatica 74 (2016), 259-269. MR3569392DOI10.1016/j.automatica.2016.08.007
  32. Yuan, D., Proutiere, A., Shi, G., Distributed Online Linear Regression., arXiv preprint arXiv:1902.04774. 
  33. Zeng, X., Yi, P., Hong, Y., 10.1109/TAC.2016.2628807, IEEE Trans. Automat. Control 62 (2017), 5227-5233. MR3708893DOI10.1109/TAC.2016.2628807

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.