Convergence Rate Optimization of a Distributed Algorithm for Solving Linear Equations Over Multi-Agent Networks

Öz

In this study, we investigate the problem of convergence rate optimization of an algorithm for solving linear equations over multi-agent systems. Each agent in the system is assumed to know only a subset of the linear equation system, and by using its local equation and the solution estimates of the neighboring agents, each agent updates its estimate and aims to compute the unique solution of the linear equation. We express the error dynamics of the agents as a linear dynamical system and relate the convergence speed of the optimization problem as the problem of minimizing the largest eigenvalue of the system matrix. By using a recently proposed metaheuristic optimization algorithm, Arithmetic Optimization Algorithm, the design parameters that provide the fastest solution have been determined. To examine the effect of the numbers of search agents and iterations on the performance of the optimization algorithm, simulation studies were repeated for different numbers of search agents and iterations. The results of the simulations are presented in a table. The evolution of the solution estimates of the agents is given for the design parameters that provide the fastest convergence.

Anahtar Kelimeler

• Optimization
• Distributed Algorithms
• Multi-agent systems

Çok Etmenli Sistemlerde Bir Dağıtık Denklem Çözüm Algoritmasının Yakınsama Hızı En İyilemesi

Öz

Bu çalışmada, çok etmenli bir ağ üzerinde tanımlanan ve doğrusal denklem sistemlerini çözmek için önerilen bir algoritmanın yakınsama hızının en iyilenmesi problemi ele alınmıştır. Sistemde bulunan her bir etmen, doğrusal denklem sisteminin yalnızca bir alt kümesini bilmekte; bu yerel denklem bilgisi ve komşu etmenlerin çözüm tahminlerini kullanarak kendi tahminlerini güncellemekte ve denklem sisteminin eşsiz çözümüne ulaşmayı amaçlamaktadırlar. Etmenlerin çözüm hatası dinamikleri bir doğrusal dinamik sistem olarak ifade edilerek yakınsama hızını en iyileme problemi, sistem matrisinin en büyük özdeğerini en küçükleme problemi olacak şekilde formüle edilmiştir. Literatürde yakın zamanda önerilmiş ve metasezgisel bir optimizasyon algoritması olan Aritmetik Optimizasyon Algoritması kullanılarak örnek bir denklem sisteminin en hızlı çözümünü sağlayan tasarım parametreleri belirlenmiştir. Arama ajanı ve yineleme sayılarının elde edilen en iyi hızlı yakınsama değerine etkisini incelemek amacıyla benzetim çalışmaları farklı sayıda arama ajanı ve maksimum yineleme sayısı için tekrarlanmış ve sonuçlar tablo halinde sunulmuştur. Elde edilen en hızlı yakınsamayı sağlayan tasarım parametreleri için etmenlerin çözüm tahminlerinin zamana bağlı değişimi verilmiştir.

Anahtar Kelimeler

• En iyileme
• Dağıtık algoritmalar
• Çok etmenli sistemler

Kaynakça

1. Abualigah, L., Diabat, A., Mirjalili, S., Abd Elaziz, M., & Gandomi, A. H. (2021). The Arithmetic Optimization Algorithm. Computer Methods in Applied Mechanics and Engineering, 376, 113609.
2. Anderson, J. (1995). Computational fluid dynamics: The basics with applications. Mc- Graw-Hill Education.
3. Anderson, B.D.O., Mou, S., Morse, A., & Helmke, U. (2016). Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control and Optimization, 6(3), 319-328.
4. Carpentieri, B., Duff, I. S., Giraud, L., & Magolu monga Made, M. (2004). Sparse symmetric preconditioners for dense linear systems in electromagnetism. Numerical Linear Algebra with Applications, 11(89), 753-771.
5. Cihan, O. (2019). Rapid Solution of Linear Equations with Distributed Algorithms over Networks. IFAC-PapersOnLine, 52(25), 467-471.
6. Cihan, O. (2020). Topology Design for Group Consensus in Directed Multi-Agent Systems, Kybernetika, 56(3), 578-597.
7. Cihan, O., & Akar, M. (2020a). Multi-consensus of second-order agents in discrete-time directed networks. International Journal of Systems Science, 51(10), 1847-1861.
8. Cihan, O., & Akar, M. (2020b). Necessary and Sufficient Conditions for Group Consensus of Agents With Third-Order Dynamics in Directed Networks. Journal of Dynamic Systems, Measurement, and Control, 142(4).

9. Frank, A., Fabregat-Traver, D., & Bientinesi, P. (2016). Large-scale linear regression: Development of high-performance routines. Applied Mathematics and Computation, 275, 411-421.
10. Hackbusch, W. (1994). Iterative solution of large sparse systems of equations: Vol. 95. Springer.
11. Krstic, M., & Smyshlyaev, A. (2008). Boundary control of PDEs: A course on backstepping designs: Vol. 16. SIAM.
12. Mirjalili, S. (2016). SCA: A Sine Cosine Algorithm for solving optimization problems. Knowledge-Based Systems, 96, 120-133.
13. Mou, S., Liu, J., & Morse, A. S. (2015). A Distributed Algorithm for Solving a Linear Algebraic Equation. IEEE Transactions on Automatic Control, 60(11), 2863-2878.
14. Pasqualetti, F., Carli, R., & Bullo, F. (2012). Distributed estimation via iterative projections with application to power network monitoring. Automatica, 48(5), 747-758.
15. Rahola, J. (1996). Solution of dense systems of linear equations in the discrete-dipole approximation. SIAM Journal on Scientific Computing, 17(1), 78-89.
16. Silvestre, D., Hespanha, J., & Silvestre, C. (2018). A pagerank algorithm based on asynchronous Gauss–Seidel iterations. In 2018 annual American control conference (pp. 484-489).
17. Stott, B., Jardim, J., & Alsac, O. (2009). DC power flow revisited. IEEE Transactions on Power Systems, 24(3), 1290-1300.
18. Wang, L., Fullmer, D., & Morse, A. S. (2016). A distributed algorithm with an arbitrary initialization for solving a linear algebraic equation. In 2016 American control conference (pp. 1078-1081).
19. Wang, P., Lin, P., Ren, W., & Song, Y. (2018). Distributed subgradient-based multiagent optimization with more general step sizes. IEEE Transactions on Automatic Control, 63(7), 2295-2302.
20. Wang, P., Mou, S., Lian, J., & Ren, W. (2019). Solving a system of linear equations: From centralized to distributed algorithms. Annual Reviews in Control, 47, 306-322.
21. Wang, P., Ren, W., & Duan, Z. (2019). Distributed Algorithm to Solve a System of Linear Equations With Unique or Multiple Solutions From Arbitrary Initializations. IEEE Transactions on Control of Network Systems, 6(1), 82-93.
22. You, K., Song, S., & Tempo, R. (2016). A networked parallel algorithm for solving linear algebraic equations. In 2016 IEEE 55th conference on decision and control (pp. 1727-1732).