Article
Full entry |
PDF
(1.6 MB)
Feedback
PDF
(1.6 MB)
Feedback
Keywords:
multi-agent systems; distributed optimization; unbalanced graph; small gain theory; linear convergence rate
multi-agent systems; distributed optimization; unbalanced graph; small gain theory; linear convergence rate
Summary:
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.
References:
[1] Cai, K., Ishii, H.: Average consensus on general strongly connected digraphs. Automatica 48 (2012), 2750-2761. DOI 10.1016/j.automatica.2012.08.003 | MR 2981359 | Zbl 1252.93004
[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 10.1109/TAC.2014.2308612 | MR 3225227
[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 10.1137/15100463X | MR 3404682
[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 10.1109/TAC.2012.2219953 | MR 3029463
[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 10.1109/TAC.2011.2161027 | MR 2932818
[6] Gharesifard, B., Cortés, J.: Distributed strategies for generating weight-balanced and doubly stochastic digraphs. Europ. J. Control 18 (2012), 539-557. DOI 10.3166/EJC.18.539-557 | MR 3086897
[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 10.1109/TAC.2013.2278132 | MR 3188487
[8] Loh, H.: 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 | MR 0265219
[9] Halabian, H.: Distributed Resource Allocation Optimization in 5G Virtualized Networks. IEEE J. Selected Areas Commun. 37 (2019), 627-642. DOI 10.1109/JSAC.2019.2894305
[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 10.1002/oca.2538 | MR 4028355
[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 10.1109/ACCESS.2019.2923269
[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 10.1109/SFCS.2003.1238221
[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 10.1109/TAC.2017.2752001 | MR 3807659
[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 10.1016/j.automatica.2018.11.056 | MR 3891993
[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 10.1016/j.automatica.2017.06.011 | MR 3680426
[18] Nedić, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control. 54 (2009), 48-61. DOI 10.1109/TAC.2008.2009515 | MR 2478070
[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 10.1109/TAC.2010.2041686 | MR 2654432
[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 10.1109/TAC.2016.2529285 | MR 3582505
[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 10.1137/16M1084316 | MR 3738851
[22] Shi, G., Anderson, B. D., Helmke, U.: Network flows that solve linear equations. IEEE Trans. Automat. Control. 62 (2017), 2659-2674. DOI 10.1109/TAC.2016.2612819 | MR 3660554
[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 10.1137/14096668X | MR 3343366
[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 10.1109/CDC.2012.6426375
[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 10.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.: Distributed subgradient projection algorithm over directed graphs. IEEE Trans. Automat. Control 62 (2017), 3986-3992. DOI 10.1109/TAC.2016.2615066 | MR 3684332
[28] Xin, R., Xi, C., Khan, U. A.: Distributed Subgradient Projection Algorithm over Directed Graphs: Alternate Proof. arXiv preprint arXiv:1706.07707 (2017). MR 3684332
[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 10.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). MR 4047486
[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 10.1016/j.automatica.2016.08.007 | MR 3569392
[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 10.1109/TAC.2016.2628807 | MR 3708893
Search
Partner of
