# Distributed least square approach for solving a multiagent linear algebraic
equation

Viet Hoang Pham1 and Hyo-Sung Ahn1 1School of Mechanical Engineering, Gwangju
Institute of Science and Technology, Gwangju, Korea. E-mails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper considers a linear algebraic equation over a multiagent network.
The coefficient matrix is partitioned into multiple blocks; each agent only
knows a subset of these blocks in different row and column partitions. Based
on a proximal ADMM algorithm, we design a distributed method for every agent
to find its corresponding parts in one least square solution of the considered
linear algebraic equation. Each agent uses only its information and
communicates with its neighbors. We show that the designed method achieves an
exponentially fast convergence for an arbitrarily initial setup. Numerical
simulations in MATLAB are provided to verify the effectiveness of the designed
method.

##  I Introduction

The control and optimization problems of multiagent systems have become
popular in many applications. The main reason is inherent complexity of large-
scale problems and memory dispersion with the growth of big data. Depending on
the communication network among agents, a multiagent system can have a
hierarchical or distributed scheme. In a hierarchical setup, one master agent
plays as a coordinator. This agent communicates with and/or assigns tasks to
all others. In a distributed setup, agents work in parallel, and each agent
can exchange information with only its neighbors. Because of the scalability
and privacy protection requirements, distributed ones have become more desired
recently.

Many fundamental problems in various engineering applications can be deduced
into solving a linear algebraic equation $\textbf{H}\textbf{z}=\textbf{h}$
where H and h are coefficient matrix and vector. Various distributed methods
have been developed to find the solution of $\textbf{H}\textbf{z}=\textbf{h}$
when each agent knows only a subset of rows in H and h. The first approach
considers constrained consensus problems [1, 2, 3, 4, 5, 6, 7]. By using an
orthogonal projection of the kernel of the local coefficient matrix, the
estimated solution at every iteration of each agent always satisfies its
linear equations. Distributed consensus schemes are exploited to drive
estimated solutions of all agents to converge to an agreement. The methods in
[1, 2, 3, 4, 6, 5] are discrete-time, and the one in [7] is continuous-time.
The convergence of these methods is guaranteed if the considered linear
algebraic equation has at least one exact solution.

Another approach considers the problem of solving a distributed linear
algebraic equation as finding the optimal solution of a multiagent
optimization problem [5, 8, 9, 10, 11, 12]. The local cost function in each
agent is the total square error of its local linear equations, and the
constraints are added to force the agreement for estimated solutions among
neighboring agents. Various distributed optimization algorithms, such as
subgradient-based methods [13, 14], and ADMM [15, 16], can be applied to solve
the optimization problem. When the considered linear algebraic equation has
one or several exact solutions, all agents can asymptotically determine one of
such points [12]. If the exact solution does not exist, the final converged
solution is one least square solution, which minimizes the total square
errors, of the considered linear algebraic equation [5, 8, 9, 10, 11].

In the works mentioned above [1, 2, 3, 4, 5, 6, 7, 12, 8, 9, 10, 11], the
authors consider a distributed linear algebraic equation
$\textbf{H}\textbf{z}=\textbf{h}$ assuming that the coefficient matrix H is
divided into multiple row partitions and each agent knows one of these
partitions. Consequently, in their proposed algorithm, except for the one in
[2], every agent controls a state vector having the same dimension as the
unknown vector z in its update. In [2], the dimension of the state vector
controlled by one agent can be reduced when considering the sparsity in its
row partition. Different from [1, 2, 3, 4, 5, 6, 7, 12, 8, 9, 10, 11], the
authors in [17] assume that the coefficient matrix H is first divided into
either multiple row partitions or column partitions. Then, each of these
partitions is further divided into multiple blocks. Only one agent can access
each block. These setups are more suitable than those in [1, 2, 3, 4, 5, 6, 7,
12, 8, 9, 10, 11] when the coefficient matrix H has large rows and columns.
However, the algorithms proposed in [17] require a hierarchical structure.
Each agent is in only one cluster corresponding to one row or column
partition. Each cluster has one aggregator to collect information on agents in
this cluster and exchange information with aggregators of others.

This paper considers a linear algebraic equation
$\textbf{H}\textbf{z}=\textbf{h}$ when the rows and columns of the coefficient
matrix H are distributed over a network of agents. Let the matrix H be divided
into multiple blocks. Each agent only knows a subset of the divided blocks,
which can be located in many row and column partitions. Unlike [17], we do not
require an aggregator to collect information from agents corresponding to the
same row or column partition. For the row partitions whose data are dispensed
across multiple agents, we introduce some virtual variables to transform their
linear equations into local constraints of individual agents combining
coupling constraints among neighboring agents. Consequently, we obtain a
distributed optimization problem whose optimal solution is one least square
solution of the considered linear algebraic equation. Then we apply a proximal
ADMM algorithm [15] to design a distributed method for finding the optimal
solution of the obtained distributed optimization problem. Each agent must
only use its information and communicate with its neighbors. Since the
designed method is discrete-time, the asymptotic convergence of the ADMM-based
method implies the exponential convergence of the estimated solution to the
optimal one. In addition, our designed method has no requirements for step-
size selection or initial point setup.

The remainder of the paper is organized as follows. Section II provides some
preliminaries for the analysis in later sections. In Section III, we introduce
distributed linear algebraic equation setup and optimization-based approach.
Then we formulate a distributed optimization problem whose optimal solution
can be used to determine the least square solution of the considered linear
algebraic equation in Section IV. Based on a proximal ADMM algorithm [15],
Section V designs a distributed method for solving the optimization problem
formulated in Section IV. Numerical simulations are provided in Section VI to
illustrate the effectiveness of the designed method. Section VII concludes
this paper.

##  II Preliminaries

###  II-A Notations

We use $\mathbb{R},\mathbb{R}^{n}$, and $\mathbb{R}^{m\times n}$ to denote the
set of real numbers, the set of $n$-dimension real vectors, and the set of
real matrices having $m$ rows and $n$ columns. Denote by $\textbf{1}_{n}$ and
$\textbf{0}_{n}$ the vectors in $\mathbb{R}^{n}$ whose all elements are $1$
and $0$, respectively. Let $\textbf{I}_{n}$ be the identity matrix in
$\mathbb{R}^{n\times n}$ and $\textbf{0}_{m\times n}$ be the zero matrix in
$\mathbb{R}^{m\times n}$. When the dimensions are clear, the subscripts of the
matrices $\textbf{I}_{n},\textbf{0}_{m\times n}$, and the vector
$\textbf{1}_{n},\textbf{0}_{n}$ can be removed. Denote by $\textbf{H}^{T}$ the
transpose matrix of H. We write $\textbf{H}\succ 0$ ($\succeq 0$) means H is a
positive (semi-)definite matrix. Define
$||\textbf{x}||_{\textbf{H}}^{2}=\textbf{x}^{T}\textbf{H}\textbf{x}$. When
$\textbf{H}=\textbf{I}$, we write it as $||\textbf{x}||^{2}$ for simplicity.
If $x$ is a scalar, we write $|x|=||x||$. We use $|\mathbb{S}|$ to denote the
cardinality of the set $\mathbb{S}$.

Let
$\mathcal{H}=\left\\{\textbf{h}_{1},\textbf{h}_{2},\dots,\textbf{h}_{m}\right\\}$
be the list of $m$ vectors, we define the column vector

$\textrm{col
}\mathcal{H}=\textrm{col}\left\\{\textbf{h}_{1},\textbf{h}_{2},\dots,\textbf{h}_{m}\right\\}=\left[\textbf{h}_{1}^{T},\textbf{h}_{2}^{T},\dots,\textbf{h}_{m}^{T}\right]^{T}.$

For a list of matrices,
$\mathcal{H}=\left\\{\textbf{H}_{1},\textbf{H}_{2},\dots,\textbf{H}_{m}\right\\}$,
we use $\textrm{blkdiag }\mathcal{H}$ to denote the block-diagonal matrix
whose main blocks are matrices in the set $\mathcal{H}$. In addition, we
define two matrices

$\textrm{blkcol
}\mathcal{H}=\textrm{blkcol}\left\\{\textbf{H}_{1},\textbf{H}_{2},\dots,\textbf{H}_{m}\right\\}=\left[\begin{matrix}\textbf{H}_{1}^{T}&\textbf{H}_{2}^{T}&\cdots&\textbf{H}_{m}^{T}\end{matrix}\right]^{T},$
$\textrm{blkrow
}\mathcal{H}=\textrm{blkrow}\left\\{\textbf{H}_{1},\textbf{H}_{2},\dots,\textbf{H}_{m}\right\\}=\left[\begin{matrix}\textbf{H}_{1}&\textbf{H}_{2}&\cdots&\textbf{H}_{m}\end{matrix}\right].$

###  II-B Proximal ADMM Algorithm

Consider the following convex optimization problem

$\min\limits_{\textbf{x}\in\mathcal{X},\textbf{y}\in\mathcal{Y}}\textrm{
}\Psi_{x}(\textbf{x})+\Psi_{y}(\textbf{y})\textrm{ s.t.
}\textbf{F}_{x}\textbf{x}+\textbf{F}_{y}\textbf{y}=\textbf{f}.$ (1)

where $\Psi_{x}(\textbf{x}),\Psi_{y}(\textbf{y})$ are convex functions,
$\mathcal{X},\mathcal{Y}$ are convex sets, $\textbf{F}_{x},\textbf{F}_{y}$ and
f are known matrices and vector. The augmented Lagrangian function associated
to the problem (1) is defined as

$\mathcal{L}_{\rho}(\textbf{x},\textbf{y},\bm{\lambda})=\Psi_{x}(\textbf{x})+\Psi_{y}(\textbf{y})+\frac{\rho}{2}\Bigl{|}\Bigl{|}\textbf{F}_{x}\textbf{x}+\textbf{F}_{y}\textbf{y}-\textbf{f}-\frac{1}{\rho}\bm{\lambda}\Bigr{|}\Bigr{|}^{2}$

where $\bm{\lambda}$ is the dual variable corresponding to the equality
constraint in (1) and $\rho>0$ is a positive penalty parameter. The proximal
ADMM algorithm proposed in [15] for solving the convex optimization problem
(1) is given as follows.

$\displaystyle\textbf{x}(s+1)$
$\displaystyle=\arg\min\limits_{\textbf{x}\in\mathcal{X}}\Bigl{\\{}\mathcal{L}_{\rho}(\textbf{x},\textbf{y}(s),\bm{\lambda}(s))+\frac{1}{2}\left|\left|\textbf{x}-\textbf{x}(s)\right|\right|_{\textbf{G}}^{2}\Bigr{\\}},$
(2a) $\displaystyle\textbf{y}(s+1)$
$\displaystyle=\arg\min\limits_{\textbf{y}\in\mathcal{Y}}\mathcal{L}_{\rho}(\textbf{x}(s+1),\textbf{y},\bm{\lambda}(s)),$
(2b) $\displaystyle\bm{\lambda}(s+1)$
$\displaystyle=\bm{\lambda}(s)-\rho\Bigl{(}\textbf{F}_{x}\textbf{x}(s+1)+\textbf{F}_{y}\textbf{y}(s+1)-\textbf{f}\Bigr{)},$
(2c)

where G is a symmetric and positive semidefinite matrix, and the initial point
$(\textbf{x}(0),\textbf{y}(0),\bm{\lambda}(0))$ can be chosen arbitrarily such
that $\textbf{x}(0)\in\mathcal{X},\textbf{y}(0)\in\mathcal{Y}$. The following
theorem is Lemma 1 in [16], which is based on the convergence result of the
proximal ADMM algorithm (2) in [15].

###### Theorem 1

Let
$\bm{\Theta}=blkdiag\left\\{\textbf{G},\rho\textbf{F}_{y}^{T}\textbf{F}_{y},\frac{1}{\rho}\textbf{I}\right\\}$
and
$\textbf{w}(s)=[\textbf{x}(s)^{T},\textbf{y}(s)^{T},\bm{\lambda}(s)^{T}]^{T}$.
Then we have

  1. 1.

$||\textbf{w}(s)-\textbf{w}(s+1)||_{\bm{\Theta}}^{2}=o\left(\frac{1}{s}\right)$

  2. 2.

$||\textbf{F}_{x}\textbf{x}(s)+\textbf{F}_{y}\textbf{y}(s)-\textbf{f}||=o\left(\frac{1}{\sqrt{s}}\right)$

  3. 3.

$|\Psi_{x}(\textbf{x}(s))+\Psi_{y}(\textbf{y}(s))-\psi^{opt}|=o\left(\frac{1}{\sqrt{s}}\right)$
where $\psi^{opt}$ is the optimal value of the cost function in (1).

##  III Problem Formulation

###  III-A Distributed linear algebraic equation

Consider a linear algebraic equation

$\textbf{H}\textbf{z}=\textbf{h},$ (3)

where $\textbf{z}\in\mathbb{R}^{n}$ is unknown vector,
$\textbf{H}\in\mathbb{R}^{m\times n}$ and $\textbf{h}\in\mathbb{R}^{m}$ are
coefficients matrix and vector, respectively. Let $\textbf{z}^{opt}$ be one
least square solution to (3). Then $\textbf{z}^{opt}$ is one optimal solution
to the following optimization problem.

$\min_{\textbf{z}}\frac{1}{2}\bigl{|}\bigl{|}\textbf{H}\textbf{z}-\textbf{h}\bigr{|}\bigr{|}^{2}.$
(4)

In general, the linear algebraic equation (3) can have one or more least
square solutions. Define
$\Psi^{opt}=\frac{1}{2}||\textbf{H}\textbf{z}^{opt}-\textbf{h}||^{2}$. We have
$\Psi^{opt}=0$ if the linear algebraic equation (3) has at least one exact
solution. If H is a full column rank matrix, we have
$\textbf{z}^{opt}=(\textbf{H}^{T}\textbf{H})^{-1}\textbf{H}^{T}\textbf{h}$ is
unique and
$\Psi^{opt}=\frac{1}{2}\textbf{h}^{T}\textbf{h}-\frac{1}{2}\textbf{h}^{T}\textbf{H}(\textbf{H}^{T}\textbf{H})^{-1}\textbf{H}^{T}\textbf{h}$.

In this paper, we are interested in determining one least square solution to
the linear algebraic equation (3) when the coefficient matrix H can be
subdivided into multiple blocks $\textbf{H}_{kl}$, where $1\leq k\leq K$ and
$1\leq l\leq L$, as in (5) and each nonzero block is known by only one agent
in a network of $N$ agents.

$\textbf{H}=\left[\begin{matrix}\textbf{H}_{11}&\textbf{H}_{12}&\cdots&\textbf{H}_{1L}\\\
\textbf{H}_{21}&\textbf{H}_{22}&\cdots&\textbf{H}_{2L}\\\
\vdots&\vdots&\ddots&\vdots\\\
\textbf{H}_{K1}&\textbf{H}_{K2}&\cdots&\textbf{H}_{KL}\end{matrix}\right].$
(5)

The coefficient matrix H in (5) includes $KL$ blocks corresponding to $K$ row
and $L$ column partitions. As each agent $i$, where $1\leq i\leq N$, knows
some nonzero blocks, we have $KL\geq N$ in general setting. We define
$\mathcal{A}[\textbf{H}_{kl}]$ as an operator to express the agent knowing the
block $\textbf{H}_{kl}$. Since there may be some zero blocks in H, we
conventionally define $\mathcal{A}[\textbf{H}_{kl}]=0$ if
$\textbf{H}_{kl}=\textbf{0}$. Note that $0$ is not an agent. For each agent
$i$, we define the relation between the block $\textbf{H}_{kl}$ and this agent
by $\delta_{i}[\textbf{H}_{kl}]$ where $\delta_{i}[\textbf{H}_{kl}]=1$ if
$\mathcal{A}[\textbf{H}_{kl}]=i$ and $\delta_{i}[\textbf{H}_{kl}]=0$,
otherwise. Let
$\mathcal{B}_{k}^{(i)}=\\{\textbf{H}_{kl}:\delta_{i}[\textbf{H}_{kl}]=1,\forall
1\leq l\leq L\\}$ be the set of blocks in the row partition $k$ known by the
agent $i$, where $1\leq k\leq K$ and $1\leq i\leq N$.

For each row partition $k$, where $1\leq k\leq K$, of the coefficient matrix
H, we define the index list of agents that have information of blocks in this
row partition as
$\mathcal{R}_{k}=\\{\mathcal{A}[\textbf{H}_{k1}],\mathcal{A}[\textbf{H}_{k2}],\dots,\mathcal{A}[\textbf{H}_{kL}]\\}$.
Let $\mathcal{C}^{l}$ be the index list of agents that have information of
blocks in the column partition $l$, i.e.,
$\mathcal{C}^{l}=\\{\mathcal{A}[\textbf{H}_{1l}],\mathcal{A}[\textbf{H}_{2l}],\dots,\mathcal{A}[\textbf{H}_{Kl}]\\}$,
where $1\leq l\leq L$. As $\mathcal{R}_{k}$ and $\mathcal{C}^{l}$, where
$1\leq k\leq K$ and $1\leq l\leq L$, are lists, they can contain duplicated
indexes. We define the set $\mathbb{S}(\mathcal{R}_{k})$ derived from the list
$\mathcal{R}_{k}$ by removing the index $0$ and merging duplicated indexes
into one element. Similarly, we define $\mathbb{S}(\mathcal{C}^{l})$ for the
list $\mathcal{C}^{l}$ where $1\leq l\leq L$. We can obtain an equivalent
linear algebraic equation to (3) if we exchange rows in the matrix H and the
vector h. So, the rows in H can be interchanged such that the ones dispensed
across the same list of agents are grouped in the same row partition. Without
loss of generality, we assume that
$\mathcal{R}_{k}\neq\mathcal{R}_{k^{\prime}}$ if $k\neq k^{\prime}$ for all
$1\leq k,k^{\prime}\leq K$.

###  III-B Optimization approach

Denote by $m_{k},n_{l}$ the dimensions of the block
$\textbf{H}_{kl}\in\mathbb{R}^{m_{k}\times n_{l}}$, where $1\leq k\leq K$ and
$1\leq l\leq L$. We have $m=\sum_{k=1}^{K}m_{k}$ and $n=\sum_{l=1}^{L}n_{l}$.
According to the partition of the coefficient matrix H, the unknown vector z
and the coefficient vector h can be partitioned as
$\textbf{z}=\textrm{col}\\{\textbf{z}_{1},\textbf{z}_{2},\dots,\textbf{z}_{L}\\}$
and
$\textbf{h}=\textrm{col}\\{\textbf{h}_{1},\textbf{h}_{2},\dots,\textbf{h}_{K}\\}$
where

$\displaystyle\textbf{z}_{l}$
$\displaystyle=\textrm{blkrow}\bigl{\\{}\textbf{0}_{n_{l}\times\sum_{j=0}^{l-1}n_{j}},\textbf{I}_{n_{l}},\textbf{0}_{n_{l}\times\bigl{(}n-\sum_{j=0}^{l}n_{j}\bigr{)}}\bigr{\\}}\textbf{z},$
$\displaystyle\textbf{h}_{k}$
$\displaystyle=\textrm{blkrow}\bigl{\\{}\textbf{0}_{m_{k}\times\sum_{j=0}^{k-1}m_{j}},\textbf{I}_{m_{k}},\textbf{0}_{m_{k}\times\bigl{(}m-\sum_{j=0}^{k}m_{j}\bigr{)}}\bigr{\\}}\textbf{h}.$

Here we set $m_{0}=n_{0}=0$ conventionally. Assume that each agent
$i\in\mathbb{S}(\mathcal{C}^{l})$ has a copy $\textbf{z}_{l}^{(i)}$ for the
part $\textbf{z}_{l}$ of the unknown vector z. We have

$\sum_{l=1}^{L}\textbf{H}_{kl}\textbf{z}_{l}=\sum_{l=1,\textbf{H}_{kl}\neq\textbf{0}}^{L}\textbf{H}_{kl}\textbf{z}_{l}^{(\mathcal{A}[\textbf{H}_{kl}])},\forall
1\leq k\leq K.$ (6)

If $\mathcal{A}[\textbf{H}_{kl}]\neq 0$, the vector
$\textbf{H}_{kl}\textbf{z}_{l}^{\mathcal{A}[\textbf{H}_{kl}]}$ is private
information of the agent $\mathcal{A}[\textbf{H}_{kl}]$. To rewrite the error
of the linear equations corresponding to the row partition $k$ as the sum of
local private functions, we make the following assumption:

###### Assumption 1

For every row partition $k$, where $1\leq k\leq K$, each agent
$i\in\mathbb{S}(\mathcal{R}_{k})$ can access to a part of $\textbf{h}_{k}$
(i.e., can have a part of information of $\textbf{h}_{k}$). Let us denote the
part of information as $\textbf{h}_{i,k}$. However, the combination of
$\textbf{h}_{i,k}$ is equivalent to $\textbf{h}_{k}$ such that
$\sum\limits_{i\in\mathbb{S}(\mathcal{R}_{k})}\textbf{h}_{i,k}=\textbf{h}_{k}$.

Under Assumption 1, we have

$\sum_{l=1}^{L}\textbf{H}_{kl}\textbf{z}_{l}-\textbf{h}_{k}=\sum_{i\in\mathbb{S}(\mathcal{R}_{k})}\Bigl{(}\sum_{\textbf{H}_{kl}\in\mathcal{B}_{k}^{(i)}}\textbf{H}_{kl}\textbf{z}_{l}^{(i)}-\textbf{h}_{i,k}\Bigr{)},$
(7)

for all $1\leq k\leq K$. So, we have an equivalent problem of the optimization
problem (4) as follows.

$\displaystyle\min_{\textbf{z}_{l}^{(i)}}\frac{1}{2}\sum_{k=1}^{K}\left|\left|\sum_{i\in\mathbb{S}(\mathcal{R}_{k})}\left(\sum_{\textbf{H}_{kl}\in\mathcal{B}_{k}^{(i)}}\textbf{H}_{kl}\textbf{z}_{l}^{(i)}-\textbf{h}_{i,k}\right)\right|\right|^{2}$
(8a) $\displaystyle\textrm{s.t.
}\textbf{z}_{l}^{(i)}=\textbf{z}_{l}^{(j)},\forall
i,j\in\mathbb{S}(\mathcal{C}^{l}),i\neq j,\forall 1\leq l\leq L.$ (8b)

It is clear that the optimal cost value
$\Phi^{opt}=\frac{1}{2}||\textbf{H}\textbf{z}^{opt}-\textbf{h}||^{2}$ is also
the optimal value for the cost function in the problem (8). In addition, each
optimal solution to the optimization problem (8) can be used to determine one
least square solution (4) of the linear algebraic equation (3).

###  III-C Communication graph

In this paper, we use an undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ to illustrate the communication
network among agents. In which, $\mathcal{V}=\\{1,2,\dots\\}$ is the node set
and $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the edge set. Each
node $i\in\mathcal{V}=\\{1,2,\dots,N\\}$ corresponds to an agent while an edge
$(i,j)\in\mathcal{E}$ represents that the agent $i$ can exchange information
with the agent $j$. As $\mathcal{G}$ is an undirected graph,
$(i,j)\in\mathcal{E}$ implies $(j,i)\in\mathcal{E}$ for every pair of nodes
$i,j\in\mathcal{V}$. The neighbor set of the agent $i\in\mathcal{V}$ is
denoted by
$\mathcal{N}_{i}=\left\\{j\in\mathcal{V}:(i,j)\in\mathcal{E}\right\\}$. Since
agents need to cooperate to find the optimal solution of the problem (8), the
communication graph $\mathcal{G}$ is required to be connected. That means
there is at least one path from $i$ to $j$ for any pair $i,j\in\mathcal{V}$,
i.e., there is a sequence of edges
$(i_{1},i_{2}),(i_{2},i_{3}),\dots,(i_{k-1},i_{k})$ such that
$i_{1}=i,i_{k}=j$ and
$i_{l}\in\mathcal{V},(i_{l-1},i_{l})\in\mathcal{E},\forall 2\leq l\leq k$.

Let $\tilde{\mathcal{V}}$ be a node subset, i.e.,
$\tilde{\mathcal{V}}\subset\mathcal{V}$. The subgraph induced by
$\tilde{\mathcal{V}}$ is defined as
$\tilde{\mathcal{G}}=(\tilde{\mathcal{V}},\tilde{\mathcal{E}})$ where
$\tilde{\mathcal{E}}=\\{(i,j)\in\mathcal{E}:i,j\in\tilde{\mathcal{V}}\\}$. We
define $\mathcal{G}_{k}=(\mathbb{S}(\mathcal{R}_{k}),\mathcal{E}_{k})$ as the
subgraph induced by the node set $\mathbb{S}(\mathcal{R}_{k})$ for each row
partition $k$, where $1\leq k\leq K$. Similarly, we define
$\mathcal{G}^{l}=(\mathbb{S}(\mathcal{C}^{l}),\mathcal{E}^{l})$ for each
column partition $l$, where $1\leq l\leq L$. The following assumption is
necessary.

###### Assumption 2

The communication graph satisfies that

  1. 1.

$\mathcal{G}^{l}$ is a connected graph for all $1\leq l\leq L$,

  2. 2.

$\mathcal{G}_{k}$ is a connected graph for all $1\leq k\leq K$.

The first item in Assumption 2 is to allow agents in the set
$\mathbb{S}(\mathcal{C}^{l})$ can cooperatively achieve an agreement on the
part $\textbf{z}_{l}$ of the unknown vector z. Under this assumption, the
constraints in (8b) can be converted into coupling constraints among
neighboring agents as follows.

$\textbf{z}_{l}^{(i)}=\textbf{z}_{l}^{(j)},\forall
j\in\mathcal{N}_{i}\cap\mathbb{S}(\mathcal{C}^{l}),\forall
i\in\mathbb{S}(\mathcal{C}^{l}),$ (9)

for all $1\leq l\leq L$. When $i\in\mathbb{S}(\mathcal{R}_{k})$, the agent $i$
takes part in the linear equations corresponding to the row partition $k$ as
shown in (7). In general, there may be some row partitions $1\leq k\leq K$
where $\mathbb{S}(\mathcal{R}_{k})\neq\mathcal{N}_{i}$ for all
$i\in\mathbb{S}(\mathcal{R}_{k})$. Since communication is only available
between two neighboring agents, it is difficult for one agent to collect
complete information on the linear equations corresponding to these row
partitions. The second item in Assumption 2 facilitates a transformation of
these linear equations into local linear equations of individual agents
combining coupling constraints among neighboring agents, as presented later in
Section III. Summarizing this section, we state the main problem of this paper
as follows.

###### Problem 1

Assume that the communication graph of the considered multiagent network
satisfies Assumption 2. Design a distributed method for each agent to find its
corresponding parts in one optimal solution of the constrained optimization
problem (8) while using only its information and communicating with its
neighbors in $\mathcal{N}_{i}$.

##  IV Distributed optimization reformulation

Let
$\bar{\textbf{z}}_{i}=\textrm{col}\\{\textbf{z}_{l}^{(i)}:i\in\mathbb{S}(\mathcal{C}^{l}),\forall
1\leq l\leq L\\}$ be the vector of local variables of the agent
$i\in\mathcal{V}$. For each neighboring agent $j\in\mathcal{N}_{i}$, define
the matrix $\textbf{P}_{ij}$ such that
$\textbf{P}_{ij}\bar{\textbf{z}}_{i}=\textrm{col}\\{\textbf{z}_{l}^{(i)}:i,j\in\mathbb{S}(\mathcal{C}^{l}),\forall
1\leq l\leq L\\}$. The constraints in (9) are equivalent to the following one:

$\textbf{P}_{ij}\bar{\textbf{z}}_{i}=\textbf{P}_{ji}\bar{\textbf{z}}_{j},\forall(i,j)\in\mathcal{E}.$
(10)

Let
$\Psi(\bar{\textbf{z}}_{1},\bar{\textbf{z}}_{2},\dots,\bar{\textbf{z}}_{N})$
be the cost function in (8a). The optimization problem (8) can be rewritten as

$\min_{\bar{\textbf{z}}_{i},\forall
i\in\mathcal{V}}\Psi(\bar{\textbf{z}}_{1},\bar{\textbf{z}}_{2},\dots,\bar{\textbf{z}}_{N})\textrm{
s.t. }\eqref{eq_coupling_commonvariable}.$ (11)

Consider a row partition $k$ where there is only one agent $i$ in the set
$\mathbb{S}(\mathcal{R}_{k})$, i.e., $\mathbb{S}(\mathcal{R}_{k})=\\{i\\}$.
Under Assumption 1, the agent $i$ knows the vector $\textbf{h}_{k}$. In this
case, we have

$\sum_{l=1}^{L}\textbf{H}_{kl}\textbf{z}_{l}-\textbf{h}_{k}=\bar{\textbf{A}}_{i,k}\bar{\textbf{z}}_{i}-\bar{\textbf{a}}_{i,k},\textrm{
if }\mathbb{S}(\mathcal{R}_{k})=\\{i\\},$ (12)

where $\bar{\textbf{a}}_{i,k}=\textbf{h}_{k}$ and
$\bar{\textbf{A}}_{i,k}=\textrm{blkrow}\Bigl{\\{}\textbf{H}_{kl}\delta_{i}[\textbf{H}_{kl}]:i\in\mathbb{S}(\mathcal{R}_{k})\cap\mathbb{S}(\mathcal{C}^{l}),\forall
1\leq l\leq L\Bigr{\\}}$. Define by
$\mathbb{M}=\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{M}\\}$ the set of row
partitions whose corresponding sets consist of two or more agents, i.e.,
$|\mathbb{S}(\mathcal{R}_{\epsilon_{k}})|\geq 2$ for all
$\epsilon_{k}\in\mathbb{M}$. For each row partition
$\epsilon_{k}\in\mathbb{M}$ and agent $i\in\mathcal{V}$, define the matrix
$\bar{\textbf{B}}_{i,\epsilon_{k}}$ by
$\bar{\textbf{B}}_{i,\epsilon_{k}}=\textrm{blkrow}\Bigl{\\{}\textbf{H}_{\epsilon_{k}l}\delta_{i}[\textbf{H}_{\epsilon_{k}l}]:i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})\cap\mathbb{S}(\mathcal{C}^{l}),\forall\leq
l\leq L\Bigr{\\}}$ and
$\bar{\textbf{b}}_{i,\epsilon_{k}}=\textbf{h}_{i,\epsilon_{k}}$. We have

$\sum_{l=1}^{L}\textbf{H}_{\epsilon_{k}l}\textbf{z}_{l}-\textbf{h}_{\epsilon_{k}}=\sum_{i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})}\left(\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}-\bar{\textbf{b}}_{i,\epsilon_{k}}\right).$
(13)

Let $\textbf{u}_{\epsilon_{k}}$ be the error of the coupling linear equations
in the row partition $\epsilon_{k}\in\mathbb{M}$, i.e.,

$\textbf{u}_{\epsilon_{k}}=\sum_{i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})}\left(\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}-\bar{\textbf{b}}_{i,\epsilon_{k}}\right),\forall\epsilon_{k}\in\mathbb{M}.$
(14)

For every $\epsilon_{k}\in\mathbb{M}$, we define the vector
$\textbf{v}_{ij,\epsilon_{k}}$ for each edge
$(i,j)\in\mathcal{E}_{\epsilon_{k}}$ such that

$\frac{1}{|\mathbb{S}(\mathcal{R}_{\epsilon_{k}})|}\textbf{u}_{\epsilon_{k}}=\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}-\bar{\textbf{b}}_{i,\epsilon_{k}}+\sum_{j\in\mathcal{N}_{i,\epsilon_{k}}}\left(\textbf{v}_{ij,\epsilon_{k}}-\textbf{v}_{ji,\epsilon_{k}}\right),$
(15)

for all $i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})$, where
$\mathcal{N}_{i,\epsilon_{k}}\equiv\mathcal{N}_{i}\cap\mathbb{S}(\mathcal{R}_{\epsilon_{k}})$.
We remark here that there always exists a set
$\\{\textbf{v}_{ij,\epsilon_{k}}:(i,j)\in\mathcal{E}_{\epsilon_{k}}\\}$ that
satisfying (15). Indeed, from (15), we have

$\sum\limits_{j\in\mathcal{N}_{i,\epsilon_{k}}}\left(\textbf{v}_{ij,\epsilon_{k}}-\textbf{v}_{ji,\epsilon_{k}}\right)=\frac{1}{|\mathbb{S}(\mathcal{R}_{\epsilon_{k}})|}\textbf{u}_{\epsilon_{k}}-\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}+\bar{\textbf{b}}_{i,\epsilon_{k}},$
(16)

for all $i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})$. Consider (16) as a
system of linear equations with
$\\{\textbf{v}_{ij,\epsilon_{k}}:(i,j)\in\mathcal{E}_{\epsilon_{k}}\\}$ is the
set of unknown variables. It is clear that there are
$|\mathbb{S}(\mathcal{R}_{\epsilon_{k}})|$ linear equations and
$2|\mathcal{E}_{\epsilon_{k}}|$ variables. Since
$\mathcal{G}_{\epsilon_{k}}=(\mathbb{S}(\mathcal{R}_{\epsilon_{k}}),\mathcal{E}_{\epsilon_{k}})$
is a connected graph, we have
$|\mathcal{E}_{\epsilon_{k}}|\geq|\mathbb{S}(\mathcal{R}_{\epsilon_{k}})|$.
This implies that the linear algebraic equation (16) has infinite roots.

Let $\textbf{v}_{ij,\epsilon_{k}}^{(i)}$ be the copy of
$\textbf{v}_{ij,\epsilon_{k}}-\textbf{v}_{ji,\epsilon_{k}},\forall(i,j)\in\mathcal{E}_{\epsilon_{k}},$
in the agent $i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})$. Under the second
item in Assumtion 2, the coupling linear equations in (14), we have
$\frac{1}{|\mathbb{S}(\mathcal{R}_{\epsilon_{k}})|}\textbf{u}_{\epsilon_{k}}=\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}+\sum_{j\in\mathcal{N}_{i,\epsilon_{k}}}\textbf{v}_{ij,\epsilon_{k}}^{(i)}-\bar{\textbf{b}}_{i,\epsilon_{k}}$
if the following constraints are satisfied for all
$j\in\mathcal{N}_{i,\epsilon_{k}}$ where
$i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})$.

$\displaystyle\sum\limits_{l\in\mathcal{N}_{i,\epsilon_{k}}}\textbf{v}_{il,\epsilon_{k}}^{(i)}+\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}-\bar{\textbf{b}}_{i,\epsilon_{k}}=\sum\limits_{l\in\mathcal{N}_{j,\epsilon_{k}}}\textbf{v}_{jl,\epsilon_{k}}^{(j)}+\bar{\textbf{B}}_{j,\epsilon_{k}}\bar{\textbf{z}}_{j}-\bar{\textbf{b}}_{j,\epsilon_{k}},$
(17a)
$\displaystyle\textbf{v}_{ij,\epsilon_{k}}^{(i)}+\textbf{v}_{ij,\epsilon_{k}}^{(j)}=\textbf{0}.$
(17b)

Let
$\mathcal{M}_{i}=\\{\epsilon_{k}\in\mathbb{M}:i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})\\}$
for each agent $i\in\mathcal{V}$. Define the stacked vector
$\bar{\textbf{v}}_{i}=\textrm{col}\Bigl{\\{}\textrm{col}\Bigl{\\{}\textbf{v}_{ij,\epsilon_{k}}^{(i)}:j\in\mathcal{N}_{i,\epsilon_{k}}\Bigr{\\}}:\epsilon_{k}\in\mathcal{M}_{i}\Bigr{\\}}$.
In addition, we define the stacked matrix $\textbf{A}_{i}$ and the stacked
vector $\textbf{a}_{i}$ for each agent $i\in\mathcal{V}$ as

$\displaystyle\textbf{A}_{i}$
$\displaystyle=\textrm{blkcol}\bigl{\\{}\bar{\textbf{A}}_{i,k}:\mathbb{S}(\mathcal{R}_{k})=\\{i\\},\forall
1\leq k\leq K\bigr{\\}},$ $\displaystyle\textbf{a}_{i}$
$\displaystyle=\textrm{blkcol}\bigl{\\{}\bar{\textbf{a}}_{i,k}:\mathbb{S}(\mathcal{R}_{k})=\\{i\\},\forall
1\leq k\leq K\bigr{\\}}.$

For simple notation, we assume $\textbf{A}_{i}=\textbf{0}$ and
$\textbf{a}_{i}=\textbf{0}$ for agent $i\in\mathcal{V}$ if
$\mathbb{S}(\mathcal{R}_{k})\neq\\{i\\},\forall 1\leq k\leq K$, i.e., the
agent $i$ does not know all nonzero blocks in any row partition of the
coefficient matrix H. From (12), (14) and (17), we have
$\Psi(\bar{\textbf{z}}_{1},\bar{\textbf{z}}_{2},\dots,\bar{\textbf{z}}_{N})=\sum_{i\in\mathcal{V}}\Psi_{i}(\bar{\textbf{z}}_{i},\bar{\textbf{v}}_{i})$
where
$\Psi_{i}(\bar{\textbf{z}}_{i},\bar{\textbf{v}}_{i})=\frac{1}{2}\bigl{|}\bigl{|}\textbf{A}_{i}\bar{\textbf{z}}_{i}-\textbf{a}_{i}\bigr{|}\bigr{|}^{2}+\sum\limits_{\epsilon_{k}\in\mathcal{M}_{i}}\frac{|\mathbb{S}(\mathcal{R}_{\epsilon_{k}})|}{2}\bigl{|}\bigl{|}\sum\limits_{j\in\mathcal{N}_{i,\epsilon_{k}}}\textbf{v}_{ij,\epsilon_{k}}^{(i)}+\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}-\bar{\textbf{b}}_{i,\epsilon_{k}}\bigr{|}\bigr{|}^{2}$.

Consider the following optimization problem:

$\min_{\bar{\textbf{z}}_{i},\bar{\textbf{v}}_{i},\forall
i\in\mathcal{V}}\sum_{i\in\mathcal{V}}\Psi_{i}(\bar{\textbf{z}}_{i},\bar{\textbf{v}}_{i})\textrm{
s.t.
}\eqref{eq_coupling_commonvariable},\eqref{eq_LE_virtual_constraint}\forall\epsilon_{k}\in\mathbb{M}.$
(18)

We have the following result:

###### Lemma 1

Let
$\textrm{col}\\{\textrm{col}\\{\bar{\textbf{z}}_{i}^{opt},\bar{\textbf{v}}_{i}^{opt}\\}:i\in\mathcal{V}\\}$
be one optimal solution to the problem (18). Then
$\bar{\textbf{z}}_{i}^{opt},\forall i\in\mathcal{V},$ is the stacked vector of
the parts corresponding to the agent $i$ in a least square solution to the
linear algebraic equation (3).

###### Proof:

Lemma 1 is proved by showing that
$\textrm{col}\\{\bar{\textbf{z}}_{i}^{opt}:i\in\mathcal{V}\\}$ is one optimal
solution to the problem (11). We consider the contradiction. Assuming that
there exists a set of vectors $\\{\bar{\textbf{z}}_{i}^{*}:i\in\mathcal{V}\\}$
satisfying constraint (10) and
$\Psi(\bar{\textbf{z}}_{1}^{*},\bar{\textbf{z}}_{2}^{*},\dots,\bar{\textbf{z}}_{N}^{*})<\Psi(\bar{\textbf{z}}_{1}^{opt},\bar{\textbf{z}}_{2}^{opt},\dots,\bar{\textbf{z}}_{N}^{opt})$.
For each $\epsilon_{k}\in\mathbb{M}$, we define
$\textbf{u}_{\epsilon_{k}}^{*}=\sum_{i\in\mathbb{S}(\mathcal{R}_{\epsilon_{k}})}\left(\bar{\textbf{B}}_{i,\epsilon_{k}}\bar{\textbf{z}}_{i}^{*}-\bar{\textbf{b}}_{i,\epsilon_{k}}\right)$
and the set
$\\{\textbf{v}_{ij,\epsilon_{k}}^{*}:(i,j)\in\mathcal{E}_{\epsilon_{k}}\\}$
satisfying (16).

Let
$\bar{\textbf{v}}_{i}^{*}=\textrm{col}\bigl{\\{}\textrm{col}\bigl{\\{}\textbf{v}_{ij,\epsilon_{k}}^{*}-\textbf{v}_{ji,\epsilon_{k}}^{*}:j\in\mathcal{N}_{i,\epsilon_{k}}\bigr{\\}}:\epsilon_{k}\in\mathcal{M}_{i}\bigr{\\}}$,
$\forall i\in\mathcal{V}$. It is clear that
$\textrm{col}\\{\textrm{col}\\{\bar{\textbf{z}}_{i}^{*},\bar{\textbf{v}}_{i}^{*}\\}:i\in\mathcal{V}\\}$
is a feasible solution of the optimization problem (18). Moreover, we have
$\sum_{i\in\mathcal{V}}\Psi_{i}(\bar{\textbf{z}}_{i}^{*},\bar{\textbf{v}}_{i}^{*})=\Psi(\bar{\textbf{z}}_{1}^{*},\bar{\textbf{z}}_{2}^{*},\dots,\bar{\textbf{z}}_{N}^{*})<\Psi(\bar{\textbf{z}}_{1}^{opt},\bar{\textbf{z}}_{2}^{opt},\dots,\bar{\textbf{z}}_{N}^{opt})=\sum_{i\in\mathcal{V}}\Psi_{i}(\bar{\textbf{z}}_{i}^{opt},\bar{\textbf{v}}_{i}^{opt})$.
This contradicts to the fact that
$\textrm{col}\\{\textrm{col}\\{\bar{\textbf{z}}_{i}^{opt},\bar{\textbf{v}}_{i}^{opt}\\}:i\in\mathcal{V}\\}$
is one optimal solution to the problem (18). ∎

###### Remark 1

In APPENDIX-A, we provide an example to illustrate the list and sets in
distributed setup and the reformulation of distributed linear algebraic
equation (12-13) into the distributed optimization problem (18).

##  V Distributed ADMM-based method

In this section, we apply the proximal ADMM algorithm proposed in [15] to
design a distributed method for solving the optimization problem (18). The
designed method is guaranteed to have exponential convergence.

###  V-A ADMM based solution

Let
$\textbf{x}_{i}=\textrm{col}\\{\bar{\textbf{z}}_{i},\bar{\textbf{v}}_{i}\\}$
be the collection of all local variables of the agent $i\in\mathcal{V}$. Let
$\bar{n}_{i}$ be the length of the vector $\bar{\textbf{z}}_{i}$ for every
agent $i\in\mathcal{V}$. We have
$\bar{\textbf{z}}_{i}=\textrm{blkrow}\\{\textbf{I}_{\bar{n}_{i}},\textbf{0}\\}\textbf{x}_{i},\forall
i\in\mathcal{V}$. Define $\textbf{u}_{\epsilon_{k}}^{(i)}$ as the copy of the
vector $\textbf{u}_{\epsilon_{k}}$ in (15) and the stacked vector
$\bar{\textbf{u}}_{i}=\textrm{col}\\{\textbf{u}_{\epsilon_{k}}^{(i)}:\epsilon_{k}\in\mathcal{M}_{i}\\}$.
Then we have
$\bar{\textbf{u}}_{i}=\textbf{C}_{i}\textbf{x}_{i}-\textbf{c}_{i}$ where
$\textbf{c}_{i}=\textrm{col}\\{\bar{\textbf{b}}_{i,\epsilon_{k}}:\epsilon_{k}\in\mathcal{M}_{i}\\}$
and
$\textbf{C}_{i}=\left[\begin{matrix}\textrm{blkrow}\\{\bar{\textbf{B}}_{i,\epsilon_{k}}^{T}:\epsilon_{k}\in\mathcal{M}_{i}\\}\\\
\textrm{blkdiag}\bigl{\\{}\textrm{blkcol}\bigl{\\{}\textbf{I}_{m_{k}}:j\in\mathcal{N}_{i,\epsilon_{k}}\bigr{\\}}:\epsilon_{k}\in\mathcal{M}_{i}\bigr{\\}}\end{matrix}\right]^{T}$.
The local cost function $\Psi_{i}(\bar{\textbf{z}}_{i},\bar{\textbf{v}}_{i})$
of the agent $i\in\mathcal{V}$ has the quadratic form as

$\Psi_{i}(\bar{\textbf{z}}_{i},\bar{\textbf{u}}_{i},\bar{\textbf{v}}_{i})=\frac{1}{2}\textbf{x}_{i}^{T}\textbf{Q}_{i}\textbf{x}_{i}+\textbf{q}_{i}^{T}\textbf{x}_{i}+\textbf{a}_{i}^{T}\textbf{a}_{i}+\textbf{c}_{i}^{T}\textbf{c}_{i}.$

where
$\textbf{Q}_{i}=\textrm{blkdiag}\Bigl{\\{}\textbf{A}_{i}^{T}\textbf{A}_{i},\textbf{0}\Bigr{\\}}+\textbf{C}_{i}^{T}\textbf{C}_{i}$
and
$\textbf{q}_{i}=\textrm{col}\\{-\textbf{A}_{i}^{T}\textbf{a}_{i},\textbf{0}\\}+\textbf{C}_{i}^{T}\textbf{c}_{i}$.
It is easy to verify that $\textbf{Q}_{i}$ is a symmetric and positive
semidefinite matrix and $\textbf{C}_{i}$ is a full row rank matrix, $\forall
i\in\mathcal{V}$.

For two agents $i$ and $j$, where $(i,j)\in\mathcal{E}$ and
$\epsilon_{k}\in\mathcal{M}_{i}\cap\mathcal{M}_{j}$, we assume that they
choose the pair of matrices $\textbf{D}_{ij,\epsilon_{k}}$ and
$\textbf{D}_{ji,\epsilon_{k}}$ such that if
$\textbf{D}_{ij,\epsilon_{k}}=\textbf{I}$ then
$\textbf{D}_{ji,\epsilon_{k}}=-\textbf{I}$ and if
$\textbf{D}_{ij,\epsilon_{k}}=-\textbf{I}$ then
$\textbf{D}_{ji,\epsilon_{k}}=\textbf{I}$ and vice versa. Define the matrices
$\textbf{E}_{ij},\forall j\in\mathcal{N}_{i}$, such that

$\textbf{E}_{ij}\textbf{x}_{i}=\textrm{col}\\{\textbf{P}_{ij}\bar{\textbf{z}}_{i},\textrm{col}\\{\textbf{u}_{\epsilon_{k}}^{(i)},\textbf{D}_{ij,\epsilon_{k}}\textbf{v}_{ij,\epsilon_{k}}^{(i)}:\epsilon_{k}\in\mathcal{M}_{i}\cap\mathcal{M}_{j}\\}\\}.$
(19)

It is clear that
$\textbf{E}_{ij}\textbf{x}_{i}=\textbf{E}_{ji}\textbf{x}_{j},\forall(i,j)\in\mathcal{E}$.
The optimization problem (18) can be rewritten in the following form:

$\displaystyle\min\limits_{\begin{subarray}{c}\textbf{x}_{i},\forall
i\in\mathcal{V}\\\
(\textbf{y}_{ij},\textbf{y}_{ji})\in\mathcal{Y}_{ij},\forall(i,j)\in\mathcal{E}\end{subarray}}$
$\displaystyle\sum_{i\in\mathcal{V}}\left(\frac{1}{2}\textbf{x}_{i}^{T}\textbf{Q}_{i}\textbf{x}_{i}+\textbf{q}_{i}^{T}\textbf{x}_{i}\right)$
(20a) s.t. $\displaystyle\textbf{E}_{ij}\textbf{x}_{i}=\textbf{y}_{ij},\forall
j\in\mathcal{N}_{i},\forall i\in\mathcal{V}.$ (20b)

where
$\mathcal{Y}_{ij}=\\{(\textbf{y}_{ij},\textbf{y}_{ji}):\textbf{y}_{ij}=\textbf{y}_{ji}\\}$
for all $(i,j)\in\mathcal{E}$. The coupling constraints (10) and (17) between
two neighboring agents $i$ and $j$, where $(i,j)\in\mathcal{E}$, are replaced
by the equality constraints in (20b) combining the constraint
$(\textbf{y}_{ij},\textbf{y}_{ji})\in\mathcal{Y}_{ij}$. It is easy to verify
that the problem (20) has the form of the convex optimization problem (1) with
the variable vectors
$\textbf{x}=\textrm{col}\\{\textbf{x}_{1},\textbf{x}_{2},\dots,\textbf{x}_{N}\\}$,
$\textbf{y}=\textrm{col}\\{\textrm{col}\\{\textbf{y}_{ij},\textbf{y}_{ji}\\}:(i,j)\in\mathcal{E}\\}$,
the cost functions
$\Psi_{x}(\textbf{x})=\sum_{i\in\mathcal{V}}\Bigl{\\{}\frac{1}{2}\textbf{x}_{i}^{T}\textbf{Q}_{i}\textbf{x}_{i}+\textbf{q}_{i}^{T}\textbf{x}_{i}\Bigr{\\}}$,
$\Psi_{y}(\textbf{y})=0$, and
$\mathcal{Y}=\prod\limits_{(i,j)\in\mathcal{E}}\mathcal{Y}_{ij}$. So, the
optimal solution of the problem (20) can be found by using the proximal ADMM
algorithm (2).

Define $\bm{\lambda}_{ij}$, $\forall j\in\mathcal{N}_{i}$, as the dual
variables corresponding to the equality constraints in (20b) of the agent
$i\in\mathcal{V}$. These dual variables can be stacked into a vector
$\bm{\lambda}=\textrm{col}\\{\textrm{col}\\{\bm{\lambda}_{ij},\bm{\lambda}_{ji}\\}:(i,j)\in\mathcal{E}\\}$.
The augmented Lagrangian function of the problem (20) is given by

$\mathcal{L}_{\rho}(\textbf{x},\textbf{y},\bm{\lambda})=\sum\limits_{i\in\mathcal{V}}\Bigl{\\{}\frac{1}{2}\textbf{x}_{i}^{T}\textbf{Q}_{i}\textbf{x}_{i}+\textbf{q}_{i}^{T}\textbf{x}_{i}+\frac{\rho}{2}\sum\limits_{j\in\mathcal{N}_{i}}||\textbf{E}_{ij}\textbf{x}_{i}-\textbf{y}_{ij}-\frac{1}{\rho}\bm{\lambda}_{ij}||^{2}\Bigr{\\}}.$

Due to the separation of the augmented Lagrangian function
$\mathcal{L}(\textbf{x},\textbf{y},\bm{\lambda})$, the equations (2a) and (2b)
are equivalent to the equations (21) and (22), respectively. Here, the matrix
$\textbf{G}=\textrm{blkdiag}\\{\textbf{G}_{i}:i\in\mathcal{V}\\}$ where
$\textbf{G}_{i}$ is a positive semi-definite matrix chosen by the agent
$i\in\mathcal{V}$.

$\textbf{x}_{i}(s+1)=\arg\min\limits_{\textbf{x}_{i}}\left(\frac{1}{2}\textbf{x}_{i}^{T}\textbf{Q}_{i}\textbf{x}_{i}+\textbf{q}_{i}^{T}\textbf{x}_{i}+\frac{\rho}{2}\sum\limits_{j\in\mathcal{N}_{i}}||\textbf{E}_{ij}\textbf{x}_{i}-\textbf{y}_{ij}(s)-\frac{1}{\rho}\bm{\lambda}_{ij}(s)||^{2}+\frac{1}{2}||\textbf{x}_{i}-\textbf{x}_{i}(s)||_{\textbf{G}_{i}}\right),\forall
i\in\mathcal{V}.$ (21)
$(\textbf{y}_{ij},\textbf{y}_{ji})(s+1)=\arg\min\limits_{\textbf{y}_{ij}=\textbf{y}_{ji}}\left(||\textbf{E}_{ij}\textbf{x}_{i}(s+1)-\textbf{y}_{ij}-\frac{1}{\rho}\bm{\lambda}_{ij}(s)||^{2}+||\textbf{E}_{ji}\textbf{x}_{j}(s+1)-\textbf{y}_{ji}-\frac{1}{\rho}\bm{\lambda}_{ji}(s)||^{2}\right),\forall(i,j)\in\mathcal{E}.$
(22)

###  V-B Detailed algorithm

Assume that $\textbf{G}_{i}$ is chosen such that the matrix
$\hat{\textbf{Q}}_{i}$ (defined in (23b)) is positive definite, the update
(21) is equivalent to (23), $\forall i\in\mathcal{V}$.

$\displaystyle\textbf{x}_{i}(s+1)$
$\displaystyle=-\hat{\textbf{Q}}_{i}^{-1}\hat{\textbf{q}}_{i}(s),$ (23a)
$\displaystyle\textrm{where }\hat{\textbf{Q}}_{i}$
$\displaystyle=\textbf{Q}_{i}+\textbf{G}_{i}+\rho\sum_{j\in\mathcal{N}_{i}}\textbf{E}_{ij}^{T}\textbf{E}_{ij},$
(23b) $\displaystyle\hat{\textbf{q}}_{i}(s)$
$\displaystyle=\textbf{q}_{i}-\textbf{G}_{i}\textbf{x}_{i}(s)-\sum\limits_{j\in\mathcal{N}_{i}}\textbf{E}_{ij}^{T}\left(\rho\textbf{y}_{ij}(s)+\bm{\lambda}_{ij}(s)\right).$
(23c)

Consider the optimization problem in (22). The KKT conditions of this problem
consist of

$\displaystyle\textbf{E}_{ij}\textbf{x}_{i}(s+1)-\textbf{y}_{ij}(s+1)-\frac{1}{\rho}\bm{\lambda}_{ij}(s)+\bm{\mu}=\textbf{0},$
(24)
$\displaystyle\textbf{E}_{ji}\textbf{x}_{j}(s+1)-\textbf{y}_{ji}(s+1)-\frac{1}{\rho}\bm{\lambda}_{ji}(s)-\bm{\mu}=\textbf{0},$
(25) $\displaystyle\textbf{y}_{ij}(s+1)=\textbf{y}_{ji}(s+1),$ (26)

where $\bm{\mu}$ is the dual variable corresponding to the constraint
$\textbf{y}_{ij}=\textbf{y}_{ji}$. Adding two equations (24) and (25), we
obtain
$\textbf{y}_{ij}(s+1)+\textbf{y}_{ji}(s+1)=\textbf{E}_{ij}\textbf{x}_{i}(s+1)-\frac{1}{\rho}\bm{\lambda}_{ij}(s)+\textbf{E}_{ji}\textbf{x}_{j}(s+1)-\textbf{y}_{ji}(s+1)-\frac{1}{\rho}\bm{\lambda}_{ji}(s)$.
From (26), we have

$\textbf{y}_{ij}(s+1)=\frac{1}{2}\left(\textbf{E}_{ij}\textbf{x}_{i}(s+1)-\frac{1}{\rho}(\bm{\lambda}_{ij}(s)+\textbf{E}_{ji}\textbf{x}_{j}(s+1)-\frac{1}{\rho}\bm{\lambda}_{ji}(s)\right),$
(27)

for all $(i,j)\in\mathcal{E}$. According to (2c), the update of the dual
variables $\bm{\lambda}_{ij},\forall(i,j)\in\mathcal{E},$ are given as

$\bm{\lambda}_{ij}(s+1)=\bm{\lambda}_{ij}(s)-\rho\left(\textbf{E}_{ij}\textbf{x}_{i}(s+1)-\textbf{y}_{ij}(s+1)\right).$
(28)

We provide Algorithm 1 to highlight the implementation of our designed method
for one agent. It is easy to verify that this algorithm requires only local
information for each agent except the common penalty parameter $\rho$ as
global information. However, this information can be easily achieved by the
agreement among agents. In the iteration update (23-28), ever agent
$i\in\mathcal{V}$ uses only information belonging to itself or received from
its neighbors in $\mathcal{N}_{i}$.

1:_Agree a common positive penalty parameter_ $\rho>0$

2:_Choose_ $\textbf{G}_{i}\succeq 0$ such that $\hat{\textbf{Q}}_{i}\succ 0$
(given in (23b))

3:_Initiate:_ $s=0,\textbf{x}_{i}(0)=\textbf{0}$ and
$\textbf{y}_{ij}(0)=\textbf{0},\forall j\in\mathcal{N}_{i}$.

4:_Repeat until convergence:_

5: $\textbf{x}_{i}(s+1)\leftarrow$ (23),

6: Send
$\textbf{E}_{ij}\textbf{x}_{i}(s+1)-\frac{1}{\rho}\bm{\lambda}_{ij}(s)$ to all
$j\in\mathcal{N}_{i}$,

7: Receive
$\textbf{E}_{ji}\textbf{x}_{j}(s+1)-\frac{1}{\rho}\bm{\lambda}_{ji}(s)$ from
all $j\in\mathcal{N}_{i}$,

8: $\textbf{y}_{i}(s+1)\leftarrow$ (27), $\forall j\in\mathcal{N}_{i}$,

9: $\bm{\lambda}_{ij}(s+1)\leftarrow$ (28), $\forall j\in\mathcal{N}_{i}$,

10: $s\leftarrow s+1$,

11:_Finish algorithm:_
$\textbf{z}_{i}^{output}=\textrm{blkrow}\\{\textbf{I}_{\bar{n}_{i}},\textbf{0}\\}\textbf{x}_{i}(s)$

Algorithm 1 Distributed method for agent $i\in\mathcal{V}$ to find
$\bar{\textbf{z}}_{\mathcal{S}_{i}}^{opt}$.

Let
$\textbf{w}_{i}(s)=\textrm{col}\Bigl{\\{}\textbf{x}_{i}(s),\textrm{col}\bigl{\\{}\textbf{y}_{ij}(s),\bm{\lambda}_{ij}(s):j\in\mathcal{N}_{i}\bigr{\\}}\Bigr{\\}}$
be the stacked vector corresponding to the estimated solution of the agent
$i\in\mathcal{V}$ at the iteration step $s$ in the update (23-28). Based on
Theorem 1, we have the following theorem:

###### Theorem 2

Let every agent $i\in\mathcal{V}$ apply Algorithm 1. The estimated solution
$\textbf{w}(s)=\textrm{col}\\{\textbf{w}_{i}(s):i\in\mathcal{V}\\}$ converges
exponentially to $\textbf{w}^{\infty}$ where
$\textbf{w}^{\infty}=\textrm{col}\\{\textbf{w}_{i}^{\infty}:i\in\mathcal{V}\\}$
is one optimal solution of the optimization problem (20).

###### Proof:

The first item in Theorem 1 implies there exists a converged point
$\textbf{w}^{\infty}$, i.e.,
$\lim_{s\rightarrow\infty}\textbf{w}(s)=\textbf{w}^{\infty}$, for arbitrarily
initial point $\textbf{w}(0)$ where
$\textbf{w}(s)=\textrm{col}\\{\textbf{w}_{i}(s):i\in\mathcal{V}\\}$ and
$\textbf{w}^{\infty}=\textrm{col}\\{\textbf{w}_{i}^{\infty}:i\in\mathcal{V}\\}$.
The second and third items of Theorem 1 correspond to the convergence of the
equality constraint and the cost function value. They guarantee that the
converged point $\textbf{w}^{\infty}$ satisfies all constraints and attain the
minimum cost function value of the problem (20). So $\textbf{w}^{\infty}$ is
one optimal solution to the optimization problem (20).

According to (23-28), there exist a constant matrix M and a constant vector m
such that

$\textbf{w}(s+1)=\textbf{M}\textbf{w}(s)+\textbf{m}.$ (29)

The detailed formulations of M and m are presented in this paper since they
are not necessary in the analysis.

Define $\overline{\textbf{w}}(s)=\textbf{w}(s+1)-\textbf{w}(s)$, we have
$\overline{\textbf{w}}(s)\rightarrow\textbf{0}$ as $s\rightarrow\infty$ with
all initial setup $\textbf{w}(0)$. From (29), we have

$\overline{\textbf{w}}(s+1)=\textbf{M}\overline{\textbf{w}}(s).$

By choosing $\textbf{w}(0)=\textbf{0}$, we have
$\overline{\textbf{w}}(s)=\textbf{M}^{s}\textbf{m}$. So,
$\lim_{s\rightarrow\infty}\textbf{M}^{s}\textbf{m}=\textbf{0}$. Let
$\textbf{v}_{(\sigma)}$ be the eigenvector of the matrix M corresponding to
the eigenvalue $\sigma$, i.e.,
$\textbf{M}\textbf{v}_{(\sigma)}=\sigma\textbf{v}_{(\sigma)}$. By choosing
$\textbf{w}(0)=\textbf{v}_{(\sigma)}$, we have
$\overline{\textbf{w}}(s)=(\sigma-1)\sigma^{s}\textbf{v}_{(\sigma)}+\textbf{M}^{s}\textbf{m}$.
The fact
$\lim_{s\rightarrow\infty}\overline{\textbf{w}}(s)=\lim_{s\rightarrow\infty}(\sigma-1)\sigma^{s}\textbf{v}_{(\sigma)}=\textbf{0}$
can be guaranteed if $|\sigma|<1$ or $\sigma=1$. That means, for every
eigenvalue $\sigma$ of the matrix M, if $\sigma\neq 1$ then $|\sigma|<1$. So,
if the matrix M does not have an eigenvalue at $1$, $\textbf{w}(s+1)$
converges to $\textbf{w}^{\infty}$ exponentially because
$\textbf{w}(s+1)-\textbf{w}^{\infty}=\textbf{M}\left(\textbf{w}(s)-\textbf{w}^{\infty}\right)$.

Assume that the matrix M has an eigenvalue at $1$ and its algebraic
multiplicity is bigger than its geometric multiplicity. That means there
exists a vector $\textbf{u}_{(1)}$ such that
$(\textbf{M}-\textbf{I})\textbf{u}_{(1)}=\textbf{v}_{(1)}$. Let
$\textbf{w}(0)=\textbf{u}_{(1)}$, we have
$\overline{\textbf{w}}(s)=\textbf{v}_{(1)}+\textbf{M}^{s}\textbf{m}$. This
contradicts the asymptotic convergence to zero vector of
$\overline{\textbf{w}}(s)$. So, if M has an eigenvalue at $1$, its algebraic
multiplicity is equal to its geometric multiplicity. This fact implies there
exists a nonsingular matrix T such that
$\textbf{M}=\textbf{T}\left[\begin{matrix}\textbf{I}_{k}&\textbf{0}\\\
\textbf{0}&\textbf{J}\end{matrix}\right]\textbf{T}^{-1}$ where $k$ is the
algebraic multiplicity corresponding to the eigenvalue $1$ of the matrix M and
the matrix J has all eigenvalues lying within the unit open disk. Since
$\textbf{w}(s+1)-\textbf{w}^{\infty}=\textbf{M}\left(\textbf{w}(s)-\textbf{w}^{\infty}\right)$,
we have

$\textbf{w}(s+l)-\textbf{w}^{\infty}=\textbf{T}\left[\begin{matrix}\textbf{I}_{k}&\textbf{0}\\\
\textbf{0}&\textbf{J}^{l}\end{matrix}\right]\textbf{T}^{-1}\left(\textbf{w}(s)-\textbf{w}^{\infty}\right).$

The asymptotic convergence of the estimated solution $\textbf{w}(s)$ to the
converged point $\textbf{w}^{\infty}$ implies

$\textbf{0}=\lim_{l\rightarrow\infty}\left(\textbf{w}(s+l)-\textbf{w}^{\infty}\right)=\textbf{T}\left[\begin{matrix}\textbf{I}_{k}&\textbf{0}\\\
\textbf{0}&\textbf{0}\end{matrix}\right]\textbf{T}^{-1}\left(\textbf{w}(s)-\textbf{w}^{\infty}\right)$

because $\textbf{J}^{l}\rightarrow\textbf{0}$ as $l\rightarrow\infty$. So we
have

$\displaystyle\textbf{w}(s+1)-\textbf{w}^{\infty}$
$\displaystyle=\textbf{M}(\textbf{w}(s)-\textbf{w}^{\infty})-\textbf{0}$
$\displaystyle=\left(\textbf{M}-\textbf{T}\left[\begin{matrix}\textbf{I}_{k}&\textbf{0}\\\
\textbf{0}&\textbf{0}\end{matrix}\right]\textbf{T}^{-1}\right)\left(\textbf{w}(s)-\textbf{w}^{\infty}\right)$
$\displaystyle=\textbf{T}\left[\begin{matrix}\textbf{0}_{k\times
k}&\textbf{0}\\\
\textbf{0}&\textbf{J}\end{matrix}\right]\textbf{T}^{-1}\left(\textbf{w}(s)-\textbf{w}^{\infty}\right)$
$\displaystyle=\textbf{T}\left[\begin{matrix}\textbf{0}_{k\times
k}&\textbf{0}\\\
\textbf{0}&\textbf{J}^{s+1}\end{matrix}\right]\textbf{T}^{-1}\left(\textbf{w}(0)-\textbf{w}^{\infty}\right).$

Since all eigenvalues in the matrix J are within the unit open disk,
$\textbf{w}(s)-\textbf{w}^{\infty}$ converges exponentially to the origin. ∎

According to Theorem 2,
$\bar{\textbf{z}}_{i}(s)=\textrm{blkrow}\\{\textbf{I}_{\bar{n}_{i}},\textbf{0}\\}\textbf{x}_{i}(s)$
converges exponentially to
$\bar{\textbf{z}}_{i}^{\infty}=\textrm{blkrow}\\{\textbf{I}_{\bar{n}_{i}},\textbf{0}\\}\textbf{x}_{i}^{\infty},\forall
i\in\mathcal{V}$. Lemma 1 guarantees that the stacked vector
$\bar{\textbf{z}}_{i}^{\infty},\forall i\in\mathcal{V},$ consists of parts
corresponding to the agent $i$ in one least square solution of the linear
algebraic equation (3).

##  VI Numerical simulations

###  VI-A Distributed setup with rows and columns decomposition

This part considers a distributed linear algebraic equation over a network of
$24$ agents, which can be represented in the form of (12-13). Assume that each
agent has $20$ local variables and there is one coupling row partition across
all agents. That means $\bar{\textbf{z}}_{i}\in\mathbb{R}^{20}$ for all
$i\in\\{1,2,\dots,24\\}$ and $\mathbb{M}=\\{\epsilon_{1}\\}$,
$\mathcal{R}_{\epsilon_{1}}=\\{1,2,\dots,24\\}$.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$18$$19$$20$$21$$22$$23$$24$
Figure 1: Communication graph: nodes represent agents and edges represent
available communication among agents.

Let the communication graph be given in Fig. 1 and
$\bar{\textbf{B}}_{i,\epsilon_{1}}=\left[\begin{matrix}\textbf{0}_{5\times
15}&\textbf{I}_{5}\end{matrix}\right],\forall i\in\\{1,2,\dots,24\\}$. Every
vector $\bar{\textbf{b}}_{i,\epsilon_{1}}$ is chosen randomly. In addition, we
assume that the first $5$ elements in local variable vectors
$\bar{\textbf{z}}_{i},\forall i\in\\{1,2,\dots,24\\}$, are common variables.
In other word,
$\textbf{P}_{ij}=\textbf{P}_{ji}=\left[\begin{matrix}\textbf{I}_{5}&\textbf{0}_{5\times
15}\end{matrix}\right]$ for all pairs $(i,j)$ of neighboring agents. We use
MATLAB to test the effectiveness of our designed method in finding least
square solutions to one hundred numerical examples. In each example, we choose
$\textbf{A}_{i}\in\mathbb{R}^{20\times 20},\textbf{a}_{i}\in\mathbb{R}^{20}$
randomly, $\forall i\in\\{1,2,\dots,24\\}$. The ADMM-based method (23-28) is
run with the selection of $\rho=1$.

Figure 2: The convergence to the least square solution of the proposed
algorithm for the distributed linear algebraic equation with rows and columns
decomposition.

Fig. 2 shows the simulation results of two examples having the fastest (blue
lines) and the slowest (red lines) convergence rates. In this figure, the
solid lines represent the convergence of the estimated solution in the update
(23-28) to one optimal solution $\textbf{x}^{opt}$ of the problem (20). The
dashed lines illustrate to the evolution of the function
$|\Psi(s)-\Psi^{opt}|$ where
$\Psi(s)=\sum_{i=1}^{24}\left(\textbf{x}_{i}(s)^{T}\textbf{Q}_{i}\textbf{x}_{i}(s)+\textbf{q}_{i}^{T}\textbf{x}_{i}(s)+\textbf{a}_{i}^{T}\textbf{a}_{i}+\textbf{c}_{i}^{T}\textbf{c}_{i}\right)$
and $\Psi^{opt}$ is the optimal cost value. From the simulation results, it is
easy to verify the exponential convergence of the estimated solution to the
optimal one. A practical solution can be achieved after about $2000$
iterations. In addition, we measure the computation time required by each
agent in every iteration step. The maximum time required by one agent for
$2000$ iterations is $0.5$ second.

###  VI-B Distributed setup with rows decomposition

In this part, we compare our designed method with the existing methods
proposed in Wang et. al. 2019 [8] and Yang et. al. 2020 [10]. Assume that the
tested linear algebraic equation system has the form of (30) and the
communication network is given in Fig. 3. Let each agent $i$ know the row
partitions $\textbf{A}_{i}$ and $\textbf{b}_{i}$.

$1$$2$$3$$4$$5$ Figure 3: Communication graph of $5$ agents.

$\textbf{A}=\left[\begin{matrix}\textbf{A}_{1}\\\ \textbf{A}_{2}\\\
\textbf{A}_{3}\\\ \textbf{A}_{4}\\\
\textbf{A}_{5}\end{matrix}\right],\textbf{b}=\left[\begin{matrix}\textbf{b}_{1}\\\
\textbf{b}_{2}\\\ \textbf{b}_{3}\\\ \textbf{b}_{4}\\\
\textbf{b}_{5}\end{matrix}\right]$ (30)

We first test the convergence of three distributed algorithms in small linear
algebraic equation systems $(\textbf{A},\textbf{b})$ where
$\textbf{A}_{i}\in\mathcal{R}^{1\times 4}$. Fig. 4 and Fig. 5 correspond with
the case $(\textbf{A},\textbf{b})=(\textbf{A}^{(1)},\textbf{b}^{(1)})$ and
$(\textbf{A},\textbf{b})=(\textbf{A}^{(2)},\textbf{b}^{(2)})$, respectively.
Note that, the linear algebraic equation $(\textbf{A}^{(1)},\textbf{b}^{(1)})$
has a unique solution while the linear algebraic equation
$(\textbf{A}^{(2)},\textbf{b}^{(2)})$ has infinity solutions.

$\textbf{A}^{(1)}=\left[\begin{matrix}1&2&1&1\\\ 2&-1&-1&1\\\ 1&-2&4&-1\\\
-1&-0.6&0.4&1.8\\\
2&2&-2&1\end{matrix}\right],\textbf{b}^{(1)}=\left[\begin{matrix}10\\\ 20\\\
15\\\ 17\\\ 11\end{matrix}\right]\textrm{ and
}\textbf{A}^{(2)}=\left[\begin{matrix}1&2&1&1\\\ 1&1.4&-1.6&2.8\\\
3&3.&-3.6&3.8\\\ -1&-0.6&0.4&1.8\\\
2&2&-2&1\end{matrix}\right],\textbf{b}^{(2)}=\left[\begin{matrix}10\\\ 20\\\
15\\\ 17\\\ 11\end{matrix}\right]$ (31)

Figure 4: The convergence to the least square solution of three distributed
algorithms for the distributed linear algebraic equation
$(\textbf{A}^{(1)},\textbf{b}^{(1)})$ with $5$ agents. Figure 5: The
convergence to the least square solution of three distributed algorithms for
the distributed linear algebraic equation
$(\textbf{A}^{(2)},\textbf{b}^{(2)})$ with $5$ agents.

In both cases, our proposed method requires significantly less iterations than
two others. Finally, we compare the effectiveness of three distributed methods
for solving a larger linear algebraic equation system. Fig. 6 presents the
numerical results when the matrix $\textbf{A}_{i}$ and the vector
$\textbf{b}_{i}$ are chosen randomly such that
$\textbf{A}_{i}\in\mathbb{R}^{60\times 30}$ and
$\textbf{b}\in\mathbb{R}^{60}$.

Figure 6: The convergence to the least square solution of three distributed
algorithms for larger distributed linear algebraic equation with $5$ agents.

In this case, the advanced convergence of our proposed method is shown more
clearly.

##  VII Conclusion

This paper considers a linear algebraic equation
$\textbf{H}\textbf{z}=\textbf{h}$ when rows and columns of the coefficient
matrix H are dispensed across a network of agents. By introducing some virtual
variables, the problem of finding one least square solution to the considered
linear algebraic equation is reformulated into a distributed optimization
problem. Then, we apply a proximal ADMM algorithm to design a distributed
method for agents to solve the formulated optimization problem cooperatively.
The estimated solution of every agent converges exponentially to its
corresponding parts in one exact least square solution of the considered
linear algebraic equation.

###  -A Illustrate the reformulation the problem of finding the least square
solution to distributed optimization problem

To illustrate the list and sets defined above, we consider an example as shown
in Fig. 7. First, we observe that
$\mathcal{B}_{1}^{(1)}=\\{\textbf{H}_{11},\textbf{H}_{13}\\}$,
$\mathcal{B}_{1}^{(2)}=\mathcal{B}_{1}^{(3)}=\mathcal{B}_{1}^{(4)}=\mathcal{B}_{1}^{(5)}=\emptyset$;
$\mathcal{B}_{2}^{(1)}=\mathcal{B}_{2}^{(3)}=\mathcal{B}_{2}^{(5)}=\emptyset$,
$\mathcal{B}_{2}^{(2)}=\\{\textbf{H}_{21}\\}$,
$\mathcal{B}_{2}^{(4)}=\\{\textbf{H}_{24}\\}$;
$\mathcal{B}_{3}^{(1)}=\mathcal{B}_{3}^{(2)}=\mathcal{B}_{3}^{(4)}=\mathcal{B}_{3}^{(5)}=\emptyset$,
$\mathcal{B}_{3}^{(3)}=\\{\textbf{H}_{32},\textbf{H}_{33}\\}$;
$\mathcal{B}_{4}^{(1)}=\mathcal{B}_{4}^{(5)}=\emptyset$,
$\mathcal{B}_{4}^{(2)}=\\{\textbf{H}_{41}\\}$,
$\mathcal{B}_{4}^{(3)}=\\{\textbf{H}_{43}\\}$,
$\mathcal{B}_{4}^{(4)}=\\{\textbf{H}_{44}\\}$;
$\mathcal{B}_{5}^{(1)}=\mathcal{B}_{5}^{(2)}=\mathcal{B}_{5}^{(3)}=\mathcal{B}_{5}^{(4)}=\emptyset$,
$\mathcal{B}_{5}^{(5)}=\\{\textbf{H}_{51},\textbf{H}_{53}\\}$;
$\mathcal{B}_{6}^{(1)}=\mathcal{B}_{6}^{(2)}=\mathcal{B}_{6}^{(3)}=\mathcal{B}_{6}^{(4)}=\emptyset$,
$\mathcal{B}_{6}^{(5)}=\\{\textbf{H}_{61},\textbf{H}_{62}\\}$. The index lists
corresponding to the row and column partitions are given as:
$\mathcal{R}_{1}=\\{1,0,1,0\\}$, $\mathcal{R}_{2}=\\{2,0,0,4\\}$,
$\mathcal{R}_{3}=\\{0,3,3,0\\}$, $\mathcal{R}_{4}=\\{2,0,3,4\\}$,
$\mathcal{R}_{5}=\\{5,0,5,0\\}$, $\mathcal{R}_{6}=\\{5,5,0,0\\}$, and
$\mathcal{C}^{1}=\\{1,2,0,2,5,5\\}$, $\mathcal{C}^{2}=\\{0,0,3,0,0,5\\}$,
$\mathcal{C}^{3}=\\{1,0,3,3,5,0\\}$, $\mathcal{C}^{4}=\\{0,4,0,4,0,0\\}$.

$\textbf{H}=\left[\begin{matrix}\textbf{H}_{11}&\textbf{0}&\textbf{H}_{13}&\textbf{0}\\\
\textbf{H}_{21}&\textbf{0}&\textbf{0}&\textbf{H}_{24}\\\
\textbf{0}&\textbf{H}_{32}&\textbf{H}_{33}&\textbf{0}\\\
\textbf{H}_{41}&\textbf{0}&\textbf{H}_{43}&\textbf{H}_{44}\\\
\textbf{H}_{51}&\textbf{0}&\textbf{H}_{53}&\textbf{0}\\\
\textbf{H}_{61}&\textbf{H}_{62}&\textbf{0}&\textbf{0}\end{matrix}\right]$a.
Coefficient matrix

Agent $1$ knows $\textbf{H}_{11},\textbf{H}_{13}$;Agent $2$ knows
$\textbf{H}_{21},\textbf{H}_{41}$;Agent $3$ knows
$\textbf{H}_{32},\textbf{H}_{33},\textbf{H}_{43}$;Agent $4$ knows
$\textbf{H}_{24},\textbf{H}_{44}$;Agent $5$ knows
$\textbf{H}_{51},\textbf{H}_{53},\textbf{H}_{61},\textbf{H}_{62}$;b.
Distribution of data

Figure 7: Example of a distributed linear algebraic equation over a network of
$5$ agents.

The sets corresponding to these lists are:
$\mathbb{S}(\mathcal{R}_{1})=\\{1\\}$,
$\mathbb{S}(\mathcal{R}_{2})=\\{2,4\\}$,
$\mathbb{S}(\mathcal{R}_{3})=\\{3\\}$,
$\mathbb{S}(\mathcal{R}_{4})=\\{2,3,4\\}$,
$\mathbb{S}(\mathcal{R}_{5})=\mathbb{S}(\mathcal{R}_{6})=\\{5\\}$, and
$\mathbb{S}(\mathcal{C}^{1})=\\{1,2,5\\}$,
$\mathbb{S}(\mathcal{C}^{2})=\\{3,5\\}$,
$\mathbb{S}(\mathcal{C}^{3})=\\{1,3,5\\}$,
$\mathbb{S}(\mathcal{C}^{4})=\\{4\\}$. Consider the distributed linear
algebraic equation in Fig. 7 and assume that the communication graph of the
multiagent network is given in Fig. 3. It can be verified that Assumption 2 is
satisfied. We have the unknown vector
$\textbf{z}=\textrm{col}\\{\textbf{z}_{1},\textbf{z}_{2},\textbf{z}_{3},\textbf{z}_{4}\\}$
and the coefficient vector
$\textbf{h}=\textrm{col}\\{\textbf{h}_{1},\textbf{h}_{2},\textbf{h}_{3},\textbf{h}_{4},\textbf{h}_{5},\textbf{h}_{6}\\}$.
From agent-index sets corresponding to column partitions, we have
$\bar{\textbf{z}}_{1}=\textrm{col}\\{\textbf{z}_{1}^{(1)},\textbf{z}_{3}^{(1)}\\}$,
$\bar{\textbf{z}}_{2}=\textbf{z}_{1}^{(2)}$,
$\bar{\textbf{z}}_{3}=\textrm{col}\\{\textbf{z}_{2}^{(3)},\textbf{z}_{3}^{(3)}\\}$,
$\bar{\textbf{z}}_{4}=\textbf{z}_{4}^{(4)}$,
$\bar{\textbf{z}}_{5}=\textrm{col}\\{\textbf{z}_{1}^{(5)},\textbf{z}_{2}^{(5)},\textbf{z}_{3}^{(5)}\\}$.
The matrices corresponding in the coupled constraints in (10) are
$\textbf{P}_{12}=\textrm{col}\\{\textbf{I}_{n_{1}},\textbf{0}_{n_{1}\times
n_{3}}\\}$, $\textbf{P}_{21}=\textbf{P}_{25}=\textbf{I}_{n_{1}}$,
$\textbf{P}_{52}=\textrm{col}\\{\textbf{I}_{n_{1}},\textbf{0}_{n_{1}\times(n_{2}+n_{3})}\\}$,
$\textbf{P}_{13}=\textrm{col}\\{\textbf{0}_{n_{3}\times
n_{1}},\textbf{I}_{n_{3}}\\}$,
$\textbf{P}_{31}=\textrm{col}\\{\textbf{0}_{n_{3}\times
n_{2}},\textbf{I}_{n_{3}}\\}$, $\textbf{P}_{35}=\textbf{I}_{n_{2}+n_{3}}$ and
$\textbf{P}_{53}=\textrm{col}\\{\textbf{0}_{(n_{2}+n_{3})\times
n_{1}},\textbf{I}_{n_{2}+n_{3}}\\}$.

For the row partition $k\in\\{1,3,5,6\\}$, the set
$\mathbb{S}(\mathcal{R}_{k})$ has only one agent. Then we have
$\bar{\textbf{A}}_{1,1}=\textrm{blkcol}\\{\textbf{H}_{11},\textbf{H}_{13}\\}$,
$\bar{\textbf{a}}_{1,1}=\textbf{h}_{1}$;
$\bar{\textbf{A}}_{3,3}=\textrm{blkcol}\\{\textbf{H}_{32},\textbf{H}_{33}\\}$,
$\bar{\textbf{a}}_{3,3}=\textbf{h}_{3}$;
$\bar{\textbf{A}}_{5,5}=\textrm{blkcol}\\{\textbf{H}_{51},\textbf{0},\textbf{H}_{53}\\}$,
$\bar{\textbf{a}}_{5,5}=\textbf{h}_{5}$ and
$\bar{\textbf{A}}_{5,6}=\textrm{blkcol}\\{\textbf{H}_{61},\textbf{H}_{62},\textbf{0}\\}$,
$\bar{\textbf{a}}_{5,6}=\textbf{h}_{6}$. The coupling row partition set is
$\mathbb{M}=\\{2,4\\}$. As $\mathbb{S}(\mathcal{R}_{2})=\\{2,4\\}$, two agents
$2$ and $4$ know respectively $\bar{\textbf{B}}_{2,2},\bar{\textbf{b}}_{2,2}$
and $\bar{\textbf{B}}_{4,2},\bar{\textbf{b}}_{4,2}$ where
$\bar{\textbf{B}}_{2,2}=\textbf{H}_{21}$,
$\bar{\textbf{B}}_{4,2}=\textbf{H}_{24}$ and
$\bar{\textbf{b}}_{2,2}+\bar{\textbf{b}}_{4,2}=\textbf{h}_{2}$. Agent $2$ has
the local variables $\textbf{u}_{2}^{(2)},\textbf{v}_{24,2}$ and agent $4$ has
the local variables $\textbf{u}_{2}^{(4)},\textbf{v}_{42,2}$. Similarly, for
the row partition $3$, agents $2$ knows
$\textbf{u}_{4}^{(2)},\textbf{v}_{24,4},\bar{\textbf{B}}_{2,4},\bar{\textbf{b}}_{2,4}$,
agents $3$ knows
$\textbf{u}_{4}^{(3)},\textbf{v}_{34,4},\bar{\textbf{B}}_{3,4},\bar{\textbf{b}}_{3,4}$
and agents $4$ knows
$\textbf{u}_{4}^{(4)},\textbf{v}_{42,4},\textbf{v}_{43,4},\bar{\textbf{B}}_{4,4},\bar{\textbf{b}}_{4,4}$.
In which $\bar{\textbf{B}}_{2,4}=\textbf{H}_{41}$,
$\bar{\textbf{B}}_{3,4}=\textrm{blkcol}\\{\textbf{0},\textbf{H}_{43}\\}$,
$\bar{\textbf{B}}_{4,4}=\textbf{H}_{44}$ and
$\bar{\textbf{b}}_{2,4}+\bar{\textbf{b}}_{3,4}+\bar{\textbf{b}}_{4,4}=\textbf{h}_{4}$.

Finally, we summarize the local information for each agent as follows. Agent
$1$ knows $\bar{\textbf{z}}_{1}$, $\textbf{P}_{12}$, $\textbf{P}_{13}$,
$\textbf{A}_{1}=\bar{\textbf{A}}_{1,1}$ and
$\textbf{a}_{1}=\bar{\textbf{a}}_{1,1}$; Agent $2$ knows
$\bar{\textbf{z}}_{2}$, $\textbf{P}_{21}$, $\textbf{P}_{25}$,
$\bar{\textbf{u}}_{2}=\textrm{col}\\{\textbf{u}_{2}^{(2)},\textbf{u}_{4}^{(2)}\\}$,
$\bar{\textbf{v}}_{2}=\textrm{col}\\{\textbf{v}_{24,2},\textbf{v}_{24,4}\\}$,
$\bar{\textbf{B}}_{2,2}$, $\bar{\textbf{b}}_{2,2}$, $\bar{\textbf{B}}_{2,4}$,
$\bar{\textbf{b}}_{2,4}$; Agent $3$ knows $\bar{\textbf{z}}_{3}$,
$\textbf{A}_{3}=\bar{\textbf{A}}_{3,3}$,
$\textbf{a}_{3}=\bar{\textbf{a}}_{3,3}$, $\textbf{P}_{31}$, $\textbf{P}_{35}$,
$\bar{\textbf{u}}_{3}=\textbf{u}_{4}^{(3)}$,
$\bar{\textbf{v}}_{3}=\textbf{v}_{34,2}$, $\bar{\textbf{B}}_{3,4}$,
$\bar{\textbf{b}}_{3,4}$; Agent $4$ knows $\bar{\textbf{z}}_{4}$,
$\bar{\textbf{u}}_{4}=\textrm{col}\\{\textbf{u}_{2}^{(4)},\textbf{u}_{4}^{(4)}\\}$,
$\bar{\textbf{v}}_{4}=\textrm{col}\\{\textbf{v}_{42,2},\textbf{v}_{42,4},\textbf{v}_{43,4}\\}$,
$\bar{\textbf{B}}_{4,2}$, $\bar{\textbf{b}}_{4,2}$, $\bar{\textbf{B}}_{4,4}$,
$\bar{\textbf{b}}_{4,4}$; Agent $5$ knows $\bar{\textbf{z}}_{5}$,
$\textbf{P}_{52}$, $\textbf{P}_{53}$,
$\textbf{A}_{5}=\textrm{blkcol}\\{\bar{\textbf{A}}_{5,5},\bar{\textbf{A}}_{5,6}\\}$
and
$\textbf{a}_{5}=\textrm{blkcol}\\{\bar{\textbf{a}}_{5,5},\bar{\textbf{a}}_{5,6}\\}$.

## References

  * [1] S. Mou, J. Liu, and A. S. Morse, “A distributed algorithm for solving a linear algebraic equation,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 11, pp. 2863–2878, 2015.
  * [2] S. Mou, Z. Lin, L. Wang, D. Fullmer, and A. S. Morse, “A distributed algorithm for efficiently solving linear equations and its applications (special issue jcw),” _Systems & Control Letters_, vol. 91, pp. 21–27, 2016.
  * [3] O. Cihan, “Rapid solution of linear equations with distributed algorithms over networks,” _IFAC-PapersOnLine_ , vol. 52, no. 25, pp. 467–471, 2019.
  * [4] J. Liu, A. S. Morse, A. Nedic, and T. Basar, “Exponential convergence of a distributed algorithm for solving linear algebraic equations,” _Automatica_ , vol. 83, pp. 37–46, 2017.
  * [5] G. Shi, B. D. O. Anderson, and U. Helmke, “Network flows that solve linear equations,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 6, pp. 2659–2674, 2017.
  * [6] J. Liu, S. Mou, and A. S. Morse, “Asynchronous distributed algorithms for solving linear algebraic equations,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 2, pp. 372–385, 2018.
  * [7] J. Liu, X. Chen, T. Basar, and A. Nedic, “A continuous-time distributed algorithm for solving linear equations,” in _Proc. of the 2016 American Control Conference (ACC)_ , 2016.
  * [8] X. Wang, J. Zhou, S. Mou, and M. J. Corless, “A distributed algorithm for least squares solutions,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 10, pp. 4217–4222, 2019.
  * [9] Y. Liu, C. Lageman, B. O. D. Anderson, and G. Shi, “An arrow–hurwicz–uzawa type flow as least squares solver for network linear equations,” _Automatica_ , vol. 100, pp. 187–193, 2019.
  * [10] T. Yang, J. George, J. Qin, X. Yi, and J. Wu, “Distributed least squares solver for network linear equations,” _Automatica_ , vol. 113, 2020.
  * [11] M. Jahvani and M. Guay, “A distributed least-squares solver for linear systems of algebraic equations,” _IFAC-PapersOnLine_ , vol. 55, no. 7, pp. 804–808, 2022.
  * [12] P. Wang, Y. Cao, N. Yu, W. Ren, J. Lian, and D. Wu, “Distributed and communication-efficient solutions to linear equations with special sparse structure,” _System & Control Letters_, vol. 160, 2022.
  * [13] B. Gharesifard and J. Cortes, “Distributed continuous-time convex optimization on weight-balanced digraphs,” _IEEE Transactions on Automatic Control_ , vol. 59, no. 3, pp. 781–786, 2014.
  * [14] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 3, pp. 1245–1260, 2017.
  * [15] B. He and X. Yuan, “On non-ergodic convergence rate of douglas–rachford alternating direction method of multipliers,” _Numer. Math._ , vol. 130, pp. 567 – 577, 2015.
  * [16] X. Pan, Z. Liu, and Z. Chen, “Linear convergence of admm under metric subregularity for distributed optimization,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 4, pp. 2513–2520, April 2023.
  * [17] X. Wang, S. Mou, and B. O. D. Anderson, “Scalable, distributed algorithms for solving linear equations via double-layered networks,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 3, pp. 1132–1143, 2020.