1

Distributed algorithms for solving a class of
convex feasibility problems
arXiv:1612.04913v1 [cs.SY] 15 Dec 2016

Kaihong Lu, Gangshan Jing, and Long Wang

Abstract
In this paper, a class of convex feasibility problems (CFPs) are studied for multi-agent systems
through local interactions. The objective is to search a feasible solution to the convex inequalities with
some set constraints in a distributed manner. The distributed control algorithms, involving subgradient
and projection, are proposed for both continuous- and discrete-time systems, respectively. Conditions
associated with connectivity of the directed communication graph are given to ensure convergence of the
algorithms. It is shown that under mild conditions, the states of all agents reach consensus asymptotically
and the consensus state is located in the solution set of the CFP. Simulation examples are presented to
demonstrate the effectiveness of the theoretical results.

Index Terms
Multi-agent systems; Consensus; Convex inequalities; Subgradient; Projection.

I. I NTRODUCTION
Distributed coordination control of multi-agent systems (MASs) has been intensively investigated in various areas including engineering, natural science, and social science [1]-[3]. As a
fundamental coordination problem, the consensus which requires that a group of autonomous
agents achieve a common state has attracted much attention, see [4]-[11]. This is due to its
This work was supported by National Science Foundation of China (Grant Nos. 61533001 61375120, and 61603288).
(Corresponding author: Long Wang)
K. Lu and G. Jing are with the Center for Complex Systems, School of Mechano-electronic Engineering, Xidian University,
Xi’an 710071, China (e-mail:khong lu@163.com; nameisjing@gmail.com)
L. Wang is with the Center for Systems and Control, College of Engineering, Peking University, Beijing 100871, China
(e-mail: longwang@pku.edu.cn)

December 16, 2016

DRAFT

2

wide applications in distributed control and estimation [12], distributed optimization [13]-[15]
and distributed methods for solving linear equations [16], [17].
Researches on consensus can be roughly categorized depending on whether the agents have
continuous- or discrete- time dynamics. Noticeable works focusing on the multi-agent systems
include [6], [9], [18], [19] for the continuous-time case and [5], [19]-[21] for the discrete-time
case. In the aforementioned works, the agents interact with each other through a network and
each agent adjusts its own state by using only local information from its neighbors. Within this
framework, connectivity of the communication graph plays a key role in achieving consensus,
and consequently several conditions of the connectivity have been established. For example,
the communication graph must have a spanning tree when the topology is fixed [6], while the
union of the communication graphs should have a spanning tree frequently enough as the system
evolves when the topology is switching [9], [21]. In addition, infinitely-joint connectedness, i.e.,
the infinitely occurring communication graphs are jointly connected, is necessary to make the
agents reach consensus when the topology is time-varying [18], [19].
In recent years, the constrained consensus problem that seeks to reach state agreement in the
intersection of a number of convex sets has been widely investigated. In [22], a projection-based
consensus algorithm was proposed when the communication graph is balanced. This algorithm
with time delays was studied in [24], where the union of the communication graphs within a
period was assumed to be strongly connected. The problem was extended to the continuous-time
case in [25], where each set serves as an optimal solution set of a local objective function,
and the global optimal solution is achieved as long as the intersection of the constrained sets is
computed. By taking the advantages of the property that the solution set of linear equations is an
affine set, the projection-based consensus algorithm in [25] was successfully applied to solving
linear equations in [26], where the projection operator in [25] was replaced with a special affine
projection operator. Unlike the distributed algorithm for solving linear equations in [16], the
projection-based consensus algorithm in [26] does not need to restrict each agent’s initial state
within the solution set of its corresponding equations. The methods in [22]-[26] are useful for
the computation of the intersection when the projections onto the local sets are easily calculated.
However, in general, the application of the projected method usually requires the solution of an
auxiliary minimization problem associated with the projection onto the local set at each time.
This might lead to a limitation on its applications.
December 16, 2016

DRAFT

3

Comparing with computing the intersection and solving linear equations, a more general
problem is solving CFPs, which usually needs to solve linear equations and convex inequalities
simultaneously, and ensure the solution to be in the intersection of some simple convex sets.
Applications of solving CFPs arise in different fields, such as pattern recognition [27], signal
processing [28] and image restoration [29], [30]. It is also well known that some convex
programming problems can be transformed into an equivalent CFP through the Karush-KuhnTucker condition [31]. For example, the linear program problem in [32] can be transformed into
a set of linear equations and inequalities. Inspired by the distributed methods for solving linear
equations [16], [26], distribute methods for CFPs will be studied in this paper. Different from
linear equations, the solution set of a CFP is usually not a simple affine set due to the existence
of inequalities which can even be nonlinear, thus it is necessary to develop alternative methods
for solving this problem.
In this paper, distributed algorithms, involving subgradient and projection, are proposed for
multi-agent systems to solve the CFP involving convex inequalities. Here the distributed control
algorithms are designed for the continuous- and the discrete-time systems, respectively. Our aim
is to obtain the graphic criteria for the convergence of these algorithms. One of the challenge
is that, the subgradient and projection operations lead to nonlinearity of the algorithms. To deal
with this problem, the control inputs are decomposed into a linear part involving the traditional
consensus term and a nonlinear part involving the subgradient and projection operations. The
linear part is analyzed by using the graph theory and some basic theories of stability associated
with linear systems, while the nonlinear part is done by Lyapunov theory. The contributions of
this paper are summarized as follows:
(1) Both continuous- and discrete-time distributed algorithms are provided for solving CFPs.
Different from the distributed algorithms for solving linear equations in [16], [17], in which the
algorithms need to restrict each agent’s initial state within the solution set of its corresponding
equations, the CFPs can be solved by the presented algorithms under arbitrary initial states.
(2) The continuous-time distributed gradient-based algorithm has also been investigated in [36],
where convergence of the algorithm relies on a time-varying parameter. Our algorithm does not
involve a time-varying parameter and it does not require the assumption on boundedness of the
subgradient as in [36]. We prove that, if the directed graph is fixed and strongly connected, all
agents’ states will reach a common point asymptotically and the point is located in the solution
December 16, 2016

DRAFT

4

set of the CFP. Moreover, we find that the CFP can be solved if the δ−graph associated with a
time-varying graph is strongly connected.
(3) Discrete-time distributed subgradient-based algorithms have been studied in [22], where the
communication graph is balanced. Unlike [22], [23], in our algorithm, only relative information
between the agents is required and the convergence can also be ensured when the communication
graph is unbalanced. We prove that the effectiveness of the presented algorithm can be guaranteed
when the directed graph is strongly connected.
This paper is organized as follows. In Section II, we present some notions in graph theory and
state the problem studied in this paper. In Section III, centralized algorithms in both continuousand discrete-time cases for the CFP are focused on and the convergence of them is analyzed. In
Section IV, the distributed control algorithm in continuous-time case is presented for the MAS to
solve the CFP, and the convergence is analyzed under both fixed and time-varying communication
graphs. The discrete-time case is studied in Section V. In Section VI, a distributed gradient-based
algorithm is designed for a CFP involving linear inequalities. Simulation examples are presented
in Section VII. Section VIII concludes the whole paper.
Notation: Throughout this paper, we use |a| to represent the absolute value of scalar a. R

and C denote the set of real number and the set of complex number,respectively. Let Rm be
the m-dimensional real vector space and Cm be the complex one. For a given vector x ∈ Rm ,
x > 0(≥ 0) implies that each entry of vector x is greater than (not less than) zero. kxk denotes
√
the standard Euclidean norm, i.e., kxk = xT x. For a function g(·) : Rm → R, we denote its

plus function by g + (·) = max[g(·), 0]. 1n denotes the n-dimensional vector with elements being
all ones. In denotes the n × n identity matrix. The transposes of matrix A and vector x are

denoted as AT and xT , respectively. For any two vectors u and v, the operator hu, vi denotes the
inner product of u and v. For matrices A and B, the Kronecker product is denoted by A ⊗ B.
II. P RELIMINARY

AND PROBLEM FORMULATION

A. Graph theory
The communication topology is denoted by G(A(t)) = (V, E(t), A(t)), V is a set of vertices,
E(t) ⊂ V × V is an edge set, and the weighted matrix A(t) = (aij (t))n×n is a non-negative
matrix for adjacency weights of edges. If node i can receive the information from node j, then
node j is called as node i’s neighbor and it is denoted by (j, i) ∈ E(t) and aij (t) > 0. Otherwise,
December 16, 2016

DRAFT

5

aij (t) = 0. Denote Ni (t) = {j ∈ V|(j, i) ∈ E(t)} to represent the neighbor set of node i at time
t. The Laplacian matrix of the graph is defined as L(t) = (lij (t))n×n , where lij (t) = −aij (t) if
n
P
i 6= j and lij (t) =
aij (t) if i = j for any i = 1, · · · , n. For a fixed and directed graph G(A),
j=1

a path of length r from node i1 to node ir+1 is a sequence of r + 1 distinct nodes i1 · · · , ir+1

such that (iq , iq+1 ) ∈ E for q = 1, · · · , r. If there exists a path between any two nodes in V,
then G(A) is said to be strongly connected. A directed graph, where every node has exactly one
neighbor except the root, is said to be a directed tree. A spanning tree of a directed graph is a
directed tree formed by graph edges that connect all the nodes of the graph [33]. We say that a
graph has a spanning tree if a subset of the edges forms a spanning tree.
For a time-varying and directed graph G(A(t)), (j, i) is called a δ−edge if there always exist
R t+T
two positive constants T and δ such that t aij (s)ds ≥ δ for any t ≥ 0. A δ−graph, induced

R t+T
by G(A(t)), is defined as G(δ,T ) = (V, E(δ,T ) ), where E(δ,T ) = (j, i) ∈ V × V| t aij (s)ds ≥

δ f or any t ≥ 0 . The communication graph G(A(t)) is said to be balanced if the sum of the
n
n
P
P
interaction weights from and to an agent i are equal, i.e.,
aij (t) =
aji (t).
j=1

j=1

Lemma 1: [5] For a fixed graph G(A), if G(A) has a spanning tree, then the Laplacian matrix

L has one simple 0 eigenvalue and the other eigenvalues have positive real parts.
Lemma 2: [6] For a fixed graph G(A), if G(A) is strongly connected, then there exists a

vector w = [w1 · · · wn ]T > 0 such that w T L = 0.

For ease of description, if G(A) has a spanning tree, we use λ1 (L) to represent the 0 eigenvalue
and λi (L), i = 2, · · · , n to represent other non-zero eigenvalues.
B. Convex analysis
A function f (·) : Rm → R is convex if it holds f (γx + (1 − γ)y) ≤ γf (x) + (1 − γ)f (y) for

any x 6= y ∈ Rm and 0 < γ < 1. For convex function f (x), if h ∇f (x), y − x i ≤ f (y) − f (x)

holds for any y ∈ Rm , then ∇f (x) is a subgradient of function f at point x ∈ Rm . There must

exist subgradients for any convex function. Furthermore, if the convex function is differentiable,
its gradient is the unique subgradient.
Given a set Ω ⊂ Rm , it is called as a convex set if γx + (1 − γ)y ∈ Ω for any scalar 0 < γ < 1
∆

and x, y ∈ Ω. For a closed convex set Ω, let kxkΩ = inf y∈Ω kx − yk denote the standard Euclidean
distance of vector x ∈ Rm from Ω. Then, there is a unique element PΩ (x) ∈ Ω such that
December 16, 2016

DRAFT

6

kx − PΩ (x)k = kxkΩ , where PΩ (·) is called the projection onto the set Ω [34]. Moreover, PΩ (·)

has the non-expansiveness property: kPΩ (x) − PΩ (y)k ≤ kx − yk for any x, y ∈ Rm .

Lemma 3: For a convex function g(·) : Rm → R, suppose the set X = {x ∈ Rm |g + (x) = 0}

is non-empty, it holds z ∈ X if and only if 0 is a subgradient of the plus function g + at point z.

Proof: Sufficiency. By the definition of g + (·), we know function g + (·) is convex. Therefore,

the subgradient of function g + (·) always exists. If 0 is a subgradient of the plus function g + at
point z, by the definition of the subgradient, we have g + (y) − g + (z) ≥ 0T (y − z) = 0 for any
y ∈ Rm . Let y ∈ X, then we have −g + (z) ≥ 0. By this and the fact that g + (z) ≥ 0, it can be
concluded that g + (z) = 0.

Necessity. If z ∈ X, we have g + (z) = 0. Due to the fact that g + (y) ≥ 0, we have g + (y) − 0 ≥

0T (y − z) for any y ∈ Rm . Thus, 0 is a subgradient of the plus function g + at point z.
Lemma 4: [22] Given a closed convex set Ω ⊂ Rm , it holds
hPΩ (x) − x, x − yi ≤ −kxk2Ω
for any x ∈ Rm , y ∈ Ω.
C. Problem formulation

Consider a MAS consisting of n agents, labeled by set V = {1, · · · , n}. Here we consider
agents with both continuous-time dynamics
ẋi (t) = ui (t), i ∈ V

(1)

xi (t + 1) = xi (t) + ui (t), i ∈ V

(2)

and discrete-time dynamics

where xi (t) ∈ Rm and ui (t) ∈ Rm are respectively, the state and input of agent i. The objectives
of this paper are to design ui (t) for (1) and (2) by using only local information to solve the
following CFP:

 gi (x) ≤ 0


x∈X :

∆

= ∩ni=1 Xi

i = 1, · · · , n

(3)

where x ∈ Rm , gi (·) : Rm → R is a convex function, it is continuous on (−∞, ∞). Each
Xi is a closed convex set. Agent i can only have access to the information associated with
December 16, 2016

DRAFT

7

subgradient ∇gi+ (·) and projection PXi (·). We assume each ∇gi+ (·) is piecewise continuous for
any i = 1, · · · , n.
Remark 1: Note that if and only if x ∈ Xi , it holds x = PXi (x). If x = PXi (x) for all
i = 1, · · · , n, then x belongs to their intersection. Since the algorithms in the following sections
refer to the projection operator PXi (·), here we only consider some convex sets Xi onto which
the projection PXi (x) can be easily calculated or their expressions could be given in detail at any
point x. For example, if set X represents the solution set of linear equation aT x−b = 0, i.e., X =


aaT
ba
{x|aT x − b = 0}, where a, x ∈ Rm , b ∈ R, it is easy to show that PX (x) = I − kak
x + kak
2
2

is a projection of x onto set X. Consequently, it is not difficult to find that the algorithms in the
following sections are also available to the CFP involving linear equations.
The solution set of CFP (3) is denoted by X∗ and the following assumption is adopted throughout
the paper.
Assumption 1: X∗ is non-empty.
Note that a vector x∗ belongs to X∗ , if and only if it holds that x∗ ∈ X and gi+ (x∗ ) = 0 for
each i ∈ {1, · · · , n}.
III. C ENTRALIZED

ALGORITHMS FOR

CFP S

In this section, we focus on the following CFP

 g(x) ≤ 0


(4)

x∈X

where x ∈ Rm , g(·) : Rm → R is a convex function, and X is a closed convex set.
A. Continuous-time case
To solve CFP (4), the following continuous-time subgradient and projection-based algorithm
is proposed.
ẋ(t) = −α(t)[x(t) − PX (x(t))] − β(t)∇g + (x(t))

(5)

where α(t),β(t) ∈ R.

Theorem 1: Suppose CFP (4) has a non-empty solution set X∗ , if α(t) ≥ 0 and β(t) ≥ 0
R∞
R∞
satisfy that 0 α(t) → ∞ and 0 β(t) → ∞, then x(t) in (5) converges to a vector x∗ in set
X∗ .

December 16, 2016

DRAFT

8

Proof: Define a positive-definite Lyapunov function candidate V (t) = 21 kx(t) − x0 k2 , where

x0 ∈ X∗ . By the definition of g + , it holds g + (x0 ) = kx0 kX = 0. Based on the property of the
subgradient, we have hx(t) − x0 , ∇g + (x(t))i ≥ g + (x(t)). Taking the derivative of function V (t)

with respect to t yields
V̇ (t) = hx(t) − x0 , ẋ(t)i
= x(t) − x0 , −α(t)[x(t) − PX (x(t))] − β(t)∇g + (x(t))

(6)
+

= −α(t) hx(t) − x0 , x(t) − PX (x(t))i − β(t)hx(t) − x0 , ∇g (x(t))i
≤ −α(t) hx(t) − x0 , x(t) − PX (x(t))i − β(t)g + (x(t)).
By Lemma 4, we know − hx(t) − x0 , x(t) − PX (x(t))i ≤ −kx(t)k2X ≤ 0. Note that g + (x(t)) ≥
0. Thus, V̇ (t) ≤ 0. Moreover, V (t) is bounded by zero, it can be concluded that V (t) converges
and V (∞) exists, which implies kx(t) − x0 k converges. By inequality (6), we have
Z ∞
Z ∞
2
α(t) kx(t)kX dt +
β(t)g + (x(t))dt ≤ V (0) − V (∞) < ∞.
0

0

Since α(t) kx(t)k2X and β(t)g + (x(t))
R∞
dt < ∞ and 0 β(t)g + (x(t))dt < ∞.

R∞
are both non-negative, then we have 0 α(t) kx(t)k2X
R∞
R∞
These and the facts 0 α(t) → ∞ and 0 β(t) → ∞

imply lim inf kx(t) − PX (x(t))k = lim inf g + (x(t)) = 0. Thus, there exists a subsequence
t→∞

t→∞

{x(tk )} of x(t) such that lim x(tk ) = lim inf x(t) = x∗ , where x∗ is a point in the solution set
k→∞

t→∞

of CFP (4). Moreover, note that V (x(t)) converges, it can be concluded that lim x(t) = x∗ ∈ X.
t→∞

Hence, the validity of the result is verified.
Corollary 1: Suppose CFP (4) has a non-empty solution set X∗ , if x(t) adjusts its value with
the following dynamics
ẋ(t) = −[x(t) − PX (x(t))] − ∇g + (x(t))
then x(t) converges to a vector x∗ in set X∗ .
B. Discrete-time case
Now we present the discrete-time algorithm for CFP (4).

+



 ξ(t) = x(t) − β(t)∇g (x(t))
December 16, 2016

ϕ(t) = α(t) (ξ(t) − PX (ξ(t)))



 x(t + 1) = ξ(t) − ϕ(t)

(7)

DRAFT

9

where PX (·) and ∇g + (x(t)) are defined as those in (5).
Assumption 2: ∇g + (x(t)) ≤ K for some K ≥ 0.

Lemma 5: [35] Let {z(t)} be a non-negative scalar sequence such that
z(t + 1) ≤ (1 + a(t))z(t) − b(t) + c(t)
for all t ≥ 0, if a(t) ≥ 0, b(t) ≥ 0, c(t) ≥ 0 with
sequence {z(t)} converges to some constant z ∗ and

∞
P

t=0
∞
P

t=0

a(t) < ∞ and
b(t) < ∞.

∞
P

t=0

c(t) < ∞, then the

Theorem 2: Under Assumptions 2, if CFP (4) has a non-empty solution set X∗ , and α(t) ,

β(t) satisfy
(a) α(t) ∈ [0, 1],

∞
P

t=0

(b) 0 ≤ β(t) ≤ ∞,

α(t) → ∞ and

∞
P

t=0

∞
P

t=0

β(t) → ∞ and

α2 (t) < ∞;

∞
P

t=0

β 2 (t) < ∞.

Then, x(t) in (7) converges to a vector x∗ in set X∗ .

Proof: We choose the Lyapunov function candidate as V (t) = kx(t) −x0 k2 , where x0 ∈ X∗ .
Taking the difference of function V (t) along with (7) yields
∆V (t) = V (t + 1) − V (t)
= kξ(t) − ϕ(t) − x0 k2 − kx(t) − x0 k2
= k(1 − α(t))(ξ(t) − x0 ) + α(t)(PX (ξ(t)) − x0 )k2 − kx(t) − x0 k2

2
≤ (1 − α(t))kξ(t) − x0 k + α(t)kPX (ξ(t)) − x0 k − kx(t) − x0 k2

(8)

≤ kξ(t) − x0 k2 − kx(t) − x0 k2

where the last inequality follows from the non-expansiveness property of projection operator,
i.e., kPX (ξ(t)) − x0 )k ≤ kξ(t) − x0 k. Moreover, we have
kξ(t) − x0 k2 ≤ kx(t) − x0 k2 − 2β(t)h∇g +(x(t)), x(t) − x0 i
+ β 2 (t)K
2

(9)
+

+

≤ kx(t) − x0 k − 2β(t) g (x(t)) − g (x0 )
+ β 2 (t)K.



From inequalities (8) and (9), we have ∆V (t) ≤ β 2 (t)K. Thus, it holds that V (t) ≤ V (0) +
t−1
∞
P 2
P
β (t)K ≤ V (0) +
β 2 (t)K < ∞. By the definition of V (t), it can be concluded that
t=0

t=0

x(t) is bounded. Since kβ(t)∇g + (x(t)) k < ∞, ξ(t) is bounded. This and the continuity of
December 16, 2016

DRAFT

10

PX (ξ(t)) imply kξ(t) − PX (ξ(t))k < ∞. Denote ∇(t) = β(t)∇g + (x(t)), since
and

∞
P

t=0

2

β (t) < ∞, it can be concluded that

(8), we also have

∞
P

t=0

2

k∇(t)k < ∞ and

∞
P

t=0

2

∞
P

t=0

α2 (t) < ∞

kϕ(t)k < ∞. Similar to

∆V (t) = V (t + 1) − V (t)
= −2h∇(t) + ϕ(t), x(t) − x0 i + k∇(t) + ϕ(t)k2
= −2h∇(t), x(t) − x0 i − 2hϕ(t), ξ(t) − x0 i
− 2hϕ(t), ∇(t)i + k∇(t) + ϕ(t)k2

(10)

= −2h∇(t), x(t) − x0 i − 2hϕ(t), ξ(t) − x0 i + k∇(t)k2 + kϕ(t)k2
≤ −2β(t)g + (x(t)) − 2α(t)kξ(t)k2X + k∇(t)k2 + kϕ(t)k2
= −2β(t)g + (x(t)) − 2α(t)kξ(t)k2X + k∇(t)k2 + kϕ(t)k2 .
∞
P

k∇(t)k2 + kϕ(t)k2 < ∞ and −2β(t)g + (x(t)) − 2α(t)kξ(t)k2X < 0,
t=0
∞ 
P
by Lemma 5, it can be concluded kx(t) − x0 k converges and it holds
β(t)g + (x(t)) +
t=0

α(t)kξ(t)k2X < ∞. Since β(t)g + (x(t)) > 0 and α(t)kξ(t)k2X > 0 for all t > 0, we have
∞
∞
∞
∞
P
P
P
P
α(t) → ∞ and
β(t) → ∞,
β(t)g + (x(t)) < ∞ and
α(t)kξ(t)k2X < ∞. By the facts

Recall the fact that

t=0

t=0

t=0

t=0

we have lim inf kξ(t) − PX (ξ(t))k = lim inf g + (x(t)) = 0. Thus, there exists a subsequence
t→∞

t→∞
∗

{x(tk )} of x(t) such that lim x(tk ) = x , where x∗ is a vector such that g + (x∗ ) = 0. By the
k→∞

fact kx(t) − x0 k converges, we can conclude lim x(t) = x∗ . Furthermore, note that ∇(t) → 0 as
t→∞

t → ∞, thus lim inf kξ(t) − PX (ξ(t))k = 0 and lim x(t) = x∗ imply lim kx∗ − PX (x∗ )k = 0.
t→∞

t→∞

t→∞

Therefore, x∗ is a solution to CFP (4), i.e., x∗ ∈ X∗ .
IV. C ONTINUOUS - TIME

DISTRIBUTED CONTROL ALGORITHMS FOR SOLVING

CFP S

In this section, we focus on solving CFP (3) for continuous-time MAS (1) in a distributed
manner, which means that each agent has access to only its own state and that from its neighbors.
The following input is proposed.

X

aij (t)(xj (t) − xi (t)) + φi (t)

 ui (t) =
i∈Ni (t)



 φ (t) = −τ [x (t) − P (x (t))] + ∇g + (x (t))
i
i
Xi
i
i
i

December 16, 2016

i∈V

(11)

DRAFT

11

where τ is a positive coefficient. Note that φi depends on only agent i’s own state, so (11)
is distributed. Based on Lemma 3 in Section II, here we set ∇gi+ (x) = 0 if gi (x) ≤ 0 and
∇gi+ (x) = ∇gi (x) otherwise.

Remark 2: If we set τ = 0 in algorithm (11), then it will become a typical linear consensus
algorithm for MASs studied in [5], [6]. In this case, MASs reach consensus asymptotically
if the communication graph is fixed and has a spanning tree. The distributed subgradientbased algorithm was studied for continuous-time multi-agent systems to optimize a sum of
convex objective functions in [36], but the convergence of the algorithm relies on a time-varying
parameter and the projection term was not involved.

T

T
Let x(t) = xT1 (t), · · · , xTn (t) and φ(t) = φT1 (t), · · · , φTn (t) , MAS (1) with (11) can be
rewritten as

ẋ(t) = − (L(t) ⊗ Im ) x(t) + φ(t).

(12)

Lemma 6: [37] Let b(t) be a bounded function, if lim b(t) = b and 0 < γ < 1, then
t→∞
R t t−s
b
lim 0 γ b(s) ds = − lnγ .

t→∞

Lemma 7: [38] Given a symmetric matrix P = (pij )n×n with 0 eigenvalue and a vector
n
n
P
P
x = [x1 , · · · , xn ]T , if P 1n = 0, then it holds xT P x = −
pij (xi − xj )2 .
i=1 j=i+1

Lemma 8: Given a linear system ẋ(t) = Ax(t) + u(t), if the state matrix A ∈ Rn×n is

Hurwitz stable and u(t) ∈ Rn satisfies ku(t)k < ∞ and lim u(t) = 0, then the linear system is
t→∞

asymptotically stable to zero, i.e., lim x(t) = 0.
t→∞

Proof: Since matrix A is Hurwitz stable, all of its eigenvalues have negative real parts.
Based on theory of Schur’s unitary triangularization, there exists a unitary matrix U ∈ Cn×n
such that






U H AU = 



λ1 λ12 · · · λ1n
0
..
.

λ2
..
.

0

0




λ23 λ2n 
∆
=
Λ
.. 
..
.
. 

0 λn

where λi is the eigenvalue of matrix A, i = 1, · · · , n; U H is the conjugate transpose matrix

of U. Denote y(t) = U H x(t) and r(t) = U H u(t), we have ẏ(t) = Λy(t) + r(t). By the
fact that lim u(t) = 0, we have lim r(t) = 0. Let y(t) = [y1 (t), · · · , yn (t)]T and r(t) =
t→∞

December 16, 2016

t→∞

DRAFT

12

[r1 (t), · · · , rn (t)]T , we have ẏn (t) = λn yn (t) + rn (t). The term rn (t) can be viewed as an control
Rt
input of the linear system and we have yn (t) = eλn t yn (0)+ 0 eλn (t−τ ) rn (τ )dτ . Since the real part
of λn is negative, it holds 0 < eλn < 1. By Lemma 6, it can be concluded that lim yn (t) = 0.
t→∞
P

n
Since ẏi (t) = λi yi (t) +
λi(i+j) yi+j (t) +ri (t) . Through the similar approach for yn (t), we
j=1
!
n
P
can conclude lim
λi(i+j) yi+j (t) + ri (t) = 0. Reusing Lemma 6 yields lim yi (t) = 0 for
t→∞

t→∞

j=1

any i = 1, · · · , n. This and the fact x(t) = Uy(t) imply lim x(t) = 0.
t→∞

To prove the fact that MAS (1) with (11) solves CFP (3), it is necessary to analyze the
convergence of MAS (1) with (11). Obviously, the conditions for convergence depend on the
connectivity of the graphs. In the following, we will provide the convergence conditions under
the fixed graph and the time-varying graph, respectively.
A. Convergence under the fixed communication graph
Proposition 1: Suppose kφi (t)k < ∞ and lim φi (t) = 0 in (11), i ∈ V, if the fixed
t→∞

graph G(A) is directed and has a spanning tree, then MAS (1) with (11) reaches consensus
asymptotically.
Proof: Define a variable x̂(t) =

n
P

wi xi (t)
n
P
wi
i=1
i=1

=



wT
1T w


⊗ Im x(t), where w = [w1 · · · wn ]T is

(wT ⊗Im )
˙
L’s left eigenvector associated with 0 eigenvalue. Based on (12), we have x̂(t)
= 1T w u(t).

T
Denote ei (t) = xi (t) − x̂(t) and e(t) = eT1 (t), · · · , eTn (t) . Note that if lim e(t) = 0, then
t→∞

MAS (1) with (11) reaches consensus. From (12), we have



1n w T
ė(t) = −(L ⊗ Im )x(t) +
In − T
⊗ Im φ(t)
1n w


1n w T
⊗ Im x(t)
= −(L ⊗ Im )x(t) + (L ⊗ Im )
1Tn w



1n w T
⊗ Im φ(t)
+
In − T
1n w



1n w T
= −(L ⊗ Im )e(t) +
In − T
⊗ Im φ(t)
1n w

√ 1 LT w = 0.
wT w
by √w1T w w, p2, · · ·

where the second equation holds for the fact that L1n = 0. Note that
use

√ 1 w
wT w

to form a set of orthonormal basis on ∈ Cn , denoted

(13)

Now we
, pn . We

define P = ( √w1T w w, p2 , · · · , pn ). It is obvious that P is a unitary matrix, so we can denote
December 16, 2016

DRAFT

13






T
P LP = 




0 | 0 ··· 0
∗
..
.

L1

∗






.




Since G(A) has a spanning tree, by Lemma 1, L has only one 0 eigenvalue and other eigenvalues
have positive real part. This implies −L1 is Hurwitz stable. Now define ẽ(t) = (P T ⊗ Im )e(t).
From (13), we have



T
T
P
1
w
n
T
˙ = −(P LP ⊗ Im )ẽ(t) +
ẽ(t)
P −
⊗ Im φ(t).
1Tn w
T

(14)

Let ẽ(t) = [ẽT1 (t), ẽT2 (t)]T , where ẽ1 (t) ∈ Rm and ẽ2 (t) ∈ R(n−1)m . By (14), we have
!
!
√ 1 w T 1n w T
1
T
√
wT − w w T
ẽ˙ 1 (t) =
⊗ Im φ(t) = 0.
T
1n w
w w



1
1n w T
1
T
T
√
√
Note that ẽ1 (t) = wT w (w ⊗ Im )e(t) = wT w (w ⊗ Im ) In − 1T w ⊗ Im x(t) = 0. Thus,
n

it holds ẽ1 (t) = 0 for any t ≥ 0. Moreover, we have
 



ẽ˙ 2 = − (L1 ⊗ Im ) ẽ2 + 
 

pT2 −
pTn

−

T
pT
2 1n w
1T
w
n



⊗Im

T
pT
n 1n w
1T
nw



⊗Im

..
.





 φ(t).


Since lim φ(t) = 0, by Lemma 8, we have lim ẽ2 (t) = 0. This and the fact that lim ẽ1 (t) = 0
t→∞

t→∞

t→∞

imply lim e(t) = 0. This leads to the validity of this result.
t→∞

Theorem 3: If the fixed graph G(A) is directed and strongly connected, then MAS (1) with

(11) reaches consensus asymptotically, and the consensus state is located in set X∗ .

Proof: Since the graph is strongly connected, by Lemma 2, there exists a vector w =
[w1 · · · wn ]T > 0 such that w T L = 0. Consider a positive-definite Lyapunov function candidate
n
P
V (t) = 21
wi kxi (t)−x0 k2 , where x0 ∈ X∗ . By the definition of gi+ , it holds g + (x0 ) = kx0 kX =
i=1

0. Based on the property of subgradient, we have xi (t) − x0 , ∇gi+ (xi (t)) ≥ gi+ (xi (t)). Taking

December 16, 2016

DRAFT

14

the derivative of function V (t) with respect to t yields
V̇ (t) =
=

n
X

i=1
n
X
i=1

wi hxi (t) − x0 , ẋi (t)i
wi xi (t) − x0 ,

X

i∈Ni (t)

aij (t)(xj (t) − xi (t)) − τ [xi (t)

− PXi (xi (t))] − τ ∇gi+ (xi (t))

=

n
X
X

i=1 i∈Ni (t)

−τ
−τ

n
X
i=1

n
X
i=1

(15)

wi aij hxi (t) − x0 , xj (t) − xi (t)i

wi hxi (t) − x0 , x(t) − PXi (xi (t))i
wi xi (t) − x0 , ∇gi+ (xi (t)) .

T
Denote x(t) = xT1 (t), · · · , xTn (t) , we have
n
X
X

i=1 i∈Ni (t)



wi aij hxi (t) − x0 , xj (t) − xi (t)i = − (x(t) − (1n ⊗ Im ) x0 )T (W L ⊗ Im ) x(t)

W L + LT W
= −x (t)
⊗ Im x(t)
2

+ xT0 w T L ⊗ Im x(t)


W (−L) + (−L)T W
T
= x (t)
⊗ Im x(t)
2
n X
n
X
wi aij + wj aji
kxj (t) − xi (t)k2
=−
2
i=1 j=i+1
T



(16)

≤0
where W = diag(w) is a diagonal matrix formed by w and the last equation results from Lemma
7. By Lemma 4, we know − hxi (t) − x0 , xi (t) − PXi (xi (t))i ≤ −kxi (t)k2Xi ≤ 0. Based on (15)
and (16), we have
V̇ (t) ≤ −τ

n
X
i=1

wi kxi (t)k2Xi − τ

n
X

wi gi+ (xi (t)).

(17)

i=1

Note that gi+ (xi (t)) ≥ 0. Thus, V̇ (t) ≤ 0. Moreover, V (t) is bounded by zero, it can be
concluded that V (t) converges and V (∞) exists, which implies kxi (t) − x0 k converges and
December 16, 2016

DRAFT

15

kxi (t)k is bounded. By (17), we have
Z ∞X
Z
n
2
τ
wi kxi (t)kXi dt + τ
0

i=1

∞
0

n
X

wi gi+ (xi (t))dt

i=1

≤ V (0) − V (∞)
< ∞.
Thus, it holds
−PXi (xi (t))

R∞
0

kxi (t)k2Xi dt < ∞ and

R∞
0

gi+ (xi (t))dt < ∞. These imply limt→∞ xi (t)

= limt→∞ gi+ (xi (t)) = 0 for each i ∈ V. By the definition of the subgradient

∇gi+ (·), we can conclude lim φi (t) = 0 for i ∈ V. By the continuity of gi+ (xi (t)) and the
t→∞

boundedness of kxi (t)k, it can be concluded φi (t) is bounded. Recall Proposition 1, we know
MAS (1) with (11) reaches consensus asymptotically, denote x∗ as the consensus state, i.e.,
lim xi (t) = x∗ for each i ∈ V. Therefore, x∗ ∈ X∗ . The validity of this result is verified.

t→∞

Remark 3: The strongly connected condition proposed in Theorem 3 is sufficient to solve
CFP (3). In fact, it is also necessary in many cases. Now we set an example to illustrate that the
CFP can not be solved by the MAS if the graph is not strongly connected. Suppose graph G is
not strongly connected, then there exists at least one strongly connected component that can not
receive information from others. We denote the set consisting of all agents in this component
by V1 . Suppose that all agents in V1 are constrained by inequality x ≤ 0. If we set xi (0) = 0
for each i ∈ V1 , then it holds xi (t) = 0 for any t > 0 and i ∈ V1 . In another strongly connected
component, if there exists one agent that is constrained by inequality x ≤ −1, it is easy to see
that the CFP can never be solved under such a graph.
If communication graph G(A) is bidirectional and aij = aji for each i ∈ V, G(A) becomes
an undirected graph. For the undirected case, we state the result as follows.
Corollary 2: If the fixed graph G(A) is undirected and connected, then MAS (1) with (11)

reaches consensus asymptotically, and the consensus state is in set X∗ .
B. Convergence under the time-varying communication graph

For system (12), by the properties of linear systems [39], the solution of system (12) can be
written as follows.
x(t) = (Φ(t, s) ⊗ Im ) x(s) +

December 16, 2016

Z

s

t

(Φ(t, τ ) ⊗ Im ) u(τ )dτ

(18)

DRAFT

16

where Φ(t, s) ⊗ Im is the state-transition matrix from state x(s) to state x(t) with t ≥ s ≥ 0.
Now, for time-varying graph G(t), the following assumptions are given.
Assumption 3: The communication graph G(t) is balanced.
Assumption 4: The δ−digraph G(δ,T ) is strongly connected.
Lemma 9: [37] Under Assumptions 3 and 4, for any t ≥ s ≥ 0, Φ(t, s) in (18) satisfies the
following inequality
[Φ(t, s)]ij −

where γ = 1 −

1
(8n2 )⌊n/2⌋

than the value of x.

1
≤ γ t−s ,
n

1
 (⌊1/δ⌋+1)⌊n/2⌋T

i, j ∈ {1, · · · , n}

(19)

, the operator ⌊x⌋ denotes the largest integer not larger

Proposition 2: Under Assumptions 3 and 4, if kφi (t)k < ∞ and lim φi (t) = 0 in (11), i ∈ V,
t→∞

then MAS (1) with (11) reaches consensus asymptotically.
Proof: Since G(t) is balanced, by Peano-Baker formula (see [39] for detail), it can be
n
P
concluded that Φ(t, s) is a double stochastic matrix. Denote x̄(t) = n1
xi (t), by (18), we have
i=1

x̄(t) =


1
1 T
1n ⊗ Im x(s) +
n
n

Z

t

s

Based on (18) and (20), we have

1
x(t) − (1n ⊗ Im ) x̄(t) =
n


1Tn ⊗ Im u(τ )dτ .




1
T
Φ(t, 0) − 1n 1n ⊗ Im x(0)
n


Z t 
1
T
+
Φ(t, τ ) − 1n 1n ⊗ Im u(τ )dτ .
n
s

(20)

(21)

Applying (19) in Lemma 9 to equation (21) yields
Z t
√
√
1
t
γ t−τ ku(τ )kdτ .
x(t) − (1n ⊗ Im ) x̄(t) ≤ mnγ kx(0)k + mn
n
s
1
 (⌊1/δ⌋+1)⌊n/2⌋T

Since 0 < γ = 1 − (8n2 )1⌊n/2⌋
< 1 and lim ku(t)k = 0, by Lemma 6, we have
t→∞

lim x(t) −

t→∞

1
n

(1n ⊗ Im ) x̄(t) = 0. This leads to the validity of this result.

Theorem 4: Under Assumptions 1, 3 and 4, if lim φi (t) = 0 in (11), i ∈ V, then MAS (1)
t→∞

with (11) reaches consensus asymptotically, and the consensus state is in set X∗ .

December 16, 2016

DRAFT

17

Proof: Consider a positive-definite Lyapunov function candidate V (t) =

1
2

i=1

where x0 ∈ X∗ . Taking the derivative of function V (t) with respect to t yields
V̇ (t) =

n
X
i=1

=

n
P

kxi (t) − x0 k2 ,

hxi (t) − x0 , ẋi (t)i

n
X
X

i=1 i∈Ni (t)

aij (t) xi (t) − x0 , xj (t) − xi (t) +

If G(t) is balanced, we have 1Tn L = 0. This implies that

n
X
i=1

n
P
P

(22)
xi (t) − x0 , φi .

i=1 i∈Ni (t)

aij (t) xi (t) − x0 , xj (t) −

xi (t) ≤ 0. The following proof is similar to Theorem 3 and hence it is omitted.
V. D ISCRETE - TIME

DISTRIBUTED ALGORITHMS FOR SOLVING

CFP S

In this section, for discrete-time MAS (2), the following input is presented to solve CFP (3).

X

u
(t)
=
h
aij (xj (t) − xi (t)) + φi (t)

i



j∈Ni






∇i (t) = β(t)∇gi+ (t)




X
i∈V
(23)
ξi (t) = xi (t) + h
aij (xj (t) − xi (t)) − ∇i (t)



j∈Ni






ϕi (t) = α(t) (ξi (t) − PXi (ξi (t)))





 φ (t) = −∇ (t) − ϕ (t)
i
i
i
P
aij (xj (t) − xi (t)),
where ∇gi+ (t) denotes the subgradient of function gi+ (y) at y = xi (t) + h
j∈Ni

h is the control gain to be designed. Note that each agent has only access to the information
from its own inequality and set, as well as its own state and the relative states between itself
and its neighbors, thus (23) is distributed.
Assumption 5: ∇gi+ (·) ≤ K for some K ≥ 0, i = 1, · · · , n.

Lemma 10: Given a linear system x(t + 1) = Ax(t) + u(t), if the state matrix A ∈ Rn×n is

Schur stable and the control input u(t) ∈ Rn is such that lim u(t) = 0, then the linear system
t→∞

is asymptotically stable to zero, i.e., lim x(t) = 0.
t→∞

Proof: It can be proved by the similar approach in Lemma 8 and using the fact that
k
P
ρk−l (A) ku(l)k = 0 for 0 < ρ(A) < 1, which has been proved in [23].
lim

k→∞ l=0

The properties of graph’s Laplacian matrix lead to the following lemmas directly [33].

December 16, 2016

DRAFT

18

Lemma 11: For an undirected graph G(A), if G(A) is connected and 0 < h <

2
,
λn

holds max |1 − hλi (L)| < 1.

then it

2≤i≤n

Lemma 12: For a directed graph G(A), if G(A) has a spanning tree and 0 < h < min

2≤i≤n

then it holds max |1 − hλi (L)| < 1.

2Re(λi (L))
,
|λi (L)|2

2≤i≤n

Proposition 3: Suppose lim φi (t) = 0 in (23), i ∈ V, if the undirected graph G(A) is
t→∞

connected and 0 < h < λ2n , then MAS (2) with (23) reaches consensus asymptotically.

T

T
Proof: Let x(t) = xT1 (t), · · · , xTn (t) and φ(t) = φT1 (t), · · · , φTn (t) , MAS (2) with (23)

can be rewritten as

x(t + 1) = ((I − hL) ⊗ Im ) x(t) + φ(t).
n
P

(24)


1Tn ⊗ Im x(t). Based on (24), we have x̄(t + 1) =
i=1

T
x̄(t) + u(t). Denote ei (t) = xi (t) − x̄(t) and e(t) = eT1 (t), · · · , eTn (t) . Note that if e(t) → 0

Denote variable x̄(t) =

1
n

xi (t) =

1
n

as t → ∞, then MAS (2) with (23) reaches consensus asymptotically. From (24), we have



1
T
(25)
e(t + 1) = ((I − hL) ⊗ Im )e(t) +
In − 1n 1n ⊗ Im φ(t).
n

Since L is symmetric for G being undirected. We select pi ∈ Rn such that pTi L = λi (L)pTi
h
i
and form an unitary matrix P = √1nn , p2 , · · · , pn to transform I − hL into a diagonal form

diag(1, (1 − h)λ2 (L), · · · , (1 − h)λn (L)) = P T (I − hL)P . Denote ẽ(t) = P T e(t) and partition
ẽ(t) into two parts , i.e., ẽ(t) = [ẽT1 (t), ẽT2 (t)]T . Then, from (25), we have




1
1 T
T
√ 1 n In − 1 n 1 n
⊗ Im φ(t).
ẽ1 (t + 1) =
n
n



T
T
1 T
1
√
√1
1
⊗
I
e(t) =
Note that
1
1
⊗
I
=
0
and
ẽ
(t)
=
1
I
−
m
n
m
1
n
n
n
n
n
n
n
Thus, it holds ẽ1 (t) = 0. Moreover, we have



pT2 − n1 pT2 1n 1Tn ⊗ Im


..
ẽ2 (t + 1) = Λẽ2 (t) + 
.


pTn − n1 pTn 1n 1Tn ⊗ Im

√1
n

n
P

ei (t) = 0.

i=1





 φ(t)


where Λ = diag((1 − hλ2 (L))Im , · · · , (1 − hλn (L))Im ). By Lemma 11, we know if 0 < h <

2
,
λn

Λ is Schur stable. Recalling Lemma 10 yields lim ẽ2 (t) = 0. This and the fact that lim ẽ1 (t) = 0
t→∞

t→∞

imply lim e(t) = 0, which leads to the validity of this result.
t→∞

December 16, 2016

DRAFT

19

Proposition 4: Suppose lim φi (t) = 0 in (23), i ∈ V, if the directed graph G(A) has
t→∞

a spanning tree and 0 < h < min

2≤i≤n

asymptotically.

2Re(λi (L))
,
|λi (L)|2

then MAS (2) with (23) reaches consensus

Proof: It can be proved by replacing the variable x̄(t) in the proof of Proposition 3 with
x̂(t) defined in the proof of Proposition 1, and using the fact that max |1 − hλi (L)| < 1 if G
2≤i≤n

2Re(λi (L))
2 ,
2≤i≤n |λi (L)|

has a spanning tree and 0 < h < min

which is stated in Lemma 12.

Now we give the convergence condition for (2) with (23) and its proof in detail when the
graph is directed.
Theorem 5: Under Assumptions 1 and 5, suppose {α(t)}, {β(t)} are two sequences such that
∞
∞
P
P
(a) α(t) ∈ [0, 1],
α(t) → ∞ and
α2 (t) < ∞;
t=0

(b) 0 ≤ β(t) ≤ ∞,

∞
P

t=0

t=0

β(t) → ∞ and

∞
P

t=0

β 2 (t) < ∞.

If the directed graph G(A) is strongly connected and 0 < h < ̺, where ̺ = min
i (L))
min 2Re(λ
2
|λ
(L)|
i
1≤i≤n

h

max

1
n
P

aij

!,

1≤i≤n j=1
i
. Then, MAS (2) with (23) reaches consensus asymptotically, and the consensus

state is in set X∗ .

Proof: Since the graph is strongly connected, by Lemma 2, there exists a vector w =
[w1 · · · wn ]T > 0 such that w T L = 0. Submitting (23) to (2), we have
xi (t + 1) = ξi (t) − ϕi (t),

i ∈ V.

Consider the positive-definite Lyapunov function candidate V (t) =
x0 ∈ X∗ . Taking the difference of function V (t) yields
∆V (t) = V (t + 1) − V (t)
=

n
X
i=1

=

n
X
i=1

−
≤

December 16, 2016

wi kξi (t) − ϕi (t) − x0 k2 −

i=1

i=1

i=1

i=1

wi kxi (t) − x0 k2 , where

wi kxi (t) − x0 k2

wi k(1 − α(t))(ξi (t) − x0 ) + α(t)(PXi (ξi (t)) − x0 )k2

n
X

n
X

n
X

n
P

wi kxi (t) − x0 k2


2
wi (1 − α(t))kξi (t) − x0 k + α(t)kPXi (ξi (t)) − x0 )k

DRAFT

20

−
≤
=

n
X
i=1

n
X
i=1

n
X
i=1

+

2

wi kξi (t) − x0 k −
wi kyi (t) − x0 k2 −

n
X
i=1

where yi (t) = xi (t) + h

P

j∈Ni

wi kxi (t) − x0 k2

2

wi k∇i (t)k −

n
X
i=1

n
X
i=1

n
X
i=1

wi kxi (t) − x0 k2
(26)
wi h∇i (t), yi (t) − x0 i

wi kxi (t) − x0 )k2

aij (xj (t) − xi (t)) and the last inequality follows form using the

non-expansiveness property of projection operator, i.e., kPXi (ξi (t)) − x0 )k ≤ kξi (t) − x0 k. Since
∇gi+ (t) denotes the subgradient of function gi+ (y) at y = yi (t), we have
− h∇i (t), yi (t) − x0 i ≤ −β(t)gi+ (yi (t)) ≤ 0.
Moreover, since 0 < h <
max

1≤i≤n

norm square function, it holds

1
n
P

aij

j=1

kyi (t) − x0 k2 = k(1 − h
≤ (1 − h

we have 0 < 1 − h

!,

X

j∈Ni

X

j∈Ni

n
P

(27)

aij < 1. By the convexity of the

j=1

lij )(xi (t) − x0 ) + h

lij )kxi (t) − x0 k2 + h

X

lij (xj (t) − x0 )k2

X

lij kxj (t) − x0 k2 .

j∈Ni

j∈Ni

Thus, we have
n
X
i=1

2

wi kyi (t) − x0 k ≤

n
X
i=1

+h

wi (1 − h
n
X
i=1

=

n
X
i=1

+h
=

i=1

December 16, 2016

j∈Ni

X

j∈Ni

lij )kxi (t) − x0 k2

lij kxj (t) − x0 k2
2

wi kxi (t) − x0 k − h
n
n
X
X
j=1

n
X

wi

X

i=1

wi lij

!

n
X
i=1

wi

n
X
j=1

lij

!

kxi (t) − x0 k2

(28)

kxj (t) − x0 k2

wi kxi (t) − x0 k2

DRAFT

21

where the last equation results from the fact that

n
P

lij = 0 and

∆V (t) ≤ −β(t)
From (29), we have V (t) ≤ V (0) +

t−1
P

t=0

n
X

wi lij = 0. Submitting (27)

i=1

j=1

and (28) into (26) yields

n
P

wi gi+ (yi (t)) +

i=1

n
X
i=1

wi k∇i (t)k2 .

β 2 (t)(w T 1n )K ≤ V (0) +

∞
P

t=0

(29)

β 2 (t)(w T 1n )K < ∞. By the

definition of V (t), it can be concluded that xi (t) is bounded. By the fact that k∇i (t)k < ∞, we
know kξi (t)k < ∞, this and the continuity of PXi (ξi ) imply kξi (t) − PXi (ξi (t))k < ∞. Thus,
lim ϕi (t) = 0. Since graph G(A) is strongly connected and 0 < h < min

2≤i≤n

t→∞

2Re(λi (L))
,
|λi (L)|2

from

Proposition 4, it can be concluded that MAS (2) with (23) reaches consensus asymptotically,
i.e., lim kxi (t) − xj (t)k = 0 for all i, j ∈ V. Moreover, similar to (26), we have
t→∞

∆V (t) = V (t + 1) − V (t)
=

n
X
i=1

=

n
X
i=1

=

n
X
i=1

+

2

wi kyi (t) − x0 − ∇i (t) − ϕi (t)k −
wi kyi (t) − x0 − ∇i (t) − ϕi (t)k2 −
wi kyi (t) − x0 k2 − 2

n
X

= −2

wi k∇i (t) + ϕi (t)k −

i=1
n
X

−2
= −2
+

i=1
n
X

i=1
n
X

December 16, 2016

n
X

i=1

wi kxi (t) − x0 )k2

i=1

wi kxi (t) − x0 )k2

wi h∇i (t), yi (t) − x0 i − 2
wi hϕi (t), ∇i (t)i +

i=1

n
X

wi kxi (t) − x0 )k2

wi h∇i (t) + ϕi (t), yi (t) − x0 i

wi h∇i (t) + ϕi (t), yi (t) − x0 i +

i=1
n
X

i=1

i=1

2

i=1
n
X

≤ −2

n
X

n
X

n
X
i=1

i=1

i=1

wi k∇i (t) + ϕi (t)k2

wi hϕi (t), ξi (t) − x0 i

wi k∇i (t) + ϕi (t)k2

wi h∇i (t), yi (t) − x0 i − 2

wi k∇i (t)k2 + kϕi (t)k2

n
X

n
X

n
X
i=1

wi hϕi (t), ξi (t) − x0 i



DRAFT

22

≤ −2β(t)
+

n
X
i=1

n
X

wi gi+ (xi (t))

i=1

− 2α(t)

wi k∇i (t)k2 + kϕi (t)k

n
X
i=1


2

where the first inequality results directly from (28). Note that
∞ and −2β(t)

n
P

i=1

wi gi+ (xi (t)) − 2α(t)

n
P

i=1

wi kξi (t)k2Xi
(30)

n
∞ P
P

t=0 i=1

wi (k∇i (t)k2 + kϕi (t)k2 ) <

wi kξi (t)k2Xi < 0. By Lemma 5 and the fact that

lim xi (t) = lim xj (t), it can be concluded V (t) converges and it holds

t→∞

α(t)

t→∞

n
P

i=1

t=0

α(t) → ∞ and

(β(t)

t=0

wi kξi (t)k2Xi )

< ∞. Since

and i = 1, · · · , n, we have
∞
P

∞
P

∞
P

t=0

∞
P

t=0

β(t)gi+ (xi (t))

> 0 and

β(t)gi+ (xi (t)) < ∞ and

i=1

α(t)kξi (t)k2Xi

∞
P

t=0

n
P

wi gi+ (xi (t))+

> 0 for all t > 0

α(t)kξi (t)k2Xi < ∞. By the facts

β(t) → ∞, we have lim inf kξi (t) − PXi (ξi (t))k = lim inf gi+ (xi (t)) = 0.
t→∞

t→∞

Thus, there exists a subsequence {xi (tk )} of xi (t) such that lim xi (tk ) = x∗i , where x∗i is a vector
k→∞

such that gi+ (x∗i ) = hi (x∗i ) = 0 for each i = 1, · · · , n. Recall the fact that lim xi (t) = lim xj (t),
t→∞

x∗i

∗

x∗j

t→∞

∗

x∗i ,

we have lim xi (tk ) = x . By the fact
for any i, j ∈ V. Let x =
=
we have
k→∞
n
P
2
wi kxi (t) − x0 k converges and lim ẋi (t) = 0, we can conclude lim xi (t) = lim xi (tk ) = x∗ .
t→∞

i=1

t→∞

k→∞

Furthermore, note that ∇i (t) → 0 as t → ∞, thus lim inf kξi (t) − PXi (ξi (t))k = 0 and
t→∞

lim xi (t) = x∗ imply lim kx∗ − PXi (x∗ )k = 0 for any i ∈ V. This means x ∈ X = ∩ni=1 Xi .

t→∞

t→∞

Therefore, x∗ is a feasible solution to CFP (3), i.e., x∗ ∈ X∗ .

Corollary 3: Under Assumptions 1 and 5, suppose {α(t)}, {β(t)} are two sequences such
that
(a) α(t) ∈ [0, 1],

∞
P

t=0

(b) 0 ≤ β(t) ≤ ∞,

α(t) → ∞ and

∞
P

t=0

∞
P

t=0

β(t) → ∞ and

α2 (t) < ∞;

∞
P

t=0

β 2 (t) < ∞.

If the graph G(A) is undirected and strongly connected, 0 < h <

max

1
n
P

. Then, MAS (2)

1≤i≤n j=1

aij

with (23) reaches consensus asymptotically, and the consensus state is in set X∗ .
Proof: By Gers̆gorin Disc theorem, we can conclude h <

2
λN

if h <
max

1
n
P

1≤i≤n j=1

. Together
aij

with Lemma 11, it can be proved by using the similar approach to Theorem 5 and hence the
proof is omitted.

December 16, 2016

DRAFT

23

VI. A

SPECIAL CASE : A DISTRIBUTED GRADIENT- BASED ALGORITHM FOR

CFP S

INVOLVING LINEAR INEQUALITIES

In this section, we will develop a distributed gradient-based algorithm for the CFP as follows.

 Ai x − bi ≤ 0
i = 1, · · · , n
(31)
∆ n

=
x ∈ X : ∩i=1 Xi

where Ai ∈ Rmi ×r and b ∈ Rmi . It assumes CFP (31) has a non-empty feasible solution set X∗ .
For a vector y = [y1 , · · · , yn ]T , we define y + = [y1+ , · · · , yn+ ]T and y − = [y1− , · · · , yn− ]T ,

where yi+ = max(yi , 0) and yi− = min(yi , 0). We introduce a function ψ(y) = ky + k2 . Note that
ψ(y) = 0 if and only if y ≤ 0. The function ψ(y) is convex and differentiable. See the following
lemma for detail.
Lemma 13: For any vector y ∈ Rr , the function ψ(y) = ky + k2 is convex, differentiable and

its gradient function at point y is ∇y ψ(y) = 2y + .

Proof: . For any vector z ∈ Rr , we have ψ(y + z) = k(y + z)+ k2 = ky + z − (y + z)− k2 ≤

ky + z − (y)− k2 = ky + + zk2 ≤ ψ(y) + 2[y + ]T z + kzk2 , where the first inequality follows
from the fact that (y + z)− = arg minv≤0 k(y + z) − vk. Moreover, it holds that ψ(y + z) =

k(y + z) − (y + z)− k2 = k(y + + [y − + z − (y + z)− ]k2 ≥ ψ(y) + 2[y +]T z + ky − + z − (y + z)− k2 ≥
ψ(y) + 2[y + ]T z, where the first inequality follows from the fact that it holds that [y + ]T y − = 0

= 2[y + ]T ∆y. This means
and [y + ]T (y + z)− ≤ 0. Therefore, it holds that lim ψ(y+ε∆y)−ψy
ε
ε→0

∇y ψ(y) = 2y + . From the fact that ψ(y + z) ≥ ψ(y) + 2[y + ]T z, we know ψ(y) is convex.
Now we present the following distributed gradient-based algorithm for CFP (31).

ẋi (t) =

X

i∈Ni


aij (xj (t) − xi (t)) − τ ATi (Ai xi (t) − bi )+ + xi (t) − PXi (xi (t)) ,

i = 1, · · · , n
(32)

where τ > 0 is a positive coefficient, xi (t) ∈ Rr represents the estimation value of the solutions
to CFP (31).
Theorem 6: If the graph G(A) is strongly connected, then xi (t) in (32) converges to a fixed

vector x∗ asymptotically for i = 1, · · · , n and x∗ is in feasible solution set X∗ of (31).

Proof: By Lemma 13, it is not difficult to prove that the term ATi (Ai xi −bi )+ is the gradient

of function k(Ai xi − bi )+ k2 . It can also be viewed as the unique subgradient of k(Ai xi − bi )+ k2 .
Then this result can be proved by the same method as Theorem 3 and hence it is omitted.
December 16, 2016

DRAFT

24

VII.

SIMULATIONS

In this section, we give numerical examples to illustrate the obtained results. Consider a
multi-agent system consisting of five agents, the goal of the agents is to cooperatively search a
feasibility z ∗ = [z1∗ , z2∗ ]T of the CPF which includes two closed convex sets X1 = {(z1 , z2 )|2 ≤
z1 ≤ 4, 0 ≤ z2 ≤ 2} and X2 = {(z1 , z2 )|2.5 ≤ z1 ≤ 4.5, 1 ≤ z2 ≤ 3}, and three linear
inequalities c(z) = 2z1 − 3z2 − 2 ≤ 0, d(z) = 2z1 + 3z2 − 11 ≤ 0 and q(z) = 8z1 − 3z2 − 28 ≤ 0.
In Fig.1, the yellow region represents the feasible region. Set Xi is only known to agent i
for i = 1, 2, and agents 3, 4 and 5 can only have access to c(z), d(z), q(z), respectively. In
the following, we will present simulation results in three cases: The first two cases are for
continuous-time distributed algorithms under the fixed and time-varying graphs, respectively.
The third case is for the discrete-time distributed algorithm under the fixed graph. For each case,
the communication graph is directed.
We first show the simulation result in the first case. The communication graph is shown in
Fig. 2, which is strongly connected. The weight of each edge connecting different agents is
1. Set coefficient τ = 20 and let the initial state of each agent be x1 (0) = [0, 5]T , x2 (0) =
[3, −2]T , x3 (0) = [2, 3]T , x4 (0) = [5, 1]T , x5 (0) = [2, −3]T . The trajectory of MAS (1) with (11)

is shown in Fig. 3. All agents also reach consensus at z ∗ = [2.58, 1.23]T which is a solution to
the CFP. This is consistent with the result established in Theorem 3.

Now, we show the simulation result in the second case, the communication topologies switch
between two bidirectional subgraphs depicted in Fig. 4 and the switching law is given by Fig. 5.
It is obvious that the δ−graph associated with the time-varying graph is strongly connected. The
weight of each edge connecting different agents is also being 1. Set coefficient τ = 35. Under
the same initial condition as the first case, the trajectory of MAS (1) with (11) is shown in Fig.
6. All agents reach consensus at z ∗ = [2.61, 1.37]T while remaining in the feasible region of the
CFP. This is consistent with the result established in Theorem 4.
In addition, we show the simulation result in the third case. The communication topology in
the first case is used to conduct this simulation. Set α(t) = β(t) =

1
0.02t+1

and h = 0.25. Under

the same initial condition as the last two cases, the trajectory of MAS (2) with (23) is shown
in Fig. 7. All agents reach consensus at z ∗ = [2.57, 1.54]T which is a solution to the CFP. This
accords with the result established in Theorem 5.

December 16, 2016

DRAFT

25

5
(1) 2z −3z −2 =0
1
2
(2) 2z1+3z2−11=0
(3) 8z −3z −28=0

(3)

4

1

z2

3

(2)

2

X

2

2
1
X1

(1)

0
−1
1

2

3

4

5

6

z1

Fig. 1.

The feasible region of the CFP.

Fig. 2.

The communication graph in the first case.

6
Agent 3

4

Agent 1

z

2

2

0

2
1.5
1

Agent 4

−2
2

2.5

3

Agent 2

Agent 5

−4
−1

0

1

2

3
z

Fig. 3.

4

5

6

1

The trajectory of the multi-agent system in the first case. Symbol “*” represents the initial states of agents while “◦”

represents the final states of them.

VIII. C ONCLUSIONS
In this paper, the CFPs have been studied for multi-agent systems through local interactions.
The distributed control algorithms were designed for both continuous- and discrete-time systems,
respectively. In each case, a centralized approach was first introduced to solve the CFP. Then
distributed control algorithms were proposed based on the subgradient and projection operations.
The conditions associated with connectivity of the communication graph were given to ensure
convergence of the distributed algorithms. The results showed that for the continuous-time case,
if the communication graph is fixed and strongly connected, the MAS can reach consensus
December 16, 2016

DRAFT

26

Fig. 4. The communication graph in the second case, which consists of two subgraphs. The left one is labeled 1 and the right

3

Agent 3

2.5

4
Agent 1

2
2
1.5

0
1

2
1.5

Agent 4

1

−2

0.5

2

2.5

3
Agent 2

Agent 5

0
0

Fig. 5.

6

z2

The switching law of time−varying graph

one is labeled 2.

10

20
t

30

−4
−1

40

The switching law of the time-varying graph.

0

1

2

3

4

5

6

z1

Fig. 6.

The trajectory of the multi-agent system in the second

case. Symbol “*” represents the initial states of agents while “◦”
represents the final states of them.

asymptotically and the consensus state is located in the solution set of the CFP. Moreover, the
same result can be achieved if the δ−graph associated with a time-varying graph is strongly
connected. For the discrete-time case, under the condition of strong connectivity associated with
the directed graph, if the control gain h and the step-sizes α(t) and β(t) are properly chosen,
convergence of the distributed algorithm can also be guaranteed. Furthermore, a distributed
gradient-based algorithm has been designed for a special case in which the CFP involves linear
inequalities. Finally, simulation examples have been conducted to demonstrate the effectiveness

December 16, 2016

DRAFT

27

6
Agent 3

4
Agent 1

z

2

2
2.5

0

Agent 4

2
1.5

−2

1
2

2.5

3

Agent 2

Agent 5

−4
−1

0

1

2

3
z

Fig. 7.

4

5

6

1

The trajectory of the multi-agent system in the third case. Symbol “*” represents the initial states of agents while “◦”

represents the final states of them.

of our results. Our future work will focus on some other interesting topics, such as the case
under quantization, time delays, packet loss and communication bandwidth constraints, which
will bring new challenges in solving CFPs over a network of agents.
R EFERENCES
[1] Y. Guan, Z. Ji, L. Zhang, L.Wang. Decentralized stabilizability of multi-agent systems under fixed and switching topologies.
Systems & Control Letters, vol. 62, no. 5, pp. 438-446, 2013.
[2] J. Ma, Y. Zheng, B. Wu, L. Wang. Equilibrium topology of multi-agent systems with two leaders: A zero-sum game
perspective. Automatica, vol. 73, pp. 200-206, 2016.
[3] J. Ma, Y. Zheng, L. Wang. Topology selection for multi-agent systems with opposite leaders. Systems & Control Letters,
vol. 93, pp. 43-49, 2016.
[4] G. Jing, Y. Zheng, L. Wang. Consensus of multiagent systems with distance-dependent communication networks. IEEE
Transactions on Neural Networks and Learning Systems, DOI: 10.1109/TNNLS.2016.2598355, 2016.
[5] W. Ren, R. Beard. Consensus seeking in multi-agent systems under dynamically changing interaction topologies. IEEE
Transactions on Automatic Control, vol. 50, no. 3, pp. 655-661, 2005.
[6] R. Olfati-Saber, R. Murray. Consensus problems in the networks of agents with switching topology and time delays. IEEE
Transactions on Automatic Control, vol. 49, no. 9, pp. 1520-1533, 2004.
[7] L. Wang, F. Xiao. Finite-time consensus problems for networks of dynamic agents. IEEE Transactions on Automatic Control,
vol. 55, no. 4, pp. 950-955, 2010.
[8] Y. Zheng, L. Wang. Finite-time consensus of heterogeneous multi-agent systems with and without velocity measurements.
Systems & Control Letters, vol. 61, no. 8, pp. 871-878, 2012.
[9] F. Xiao and L. Wang. Asynchronous consensus in continuous-time multi-agent systems with switching topology and timevarying delays. IEEE Transactions on Automatic Control, vol. 53, no. 8, pp. 1804-1816, 2008.
December 16, 2016

DRAFT

28

[10] Z. Zhang, L. Zhang, F. Hao, L. Wang. Leader-Following Consensus for Linear and Lipschitz Nonlinear Multiagent Systems
With Quantized Communication. IEEE Transactions on Cybernetics, DOI: 10.1109/TCYB.2016.2580163, 2016.
[11] Y. Tang, H. Gao, W. Zou, J. Kurths. Distributed synchronization in networks of agent systems with nonlinearities and
random switchings. IEEE Transactions on Cybernetics, vol. 43, no. 1, pp. 358-370, 2013.
[12] S. Kar, J. M. F. Moura, K. Ramanan. Distributed parameter estimation in sensor networks: nonlinear observation models
and imperfect communication. IEEE Transactions on Information Theory, vol. 58, no. 6, pp. 3575-3605, 2012.
[13] P. Lin, W. Ren, Y. Song. Distributed multi-agent optimization subject to nonidentical constraints and communication delays.
Automatica, vol. 65, pp. 120-131, 2016.
[14] A. Nedić, A. Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic
Control, vol.60, no.3, pp. 601-615, 2015.
[15] S. Rahili, W. Ren. Distributed continuous-time convex optimization with time-varying cost functions. IEEE Transactions
on Automatic Control, DOI 10.1109/TAC.2016.2593899, 2016.
[16] S. Mou, J. Liu, A. S. Morse. A distributed algorithm for solving a linear algebraic equation. IEEE Transactions on
Automatic Control, vol. 60, no. 11, pp. 2863-2878, 2015.
[17] H. Cao, T. E. Gibson, S. Mou, Y. Liu. Impacts of network topology on the performance of a distributed algorithm solving
linear equations. arXiv preprint arXiv: 1603.04154, 2016.
[18] S. Martin, J. M. Hendrickx. Continuous-time consensus under non-instantaneous reciprocity. IEEE Transactions on
Automatic Control, vol. 61, no. 9, pp. 2484-2495, 2016.
[19] J. M. Hendrickx, J. N. Tsitsiklis. Convergence of type-symmetric and cut-balanced consensus seeking systems. IEEE
Transactions on Automatic Control, vol. 58, no. 1, pp. 214-218, 2013.
[20] A. Jadbabaie, J. Lin, A. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE
Transactions on Automatic Control, vol. 48, no. 6, pp. 988-1001, 2003.
[21] L. Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic
Control, vol. 50, no. 2, pp. 169-182, 2005.
[22] A. Nedić, A. Ozdaglar, P. A. Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions
on Automatic Control, vol. 55, no. 4, pp. 922-938, 2010.
[23] S. S. Ram, A. Nedic, V. V. Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization.
Journal of Optimization Theory and Applications, vol.147, pp. 516-545, 2010.
[24] P. Lin, W. Ren. Constrained consensus in unbalanced networks with communication delays. IEEE Transactions on
Automatic Control, vol. 59, no. 3, PP. 775-781, 2014.
[25] G. Shi, K. H. Johansson, Y. Hong. Reaching an optimal consensus: dynamical systems that compute intersections of convex
sets. IEEE Transactions on Automatic Control, vol. 58, no.3, pp. 610-622, 2013.
[26] G. Shi, B. D. O. Anderson. Distributed network flows solving linear algebraic equations. 2016 American Control Conference
(ACC). IEEE, pp. 2864-2869, 2016.
[27] T. M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition.
IEEE transactions on electronic computers, vol. EC-14, pp. 326-334, 1965.
[28] I. Yamada, K. Slavakis, K.Yamada. An efficient robust adaptive filtering algorithm based on parallel subgradient projection
techniques. IEEE Transactions on Signal Processing, vol. 50, no. 5, pp. 1091-1101, 2002.
[29] Y. Censor, M. D. Altschuler, W. D. Powlis. On the use of Cimminos simultaneous projections method for computing a
solution of the inverse problem in radiation therapy treatment planning. Inverse Problems, vol. 4, pp. 607-623, 1998.

December 16, 2016

DRAFT

29

[30] G. T. Herman. Image reconstruction from projections. Academic Press, New York, 1980.
[31] S. Han, O. Mangasarian. Exact penalty functions in nonlinear programming. Mathematical programming, vol. 17, no. 1,
pp. 251-269, 1979.
[32] D. Richert, J. Cortés. Robust Distributed Linear Programming. IEEE Transactions on Automatic Control, vol. 60, no. 10,
PP. 2567-2582, 2014.
[33] C. Godsil, G. Royle. Algebraic Graph Theory. New York: Springer, 2001.
[34] J. Aubin, A. Cellina. Differential Inclusions. Berlin, Germany: Speringer-Verlag, 1984.
[35] H. Robbins, D. Siegmund. A convergence theorem for nonnegative almost supermartingales and some applications.
Optimizing Methods in Statistics, Academic Press, New York, pp. 233-257, 1971.
[36] B. Touri, B. Gharesifard. Continuous-time distributed convex optimization on time-varying directed networks. 2015 54th
IEEE Conference on Decision and Control (CDC), IEEE, pp. 724-729, 2015.
[37] K. Lu, G. Jing, and L. Wang. Distributed algorithms for solving convex inequalities. arXiv preprint arXiv:1609.03161,
2016.
[38] B. Touri. Product of random stochastic matrices and distributed averaging. Springer, 2012.
[39] R. W. Brockett. Finite-Dimensional Linear Systems. New York: Wiley, 1970.

December 16, 2016

DRAFT

