Automatica 122 (2020) 109286

Contents lists available at ScienceDirect

Automatica
journal homepage: www.elsevier.com/locate/automatica

Distributed algorithms for computing a fixed point of multi-agent

nonexpansive operatorsI
⇤
Xiuxian Li, Lihua Xie
School of Electrical and Electronic Engineering, Nanyang Technological University, 50 Nanyang Avenue, Singapore, 639798, Singapore

article info a b s t r a c t

Article history: This paper investigates the problem of finding a fixed point for a global nonexpansive operator under
Received 1 November 2019 time-varying communication graphs in real Hilbert spaces, where the global operator is separable
Received in revised form 27 July 2020 and composed of an aggregate sum of local nonexpansive operators. Each local operator is only
Accepted 11 August 2020
privately accessible to each agent, and all agents constitute a network. To seek a fixed point of the
Available online xxxx
global operator, it is indispensable for agents to exchange local information and update their solution
Keywords: cooperatively. To solve the problem, two algorithms are developed, called distributed Krasnosel’skiı̆–
Distributed algorithms Mann (D-KM) and distributed block-coordinate Krasnosel’skiı̆–Mann (D-BKM) iterations, for which
Multi-agent networks D-BKM is a block-coordinate version of D-KM in the sense of randomly choosing and computing only
Nonexpansive operators one block-coordinate of local operators at each time for each agent. It is shown that the proposed two
Fixed point
algorithms can both converge weakly to a fixed point of the global operator. Meanwhile, the designed
Distributed optimization
algorithms are applied to recover the classical distributed gradient descent (DGD) algorithm, devise
a new block-coordinate DGD algorithm, handle a distributed shortest distance problem in the Hilbert
space for the first time, and solve linear algebraic equations in a novel distributed approach. Finally,
the theoretical results are corroborated by a few numerical examples.
© 2020 Elsevier Ltd. All rights reserved.

1. Introduction computing a fixed point of a nonexpansive operator is the so-

called Krasnosel’skiı̆–Mann (KM) iteration (Krasnosel’skiı̆, 1955;
Fixed point theory in Hilbert spaces has a wide range of appli- Mann, 1953), which can converge weakly to a fixed point of the
cations, for instance, in optimization, game theory, and nonlinear considered nonexpansive operator under mild conditions (Reich,
numerical analysis, and so forth (Bauschke & Combettes, 2017; 1979). Along this line, fruitful results have been developed in
Cegielski, 2012). An important problem is to develop algorithms recent decades. For example, the convergence rate was analyzed
to find a fixed point for an operator or to seek a common fixed for exact and inexact KM iterations in Cominetti et al. (2014),
point for a finite/infinite family of operators. Matsushita (2017) and Bravo et al. (2019), Liang et al. (2016),
To date, a wide spectrum of works has been established to respectively. More recently, a superlinear convergent algorithm,
deal with the fixed point seeking problem for nonexpansive op- called SuperMann, was proposed and analyzed for computing a
erators under various scenarios (Borwein, Li, & Tam, 2017; Bravo, fixed point of a nonexpansive operator in Themelis and Patri-
Cominetti, & Pavez-Signé, 2019; Cominetti, Soto, & Vaisman, nos (2019). However, it is worthwhile to point out that all the
2014; Dall’Anese, Simonetto, & Bernstein, 2019; Iiduka, 2016; aforementioned works focus on the centralized case, that is, there
Kanzow & Shehu, 2017; Liang, Fadili, & Peyré, 2016; Matsushita, exists a global computing unit or coordinator who can access
2017; Shehu, 2018; Themelis & Patrinos, 2019). It is noteworthy all the information relevant to the considered problem, which is
that the conventional Picard iteration is generally not guaran- restrictive or even unimplementable for large-scale problems in
teed to converge for nonexpansive operators, thus motivating a practice.
Compared with centralized algorithms, distributed algorithms
large body of research. One of most prominent algorithms for
have a multitude of advantages, including lower computational
cost, less storage required, and more robust to failures or ma-
I This work was supported by the Ministry of Education of Singapore under
licious attacks, etc. In a distributed scenario, there are a finite
MoE Tier 1 Research Grant RG72. The material in this paper was not presented number of agents in a network, and each agent is only capable
at any conference. This paper was recommended for publication in revised form
by Associate Editor Claudio Altafini under the direction of Editor Christos G.
of accessing partial information of the studied problem, hence
Cassandras. leading to that every single agent cannot solve the global problem
⇤ Corresponding author. alone. In this case, each agent must propagate its information
E-mail addresses: [email protected] (X. Li), [email protected] (L. Xie). to some other agents via local communication in order to cope

https://doi.org/10.1016/j.automatica.2020.109286
0005-1098/© 2020 Elsevier Ltd. All rights reserved.
X. Li and L. Xie Automatica 122 (2020) 109286

with the global problem in a cooperative manner. Wherein, the (3) The studied problem provides a unified framework for
communication channels (e.g., wireless channels) are possibly various problems. Specifically, the well-known distributed
unreliable and subject to packet dropout, etc., thereby making gradient descent (DGD) algorithm can be recovered from
the communication channels time-varying. Consequently, dis- D-KM, including that a new block-coordinate DGD algo-
tributed algorithms under time-invariant/time-varying commu- rithm is provided by D-BKM, a distributed shortest distance
nication graphs have thus far been vastly investigated in dis- problem is first resolved in the Hilbert space by appeal-
tributed optimization, see Li, Xie and Hong (2020), Liang, Wang, ing to the developed algorithms, and furthermore, the de-
and Yin (2019), Liu, Qiu and Xie (2017), Mansoori and Wei (2020), signed D-KM can be leveraged to solve linear algebraic
Mateos-Núnez and Cortés (2017), Nedi¢ and Ozdaglar (2009), equations in a novel distributed manner.
Nedi¢, Pang, Scutari, and Sun (2018), Xie, You, Tempo, Song, and
Wu (2018) and Zeng, Chen, Liang, and Hong (2019), to just name The rest of this paper is structured as follows. Related basic
a few, and multi-agent systems/networks, see Guo, Li, and Xie knowledge is provided in Section 2, and the main results are pre-
(2020), Li, Chen, Su, and Li (2016), Meng, Liu, and Feng (2017), sented in Section 3, including two proposed algorithms, i.e., the
Olfati-Saber, Fax, and Murray (2007) and Ren and Cao (2010) for D-KM and D-BKM iterations. Several applications are given in Sec-
some references. tion 4, and two numerical examples are introduced in Section 5.
Over the past few years, distributed algorithms for finding Finally, the conclusion of this paper is drawn and the future topics
fixed points of operators have become a focus of researchers. are discussed in Section 6.
To be specific, the problem of seeking a common fixed point
for a finite number of paracontraction operators was addressed 2. Preliminaries and problem formulation
in Fullmer, Liu, and Morse (2016), Fullmer and Morse (2018),
and a distributed algorithm was designed along with convergence
analysis. Also, the common fixed point finding problem for a Notations: Denote by H a real Hilbert space with inner product
family of strongly quasi-nonexpansive operators was addressed h·, ·i and associated norm k · k. Define [N ] := {1, 2, . . . , N }
in Liu, Fullmer, Nedi¢, Ba≥ar and Morse (2017). The aforemen- to be the index set for any positive integer N, and denote by
tioned common fixed point seeking problem can find numerous col(z1 , . . . , zk ) the concatenated column vector or matrix of zi , i 2
applications, such as, in convex feasibility problems (Kruger, Luke, [k]. For a positive integer n, let R, Rn , Rn⇥n , and N be the sets of
& Thao, 2018; Necoara, Richtárik, & Patrascu, 2019) and solving real numbers, n-dimensional real vectors, n ⇥ n real matrices, and
linear algebraic equations in a distributed approach (Alaviani & nonnegative integers, respectively. PX (·) stands for the projection
Elia, 2018; Mou, Liu, & Morse, 2015; Wang, Mou, & Anderson, operator onto a closed and convex set X ⇢ H , i.e., PX (z) :=
2020; Wang, Mou, & Sun, 2017; Wang, Ren and Duan, 2019), arg minx2X kz xk for z 2 H . Also, let I, Id, and ⌦ be the identity
and so on. It should be noticed that the aforesaid works are only matrix of appropriate dimension, the identity operator, and the
concerned with the Euclidean space. With regard to the Hilbert Kronecker product, respectively. Define dX (z) := infx2X kz xk,
space, distributed optimization was considered under random i.e., the distance from z 2 H to the set X . Let bc c and dc e be
communication digraphs in Alaviani and Elia (2020), and the respectively the floor and ceiling functions for a real number c.
common fixed point seeking problem was taken into account Given an operator M : H ! H , define Fix(M) := {x 2 H :
for a finite collection of nonexpansive operators in Li and Feng M(x) = x}, i.e., the set of fixed points of M. Let * and ! denote
(2020), where two distributed algorithms, namely the distributed weak and strong convergence, respectively. Define a H -valued
inexact KM iteration and distributed inexact block-coordinate random variable as a measurable map x : (⌦ , F ) ! (H , B ),
KM iteration, were proposed. It can be observed that, in Li and along with the probability space (⌦ , F , P) and the expectation
Feng (2020), it is assumed that there exists at least one common E. A measurable (or F -measurable) map is defined by holding
fixed point for all local operators, which motivates the further {! 2 ⌦ : x(!) 2 S } ⇢ F for every set S 2 B . Denote by
investigation on the case without any common fixed point for all (G) the -algebra generated by the family G of random variables.
local operators. Let F = {Fk }k2N be a filtration, i.e., each Fi is a sub-sigma
Inspired by the above facts, this paper aims at proposing dis- algebra of F such that Fk ⇢ Fk+1 for all k 2 N. Let `+ (F)
tributed algorithms for finding a fixed point of a global operator be the set of [0, 1)-valued random variable sequence {⇣k }k2N
under time-varying communication graphs in real Hilbert spaces, adapted to F, i.e., ⇣k is Fk -measurable for all k 2 N, and define
P
where the global operator is separable, consisting of a sum of `1+ (F) = {{⇣k }k2N 2 `+ (F) : k2N ⇣k < 1 a.s.}. In this paper, all
local nonexpansive operators. In this problem, each local operator equalities and inequalities are understood to hold P-almost surely
is privately known to each agent in a network. To tackle the prob- (abbreviated as a.s.) whenever involving random variables, even
lem, two distributed algorithms are developed with diminishing though ‘‘P-almost surely’’ is not expressed explicitly.
stepsizes. In summary, the contributions of this paper are listed
below. Nonexpansiveness (Bauschke & Combettes, 2017): Consider an op-
erator T : S ! H , where S ⇢ H . The operator T is called
(1) To our best knowledge, this paper is the first to investigate nonexpansive if kT (x) T (y)k  kx yk for all x, y 2 S. It is
the fixed point seeking problem in real Hilbert spaces in well known that the fixed point set Fix(T ) is closed and convex if
a distributed setup. To handle the problem, a distributed T is nonexpansive (Cegielski, 2015).
algorithm, called distributed KM (D-KM) iteration, is de-
veloped, and it is shown that, under some appropriate 2.1. Problem formulation
assumptions, D-KM can converge weakly to a fixed point
of the considered global operator. The objective is to design distributed algorithms for computing
(2) To alleviate computational complexity, another algorithm, a fixed point for a global operator F in H , i.e.,
called distributed block-coordinate KM (D-BKM) iteration, N
is proposed, which is ameliorated based on D-KM by ran- 1 X
finding x 2 H , s.t. x 2 Fix(F ), F := Fi , (1)
domly selecting and computing one block-coordinate of N
i=1
local operators at a point for each agent, instead of the
whole coordinate as in D-KM. It is proved that D-BKM where Fi : H ! H is a nonexpansive operator, called a local
is still weakly convergent to a fixed point of the global operator, for all i 2 [N ]. It can be observed from (1) that the
operator. global operator F is separable and composed of a sum of local
2
X. Li and L. Xie Automatica 122 (2020) 109286

operators, which is especially practical for large-scale problems, 3.1. The D-KM iteration
and each local operator Fi can be only privately accessible to agent
i, for example, agent 1 only knows F1 , but unaware of other local For problem (1), if there exists a global computing unit who
operators. Note that application examples in real Hilbert spaces, knows the exact information F , then one famous centralized algo-
but not in Rn , include L2 ([0, 1]) (the space of all square integrable rithm, called the KM iteration (Cominetti et al., 2014; Matsushita,
functions f : [0, 1] ! R) and digital signal processing (Debnath 2017), can be used
& Mikusinski, 2005), etc.
To move forward, let us introduce an assumption, which is xk+1 = xk + ↵k (F (xk ) xk ) , (3)
needed for the ensuing convergence analysis.
where ↵k 2 [0, 1] for all k 2 N is a sequence of relaxation
parameters. It can be found in Reich (1979) that the KM iter-
Assumption 1. Each operator Fi Id is bounded, i.e.,
ation is weaklyP convergent to a fixed point of F under mild
1
kFi (x) xk  B, for some B > 0, 8i 2 [N ], x 2 H . (2) conditions, e.g., j=1 ↵j (1 ↵j ) = 1. Nevertheless, the classical
centralized algorithms are not applicable here since no global
Remark 1. It should be noted that Assumption 1 can be satisfied coordinators can access the total information on F , instead it is
in many interesting problems. For instance, consider the mini- imperative to develop distributed algorithms, which are based on
mization problem for a differentiable convex function f : Rn ! R local information exchange among all agents.
with Lipschitz gradient, that is, kr f (x) r f (y)k  Lkx yk for Inspired by the classical KM iteration, a distributed KM (D-KM)
all x, y 2 Rn and a constant L > 0. In this case, the minimization iteration is proposed for each i 2 [N ] as
problem is equivalent to the fixed point finding problem for a
N
nonexpansive operator T : x 7 ! x ⌧ r f (x), where ⌧ 2 (0, 2/L) is X
a constant (Liang et al., 2016). Then, (2) in Assumption 1 amounts xi,k+1 = x̂i,k + ↵k (Fi (x̂i,k ) x̂i,k ), x̂i,k = aij,k xj,k , (4)
to the boundedness of r f , which has been widely employed in j=1

lots of existing literature in distributed optimization, e.g., Liang where x̂i,k stands for an aggregate message received from the
et al. (2019), Liu, Qiu et al. (2017), Mateos-Núnez and Cortés neighbors of agent i at time instant k > 0, xi,k is an estimate of a
(2017), Nedi¢ and Ozdaglar (2009) and Xie et al. (2018).
fixed point of the global operator F by agent i at time slot k for
At this position, it is necessary to review graph theory for all i 2 [N ], and ↵k is a positive stepsize. As for (4), it is easy to
modeling the communications among all agents (Ren & Cao, see that the algorithm is distributed since every agent only makes
2010). Usually, a digraph G = (V , E ) is exploited to delin- use of its local information.
eate their communications, where V = [N ] and E ⇢ V ⇥ V To proceed, it is useful to postulate a few properties on ↵k .
are respectively the node (or vertex) and edge sets. An edge
(i, j) 2 E connotes an information flow from agent i to agent Assumption 3 (Stepsizes). The stepsize ↵k is nonincreasing for
j, and then agent i (resp. j) is called an in-neighbor or simply each k 2 N, satisfying the following properties:
neighbor (resp. out-neighbor) of agent j (resp. i). Moreover, a
1
X 1
X
directed path is a sequence of consecutive edges in the form
(i1 , i2 ), (i2 , i3 ), . . . , (il 1 , il ). A graph is called strongly connected if ↵k 2 (0, 1], ↵k = 1, ↵k ↵b k c < 1. (5)
2
any node in the graph has at least one directed path to any other k=1 k=1

node. To be practical, the communication graph is assumed to It is now ready for us to present the main result on D-KM.
be time-varying in this paper, i.e., any directed edge can have
distinct status at different time slots. As such, let us denote by Theorem 1. If Assumptions 1–3 hold, then all xi,k ’s generated by
Gk = (V , Ek ) the time-varying graph with k 2 N being the time D-KM (4) are bounded and converge weakly to a common point in
index. Define the union of graphs Gl = (V , El ), l = 1, . . . , m as Fix(F ).
[m m
l=1 Gl = (V , [l=1 El ). At each time k 2 N, define an adjacency
matrix as Ak = (aij,k ) 2 RN ⇥N such that aij,k > 0 if (j, i) 2 Ek , Proof. The proof is postponed to Appendix A.1. ⌅
and aij,k = 0 otherwise. It is standard to assume the following
assumptions.
Remark 2. In contrast to Fullmer and Morse (2018), where the
common fixed point seeking problem is studied in the Euclidean
Assumption 2 (Q -Strong-Connectivity and Weights Rule).
space, the problem here is more general, where we do not assume
(1) Gk is uniformly jointly strongly connected, i.e., there exists a common fixed point for all Fi ’s and consider the problem in real
Q
an integer Q > 0 such that the graph union [l=1 Gk+l is Hilbert spaces. Our work also extends the case where all local
strongly connected for all k 0. operators have nonempty common fixed points addressed in Li
PN
For all k 2 N, Ak is doubly stochastic, i.e., j=1 aij,k = 1 and
(2) P and Feng (2020) in real Hilbert spaces. Note that the methods
employed in Li and Feng (2020) are no longer applicable to
i=1 aij,k = 1 for all i, j 2 [N ]. Meanwhile, aij,k > a for a
constant a 2 (0, 1) whenever aij,k > 0, and aii,k > a for all the problem studied here. Also, without the property of having
i 2 [N ], k 2 N. at least a common fixed point for all Fi ’s, the problem here
requires more stringent assumptions than those in Li and Feng
It should be noted that Metropolis weights (Ba≥ary, Etesami, & (2020). That is, Assumption 1 and the column-stochasticity in
Olshevsky, 2014) can be employed to satisfy the double-stochas- Assumption 2 in this paper are not needed in Li and Feng (2020),
ticity for undirected graphs. For directed graphs, the double-
and the conditions on stepsize {↵k } in Assumption 3 are more
stochasticity can be ensured by several methods in the literature.
restrictive than that in Li and Feng (2020), where ↵k can even be
For example, some distributed strategies were proposed in Ghare-
a positive constant. On the other hand, it is worth pointing out
sifard and Cortés (2012) for strongly connected directed graphs to
that Theorem 1 still holds for the case with F , Fi : X ! X , where
compute a doubly stochastic weight assignment in finite time.
X ✓ H is nonempty, closed and convex with X \ Fix(F ) 6 = ;.
3. Main results
Remark 3. Note that decaying stepsizes are employed in The-
This section aims at proposing two distributed algorithms for orem 1. In general, the exact weak convergence cannot be es-
coping with problem (1), i.e., D-KM and D-BKM. tablished for D-KM under constant stepsizes, as in the standard
3
X. Li and L. Xie Automatica 122 (2020) 109286

distributed optimization (Nedi¢ & Ozdaglar, 2009). However, we it over i 2 [N ] and invoking the double-stochasticity of Ak in
believe that the weak convergence within a ball can be ensured Assumption 2, it can be obtained that
by some constant stepsize (Simonetto, 2017; Yuan, Ling, & Yin, ⇣ PN T ⌘ PN
2016), although the current technical analysis is not applicable i=1 i,k i=1 xi,k
x̄k+1 = x̄k + ↵k x̄k ,
. x̄k :=
(8)
to the case of constant stepsize since its convergence analysis N N
critically depends on Assumption 3. Moreover, the exact con- Before presenting the main result, it is helpful to propose a
vergence may also be guaranteed using identical/nonidentical new norm |||·||| and corresponding inner product hh·, ·ii on H as
constant stepsizes (e.g., Alexander, Cesar, Alexander, Nikolai, & in Li and Feng (2020), i.e., for any y, z 2 H
Angelia, 2020; Wang, Zhou, Mou and Corless, 2019) by tracking m
X m
X
F for each agent (Xu, Zhu, Soh, & Xie, 2018), which is one of our 1 1
|||y|||2 := kyl k2 , hhy, z ii := hyl , zl i, (9)
ongoing research works. pl pl
l=1 l=1

3.2. The D-BKM iteration for which it is easy to verify that kyk2  |||y|||2  kyk2 /p0 , where
p0 := minl2[m] pl .
This subsection is concerned with developing another dis- We are now in a position to give the main result on (6).
tributed algorithm for handling problem (1). In reality, it may be
computationally expensive or prohibitive to compute the whole Theorem 2. If Assumptions 1–3 hold, then all xi,k ’s generated by
coordinates of Fi at a point for i 2 [N ]. Instead, it is preferable D-BKM (6) are bounded and converge weakly, in the space (H , |||·|||),
and practical to randomly compute only a partial coordinates of to a common point in Fix(F ) a.s.
Fi at the point for i 2 [N ], in order to alleviate the computational
complexity. For example, in Remark 1 the operator T = Id ⌧ r f Proof. The proof is postponed to Appendix A.2. ⌅
involves the gradient r f , which is known to be computationally
heavy to calculate the entire coordinates of r f (x) at a point x Remark 4. It is worthwhile to notice that the D-BKM iteration (6)
especially when x is of large dimension, while it is cheaper to requires a global coordinator to randomly select one of m block-
only compute some partial coordinates of r f (x). coordinates for all agents at each time instant, while no such sort
In this subsection, H = H1 · · · Hm is the direct Hilbert of global coordinator is required in Li and Feng (2020) for the
sum with Borel -algebra B and each Hi , i 2 [m] being a case where all local operators have common fixed points. In this
separable real Hilbert space. H is endowed with the same inner regard, the main difficulty lies in the general setup in this paper
product h·, ·i and associated norm k · k as before. Denote by that no common fixed point is assumed for all local operators, and
x = (x1 , . . . , xm ) a generic vector in H . All local operators are par- it is still open to consider the case where no such coordinator is
titioned into m block-coordinates, i.e., Fi : x 7 ! (Fi1 (x), . . . , Fim (x)) present in the network, which is left as one of our future works.
with Fil : H ! Hl being measurable for all i 2 [N ] and l 2 [m].
To tackle problem (1), another distributed algorithm, called 4. Applications
distributed block-coordinate KM (D-BKM) iteration, is designed in
4.1. Distributed gradient descent algorithm
(6). Let each initial vector xi,0 be a H -valued random variable
for all i 2 [N ]. At time k + 1, a global coordinator randomly
In this subsection, let us consider the following distributed
selects a block-coordinate number, say q 2 [m], with a probability
optimization problem in real Hilbert spaces
distribution, and then broadcast the number q to all agents.
Subsequently, each agent i 2 [N ] only needs to compute Fiq (x̂i,k ) N
X
(instead of the whole coordinates Fi (x̂i,k )), updates all block- min f (x) := fi (x), (10)
coordinates as in (6) with bl,k = 1 for l = q and with bl,k = 0 i=1
for l 6 = q, and then propagates xi,k+1 to its out-neighbors. where fi : H ! R is a convex and differentiable function with
N Lipschitz gradient of constant Li for all i 2 [N ].
X
x̂il,k = aij,k xjl,k , 8l 2 [m], i 2 [N ] (6a) Define L := maxi2[N ] Li and Fi := Id ⌧ r fi for a constant
j=1
⌧ 2 (0, 2/L). Note that L can be obtained in a distributed manner
in finite time using a max-consensus algorithm (Li, Feng and
xil,k+1 = x̂il,k + bl,k ↵k (Fil (x̂i,k ) x̂il,k ), (6b) Xie, 2020). It can be then asserted that the operators Fi ’s are all
where xi,k = (xi1,k , . . . , xim,k ) represents an estimate of a fixed nonexpansive (Liang et al., 2016). As a result, it is easy to verify
that problem P (10) is equivalent to finding fixed points of the
point of the global operator F for agent i at time step k, and x̂il,k N
is the lth block-coordinate of x̂i,k = (x̂i1,k , . . . , x̂im,k ), serving as operator F := i=1 Fi /N, which is exactly the same as (1).
an aggregate information collected from its neighbors at time in- In this respect, the D-KM and D-BKM iterations become
stant k. Moreover, {bl,k }k2N is a sequence of {0, 1}-valued random xi,k+1 = x̂i,k + k r fi (x̂i,k ), (11)
variables (independently identically distributed). Also, {↵k }k2N is
a sequence of stepsizes. xil,k+1 = x̂il,k + bl,k k r fil (x̂i,k ), (12)
For brevity, let i,k := (xi,0 , . . . , xi,k ), k := ( 1,k , . . . , N ,k ), respectively, of which (11) is the classical distributed gradient
and Ei,k := (bi,k ) for i 2 [N ] and k 2 N. Set = { k }k2N . It is descent (DGD) algorithm (Liu, Qiu et al., 2017; Nedi¢ & Ozdaglar,
standard to assume that Ei,k is independent of both k and Ej,k for 2009; Yuan et al., 2016), and (12) is a block-coordinate based
j 6 = i 2 [N ]. Moreover, define pl := P(bl,0 = 1) and assume pl > 0 DGD algorithm. Wherein, k := ⌧ ↵k , ↵k is the stepsize satisfying
for all l 2 [m], connoting that there is an opportunity for every Assumption 3, x̂i,k and bl,k are the same as in (4) and (6b),
block-coordinate to be selected. respectively, and fil , x̂il,k are the lth components of fi and x̂i,k for
To proceed, it is helpful to rewrite (6) as xil,k+1 = x̂il,k + l 2 [m], respectively. Hence, under Assumptions 1–3, Theorems 1
↵k (Til,k x̂il,k ), where and 2 hold for (11) and (12), respectively. It should be noted that
Assumption 1 in this case amounts to saying that the gradients of
Til,k := x̂il,k + bl,k (Fil (x̂i,k ) x̂il,k ). (7)
all fi ’s are bounded, which is widely employed in the literature,
By defining Ti,k := (Ti1,k , . . . , Tim,k ), (6) can be further rewritten e.g., Liang et al. (2019), Liu, Qiu et al. (2017), Mateos-Núnez and
in a compact form as xi,k+1 = x̂i,k + ↵k (Ti,k x̂i,k ). By summing Cortés (2017), Nedi¢ and Ozdaglar (2009) and Xie et al. (2018).

4
X. Li and L. Xie Automatica 122 (2020) 109286

Remark 5. To our best knowledge, (12) is the first block- 4.3. Solving linear algebraic equations
coordinate DGD algorithm for distributed optimization under
time-varying directed communication graphs. We note that the This subsection is on a classical problem of solving a linear
distributed optimization (10) was also studied recently in Ala- algebraic equation in a distributed approach, that is,
viani and Elia (2020) in real Hilbert spaces and in Alexander
et al. (2020) and Iiduka (2018) in the Euclidean space. However, solving H(x) := Rx r = 0, (16)
problem (10) is a special case of problem (1) in real Hilbert n
where x 2 R , r 2 R , and R 2 R n n⇥n
is a symmetric positive
spaces. Note that the weak convergence may be established by semi-definite matrix with positive diagonal entries. This setting
analyzing the dynamic/static regret in the online case (Zhang, is general, since the form Ax = b with A 2 Rd⇥n , b 2 Rd can be
Ravier, Tarokh, & Zavlanos, 2019), i.e., all fi ’s are time-varying, cast as (16) by defining R = A> A and r = A> b.
which however is left as one of future works. It is easy to see that (16) amounts to finding a fixed point of
the operator F , where F is defined by F : x 7 ! (I ✓ R)x +✓ r , 8x 2
4.2. A distributed shortest distance problem
Rn for any constant ✓ > 0.
Consider the case when R and r are separable, i.e., there are
Consider now a special case of (1) by selecting Fi = PXi , where
matrices Ri ’s and vectors ri ’s such that
Xi is a subset of H for all i 2 [N ], and all Xi ’s are convex and
PN PN
compact. In this case, problem (1) reduces to Ri ri
i=1
R= , r = i=1 . (17)
1 X
N N N
finding x 2 H , s.t. x 2 Fix(F ), F := PXi , (13) In this case, agent i is only capable of accessing the information
N
i=1 on Ri and ri for each i 2 [P
N ]. Consequently, the global operator F
N
which is called a distributed shortest
PN 2distance problem, since (13) can be rewritten as F = i=1 Fi /N, where each local operator Fi
is equivalent to minimizing i=1 dXi (x) for x 2 H that can be
is defined as
applied such as in distributed shortest distance rendezvous (Lin,
Fi : x 7 ! (I ✓ Ri )x + ✓ ri , 8x 2 R n (18)
Ren, Wang, & Al-Saggaf, 2019) and source localization (Zhang,
Lou, Hong, & Xie, 2015). For example, consider a group of N robots which is nonexpansive if kI ✓ Ri k  1. In the case when all
in Rn (n = 2 or 3) with first-order dynamics xi,k+1 = xi,k + ui,k , the eigenvalues of Ri , i 2 [N ] are real and positive, ✓ can take any
where xi,k and ui,k are the position and control input of ith robot at value from (0, 1/ M ), where M := maxi2[N ] { max (Ri )} with max (·)
time k, respectively. And each robot i privately knows its own set being the largest eigenvalue of a matrix. In the case when Ri ’s are
Xi ✓ Rn . The goal of distributed shortest distance rendezvous
PN is to positive semi-definite, ✓ can take any value from (0, 2/ M ].
steer all robots to arrive at a point that minimizes i=1 d2X (x) (Lin Eventually, problem (16) is equivalent to problem (1). How-
i
et al., 2019), which fits into problem (13). For this problem, the ever, Assumption 1 cannot be directly confirmed for Fi ’s in (18),
controller is designed as ui,k = xi,k + x̂i,k + ↵k (PXi (x̂i,k ) x̂i,k ) for which the following result indicates that Assumption 1 is
when applying D-KM (4). indeed correct for the D-KM iteration.
Along this line, the D-KM and D-BKM iterations become
xi,k+1 = x̂i,k + ↵k (PXi (x̂i,k ) x̂i,k ), (14) Proposition 2. Under Assumptions 2 and 3, for the D-KM iteration
with Fi ’s in (18), Assumption 1 holds.
xil,k+1 = x̂il,k + bl,k ↵k (PXi l (x̂i,k ) x̂il,k ), (15)
respectively, where PXi l is the lth component of PXi , i.e., PXi = Proof. The proof is postponed to Appendix A.4. ⌅
(PXi 1 , . . . , PXi m ). Based on Proposition 2, Assumptions 2 and 3, Theorem 1 holds,
Due to the compactness of Xi ’s, it is easy to see that kPXi (x)k that is, the D-KM iteration is strongly convergent to a solution of
is bounded for any x 2 H and all i 2 [N ], which however cannot problem (16).
ensure the correctness of Assumption 1. Thus, there is a need to
first show the boundedness in Assumption 1.
Remark 7. Lots of existing works focus on solving (16) in a
distributed manner, such as Alaviani and Elia (2018), Mou et al.
Proposition 1. Under Assumptions 2 and 3, for iterations (14) and
(2015), Wang et al. (2017) and Wang, Ren et al. (2019). However,
(15) with pl = 1/m for l 2 [m], Assumption 1 holds.
these works can only handle the case where each agent knows
some complete rows of R and corresponding entries of r, while
Proof. The proof is postponed to Appendix A.3. ⌅
the setup here allows each agent to access a matrix Ri , which can
Equipped with Proposition 1, Assumptions 2 and 3, the weak be sparse, including a row case as a special case, i.e., Rowi0 (Ri ) =
convergence to a solution of (13) for iterations (14) and (15) with Rowi0 (R) with small positive diagonal entries and other entries be-
pl = 1/m can be ensured by Theorems 1 and 2. ing 0, where Rowi0 (W ) denotes the ith row of a matrix W = (wij )
by setting wii = 0. Thus, this paper provides a new perspective
Remark 6. The distributed shortest distance problem has been for solving (16) in a distributed manner. Although a relatively
investigated in Lin et al. (2019) and Lou, Hong, and Wang (2016), general partition of R is addressed in Wang et al. (2020) based
where distributed continuous-time algorithms are designed in on a double-layered network, it only applies to undirected and
the Euclidean space. In contrast, this paper develops distributed fixed graphs, and only provides continuous-time algorithms. In
discrete-time algorithms (14) and (15) in the Hilbert space. Par- contrast, the D-KM iteration here is a discrete-time algorithm,
ticularly, to our best knowledge, (15) is the first distributed and the underlying communication graph is simple one-layered,
block-coordinate algorithm for (13) under time-varying directed directed, and time-varying.
graphs. It is also worth mentioning that problem (13) encom-
passes the classical convex feasibility problem (Kruger et al., 2018; 5. Numerical examples
Necoara et al., 2019) as a special case, i.e., find x 2 H , s.t. x 2
\Ni=1 Xi , when all Xi ’s have a common point due to Fix(F ) = Consider the distributed shortest distance problem (Lou et al.,
\Ni=1 Fix(Fi ) = \Ni=1 Xi (e.g., Proposition 4.47 in Bauschke and 2016) in Section 4.2 with N = 100 agents in R3 , i.e., minx2R3
PN 2
Combettes (2017)). 3
i=1 dX (x), where Xi ’s are convex and compact subsets of R and
i

5
X. Li and L. Xie Automatica 122 (2020) 109286

Fig. 1. Evolutions of xi2,k ’s by D-KM. (a) Q = 2; (b) Q = 10.

Fig. 2. Evolutions of xi2,k ’s by D-BKM. (a) Q = 2; (b) Q = 10.

agent i can only accesspXi . pIn this case, Fi = PXi for all i 2 [N ]. Let been presented to support the theoretical results. Directions for
↵p = 1p/k 0.7
and X = [ i , i + 1] ⇥ [sin(i⇡/2), 1 + sin(i⇡/2)] ⇥ future work include convergence speed, fully distributed block-
k pi
[ i N + 2, i] for all i 2 [N ]. coordinate KM iteration (i.e., without the global coordinator for
By choosing the initial vectors arbitrarily, the simulation tra- selecting the updated block-coordinate for all agents), the case
jectories are given in Figs. 1 and 2 for the D-KM and D-BKM with random communication graphs, the nonidentical stepsize
iterations, respectively, where pl = P(bl,0 = 1) = 1/3 for case, the constant stepsize case, and the resilience of proposed
l 2 [3] for the D-BKM iteration. Note that only the evolutions of algorithms (Wang, Mou and Sundaram, 2019).
the second coordinate are presented due to space limitation. The
Acknowledgments
simulation results indicate that both algorithms indeed converge
to the solution of the studied problem as asserted in Theorems 1
The authors are grateful to the Editor, the Associate Editor and
and 2. Meanwhile, in both simulations, it can be observed that the
the anonymous reviewers for their insightful comments.
convergence rate for Q = 2 is faster than that for Q = 10, which
is consistent with the intuition that the convergence is faster for Appendix
more connected communication graphs.

6. Conclusion A.1. Proof of Theorem 1

This paper has addressed the fixed point seeking problem Lemma 1 (Li & Feng, 2020). Let {vk } be a sequence of nonnegative
for a global nonexpansive operator in real Hilbert spaces, where scalars such that vk+1  (1 + bk )vk uk + ck for
P1 all k 0, where
the global operator is a sum of local nonexpansive operators b
P k 0, uk 0 and ck 0 for all k 0 with k=1 bk < 1 and
1
and each local operator is only privately accessible to individual k=1 ck < 1. Then, the sequence {vk } converges to some v 0
agent. In the setup, all agents must communicate via information P1
and k=1 uk < 1 .
exchange to handle the problem in a cooperative way, and the
communications among all agents are directed and time-varying,
Lemma 2 (Bauschke & Combettes, 2017). Let x, y 2 H , and let
satisfying Q -strong-connectivity. To deal with the problem, two
r 2 R. Then
distributed algorithms have been developed and rigorously an-
alyzed for the weak convergence. One algorithm is called the krx + (1 r)yk2 = r kxk2 + (1 r)kyk2 r(1 r)kx yk2 .
D-KM iteration, motivated by the classical centralized KM it-
eration, and the other is called the D-BKM iteration, which is Lemma 3 (Li & Feng, 2020). Let A 2 Rn⇥n and B be a linear operator
the block-coordinate version of the D-KM iteration. As appli- in real Hilbert space H , then kA ⌦ Bk  namax kBk, where amax is
cations of the theoretical results in this paper, three problems the largest entry of the matrix A in the modulus sense.
have been considered, i.e., distributed optimization, a distributed
shortest distance problem, and solving linear algebraic equa- Lemma 4. Under Assumptions 1–3, there holds that kxi,k x̄k k =
PN
tions in a distributed manner. Numerical examples have also O(↵b k c ), where x̄k = i=1 xi,k /N for all k 2 N.
2

6
X. Li and L. Xie Automatica 122 (2020) 109286

Proof. The D-KM iteration (4) can be compactly written as  ka1 k2 + ka2 k2 + 2ka1 k · ka2 k
N N
xk+1 = (Ak ⌦ Id)xk + "k , (19) 2ka1 k X 1 X
 kx̄k x⇤ k 2 + kx̂i,k x̄k k + kx̂i,k x̄k k2
where xk := col(x1,k , . . . , xN ,k ) and "k := col(↵k (F1 (x̂1,k ) N N
i=1 i=1
x̂1,k ), . . . , ↵k (FN (x̂N ,k ) x̂N ,k )). Note that k"k k ! 0 as ↵k ! 0 and N
Fi (x̂i,k ) x̂i,k are bounded under Assumption 1. For (19), invoking 2ka1 k + 1 X
the same reasoning as in Lemmas 3 and 4 in Xie et al. (2018),  kx̄k x⇤ k2 + kxj,k x̄k k, (26)
N
together with Lemma 3, yields the conclusion. ⌅ j=1

With the above lemmas, it is now ready to prove Theorem 1. where the nonexpansiveness of Fi ’s is used to get the second
inequality, and (22) is employed to deduce the last inequality.
Proof of Theorem 1. For (19), by left multiplying a row vector For S2 , it can be obtained that
(1, . . . , 1), it is easy to obtain that S2 = k F (x̄k ) x̄k +a2 k2 ( k a3 k ka2 k)2
⇣ PN F (x̂ ) ⌘ | {z }
i=1 i i,k =:a3
x̄k+1 = x̄k + ↵k x̄k . (20)
N ka3 k 2

Now, for any x⇤ 2 Fix(F ), appealing to (20) gives rise to ka2 k2 , (27)
2
⇣ PN Fi (x̂i,k ) ⌘
i=1 where the last inequality has applied the fact that (a b)2
kx̄k+1 x⇤ k = k(1 ↵k )(x̄k x⇤ ) + ↵ k x⇤ k
N a2 /2 b2 for any a, b 0.
PN Plugging (26) and (27) into (25) results in
Fi (x̄k )
 (1 ↵k )kx̄k x k + ↵k k i=1⇤
x⇤ k N
N 2↵k ka1 k X
PN PN kx̄k+1 x⇤ k2  kx̄k x⇤ k2 + kxj,k x̄k k
i=1 Fi (x̂i,k ) i=1 Fi (x̄k ) N
+ ↵k k k j=1
N N
N N
N
↵k X ↵k X ↵k (1 ↵k ) X
 kx̄k ⇤
x k+ kFi (x̂i,k ) Fi (x̄k )k + kxj,k x̄k k2 + kxj,k x̄k k2
N N N
i=1 j=1 j=1

N ↵k (1 ↵k )
↵k X kF (x̄k ) x̄k k2
 kx̄k x⇤ k + kx̂i,k x̄k k, (21) 2
N ↵k (1 ↵k )
i=1
 kx̄k x⇤ k2 kF (x̄k ) x̄k k2 + c2 ↵k ↵b k c (28)
where the nonexpansiveness of Fi ’s has been utilized in the last 2 2

two inequalities. for some constant c2 > 0, where the last inequality has employed
Let us consider the term kx̂i,k x̄k k. One has that Lemma 4 and the boundedness of ka1 k due to (24). P1
N
X N
X From (28), invoking Assumption 3 and LemmaP11 yields k=1
2
kx̂i,k x̄k k = k aij,k xj,k x̄k k  aij,k kxj,k x̄k k. (22) ↵k kF (x̄k ) x̄k k < 1, which, together with k=1 ↵k = 1 in
j=1 j=1
Assumption 3, follows
PN lim infkF (x̄k ) x̄k k = 0. (29)
In view of i=1 aij,k = 1, inserting (22) to (21) leads to k!1
N
↵k X On the other hand, it can be obtained that
kx̄k+1 x⇤ k  kx̄k x⇤ k + k xj,k x̄k k
N kF (x̄k+1 ) x̄k+1 k = kF (x̄k+1 ) F (x̄k ) + F (x̄k ) x̄k+1 k
j=1
⇤ =k F (x̄k+1 ) F (x̄k ) + (1 ↵k )(F (x̄k ) x̄k )
 kx̄k x k + c1 ↵k ↵b k c , (23)
2 N
↵k X
where c1 > 0 is some constant, and the last inequality has (Fi (x̂i,k ) Fi (x̄k )) k
employed Lemma 4. N
i=1
By Assumption 3, applying Lemma 1 to (23) yields that
 kx̄k+1 x̄k k + (1 ↵k )kF (x̄k ) x̄k k
kx̄k x⇤ k is convergent, (24) N
↵k X
and hence x̄k , xi,k are bounded for all k 2 N. + kFi (x̂i,k ) Fi (x̄k )k
N
In the following, it remains to prove the weak convergence of i=1
P
xi,k ’s. To do so, one can obtain that kx̄k+1 x⇤ k2 = k(1 ↵k )(x̄k N
PN i=1 Fi (x̂i,k )
x⇤ ) +↵k ( i=1 Fi (x̂i,k )/N x⇤ )k2 , which, invoking Lemma 2, follows  ↵k x̄k + (1 ↵k )kF (x̄k ) x̄k k
N
that N
PN ↵k X
i=1 Fi (x̂i,k ) + kFi (x̂i,k ) Fi (x̄k )k
kx̄k+1 x⇤ k 2 = ↵k (1 ↵k ) x̄k 2
N
| N {z }
i=1
N
=:S2 2↵k X
PN  kF (x̄k ) x̄k k + kFi (x̂i,k ) Fi (x̄k )k
⇤ 2 i=1 Fi (x̂i,k ) ⇤ 2
N
+ (1 ↵k )kx̄k x k + ↵k x . (25) i=1
N {z N
| } 2↵k X
=:S1  kF (x̄k ) x̄k k + kxj,k x̄k k
N
j=1
Consider terms S1 and S2 . For S1 , it has that
PN PN  kF (x̄k ) x̄k k + c3 ↵k ↵b k c , (30)
i=1 Fi (x̄k ) ⇤ i=1 [Fi (x̂i,k ) Fi (x̄k )] 2 2
S1 = x +
| N {z } | N
{z } where c3 > 0 is some constant, (20) has been leveraged to obtain
=:a1 =:a2 the second equality and inequality, the nonexpansiveness of F
7
X. Li and L. Xie Automatica 122 (2020) 109286

and Fi ’s has been used in the first and fourth inequalities, and where the last inequality has exploited the nonexpansive prop-
Lemma 4 has been used in the last inequality. erty of Fi ’s. By (22), Lemma 7, and Assumption 1, from (33) one
Applying Lemma 1 to (30) implies that kF (x̄k ) x̄k k is conver- can obtain the first conclusion of this lemma.
gent, which in combination with (29) leads to For the second claim of this lemma, one has that
⇣ PN T ⌘
lim kF (x̄k ) x̄k k = 0. (31) E ||| i=1
i,k
x̄k |||2 |
k!1 k
N
At this moment, for any weak sequential cluster point xc of m PN
X 1 ⇣ Til,k ⌘
{x̄k }k2N , i.e., x̄k * xc , with reference to (31) and Corollary 4.28 = E k i=1 x̄kl k2 | k
in Bauschke and Combettes (2017), one can claim that xc 2 pl N
l=1
Fix(F ). Subsequently, appealing to Lemma 2.47 in Bauschke and m PN PN
X Fil (x̂i,k ) Fi (x̂i,k )
Combettes (2017) and (24) yields that x̄k * x0 for some point = k i=1
x̄kl k2 = k i=1
x̄k k2
x0 2 Fix(F ). Therefore, for any x 2 H and i 2 [N ], one has that N N
l=1

hxi,k 0
x , xi = hxi,k x̄k , xi + hx̄k 0
x , xi = O(1), (34)
0
 kxi,k x̄k k · kxk + hx̄k x , xi where x̄kl is the lth entry of x̄k , i.e., x̄k = (x̄k1 , . . . , x̄km ), and the
last equality has used the first conclusion of this lemma.
! 0. (32)
Regarding the third claim, using (8) implies that
As a consequence, it can be concluded that xi,k * x for all i 2 [N ]. 0
⇣ PN T ⌘
i,k
This ends the proof. ⌅ E(|||x̄k+1 2
x̄k ||| | k) =↵ 2
kE ||| i=1 x̄k |||2 | k
N
A.2. Proof of Theorem 2 = O(↵k2 ), (35)
where the last equality has made use of the second conclusion of
The following lemmas are useful for the upcoming analysis. this lemma. ⌅

Lemma 5 (Robbins & Siegmund, 1971). Let F = {Fk }k2N be a Armed with the above lemma, it is now ready to give the proof
of Theorem 2.
filtration. If {zk }k2N 2 `+ (F), {&k }k2N 2 `1+ (F), {#k }k2N 2 `+ (F),
and {⌘k }k2N 2 `1+ (F) satisfy the following inequality a.s.:
Proof of Theorem 2. Note that x̄k = (x̄k1 , . . . , x̄km ) and x⇤ =
E(zk+1 |Fk )  (1 + &k )zk #k + ⌘k , 8k 2 N (x⇤1 , . . . , x⇤m ) throughout this proof. For arbitrary x⇤ 2 Fix(F ),
invoking (8) implies that
1
then, {#k }k2N 2 `+ (F) and zk converges to a [0, 1)-valued random
variable a.s. E(|||x̄k+1 x⇤ |||2 | k)
PN
i=1 Ti,k
Lemma 6 (Li & Feng, 2020). Let T : H ! H be a nonexpansive = E(|||x̄k x⇤ + ↵k ( x̄k )|||2 | k)
N
operator with Fix(T ) 6 = ;. Then, there holds 2hy z, y T (y)i PN
Ti,k
kT (y) yk2 for all y 2 H and z 2 Fix(T ). = |||x̄k x⇤ |||2 +↵k2 E(||| i=1
x̄k |||2 | k)
N
m PN
Lemma 7. Under Assumptions 1–3, there holds that kxi,k x̄k k = X 2↵k D E( i=1 Til,k | k)
E
O(↵b k c ), a.s. 8k 2 N. + x̄kl , x̄kl x⇤l . (36)
2 pl N
l=1

Consider now the last two terms on the right-hand side of (36).
Proof. The conclusion can be readily obtained using the same ar-
First, invoking Lemma 8 yields that for some c4 > 0
gument as in Lemma 4, once noting that all error terms PN
kbl,k ↵k (Fil (x̂i,k ) x̂il,k )k = O(↵k ) a.s. ⌅ 2 i=1 Ti,k
↵ k E( ||| x̄k |||2 | k )  c4 ↵k2  c4 ↵k ↵b k c . (37)
N 2
Lemma 8. Under Assumptions 1–3, one has that Second, it can be obtained that
PN PN
Fi (x̂i,k ) m
X 2↵k D E( Til,k | E
i=1
x̄k = O(1), i=1 k)
N x̄kl , x̄kl x⇤l
pl N
⇣ PN T ⌘ l=1
E ||| i=1
i,k 2
x̄k ||| | = O(1), mP
k XD N Fil (x̂i,k ) E
N = 2↵k i=1
x̄kl , x̄kl x⇤l
E(|||x̄k+1 x̄k |||2 | k) = O(↵k2 ), a.s. N
l=1
N
where Ti,k = (Ti1,k , . . . , Tim,k ) is defined in (7). 2↵k X
= hFi (x̂i,k ) Fi (x̄k ), x̄k x⇤ i
PN N
Proof. By noting that F = i=1 Fi /N, it is easy to obtain that i=1

PN + 2↵k hF (x̄k ) x̄k , x̄k x⇤ i

i=1 Fi (x̂i,k ) N
x̄k 2↵k X
N  kx̂i,k x̄k k · kx̄k x⇤ k ↵k kF (x̄k ) x̄k k2 ,
PN N
i=1 Fi (x̂i,k ) i=1
k F (x̄k )k + kF (x̄k ) x̄k k
N where the last inequality has used the Cauchy–Schwarz inequal-
N
1 X ity, the nonexpansiveness of Fi ’s, and Lemma 6.
 kFi (x̂i,k ) Fi (x̄k )k + kF (x̄k ) x̄k k Furthermore, applying Young’s inequality to the above in-
N equality gives rise to
i=1
N m PN
1 X X 2↵k D E( i=1 Til,k | k)
E
 kx̂i,k x̄k k + kF (x̄k ) x̄k k, (33) x̄kl , x̄kl x⇤l
N pl N
i=1 l=1

8
X. Li and L. Xie Automatica 122 (2020) 109286

N
↵k X 2
↵k ↵b k c Meanwhile, by Lemma 8, it can be concluded that there exists
 kx̂i,k x̄k k + 2
kx̄k x⇤ k 2 a constant c7 > 0 such that
N ↵b k c N
2 i=1 PN
Ti,k
↵k kF (x̄k ) x̄k k2 ↵k2 E(||| i=1
x̄k |||2 | k )  c7 ↵k2 . (44)
1 N
 ↵k ↵b k c c5 + kx̄k x⇤ k 2 ↵k kF (x̄k ) x̄k k2 (38) For S6 , it can be implied that
2 N
m
for some constant c5 > 0, where the last inequality has employed X 2
S6  E(kFgl (x̄k+1 ) Fgl (x̄k )kkFgl (x̄k ) x̄kl k| k)
(22) and Lemma 7. pl
l=1
Substituting (37) and (38) into (36) implies that m
X 1
⇣ ↵k ↵b k c ⌘ E(kFgl (x̄k+1 ) Fgl (x̄k )k2 |
 k)
E(|||x̄k+1 x⇤ |||2 | k)  1+ 2
|||x̄k x⇤ |||2 pl ↵k
N l=1
m
+ (c4 + c5 )↵k ↵b k c ↵k kF (x̄k ) x̄k k2 , (39) X ↵k
2 + kFgl (x̄k ) x̄kl k2
⇤ pl
which, together with Lemma 5, results in |||x̄k x ||| is convergent, l=1

x̄k is bounded, and 1 ↵k

 E(kF (x̄k+1 ) F (x̄k )k2 | k) + kF (x̄k ) x̄k k2
1
X p0 ↵k p0
↵k kF (x̄k ) x̄k k2 < 1, a.s. (40) 1 ↵k
 E(kx̄k+1 x̄k k2 | k) + kF (x̄k ) x̄k k2 ,
k=0 p0 ↵k p0
In light of Assumption 3, one can obtain from (40) that where the Cauchy–Schwarz inequality and nonexpansiveness of
F have been invoked to obtain the second and last inequalities.
lim infkF (x̄k ) x̄k k2 = 0, a.s. Applying (8) to the above inequality implies that
k!1
PN
i.e., lim inf|||F (x̄k ) x̄k ||| = 0, a.s. (41) ↵k i=1 Ti,k ↵k
k!1 S6  E (k x̄k k2 | k) + kF (x̄k ) x̄k k2
p0 N p0
On the other hand, by (8), it can be concluded that m PN
↵k X i=1 Til,k ↵k
E(|||F (x̄k+1 ) x̄k+1 ||| | 2 = E (k x̄kl k2 | k) + kF (x̄k ) x̄k k2
k) p0 N p0
l=1
= E(|||F (x̄k+1 ) F (x̄k ) + F (x̄k ) x̄k m PN
PN ↵k X i=1 Fil (x̂i,k ) ↵k
Ti,k = pl k x̄kl k2 + kF (x̄k ) x̄k k2
↵k ( i=1 x̄k )|||2 | k ) p0 N p0
N l=1
PN
2 2
= E(|||F (x̄k+1 ) F (x̄k )||| | k) + |||F (x̄k ) x̄k ||| ↵k i=1 Fi (x̂i,k ) ↵k
PN  k x̄k k2 + kF (x̄k ) x̄k k2
p0 N p0
i=1 Ti,k
+ ↵k2 E(||| x̄k |||2 | k)
PN
Fi (x̂i,k )
N 2↵k i=1 3↵k
m  k F (x̄k )k2 + kF (x̄k ) x̄k k2
X 2 p0 N p0
+ E(hFgl (x̄k+1 ) Fgl (x̄k ), Fgl (x̄k ) x̄kl i| k) N
pl 2↵k X 3↵k
l=1
| {z }  kx̂i,k x̄k k2 + kF (x̄k ) x̄k k2
Np0 p0
=:S6 i=1
m PN 3↵k
X 2↵k Til,k  c8 ↵k ↵b k c + kF (x̄k ) x̄k k2 , (45)
i=1
E(hFgl (x̄k+1 ) Fgl (x̄k ), x̄kl i| k) 2 p0
pl N
l=1
| {z } where c8 > 0 is some constant, the nonexpansiveness of Fi ’s
=:S7 has been exploited to obtain the fourth inequality, and (22) and
m PN Lemma 7 to have the last inequality.
X 2↵k Til,k
i=1
E(hFgl (x̄k ) x̄kl , x̄kl i| k) , (42) For S7 , one has that
pl N PN
l=1 m
| {z } X 2↵k Til,k
i=1
=:S8 S7  E(kFgl (x̄k+1 ) Fgl (x̄k )kk x̄kl k| k) ,
pl N
l=1
where Fgl is the lth component of the global operator F , i.e., F (x) =
(Fg1 (x), . . . , Fgm (x)) for any x 2 H . where, invoking Assumption 1, it is easy to verify that
PN PN
In the sequel, consider each term in (42). One has that Til,k bil.k (Fil (x̂i,k ) x̂il,k )
i=1 i=1
k x̄kl k = k k
E(|||F (x̄k+1 ) F (x̄k )|||2 | k ) N N
N
1 1 X
 E(kF (x̄k+1 ) F (x̄k )k2 | k)  kFil (x̂i,k ) x̂il,k k
p0 N
i=1
1  B, a.s.
 E(kx̄k+1 x̄k k2 | k )
p0
which further implies that
 c6 ↵k2 (43)
m
X 2B↵k
for some constant c6 > 0, where the relationship after (9) has S7  E(kFgl (x̄k+1 ) Fgl (x̄k )k| k)
pl
been used to obtain the first inequality, the nonexpansiveness of l=1
p
F to deduce the second inequality, and Lemma 8 to derive the last 2 mB↵k
inequality.  E(kF (x̄k+1 ) F (x̄k )k| k)
p0
9
X. Li and L. Xie Automatica 122 (2020) 109286
p
2 mB↵k Lemma 4 holds. Now, invoking the same argument as in (21)–(24)
 E(kx̄k+1 x̄k k| k)
p0 yields that x̄k is bounded, which, together with Lemma 4, further
p implies that xi,k ’s are all bounded. Notice that Fi ’s are bounded.
2 mB↵k p
 E(kx̄k+1 x̄k k2 | k) Thus, Assumption 1 holds for (23).
p0
As for the D-BKM iteration (15), which amounts to
 c9 ↵k2 (46)
Pm p xi,k+1 = (I ↵k k )x̂i,k + ↵k k Fi (x̂i,k ) , (50)
for some constant c9 > 0, where the fact that l=1 kzl k  mkz k
for any z = (z1 , . . . , zm ) has been used to get the second in- where k := diag {b1,k I , . . . , bm,k I }.
equality, the nonexpansiveness of F to obtain the third inequality, Keeping in mind (50) and k1 ↵k k k  1, appealing to the
Jensen’s inequality to deduce the fourth inequality, and Lemma 8 same reasoning as the above for (49) gives rise to that Lemma 4
to derive the last inequality. holds a.s.
For S8 , it can be concluded that Subsequently, for x⇤ 2 Fix(F ), invoking (8) yields that
PN E(kx̄k+1 x⇤ k 2 | k)
m
X 2↵k Til,k
i=1 PN
S8 = hFgl (x̄k ) x̄kl , E( x̄kl | k) i
pl N i=1 Ti,k
l=1 = E(k(1 ↵k )(x̄k ⇤
x ) + ↵k ( x⇤ )k2 | k)
m PN N
X PN
i=1 Fil (x̂i,k ) X m
= 2↵k hFgl (x̄k ) x̄kl , x̄kl i i=1 Til,k
N  (1 ↵k )kx̄k x⇤ k2 + ↵k E (k x⇤l k2 | k)
l=1 N
l=1
= 2↵k kF (x̄k ) x̄k k2 m
PN 1 X
Xm
Fil (x̂i,k ) = (1 ↵k )kx̄k x⇤ k2 + ↵k (1 ) kx̄kl x⇤l k2
+ 2↵k hFgl (x̄k ) x̄kl , Fgl (x̄k ) i=1
i m
l=1
N PN
l=1 m
PN ↵k X i=1 Fil (x̂i,k )
m
X Fil (x̂i,k ) + k x⇤l k2
 2↵k kFgl (x̄k ) x̄kl kkFgl (x̄k ) i=1
k m N
l=1
N
l=1 1
m
X
PN = (1 ↵k )kx̄k x⇤ k2 + ↵k (1 )kx̄k x⇤ k2
i=1 Fil (x̂i,k ) m
 2B↵k kFgl (x̄k ) k PN
N ↵k Fi (x̂i,k )
l=1
PN + k i=1 x⇤ k2 , (51)
p m N
i=1 Fi (x̂i,k )
 2B m↵k kF (x̄k ) k where Lemma 2 and pl = 1/m, i 2 [m] have been applied to
N
p N
obtain the first inequality and second equality, respectively.
2B m↵k X Regarding the last term in (51), one has that
 kFi (x̄k ) Fi (x̂i,k )k
PN
N
i=1
i=1 Fi (x̂i,k )
p N k x⇤ k 2
2B m↵k X N
 kx̄k x̂i,k k PN
N i=1 Fi (x̂i,k )
i=1 =k F (x̄k ) + F (x̄k ) x⇤ k 2
N
 c10 ↵k ↵b k c (47) PN
2 i=1 Fi (x̂i,k )
=k F (x̄k )k2 + kF (x̄k ) x⇤ k 2
for some constant c10 > 0, where Assumption 1 has been N
PN
appealed to obtain the second inequality, the nonexpansiveness Fi (x̂i,k )
i=1
of Fi ’s to deduce the fifth inequality, and (22) and Lemma 7 to + 2h F (x̄k ), F (x̄k ) x⇤ i
N
derive the last inequality. N
At this position, substituting (43)–(47) into (42) yields that 1 X
 ( kx̂i,k x̄k k)2 + kx̄k x⇤ k 2
2 2 N2
E(|||F (x̄k+1 ) x̄k+1 ||| | k)  |||F (x̄k ) x̄k ||| i=1
N
3↵k 2 X
+ c10 ↵k ↵b k c + kF (x̄k ) x̄k k2 , (48) + kx̂i,k x̄k k · kx̄k x⇤ k
2 p0 N
i=1
P10
where ↵k2  ↵k ↵b k c has been utilized, and c10 := d=6 cd .
N
2 1 X
Now, applying Lemma 5 to (48), in conjunction with (40) and  ( kx̂i,k x̄k k)2 + kx̄k x⇤ k 2
N2
Assumption 3, one has that |||F (x̄k ) x̄k |||2 is convergent a.s., which, i=1
together with (41), further implies that limk!1 |||F (x̄k ) x̄k |||= PN
↵b k c
2 ⇤ 2 ( i=1 kx̂i,k x̄k k)2
0, a.s. Finally, following the same argument as that after (31), + kx̄k x k + , (52)
N N ↵b k c
Theorem 2 can be claimed. This completes the proof. ⌅ 2

where the Cauchy–Schwarz inequality and the nonexpansiveness

A.3. Proof of Proposition 1 of F and Fi ’s have been invoked to obtained the first inequality,
and Young’s inequality has been utilized to get the last inequality.
For brevity, PXi is still denoted as Fi for i 2 [N ] throughout this By (22) and Lemma 4, plugging (52) into (51) yields that
proof.
↵k ↵b k c
First, the D-KM iteration (14) can be written as E(kx̄k+1 x⇤ k 2 | 2
)kx̄k x⇤ k2 + ⇣1 ↵k ↵b k c , (53)
k)  (1 +
mN 2
xi,k+1 = (1 ↵k )x̂i,k + ↵k Fi (x̂i,k ). (49)
where ⇣1 > 0 is some constant.
Note that |1 ↵k |  1 and Fi ’s are bounded due to the Invoking Lemma 5 and Assumption 3, one can claim from
compactness of Xi . Hence, similar to Lemma 4, one can obtain that (53) that x̄k is bounded a.s., which in combination with Lemma 4
10
X. Li and L. Xie Automatica 122 (2020) 109286

ensures the boundedness of xi,k ’s a.s. The conclusion can be then Gharesifard, B., & Cortés, J. (2012). Distributed strategies for generating weight-
drawn. ⌅ balanced and doubly stochastic digraphs. European Journal of Control, 18(6),
539–557.
Guo, K., Li, X., & Xie, L. (2020). Simultaneous cooperative relative localization and
A.4. Proof of Proposition 2 distributed formation control for multiple UAVs. Science China. Information
Sciences, 63(1), Article 119201.
In this case, the D-KM iteration can be written as Iiduka, H. (2016). Convergence analysis of iterative methods for nonsmooth
convex optimization over fixed point sets of quasi-nonexpansive mappings.
xi,k+1 = ⌦i,k x̂i,k + ↵k ✓ ri , (54) Mathematical Programming, 159(1–2), 509–538.
Iiduka, H. (2018). Distributed optimization for network resource allocation with
where ⌦i,k := I ↵k ✓ Ri . It should be noted that k⌦i,k k  1 for nonsmooth utility functions. IEEE Transactions on Control of Network Systems,
all i 2 [N ], k 2 N due to kI ✓ Ri k  1 and ↵k 2 (0, 1]. 6(4), 1354–1465.
Moreover, (54) can be written in a compact form Kanzow, C., & Shehu, Y. (2017). Generalized Krasnosel’skiı̆-Mann-type iterations
for nonexpansive mappings in Hilbert spaces. Computational Optimization and
xk+1 = Tk (xk ), (55) Applications, 67(3), 595–620.
Krasnosel’skiı̆, M. A. (1955). Two comments on the method of successive
where xk = col(x1,k , . . . , xN ,k ) and Tk is defined as Tk : x 7 ! approximations. Uspekhi Matematicheskikh Nauk, 10, 123–127.
⌦k (Ak ⌦ In )x + ↵k ✓ r̃, with ⌦k := diag {I ↵k ✓ R1 , . . . , I ↵k ✓ RN } Kruger, A. Y., Luke, D. R., & Thao, N. H. (2018). Set regularities and feasibility
and r̃ := col(r1 , . . . , rN ). problems. Mathematical Programming, 168(1–2), 279–311.
Li, X., Chen, M. Z. Q., Su, H., & Li, C. (2016). Consensus networks with switching
It is easy to verify that for any x, y 2 RnN
topology and time-delays over finite fields. Automatica, 68, 39–43.
kTk x Tk yk = k⌦k (Ak ⌦ In )x ⌦k (Ak ⌦ In )yk Li, X., & Feng, G. (2020). Distributed algorithms for computing a common fixed
point of a group of nonexpansive operators. IEEE Transactions on Automatic
 k⌦k kk(Ak ⌦ In )x (Ak ⌦ In )yk Control, http://dx.doi.org/10.1109/TAC.2020.3004773, in press.
Li, X., Feng, G., & Xie, L. (2020). Distributed proximal algorithms for multi-
 k(Ak ⌦ In )x (Ak ⌦ In )yk
agent optimization with coupled inequality constraints. IEEE Transactions on
 kAk ⌦ In kkx yk Automatic Control, http://dx.doi.org/10.1109/TAC.2020.2989282, in process.
Li, X., Xie, L., & Hong, Y. (2020). Distributed continuous-time nonsmooth convex
= kx yk, (56) optimization with coupled inequality constraints. IEEE Transactions on Control
of Network Systems, 7(1), 74–84.
where k⌦k k  1 and kAk ⌦ In k = 1 have been employed. Liang, J., Fadili, J., & Peyré, G. (2016). Convergence rates with inexact
Therefore, Tk is nonexpansive. non-expansive operators. Mathematical Programming, 159(1–2), 403–434.
Now, for any x⇤k 2 Fix(Tk ), invoking (55) yields that Liang, S., Wang, L., & Yin, G. (2019). Distributed quasi-monotone subgradi-
ent algorithm for nonsmooth convex optimization over directed graphs.
kxk+1 x⇤k k = kTk xk Tk x⇤k k  kxk x⇤k k, (57) Automatica, 101, 175–181.
Lin, P., Ren, W., Wang, H., & Al-Saggaf, U. M. (2019). Multi-agent rendezvous with
implying that xk and thus xi,k ’s are bounded. Consequently, As- shortest distance to convex regions with empty intersection: algorithms and
sumption 1 holds. This ends the proof. ⌅ experiments. IEEE Transactions on Cybernetics, 49(3), 1026–1034.
Liu, J., Fullmer, D., Nedi¢, A., Ba≥ar, T., & Morse, A. S. (2017). A distributed
algorithm for computing a common fixed point of a family of strongly
References
quasi-nonexpansive maps. In Proceedings of American control conference (pp.
686–690). Seattle, USA.
Alaviani, S. S., & Elia, N. (2018). A distributed algorithm for solving linear
Liu, S., Qiu, Z., & Xie, L. (2017). Convergence rate analysis of distributed
algebraic equations over random networks. In Proceedings of 57th conference
optimization with projected subgradient algorithm. Automatica, 83, 162–169.
on decision and control (pp. 83–88). Miami Beach, FL, USA.
Lou, Y., Hong, Y., & Wang, S. (2016). Distributed continuous-time approximate
Alaviani, S. S., & Elia, N. (2020). Distributed multi-agent convex optimization over
projection protocols for shortest distance optimization problems. Automatica,
random digraphs. IEEE Transactions on Automatic Control, 65(3), 986–998.
69, 289–297.
Alexander, R., Cesar, U., Alexander, G., Nikolai, M., & Angelia, N. (2020). Op-
Mann, W. R. (1953). Mean value methods in iteration. Proceedings of the Americal
timal distributed convex optimization on slowly time-varying graphs. IEEE
Mathematical Society, 4(3), 506–510.
Transactions on Control of Network Systems, 7(2), 829–841.
Mansoori, F., & Wei, E. (2020). A fast distributed asynchronous Newton-
Ba≥ary, T., Etesami, S. R., & Olshevsky, A. (2014). Fast convergence of quantized
based optimization algorithm. IEEE Transactions on Automatic Control, 65(7),
consensus using Metropolis chains. In Proceedings of 53rd IEEE conference on
2769–2784.
decision and control (pp. 1330–1334). Los Angeles, USA.
Mateos-Núnez, D., & Cortés, J. (2017). Distributed saddle-point subgradient
Bauschke, H. H., & Combettes, P. L. (2017). Convex analysis and monotone operator
algorithms with Laplacian averaging. IEEE Transactions on Automatic Control,
theory in Hilbert spaces (2nd ed.). New York: Springer.
Borwein, J. M., Li, G., & Tam, M. K. (2017). Convergence rate analysis for averaged 62(6), 2720–2735.
fixed point iterations in common fixed point problems. SIAM Journal on Matsushita, S. (2017). On the convergence rate of the Krasnosel’skiı̆-Mann
Optimization, 27(1), 1–33. iteration. Bulletin of Australian Mathematical Society, 96(1), 162–170.
Bravo, M., Cominetti, R., & Pavez-Signé, M. (2019). Rates of convergence Meng, M., Liu, L., & Feng, G. (2017). Adaptive output regulation of heterogeneous
for inexact Krasnosel’skiı̆-Mann iterations in Banach spaces. Mathematical multi-agent systems under Markovian switching topologies. IEEE Transactions
Programming, 175(1–2), 241–262. on Cybernetics, 48(10), 2962–2971.
Cegielski, A. (2012). Iterative methods for fixed point problems in Hilbert spaces, Mou, S., Liu, J., & Morse, A. S. (2015). A distributed algorithm for solving a
Vol. 2057. Heidelberg: Springer. linear algebraic equation. IEEE Transactions on Automatic Control, 60(11),
Cegielski, A. (2015). Application of quasi-nonexpansive operators to an itera- 2863–2878.
tive method for variational inequality. SIAM Journal on Optimization, 25(4), Necoara, I., Richtárik, P., & Patrascu, A. (2019). Randomized projection methods
2165–2181. for convex feasibility problems: conditioning and convergence rates. SIAM
Cominetti, R., Soto, J. A., & Vaisman, J. (2014). On the rate of convergence of Journal on Optimization, 29(4), 2814–2852.
Krasnosel’skiı̆-Mann iterations and their connection with sums of Bernoullis. Nedi¢, A., & Ozdaglar, A. (2009). Distributed subgradient methods for multi-agent
Israel Journal of Mathematics, 199(2), 757–772. optimization. IEEE Transactions on Automatic Control, 54(1), 48–61.
Dall’Anese, E., Simonetto, A., & Bernstein, A. (2019). On the convergence of the Nedi¢, A., Pang, J., Scutari, G., & Sun, Y. (2018). Multi-agent optimization: Cetraro,
inexact running Krasnosel’skiı̆-Mann method. IEEE Control Systems Letters, Italy 2014, Vol. 2224. Springer.
3(3), 613–618. Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007). Consensus and cooperation in
Debnath, L., & Mikusinski, P. (2005). Introduction to Hilbert spaces with networked multi-agent systems. Proceedings of the IEEE, 95(1), 215–233.
applications. Academic Press. Reich, S. (1979). Weak convergence theorems for nonexpansive mappings in
Fullmer, D., Liu, J., & Morse, A. S. (2016). An asynchronous distributed algorithm Banach spaces. Journal of Mathematical Analysis and Applications, 67(2),
for computing a common fixed point of a family of paracontractions. In 274–276.
Proceedings of 55th conference on decision and control (pp. 2620–2625). Las Ren, W., & Cao, Y. (2010). Distributed coordination of multi-agent networks:
Vegas, USA. Emergent problems, models, and issues. London, U.K.: Springer-Verlag.
Fullmer, D., & Morse, A. S. (2018). A distributed algorithm for computing a Robbins, H., & Siegmund, D. (1971). A convergence theorem for nonnegative
common fixed point of a finite family of paracontractions. IEEE Transactions almost supermartingales and some applications. In Proceedings of optimizing
on Automatic Control, 63(9), 2833–2843. methods in statistics (pp. 233–257). Ohio, USA.

11
X. Li and L. Xie Automatica 122 (2020) 109286

Shehu, Y. (2018). Convergence rate analysis of inertial Krasnosel’skiı̆-Mann type Xiuxian Li received the B.S. degree in mathematics and
iteration with applications. Numerical Functional Analysis and Optimization, applied mathematics and the M.S. degree in pure math-
39(10), 1077–1091. ematics from Shandong University, Jinan, Shandong,
Simonetto, A. (2017). Time-varying convex optimization via time-varying China, in 2009 and 2012, respectively, and the Ph.D.
averaged operators. arXiv preprint arXiv:1704.07338. degree in mechanical engineering from the University
Themelis, A., & Patrinos, P. (2019). SuperMann: a superlinearly convergent algo- of Hong Kong, Hong Kong, in 2016. Since 2016, he
rithm for finding fixed points of nonexpansive operators. IEEE Transactions has been a research fellow with the School of Electri-
on Automatic Control, 64(12), 4875–4890. cal and Electronic Engineering, Nanyang Technological
Wang, X., Mou, S., & Anderson, B. D. O. (2020). Scalable, distributed algorithms University, Singapore, and a senior research associate
for solving linear equations via double-layered networks. IEEE Transactions with the Department of Biomedical Engineering, City
on Automatic Control, 65(3), 1132–1143. University of Hong Kong, Kowloon, Hong Kong (August
Wang, X., Mou, S., & Sun, D. (2017). Further discussions on a distributed 2018–January 2019). He held a visiting position at King Abdullah University of
algorithm for solving linear algebra equations. In Proceedings of American Science and Technology, Saudi Arabia, in September 2019.
control conference (pp. 4274–4278). Seattle, USA. His research interests include optimization, algorithms, machine learning,
Wang, X., Mou, S., & Sundaram, S. (2019). A resilient convex combination game, distributed control, and multi-agent networks.
for consensus-based distributed algorithms. Numerical Algebra, Control &
Optimization, 9(3), 269–281.
Wang, P., Ren, W., & Duan, Z. (2019). Distributed algorithm to solve a sys- Lihua Xie received the B.E. and M.E. degrees in elec-
tem of linear equations with unique or multiple solutions from arbitrary trical engineering from Nanjing University of Science
initializations. IEEE Transactions on Control of Network Systems, 6(1), 82–93. and Technology in 1983 and 1986, respectively, and
Wang, X., Zhou, J., Mou, S., & Corless, M. J. (2019). A distributed algorithm the Ph.D. degree in electrical engineering from the
for least squares solutions. IEEE Transactions on Automatic Control, 64(10), University of Newcastle, Australia, in 1992. Since 1992,
4217–4222. he has been with the School of Electrical and Elec-
Xie, P., You, K., Tempo, R., Song, S., & Wu, C. (2018). Distributed convex opti- tronic Engineering, Nanyang Technological University,
mization with inequality constraints over time-varying unbalanced digraphs. Singapore, where he is currently a professor and Direc-
IEEE Transactions on Automatic Control, 63(12), 4331–4337. tor, Delta-NTU Corporate Laboratory for Cyber–Physical
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018). Convergence of asynchronous Systems. He served as the Head of Division of Control
distributed gradient methods over stochastic networks. IEEE Transactions on and Instrumentation from July 2011 to June 2014. He
Automatic Control, 63(2), 434–448. held teaching appointments in the Department of Automatic Control, Nanjing
Yuan, K., Ling, Q., & Yin, W. (2016). On the convergence of decentralized gradient University of Science and Technology from 1986 to 1989.
descent. SIAM Journal on Optimization, 26(3), 1835–1854. Dr. Xie’s research interests include robust control and estimation, networked
Zeng, X., Chen, J., Liang, S., & Hong, Y. (2019). Generalized Nash equilibrium control systems, multi-agent networks, localization and unmanned systems. He
seeking strategy for distributed nonsmooth multi-cluster game. Automatica, is an Editor-in-Chief for Unmanned Systems and an Associate Editor for IEEE
103, 20–26. Transactions on Control of Network Systems. He has served as an editor of
Zhang, Y., Lou, Y., Hong, Y., & Xie, L. (2015). Distributed projection-based algo- IET Book Series in Control and an Associate Editor of a number of journals
rithms for source localization in wireless sensor networks. IEEE Transactions including IEEE Transactions on Automatic Control, Automatica, IEEE Transactions
on Wireless Communication, 14(6), 3131–3142. on Control Systems Technology, and IEEE Transactions on Circuits and Systems-
Zhang, Y., Ravier, R. J., Tarokh, V., & Zavlanos, M. M. (2019). Distributed online II. He is an elected member of Board of Governors, IEEE Control System Society
convex optimization with improved dynamic regret. arXiv preprint arXiv: (Jan 2016–Dec 2018). Dr. Xie is Fellow of Academy of Engineering Singapore,
1911.05127. Fellow of IEEE and Fellow of IFAC.

12