×

Distributed delay-tolerant strategies for equality-constraint sum-preserving resource allocation. (English) Zbl 1536.93037

Summary: This paper proposes two nonlinear dynamics to solve constrained distributed optimization problem for resource allocation over a multi-agent network. In this setup, coupling constraint refers to resource-demand balance which is preserved at all-times. The proposed solutions can address various model nonlinearities, for example, due to quantization and/or saturation. Further, it allows to reach faster convergence or to robustify the solution against impulsive noise or uncertainties. We prove convergence over weakly connected networks using convex analysis and Lyapunov theory. Our findings show that convergence can be reached for general sign-preserving odd nonlinearity. We further propose delay-tolerant mechanisms to handle general bounded heterogeneous time-varying delays over the communication network of agents while preserving all-time feasibility. This work finds application in CPU scheduling and coverage control among others. This paper advances the state-of-the-art by addressing (i) possible nonlinearity on the agents/links, meanwhile handling (ii) resource-demand feasibility at all times, (iii) uniform-connectivity instead of all-time connectivity, and (iv) possible heterogeneous and time-varying delays. To our best knowledge, no existing work addresses contributions (i)-(iv) altogether. Simulations and comparative analysis are provided to corroborate our contributions.

MSC:

93A16 Multi-agent systems
93B70 Networked control
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
93A14 Decentralized systems

Software:

GitHub

References:

[1] Doostmohammadian, M.; Aghasi, A.; Charalambous, T.; Khan, U. A., Distributed support vector machine over dynamic balanced directed networks. IEEE Control Syst. Lett., 758-763 (2021)
[2] Khan, U. A.; Bajwa, W. U.; Nedić, A.; Rabbat, M. G.; Sayed, A. H., Optimization for data-driven learning and control. Proc. IEEE, 11, 1863-1868 (2020)
[3] Molzahn, D. K.; Dörfler, F.; Sandberg, H.; Low, S. H.; Chakrabarti, S.; Baldick, R.; Lavaei, J., A survey of distributed optimization and control algorithms for electric power systems. IEEE Trans. Smart Grid, 6, 2941-2962 (2017)
[4] Yang, S.; Tan, S.; Xu, J., Consensus based approach for economic dispatch problem in a smart grid. IEEE Trans. Power Syst., 4, 4416-4426 (2013)
[5] C.N. Hadjicostis, T. Charalambous, Asynchronous coordination of distributed energy resources for the provisioning of ancillary services, in: 49th IEEE Allerton Conference on Communication, Control, and Computing, 2011, pp. 1500-1507.
[6] Cherukuri, A.; Cortés, J., Distributed generator coordination for initialization and anytime optimization in economic dispatch. IEEE Trans. Control Netw. Syst., 3, 226-237 (2015) · Zbl 1370.90304
[7] Wei, J.; Yi, X.; Sandberg, H.; Johansson, K. H., Nonlinear consensus protocols with applications to quantized communication and actuation. IEEE Trans. Control Netw. Syst., 2, 598-608 (2019) · Zbl 1515.93191
[8] Hadjicostis, C. N.; Vaidya, N. H.; Domínguez-García, A. D., Robust distributed average consensus via exchange of running sums. IEEE Trans. Automat. Control, 6, 1492-1507 (2016) · Zbl 1359.94979
[9] Parsegov, S. E.; Polyakov, A. E.; Shcherbakov, P. S., Fixed-time consensus algorithm for multi-agent systems with integrator dynamics. IFAC Proc. Vol., 27, 110-115 (2013)
[10] Garg, K.; Baranwal, M.; Hero, A. O.; Panagou, D., Fixed-time distributed optimization under time-varying communication topology (2019), arXiv preprint arXiv:1905.10472
[11] S.S. Stanković, M. Beko, M.S. Stanković, Robust Nonlinear Consensus Seeking, in: 58th IEEE Conference on Decision and Control, 2019, pp. 4465-4470.
[12] A. Agarwal, J.C. Duchi, Distributed delayed stochastic optimization, in: 51st IEEE Conference on Decision and Control, 2012, pp. 5451-5452.
[13] H. Al-Lawati, S.C. Draper, Gradient Delay Analysis in Asynchronous Distributed Optimization, in: IEEE International Conference on Acoustics, Speech and Signal Processing, 2020, pp. 4207-4211.
[14] Wang, D.; Wang, Z.; Chen, M.; Wang, W., Distributed optimization for multi-agent systems with constraints set and communication time-delay over a directed graph. Inform. Sci., 1-14 (2018) · Zbl 1440.68308
[15] Wang, X.; Hong, Y.; Sun, X.; Liu, K., Distributed optimization for resource allocation problems under large delays. IEEE Trans. Ind. Electron., 12, 9448-9457 (2019)
[16] Hu, C.; Wen, G.; Wang, S.; Fu, J.; Yu, W., Distributed multiagent reinforcement learning with action networks for dynamic economic dispatch. IEEE Trans. Neural Netw. Learn. Syst. (2023)
[17] Dai, P.; Yu, W.; Wen, G.; Baldi, S., Distributed reinforcement learning algorithm for dynamic economic dispatch with unknown generation cost functions. IEEE Trans. Ind. Inform., 4, 2258-2267 (2019)
[18] M. Doostmohammadian, A. Aghasi, M. Pirani, E. Nekouei, U.A. Khan, T. Charalambous, Fast-Convergent Anytime-Feasible Dynamics for Distributed Allocation of Resources Over Switching Sparse Networks with Quantized Communication Links, in: European Control Conference, 2022, pp. 84-89.
[19] A. Nedic, A. Olshevsky, A. Ozdaglar, J.N. Tsitsiklis, Distributed subgradient methods and quantization effects, in: 47th IEEE Conference on Decision and Control, 2008, pp. 4177-4184.
[20] Rikos, A. I.; Hadjicostis, C. N., Distributed average consensus under quantized communication via event-triggered mass splitting. IFAC-PapersOnLine, 2, 2957-2962 (2020)
[21] A.I. Rikos, T. Charalambous, K.H. Johansson, C.N. Hadjicostis, Privacy-Preserving Event-Triggered Quantized Average Consensus, in: 59th IEEE Conference on Decision and Control, 2020, pp. 6246-6253.
[22] Nekouei, E.; Alpcan, T.; Nair, G. N.; Evans, R. J., Convergence analysis of quantized primal-dual algorithms in network utility maximization problems. IEEE Trans. Control Netw. Syst., 1, 284-297 (2016) · Zbl 1507.93093
[23] Nekouei, E.; Nair, G. N.; Alpcan, T., Performance analysis of gradient-based nash seeking algorithms under quantization. IEEE Trans. Automat. Control, 12, 3771-3783 (2016) · Zbl 1359.91002
[24] Liu, Z.; Saberi, A.; Stoorvogel, A. A.; Nojavanzadeh, D., Global regulated state synchronization for homogeneous networks of non-introspective agents in presence of input saturation: Scale-free nonlinear and linear protocol designs. Automatica (2020) · Zbl 1451.93373
[25] Doostmohammadian, M., Single-bit consensus with finite-time convergence: Theory and applications. IEEE Trans. Aerosp. Electron. Syst., 4, 3332-3338 (2020)
[26] Chen, G.; Ren, J.; Feng, E. N., Distributed finite-time economic dispatch of a network of energy resources. IEEE Trans. Smart Grid, 2, 822-832 (2016)
[27] Ning, B.; Han, Q.; Zuo, Z., Distributed optimization for multiagent systems: An edge-based fixed-time consensus approach. IEEE Trans. Cybern., 1, 122-132 (2017)
[28] Wei, J.; Everts, A. R.F.; Camlibel, M. K.; van der Schaft, A. J., Consensus dynamics with arbitrary sign-preserving nonlinearities. Automatica, 226-233 (2017) · Zbl 1373.93036
[29] X. Wu, S. Magnusson, M. Johansson, A New Family of Feasible Methods for Distributed Resource Allocation, in: 60th IEEE Conference on Decision and Control, 2021, pp. 3355-3360.
[30] A.I. Rikos, A. Grammenos, E. Kalyvianaki, C.N. Hadjicostis, T. Charalambous, K.H. Johansson, Optimal CPU Scheduling in Data Centers via a Finite-Time Distributed Quantized Coordination Mechanism, in: 60th IEEE Conference on Decision and Control, 2021, pp. 6276-6281.
[31] Zhu, Y.; Ren, W.; Yu, W.; Wen, G., Distributed resource allocation over directed graphs via continuous-time algorithms. IEEE Trans. Syst. Man Cybern. Syst., 2, 1097-1106 (2019)
[32] N.S. Aybat, E. Yazdandoost Hamedani, Distributed primal-dual method for multi-agent sharing problem with conic constraints, in: 50th IEEE Asilomar Conference on Signals, Systems and Computers, 2016, pp. 777-782.
[33] Nedić, A.; Olshevsky, A.; Shi, W., Improved convergence rates for distributed resource allocation, 172-177
[34] G. Banjac, F. Rey, P. Goulart, J. Lygeros, Decentralized resource allocation via dual consensus ADMM, in: IEEE American Control Conference, 2019, pp. 2789-2794.
[35] Falsone, A.; Notarnicola, I.; Notarstefano, G.; Prandini, M., Tracking-ADMM for distributed constraint-coupled optimization. Automatica (2020) · Zbl 1441.93101
[36] Chang, T., A proximal dual consensus ADMM method for multi-agent constrained optimization. IEEE Trans. Signal Process., 14, 3719-3734 (2016) · Zbl 1414.94105
[37] Jiang, W.; Doostmohammadian, M.; Charalambous, T., Distributed resource allocation via ADMM over digraphs, 5645-5651
[38] Falsone, A.; Margellos, K.; Prandini, M., A distributed iterative algorithm for multi-agent MILPs: Finite-time feasibility and performance characterization. IEEE Control Syst. Lett., 4, 563-568 (2018)
[39] Aybat, N.; Yazdandoost Hamedani, E., A distributed ADMM-like method for resource sharing over time-varying networks. SIAM J. Optim., 4, 3036-3068 (2019) · Zbl 1427.90214
[40] Doostmohammadian, M.; Jiang, W.; Charalambous, T., DTAC-ADMM: Delay-tolerant augmented consensus ADMM-based algorithm for distributed resource allocation, 308-315
[41] S. Kar, G. Hug, Distributed robust economic dispatch in power systems: A consensus + innovations approach, in: IEEE Power and Energy Society General Meeting, 2012, pp. 1-8.
[42] Venkat, A. N.; Hiskens, I. A.; Rawlings, J. B.; Wright, S. J., Distributed MPC strategies with application to power system automatic generation control. IEEE Trans. Control Syst. Technol., 6, 1192-1206 (2008)
[43] M. Doostmohammadian, A. Aghai, A.I. Rikos, A. Grammenos, E. Kalyvianaki, C.N. Hadjicostis, K.H. Johansson, T. Charalambous, Distributed CPU Scheduling Subject to Nonlinear Constraints, in: IEEE Conference on Control Technology and Applications, pp. 746-751.
[44] Sayyaadi, H.; Moarref, M., A distributed algorithm for proportional task allocation in networks of mobile agents. IEEE Trans. Automat. Control, 2, 405-410 (2011) · Zbl 1368.90096
[45] Falsone, A.; Margellos, K.; Garatti, S.; Prandini, M., Dual decomposition for multi-agent distributed optimization with coupling constraints. Automatica, 149-158 (2017) · Zbl 1376.93005
[46] Xiao, L.; Boyd, S., Optimal scaling of a gradient method for distributed resource allocation. J. Optim. Theory Appl., 3, 469-488 (2006) · Zbl 1330.90136
[47] Yi, P.; Hong, Y.; Liu, F., Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems. Automatica, 259-269 (2016) · Zbl 1348.93024
[48] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679
[49] M. Doostmohammadian, A. Aghasi, M. Vrakopoulou, T. Charalambous, 1st-Order Dynamics on Nonlinear Agents for Resource Allocation over Uniformly-Connected Networks, in: IEEE Conference on Control Technology and Applications, 2022, pp. 1184-1189.
[50] Lakshmanan, H.; De Farias, D. P., Decentralized resource allocation in dynamic networks of agents. SIAM J. Optim., 2, 911-940 (2008) · Zbl 1176.90460
[51] Bertsekas, D. P., Necessary and sufficient conditions for a penalty method to be exact. Math. Progr., 1, 87-99 (1975) · Zbl 0325.90055
[52] Bertsekas, D. P.; Nedic, A.; Ozdaglar, A. E., Convexity, duality, and lagrange multipliers
[53] Nedić, A.; Olshevsky, A., Distributed optimization over time-varying directed graphs. IEEE Trans. Automat. Control, 3, 601-615 (2014) · Zbl 1360.90262
[54] Ren, W.; Beard, R. W., Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Trans. Automat. Control, 5, 655-661 (2005) · Zbl 1365.93302
[55] N.H. Vaidya, C.N. Hadjicostis, A.D. Dominguez-Garcia, Robust average consensus over packet dropping links: Analysis via coefficients of ergodicity, in: IEEE 51st IEEE Conference on Decision and Control, 2012, pp. 2761-2766.
[56] Olfati-Saber, R.; Murray, R. M., Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans. Automat. Control, 9, 1520-1533 (2004) · Zbl 1365.93301
[57] Gross, J. L.; Yellen, J., Handbook of Graph Theory (2004), CRC Press · Zbl 1036.05001
[58] H. Wang, P. Van Mieghem, Algebraic connectivity optimization via link addition, in: 3rd International Conference on Bio-Inspired Models of Network, Information and Computing Systems, 2008, pp. 1-8.
[59] Hadjicostis, C. N.; Charalambous, T., Average consensus in the presence of delays in directed graph topologies. IEEE Trans. Automat. Control, 3, 763-768 (2014) · Zbl 1360.93027
[60] Charalambous, T.; Yuan, Y.; Yang, T.; Pan, W.; Hadjicostis, C. N.; Johansson, M., Distributed finite-time average consensus in digraphs in the presence of time delays. IEEE Trans. Control Netw. Syst., 4, 370-381 (2015) · Zbl 1370.93169
[61] T. Charalambous, C.N. Hadjicostis, Average consensus in the presence of dynamically changing directed topologies and time delays, in: 53rd IEEE Conference on Decision and Control, 2014, pp. 709-714.
[62] K.I. Tsianos, M.G. Rabbat, Distributed consensus and optimization under communication delays, in: 49th Annual Allerton Conference on Communication, Control, and Computing, 2011, pp. 974-982.
[63] M. Maróti, B. Kusy, G. Simon, A. Lédeczi, The flooding time synchronization protocol, in: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, 2004, pp. 39-49.
[64] Berry, R. A.; Gallager, R. G., Communication over fading channels with delay constraints. IEEE Trans. Inform. Theory, 5, 1135-1149 (2002) · Zbl 1061.94501
[65] Gharesifard, B.; Cortés, J., Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Trans. Automat. Control, 3, 781-786 (2013) · Zbl 1360.90257
[66] E. Ghadimi, M. Johansson, I. Shames, Accelerated gradient methods for networked optimization, in: IEEE American Control Conference, 2011, pp. 1668-1673.
[67] Doan, T. T.; Olshevsky, A., Distributed resource allocation on dynamic networks in quadratic time. Systems Control Lett., 57-63 (2017) · Zbl 1353.93012
[68] T.T. Doan, C.L. Beck, Distributed Lagrangian methods for network resource allocation, in: IEEE Conference on Control Technology and Applications, CCTA, 2017, pp. 650-655.
[69] A. Kashyap, T. Basar, R. Srikant, Consensus with quantized information updates, in: 45th IEEE Conference on Decision and Control, 2006, pp. 2728-2733.
[70] Binazadeh, T.; Bahmani, M., Design of robust controller for a class of uncertain discrete-time systems subject to actuator saturation. IEEE Trans. Automat. Control, 3, 1505-1510 (2016) · Zbl 1366.93324
[71] Wang, Y.; Song, Y.; Hill, D. J.; Krstic, M., Prescribed-time consensus and containment control of networked multiagent systems. IEEE Trans. Cybern., 4, 1138-1147 (2019)
[72] T. Charalambous, C.N. Hadjicostis, M. Johansson, Distributed minimum-time weight balancing over digraphs, in: 6th International Symposium on Communications, Control and Signal Processing, 2014, pp. 190-193.
[73] Jurafsky, D.; Martin, J. H., Speech and Language Processing (2020), Prentice Hall
[74] Nesterov, Y., Introductory lectures on convex programming, Volume I: Basic course. Lect. Notes, 4, 5 (1998)
[75] Amjady, N.; Nasiri-Rad, H., Economic dispatch using an efficient real-coded genetic algorithm. IET Gener. Trans. Distrib., 3, 266-278 (2009)
[76] Wood, A. J.; Wollenberg, B. F.; Sheble, G. B., Power Generation Operation and Control (1996), John Wiley & Sons
[77] Reliability test system grid modernization lab consortium data (2022), https://github.com/GridMod/RTS-GMLC. Online; (Accessed 10 August 2022)
[78] Grammenos, A.; Charalambous, T.; Kalyvianaki, E., CPU scheduling in data centers using asynchronous finite-time distributed coordination mechanisms. IEEE Trans. Netw. Sci. Eng. (2023)
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.