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

Cheng, Songsong ; Liang, Shu

Kybernetika, Tome 56 (2020) no. 3, pp. 559-577

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2020-3-0559

Classification : 68W15, 90C33
Keywords: multi-agent systems; distributed optimization; unbalanced graph; small gain theory; linear convergence rate

Bibliographie

[1] Cai, K., Ishii, H.: Average consensus on general strongly connected digraphs. Automatica 48 (2012), 2750-2761. | DOI | MR | Zbl

[2] Chang, T., Nedić, A., Scaglione, A.: Distributed constrained optimization by consensus-based primal-dual perturbation method. IEEE Trans. Automat. Control 59 (2014), 1524-1538. | DOI | MR

[3] Chen, C., Chan, R., Ma, S., Yang, J.: Inertial proximal ADMM for linearly constrained separable convex optimization. SIAM J. Imaging Sci. 8 (2015), 2239-2267. | DOI | MR

[4] Dominguez-Garcia, A., Hadjicostis, C.: Distributed matrix scaling and application to average consensus in directed graphs. IEEE Trans. Automat. Control 58 (2013), 667-681. | DOI | MR

[5] Duchi, J., Agarwal, A., Wainwright, M.: Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Automat. Control 57 (2012), 592-606. | DOI | MR

[6] Gharesifard, B., Cortés, J.: Distributed strategies for generating weight-balanced and doubly stochastic digraphs. Europ. J. Control 18 (2012), 539-557. | DOI | MR

[7] Gharesifard, B., Cortés, J., Jorge: Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Trans. Automat. Control 59 (2014), 781-786. | DOI | MR

[8] Loh, H.: On a class of directed graphswith an application to traffic-flow problems. Oper. Res. 18 (1970), 87-94. | DOI | MR

[9] Halabian, H.: Distributed Resource Allocation Optimization in 5G Virtualized Networks. IEEE J. Selected Areas Commun. 37 (2019), 627-642. | DOI

[10] Jian, L., Hu, J., Wang, J. W., Shi, K.: Distributed inexact dual consensus ADMM for network resource allocation. Optimal Control, Appl. Methods 40 (2019), 6, 1071-1087. | DOI | MR

[11] Jian, L., Zhao, Y., Hu, J., Li, P.: Distributed inexact consensus-based ADMM method for multi-agent unconstrained optimization problem. IEEE Access 7 (2019), 1, 79311-79319. | DOI

[12] Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (2003), 482-491. | DOI

[13] Liang, S., Zeng, X., Hong, Y.: Distributed nonsmooth optimization with coupled inequality constraints via modified lagrangian function. IEEE Trans. Automat. Control 63 (2018), 1753-1759. | DOI | MR

[14] Liang, S., Wang, L., Yin, G.: Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs. Automatica 101 (2019), 175-181. | DOI | MR

[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.: Convergence rate analysis of distributed optimization with projected subgradient algorithm. Automatica 83 (2017), 162-169. | DOI | MR

[18] Nedić, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control. 54 (2009), 48-61. | DOI | MR

[19] Nedić, A., Ozdaglar, A., Parrilo, P. A.: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control. 55 (2010), 922-938. | DOI | MR

[20] Nedić, A., Olshevsky, A.: Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Trans. Automat. Control 61 (2016), 3936-3947. | DOI | MR

[21] Nedić, A., Olshevsky, A., Shi, W.: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J. Optim. 27 (2017), 2597-2633. | DOI | MR

[22] Shi, G., Anderson, B. D., Helmke, U.: Network flows that solve linear equations. IEEE Trans. Automat. Control. 62 (2017), 2659-2674. | DOI | MR

[23] Shi, W., Ling, Q., Wu, G., Yin, W.: Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25 (2015), 944-966. | DOI | MR

[24] Tsianos, K. I., Lawlor, S., Rabbat, M. G.: Push-sum distributed dual averaging for convex optimization. In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) 2012, pp. 5453-5458. | DOI

[25] Tsianos, K. I., Rabbat, M. G.: Distributed dual averaging for convex optimization under communication delays. In: 2012 American Control Conference (ACC) 2012, pp. 1067-1072. | DOI

[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.: Distributed subgradient projection algorithm over directed graphs. IEEE Trans. Automat. Control 62 (2017), 3986-3992. | DOI | MR

[28] Xin, R., Xi, C., Khan, U. A.: Distributed Subgradient Projection Algorithm over Directed Graphs: Alternate Proof. arXiv preprint arXiv:1706.07707 (2017). | MR

[29] Xin, R., Xi, C., Khan, U. A.: FROST-Fast row-stochastic optimization with uncoordinated step-sizes. EURASIP J. Advances Signal Process. 1 (2019), 1-14. | DOI

[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). | MR

[31] Yi, P., Hong, Y., 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 | MR

[32] Yuan, D., Proutiere, A., Shi, G.: Distributed Online Linear Regression. arXiv preprint arXiv:1902.04774.

[33] Zeng, X., Yi, P., Hong, Y.: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2017), 5227-5233. | DOI | MR