Kybernetika 53 no. 5, 803-819, 2017

Computation of linear algebraic equations with solvability verification over multi-agent networks

Xianlin Zeng and Kai CaoDOI: 10.14736/kyb-2017-5-0803

Abstract:

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.

Keywords:

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

Classification:

15A06, 93D20

paper.pdf

References:

  1. C. Godsil and G. F. Royle: Algebraic Graph Theory. Springer-Verlag, New York 2001.   DOI:10.1007/978-1-4613-0163-9
  2. W. M. Haddad and V. Chellaboina: Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach. Princeton University Press, New Jersey 2008.   CrossRef
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. A. Ruszczynski: Nonlinear Optimization. Princeton University Press, New Jersey 2006.   CrossRef
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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