Cooperative convex optimization with subgradient delays using push-sum distributed dual averaging. (English) Zbl 1471.93024
Summary: In this paper, we address the distributed convex optimization problems for multi-agent systems. In our research, it is assumed that each agent in the multi-agent system could merely interact with its neighbors via a directed graph and is available to its own cost function. We then utilize the push-sum distributed dual averaging (PS-DDA) algorithm to tackle with the distributed optimization problem. However, we consider that there exist subgradient delays in PS-DDA algorithm. The proof of the main result which shows that the PS-DDA algorithm with subgradient delays converges and the error possesses sublinear growth of a rate \(\mathcal{O}(\tau^2T^{-0.5})\), where \(T\) denotes the total amount of iterations, is detailed presented in this paper. Finally, a numerical example is simulated to show the performance of the algorithm we study in this paper.
References:
| [1] | Wang, H.; Liao, X.; Huang, T.; Li, C., Cooperative distributed optimization in multiagent networks with delays, IEEE Trans. Syst. Man Cybern., 45, 363-369 (2015) |
| [2] | Liu, S.; Chen, P.; Hero, A. O., Accelerated distributed dual averaging over evolving networks of growing connectivity, IEEE Trans. Signal Process., 66, 1845-1859 (2018) · Zbl 1414.94958 |
| [3] | Mateos-Nunez, D.; Corts, J., Distributed saddle-point subgradient algorithms with Laplacian averaging, IEEE Trans. Autom. Control, 62, 2720-2735 (2017) · Zbl 1369.90193 |
| [4] | Juelsgaard, M.; Wisniewski, R.; Bendtsen, J., Fault tolerant distributed portfolio optimization in smart grids, Int. J. Robust Nonlinear Control, 24, 4246-4260 (2014) · Zbl 1291.93106 |
| [5] | Lin, W.; Wang, Y.; Li, C.; Yu, X., Predefined-time optimization for distributed resource allocation, J. Frankl. Inst., 357, 11323-11348 (2020) · Zbl 1450.91017 |
| [6] | Tao, W.; Pan, Z.; Wu, G.; Tao, Q., Primal averaging: a new gradient evaluation step to attain the optimal individual convergence, IEEE Trans. Cybern., 50, 835-845 (2020) |
| [7] | Liang, S.; Wang, L.; Yin, G., Distributed continuous-time algorithm for nonsmooth optimal consensus without sharing local decision variables, J. Frankl. Inst., 357, 3585-3600 (2020) · Zbl 1437.93120 |
| [8] | Nedic, A.; Ozdaglar, A.; Parrilo, P. A., Constrained consensus and optimization in multi-agent networks, IEEE Trans. Autom. Control, 55, 922-938 (2010) · Zbl 1368.90143 |
| [9] | Nedic, A.; Ozdaglar, A., Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control, 54, 48-61 (2009) · Zbl 1367.90086 |
| [10] | Nedic, A.; Olshevsky, A., Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Trans. Autom. Control, 61, 3936-3947 (2016) · Zbl 1359.90142 |
| [11] | Wang, Q.; Chen, J.; Zeng, X.; Xin, B., Distributed proximal-gradient algorithms for nonsmooth convex optimization of second-order multiagent systems, Int. J. Robust Nonlinear Control, 30, 7574-7592 (2020) · Zbl 1525.93013 |
| [12] | Yi, P.; Hong, Y.; Liu, F., Distributed gradient algorithm for constrained optimization with application to load sharing in power systems, Syst. Control Lett., 83, 45-52 (2015) · Zbl 1327.93033 |
| [13] | Li, H.; Zhang, H.; Wang, Z.; Zhu, Y.; Han, Q., Distributed consensus-based multi-agent convex optimization via gradient tracking technique, J. Frankl. Inst., 356, 3733-3761 (2019) · Zbl 1411.93012 |
| [14] | Yuan, D.; Xu, S.; Zhao, H., Distributed primal-dual subgradient method for multiagent optimization via consensus algorithms, IEEE Trans. Syst. Man Cybern. Part B, 41, 1715-1724 (2011) |
| [15] | Niu, Y.; Wang, H.; Wang, Z.; Xia, D.; Li, H., Primal-dual stochastic distributed algorithm for constrained convex optimization, J. Frankl. Inst., 356, 9763-9787 (2019) · Zbl 1452.90245 |
| [16] | Nedic, A.; Olshevsky, A., Distributed optimization over time-varying directed graphs, IEEE Trans. Autom. Control, 60, 601-615 (2015) · Zbl 1360.90262 |
| [17] | Tsianos, K. I.; Lawlor, S.; Rabbat, M. G., Push-sum distributed dual averaging for convex optimization, Proc. 51st IEEE Conf. Decis. Control, Maui, Hawaii, 5453-5458 (2012) |
| [18] | Yuan, D.; Xu, S.; Lu, J., Gradient-free method for distributed multi-agent optimization via push-sum algorithms, Int. J. Robust Nonlinear Control, 25, 1569-1580 (2015) · Zbl 1317.93273 |
| [19] | Liang, S.; Wang, L. Y.; Yin, G., Dual averaging push for distributed convex optimization over time-varying directed graph, IEEE Trans. Autom. Control, 65, 1785-1791 (2020) · Zbl 07256302 |
| [20] | Gu, C.; Li, J.; Wu, Z., An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs, J. Frankl. Inst., 356, 7548-7570 (2019) · Zbl 1418.93117 |
| [21] | Yuan, D.; Ho, D. W.C.; Xu, S., Inexact dual averaging method for distributed multi-agent optimization, Syst. Control Lett., 71, 23-30 (2014) · Zbl 1296.93013 |
| [22] | Yuan, D.; Xu, S.; Zhao, H.; Rong, L., Distributed dual averaging method for multi-agent optimization with quantized communication, Syst. Control Lett., 61, 1053-1061 (2012) · Zbl 1252.93008 |
| [23] | Tsianos, K. I.; Rabbat, M. G., Distributed consensus and optimization under communication delays, 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, 974-982 (2011) |
| [24] | Tsianos, K. I.; Rabbat, M. G., Distributed dual averaging for convex optimization under communication delays, 2012 American Control Conference (ACC), Montreal, QC, 1067-1072 (2012) |
| [25] | Wang, J.; Ru, T.; Xia, J.; Shen, H.; Sreeram, V., Asynchronous event-triggered sliding mode control for semi-Markov jump systems within a finite-time interval, IEEE Trans. Circuits Syst. I, 68, 458-468 (2021) |
| [26] | Agarwal, A.; Duchi, J. C., Distributed delayed stochastic optimization, 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), Maui, HI, 5451-5452 (2012) |
| [27] | Li, J.; Chen, G.; Dong, Z.; Wu, Z., Distributed mirror descent method for multi-agent optimization with delay, Neurocomputing, 177, 643-650 (2016) |
| [28] | Duchi, J. C.; Agarwal, A.; Wainwright, M. J., Dual averaging for distributed optimization: convergence analysis and network scaling, IEEE Trans. Autom. Control, 57, 592-606 (2012) · Zbl 1369.90156 |
| [29] | Coucheney, P.; Gaujal, B.; Mertikopoulos, P., Distributed optimization in multi-user MIMO systems with imperfect and delayed information, 2014 IEEE International Symposium on Information Theory, Honolulu, HI, 3097-3101 (2014) |
| [30] | Wang, D.; Chen, F.; Meng, B.; Hu, X.; Wang, J., Event-based secure \(\operatorname{H}_\infty\) load frequency control for delayed power systems subject to deception attacks, Appl. Math. Comput., 394, 125788 (2021) · Zbl 1508.93089 |
| [31] | Yuan, Y.; Li, H.; Hu, J.; Wang, Z., Stochastic gradient-push for economic dispatch on time-varying directed networks with delays, Int. J. Electr. Power Energy Syst., 113, 564-572 (2019) |
| [32] | Wang, X.; Hong, Y.; Sun, X.; Liu, K., Distributed optimization for resource allocation problems under large delays, IEEE Trans. Ind. Electron., 66, 9448-9457 (2019) |
| [33] | Guo, Z.; Chen, G., Distributed zero-gradient-sum algorithm for convex optimization with time-varying communication delays and switching networks, Int. J. Robust Nonlinear Control, 28, 4900-4915 (2018) · Zbl 1403.93014 |
| [34] | Liu, Y.; Tang, S.; Liu, Y.; Kong, Q.; Wang, J., Extended dissipative sliding mode control for nonlinear networked control systems via event-triggered mechanism with random uncertain measurement, Appl. Math. Comput., 396, 125901 (2021) · Zbl 1508.93306 |
| [35] | Lin, P.; Ren, W.; Song, Y., Distributed multi-agent optimization subject to nonidentical constraints and communication delays, Automatica, 65, 120-131 (2016) · Zbl 1328.93024 |
| [36] | Zhang, H.; Li, H.; Zhu, Y.; Wang, Z.; Xia, D., A distributed stochastic gradient algorithm for economic dispatch over directed network with communication delays, Int. J. Electr. Power Energy Syst., 110, 759-771 (2019) |
| [37] | Bregman, L., The relaxation method of finding the common point of sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys., 7, 200-217 (1967) · Zbl 0186.23807 |
| [38] | P. Tseng, On accelerated proximal gradient methods for convex-concave optimization [online], 2008. Available: http://www.mit.edu/dimitrib/PTseng/papers/apgm.pdf. |
| [39] | Fill, J. A., Eigenvalue bounds on convergence to stationarity for non reversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab., 1, 62-87 (1991) · Zbl 0726.60069 |
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.
