Network Flows that Solve Linear Equations
Guodong Shi, Brian D. O. Anderson and Uwe Helmke∗†‡§

Abstract

arXiv:1510.05176v3 [] 20 Sep 2016

We study distributed network flows as solvers in continuous time for the linear algebraic equation
z = Hy. Each node i has access to a row hT
i of the matrix H and the corresponding entry zi in
the vector z. The first “consensus + projection” flow under investigation consists of two terms, one
from standard consensus dynamics and the other contributing to projection onto each affine subspace
specified by the hi and zi . The second “projection consensus” flow on the other hand simply replaces
the relative state feedback in consensus dynamics with projected relative state feedback. Without
dwell-time assumption on switching graphs, we prove that all node states converge to a common
solution of the linear algebraic equation, if there is any. The convergence is global for the “consensus
+ projection” flow while local for the “projection consensus” flow in the sense that the initial values
must lie on the affine subspaces. If the linear equation has no exact solutions, we show that the
node states can converge to a ball around the least squares solution whose radius can be made
arbitrarily small through selecting a sufficiently large gain for the “consensus + projection” flow for
a fixed bidirectional graph. Semi-global convergence to approximate least squares solutions is also
demonstrated for switching balanced directed graphs under suitable conditions. It is also shown that
the “projection consensus” flow drives the average of the node states to the least squares solution
with a complete graph. Numerical examples are provided as illustrations of the established results.

1

Introduction

In the past decade, distributed consensus algorithms have attracted a significant amount of research
attention [8–11], due to their wide applications in distributed control and estimation [12,13], distributed
signal processing [14], and distributed optimization methods [15, 16]. The basic idea is that a network
of interconnected nodes with different initial values can reach a common value, namely an agreement
∗
†

A brief version of the current manuscript was presented at the American Control Conference in Boston, July 2016 [1].
G. Shi is with the Research School of Engineering, College of Engineering and Computer Science, The Australian

National University, Canberra 0200, Australia. E-mail: guodong.shi@anu.edu.au.
‡
B. D. O. Anderson is with the National ICT Australia (NICTA) and the Research School of Engineering, College of Engineering and Computer Science, The Australian National University, Canberra 0200, Australia. E-mail:
brian.anderson@anu.edu.au.
§
U. Helmke is deceased but was with Institute of Mathematics, University of Würzburg, 97074 Würzburg, Germany.

1

or a consensus, via local information exchange as long as the communication graph is well connected.
The consensus value is informative in the sense that it can depend on all nodes’ initial states even if the
value is not the exact average [17]; the consensus processes are robust against random or deterministic
switching of network interactions as well as against noises [18–21].
As a generalized notion, constrained consensus seeks to reach state agreement in the intersection of a
number of convex sets, where each set serves as the supporting state space for a particular node [22]. It
was shown that with doubly stochastic arc weights, a projected consensus algorithm, where each node
iteratively projects a weighted average of its neighbor’s values onto its supporting set, can guarantee
convergence to constrained consensus when the intersection set is bounded and contains an interior
point [22]. This idea was then extended to the continuous-time case under which the graph connectivity
and arc weight conditions can be relaxed with convergence still being guaranteed [23]. The projected
consensus algorithm was shown to be convergent even under randomized projections [24]. In fact, those
developments are closely related to a class of so-called alternating projection algorithms, which was
first studied by von Neumann in the 1940s [25] and then extensively investigated across the past many
decades [26–29].
A related but different intriguing problem lies in how to develop distributed algorithms that solve
a linear algebraic equation z = Hy, H ∈ RN ×m , z ∈ RN with respect to variable y ∈ Rm , to which
tremendous efforts have been devoted with many algorithms developed under different assumptions of
information exchanges among the nodes [30–39]. Naturally, we can assume that a node i has access to a
row vector, hT
i of H as well as the corresponding entry, zi in z. Each node will then be able to determine
with straightforward calculations an affine subspace whose elements satisfy the equation hT
i y = zi . This
means that, as long as the original equation z = Hy has a nonempty solution set, solving the equation
would be equivalent to finding a point in the intersection of all the affine subspaces and therefore can
be put into the constrained consensus framework. If however the linear equation has no exact solution
and its least squares solutions are of interest, we ended up with a convex optimization problem with
quadratic cost and linear constraints. Many distributed optimization algorithms, such as [16, 22, 40–46],
developed for much more complex models, can therefore be directly applied. It is worth emphasizing
that the above ideas of distributed consensus and optimization were traced back to the seminal work of
Bertsekas and J. Tsitsiklis [47, 48].
In this paper, we study two distributed network flows as distributed solvers for such linear algebraic
equations in continuous time. The first so-called “consensus + projection” flow consists of two additive
terms, one from standard consensus dynamics and the other contributing to projection onto each affine
subspace. The second “projection consensus” flow on the other hand simply replaces the relative state
feedback in consensus dynamics with projected relative state feedback. Essentially only relative state
information is exchanged among the nodes for both of the two flows, which justifies their full distribut-

2

edness. To study the asymptotic behaviours of the two distributed flows with respect to the solutions of
the linear equation, new challenges arise in the loss of intersection boundedness and interior points for
the exact solution case as well as in the complete loss of intersection sets for the least squares solution
case. As a result, the analysis cannot be simply mapped back to the studies in [22, 23].
The contributions of the current paper are summarized as follows.
• Under mild conditions on the communication graphs (without requiring a dwell-time for switching
graphs and only requiring a positively lower bound on the integral of arc weights over certain time
intervals), we prove that all node states asymptotically converge to a common solution of the linear
algebraic equation for the two flows, if there is any. The convergence is global for the “consensus +
projection” flow, and local for the “projection consensus” flow in the sense that the initial values
must be put into the affine subspaces (which is a very minor restriction indeed). We manage to
characterize the node limits for balanced or fixed graphs.
• If the linear equation has no exact solutions, we show that the node states can be forced to converge
to a ball of fixed but arbitrarily small radius surround the least squares solution by taking the gain
of the consensus dynamics to be sufficiently large for “consensus + projection” flow under fixed and
undirected graphs. Semi-global convergence to approximate least squares solutions is established
for switching balanced directed graphs under suitable conditions. A minor, but more explicit result
arises where it is also shown that the “projection consensus” flow drives the average of the node
states to the least squares solution with complete communication graphs.
These results rely on our development of new technique of independent interest for treating the interplay between consensus dynamics and the projections onto affine subspaces in the absence of intersection
boundedness and interior point assumptions. All the convergence results can be sharpened to provide
exponential convergence with suitable conditions on the switching graph signals.
The remainder of this paper is organized as follows. Section 2 introduces the network model, presents
the distributed flows under consideration, and defines the problem of interest. Section 3 discusses the
scenario where the linear equation has at least one solution. Section 4 then turns to the least squares case
where the linear equation has no solution at all. Finally, Section 5 presents a few numerical examples
illustrating the established results and Section 6 concludes the paper with a few remarks.

Notation and Terminology
A directed graph (digraph) is an ordered pair of two sets denoted by G = (V, E) [2]. Here V = {1, . . . , N }
is a finite set of vertices (nodes). Each element in E is an ordered pair of two distinct nodes in V, called
an arc. A directed path in G with length k from v1 to vk+1 is a sequence of distinct nodes, v1 v2 . . . vk+1 ,
such that (vm , vm+1 ) ∈ E, for all m = 1, . . . , k. A digraph G is termed strongly connected if for any two
3

distinct nodes i, j ∈ V, there is a path from i to j. A digraph is called bidirectional when (i, j) ∈ E if and
only if (j, i) ∈ E for all i and j. A strongly connected bidirectional digraph is simply called connected.
All vectors are column vectors and denoted by bold, lower case letters, i.e., a, b, c, etc.; matrices are
denoted with bold, upper case letters, i.e., A, B, C, etc.; sets are denoted with A, B, C, etc. Depending
on the argument, | · | stands for the absolute value of a real number or the cardinality of a set. The
Euclidean inner product between two vectors a and b in Rm is denoted as ha, bi, and sometimes simply
aT b. The Euclidean norm of a vector is denoted as k · k.

2

Problem Definition

2.1

Linear Equations

Consider the following linear algebraic equation:
z = Hy

(1)

with respect to variable y ∈ Rm , where H ∈ RN ×m and z ∈ RN . We know from the basics of linear
algebra that overall there are three cases.
(I) There exists a unique solution satisfying Eq. (1): rank(H) = m and z ∈ span(H).
(II) There is an infinite set of solutions satisfying Eq. (1): rank(H) < m and z ∈ span(H).
(III) There exists no solution satisfying Eq. (1): z ∈
/ span(H).
We denote







hT
 1

 T
 h2 

H=
 ..  ,
 . 
 
hT
N



z
 1
 
 z2 

z=
 .. 
 . 
 
zN

with hT
i being the i-th row vector of H. For the ease of presentation and with inessential loss of generality
we assume throughout the rest of the paper that
hi = 1, i = 1, . . . , N.
Introduce
n
o
Ai := y : hT
i y = zi
for each i = 1, . . . , N , which is an affine subspace. It is then clear that Case (I) is equivalent to the
T
condition that A := N
i=1 Ai is a singleton, and that Case (II) is equivalent to the condition that
4

A :=

TN

i=1 Ai

is an affine space with a nontrivial dimension. For Case (III), a least squaress solution of

(1) can be defined via the following optimization problem:
min z − Hy

y∈Rm

2

,

(2)

which yields a unique solution y? = (HT H)−1 Hz if rank(H) = m.

Consider a network with nodes indexed in the set V = 1, . . . , N . Each node i has access to the value
of hi and zi without the knowledge of hj or zj from other nodes. Each node i holds a state xi (t) ∈ Rm
and exchanges this state information with other neighbor nodes, these being determined by the edges of
the graph of the network. We are interested in distributed flows for the xi (t) that asymptotically solve
the equation (1), i.e., xi (t) approaches some solution of (1) as t grows.

2.2

Network Communication Structures

Let Θ denote the set of all directed graphs associated with node set V. Node interactions are described

by a signal σ(·) : R≥0 7→ Θ. The digraph that σ(·) defines at time t is denoted as Gσ(t) = V, Eσ(t) ,
where Eσ(t) is the set of arcs. The neighbor set of node i at time t, denoted Ni (t), is given by
n
o
Ni (t) := j : (j, i) ∈ Eσ(t) .
This is to say, at any given time t, node i can only receive information from the nodes in the set Ni (t).
Let R≥0 and R+ be the sets of nonnegative and positive real numbers, respectively. Associated with
each ordered pair (j, i) there is a function aij (·) : R≥0 → R+ representing the weight of the possible
connection (j, i). We impose the following assumption, which will be adopted throughout the paper
without specific further mention.
Weights Assumption. The function aij (·) is continues except for at most a set with measure zero over
R≥0 for all i, j ∈ V; there exists a∗ > 0 such that aij (t) ≤ a∗ for all t ∈ R≥0 and all i, j ∈ V.
Denote I(j,i)∈Eσ(t) as an indicator function for all i 6= j ∈ V, where I(j,i)∈Eσ(t) = 1 if (j, i) ∈ Eσ(t)
and I(j,i)∈Eσ(t) = 0 otherwise. We impose the following definition on the connectivity of the network
communication structures.
Definition 1

(i) An arc (j, i) is said to be a δ-arc of Gσ(t) for the time interval [t1 , t2 ) if
Z t2
aij (t)I(j,i)∈Eσ(t) dt ≥ δ.
t1

(ii) Gσ(t) is δ-uniformly jointly strongly connected (δ-UJSC) if there exists T > 0 such that the δ-arcs
of Gσ(t) on time interval [s, s + T ) form a strongly connected digraph for all s ≥ 0;
(iii) Gσ(t) is δ-bidirectionally infinitely jointly connected (δ-BIJC) if Gσ(t) is bidirectional for all t ≥ 0
and the δ-arcs of Gσ(t) on time interval [s, ∞) form a connected graph for all s ≥ 0.
5

Figure 1: An illustration of the “consensus + projection” flow (left) and the “projection consensus” flow
(right). The blue arrows mark the vector of ẋi for the two flows, respectively.

2.3

Distributed Flows

Define the mapping PAi : Rm → Rm as the projection onto the affine subspace Ai . Let K > 0 be a given
constant. We consider the following continuous-time network flows:
[“Consensus + Projection” Flow]:
ẋi = K

 X

aij (t) xj − xi



+ PAi (xi ) − xi , i ∈ V;

(3)

j∈Ni (t)

[“Projection Consensus” Flow]:
ẋi =

X


aij (t) PAi (xj ) − PAi (xi ) , i ∈ V.

(4)

j∈Ni (t)

The first term of (3) is a standard consensus flow [8], while along
ẋi = PAi (xi ) − xi ,

(5)

xi (t) will be asymptotically projected onto Ai since (5) is a gradient flow with PAi (v) − v = −∇kvk2Ai /2,
where ∇kvk2Ai is a C ∞ convex function. The flow (4) simply replaces the relative state in standard
consensus flow with relative projective state.
Notice that a particular equilibrium point of these equations is given by x1 = x2 = · · · = xN = y,
where y is a solution of Eq. (1). The aim of the two flows is to ensure that the xi (t) asymptotically tend
to a solution of Eq. (1). Note that, the projection consensus flow (4) can be rewritten as1
ẋi = PAi

 X


X
aij (t)(xj − xi ) −
aij (t) · PAi (0).

j∈Ni (t)
1

j∈Ni (t)

A rigorous treatment will be given later in Lemma 4.

6

Therefore, in both of the “consensus + projection” and the “projection consensus” flows, a node i
essentially only receives the information
X


aij (t) xj (t) − xi (t)

j∈Ni (t)

from its neighbors, and the flows can then be utilized in addition with the hi and zi it holds. In this way,
the flows (3) and (4) are distributed.
T
T
Without loss of generality we assume the initial time is t0 = 0. We denote by x(t) = (xT
1 (t) · · · xN (t))

a trajectory along any of the two flows.

2.4
2.4.1

Discussions
Geometries

The two network flows are intrinsically different in their geometries. In fact, the “consensus + projection”
flow is a special case of the optimal consensus flow proposed in [23] consisting of two parts, a consensus
part and another projection part. The “projection consensus” flow, first proposed and studied in [39]
for fixed bidirectional graphs, is the continuous-time analogue of the projected consensus algorithm
proposed in [22]. Because it is a gradient descent on a Riemannian manifold if the communication graph
is undirected and fixed, there is guaranteed convergence to an equilibrium point. The two flows are
closely related to the alternating projection algorithms, first studied by von Neumann in the 1940s [25].
We refer to [29] for a thorough survey on the developments of alternating projection algorithms. We
illustrate the intuitive difference between the two flows in Figure 1.
2.4.2

Relation with Previous Work

The dynamics described in systems (3) and (4) are linear, in contrast to the nonlinear dynamics associated
with the general convex sets studied in [22,23]. However, we would like to emphasize that new challenges
arise with the systems (3) and (4) compared to the work of [22, 23]. First of all, for both of the Cases (I)
T
and (II), A := N
i=1 Ai contains no interior point. This interior point condition however is essential to
T
the results in [22]. Next, for Case (II) where A := N
i=1 Ai is an affine space with a nontrivial dimension,
the boundedness condition for the intersection of the convex sets no longer holds, which plays a key role
T
in the analysis of [22, 23]. Finally, for Case (III), A := N
i=1 Ai becomes an empty set. The least squares
solution case then completely falls out from the discussions of constrained consensus in [22, 23].
2.4.3

Grouping of Rows

We have assumed hitherto that each node i only has access to the value of hi and zi from the equation
(1) and therefore there are a total of N nodes. Alternatively and as a generalization, there can be
7

n ≤ N nodes with node i holding ni ≥ 1 rows, denoted (hi(1) zi(1) ), . . . , (hi(ni ) zi(ni ) ) of (H z) with
i(k) ∈ {1, . . . , Z}. In this case, we can revise the definition of Ai to
n
o
Ai := y : hT
y
=
z
,
k
=
1,
.
.
.
,
n
,
i
i(k)
i(k)
which is nonempty if (1) has at least one solution. Then the two flows (3) and (4) can be defined in the
same manner for the n nodes. Of course, if ni is large, finding an initial condition consistent with Ai
becomes computationally more burdensome.
Let2
Sn 
i=1


i(1), . . . , i(ni ) = 1, . . . , Z .

Note that, the Ai are still affine subspaces, while solving (1) exactly continues to be equivalent to finding
T
a point in ni=1 Ai . Consequently, all our results for Cases (I) and (II) apply also to this new setting with
row grouping.

3

Exact Solutions

In this section, we show how the two distributed flows asymptotically solve the equation (1) under quite
general conditions for Cases (I) and (II).

3.1

Singleton Solution Set

We first focus on the case when Eq. (1) admits a unique solution y∗ , or equivalently,
A :=

TN

i=1 Ai

= {y∗ }

is a singleton. For the “consensus + projection” flow (3), the following theorem holds.
Theorem 1 Let (I) hold. Then along the “consensus + projection” flow (3), there holds
lim xi (t) = y∗ , ∀i ∈ V

t→∞

for all initial values if Gσ(t) is either δ-UJSC or δ-BIJC.
The “projection consensus” flow (4), however, can only guarantee local convergence for a particular
set of initial values. The following theorem holds.
Theorem 2 Let (I) hold. Suppose xi (0) ∈ Ai for all i. Then along the “projection consensus” flow (4),
there holds
lim xi (t) = y∗ , ∀i ∈ V

t→∞

if Gσ(t) is either δ-UJSC or δ-BIJC.
2


Note that, it is not necessary to require the i(1), . . . , i(ni ) to be disjoint.

8

Remark 1 Convergence along the “projection consensus” flow relies on specific initial values due to the
existence of equilibriums other than the desired consensus states within the set A: if xi (0) are all equal,
then obviously they will stay there for ever along the flow (4). It was suggested in [39] that one can add
another term in the “projection consensus” flow and arrive at
X

ẋi =


aij (t) PAi (xj ) − PAi (xi ) + PAi (xi ) − xi

(6)

j∈Ni (t)

for i ∈ V, then convergence will be global under (6). We would like to point out that (6) has a similar
structure as the “consensus + projection” flow with the consensus dynamics being replaced by projection
consensus. In fact, our analysis of the “consensus + projection” flow developed in this paper can be
refined and generalized to the flow (6) and then leads to results under the same graph conditions for both
exact and least squares solutions.

3.2

Infinite Solution Set

We now turn to the scenario when Eq. (1) has an infinite set of solutions, i.e., A :=

TN

i=1 Ai

is an affine

space with a nontrivial dimension. We note that in this case A is no longer a bounded set; nor does it
contain interior points. This is in contrast to the situation studied in [22, 23].
For the “consensus + projection” flow (3), we present the following result.
Theorem 3 Let (II) hold. Then along the “consensus + projection” flow (3) and for any initial value
x(0), there exists y[ (x(0)), which is a solution of (1), such that
lim xi (t) = y[ (x(0)), ∀i ∈ V

t→∞

if Gσ(t) is either δ-UJSC or δ-BIJC.
For the “projection consensus” flow, convergence relies on restricted initial nodes states.
Theorem 4 Let (II) hold. Then along the ‘projection consensus” flow (4) and for any initial value x(0)
with xi (0) ∈ Ai for all i, there exists y[ (x(0)), which is a solution of (1), such that
lim xi (t) = y[ (x(0)), ∀i ∈ V

t→∞

if Gσ(t) is either δ-UJSC or δ-BIJC.

3.3

Discussion: Convergence Speed/The Limits

For any given graph signal Gσ(t) , the value of y[ (x(0)) in Theorems 3 and 4 depends only on the initial
value x(0). We manage to provide a characterization to y[ (x(0)) for balanced switching graphs or fixed
graphs. Denote PA as the projection operator over A.
9

Theorem 5 The following statements hold for both the “consensus + projection” and the “projection
consensus” flows.
(i) Suppose Gσ(t) is balanced, i.e.,

P

j∈Ni (t) aij (t)

=

P

i∈Nj (t) aji (t)

for all t ≥ 0 and for all i, j ∈ V.

Suppose in addition that Gσ(t) is either δ-UJSC or δ-BIJC. Then
lim xi (t) =

t→∞

N
X

PA xi (0) /N, ∀i ∈ V.


i=1

(ii) Suppose Gσ(t) ≡ G§ for some fixed, strongly connected, digraph G§ and for any i, j ∈ V, aij (t) ≡ a§ij
P
for some constant a§ij . Let w := (w1 . . . wN )T with N
i=1 wi = 1 be the left eigenvector corresponding
to the simple eigenvalue zero of the Laplacian3 L§ of the digraph G§ . Then we have
lim xi (t) =

t→∞

N
X


wi PA xi (0) , ∀i ∈ V.

i=1

Due to the linear nature of the systems (3) and (4), it is straightforward to see that the convergence
stated in Theorems 1, 2, 3 and 4 is exponential if Gσ(t) is periodic and δ-UJSC. It is however difficult
to provide tight approximations of the exact convergence rates because of the general structure with
switching interactions adopted by our network model. For time-invariant networks with constant edge
weights, the two flows become linear time-invariant, and then the convergence rate is determined by the
spectrum of the state transition matrix: the rate of convergence for the “consensus + projection” flow is
determined together by both the graph Laplacian and the structure of the linear manifolds Ai and one
in fact cannot dominate another; the rate of convergence for the “projection consensus” flow is upper
bounded by the smallest nonzero eigenvalue of the graph Laplacian [39].

3.4

Preliminaries and Auxiliary Lemmas

Before presenting the detailed proofs for the stated results, we recall some preliminary theories from
affine subspaces, convex analysis, invariant sets, and Dini derivatives, as well as a few auxiliary lemmas
which will be useful for the analysis.
3.4.1

Affine Spaces and Projection Operators

An affine space is a set X that admits a free transitive action of a vector space V. A set K ⊂ Rd is said
to be convex if (1 − λ)x + λy ∈ K whenever x ∈ K, y ∈ K and 0 ≤ λ ≤ 1 [4]. For any set S ⊂ Rd , the
intersection of all convex sets containing S is called the convex hull of S, denoted by co(S). Let K be a
The Laplacian matrix L§ associated with the graph G§ under the given arc weights is defined as L§ = D§ − A§ where

PN
PN
§
§
§
A§ = [I(j,i)∈E§ a§ij ] and D§ = diag
j=1 I(j,1)∈E§ a1j , . . . ,
j=1 I(j,N )∈E§ aN j . In fact, we have wi > 0 for all i ∈ V if G is
3

strongly connected [6].

10

.
closed convex subset in Rd and denote kxkK = miny∈K kx − yk as the distance between x ∈ Rd and K.
There is a unique element PK (x) ∈ K satisfying kx − PK (x)k = kxkK associated to any x ∈ Rd [3]. The
map PK is called the projector onto K4 . The following lemma holds [3].
Lemma 1 (i) hPK (x) − x, PK (x) − yi ≤ 0,

∀x ∈ Rd , y ∈ K.

(ii) kPK (x) − PK (y)k ≤ kx − yk, ∀x, y ∈ Rd .

(iii) The function kxk2K is continuously differentiable at every x ∈ Rd with ∇kxk2K = 2 x − PK (x) .
3.4.2

Invariant Sets and Dini Derivatives

Consider the following autonomous system
ẋ = f (x),

(7)

where f : Rd → Rd is a continuous function. Let x(t) be a solution of (7) with initial condition x(t0 ) = x0 .
Then Ω0 ⊂ Rd is called a positively invariant set of (7) if, for any t0 ∈ R and any x0 ∈ Ω0 , we have
x(t) ∈ Ω0 , t ≥ t0 , along every solution x(t) of (7).
The upper Dini derivative of a continuous function h : (a, b) → R (−∞ ≤ a < b ≤ ∞) at t is defined
as
D+ h(t) = lim sup
s→0+

h(t + s) − h(t)
.
s

When h is continuous on (a, b), h is non-increasing on (a, b) if and only if D+ h(t) ≤ 0 for any t ∈ (a, b).
Hence if D+ h(t) ≤ 0 for all t ≥ 0 and h(t) is lower bounded then the limit of h(t) exists as a finite
number when t tends to infinity.
The next result is convenient for the calculation of the Dini derivative [7].
Lemma 2 Let Vi (t, x) : R × Rd → R (i = 1, . . . , n) be a continuously differentiable function with respect
to both t and x and V (t, x) = maxi=1,...,n Vi (t, x). Let x(t) be an absolutely continuous function. If
I(t) = {i ∈ {1, 2, . . . , n} : V (t, x(t)) = Vi (t, x(t))} is the set of indices where the maximum is reached at
t, then D+ V (t, x(t)) = maxi∈I(t) V̇i (t, x(t)).
3.4.3

Key Lemmas

The following lemmas, Lemmas 3, 4, 5 can be easily proved using the properties of affine spaces, which
turn out to be useful throughout our analysis. We therefore collect them below and the details of their
proofs are omitted.
Lemma 3 Let K := {y ∈ Rm : aT y = b} be an affine subspace, where a ∈ Rm with kak = 1, and
b ∈ R. Denote PK (·) : Rm → K as the projection onto K. Then PK (y) = (I − aaT )y + ba for all y ∈ Rm .
Consequently there holds PK (y − u) = PK (y) − PK (u) + PK (0) for all y, u ∈ Rm .
4

The projections PAi and PA introduced earlier are consistent with this definition.

11

Lemma 4 Let K be an affine subspace in Rm . Take an arbitrary point k ∈ K and define Yk := {y − k :
y ∈ K}, which is a subspace in Rm . Denote PK (·) : Rm → K and PYk (·) : Rm → Yk as the projectors
onto K and Yk , respectively. Then PYk (y − u) = PK (y) − PK (u) for all y, u ∈ Rm .
Lemma 5 Let K1 and K2 be two affine subspaces in Rm with K1 ⊆ K2 . Denote PK1 (·) : Rm → K1 and


PK2 (·) : Rm → K2 as the projections onto K1 and K2 , respectively. Then PK1 (y) = PK1 PK2 (y) , ∀y ∈
Rm .
Lemma 6 Suppose either (I) or (II) holds. Take y] as an arbitrary solution of (1) and let r > 0 be
n
o
arbitrary. Define M] (r) := w ∈ Rm : w − y] ≤ r . Then
N
(i) M] (r)
= M] (r) × · · · × M] (r) is a positively invariant set for the “consensus + projection”
flow (3);
N T

(ii) M] (r)
A1 × · · · × AN is a positively invariant set for the “projection consensus” flow (4).
T
T
]
Proof. Let x(t) = (xT
1 (t) . . . xN (t)) be a trajectory along the flows (3) or (4). Define f (t) := maxi∈V

2
2
.
y] . Denote I(t) := i : f ] (t) = xi (t) − y]

1
2

xi (t)−

(i) From Lemma 2 we obtain that along the flow (3)
E
D
 X

D+ f ] (t) = max xi (t) − y] , K
aij (t) xj (t) − xi (t) + PAi (xi (t)) − xi (t)
i∈I(t)

j∈Ni (t)



D
X

E
a)
T
] 2
]
]
]
= max K
− hi (xi (t) − y )
aij (t) xi (t) − y , xj (t) − y − xi (t) − y
i∈I(t)

j∈Ni (t)



b)

X aij (t) 
≤ max K
xj (t) − y]
2
i∈I(t)
j∈Ni (t)


c)
T
] 2
≤ max − hi (xi (t) − y )

2

− xi (t) − y

] 2



−

hTi (xi (t)

]

−y )

2



i∈I(t)

≤ 0,

(8)

where a) follows from the fact that xi (t)−y] , PAi (xi (t))−xi (t) = − hTi (xi (t)−y] )
3 and the fact that

y]

2

in view of Lemma

is a solution of (1); b) makes use of the elementary inequality

hα, βi ≤ kαk2 + kβk2 /2, ∀α, β ∈ Rm ;

(9)

c) follows from the definition of f ] (t) and I(t).
We therefore know from (8) that f ] (t) is always a non-increasing functions. This implies that, if
N
x(t0 ) ∈ M] (r) , i.e., xi (t0 ) − y] ≤ r for all i, then xi (t) − y] ≤ r for all i and all t ≥ t0 .
N
Equivalently, M] (r)
is a positively invariant set for the flow (3).

12

(ii) Let x(t0 ) ∈ A1 × · · · × AN . The structure of the flow (4) immediately tells that x(t) ∈ A1 × · · · × AN
for all t ≥ t0 . Furthermore, again by Lemma 2 we obtain
D
X
E
aij (t) PAi (xj ) − PAi (xi )
D+ f ] (t) = max xi (t) − y] ,
i∈I(t)

a)

= max
i∈I(t)
b)

= max
i∈I(t)

j∈Ni (t)

D

E
aij (t) xi (t) − y] , I − hi hTi xj (t) − xi (t)

X
j∈Ni (t)


T 
2 


· xj (t) − y] − xi (t) − y]
aij (t) xi (t) − y]
I − hi hTi

X
j∈Ni (t)

 X

 2


 2 
c)
aij (t)  
T
]
T
]
≤ max
− I − hi hi
I − hi hi
xj (t) − y
xi (t) − y
2
i∈I(t)
j∈Ni (t)
 X

d)
aij (t) 
] 2
] 2
xj (t) − y
− xi (t) − y
≤ max
2
i∈I(t)
j∈Ni (t)

≤ 0,

(10)

where a) follows from Lemma 3, b) holds due to the fact that I − hi hTi is a projection matrix, c) is again


based on the inequality (9), and d) holds because xi (t) ∈ Ai (so that I − hi hTi xi (t) − y] = xi (t) − y] )


and that I − hi hTi is a projection matrix (so that I − hi hTi xj (t) − y] ≤ xj (t) − y] ).
N T

We can therefore readily conclude that M] (r)
A1 × · · · × AN is a positively invariant set for
the “projection consensus” flow (4).

3.5



Proofs of Statements

We now have the tools in place to present the proofs of the stated results.
3.5.1

Proof of Theorems 1 and 2

When (I) holds, A :=

TN

i=1 Ai

= {y∗ } is a singleton, which is obviously a bounded set. The “consensus

+ projection” flow (3) is a special case of the optimal consensus flow proposed in [23]. Theorem 1
readily follows from Theorems 3.1 and Theorems 3.2 in [23] by adapting the treatments to the Weights
Assumption adopted in the current paper using the techniques established in [21]. We therefore omit the
details.
Being a special case of Theorem 4, Theorem 2 holds true as a direct consequence of Theorem 4, whose
proof will be presented below.
3.5.2

Proof of Theorem 3

Recall that y] is an arbitrary solution of (1). With Lemma 6, for any initial value x(0), the set
N
M] (max kxi (0)k) ,
i∈V

13

which is obviously bounded, is a positively invariant set for the “consensus + projection” flow (3). Define
A]i := Ai
and A] := A

T

T

M] (max kxi (0)k), i = 1, . . . , N
i∈V

M] (maxi∈V kxi (0)k). As a result, recalling Theorem 3.1 and Theorem 3.2 from [23]5 , if

Gσ(t) is either δ-UJSC or δ-BIJC, there hold
(i) limt→∞ kxi (t)kA] = 0 for all i ∈ V;
(ii) limt→∞ kxi (t) − xj (t)k = 0 for all i and j.
We still need to show that the limits of the xi (t) indeed exist. Introduce
n
o
Si := y : hT
y
=
0
, i∈V
i
and S :=

TN

i=1 Si .

With Lemma 5, we see that





PS PSi (xi − y] ) − PS xi − y] = PS xi − y] − PS xi − y] = 0.

(11)

As a result, taking PS (·) from both the left and right sides of (3)6 , we obtain
d
PS (xi (t) − y] )
dt 


X


=K
aij (t) PS (xj (t) − y] ) − PS (xi (t) − y] ) + PS PSi (xi − y] ) − PS xi − y]
j∈Ni (t)

=K

 X

aij (t) PS (xj (t) − y] ) − PS (xi (t) − y] )



.

(12)

j∈Ni (t)

This is to say, if Gσ(t) is either δ-UJSC or δ-BIJC, we can invoke Theorem 4.1 (for δ-UJSC graphs) and
Theorem 5.2 (for δ-BIJC graphs) in [21] to conclude: for any initial value x(0), there exists p0 (x(0)) ∈ S
such that
lim PS (xi (t) − y] ) = p0 , i = 1, . . . , N.

t→∞

(13)

While on the other hand limt→∞ kxi (t)kA ≤ limt→∞ kxi (t)kA] = 0 leads to
0 = lim xi (t) − PA (xi (t))
t→∞


= lim xi (t) − y] − PA (xi (t)) − y]
t→∞

= lim xi (t) − y] − PS (xi (t) − y] ,
t→∞

(14)

where the last equality follows from Lemma 4. We conclude from (13) and (14) that
lim xi (t) = p0 + y] := y[ (x(0)), i ∈ V.

t→∞

(15)

We have now completed the proof of Theorem 3.
5

Again, the arguments in [23] were based on switching graph signals with dwell time and absolutely bounded weight

functions. We can however borrow the treatments in [21] to the generalized graph and arc weight model considered here
under which we can rebuild the results in [23]. More details will be provided in the proof of Theorem 4.
6
Note that, PS (·) is a projector onto a subspace.

14

3.5.3

Proof of Theorem 4

We continue to use the notation
A]i := Ai
and A] := A

T

T

M] (max kxi (0)k), i = 1, . . . , N
i∈V

M] (maxi∈V kxi (0)k) introduced in the proof of Theorem 3. In view of Lemma 6, for any

initial value x(0),
A]1 × · · · × A]N
is a positively invariant set for the “projection consensus” flow (4). Define
h] (t) := max
i∈V


Let I0 (t) = i : h] (t) = xi (t)
D+ h] (t) = max
i∈I0 (t)

2
A]

1
xi (t)
2

2
.
A]

(16)

. We obtain from Lemma 1.(iii) that

D
X
E
xi (t) − PA] (xi (t)),
aij (t) PAi (xj ) − PAi (xi ) .

(17)

j∈Ni (t)

In (17), the argument used to establish (10) can be carried through when y] is replaced by PA] (xi (t)).
Accordingly, we obtain7 , D+ h] (t) ≤ 0. This immediately implies that there is a constant h§ ≥ 0 such
that limt→∞ h] (t) = h2§ /2. As a result, for any  > 0, there exists T > 0 such that
xi (t)

A]

≤ h§ + , ∀t ≥ T .

(18)

Now that h§ is a nonnegative constant satisfying limt→∞ h] (t) = h2§ /2, we can in fact show that h§ = 0
with suitable graph conditions, as summarized in the following two technical lemmas. Details of their
proofs can be found in the Appendix.
Lemma 7 Let Gσ(t) be δ-UJSC. Then h§ = 0. In fact, h§ = 0 due to the following two contradictive
conclusions:
(i) If h§ > 0, then there holds limt→∞ kxi (t)kA] = h§ for all i ∈ V along the “projection consensus”
flow (4).
(ii) If limt→∞ kxi (t)kA] = h§ for all i ∈ V along the “projection consensus” flow (4), then h§ = 0.

Lemma 8 Suppose Gσ(t) is δ-BIJC. Then h§ = 0 along the “projection consensus” flow (4).
Recall y] ∈ A. Applying PS (·) to both the left and right sides of (4), we have
X

d
PS (xi − y] ) =
aij (t) (PS (xj − y] ) − PS (xi − y] )
dt
j∈Ni (t)

7

Note that the inequalities in (10) hold without relying on the fact that y] is a constant.

15

(19)

where we have used Lemma 4 to derive

PS PAi (xj ) − y] = PA PAi (xj ) − y] = PA (xj ) − y] = PS (xj − y] ).




(20)

We can again make use of the argument in the proof of Theorem 3 and conclude that the limits of the
xi (t) exist and they are obviously the same.
We have now completed the proof of Theorem 4.
3.5.4

Proof of Theorem 5

We provide detailed proof for the “projection+consensus” flow. The analysis for the projection consensus
flow can be similarly established in view of (19).
(i) With (12), we have
 X

d
aij (t) PS (xj (t) − y] ) − PS (xi (t) − y] )
PS (xi (t) − y] ) = K
dt

(21)

j∈Ni (t)

along the “projection+consensus” flow. Note that (21) is a standard consensus flow with arguments
being PS (xi (t) − y] ), i = 1, . . . , N . As a result, there holds
]

lim PS (xi (t) − y ) =

t→∞

=

N
X

PS (xi (0) − y] )/N

i=1
N 
X



PA (xi (0)) − y] /N

i=1

if Gσ(t) is balanced for all t [10]. As a result, similar to (15), we have
lim xi (t) = p0 + y]

t→∞

N 
X

:=

=



PA (xi (0)) − y] /N + y]

i=1
N
X

PA (xi (0))/N, i ∈ V.

(22)

i=1

(ii) If Gσ(t) ≡ G§ for some fixed digraph G§ and for any i, j ∈ V, aij (t) ≡ a§ij for some constant a§ij , then
along (21) we have [10]
lim PS (xi (t) − y] ) =

t→∞

N
X

wi PS (xi (0) − y] ) =

i=1

N
X

wi PA (xi (0)) − y] ,

i=1

where w := (w1 . . . wN )T is the left eigenvector corresponding to eigenvalue zero for the Laplacian matrix
L§ . This immediately gives us
lim xi (t) =

t→∞

N
X

wi PA (xi (0)), i ∈ V,

i=1

which completes the proof.
16

(23)

4

Least Squares Solutions

In this section, we turn to Case (III) and consider that (1) admits a unique least squares solution y? .
Evidently, neither of the two continuous-time distributed flows (3) and (4) in general can yield exact
convergence to the least squares solution of (1) since, even for a fixed interaction graph, y? is not an
equilibrium of the two network flows.
It is indeed possible to find the least squares solution using double-integrator node dynamics [40, 45].
However, the use of double integrator dynamics was restricted to networks with fixed and undirected (or
balanced) communication graphs [40, 45]. In another direction, one can also borrow the idea of the use
of square-summable step-size sequences with infinite sums in discrete-time algorithms [22] and build the
following flow
ẋi = K

 X

aij (t) xj − xi

j∈Ni (t)



+


1
PAi (xi ) − xi ,
t

(24)

for i ∈ V. The least squares case can then be solved under graph conditions of connectedness and
balance [22], but the convergence rate is at best O(1/t). This means (24) will be fragile against noises.
For the “projection+consensus” flow, we can show that under fixed and connected bidirectional interaction graphs, with a sufficiently large K, the node states will converge to a ball around the least
squares solution whose radius can be made arbitrarily small. This approximation is global in the sense
that the required K only depends on the accuracy between the node state limits and the y? .
Theorem 6 Let (III) hold with rank(H) = m and denote the unique least squares solution of (1) as
y? . Suppose Gσ(t) = G§ = (V, E§ ) for some bidirectional, connected graph G§ and for any i, j ∈ V,
aij (t) = aji (t) ≡ a§ij for some constant a§ij . Then along the flow (3), for any  > 0, there exists K∗ () > 0
such that x(∞) := limt→∞ x(t) exists and
xi (∞) − y? ≤ , ∀i ∈ V
for any initial value x(0) if K ≥ K∗ ().
The intuition behind Theorem 6 can be described briefly as follows (see its proof presented later
for a full exposure of this intuition). With fixed and undirected network topology, the “consensus +
projection” flow (3) is a gradient flow in the form of
ẋi = −∇xi DK (x)
where
N

1X
xi
DK (x) :=
2
i=1

2
Ai

+

K
2

17

X
{i,j}∈E§

a§ij xj − xi

2

.

(25)

There holds

PN

2
i=1 kxi kAi

= hT
i xi − zi

2

if each hi is normalized with a unit length. Therefore, for large

K, the trajectory of (3) will asymptotically tend to be close to the solution of the following optimization
problem:
N
X

min

y1 ,...,yN ∈Rm

hT
i yi − zi

2

i=1

y1 = · · · = y N .

s.t.

Any solution of the above problem consists of N copies of the solution to
Hy − z

minm

y∈R

2

which is the unique least squares solution y? = (HT H)−1 Hz if rank(H) = m. Therefore, a large K can
drive the node states to somewhere near y? along the flow (3) as stated in Theorem 6.
Remark 2 (Least Squares Solutions without Normalizing hi ) From the above argument, for the
case when hi is not normalized, we can replace the “consensus + projection” flow (3) with
 X

2
ẋi = K
aij (t) xj − xi − ∇xi hT
i xi − zi /2
j∈Ni (t)

=K

 X

aij (t) xj − xi



− hi hT
i xi − zi



(26)

j∈Ni (t)

for all i ∈ V. The statement of Theorem 6 will continue to hold for the flow (26).
Remark 3 (Tradeoff between Convergence Rate and Accuracy) Under the assumptions of Theorem 6, the flow defines a linear time-invariant system


ẋ = − KL§ ⊗ Im + J x + hz

(27)

T
where L§ is the Laplacian of the graph G§ , J = diag(h1 hT
1 , · · · , hN hN ) is a block-diagonal matrix, and
T T
hz = (z1 hT
1 · · · zN hN ) . Therefore, the rate of convergence is given by


λmin KL§ ⊗ Im + J ,

which is influenced by both L§ (the graph) and J (the linear equation). We also know that λmin KL§ ⊗

Im + J in general cannot grow to infinity by increasing K due to the presence of the zero eigenvalue in
L§ . One can however speed up the convergence by adding a weight γ to the projection term in the flow
(3) and obtain
ẋi = K

 X

aij (t) xj − xi





+ γ PAi (xi ) − xi , i ∈ V.

(28)

j∈Ni (t)

Certainly the convergence rate (to a ball centered at y? with radius ) of (28) can be arbitrarily large by
selecting sufficiently large K and γ. However, it is clear from the proof of Theorem 6 that the required
K for a given accuracy  will in turn depend on γ and require a large K for a large γ.
18

We also manage to establish the following semi-global result for switching but balanced graphs under
two further assumptions.

[A1] The set W(y) := PAiJ · · · PAi1 (y) : i1 , . . . , iJ ∈ V, J ≥ 1 is a bounded set.
P
[A2] N
i=1 PAi (0) = 0.
Theorem 7 Let (III) hold with rank(H) = m and denote the unique least squares solution of (1) as y? .
Assume [A1] and [A2]. Suppose Gσ(t) is balanced for all t ∈ R+ and δ-UJSC with respect to T > 0. Then
for any  > 0 and any x(0) ∈ A1 × · · · × AN , there exist two constants K∗ (, x(0)) > 0 and T∗ (, x(0))
such that when K ≥ K∗ and T ≤ T∗ , there holds
lim sup xi (t) − y? ≤ , ∀i ∈ V
t→∞

along the flow (3) with the initial value x(0).
Remark 4 The two assumptions, [A1] and [A2] are indeed rather strong assumptions. In general, [A1]
T
holds if N
i=1 Ai is a nonempty bounded set [29], which is exactly opposite to the least squares solution
case under consideration. We conjecture that at least for m = 2 case, [A1] should hold when h1 , . . . , hN
are distinct vectors. The assumption [A2] requires a strong symmetry in the affine spaces Ai , which turns
out to be essential for the result to stand.
For the “projection consensus” flow, we present the following result.
Theorem 8 Let (III) hold with rank(H) = m and denote the unique least squares solution of (1) as y? .
Suppose Gσ(t) = G§ is fixed, complete, and aij (t) ≡ a§ > 0 for all i, j ∈ V. Then for any initial value
x(0) ∈ A1 × · · · × AN , there holds
PN
lim

t→∞

i=1 xi (t)

N

= y?

(29)

along the flow (4).
Based on simulation experiments, the requirement that Gσ(t) = G§ does not have to be complete for
the Theorem 8 to be valid for certain choices of the Ai . Moreover, because the flow (4) is a gradient
flow over the manifold A1 × · · · × AN , the xi (t) will converge but perhaps to different limits at different
nodes.

4.1

Proof of Theorem 6

Suppose Gσ(t) = G§ for some bidirectional, connected graph G§ and for any i, j ∈ V, aij (t) = aji (t) ≡ a§ij
for some constant a§ij . Fix  > 0. Note that, we have
X §

K
aij xj − xi + PAi (xi ) − xi = −∇xi DK (x).
j∈Ni

19

(30)

Therefore, the flow (3) is a gradient flow written as
ẋ = −∇DK (x)

where DK (x) is a C ∞ convex function. Denote ZK := x : ∇DK (x) = 0 . There must hold
lim x(t)

t→∞

= 0.

ZK

(31)

The following lemma holds.
Lemma 9 Suppose rank(H) = m. Then
(i) ZK is a singleton, which implies that x(t) converges to a fixed point asymptotically;
(ii)

S

K>κ0 ZK

is a bounded set for all κ0 > 0.

T
Proof. (i) Recall that L§ is the Laplacian of the graph G§ , J = diag(h1 hT
1 , · · · , hN hN ) is a block-diagonal
T T
matrix, and hz = (z1 hT
1 · · · zN hN ) . With Lemma 3, the equation ∇x DK (x) = 0 can be written as

K

X

a§ij (xj − xi ) − hi hT
i xi = zi hi , i ∈ V,

(32)

j∈Ni

or, in a compact form,



KL§ ⊗ Im + J x = −hz .

(33)

Consider


QK (x) := xT KL§ ⊗ Im + J x
=

N
X

hT
i xi

2

2

a§ij xj − xi

X

+K

.

{i,j}∈E§

i=1

We immediately know from the second term of Q that Q(x) = 0 only if x1 = · · · = xN . On the other
hand, obviously
N
X

hT
i w

2

>0

i=1

for any w 6= 0 ∈ Rm if rank(H) = m. Therefore, KL§ ⊗ Im + J is positive-definite, which yields
n 
−1 o
ZK = − KL§ ⊗ Im + J
hz .
(ii) By the Courant-Fischer Theorem (see Theorem 4.2.11 in [5]), we have


λmin KL§ ⊗ Im + J = min QK (x)
kxk=1

= min

kxk=1

X
N

2
hT
i xi

+K

i=1

X
{i,j}∈E

20

a§ij

x j − xi

2


.

(34)

This immediately implies




λmin KL§ ⊗ Im + J ≥ λmin κ0 L§ ⊗ Im + J > 0,
for all K ≥ κ0 and consequently,

S

K>κ0 ZK

(35)

is obviously a bounded set. This proves the desired lemma.


Now we introduce Z∗ :=

S

K≥1 ZK .

T )T with w ∈ Rm and define
Let w = (w1T . . . wN
i

B0 := sup max PAi (wi ) − wi

(36)

C0 := sup max y? − wi

(37)

w∈Z∗ i∈V

and

w∈Z∗ i∈V

with y? being the unique least squares solution of (1). We see that B0 and C0 are finite numbers due to
the boundedness of Z∗ . The remainder of the proof contains two steps.
−1
Step 1. Let v(K) = (v1T (K) . . . vN (K)T ) = − KL§ ⊗ Im + J hz ∈ ZK . Then v satisfies (32), or in
equivalent form,




§
KL ⊗ Im v = 



Denote8 vave (K) =

PN

i=1 vi (K).

T 
T 

v2 − PA2 (v2 ) 
.
..


.
T 
vN − PAN (vN )
v1 − PA1 (v1 )

(38)

Let

n
o
T T
M := w = (w1T . . . wN
) : w1 = · · · = wN .

(39)

be the consensus manifold. Denote λ2 (L§ ) > 0 as the second smallest eigenvalue of L§ . We can now
conclude that
a)

(Kλ2 (L§ ))2 kvk2M ≤ KL§ ⊗ Im v
b)

=

N
X

2

vi − PAi (vi )

2

i=1
c)

≤ N B02

(40)

where a) holds from the fact that the zero eigenvalue of L§ corresponds to a unique unit eigenvector
whose entries are all the same, b) is from (38), and c) holds from the definition of B0 and the fact that
8

In the rest of the proof we sometimes omit K in vi (K), v(K), and vave (K) in order to simplify the presentation. One

should however keep in mind that they always depend on K.

21

v ∈ ZK . This allows us to further derive
§

2

(Kλ2 (L ))

kvk2M

§

2

= (Kλ2 (L ))

N
X

kvi − vave k2 ≤ N B02 ,

(41)

i=1

and then
N
X

kvi − vave k2 ≤

i=1

N B02
.
(Kλ2 (L§ ))2

(42)

Therefore, for any ς > 0 we can find K1 (ς) > 0 that
N
X

vi (K) − vave (K) ≤ ς,

(43)

i=1

for all K ≥ K1 (ς).
Step 2. Applying Lemma 3, we have
U (y) := kz − Hyk2 =

N
X

zi − hT
i y

2

=

i=1

N
X

y

2
.
Ai

(44)

i=1

Then with (43) and noticing the continuity of U (·), for any ς > 0, there exists % > 0 such that
U (vi ) − U (vave ) ≤ ς, i = 1, . . . , N

(45)

if
N
X

vi (K) − vave (K) ≤ %.

(46)

i=1

Consequently, we can conclude without loss of generality9 that for any ς > 0 we can find K1 (ς) > 0 so
that both (43) and (45) hold when K ≥ K1 (ς).
Now noticing 1T L§ = 0, from (38) we have
N
X


vi − PAi (vi ) = 0.

(47)

i=1

Therefore, with (43), we can find another K2 (ς) such that
N
X


vave − PAi (vave ) ≤ ς/C0

(48)

i=1

for all K ≥ K2 (ς).
9

If % ≥ ς then we can replace % with ς in (46) with (45) continuing to hold; if % < ς then both (43) and (45) hold directly.

22

Take K∗ () = max{1, K1 (/2), K2 (/4)}. We can finally conclude that
a)

U (y? ) − U (vi ) ≤ U (y? ) − U (vave ) +


2

b)

≤ ∇U (vave ) · y? − vave +
N
X

c)

=2

i=1
d)

≤


2



vave − PAi (vave ) · y? − vave +
2



· y? − vave +
2C0
2

e)

≤

(49)

for all i ∈ V, where a) is from (45), b) is from the convexity of U , c) is based on direct computation of
∇U in (44), d) is due to (48), and e) holds because y? − vave ≤ C0 from the definition of C0 and vave .
This completes the proof of Theorem 6.

4.2

Proof of Theorem 7

Consider the following dynamics for the considered network model:
q̇i = K

X


aij (t) qj − qi + wi (t), i ∈ V

(50)

j∈Ni (t)

where qi ∈ R, K > 0 is a given constant, aij (t) are weight functions satisfying our standing assumption,
and wi (t) is a piecewise continuous function. The proof is based on the following lemma on the robustness
of consensus subject to noises, which is a special case of Theorem 4.1 and Proposition 4.10 in [21].
Lemma 10 Let Gσ(t) be δ-UJSC with respect to T > 0. Then along (50), there holds that for any  > 0,
there exist a sufficiently small T > 0 and sufficiently large K such that
lim sup qi (t) − qj (t) ≤ kw(t)k∞
t→+∞

for all initial value q 0 when K ≥ K and T ≤ T , where kw(t)k∞ := maxi∈V supt∈[0,∞) |wi (t)|.
With Assumption [A1], the set
∆x(0)

 
 N
SN
:= co
i=1 W(xi (0))

is a compact set, and is obviously positively invariant along the flow (3). Therefore, we can define
n
o
T T
Dx(0) := max sup PAi (ui ) − ui : u = (uT
.
.
.
u
)
∈
∆
x(0) .
1
N
i∈V

as a finite number. Now along the trajectory x(t) of (3), we have

PAi (xi (t)) − xi (t) ≤ Dx(0)
23

for all t ≥ 0 and all i ∈ V. Invoking Lemma 10 we have for any  > 0 and any initial value x(0), there
exist K0 (, x(0)) > 0 and T0 (, x(0)) such that
lim sup xi (t) − xj (t) ≤ , ∀i, j ∈ V
t→∞

if K ≥ K0 and T ≤ T0 .
Furthermore, with Lemma 4, we have


 X
X
 
d
aij (t) PAi (0)
aij (t) PAi (xj ) − PAi (xi ) + 1 + K
PAi (xi ) − xi = K
dt
j∈Ni (t)
j∈Ni (t)

 X
 
aij (t) xj − xi − PAi (xi ) − xi ,
−K

(51)

j∈Ni (t)

which implies
N

N



X
d X
PAi (xi ) − xi = −
PAi (xi ) − xi
dt
i=1

(52)

i=1

if Assumption [A2] holds and Gσ(t) is balanced. While if x(0) ∈ A1 × · · · × AN , then
N 
X



PAi (xi (0)) − xi (0) = 0.

i=1

This certainly guarantees

PN



i=1



PAi (xi (t)) − xi (t) = 0 for all t ≥ 0 in view of (52). The proof for the

fact that
lim sup xi (t) − y? ≤ , i ∈ V
t→∞

can then be built using exactly the same analysis as the final part of the proof of Theorem 6.
We have now completed the proof of Theorem 7.

4.3

Proof of Theorem 8

The proof is based on the following lemma.
Lemma 11 There holds PAm (

PN

i=1 xi /N )

=

PN

i=1

PAm (xi )/N for all m ∈ V.

Proof. From Lemma 4 we can easily know PK (y + u) = PK (y) + PK (u) − PK (0) for all y, u ∈ Rm . As a
result, we have
N
X

PAm (

xi ) = N PAm (

i=1

N
X

xi /N ) − (N − 1)PK (0).

(53)

i=1

On the other hand,
N
X

PAm (

i=1

xi ) =

N
X

PAm (xi ) − (N − 1)PK (0).

i=1

24

(54)

Figure 2: The trajectories of the node states along the “consensus + projection” flow (left) and the
“projection consensus” flow (right).
The desired lemma thus holds.



Suppose Gσ(t) = G§ is fixed, complete, and aij (t) ≡ a§ > 0 for all i, j ∈ V. Now along the flow (4), we
have
d
dt

PN

i=1 xi

N

=

N X
N
X


a§ PAi (xj ) − PAi (xi ) /N

i=1 j=1

=

N X
N
X


a§ PAi (xj ) − xi /N

i=1 j=1
§

N 
X

§

i=1
N 
X

=a

=a

PN

j=1

PAi

PAi (xj )

N
P
 N

i=1

j=1 xj

N

PN
−



−

j=1 xj

N
PN



j=1 xj



N

(55)

for any initial value x(0) ∈ A1 × · · · × AN . The desired result follows straightforwardly and this concludes
the proof of Theorem 8.

5

Numerical Examples

In this section, we provide a few examples illustrating the established results.
Example 1. Consider three nodes in the set {1, 2, 3} whose interactions form a fixed, three-node directed
√
√
cycle. Let m = 2, K = 1, and aij = 1 for all i, j ∈ V. Take h1 = (−1/ 2 1/ 2)T , h2 = (0 1)T ,
√
√
√
√
h1 = (1/ 2 1/ 2)T and z1 = 1/ 2, z2 = 1, z3 = 1/ 2 so the linear equation (1) has a unique solution
at (0, 1) corresponding to Case (I). With the same initial value x1 (0) = (−2 − 1)T , x2 (0) = (5 1)T , and
x3 (0) = (4 − 3)T , we plot the trajectories of x(t), respectively, for the “consensus + projection” flow (3)
25

Figure 3: The trajectories of Ri (t) along the “consensus + projection” flow (left) and the “projection
consensus” flow (right).
and the “projection consensus” flow (4) in Figure 2. The plot is consistent with the result of Theorems
1 and 2.
Example 2. Consider three nodes in the set {1, 2, 3} whose interactions form a fixed, three-node directed
√
√
cycle. Let m = 3, K = 1, and aij = 1 for all i, j ∈ V. Take h1 = (−1/ 2 1/ 2 0)T , h2 = (0 1 0)T ,
√
√
√
√
h1 = (1/ 2 1/ 2 0)T and z1 = 1/ 2, z2 = 1, z3 = 1/ 2 so corresponding to Case (II), the linear
equation (1) admits an infinite solution set
A :=





(
y ∈ R3 :

hT
 1
hT
2

 )
z1T
y=  .
z2T

For the initial value x1 (0) = (1 2 3)T , x2 (0) = (−1 1 2)T , and x3 (0) = (1 0 1)T , we plot the trajectories
of
Ri (t) := xi (t) −

3
X

PA (xi (0))/3 , i = 1, 2, 3

i=1

respectively, for the “consensus + projection” flow (3) and the “projection consensus” flow (4) in Figure
3. The plot is consistent with the result of Theorems 3, 4, and 5.
Example 3. Consider four nodes in the set {1, 2, 3, 4} whose interactions form a fixed, four-node undi√
√
√
√
rected cycle. Let m = 2, and aij = 1 for all i, j ∈ V. Take h1 = (−1/ 2 1/ 2)T , h2 = (1/ 2 1/ 2)T ,
√
√
√
√
√
√
√
√
h3 = (−1/ 2 1/ 2)T , h4 = (1/ 2 1/ 2)T and z1 = 1/ 2, z3 = 1/ 2, z3 = −1/ 2, z3 = −1/ 2
so corresponding to Case (III) the linear equation (1) has a unique least squares solution y? = (0 0).
For the initial value x1 (0) = (0 1)T , x2 (0) = (1 0)T , x3 (0) = (2 1)T , and x4 (0) = (−1 0)T we plot the
trajectories of
EK (t) :=

4
X

xi (t) − y?

i=1

26

2

,

Figure 4: The evolution of EK (t) for K = 1, 5, 100, respectively along the “consensus + projection” flow.
along the “consensus + projection” flow (3) for K = 1, 5, 100, respectively in Figure 4. The plot is
consistent with the result of Theorem 6.

6

Conclusions

Two distributed network flows were studied as distributed solvers for a linear algebraic equation z = Hy,
where a node i holds a row hT
i of the matrix H and the entry zi in the vector z. A “consensus + projection”
flow consists of two terms, one from standard consensus dynamics and the other as projection onto
each affine subspace specified by the hi and zi . Another “projection consensus” flow simply replaces
the relative state feedback in consensus dynamics with projected relative state feedback. Under mild
graph conditions, it was shown that that all node states converge to a common solution of the linear
algebraic equation, if there is any. The convergence is global for the “consensus + projection” flow while
local for the “projection consensus” flow. When the linear equation has no exact solutions but has a
well defined least squares approximate solution, it was proved that the node states can converge to
somewhere arbitrarily near the least squares solution as long as the gain of the consensus dynamics is
sufficient large for “consensus + projection” flow under fixed and undirected graphs. It was also shown
that the “projection consensus” flow drives the average of the node states to the least squares solution
if the communication graph is complete. Numerical examples were provided verifying the established
results. Interesting future direction includes more precise comparisons of the existing continuous-time
or discrete-time linear equation solvers in terms of convergence speed, computational complexity, and
communication complexity.

27

Appendix
A. Proof of Lemma 7. (i)
Suppose h§ > 0. We show limt→∞ kxi (t)kA] = h§ for all i ≥ V by a contradiction argument. Suppose (to
obtain a contradiction) that there exists a node i0 ∈ V with l§ := lim inf t→∞ kxi0 (t)kA] < h§ . Therefore,
we can find a time instant t∗ > T with
s
kxi0 (t∗ )kA] ≤

h2§ + l§2
2

.

(56)

In other words, there is an absolute positive distance between kxi0 (t∗ )kA] and the limit h§ of max∈V kxi (t)kA] .
Let Gσ(t) be δ-UJSC. Consider the N − 1 time intervals [t∗ , t∗ + T ], · · · , [t∗ + (N − 2)T, t∗ + (N − 1)T ].
In view of the arguments in (10), we similarly obtain
d
xi0 (t)
dt

2
A]

D
X
E
ai0 j (t) Pi0 (xj ) − Pi0 (xi0 )
= 2 xi0 (t) − PA] (xi0 (t)),
j∈Ni0 (t)

X

≤

ai0 j (t)



xj (t)

2
A]

− xi0 (t)

2
A]



,

(57)

j∈Ni0 (t)

which leads to
d
xi0 (t)
dt

2
≤
A]

X


ai0 j (t) (h§ + )2 − xi0 (t)

2
A]



(58)

j∈Ni0 (t)

for all t ≥ T noticing (18). Denoting t∗ := t∗ + (N − 1)T and applying Grönwall’s inequality we can
further conclude that
2
A]
Rt P

xi0 (t)

R P


− t
ai j (s)ds
+ 1 − e t∗ j∈Ni0 (s) 0
(h§ + )2
R ∗P
R ∗P


− tt∗
− tt∗
2
j∈Ni (s) ai0 j (s)ds
j∈Ni (s) ai0 j (s)ds
0
0
≤e
xi0 (t∗ ) A] + 1 − e
(h§ + )2

2
≤ µ xi0 (t∗ ) A] + 1 − µ (h§ + )2
µ
µ
· (h§ + )2
≤ · l§2 + 1 −
2
2

≤e

−

t∗

j∈Ni (s)
0

ai0 j (s)ds

xi0 (t∗ )

2
A]

(59)

∗

for all t ∈ [t∗ , t∗ ], where µ = e−(N −1)T a .
Now that Gσ(t) is δ-UJSC, there must be a node i1 6= i0 for which (i0 , i1 ) is a δ-arc over the time

28

interval [t∗ , t∗ + T ). Thus, there holds


X
d
2
2
2
ai1 j (t) xj (t) A] − xi1 (t) A]
xi1 (t) A] ≤
dt
j∈Ni1 (t)

2
= I(i0 ,i1 )∈Eσ(t) ai1 i0 (t) xi0 (t) A] − xi1 (t)

2
A]



+


ai1 j (t) xj (t)

X

2
A]

− xi1 (t)

2
A]

j∈Ni1 (t)\{i0 }

µ

µ
≤ I(i0 ,i1 )∈Eσ(t) ai1 i0 (t)
· l§2 + 1 −
· (h§ + )2 − xi1 (t)
2
2


X
2
ai1 j (t) (h§ + )2 − xi1 (t) A]
+

2
A]


(60)

j∈Ni1 (t)\{i0 }

for t ∈ [t∗ , t∗ + T ]. Noticing the definition of δ-arcs and that kxi1 (t∗ )k2A] ≤ (h§ + )2 , we invoke the
Grönwall’s inequality again and conclude from (60) that


Z
µl§2 − Rtt∗ +T Pj∈N (s) ai1 j (s)ds t∗ +T R t f1 (s)ds
2
∗
i
t
1
f1 (t)dt
e
xi1 (t∗ + T ) A] ≤
e ∗
2
t∗


Z t∗ +T R
R
P
t
µ(h§ + )2
− tt∗∗ +T j∈N (s) ai1 j (s)ds
f
(s)ds
1
i
1
+
e t∗
f1 (t)dt
·
1−e
2
t∗
µγ 2
µγ 
≤
· l§ + 1 −
· (h§ + )2
2
2

(61)

∗

where f1 (t) := I(i0 ,i1 )∈Eσ(t) ai1 i0 (t) and γ = e−T a (1 − e−δ ). This further allows us to apply the estimation
of kxi0 (t∗ + T )k2A] over the interval [t∗ , t∗ ] to node i1 for the interval [t∗ + T, t∗ ] and obtain
xi1 (t∗ + T )

2
A]

≤

µ2 γ 
µ2 γ 2
· l§ + 1 −
· (h§ + )2
2
2

(62)

for all t ∈ [t∗ + T, t∗ ]. Since Gσ(t) is δ-UJSC, the above analysis can be recursively applied to the intervals
[t∗ +T, t∗ +2T ), . . . , [t∗ +(N −2)T, t∗ +(N −1)T ), for which nodes i2 , . . . , iN −1 can be found, respectively,
with V = {i0 , . . . , iN −1 } such that
xim (t∗ )

2
A]

≤

µN −1 γ 2
µN −1 γ 
· l§ + 1 −
· (h§ + )2 ,
2
2

(63)

for m = 0, 1, . . . , N − 1. This implies
h] (t∗ ) ≤

µN −1 γ 
µN −1 γ 2
· l§ /2 + 1 −
· (h§ + )2 /2
2
2

< h2§ /2

(64)

when  is sufficiently small. However, we have known that non-increasingly there holds limt→∞ h] (t) =
h2§ /2, and therefore such i0 does not exist, i.e., limt→∞ kxi (t)kA] = h§ for all i ≥ V. The statement of
Lemma 7. (i) is proved.

B. Proof of Lemma 7. (ii)
Suppose limt→∞ kxi (t)kA] = h§ for all i ≥ V. Then for any  > 0, there exists T̂ > 0 such that
h§ −  ≤ xi (t)

A]

≤ h§ + , ∀t ≥ T̂ .

29

(65)



Moreover, for the ease of presentation we assume that h1 , . . . , hN are distinct vectors since otherwise
we can always combine the nodes with the same hi as a cluster to be treated together in the following
arguments. Denote the angle between the two unit vectors hi 6= hj as βij 6= 0. Then10



= cos(βij ) · xj A] .
xj − PA] xj
I − hi hTi

(66)

This leads to (cf., (10))
D
X
E
d
2
aij (t) PAi (xj ) − PAi (xi )
xi A] = 2 xi (t) − PA] (xi (t)),
dt
j∈Ni∗ (t)
 

 2


 2
X
− I − hi hTi
aij (t)
I − hi hTi
xj (t) − PA] (xj (t))
xi (t) − y]
≤
j∈Ni (t)

≤

X

aij (t)



2

cos(βij ) kxj

2
A]

− kxi

2
A]



j∈Ni (t)

≤

X


aij (t) χ∗ kxj

2
A]

− kxi

2
A]




aij (t)χ∗ kxj

2
A]

− kxi

2
A]



j∈Ni (t)

=

X

X

− (1 − χ∗ )

j∈Ni (t)

aij (t)kxi

2
A]

(67)

j∈Ni (t)
2

< 1 for all t ≥ 0. This will in turn give us
X
X
d
2
xi (t) A] ≤ 2χ∗ 
aij (t) − (1 − χ∗ )
aij (t)kxi (t)
dt

with χ∗ = maxi,j∈V cos(βij )

j∈Ni (t)

2
A]

(68)

j∈Ni (t)

for all t ≥ T̂ . Now we have
Z

∞

X

aij (t)dt = ∞

(69)

T̂ j∈N (t)
i

if Gσ(t) is δ-UJSC. Combining (68) and (69) we arrive at
lim sup xi (t)
t→∞

2
A]

≤

2χ∗
,
1 − χ∗

(70)

which leaves h§ = 0 the only possibility since  can be arbitrary number. This proves Lemma 7. (ii).

C. Proof of Lemma 8
Again without loss of generality we can assume that h1 , . . . , hN are distinct vectors. With (71), we have
N

d X
xi
dt

2
A]

≤

N
X
X


aij (t)χ∗ kxj

2
A]

− kxi

2
A]



i=1 j∈Ni (t)

i=1

− (1 − χ∗ )

N
X
X

aij (t)kxi

2
A]

i=1 j∈Ni (t)

= −(1 − χ∗ )

N
X
i=1

10

Again, note that xj∗ (t) ∈ Aj∗ for all t ≥ 0.

30

bi (t)kxi

2
,
A]

(71)

where bi (t) :=

P

j∈Ni (t) aij (t).

It is easy to see from (71) using a contradiction argument that if Gσ(t) is

δ-BIJC, there must hold
lim

t→∞

N
X

xi

2
A]

= 0.

i=1

Therefore, we conclude that h§ = 0 immediately and this proves the desired lemma.

Acknowledgement
The authors thank Zhiyong Sun for his generous help in the preparation of the numerical examples.

References
[1] G. Shi and B. D. O. Anderson, “Distributed network flows solving linear algebraic equations,”
American Control Conference, Boston, MA, pp. 2864-2869, 2016.
[2] C. Godsil and G. Royle, Algebraic Graph Theory. New York: Springer-Verlag, 2001.
[3] J. Aubin and A. Cellina. Differential Inclusions. Berlin: Speringer-Verlag, 1984.
[4] R. T. Rockafellar. Convex Analysis. New Jersey: Princeton University Press, 1972.
[5] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press. 1985.
[6] M. Mesbahi and M. Egerstedt. Graph Theoretic Methods in Multiagent Networks. Princeton University Press, 2010.
[7] J. Danskin, “The theory of max-min, with applications,” SIAM J. Appl. Math., vol. 14, 641-664,
1966.
[8] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using
nearest neighbor rules,” IEEE Trans. Autom. Control, vol. 48, no. 6, pp. 988-1001, 2003.
[9] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Syst. Contr. Lett., vol. 53,
pp. 65-78, 2004.
[10] R. Olfati-Saber and R. Murray, “Consensus problems in the networks of agents with switching
topology and time delays,” IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1520-1533, 2004.
[11] W. Ren and R. Beard, “Consensus seeking in multi-agent systems under dynamically changing
interaction topologies,” IEEE Trans. Autom. Control, vol. 50, no. 5, pp. 655-661, 2005.

31

[12] S. Martinez, J. Cortés, and F. Bullo, “Motion coordination with distributed information,” IEEE
Control Syst. Mag., vol. 27, no. 4, pp. 75-88, 2007.
[13] S. Kar, J. M. F. Moura and K. Ramanan, “Distributed parameter estimation in sensor networks:
nonlinear observation models and imperfect communication,” IEEE Trans. Information Theory,
58(6), pp. 3575-52, 2012.
[14] A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A Scaglione, “Gossip algorithms for
distributed signal processing,” Proceedings of IEEE, vol. 98, no. 11, pp. 1847-1864, 2010.
[15] M. Rabbat and R. Nowak, “Distributed optimization in sensor networks,” in Proc. IPSN04, pp.
20-27, 2004.
[16] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE
Trans. Autom. Control, vol. 54, no. 1, pp. 48-61, 2009.
[17] B. Golub, and M. O. Jackson, “Naive learning in social networks and the wisdom of crowds,”
American Economic Journal: Microeconomics, 2(1): 112-149, 2010.
[18] L. Moreau, “Stability of multiagent systems with time-dependent communication links,” IEEE
Trans. Automat. Control, 50, pp. 169182, 2005.
[19] Z. Lin, B. Francis, and M. Maggiore, “State agreement for continuous-time coupled nonlinear systems,” SIAM J. Control Optim., vol. 46, no. 1, pp. 288-307, 2007.
[20] A. Tahbaz-Salehi and A. Jadbabaie, “A necessary and sufficient condition for consensus over random
networks,” IEEE Trans. Autom. Control, vol. 53, no. 3, pp. 791-795, 2008.
[21] G. Shi and K. H. Johansson, “Robust consusus for continuous-time multi-agent dynamics,” SIAM
J. Control Optim., vol. 51, no. 5, pp. 3673-3691, 2013.
[22] A. Nedić, A. Ozdaglar and P. A. Parrilo, “Constrained consensus and optimization in multi-agent
networks,” IEEE Trans. Autom. Control, vol. 55, no. 4, pp. 922-938, 2010.
[23] G. Shi, K. H. Johansson and Y. Hong, “Reaching an optimal consensus: dynamical systems that
compute intersections of convex sets,” IEEE Trans. Autom. Control, vol. 58, no.3, pp. 610-622, 2013.
[24] G. Shi and K. H. Johansson, “Randomized optimal consensus of multi-agent systems,” Automatica,
48(12): 3018-3030, 2012.
[25] J. von Neumann, “On rings of operators - reduction theory,” Ann. of Math., 50(2): 401-485, 1949.

32

[26] N. Aronszajn, “Theory of reproducing kernels,” Trans. Amer. Math. Soc., vol. 68, no. 3, pp. 337-404,
1950.
[27] L. G. Gubin, B. T. Polyak, and E. V. Raik, “The method of projections for finding the common point
of convex sets,” U.S.S.R. Computational Mathematics and Mathematical Physics, 7:1-24, 1967.
[28] F. Deutsch, “Rate of convergence of the method of alternating projections,” in Parametric Optimization and Approximation, B. Brosowski and F. Deutsch, Eds.,ol. 76, pp. 96-107, Basel, Switzerland:
Birkhäuser, 1983.
[29] H. H. Bauschke and J. M. Borwein, “On projection algorithms for solving convex feasibility problems,” SIAM Review, Vol. 38, No. 3, pp. 367-426, 1996.
[30] C. Anderson, “Solving linear eqauations on parallel distributed memory architectures by extrapolation,” Technical Report, Royal Institute of Technology, 1997.
[31] R. Mehmood and J. Crowcroft, “Parallel iterative solution method of large sparse linear equation
systems,” Technical Report, University of Cambridge, 2005.
[32] J. Lu and C. Y. Tang, “Distributed asynchronous algorithms for solving positive definite linear
equations over networks - Part II: wireless networks. In Proc first IFAC Workshop on Estimation
and Control of Networked Systems, pages 258-264, 2009.
[33] J. Lu and C. Y. Tang, “Distributed asynchronous algorithms for solving positive definite linear
equations over networks - Part I: agent networks,” In Proc first IFAC Workshop on Estimation and
Control of Networked Systems, pages 22-26, 2009.
[34] J. Liu, S. Mou, and A. S. Morse, “An asynchronous distributed algorithm for solving a linear
algebraic equation,” In Proceedings of the 2013 IEEE Conference on Decision and Control, pp.
5409-5414, 2013.
[35] S. Mou and A. S. Morse, “A fixed-neighbor, distributed algorithm for solving a linear algebraic
equation,” In Proceedings of the 2013 European Control Confrence, pages 2269-2273, 2013.
[36] C. E. Lee, A. Ozdaglar, and D. Shah, “Solving systems of linear equations: locally and asynchronously,” preprint arXiv 1411.2647, 2014.
[37] R. Tutunov, H. B. Ammar, and A. Jadbabaie, “A fast distributed solver for symmetric diagonally
dominant linear equations,” preprint arXiv 1502.03158, 2015.
[38] S. Mou, J, Liu, and A. S. Morse, “A distributed algorithm for solving a linear algebraic equation,”
IEEE Trans. Autom. Control, [Online] in press, 2015.
33

[39] B. D. O. Anderson, S. Mou, A. S. Morse, and U. Helmke, “Decentralized gradient algorithm for
solution of a linear equation,” Numerical Algebra, Control and Optimization, to appear (preprint
arXiv:1509.04538).
[40] J. Wang and N. Elia, “Control approach to distributed optimization,” The 48th Annual Allerton
Conference, pp. 557-561, 2010.
[41] D. Jakovetić, J. Xavier and J. M. F. Moura, “Cooperative convex optimization in networked systems: augmented Lagrangian algorithms with directed gossip communication,” IEEE Trans. Signal
Processing, vol. 59, no. 8, pp. 3889-3902, 2011.
[42] K. Srivastava and A. Nedić, “Distributed asynchronous constrained stochastic optimization,” IEEE
J. Select. Topics Signal Process., vol. 5, no. 4, pp. 772-790, 2011.
[43] K. I. Tsianos and M. G. Rabbat, “Distributed strongly convex optimization,” in the 50th Annual
Allerton Conference on Communication, Control, and Computing, pp. 593-600, 2012.
[44] J. Lu and C. Y. Tang, “Zero-gradient-sum algorithms for distributed convex optimization: the
continuous-time case,” IEEE Trans. Automat. Contr., 57(9): 2348-2354, 2012.
[45] B. Gharesifard and J. Cortés, “Distributed continuous-time convex optimization on weight-balanced
digraphs,” IEEE Trans. Automatic Control, vol. 59, no. 3, pp. 781-786, 2014.
[46] D. Jakovetić, J. M. F. Moura and J. Xavier, “Fast distributed gradient methods,” IEEE Trans.
Automatic Control, 59(5): 1131-1146, 2014.
[47] J. Tsitsiklis, D. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic
gradient optimization algorithms,” IEEE Trans. Autom. Control, vol. 31, no. 9, pp. 803-812, 1986.
[48] D. Bertsekas and J. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Princeton,
NJ: Princeton, 1989.

34

