A Simple Suﬃcient Condition for Convergence ofProjected Consensus Algorithm
Author(s): Norikazu Takahashi and Kosuke Kawashima
Journal: IEEE Control Systems Letters
Volume: 2
Number: 3
Pages: 537–542
Month: July
Year: 2018
DOI: 10.1109/LCSYS.2018.2843679
Published Version: http://ieeexplore.ieee.org/document/8371323

c⃝2018
IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing thismaterial for advertising or promotional purposes, creating new collective works, for resale
orredistribution to servers or lists, or reuse of any copyrighted component of this work in otherworks.

A Simple Sufficient Condition for Convergence ofProjected Consensus Algorithm
Norikazu Takahashi and Kosuke Kawashima

Abstract—This paper studies the convergence property of the
projected consensus algorithm. Under the assumption that i) theintersection of all constraint sets is nonempty, ii) the directed
graph representing the communication among agents is timeinvariant, strongly connected and aperiodic, and iii) the sum of
the weights on incoming edges to each vertex of the graph isone, we prove that the states of all agents converge to a common
point in the intersection of all constraint sets. Our proof does
not need the assumption that every vertex has a self-loop. The
validity of the theoretical analysis is confirmed through numericalexperiments performed for a system of linear equations with
nonnegativity constraints.
Index Terms—Distributed control, decentralized control, optimization algorithms

I. I NTRODUCTIONISTRIBUTED computations by multi-agent networks
such as average consensus [1]–[4], dynamic consensus[5], [6], constrained consensus [7]–[11], distributed formation [12]–[14], distributed optimization [7], [15]–[19], algebraic connectivity estimation [20]–[23] have attracted a great
deal of attention. In these problems, agents are interconnected
over an underlying communication network, and each agent
computes or estimates the value of some global feature only
from the information of itself and the agents in its neighborhood.
In this paper, we focus our attention on the constrained
consensus problem [7], [9] where the states of m agents
have to converge to a common vector in the intersection ofm constraint sets which are closed and convex, under thecondition that agent i only knows the i-th constraint set.
For this problem, Nedić et al. [7] proposed a distributed
algorithm called the projected consensus algorithm, in which
each agent performs the projection onto its constraint set
and the weighted averaging of the states of the agents in
its neighborhood, alternately. They considered the case where
the directed graph, which we call the communication graphin this paper, representing the information exchange among
agents is time-varying, and proved under some assumptions
that a constrained consensus is reached by their algorithm
for any initial condition. The assumptions include the double
stochasticity of the weights and the existence of a positive
lower bound for the weights on self-loops. By the double
stochasticity, we mean that not only the sum of the weights
on incoming edges but also the sum of the weights on

D

This work was partially supported by JSPS KAKENHI Grant Number
JP15K00035.
N. Takahashi and K. Kawashima are with the Graduate
School of Natural Science and Technology, Okayama University,
Okayama 700–8530, Japan (email: takahashi@cs.okayama-u.ac.jp;

kawashima@momo.cs.okayama-u.ac.jp)

outgoing edges from each vertex are one. Recently, Nedić and
Liu [9] proved the convergence of the algorithm under weakerassumptions. In their analysis, the double stochasticity of theweights is relaxed to the single stochasticity, which means that
only the sum of the weights on incoming edges to each vertex
is one. However, the existence of a positive lower bound forthe weights on self-loops is still needed.
The objective of this paper is to show that the abovementioned assumption on the weights on self-loops is notneeded to guarantee the convergence of the projected consensus algorithm when the communication graph is timeinvariant. To be more specific, we prove that the states of
all agents converge to a common vector in the intersectionof all constraint sets under the following assumptions: i)
the intersection of all constraint sets is nonempty, ii) thecommunication graph is time-invariant, strongly connected
and aperiodic, and iii) the sum of the weights on incomingedges to each vertex of the graph is one. A directed graphis said to be aperiodic if the greatest common divisor of
the lengths of cycles is one. For example, if there exists a
vertex having a self-loop then the communication graph is
aperiodic. A key difference between the proof given in thispaper and the one in [9] is that max1≤i≤m {∥xi (k) − x∥}is employed
Lyapunov function in the former∑m as a candidate
i
π
(k)∥x
(k)
−
x∥2 is used in the latter, where
while
i=1 i
i
x (k) is the state of agent i at time k which is expected to converge to a common point in the intersection of m constraints,
x is any vector in the intersection of all constraint sets, andπi (k) are the suitably defined time-varying positive weights1 .
Our Lyapunov function is similar to the one used in [24] wheremulti-agent systems with continuous-time dynamics is studied.
In order to confirm the validity of the theoretical analysis,
we perform some numerical experiments for a system of
linear equations with nonnegativity constraints [25], [26].
In this problem, the projection onto each constraint set iseasily done by using the algorithm presented in [25]. It isshown experimentally that the states of all agents converge
to a common solution vector exponentially if our sufficientcondition is satisfied.
II. P ROJECTED C ONSENSUS A LGORITHM
In what follows, we denote the set of real numbers and theset of nonnegative integers by R and Z+ , respectively. Also,
we use ∥x∥ to denote the Euclidean norm of a vector x. Let
us consider a network of m agents labeled by 1, 2, . . . , m.
Given m closed convex sets X1 , X2 , . . . , Xm ⊆ Rn , we want
1 Note that the communication graph is assumed to be time-varying in [9].
If it is time-invariant, πi (k) become positive constants.

to make agents in the network find a point x ∈ X = ∩mi=1 Xiin a distributed manner. That is, we assume that i) agent i
only knows Xi , ii) agent i has its own state xi ∈ Xi , iii)
agents exchange their states through communication channels,iv) agent i updates its own state xi based on the states of theagents in its neighborhood.
Nedić et al. [7] proposed a distributed algorithm called
the projected consensus algorithm for agents to solve theconstrained consensus problem. When the communication
among agents is time-invariant, their algorithm is describedby{
PXi [si ],if k = 0,i[](1)x (k) =
PXi wi (k − 1) , if k ≥ 1,withwi (k) =m∑

aij xj (k)j=1where x (k) ∈ Xi denotes the state of agent i at timek ∈ Z+ , si ∈ Rn is the seed to determine the initial statexi (0) of agent i, wi (k) ∈ Rn is the weighted average ofthe states of all agents at time k computed by agent i, aij
is a nonnegative number representing the weight of the state
xj (k − 1) in wi (k), PXi [x̄] is the projection of x̄ on Xi , that
is, PXi [x̄] = arg minx∈Xi ∥x̄ − x∥.
As is easily seen from (1), agent i receives information fromagent j if and only if aij > 0. In this sense, the informationexchange or communication among agents is determined by
the values of aij , and can be represented by the directed graph
G = (V, E) where V = {1, 2, . . . , m} is the vertex set, E ={(j, i) | aij > 0} is the edge set. In what follows, this directed
graph is called the communication graph of the multi-agent
network.
As far as (1) is considered, the result of the convergence
analysis done by Nedić et al. [9] can be stated as follows.
Theorem 1: Let the set X = ∩mi=1 Xi be nonempty. If
the three assumptions below are valid then for any seeds
s1 , s2 , . . . , sm there exists a point x ∈ X such thatlimk→∞ xi (k) = x for all i.
∑m i
1)
j=1 aj = 1 for all i.
2) The communication graph G is strongly connected.
3) aii > 0 for all i.
first assumption is natural because wi (k − 1) =
∑The
m
i j
a
j=1 j x (k − 1) can be seen as a weighted average of thestates xj (k − 1) (j = 1, 2, . . . , m). The second assumption is
also natural because agents cannot reach a consensus without
the strong connectivity of the network in general. On the other
hand, it is not clear whether the third assumption is reallyneeded, though it plays an important role in the convergence
analysis of Nedić et al. [9]. In the next section, we showthat the convergence of (1) is guaranteed even if the thirdassumption is not satisfied.
iIII. C ONVERGENCE A NALYSIS
In this section, we prove the convergence of (1) under thefollowing assumption.
Assumption 1: The weights {aij } and the associated communication graph G satisfy the following three conditions.

∑m i1)
j=1 aj = 1 for all i.
2) G is strongly connected.
3) G is aperiodic.
A directed graph is said to be aperiodic if the greatest common divisor of the lengths2 of its cycles is one. For example, if
there exists a vertex having a self-loop then the communicationgraph is aperiodic, because it has a cycle with length one. The
following lemma describes an important property of strongly
connected aperiodic directed graphs, which plays a crucial rolein later analysis.
Lemma 1 (See, for example, [27]): If a directed graph G =(V, E) is strongly connected and aperiodic then there exists a
positive integer r such that there exists a directed walk fromvertex j to vertex i with length r for all (i, j) ∈ V × V .
For∏ a point x ∈ X = ∩mi=1 Xi , we define the functionmfx : i=1 Xi → R as{}fx (x1 (k), x2 (k), . . . , xm (k)) = max ∥xi (k) − x∥ .
1≤i≤m

The left-hand side of this equation is ∏denoted by fx (k) form
simplicity. We also define the set Ω ⊂ i=1 Xi as
{
}
m
∏
1
m
1
m
Ω = (x , . . . , x ) ∈Xi x = · · · = x ∈ X .
i=1

We first give two lemmas regarding the monotonicity of thesequence {fx (k)}∞k=0 .
Lemma 2: Suppose that the first condition in Assumption 1
holds. Let x be any point in X. Then ∥wi (k) − x∥ ≤ fx (k)holds for all i ∈ {1, 2, . . . , m} and k ∈ Z+ . In particular, if
there exist j1 and j2 such that aij1 > 0, aij2 > 0 and xj1 (k) ̸=
xj2 (k) then ∥wi (k) − x∥ < fx (k) holds.
Proof: Using the first condition in Assumption 1 and thestrong convexity of the function g(y) = ∥y∥2 defined on Rn(see also [9, Lemma 5]), we have∥wi (k) − x∥2
=

m
∑

2

aij (xj (k) − x)

j=1

=

m
∑

2

aij xj (k) − x

j=1

−
≤

1 ∑ ∑ i i2a a xj1 (k) − xj2 (k)2 j =1 j =1 j1 j2

m
∑

m

m

1

2

m ∑
m
∑

1
aij fx (k)2 −ai ai xj1 (k) − xj2 (k)2 j =1 j =1 j1 j2

j=1

1

2

2

1 ∑ ∑ i i
2
= fx (k)2 −aj1 aj2 xj1 (k) − xj2 (k)2 j =1 j =1
m

m

1

2

≤ fx (k)2 .
The last inequality holds strictly if there exist j1 and j2 suchthat aij1 > 0, aij2 > 0 and xj1 (k) ̸= xj2 (k).
Lemma 3: Suppose that the first condition in Assumption 1
holds. Let x be any point in X. Then the sequence {fx (k)}∞k=0
is monotone nonincreasing.
2 We are assuming that all edges have length one.

Proof: Because Xi is a closed convex set, ∥PXi [y]−x∥ ≤∥y − x∥ holds for any y ∈ Rn [7]. Taking this inequality andLemma 2 into account, we have{ i}fx (k + 1) = max
x (k + 1) − x
1≤i≤m
{
}
= max
PXi [wi (k)] − x
1≤i≤m
{ i
}
≤ max
w (k) − x1≤i≤m≤fx (k)

which means that {fx (k)}∞k=0 is monotone nonincreasing.
We next give two lemmas to show that if a constrained
consensus is not reached at some time instance then fx (k)strictly decreases within a fixed number of iterations.
Lemma 4: Suppose that the first condition in Assumption 1
holds. Let x be any point in X. Then ∥xi (k+1)−x∥ = fx (k)holds if and only if there exists a vector y such that i) y ∈ Xi ,ii) xj (k) = y for all j with aij > 0 and iii) ∥y − x∥ = fx (k).
Proof: Suppose that there exists a vector y satisfying thethree conditions. Then we have∥xi (k + 1) − x∥ = ∥PXi [wi (k)] − x∥
= ∥PXi [y] − x∥= ∥y − x∥= fx (k).
Suppose next that there does not exist such a vector y. In thiscase, the following three cases have to be considered.
1) There exist j1 and j2 such that aij1 > 0, aij2 > 0 and
xj1 (k) ̸= xj2 (k).
2) There exists a vector y such that xj (k) = y for all jwith aij > 0, but y ̸∈ Xi .
3) There exists a vector y ∈ Xi such that xj (k) = y for
all j with aij > 0, but ∥y − x∥ < fx (k).
In the first case, by Lemma 2, we have∥xi (k + 1) − x∥=

PXi [wi (k)] − x≤ ∥wi (k) − x∥
< fx (k).
In the second case, it follows from [7, Lemma 1 (b)] that∥xi (k + 1) − x∥ = ∥PXi [y] − x∥ < ∥y − x∥ ≤ fx (k). In
the last case, we have ∥xi (k + 1) − x∥ = ∥PXi [y] − x∥ ≤∥y − x∥ < fx (k).
Lemma 5: Suppose that all of the three conditionsin Assumption 1 hold. Let x be any point in X. If(x1 (k ∗ ), x2 (k ∗ ), . . . , xm (k ∗ )) ̸∈ Ω for some k ∗ ∈ Z+ thenfx (k ∗ + r) < fx (k ∗ ) holds, where r is the integer having theproperty given in Lemma 1 for the communication graph.
Proof: Suppose that (x1 (k ∗ ), x2 (k ∗ ), . . . , xm (k ∗ )) ̸∈ Ω
for some k ∗ ∈ Z+ . We prove the inequality fx (k ∗ + r) <fx (k ∗ ) by contradiction. Assume that this is not the case. Then∥xi (k ∗ + r) − x∥ = fx (k ∗ + r) = fx (k ∗ + r − 1) = · · · =fx (k ∗ ) for some i. Using Lemma 4, we can say that xj (k ∗ +r−1) = xi (k ∗ +r) ∈ Xj for all j with aij > 0. This means that∥xj (k ∗ + r − 1) − x∥ = fx (k ∗ + r − 2) for all j with aij > 0.
Using Lemma 4 again, we can say that xj (k ∗ + r − 2) =xi (k ∗ + r) ∈ Xj for all j such that there exists a directed
walk from vertex j to vertex i with length two. Repeating thisargument, we can finally say that xj (k ∗ ) = xi (k ∗ + r) ∈ Xj
for all j such that there exists a directed walk from vertex
j to vertex i with length r. This implies by Lemma 1 thatxj (k ∗ ) = xi (k ∗ + r) ∈ X for all j ∈ V , which contradicts
the assumption that (x1 (k ∗ ), x2 (k ∗ ), . . . , xm (k ∗ )) ̸∈ Ω.
Now we are ready to prove the main result of this paper.
Theorem 2: Let X = ∩mi=1 Xi be nonempty. Suppose that
all of the three conditions in Assumption 1 hold. Then, forany seeds s1 , s2 , . . . , sm , the sequence {(x1 (k), x2 (k), . . . ,xm (k))}∞
k=0 generated by the projected consensus algorithm(1) converges to a point in Ω.
Proof: Let r be the positive integer having the property
given in Lemma 1 for the communication graph. Let the
mapping that maps (x1 (k), x2 (k), . . . , xm (k)) to (x1 (k +r), x2∏(k + r), . . . , ∏xm (k + r)) by using (1) be denoted bymm
A : i=1 Xi → i=1 Xi . Then, the following statements
hold true.
1) The sequence {Al (x1 (0), x2 (0),∏. . . , xm (0))}∞l=0 ismcontained in a bounded subset of i=1 Xi , because it
follows from Lemma 3 thatfx (Al (x1 (0), x2 (0), . . . , xm (0)))≤ fx (x1 (0), x2 (0), . . . , xm (0)){}= max ∥xi (0) − x∥1≤i≤mholds for all l ∈ Z+ .
2) If Al (x1 (0), x2 (0), . . . , xm (0)) ̸∈ Ω thenfx (Al+1 (x1 (0), x2 (0), . . . , xm (0)))< fx (Al (x1 (0), x2 (0), . . . , xm (0))),and if Al (x1 (0), x2 (0), . . . , xm (0)) ∈ Ω then
Al+1 (x1 (0), x2 (0), . . . , xm (0))= Al (x1 (0), x2 (0), . . . , xm (0)).
3) A is continuous because it is a composite mappingof two kinds of continuous mappings: the weighted
averaging and the projection onto a closed convex set.
From
these
observations
andZangwill’s
globalconvergence theorem [28], we can say that the sequence{Al (x1 (0), x2 (0), . . . , xm (0))}∞l=0 generated by (1) has
at least one convergent subsequence and the limitof any convergent subsequence is a point in Ω. Let{Al (x1 (0), x2 (0), . . . , xm (0))}l∈L⊂Z+ be any convergent
subsequence of {Al (x1 (0), x2 (0), . . . , xm (0))}∞l=0 and let(u, u, . . . , u) ∈ Ω be its limit point. Then the corresponding
subsequence {fu (rl)}l∈L of {fu (k)}∞k=0 converges to zero.
Taking this result and Lemma 3 into account, we can conclude
that the entire sequence {fu (k)}∞k=0 converges to zero, whichmeans that {(x1 (k), x2 (k), . . . , xm (k))}∞k=0 converges to(u, u, . . . , u).
The convergence of the algorithm (1) is now guaranteedby Theorem 2. What we need to do next is to determine
the convergence rate. The results given in [9] can be used
when aii > 0 for all i. However, when aii = 0 for some i,

no meaningful conclusion can be drawn by the direct use of
the results in [9]. The analysis of the convergence rate for thiscase is left for a future work.
The extension of our results to multi-agent networks having
switching topology is also an important issue. It is easy to seefrom the proof of Theorem 2 that if the time-varying weights
always satisfy Assumption 1 and each topology lasts at leastr time steps, where r is the integer given in Lemma 1 anddetermined from the topology, then the same conclusion as
Theorem 2 is drawn. However, this condition is too severe.
Further studies are needed to obtain milder condition.

0.3

1

0.3

0.4
0.2
0.1

3

2
0.3

0.4
0.4

0.4

0.1

0.3

0.3
0.2
0.5

0.3

5

4
0.2
0.3

IV. A PPLICATION TO L INEAR E QUATIONS WITH
N ONNEGATIVITY C ONSTRAINTS

Fig. 1. Communication graph of the multi-agent network used for the firstexperiment. Numbers beside directed edges represent weights.

As an example of the constrained consensus problem, we consider the problem of finding a vector x =(x1 , x2 , . . . , xn )T satisfying
Bx = c,x≥0(2)where B = (bij )T ∈ Rm×n is a constant matrix and c ∈ Rm
is a constant vector. The inequality x ≥ 0 means that all
entries of x are nonnegative. Let bi be the i-th row of B and
let Xi ≜ {x ∈ Rn | bi x = ci , x ≥ 0} for i = 1, 2, . . . , m.
Then the problem is equivalent to finding a point in X =∩m
i=1 Xi , and thus can be solved by (1) if X is nonempty.
In order to confirm the validity of the theoretical analysis
in the previous section, we conduct some numerical experiments. Various kinds of methods can be used for computing
PXi [x]. In our experiments, we use the algorithm proposedby Michelot [25], which is described in Algorithm 1, because
it is simple and easy to implement.
Algorithm 1 Projection onto Xi = {x | bi x = ci , x ≥ 0}
Input: x = (x1 , x2 , . . . , xn )T ∈ Rn , bi = (bi1 ,bi2 , . . . , bin ) ∈ Rn and ci ∈ R.
Output: y ∈ {PXi [x], −1} (y = −1 means Xi is empty)
1: Set y ← x.
2: If bi = 0 (then go to Step 5.
)2
2
3: Set y ← I − bTx̂ + ci bT
i bi /∥bi ∥i /∥bi ∥ .
4: If y ≥ 0 then return y and stop.
5: Set J ← {j | yj < 0}.
6: Set yj ← 0 and bij ← 0 for all j ∈ J.
7: If bi ̸= 0 then go to Step 3.
8: If ci ̸= 0 set y ← −1. Return y and stop.
In the first experiment, we consider the situation in which
the problem (2) with


−65
33
28
71
59 −66
 56
29
38 −75 −33
86 


72
−91
73
14
−70
43 
B = 

,
 16
9 −23
63 −62
85 
−21
86
−6
23
56
24
c

=

(−115, 978, 612, 148, 399)T

is solved by a five-agent network. Note that X is nonempty
in this case because x = (5, 4, 8, 0, 2, 4)T is a solution of
Bx = c. The weights on the states are set to
0.3 0.4 0.3 0.0 0.0 11
a1 . . . a5
 0.2 0.4 0.1 0.3 0.0 



 ..
.
.

..
..  = A= .
 0.1 0.3 0.4 0.0 0.2  0.0 0.4 0.0 0.3 0.3 
a51 . . . a55
0.0 0.0 0.3 0.2 0.5
and the entries of the seeds s1 , s2 , . . . , sm are chosen randomly from the interval [−1, 1]. Note that A satisfies allconditions in Assumption 1. The communication graph of themulti-agent network is shown in Fig. 1. It is easy to see thatthe graph is strongly connected.
The results of the first experiment are shown in Fig. 2.
Figure 2 (a) shows the time evolution of ei (k) = ∥Bxi (k) −c∥/∥c∥ for i = 1, 2, . . . , 5. It is clear from the figure thatei (k) converges exponentially to zero for all i. This meansthat each agent eventually finds a vector x satisfying (2).
Figure∑2 (b) shows the time∑evolution of v i (k) = ∥xi (k) −55(1/5) j=1 xj (k)∥/∥(1/5) j=1 xj (k)∥ for i = 1, 2, . . . , 5.
It is clear from the figure that v i (k) also converges exponentially to zero for all i. This means that the states xi (k)(i = 1, 2, . . . , 5) converge to the same value, that is, five agents
eventually reach a consensus.
In the second experiment, we consider the situation in which
the same problem as in the first experiment is solved by adifferent five-agent network. The weights on the states are setto
0.3 0.4 0.3 0.0 0.0
 0.2 0.0 0.5 0.3 0.0 



A=
 0.5 0.3 0.0 0.0 0.2  0.0 0.4 0.0 0.0 0.6 
0.0 0.0 0.3 0.7 0.0
and the entries of the seeds s1 , s2 , . . . , sm are set to thesame values as in the first experiment. The matrix A above
is obtained from the one in the first experiment by setting aii(i = 2, 3, 4, 5) to zero and then by increasing the values ofthe smallest offdiagonal entries in each row so that the first
condition in Assumption 1 is satisfied. The communication

0

0

10

10

i=1
i=2
i=3
i=4
i=5

10-1

10-1
10-2
ei(k)

ei(k)

10-2
-3

10

-3

10

10-4

10-4

10-5

10-5

10-6

i=1
i=2
i=3
i=4
i=5

0

500

1000

1500

2000

2500

10-6

3000

0

500

1000

1500

k

(a)

3000

0

10

10

i=1
i=2
i=3
i=4
i=5

10-1

i=1
i=2
i=3
i=4
i=5

10-1

-2

-2

10
vi(k)

10
vi(k)

2500

(a)

0

-3

10

-3

10

10-4

10-4

-5

10

-5

10

10-6

2000

k

0

500

1000

1500

2000

2500

10-6

3000

k

0

500

1000

1500

2000

2500

3000

k

(b)

(b)
ei (k)

Fig. 2. Results of the first experiment. (a) Time evolution of=∥Bxi (k)(b) Time
evolution of v i (k) = ∥xi (k) −∑∑5 − c∥/∥c∥.
(1/5) j=1 xj (k)∥/∥(1/5) 5j=1 xj (k)∥.

Fig. 3.
Results of the second experiment. (a) Time evolution ofiiei (k) ∑= ∥Bxi (k) − c∥/∥c∥.
∑ (b) Time evolution of v (k) = ∥x (k) −(1/5) 5j=1 xj (k)∥/∥(1/5) 5j=1 xj (k)∥.

graph of this multi-agent network is strongly connected. In
addition, it is aperiodic because vertex 1 has a self-loop.
The results of the second experiment are shown in
Fig. 3. Figures 3 (a) and 3 (b) show the time evolution of ei (k) ∑= ∥Bxi (k) − c∥/∥c∥and v i (k) =∑55ij∥x (k) − (1/5) j=1 x (k)∥/∥(1/5) j=1 xj (k)∥, respectively, for i = 1, 2, . . . , 5. As in the first experiment, bothei (k) and v i (k) converge exponentially to zero for all i. But
the more important point is that their convergence rates are
faster than those in the first experiment.
In the third experiment, we consider the situation in which
the same problem as in the first experiment is solved by afive-agent network with aii = 0 for all i. The weights on thestates are set to
0.0 0.4 0.6 0.0 0.0
 0.2 0.0 0.5 0.3 0.0 



A=
 0.5 0.3 0.0 0.0 0.2  0.0 0.4 0.0 0.0 0.6 
0.0 0.0 0.3 0.7 0.0

multi-agent network is strongly connected. In addition, it isaperiodic because the greatest common divisor of the lengths
of cycles, which are three, four and five, is one.
The results of the third experiment are shown in
Fig. 4. Figures 4 (a) and 4 (b) show the time evolution of ei (k) ∑= ∥Bxi (k) − c∥/∥c∥and v i (k) =∑55ji∥x (k) − (1/5) j=1 x (k)∥/∥(1/5) j=1 xj (k)∥, respectively, for i = 1, 2, . . . , 5. As in the first and second experiments, both ei (k) and v i (k) converge exponentially to zerofor all i. In addition, their convergence rates are faster thanthose in the second experiment.
The results of these experiments suggest that the smaller
the weights on self-loops are, the faster the convergence rateof the algorithm is. We do not address this issue in this paper.
Further studies are needed to determine whether this statement
holds true.

and the entries of the seeds s1 , s2 , . . . , sm are set to thesame values as in the first experiment. The matrix A above isobtained from the one in the first experiment by setting aii tozero for all i and then by increasing the values of the smallest
offdiagonal entries in each row so that the first condition in
Assumption 1 is satisfied. The communication graph of thisV. C ONCLUSION
The convergence property of the projected consensus algorithm proposed by Nedić et al. [7] was studied in this paper.
Restricting ourselves to the case where the communicationgraph is time-invariant, we have proved, under weaker conditions than those in the literature, that a constrained consensus
is achieved by the algorithm. In our proof, self-loops in thecommunication graph are not necessarily needed, while it is

0

10

i=1
i=2
i=3
i=4
i=5

10-1

ei(k)

10-2
-3

10

10-4
10-5
10-6

0

500

1000

1500

2000

2500

3000

k

(a)
0

10

i=1
i=2
i=3
i=4
i=5

10-1
-2

vi(k)

10

-3

10

10-4
-5

10

10-6

0

500

1000

1500

2000

2500

3000

k

(b)
Fig. 4. Results of the third experiment. (a) Time evolution of ei (k) =∥Bxi (k)evolution of v i (k) = ∥xi (k) −∑∑ − c∥/∥c∥. (b) Time
(1/5) 5j=1 xj (k)∥/∥(1/5) 5j=1 xj (k)∥.

assumed that every vertex has a self-loop in, for example,
the convergence analysis done by Nedić and Liu [9]. We
have also confirmed the validity of the theoretical analysis
through numerical experiments in which a system of linear
equations with nonnegativity constraints are solved by thealgorithm. Experimental results indicate that the convergence
rate may become faster as the weights on self-loops become
smaller. Clarifying the relationship between the weights andthe convergence rate is left for a future work.
VI. ACKNOWLEDGMENTS
The authors would like to thank Professor Y. Tanji andProfessor K. Fujimoto, Kagawa University, for their valuablecomments on linear equations with nonnegativity constraints.
The authors also would like to thank anonymous reviewers
for their valuable comments and suggestions to improve thequality of the paper.
R EFERENCES[1] R. Olfati-Saber and R. M. Murray, “Consensus protocols for networksof dynamic agents,” in Proceedings of the 2003 American Control
Conference, Jun. 2003, pp. 951–956.
[2] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,”
Systems & Control Letters, vol. 53, pp. 65–78, Sep. 2004.
[3] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor
fusion based on average consensus,” in Proceedings of the FourthInternational Symposium on Information Processing in Sensor Networks,
Apr. 2005, pp. 63–70.

[4] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proc. IEEE, vol. 95, no. 1, pp.
215–233, Jan. 2007.
[5] D. P. Spanos, R. Olfati-Saber, and R. M. Murray, “Dynamic consensus
for mobile networks,” in Proceedings of the 16th IFAC World Congress,
2005.
[6] M. Zhu and S. Martı́nez, “Dicrete-time dynamic average consensus,”
Automatica, vol. 46, pp. 322–329, 2010.
[7] A. Nedić, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus andoptimization in multi-agent networks,” IEEE Trans. Autom. Control,
vol. 55, no. 4, pp. 922–938, Apr. 2010.
[8] S. Mou, J. Liu, and A. S. Morse, “A distributed algorithm for solving alinear algebraic equation,” IEEE Trans. Autom. Control, vol. 60, no. 11,
pp. 2863–2878, Nov. 2015.
[9] A. Nedić and J. Liu, “On convergence rate of weighted-averaging
dynamics for consensus problems,” IEEE Trans. Autom. Control, vol. 62,
no. 2, pp. 766–781, Feb. 2017.
[10] G. Shi, B. D. Anderson, and U. Helmke, “Network flows that solve linear
equations,” IEEE Trans. Autom. Control, vol. 62, no. 6, pp. 2659–2674,
Jun. 2017.
[11] J. Liu, S. Mou, and A. S. Morse, “Asynchronous distributed algorithms
for solving linear algebraic equations,” IEEE Trans. Autom. Control,
vol. 63, no. 2, pp. 372–385, Feb. 2018.
[12] I. Suzuki and M. Yamashita, “Distributed anonymous mobile robots:
Formation of geometric patterns,” SIAM Journal on Computing, vol. 28,
no. 4, pp. 1347–1363, 1999.
[13] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobileautonomous agents using nearest neighbor rules,” IEEE Trans. Autom.
Control, vol. 48, no. 6, pp. 988–1001, Jun. 2003.
[14] J. A. Fax and R. M. Murray, “Information flow and cooperative controlof vehicle formations,” IEEE Trans. Autom. Control, vol. 49, no. 9, pp.
1465–1476, Sep. 2004.
[15] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multiagent optimization,” IEEE Trans. Autom. Control, vol. 54, no. 1, pp.
48–61, Jan. 2009.
[16] S. S. Ram, A. Nedić, and V. V. Veeravalli, “Distributed stochastic
subgradient projection algorithms for convex optimization,” Journal of
Optimization Theory and Applications, vol. 147, no. 3, pp. 516–545,
2010.
[17] G. Notarstefano and F. Bullo, “Distributed abstract optimization via
constraints consensus: Theory and applications,” IEEE Trans. Autom.
Control, vol. 56, no. 10, pp. 2247–2261, Oct. 2011.
[18] M. Bürger, G. Notarstefano, F. Bullo, and F. Allgöwer, “A distributed
simplex algorithm for degenerate linear programs and multi-agent assignments,” Automatica, vol. 48, no. 9, pp. 2298–2304, 2012.
[19] P. Lin, W. Ren, and Y. Song, “Distributed multi-agent optimization subject to nonidentical constraints and communication delays,” Automatica,
vol. 65, pp. 120–131, 2016.
[20] P. Yang, R. Freeman, G. Gordon, K. Lynch, S. Srinivasa, and R. Sukthankar, “Decentralized estimation and control of graph connectivity formobile sensor networks,” Automatica, vol. 46, pp. 390–396, 2010.
[21] K. Yamane and N. Takahashi, “Proposal of a truly decentralized algorithm for estimating algebraic connectivity of multi-agent networks,” inProceedings of 2015 International Symposium on Nonlinear Theory andits Applications, 2015, pp. 277–280.
[22] K. Endo and N. Takahashi, “A new decentralized discrete-time algorithm for estimating algebraic connectivity of multiagent networks,” inProceedings of 2016 Asia Pacific Conference on Circuits and Systems,
2016, pp. 232–235.
[23] E. Montijano, J. I. Montijano, and C. Sagues, “Fast distributed algebraic
connectivity estimation in large scale networks,” Journal of the Franklin
Institute, vol. 354, no. 13, pp. 5421–5442, 2017.
[24] 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, Mar. 2013.
[25] C. Michelot, “A finite algorithm for finding the projection of a point
onto the canonical simplex of Rn ,” Journal of Optimization Theory andApplications, vol. 50, no. 1, pp. 195–200, 1986.
[26] A. Al-Ola, M. Omar, K. Fujimoto, and T. Yoshinaga, “Common Lyapunov function based on Kullback–Leibler divergence for a switchednonlinear system,” Mathematical Problems in Engineering, vol. 2011,2011, 723509.
[27] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing
Times. American Mathematical Soc., 2008.
[28] W. Zangwill, Nonlinear Programming: A Unified Approach. PrenticeHall, 1969.