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

Zeng, Xianlin   ; Cao, Kai

Kybernetika, Tome 53 (2017) no. 5, pp. 803-819

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2017-5-0803

Classification : 15A06, 93D20
Keywords: multi-agent network; distributed optimization; linear algebraic equation; least squares solution; solvability verification

Bibliographie

[1] Godsil, C., Royle, G. F.: Algebraic Graph Theory. Springer-Verlag, New York 2001. | DOI | MR | Zbl

[2] Haddad, W. M., Chellaboina, V.: Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach. Princeton University Press, New Jersey 2008. | MR | Zbl

[3] Hui, Q., Haddad, W. M., Bhat, S. P.: Semistability, finite-time stability, differential inclusions, and discontinuous dynamical systems having a continuum of equilibria. IEEE Trans. Automat. Control 54 (2009), 2465-2470. | DOI | MR

[4] Liu, Y., Lageman, C., Anderson, B., Shi, G.: An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations. arXiv:1701.03908v1.

[5] Liu, J., Morse, A. S., Nedic, A., Basar, T.: Exponential convergence of a distributed algorithm for solving linear algebraic equations. Automatica 83 (2017), 37-46. | DOI | MR

[6] Liu, J., Mou, S., Morse, A. S.: Asynchronous distributed algorithms for solving linear algebraic equations. IEEE Trans. Automat Control PP (2017), 99, 1-1. | DOI

[7] Mou, S., Liu, J., Morse, A. S.: A distributed algorithm for solving a linear algebraic equation. IEEE Trans. Automat. Control 60 (2015), 2863-2878. | DOI | MR

[8] Nedic, A., Ozdaglar, A., Parrilo, P. A.: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 922-938. | DOI | MR

[9] Ni, W., Wang, X.: Averaging approach to distributed convex optimization for continuous-time multi-agent systems. Kybernetika 52 (2016), 898-913. | DOI | MR

[10] Qiu, Z., Liu, S., Xie, L.: Distributed constrained optimal consensus of multi-agent systems. Automatica 68 (2016), 209-215. | DOI | MR

[11] Ruszczynski, A.: Nonlinear Optimization. Princeton University Press, New Jersey 2006. | MR

[12] Shi, G., Anderson, B. D. O.: Distributed network flows solving linear algebraic equations. In: American Control Conference, Boston 2016, pp. 2864-2869. | DOI

[13] Shi, G., Anderson, B. D. O., Helmke, U.: Network flows that solve linear equations. IEEE Trans. Automat. Control 62 (2017), 2659-2764. | DOI | MR

[14] Shi, G., Johansson, K. H.: Randomized optimal consensus of multi-agent systems. Automatica 48 (2012), 3018-3030. | DOI | MR

[15] Yi, P., Hong, Y., Liu, F.: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Systems Control Lett. 83 (2015), 45-52. | DOI | MR | Zbl

[16] Zeng, X., Hui, Q.: Energy-event-triggered hybrid supervisory control for cyber-physical network systems. IEEE Trans. Automat. Control 60 (2015), 3083-3088. | DOI | MR

[17] Zeng, X., Yi, P., Hong, Y.: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2017), 5227-5233. | DOI | MR