In this paper, we consider the problem of solving a linear algebraic equation $Ax=b$ in a distributed way by a multi-agent system with a solvability verification requirement. In the problem formulation, each agent knows a few columns of $A$, different from the previous results with assuming that each agent knows a few rows of $A$ and $b$. Then, a distributed continuous-time algorithm is proposed for solving the linear algebraic equation from a distributed constrained optimization viewpoint. The algorithm is proved to have two properties: firstly, the algorithm converges to a least squares solution of the linear algebraic equation with any initial condition; secondly, each agent in the algorithm knows the solvability property of the linear algebraic equation, that is, each agent knows whether the obtained least squares solution is an exact solution or not.

distributed optimization, multi-agent network, linear algebraic equation, least squares solution, solvability verification

15A06, 93D20

- C. Godsil and G. F. Royle: Algebraic Graph Theory. Springer-Verlag, New York 2001. DOI:10.1007/978-1-4613-0163-9
- W. M. Haddad and V. Chellaboina: Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach. Princeton University Press, New Jersey 2008. CrossRef
- Q. Hui, W. M. Haddad and S. P. Bhat: Semistability, finite-time stability, differential inclusions, and discontinuous dynamical systems having a continuum of equilibria. IEEE Trans. Automat. Control 54 (2009), 2465-2470. DOI:10.1109/tac.2009.2029397
- Y. Liu, C. Lageman, B. Anderson and G. Shi: An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations. arXiv:1701.03908v1. CrossRef
- J. Liu, A. S. Morse, A. Nedic and T. Basar: Exponential convergence of a distributed algorithm for solving linear algebraic equations. Automatica 83 (2017), 37-46. DOI:10.1016/j.automatica.2017.05.004
- J. Liu, S. Mou and A. S. Morse: Asynchronous distributed algorithms for solving linear algebraic equations. IEEE Trans. Automat Control PP (2017), 99, 1-1. DOI:10.1109/TAC.2017.2714645
- S. Mou, J. Liu and A. S. Morse: A distributed algorithm for solving a linear algebraic equation. IEEE Trans. Automat. Control 60 (2015), 2863-2878. DOI:10.1109/tac.2015.2414771
- A. Nedic, A. Ozdaglar and P. A. Parrilo: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 922-938. DOI:10.1109/tac.2010.2041686
- W. Ni and X. Wang: Averaging approach to distributed convex optimization for continuous-time multi-agent systems. Kybernetika 52 (2016), 898-913. DOI:10.14736/kyb-2016-6-0898
- Z. Qiu, S. Liu and L. Xie: Distributed constrained optimal consensus of multi-agent systems. Automatica 68 (2016), 209-215. DOI:10.1016/j.automatica.2016.01.055
- A. Ruszczynski: Nonlinear Optimization. Princeton University Press, New Jersey 2006. CrossRef
- G. Shi and B. D. O. Anderson: Distributed network flows solving linear algebraic equations. In: American Control Conference, Boston 2016, pp. 2864-2869. DOI:10.1109/acc.2016.7525353
- G. Shi, B. D. O. Anderson and U. Helmke: Network flows that solve linear equations. IEEE Trans. Automat. Control 62 (2017), 2659-2764. DOI:10.1109/tac.2016.2612819
- G. Shi and K. H. Johansson: Randomized optimal consensus of multi-agent systems. Automatica 48 (2012), 3018-3030. DOI:10.1016/j.automatica.2012.08.018
- P. Yi, Y. Hong and F. Liu: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Systems Control Lett. 83 (2015), 45-52. DOI:10.1016/j.sysconle.2015.06.006
- X. Zeng and Q. Hui: Energy-event-triggered hybrid supervisory control for cyber-physical network systems. IEEE Trans. Automat. Control 60 (2015), 3083-3088. DOI:10.1109/tac.2015.2409900
- X. Zeng, P. Yi and Y. Hong: 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