# Event-Triggered Discrete-Time Distributed Consensus Optimization over Time-Varying Graphs

Authors: Qingguo Lü; Huaqing Li
Journal: Complexity
 (2017)

---

## Abstract

This paper focuses on a class of event-triggered discrete-time distributed consensus optimization algorithms, with a set of agents whose communication topology is depicted by a sequence of time-varying networks. The communication process is steered by independent trigger conditions observed by agents and is decentralized and just rests with each agent’s own state. At each time, each agent only has access to its privately local Lipschitz convex objective function. At the next time step, every agent updates its state by applying its own objective function and the information sent from its neighboring agents. Under the assumption that the network topology is uniformly strongly connected and weight-balanced, the novel event-triggered distributed subgradient algorithm is capable of steering the whole network of agents asymptotically converging to an optimal solution of the convex optimization problem. Finally, a simulation example is given to validate effectiveness of the introduced algorithm and demonstrate feasibility of the theoretical analysis.


---

## Body

## 1. Introduction

In the last decade, multiagent systems have obtained some achievements in theory and application, like consensus problem [1–7], flocking problem [8–10], resource allocation control [11–13], and so on [14–17]. Multiagent systems not only have the characteristics of resource sharing, good coordination, high distribution, and strong autonomy, but also can cooperatively solve large-scale complex tasks [18–23]. However, as an emerging issue, the coordination control of multiagent systems still faces many problems in theoretical researches and practical applications. As one of the most important research subjects in the field of coordination control of multiagent systems, the consensus problem has achieved considerable attention over the past few years due to its expanding applications in cooperative control of highway system, mobile multirobot system, design of distributed sensor networks, and other areas [24–31]. Generally speaking, consensus means that the states of all agents asymptotically or even exponentially reach an agreement on a unique value by effectively applying local information of each agent. Naturally, in order to guide the actual application and achieve greater value, we still need further study.Among the existing papers, the consensus-based subgradient methods for solving the distributed convex optimization problem have drawn a surge of attentions since Nedic and Ozdaglar presented a systematic analysis of it in [32]. To date, many valuable consensus-based subgradient algorithms have been addressed. Projection-based distributed subgradient algorithm for distributed optimization was put forward in Nedic et al. [33], where each agent was constrained to an individual closed convex set. Convergence to the same optimal solution is proved for the cases when the weights were constant and equal and when the weights were uniform but all agents had the same constraint set. Further distributed algorithm for set constrained optimization was investigated in Bianchi and Jakubowicz [34] and Lou et al. [35]. To work out the distributed optimization problems with asynchronous step-sizes or inequality-equality constraints, distributed Lagrangian and penalty primal-dual subgradient algorithms were developed in Zhu and Martinez [36] and Towfic and Sayed [37]. Both of them were designed for function constrained problems. Meanwhile, the distributed convex optimization problems over general networks were settled in Lobel et al. [38] and Matei and Baras [39]. Recent works [40–45] have coordinately put their efforts on the consensus of multiagent systems by designing the control protocols based on event-triggered sampling schemes. Lu and Tang [41] proposed a continuous-time consensus-based zero-gradient-sum (ZGS) algorithm which is built on the condition of the gradient sum being zero. Seyboth et al. [42] studied a variant of the event-trigger average consensus problem for single-integrators and double-integrators, where a novel control strategy for multiagent coordination was employed to simplify the performance and convergence analysis of the method. To solve the optimization problem with more general case that the mean square consensus for multiple agents is affected by noises over directed networks, Hu et al. [44] proposed a novel centralized and decentralized event-triggered protocols and built its convergence. In more recent literature, Li et al. [45] investigated event-triggered nonlinear consensus in directed multiagent systems with combinational state measurements. In general, event-triggered sampling schemes were introduced into the implementation of the aforementioned methods, respectively.Our method builds on the pioneering work of [33, 46, 47]. Nedic et al. [33] assumed that each agent was constrained to remain in a closed convex set. Convergence to the same optimal solution was proved for the cases when the weights were constant and equal and when the weights were time-varying but all agents had the same constraint set. Furthermore, paper [46] developed a broadcast-based algorithm, called the subgradient-push, which guides each agent to reach an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires neither the knowledge of the number of agents nor the graph sequence to implement. In order to avoid unnecessary communication and ensure fast and exact convergence, Chen and Ren [47] presented an event-triggered zero-gradient-sum distributed consensus optimization over directed networks with a general assumption that the objective function is twice continuously differentiable.Contributions. Inspired by the previous works, this paper proposes a novel distributed subgradient algorithm for multiagent convex optimization with event-triggered sampling scheme. Previous works did not perform well on the applications of the distributed algorithms in multiagent network; for example, they may just study discrete-time distributed consensus optimization over time-varying graphs without trigger condition or they only consider event-based distributed consensus of multiagent systems with general networks. However, our methods perfectly integrate the event-triggered scheme with discrete-time distributed consensus optimization over time-varying graphs. Also, we only require that the network topology is uniformly strongly connected and weight-balanced, which makes our algorithm more effective. More precisely, the contribution of this paper is mainly in three aspects. Firstly, we study the convex optimization problem of discrete-time multiagent systems by a distributed event-triggered sampling control scheme, where the event-triggered control strategy in this paper can eliminate unnecessary communications among neighboring agents, leading to the reduction of computation costs and energy consumption in practice. Secondly, based on the assumption that the digraph is weight-balanced and uniformly strongly connected, we introduce a novel distributed subgradient algorithm by a distributed event-triggered sampling control scheme. Thirdly, we also show the convergence of the algorithm and prove that it can achieve the optimal point of the sum of agents’ local objective functions while satisfying the trigger condition.The remainder of this paper is organized as follows. Some essential concepts and knowledge with regard to graph theory are given, and problems are formulated in Section2. Then, in Section 3, the main results are presented. Furthermore, the effectiveness of the algorithm is testified by using a numerical example in Section 4. Finally, the conclusion is drawn in Section 5.


## 2. Preliminaries and Concepts

In this section, we present some important mathematical preliminaries including algebraic graph theory, notations, and problem formulation (referring to [48, 49]).


### 2.1. Algebraic Graph Theory

We always employ a graph to describe the information exchange between the nodes. The information exchange betweenN nodes in an information interaction topology can be modeled as a weighted directed graph G={V,E,W}, where V={1,2,…,N} is the set of vertices with i representing ith vertex and E⊆V×V is the set of edges. The graph is assumed to be simple when there are no repeated edges or self-loops. The weighted adjacency matrix of G is denoted by W=[wij]∈RN×N with nonnegative adjacency elements wij and zero diagonal elements. Note that the diagonal elements wii=0 and W is generally an asymmetric matrix. A directed edge denoted by a pair (j,i) implies that node j can arrive at node i or node i can receive information from node j. If an edge (j,i)∈E, then node j is called a neighbor of node i and wij>0. The neighbor index node set of node i is denoted by Ni, while we show Ni, the number of neighbors of node i. The Laplacian matrix L=(lij)N×N of digraph G associated with the adjacency matrix W is defined by lij=-wij, i≠j; lii=∑j=1,j≠iNwij, which ensures that ∑j=1Nlij=0. The in-degree and out-degree of node i can be defined by the Laplacian matrix as din(i)=-∑j=1,j≠iNlij=lii and dout(i)=-∑j=1,j≠iNlji, respectively. A directed path from node j to node i is a sequence of edges (j,i1),(i1,i2),…,(im,i) in the directed graph G with different nodes ik, k=1,2,…,m. A directed graph is strongly connected if and only if, for any two distinct nodes j and i in the set V, there exists a directed path from node j to node i. A graph is called an out-degrees (or in-degrees) balanced graph if the out-degrees (or in-degrees) of all nodes in the directed graph are equivalent. A directed graph with N nodes is called a directed tree if it includes N-1 edges and there exists a root node to every other node with directed paths. For a directed graph, a directed tree can be regarded as a directed spanning tree if it contains all network nodes.


### 2.2. Notations

Some mathematically standard notations throughout this paper are listed in the following.R,Rn, and Rn×n refer to the set of real numbers, the set of n×1 real vectors, and the set of n×n real matrices, respectively. In and 0n×n denote the identity matrix and the n×n zero matrix, respectively. Let 1n∈Rn and 0n∈Rn refer to the vector with all entries being one and zero, respectively. We let xT or WT denote the transpose of a vector x or a matrix W. For a vector x∈Rn, we denote x=(x1,…,xn-)T, while x is the standard Euclidean norm in the Euclidean space. ∇f:Rn→Rn denote the gradient of f. For a matrix W, we write Wij or [W]ij to denote its i,j’th entry.


### 2.3. Distributed Optimization Problem

In this subsection, we consider a network ofn nodes whose object is to solve the following distributed minimization problem:(1)minimizefx=∑i=1Nfixoverx∈Rn,where fi:Rn→R is the convex objective function of agent i and x is a global decision vector. Assume that fi is only known by agent i and probably different. Under the condition that the set of optimal solutions X∗=arg⁡minx∈Rn⁡f(x) is nonempty, we would like to denote f∗ the optimal value of and x∗ an optimizer of (1).In this paper, we do not assume the differentiability of the local objective functionfi. At the points where the function is not differentiable, the subgradient plays the role of gradient. For a given convex function f:Rn→R and a point x~∈Rn, a subgradient of the function f at x~ is a vector ∇f(x~)∈Rn such that the following subgradient inequality holds for any x∈Rn:(2)∇fx~Tx-x~≤fx-fx~.The following assumptions are necessary in the analysis of distributed optimization algorithm throughout this paper.Assumption 1 (weight-balanced).
G
(
t
) is weight-balanced if dout(i)=din(i) for all i∈V.Assumption 2 (uniformly strongly connected).
LetG={V,E∞}=⋃t=0∞G(t). There exists an integer B≥1 such that, for every (j,i)∈E∞, agent j sends its information to a neighboring agent i at least once every B consecutive time slots, that is, at time tk or at time tk+1 and so on until (at last) at time tk+B-1 for any k≥0. In other words, the graph sequence {G(t)} is uniformly strongly connected.Assumption 3 (subgradient boundedness).
The subgradients∇fi(x) of each fi(x) are uniformly bounded; that is, there exists 0<Li<∞ for all i=1,…,N such that ∇fi(x)≤Li for all subgradients ∇fi(x) of fi(x).


## 2.1. Algebraic Graph Theory

We always employ a graph to describe the information exchange between the nodes. The information exchange betweenN nodes in an information interaction topology can be modeled as a weighted directed graph G={V,E,W}, where V={1,2,…,N} is the set of vertices with i representing ith vertex and E⊆V×V is the set of edges. The graph is assumed to be simple when there are no repeated edges or self-loops. The weighted adjacency matrix of G is denoted by W=[wij]∈RN×N with nonnegative adjacency elements wij and zero diagonal elements. Note that the diagonal elements wii=0 and W is generally an asymmetric matrix. A directed edge denoted by a pair (j,i) implies that node j can arrive at node i or node i can receive information from node j. If an edge (j,i)∈E, then node j is called a neighbor of node i and wij>0. The neighbor index node set of node i is denoted by Ni, while we show Ni, the number of neighbors of node i. The Laplacian matrix L=(lij)N×N of digraph G associated with the adjacency matrix W is defined by lij=-wij, i≠j; lii=∑j=1,j≠iNwij, which ensures that ∑j=1Nlij=0. The in-degree and out-degree of node i can be defined by the Laplacian matrix as din(i)=-∑j=1,j≠iNlij=lii and dout(i)=-∑j=1,j≠iNlji, respectively. A directed path from node j to node i is a sequence of edges (j,i1),(i1,i2),…,(im,i) in the directed graph G with different nodes ik, k=1,2,…,m. A directed graph is strongly connected if and only if, for any two distinct nodes j and i in the set V, there exists a directed path from node j to node i. A graph is called an out-degrees (or in-degrees) balanced graph if the out-degrees (or in-degrees) of all nodes in the directed graph are equivalent. A directed graph with N nodes is called a directed tree if it includes N-1 edges and there exists a root node to every other node with directed paths. For a directed graph, a directed tree can be regarded as a directed spanning tree if it contains all network nodes.


## 2.2. Notations

Some mathematically standard notations throughout this paper are listed in the following.R,Rn, and Rn×n refer to the set of real numbers, the set of n×1 real vectors, and the set of n×n real matrices, respectively. In and 0n×n denote the identity matrix and the n×n zero matrix, respectively. Let 1n∈Rn and 0n∈Rn refer to the vector with all entries being one and zero, respectively. We let xT or WT denote the transpose of a vector x or a matrix W. For a vector x∈Rn, we denote x=(x1,…,xn-)T, while x is the standard Euclidean norm in the Euclidean space. ∇f:Rn→Rn denote the gradient of f. For a matrix W, we write Wij or [W]ij to denote its i,j’th entry.


## 2.3. Distributed Optimization Problem

In this subsection, we consider a network ofn nodes whose object is to solve the following distributed minimization problem:(1)minimizefx=∑i=1Nfixoverx∈Rn,where fi:Rn→R is the convex objective function of agent i and x is a global decision vector. Assume that fi is only known by agent i and probably different. Under the condition that the set of optimal solutions X∗=arg⁡minx∈Rn⁡f(x) is nonempty, we would like to denote f∗ the optimal value of and x∗ an optimizer of (1).In this paper, we do not assume the differentiability of the local objective functionfi. At the points where the function is not differentiable, the subgradient plays the role of gradient. For a given convex function f:Rn→R and a point x~∈Rn, a subgradient of the function f at x~ is a vector ∇f(x~)∈Rn such that the following subgradient inequality holds for any x∈Rn:(2)∇fx~Tx-x~≤fx-fx~.The following assumptions are necessary in the analysis of distributed optimization algorithm throughout this paper.Assumption 1 (weight-balanced).
G
(
t
) is weight-balanced if dout(i)=din(i) for all i∈V.Assumption 2 (uniformly strongly connected).
LetG={V,E∞}=⋃t=0∞G(t). There exists an integer B≥1 such that, for every (j,i)∈E∞, agent j sends its information to a neighboring agent i at least once every B consecutive time slots, that is, at time tk or at time tk+1 and so on until (at last) at time tk+B-1 for any k≥0. In other words, the graph sequence {G(t)} is uniformly strongly connected.Assumption 3 (subgradient boundedness).
The subgradients∇fi(x) of each fi(x) are uniformly bounded; that is, there exists 0<Li<∞ for all i=1,…,N such that ∇fi(x)≤Li for all subgradients ∇fi(x) of fi(x).


## 3. Main Results

In this section, motivated by [35, 36], we provide a novel distributed subgradient algorithm to solve the optimization problem (1), followed by its convergence properties. To this end, we consider a group of agents V={1,…,N} with the communication topology described by a sequence of uniformly strongly connected time-varying digraph G(t)={V,E(t),W(t)} as before. The distributed subgradient algorithm is a discrete-time dynamical system, which is depicted as follows.


### 3.1. Distributed Subgradient Algorithm

Consider a setV={1,…,N} of agents. Formally, at each iteration t={1,…,T}, the agent i updates its next time state according to the following laws:(3)xit+1=xit+h∑j∈Niwijtx^jt-x^it-hgt∇fixit,where t∈⋂i∈V[tkii,tki+1i) is the iteration number, h is the control gain, tkii denotes the instant when the kith event happens for the agent i, x^i(t)=xi(tkii) for tkii≤t<tki+1i, the positive scalars g(t)>0 are step-sizes, the scalars wij(t) are nonnegative weights and have an upper bound M, and the vector ∇fi(xi(t)) is a subgradient of the agent i objective function fi(x) at x=xi(t).Remark 4.
Denote the measurement error as(4)eit=x^it-xit,ejt=x^jt-xjt.Then, we can rewrite algorithm (3) into the following form:(5)xit+1=xit+h∑j∈Niwijtxjt-xit+Eit,where Ei(t)=h∑j∈Niwij(t)(ej(t)-ei(t))-hg(t)∇fi(xi(t)) is an error term. Due to (5), it follows that (6)xit+1=xit-h∑j∈Nilijtxjt+Eit.Modifying the second term on the right-hand side in the above formula, we then have(7)xit+1=xit-hliitxit-h∑j=1,j≠iNlijtxjt+Eit=1-hliitxit-h∑j=1,j≠iNlijtxjt+Eit.Letting aii(t)=(1-hlii(t)),aij(t)=-hlij(t), one has(8)xit+1=∑j=1Naijtxjt+Eit.Since graph G(t) is balanced, we then have ∑j=1Naij(t)=1 and ∑i=1Naij(t)=1 hold if h satisfies 1-hlii(t)>0.Before giving some supporting lemmas, we need the following assumption on the sequences of step-sizes and{A(t)}.Assumption 5 (step-size assumption).
The step-sizes{g(t)} are positive sequence, which satisfies the following: (9)∑t=0+∞gt=+∞,∑t=0+∞g2t<+∞,gt≤gs∀t>s≥1.Assumption 6 (nondegeneracy).
There exists a constantη with 0<η<1 such that, for all i,j∈{1,…,n}, (a) aii(t)≥η for all t≥0 and (b) if aij(t)≥0, then aij(t)≥η.
Next, the transition matrices are introduced as follows:(10)Φt,s=AsAs+1⋯At-1At∀s,twitht≥s,where Φ(t,t)=A(t) for all t. And the ith column of Φ(t,s) is defined as [Φ(t,s)]i=AsAs+1⋯A(t-1)ai(t). Meanwhile, the entry in ith column and jth row of Φ(t,s) is described as [Φ(t,s)]ij=[A(s)A(s+1)⋯A(t-1)ai(t)]j. A crucial property of the transition matrices is given in the following, which plays a key role in our analysis of the algorithms.Lemma 7 (see [35]).
Let the weight-balanced Assumption1, the uniformly strongly connected Assumption 2, and the nondegeneracy Assumption 6 hold. Then the entries [Φ(t,s)]ij of the transition matrices converge as t→∞ to a uniform geometric rate 1/N with respect to i and j, that is, for all i,j∈{1,…,N},(11)Φt,sij-1N≤21+η-B01-ηB01-ηB0t-s/B0∀s,twitht≥s,where η is the lower bound of the nondegeneracy Assumption 6, N is the number of agents, B0=(N-1)B, and B is given in the uniformly strongly connected Assumption 2.Proof.
We refer the reader to the papers [35, 37] for proofs of this and similar assertions.Before moving on, it is important to introduce the following lemma and the proof of the lemma.Lemma 8 (see [33]).
Let0<λ<1 and let {ψt} be a positive scalar sequence. Suppose limt→∞⁡ψt=0. Then(12)limt→∞∑l=0tλt-lψl=0.Furthermore, if ∑t=0∞ψt<∞, then(13)∑t=0∞∑l=0tλt-lψl<∞.Proof.
We do not give the proof of Lemma8 since it is almost identical to that of Lemma  7 in [33].Chen and Ren [47] provided an event-triggered consensus algorithm of multiagent system. Inspired by this work, we design a new event-triggered scheme applied as follows.We now define the triggering time sequence{tki} for agent i by (14)tk+1i=inf⁡t:t>tki,yit>0,where(15)yit=eit-c1-ββtis referred to as the trigger function for all 0<β<1, c>0, and ei(t)=x^i(t)-xi(t). Therefore, we can conclude that ei(t)=0 at t=tki.Lemma 9.
(16)
l
i
m
t
→
∞
E
i
t
=
0
.Proof.
SinceEi(t)=h∑j∈Niwij(t)(ej(t)-ei(t))-hg(t)∇fi(xi(t)), then we have for all t>0(17)Eit=h∑j∈Niwijtejt-eit-hgt∇fixit≤h∑j∈Niwijtejt-eit+hgt∇fixit.By the weight-balanced Assumption 1 and the subgradient boundedness Assumption 3, we therefore have(18)Eit≤2Mheit+hLgt,where L=maxi∈VLi. Substituting (15) into (18) yields (19)Eit≤2Mhc1-ββt+hLgt.Taking the limits of both sides of (19) as t→∞, one can see that limt→∞⁡Ei(t)=0. Thus, the proof is completed.Remark 10.
Lemma9 shows that if the error term in system (8) decays, the differences between the states of all the agents will vanish asymptotically.


### 3.2. Convergence Analysis

We next introduce the characteristic that the agents reach a consensus asymptotically, which means the agent estimatesxi(t) converge to the same point when t goes to infinity.Theorem 11 (consensus).
Let the weight-balanced Assumption1, the uniformly strongly connected Assumption 2, the subgradient boundedness Assumption 3, the step-size Assumption 5, and the nondegeneracy Assumption 6 hold. Consider the sequence {xi(t)} being produced by the distributed subgradient algorithm (3). We then have for x-(t)=(1/N)∑i=1Nxi(t) and all i(20)limt→∞xit-x-t=0.Proof.
It is obtained from (8) that(21)xt+1=Atxt+Et=AtAt-1xt-1+Et-1+Et=AtAt-1At-2xt-2+Et-2+AtEt-1+Et⋮=AtAt-1At-2⋯A0x0+AtAt-1⋯A1E0+⋯+AtAt-1Et-2+AtEt-1+Et.Using the transition matrices Φ(t,s), we can write for all t and s with t>s(22)xt+1=Φt:0x0+∑s=1tΦt:sEs-1+Et.Therefore, we have the following:(23)xit=∑j=1NΦt-1,0ijxj0+∑s=1t-1∑j=1NΦt-1,sijEjs-1+Eit-1.Then, using (8) and x-(t)=(1/N)∑i=1Nxi(t), we can achieve that(24)x-t=x-t-1+1N∑i=1NEit-1=x-t-2+1N∑i=1NEit-2+1N∑i=1NEit-1⋮=x-0+1N∑i=1NEi0+⋯+1N∑i=1NEit-2+1N∑i=1NEit-1=x-0+1N∑s=0t-1∑i=1NEis.Together with (23), it yields that(25)xit-x-t=∑j=1NΦt-1,0ijxj0+∑s=1t-1∑j=1NΦt-1,sijEjs-1+Eit-1-∑j=1N1Nxj0-∑s=1t-1∑j=1N1NEjs-1-1N∑j=1NEjt-1=∑j=1NΦt-1,0ij-1Nxj0+∑s=1t-1∑j=1NΦt-1,sij-1NEjs-1+Eit-1-1N∑j=1NEjt-1.According to the property of standard Euclidean norm, we then have(26)xit-x-t≤max1≤k≤N⁡xk0·∑j=1NΦt-1,0ij-1N+∑s=1t-1∑j=1NΦt-1,sij-1NEjs-1+1N∑j=1NEjt-1-Eit-1≤max1≤k≤N⁡xk0·N·maxi,j∈1,2,…,N⁡Φt-1,0ij-1N+∑s=1t-1N·maxi,j∈1,2,…,N⁡Φt-1,0ij-1N·max1≤k≤N⁡Eks-1+1N∑j=1NEjt-1-Eit-1.Letting b(t,s)=maxi,j∈{1,2,…,N}[Φ(t,s)]ij-(1/N) and D=max1≤k≤Nxk(0), the following inequality can be built: that is,(27)xit-x-t≤N∑s=1t-1bt-1,smax1≤k≤N⁡Eks-1+2max1≤k≤N⁡Ekt-1+NDbt-1,0.Using the upper bound estimate for [Φ(t,s)]ij-(1/N) of Lemma 7, we get for all t≥s(28)Φt,sij-1N≤Cχt-s∀i,j,with C=2(1+η-B0/1-ηB0) and χ=(1-ηB0)1/B0. Therefore, this together with (27) results in(29)xit-x-t≤NC∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2max1≤k≤N⁡Ekt-1+NDCχt-1.By Lemmas 8 and 9 and taking limits on both sides of (29), one can finally have limt→∞⁡xi(t)-x-(t)=0 for all i∈{1,…,N}.We now begin to introduce a well-known convergence result which is shown in the following lemma.Lemma 12 (see [38]).
Letvt be a nonnegative scalar sequence such that(30)vt+1≤1+btvt-ut+ct∀t≥0,where b(t)≥0,u(t)≥0, and c(t)≥0 for all t≥0 with ∑t=0∞b(t)<∞ and ∑t=0∞c(t)<∞. Then, the sequence {v(t)} converges to some v≥0 and ∑t=0∞u(t)<∞.Proof.
The proof process can imitate that of [38], and thus it is omitted.In what follows, we present a key lemma, which is important in the analysis of the distributed optimization algorithm. Thereafter, we study the convergence behavior of the subgradient algorithm, where the optimal solution can be asymptotically reached.Lemma 13 (see [46]).
Consider an optimization problemminx∈Rn⁡f(x), where f:Rn→R is a continuous objective function. Assume that the optimal solution set X∗ of the optimization problem is nonempty. Let {x(t)} be a sequence with all x∈X∗ and all t≥0 such that(31)xt+1-x2≤1+btxt-x2-αtfxt-fx+ct,where b(t)≥0, α(t)≥0, and c(t)≥0 for all t≥0 with ∑t=0∞b(t)<∞, ∑t=0∞α(t)=∞, and ∑t=0∞c(t)<∞. Then the sequence {x(t)} converges to some optimal solution x∗∈X∗.Proof.
The proof procedure can imitate that of Lemma  7 in [46], and thus it is omitted.Theorem 14 (optimization).
Let the weight-balanced Assumption1, the uniformly strongly connected Assumption 2, the subgradient boundedness Assumption 3, the step-size Assumption 5, and the nondegeneracy Assumption 6 hold. For problem (1), consider the sequence {xi(t)} being updated by the distributed subgradient algorithm (3). Then there exists an optimal solution x∗∈X∗ such that (32)limt→∞⁡xit-x∗=0∀i∈1,…,N.Proof.
Applying (3) to the average process, it is obtained that(33)1N∑i=1Nxit+1=1N∑i=1Nxit+hN∑i=1N∑j∈Niwijtx^jt-x^it-hNgt∑i=1N∇fixit.Using x-=(1/N)∑i=1Nxi(t), the control law (33) can be rewritten as(34)x-t+1=x-t-hNgt∑i=1N∇fixit.Now, let x∈Rn be arbitrary vector; we have for all t≥0 that(35)x-t+1-x2=x-t-hNgt∑i=1N∇fixit-x2=x-t-x2-2hNgt∑i=1N∇fixitTx-t-x+h2N2g2t∑i=1N∇fixit2.Since the subgradient of each fi(x) is uniformly bounded by Li and L=maxi∈V⁡Li, then it follows that for all t≥0(36)x-t+1-x2≤x-t-x2-2hNgt∑i=1N∇fixitTx-t-x+h2L2g2t.We next study the cross-term ∇fi(xi(t))T(x-(t)-x) in (36). For this term, we write(37)∇fixitTx-t-x=∇fixitTx-t-xit+∇fixitTxit-x.Using the subgradient boundedness, we can lower-bound the first term [∇fi(xi(t))]T(x-(t)-xi(t)) as (38)∇fixitTx-t-xit≥-∇fixitx-t-xit.As for the second term [∇fi(xi(t))]T(xi(t)-x), we use the convexity of fi to obtain(39)∇fixitTxit-x≥fixit-fix,from which, by adding and subtracting fi(x-(t)) and using the Lipschitz continuity of fi (implied by the subgradient boundedness), we further obtain(40)∇fixitTx-t-x≥-∇fixitx-t-xit+fixit-fix-t+fix-t-fix≥-∇fixitx-t-xit+∇fix-tTxit-x-t+fix-t-fix≥-∇fixitx-t-xit-∇fix-txit-x-t+fix-t-fix=-∇fixit+∇fix-tx-t-xit+fix-t-fix.Substituting (40) into (36) yields(41)x-t+1-x2≤x-t-x2+2hgtN∑i=1N∇fixit+∇fix-tx-t-xit+fix-fix-t+h2L2g2t≤x-t-x2+4hLgtN∑i=1Nx-t-xit-2hgtN∑i=1Nfix-t-fix+h2L2g2t≤x-t-x2+4hLgtN∑i=1Nx-t-xit-2hgtN∑i=1Nfix-t-fix+h2L2g2t,where in the second inequality we used the subgradient boundedness. Now, suppose that we can employ (41) with x=x∗ for arbitrary x∗∈X∗ to obtain(42)x-t+1-x∗2≤x-t-x∗2+4hLgtN∑i=1Nx-t-xit-2hgtN∑i=1Nfix-t-fix∗+h2L2g2t.By rearranging the above formula and using f(x)=∑i=1Nfi(x), we easily get(43)2hgtNfx-t-f∗+x-t+1-x∗2≤x-t-x∗2+4hLgtN∑i=1Nx-t-xit+h2L2g2t,where f∗ is the optimal value. Summing (43) over [1,∞), dropping the nonnegative term on the left hand side, and multiplying by N on both sides, we obtain(44)2hgt∑t=1∞fx-t-f∗≤Nx-1-x∗2+4hLgt∑t=1∞∑i=1Nx-t-xit+Nh2L2∑t=1∞g2t.Now, we are in the position to analyze inequality (44). The right side of (44) can be partitioned as three items. For the first item, it is easy to get(45)Nx-1-x∗2<∞. Similarly, under the step-size Assumption 5, we immediately obtain (46)Nh2L2∑t=1∞g2t<∞∀t≥0.Thus, we will place emphasis on the second item of (44). Recalling (29), we get(47)∑i=1Nxit-x-t≤N2C∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2Nmax1≤k≤N⁡Ekt-1+N2DCχt-1.Multiplying the above relation with g(t), it yields that(48)gt∑i=1Nxit-x-t≤N2Cgt∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2Ngtmax1≤k≤N⁡Ekt-1+N2DCgtχt-1.By using g(t)χt-1≤g2(t)+χ2(t-1), we have(49)gt∑i=1Nxit-x-t≤N2Cgt∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2Ngtmax1≤k≤N⁡Ekt-1+N2DCg2t+χ2t-1.Therefore, by summing (49) over [1,∞) and rearranging some of the items, we can get(50)∑t=1∞gt∑i=1Nxit-x-t≤2N∑t=1∞gtmax1≤k≤N⁡Ekt-1+N2DC∑t=1∞g2t+χ2t-1+N2C∑t=1∞gt∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1.Since limt→∞⁡Ei(t)=0, then, by Lemmas 8 and 9, we therefore obtain(51)∑t=1∞gtmax1≤k≤N⁡Ekt-1≤∑t=1∞gt2Mhc1-ββt+hLgt<∞.By the step-size Assumption 5 and 0<χ<1, this implies that(52)∑t=1∞g2t+χ2t-1<∞.Since ∑s=1t-1λt-1-s≤1/(1-λ), one has(53)∑t=1∞gt∑s=1t-1χt-1-smax1≤k≤N⁡Ekt-1≤11-λ∑t=1∞gtmax1≤k≤N⁡Ekt-1<∞.Combining (50)–(53), it can be derived that (54)∑t=1∞gt∑i=1Nxit-x-t<∞.Substituting (45), (46), and (54) into (44) yields(55)∑t=1∞gtfx-t-f∗<∞.Since ∑t=1∞g(t)=∞ and f(x-(t))-f∗≥0 (because f∗ is the optimal value), we obtain(56)limt→∞⁡inffx-t-f∗=0.Then, by step-size Assumption 5 we have ∑t=1∞g2(t)<∞. Thus, from (42), we can deduce that the conditions of Lemma 13 are established. Under this lemma, we conclude that the average sequence {x-(t)} converges to a solution x∗∈X∗. Recalling Theorem 11, it yields that each sequence {xi(t)}, i=1,…,N, converges to the same solution x∗. The proof is thus completed.


## 3.1. Distributed Subgradient Algorithm

Consider a setV={1,…,N} of agents. Formally, at each iteration t={1,…,T}, the agent i updates its next time state according to the following laws:(3)xit+1=xit+h∑j∈Niwijtx^jt-x^it-hgt∇fixit,where t∈⋂i∈V[tkii,tki+1i) is the iteration number, h is the control gain, tkii denotes the instant when the kith event happens for the agent i, x^i(t)=xi(tkii) for tkii≤t<tki+1i, the positive scalars g(t)>0 are step-sizes, the scalars wij(t) are nonnegative weights and have an upper bound M, and the vector ∇fi(xi(t)) is a subgradient of the agent i objective function fi(x) at x=xi(t).Remark 4.
Denote the measurement error as(4)eit=x^it-xit,ejt=x^jt-xjt.Then, we can rewrite algorithm (3) into the following form:(5)xit+1=xit+h∑j∈Niwijtxjt-xit+Eit,where Ei(t)=h∑j∈Niwij(t)(ej(t)-ei(t))-hg(t)∇fi(xi(t)) is an error term. Due to (5), it follows that (6)xit+1=xit-h∑j∈Nilijtxjt+Eit.Modifying the second term on the right-hand side in the above formula, we then have(7)xit+1=xit-hliitxit-h∑j=1,j≠iNlijtxjt+Eit=1-hliitxit-h∑j=1,j≠iNlijtxjt+Eit.Letting aii(t)=(1-hlii(t)),aij(t)=-hlij(t), one has(8)xit+1=∑j=1Naijtxjt+Eit.Since graph G(t) is balanced, we then have ∑j=1Naij(t)=1 and ∑i=1Naij(t)=1 hold if h satisfies 1-hlii(t)>0.Before giving some supporting lemmas, we need the following assumption on the sequences of step-sizes and{A(t)}.Assumption 5 (step-size assumption).
The step-sizes{g(t)} are positive sequence, which satisfies the following: (9)∑t=0+∞gt=+∞,∑t=0+∞g2t<+∞,gt≤gs∀t>s≥1.Assumption 6 (nondegeneracy).
There exists a constantη with 0<η<1 such that, for all i,j∈{1,…,n}, (a) aii(t)≥η for all t≥0 and (b) if aij(t)≥0, then aij(t)≥η.
Next, the transition matrices are introduced as follows:(10)Φt,s=AsAs+1⋯At-1At∀s,twitht≥s,where Φ(t,t)=A(t) for all t. And the ith column of Φ(t,s) is defined as [Φ(t,s)]i=AsAs+1⋯A(t-1)ai(t). Meanwhile, the entry in ith column and jth row of Φ(t,s) is described as [Φ(t,s)]ij=[A(s)A(s+1)⋯A(t-1)ai(t)]j. A crucial property of the transition matrices is given in the following, which plays a key role in our analysis of the algorithms.Lemma 7 (see [35]).
Let the weight-balanced Assumption1, the uniformly strongly connected Assumption 2, and the nondegeneracy Assumption 6 hold. Then the entries [Φ(t,s)]ij of the transition matrices converge as t→∞ to a uniform geometric rate 1/N with respect to i and j, that is, for all i,j∈{1,…,N},(11)Φt,sij-1N≤21+η-B01-ηB01-ηB0t-s/B0∀s,twitht≥s,where η is the lower bound of the nondegeneracy Assumption 6, N is the number of agents, B0=(N-1)B, and B is given in the uniformly strongly connected Assumption 2.Proof.
We refer the reader to the papers [35, 37] for proofs of this and similar assertions.Before moving on, it is important to introduce the following lemma and the proof of the lemma.Lemma 8 (see [33]).
Let0<λ<1 and let {ψt} be a positive scalar sequence. Suppose limt→∞⁡ψt=0. Then(12)limt→∞∑l=0tλt-lψl=0.Furthermore, if ∑t=0∞ψt<∞, then(13)∑t=0∞∑l=0tλt-lψl<∞.Proof.
We do not give the proof of Lemma8 since it is almost identical to that of Lemma  7 in [33].Chen and Ren [47] provided an event-triggered consensus algorithm of multiagent system. Inspired by this work, we design a new event-triggered scheme applied as follows.We now define the triggering time sequence{tki} for agent i by (14)tk+1i=inf⁡t:t>tki,yit>0,where(15)yit=eit-c1-ββtis referred to as the trigger function for all 0<β<1, c>0, and ei(t)=x^i(t)-xi(t). Therefore, we can conclude that ei(t)=0 at t=tki.Lemma 9.
(16)
l
i
m
t
→
∞
E
i
t
=
0
.Proof.
SinceEi(t)=h∑j∈Niwij(t)(ej(t)-ei(t))-hg(t)∇fi(xi(t)), then we have for all t>0(17)Eit=h∑j∈Niwijtejt-eit-hgt∇fixit≤h∑j∈Niwijtejt-eit+hgt∇fixit.By the weight-balanced Assumption 1 and the subgradient boundedness Assumption 3, we therefore have(18)Eit≤2Mheit+hLgt,where L=maxi∈VLi. Substituting (15) into (18) yields (19)Eit≤2Mhc1-ββt+hLgt.Taking the limits of both sides of (19) as t→∞, one can see that limt→∞⁡Ei(t)=0. Thus, the proof is completed.Remark 10.
Lemma9 shows that if the error term in system (8) decays, the differences between the states of all the agents will vanish asymptotically.


## 3.2. Convergence Analysis

We next introduce the characteristic that the agents reach a consensus asymptotically, which means the agent estimatesxi(t) converge to the same point when t goes to infinity.Theorem 11 (consensus).
Let the weight-balanced Assumption1, the uniformly strongly connected Assumption 2, the subgradient boundedness Assumption 3, the step-size Assumption 5, and the nondegeneracy Assumption 6 hold. Consider the sequence {xi(t)} being produced by the distributed subgradient algorithm (3). We then have for x-(t)=(1/N)∑i=1Nxi(t) and all i(20)limt→∞xit-x-t=0.Proof.
It is obtained from (8) that(21)xt+1=Atxt+Et=AtAt-1xt-1+Et-1+Et=AtAt-1At-2xt-2+Et-2+AtEt-1+Et⋮=AtAt-1At-2⋯A0x0+AtAt-1⋯A1E0+⋯+AtAt-1Et-2+AtEt-1+Et.Using the transition matrices Φ(t,s), we can write for all t and s with t>s(22)xt+1=Φt:0x0+∑s=1tΦt:sEs-1+Et.Therefore, we have the following:(23)xit=∑j=1NΦt-1,0ijxj0+∑s=1t-1∑j=1NΦt-1,sijEjs-1+Eit-1.Then, using (8) and x-(t)=(1/N)∑i=1Nxi(t), we can achieve that(24)x-t=x-t-1+1N∑i=1NEit-1=x-t-2+1N∑i=1NEit-2+1N∑i=1NEit-1⋮=x-0+1N∑i=1NEi0+⋯+1N∑i=1NEit-2+1N∑i=1NEit-1=x-0+1N∑s=0t-1∑i=1NEis.Together with (23), it yields that(25)xit-x-t=∑j=1NΦt-1,0ijxj0+∑s=1t-1∑j=1NΦt-1,sijEjs-1+Eit-1-∑j=1N1Nxj0-∑s=1t-1∑j=1N1NEjs-1-1N∑j=1NEjt-1=∑j=1NΦt-1,0ij-1Nxj0+∑s=1t-1∑j=1NΦt-1,sij-1NEjs-1+Eit-1-1N∑j=1NEjt-1.According to the property of standard Euclidean norm, we then have(26)xit-x-t≤max1≤k≤N⁡xk0·∑j=1NΦt-1,0ij-1N+∑s=1t-1∑j=1NΦt-1,sij-1NEjs-1+1N∑j=1NEjt-1-Eit-1≤max1≤k≤N⁡xk0·N·maxi,j∈1,2,…,N⁡Φt-1,0ij-1N+∑s=1t-1N·maxi,j∈1,2,…,N⁡Φt-1,0ij-1N·max1≤k≤N⁡Eks-1+1N∑j=1NEjt-1-Eit-1.Letting b(t,s)=maxi,j∈{1,2,…,N}[Φ(t,s)]ij-(1/N) and D=max1≤k≤Nxk(0), the following inequality can be built: that is,(27)xit-x-t≤N∑s=1t-1bt-1,smax1≤k≤N⁡Eks-1+2max1≤k≤N⁡Ekt-1+NDbt-1,0.Using the upper bound estimate for [Φ(t,s)]ij-(1/N) of Lemma 7, we get for all t≥s(28)Φt,sij-1N≤Cχt-s∀i,j,with C=2(1+η-B0/1-ηB0) and χ=(1-ηB0)1/B0. Therefore, this together with (27) results in(29)xit-x-t≤NC∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2max1≤k≤N⁡Ekt-1+NDCχt-1.By Lemmas 8 and 9 and taking limits on both sides of (29), one can finally have limt→∞⁡xi(t)-x-(t)=0 for all i∈{1,…,N}.We now begin to introduce a well-known convergence result which is shown in the following lemma.Lemma 12 (see [38]).
Letvt be a nonnegative scalar sequence such that(30)vt+1≤1+btvt-ut+ct∀t≥0,where b(t)≥0,u(t)≥0, and c(t)≥0 for all t≥0 with ∑t=0∞b(t)<∞ and ∑t=0∞c(t)<∞. Then, the sequence {v(t)} converges to some v≥0 and ∑t=0∞u(t)<∞.Proof.
The proof process can imitate that of [38], and thus it is omitted.In what follows, we present a key lemma, which is important in the analysis of the distributed optimization algorithm. Thereafter, we study the convergence behavior of the subgradient algorithm, where the optimal solution can be asymptotically reached.Lemma 13 (see [46]).
Consider an optimization problemminx∈Rn⁡f(x), where f:Rn→R is a continuous objective function. Assume that the optimal solution set X∗ of the optimization problem is nonempty. Let {x(t)} be a sequence with all x∈X∗ and all t≥0 such that(31)xt+1-x2≤1+btxt-x2-αtfxt-fx+ct,where b(t)≥0, α(t)≥0, and c(t)≥0 for all t≥0 with ∑t=0∞b(t)<∞, ∑t=0∞α(t)=∞, and ∑t=0∞c(t)<∞. Then the sequence {x(t)} converges to some optimal solution x∗∈X∗.Proof.
The proof procedure can imitate that of Lemma  7 in [46], and thus it is omitted.Theorem 14 (optimization).
Let the weight-balanced Assumption1, the uniformly strongly connected Assumption 2, the subgradient boundedness Assumption 3, the step-size Assumption 5, and the nondegeneracy Assumption 6 hold. For problem (1), consider the sequence {xi(t)} being updated by the distributed subgradient algorithm (3). Then there exists an optimal solution x∗∈X∗ such that (32)limt→∞⁡xit-x∗=0∀i∈1,…,N.Proof.
Applying (3) to the average process, it is obtained that(33)1N∑i=1Nxit+1=1N∑i=1Nxit+hN∑i=1N∑j∈Niwijtx^jt-x^it-hNgt∑i=1N∇fixit.Using x-=(1/N)∑i=1Nxi(t), the control law (33) can be rewritten as(34)x-t+1=x-t-hNgt∑i=1N∇fixit.Now, let x∈Rn be arbitrary vector; we have for all t≥0 that(35)x-t+1-x2=x-t-hNgt∑i=1N∇fixit-x2=x-t-x2-2hNgt∑i=1N∇fixitTx-t-x+h2N2g2t∑i=1N∇fixit2.Since the subgradient of each fi(x) is uniformly bounded by Li and L=maxi∈V⁡Li, then it follows that for all t≥0(36)x-t+1-x2≤x-t-x2-2hNgt∑i=1N∇fixitTx-t-x+h2L2g2t.We next study the cross-term ∇fi(xi(t))T(x-(t)-x) in (36). For this term, we write(37)∇fixitTx-t-x=∇fixitTx-t-xit+∇fixitTxit-x.Using the subgradient boundedness, we can lower-bound the first term [∇fi(xi(t))]T(x-(t)-xi(t)) as (38)∇fixitTx-t-xit≥-∇fixitx-t-xit.As for the second term [∇fi(xi(t))]T(xi(t)-x), we use the convexity of fi to obtain(39)∇fixitTxit-x≥fixit-fix,from which, by adding and subtracting fi(x-(t)) and using the Lipschitz continuity of fi (implied by the subgradient boundedness), we further obtain(40)∇fixitTx-t-x≥-∇fixitx-t-xit+fixit-fix-t+fix-t-fix≥-∇fixitx-t-xit+∇fix-tTxit-x-t+fix-t-fix≥-∇fixitx-t-xit-∇fix-txit-x-t+fix-t-fix=-∇fixit+∇fix-tx-t-xit+fix-t-fix.Substituting (40) into (36) yields(41)x-t+1-x2≤x-t-x2+2hgtN∑i=1N∇fixit+∇fix-tx-t-xit+fix-fix-t+h2L2g2t≤x-t-x2+4hLgtN∑i=1Nx-t-xit-2hgtN∑i=1Nfix-t-fix+h2L2g2t≤x-t-x2+4hLgtN∑i=1Nx-t-xit-2hgtN∑i=1Nfix-t-fix+h2L2g2t,where in the second inequality we used the subgradient boundedness. Now, suppose that we can employ (41) with x=x∗ for arbitrary x∗∈X∗ to obtain(42)x-t+1-x∗2≤x-t-x∗2+4hLgtN∑i=1Nx-t-xit-2hgtN∑i=1Nfix-t-fix∗+h2L2g2t.By rearranging the above formula and using f(x)=∑i=1Nfi(x), we easily get(43)2hgtNfx-t-f∗+x-t+1-x∗2≤x-t-x∗2+4hLgtN∑i=1Nx-t-xit+h2L2g2t,where f∗ is the optimal value. Summing (43) over [1,∞), dropping the nonnegative term on the left hand side, and multiplying by N on both sides, we obtain(44)2hgt∑t=1∞fx-t-f∗≤Nx-1-x∗2+4hLgt∑t=1∞∑i=1Nx-t-xit+Nh2L2∑t=1∞g2t.Now, we are in the position to analyze inequality (44). The right side of (44) can be partitioned as three items. For the first item, it is easy to get(45)Nx-1-x∗2<∞. Similarly, under the step-size Assumption 5, we immediately obtain (46)Nh2L2∑t=1∞g2t<∞∀t≥0.Thus, we will place emphasis on the second item of (44). Recalling (29), we get(47)∑i=1Nxit-x-t≤N2C∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2Nmax1≤k≤N⁡Ekt-1+N2DCχt-1.Multiplying the above relation with g(t), it yields that(48)gt∑i=1Nxit-x-t≤N2Cgt∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2Ngtmax1≤k≤N⁡Ekt-1+N2DCgtχt-1.By using g(t)χt-1≤g2(t)+χ2(t-1), we have(49)gt∑i=1Nxit-x-t≤N2Cgt∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1+2Ngtmax1≤k≤N⁡Ekt-1+N2DCg2t+χ2t-1.Therefore, by summing (49) over [1,∞) and rearranging some of the items, we can get(50)∑t=1∞gt∑i=1Nxit-x-t≤2N∑t=1∞gtmax1≤k≤N⁡Ekt-1+N2DC∑t=1∞g2t+χ2t-1+N2C∑t=1∞gt∑s=1t-1χt-1-smax1≤k≤N⁡Eks-1.Since limt→∞⁡Ei(t)=0, then, by Lemmas 8 and 9, we therefore obtain(51)∑t=1∞gtmax1≤k≤N⁡Ekt-1≤∑t=1∞gt2Mhc1-ββt+hLgt<∞.By the step-size Assumption 5 and 0<χ<1, this implies that(52)∑t=1∞g2t+χ2t-1<∞.Since ∑s=1t-1λt-1-s≤1/(1-λ), one has(53)∑t=1∞gt∑s=1t-1χt-1-smax1≤k≤N⁡Ekt-1≤11-λ∑t=1∞gtmax1≤k≤N⁡Ekt-1<∞.Combining (50)–(53), it can be derived that (54)∑t=1∞gt∑i=1Nxit-x-t<∞.Substituting (45), (46), and (54) into (44) yields(55)∑t=1∞gtfx-t-f∗<∞.Since ∑t=1∞g(t)=∞ and f(x-(t))-f∗≥0 (because f∗ is the optimal value), we obtain(56)limt→∞⁡inffx-t-f∗=0.Then, by step-size Assumption 5 we have ∑t=1∞g2(t)<∞. Thus, from (42), we can deduce that the conditions of Lemma 13 are established. Under this lemma, we conclude that the average sequence {x-(t)} converges to a solution x∗∈X∗. Recalling Theorem 11, it yields that each sequence {xi(t)}, i=1,…,N, converges to the same solution x∗. The proof is thus completed.


## 4. Numerical Example

In this section, a numerical example is presented to verify the feasibility of the proposed algorithm and correctness of our theoretical analysis. Consider the time-varying communication graphG(t)={V,E(t),W(t)=[wij]5×5}, where E(t)={(1,2),(2,1),(2,4),(4,2),(3,5),(5,3)}, w12(t)=1.5, w21(t)=1.5, w24(t)=0.7, w42(t)=0.7, w35(t)=0.7, w53(t)=0.7, and wij(t)=0, if (i,j)∉E(t) when t=3k,k=0,1,….E(t)={(1,2),(1,3),(2,4),(3,1),(4,5),(5,3)}, w12(t)=1.25, w13(t)=1.25, w24(t)=1.25, w31(t)=2.5, w45(t)=1.25, w53(t)=1.25, and wij(t)=0, if (i,j)∉E(t) when t=3k+1,k=0,1,….E(t)={(1,3),(3,1),(4,5),(5,4)}, w13(t)=0.9, w31(t)=0.9, w45(t)=0.9, w54(t)=0.9, and wij(t)=0, and if (i,j)∉E(t) when t=3k+2,k=0,1,…. Obviously, G(t) is a directed balanced graph sequence. Moreover, by computation, one has η=0.7, B=3, B0=12, C=2.0561, and χ=0.995. In the following example, the graph sequence G(t) described above will be employed.Example 1.
Consider the optimization problem (1) with fi(x)=0.5x2ln⁡(1+x2)+x2(i=1,2,3,4,5), where fi:R3→R is the convex objective function of agent i and x∈R3 is a global decision vector. Moreover, we use algorithm (3) with the triggering function (15). In simulation, we select the design parameters β=e-0.015, c=1/(1-e-0.015), and h=0.005 and the step-sizes {g(t)}=0.02/(t+d). The simulation results of the distributed subgradient algorithm (3) are shown in Figures 1–4. The state evolutions of all agents are shown in Figure 1, from which we can observe that all the agents asymptotically achieve the optimal solution by taking 800 iterations. Figure 2 shows that the distributed control input ui(t) tends to 0 when achieving consensus. The event-triggered sampling time instants for each agent are described in Figure 3, from which we can observe that the updates of the control inputs are asynchronous. According to the statistics, the sampling times for the five agents are [20,20,20,19,18], and the average sampling time is 20. Thus, the average update rate of control inputs is 20/800=2.5%. In Figure 4, for agent 1, it is explicit that the norm of measurement error e1(t) is asymptotically reduced to zero.Figure 1
All agents’ statesxi(t).Figure 2
Evolution of all agents’ control inputsui(t).Figure 3
All agents’ sampling time instant sequences{tkii}.Figure 4
Evolution of measurement error and threshold for agent1.


## 5. Conclusion and Future Work

In this paper, a novel consensus-based event-triggered algorithm for solving the distributed convex optimization problem over time-varying directed networks has been analyzed in detail. We have proved that, based on the designed distributed event-triggered scheme and the uniformly strongly connected communication graph sequence{G(t)}, the algorithm succeeds in making all the nodes converge to the optimal point asymptotically. Moreover, the theoretical results are demonstrated through a numerical example. Future work will concentrate on the event-triggered algorithms for the constrained convex optimization problem. And the convergence rate of the algorithm we introduce in this paper deserves further investigation as well.



---

*Source: 5385708-2017-05-21.xml*