Distributed consensus-based multi-agent convex optimization via gradient tracking technique. (English) Zbl 1411.93012
Summary: This paper considers solving a class of optimization problems over a network of agents, in which the cost function is expressed as the sum of individual objectives of the agents. The underlying communication graph is assumed to be undirected and connected. A distributed algorithm in which agents employ time-varying and heterogeneous step-sizes is proposed by combining consensus of multi-agent systems with gradient tracking technique. The algorithm not only drives the agents’ iterates to a global and consensual minimizer but also finds the optimal value of the cost function. When the individual objectives are convex and smooth, we prove that the algorithm converges at a rate of \(O(1/\sqrt{t})\) if the homogeneous step-size does not exceed some upper bound, and it accelerates to \(O(1/t)\) if the homogeneous step-size is sufficiently small. When at least one of the individual objectives is strongly convex and all are smooth, we prove that the algorithm converges at a linear rate of \(O(\lambda^t)\) with \(0<\lambda<1\) even though the step-sizes are time-varying and heterogeneous. Two numerical examples are provided to demonstrate the efficiency of the proposed algorithm and to validate the theoretical findings.
MSC:
| 93A14 | Decentralized systems |
| 68T42 | Agent technology and artificial intelligence |
| 49N90 | Applications of optimal control and differential games |
References:
| [1] | Bliek, L.; Verstraete, H.; Verhaegen, M.; Wahls, S., Online optimization with costly and noisy measurements using random fourier expansions, IEEE Trans. Neural Netw. Learn. Syst., 29, 1, 167-182 (2018) |
| [2] | Dai, L.; Cao, Q.; Xia, Y.; Gao, Y., Distributed MPC for formation of multi-agent systems with collision avoidance and obstacle avoidance, J. Franklin Inst., 354, 4, 2068-2085 (2017) · Zbl 1378.93009 |
| [3] | S. Qin, X. Le, J. Wang, A neurodynamic optimization approach to bilevel quadratic programming, IEEE Trans. Neural Netw. Learn. Syst. doi:10.1109/TNNLS.2016.2595489; S. Qin, X. Le, J. Wang, A neurodynamic optimization approach to bilevel quadratic programming, IEEE Trans. Neural Netw. Learn. Syst. doi:10.1109/TNNLS.2016.2595489 |
| [4] | Chen, L.; Sun, J., Distributed optimal analysis for the multi-agent system with hybrid protocols, J. Franklin Inst., 354, 2, 1160-1168 (2017) · Zbl 1355.93009 |
| [5] | He, X.; Li, C.; Huang, T.; Li, C.; Huang, J., A recurrent neural network for solving bilevel linear programming problem, IEEE Trans. Neural Netw. Learn. Syst., 25, 4, 824-830 (2014) |
| [6] | Li, H.; Chen, G.; Huang, T.; Dong, Z., High-performance consensus control in networked systems with limited bandwidth communication and time-varying directed topologies, IEEE Trans. Neural Netw. Learn. Syst., 28, 5, 1043-1054 (2017) |
| [7] | Li, C.; Li, L., A distributed multiple dimensional QOS constrained resource scheduling optimization policy in computational grid, J. Comput. Syst. Sci. COMPU, 72, 4, 706-726 (2006) · Zbl 1101.68408 |
| [8] | Rabbat, M.; Nowak, R., Distributed optimization in sensor networks, Proceedings of the Third International Symposium on Information Processing in Sensor Networks, 20-27 (2004) |
| [9] | Dimakis, A.; Kar, S.; Moura, M.; Scaglione, A., Gossip algorithms for distributed signal processing, Proc. IEEE, 98, 11, 1847-1864 (2010) |
| [10] | Forero, P.; Cano, A.; Giannakis, G., Consensus-based distributed support vector machines, J. Mach. Learn. Res., 11, 1663-1707 (2010) · Zbl 1242.68222 |
| [11] | Bekkerman, R.; Bilenko, M.; Langford, J., Scaling up Machine Learning: Parallel and Distributed Approaches (2011), Cambridge University Press |
| [12] | Tsianos, K.; Lawlor, S.; Rabbat, M., Consensus-based distributed optimization: practical issues and applications in large-scale machine learning, Proceedings of 50th Annual Allerton Conference on Communication, Control, and Computing, 1543-1550 (2012) |
| [13] | Cevher, V.; Becker, S.; Schmidt, M., Convex optimization for big data: Scalable, randomized, and parallel algorithms for big data analytics, IEEE Signal Proc. Mag., 31, 5, 32-43 (2014) |
| [14] | Cai, K.; Ishii, H., Average consensus on arbitrary strongly connected digraphs with time-varying topologies, IEEE Trans. Autom. Control, 59, 4, 1066-1071 (2014) · Zbl 1360.93014 |
| [15] | Bazerque, J.; Giannakis, G., Distributed spectrum sensing for cognitive radio networks by exploiting sparsity, IEEE Trans. Signal Proces., 58, 3, 1847-1862 (2010) · Zbl 1392.94010 |
| [16] | Liu, L.; Shan, J., Distributed formation control of networked Euler-Lagrange systems with fault diagnosis, J. Franklin I., 352, 3, 952-973 (2017) · Zbl 1307.93032 |
| [17] | Gan, L.; Topcu, U.; Low, S., Optimal decentralized protocol for electric vehicle charging, IEEE Trans. Power Syst., 28, 2, 940-951 (2013) |
| [18] | Forero, P.; Cano, A.; Giannakis, G., Consensus-based distributed support vector machines, J. Mach. Learn. Res., 11, 1663-1707 (2010) · Zbl 1242.68222 |
| [19] | Nedíc, A.; Olshevsky, A.; Uribe, C., Fast convergence rates for distributed non-bayesian learning, IEEE Trans. Autom. Control, 62, 11, 5538-5553 (2017) · Zbl 1458.62116 |
| [20] | Tsitsiklis, J.; Bertsekas, D.; Athans, M., Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Autom. Control, 31, 9, 803-812 (1986) · Zbl 0602.90120 |
| [21] | Nedic, A.; Ozdaglar, A., Distributed subgradient methods for multiagent optimization, IEEE Trans. Autom. Control, 54, 1, 48-61 (2009) · Zbl 1367.90086 |
| [22] | Yuan, D.; Hong, Y.; Ho, D. W.C.; Jiang, G., Optimal distributed stochastic mirror descent for strongly convex optimization, Automatica, 90, 196-203 (2018) · Zbl 1387.93190 |
| [23] | Yuan, D.; Ho, D. W.C.; Xu, S., Regularized primal-dual subgradient method for distributed constrained optimization, IEEE Trans. Cybern., 46, 9, 2109-2118 (2016) |
| [24] | Ram, S.; Nedíc, A.; Veeravalli, V., Distributed stochastic subgradient projection algorithms for convex optimization, J. Optim. Theory App., 147, 3, 516-545 (2010) · Zbl 1254.90171 |
| [25] | Nedíc, A., Asynchronous broadcast-based convex optimization over a network, IEEE Trans. Autom. Control, 56, 6, 1337-1351 (2011) · Zbl 1368.90126 |
| [26] | Lobel, I.; Ozdaglar, A., Convergence analysis of distributed subgradient methods over random networks, Proceedings of 46th Annual Allerton Conference on Communication, Control, and Computing, IEEE, 353-360 (2008) |
| [27] | Duchi, J.; Agarwal, A.; Wainwright, M., Dual averaging for distributed optimization: convergence analysis and network scaling, IEEE Trans. Autom. Control, 57, 3, 592-606 (2012) · Zbl 1369.90156 |
| [28] | Nedíc, A.; Olshevsky, A., Distributed optimization over time-varying directed graphs, IEEE Trans. Autom. Control, 60, 3, 601-615 (2015) · Zbl 1360.90262 |
| [29] | Matei, I.; Baras, J., Performance evaluation of the consensus-based distributed subgradient method under random communication topologies, IEEE J. Sel. Topics Signal Process., 5, 4, 754-771 (2011) |
| [30] | Olshevsky, A., Linear time average consensus and distributed optimization on fixed graphs, SIAM J. Control Optim., 55, 6, 3990-4014 (2017) · Zbl 1386.93015 |
| [31] | Li, H.; Liao, X.; Chen, G.; Dong, Z.; Hill, D.; Huang, T., Event-triggered asynchronous intermittent communication strategy for synchronization in complex dynamical networks, Neural Netw., 66, 1-10 (2015) · Zbl 1396.93091 |
| [32] | Zhu, M.; Martínez, S., On distributed convex optimization under inequality and equality constraints, IEEE Trans. Autom. Control, 57, 1, 151-164 (2012) · Zbl 1369.90129 |
| [33] | Lobel, I.; Ozdaglar, A.; Feijer, D., Distributed multi-agent optimization with state-dependent communication, Math. Program., 129, 2, 255-284 (2011) · Zbl 1229.90201 |
| [34] | Chen, A.; Ozdaglar, A., A fast distributed proximal-gradient method, Proceedings of the 50th Annual Allerton Conference on Communication, Control, and Computing, 601-608 (2012) |
| [35] | Jakovetić, D.; Xavier, J.; Moura, J., Fast distributed gradient methods, IEEE Trans. Autom. Control, 59, 5, 1131-1146 (2014) · Zbl 1360.90292 |
| [36] | Sayed, A., Diffusion adaptation over networks, Academic Press Library in Signal Processing, 323-454 (2013) |
| [37] | Shi, W.; Ling, Q.; Wu, G.; Yin, W., A proximal gradient algorithm for decentralized composite optimization, IEEE Trans. Signal Proces., 63, 22, 6013-6023 (2015) · Zbl 1394.94531 |
| [38] | Shi, W.; Ling, Q.; Wu, G.; Yin, W., EXTRA: an exact first-order algorithm for decentralized consensus optimization, SIAM J. Optim., 25, 2, 944-966 (2015) · Zbl 1328.90107 |
| [39] | Yuan, K.; Ling, Q.; Yin, W., On the convergence of decentralized gradient descent, SIAM J. Optim., 26, 3, 1835-1854 (2016) · Zbl 1345.90068 |
| [40] | Xu, J.; Zhu, S.; Soh, Y.; Xie, L., Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes, Proceedings of the 54th IEEE Conference on Decision and Control, IEEE, 2055-2060 (2015) |
| [41] | Solmaz, K.; Cortés, J.; Martínez, S., Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication, Automatica, 55, 254-264 (2015) · Zbl 1377.93018 |
| [42] | Zhu, M.; Martínez, S., Discrete-time dynamic average consensus, Automatica, 46, 2, 322-329 (2010) · Zbl 1205.93014 |
| [43] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press: Cambridge University Press New York, NY · Zbl 1058.90049 |
| [44] | Qu, G.; Li, N., Harnessing smoothness to accelerate distributed optimization, IEEE Trans. Control Netw. Syst., 5, 3, 1245-1260 (2018) · Zbl 1515.93111 |
| [45] | Nedíc, A.; Olshevsky, A.; Shi, W.; Uribe, C. A., Geometrically convergent distributed optimization with uncoordinated step-sizes, Proceedings of the 2017 American Control Conference (2017) |
| [46] | Xiao, L.; Boyd, S., Fast linear iterations for distributed averaging, Syst. Control Lett., 53, 1, 65-78 (2004) · Zbl 1157.90347 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
