# Distributed Adaptive Optimization for Generalized Linear Multiagent Systems

Authors: Shuxin Liu; Haijun Jiang; Liwei Zhang; Xuehui Mei
Journal: Discrete Dynamics in Nature and Society
 (2019)

---

## Abstract

In this paper, the edge-based and node-based adaptive algorithms are established, respectively, to solve the distribution convex optimization problem. The algorithms are based on multiagent systems with general linear dynamics; each agent uses only local information and cooperatively reaches the minimizer. Compared with existing results, a damping term in the adaptive law is introduced for the adaptive algorithms, which makes the algorithms more robust. Under some sufficient conditions, all agents asymptotically converge to the consensus value which minimizes the cost function. An example is provided for the effectiveness of the proposed algorithms.


---

## Body

## 1. Introduction

Recently, the consensus problems of multiagent systems have been extensively investigated on account of its widespread application, such as cooperative reconnaissance and unmanned aerial vehicles formation. Many meaningful results about consensus algorithms [1–7] have been established. Specially, the consensus problems can solve the distributed optimization, when the consensus value minimizes the global cost function, which is a sum of local objective functions each of which is known by one agent.Meanwhile, with the development of various network systems, various distributed optimization problems have emerged. Extensive efforts to design the efficient algorithm have been put into the distributed optimization problems. Because of the advantages of decentralized and distributed structure, the distributed algorithms based on multiagent systems are more efficient than the centralized algorithm. A large number of consensus-based optimization algorithms have been presented over the past two decades. For instance, in [8, 9], the subgradient algorithms upon multiagent systems have been presented. In [10], the algorithms with fixed step size have been proposed. In [11], edge-based fixed-time consensus algorithms have been established. More results can be found in [12–15].In the above works, the proposed optimization algorithms depend on the selection of constant control gains. In fact, the lower bound of the gains is determined by the smallest nonzero eigenvalue of Laplacian matrix for the communication graph, i.e., algebraic connectivity which is global information. These consensus algorithms are not fully distributed. To face this challenge, some well-performing adaptive algorithms have been proposed, where the adaptive gain updating laws rely on local information of the agents. For example, in [16, 17], the adaptive algorithms of the finite time convergence have been established upon integrator multiagent systems. In [18], the adaptive algorithms have been proposed upon general linear multiagent systems from the edge-based and node-based design.Note that more agent networks in practical applications are described by generalized linear systems. Moreover, from the results in [19], the control gains in [17, 18] monotonically increase very quickly when the value of the initial states is large. Overlarge control gains will magnify the control input and will lead to unstable algorithms. Based on the above considerations, from the edge-based and node-based standpoint two distributed adaptive algorithms for solving the distributed convex optimization problems are proposed upon general linear multiagent systems in this paper. Compared with the existing algorithms, the proposed algorithms based on generalized linear dynamical systems are more practical and its theoretical analysis is more difficult than that based on integrator systems. The algorithm does not require global information, which makes it fully distributed and easier to implement. The proposed algorithms introduce a damping term in the update law, which makes the algorithm robust under input disturbance and the high-gain update law.The article is organized as follows. In next section, some preliminaries and lemmas are introduced. In Section3, the edge-based and node-based consensus protocols are designed for solving the distributed convex optimization; the asymptotic convergence is guaranteed for the adaptive algorithms. In Section 4, the effectiveness of the performance for the algorithm to solve the distributed convex optimization problems is presented by a typical example. In Section 5, a brief conclusion is given.


## 2. Notations and Preliminaries

In this paper,Rl is the set of all l-dimensional real vectors. Rm×q is the set of m×q real matrices. 1=[1,1,…,1]T means the vector that all the elements are one. Im is the m-dimensional identity matrix. For a real matrix B, B>0(B≥0) means B is positive definite (semidefinite). (·)T represents the transpose. ·1, ·, and ·∞ denote the 1-norm, 2-norm and infinite norm, respectively. Given y∈Rl, ∇h(y)=(∂h(y)/∂y1,∂h(y)/∂y2,…,∂h(y)/∂yl)T represents the gradient of the function h(y). The function g(t):R→Rl is g(t)∈L2, if ∫0∞g(t)Tg(t)dt<0 and g(t)∈L∞ if for any element gi(t) for g(t), supt⁡git<∞,i=1,…,l.An undirected graphG consists of a node set V={1,2,…,m} and an edge set E⊆V×V, the edge (i,j)∈E if and only if (j,i)∈E, and the self-edge (i,i) is not allowed. The incidence matrix D=[dij]m×E corresponds to a graph G with an arbitrary orientation, namely, whose edges have a terminal node and initial node. For jth edge, if the node i is initial, dij=1, if the node i is terminal, dij=-1; otherwise, dij=0. The graph Laplacian of G is defined as L=DDT. A path in the graph G from i to j is a sequence of distinct nodes starting with i and ending with j. The graph G is connected, if there is a path between any two nodes.Assumption 1.
The undirected graphG is connected.Lemma 2 (see [20]).
Under Assumption1, L is positive semidefinite, 0 is a simple eigenvalue for L, and 1 is the associated eigenvector; its smallest nonzero eigenvalue λ2=miny≠0,1Ty=0⁡yTLx/yTy.Lemma 3 (see [21]).
Leth(y):Rl→R be a continuously differentiable convex function; then h(y) is minimized if and only if limu→y⁡∇h(u)=0.Lemma 4 (see [22]).
Ifg(t),g˙(t)∈L∞, and g(t)∈Lp,p∈[1,+∞), then limt→∞⁡g(t)=0.


## 3. Problem Formulation

Consider the following multiagent system; each agent satisfies the dynamics:(1)y˙it=Byit+Cuit,i∈T=1,2,…,m,where ui(t)∈Rq is the protocol, yi(t) is the state for ith agent, and B∈Rl×l and C∈Rl×q are the constant matrices.Our aim is to designui(t) for (1) by using only local information, such that all agents cooperatively arrive the consensus value y∗ which minimizes the convex problem(2)min∑i=1mhiy,subjecttoy∈Rl,where hi(y):Rl→R is a local cost function, which is known only to agent i.We give the following hypothesis.Assumption 5.
The local cost functionhi(y) is convex and differentiable; its gradient satisfies(3)∇hiy=B~y+C~ψiy,where B,C are defined in (1), B~=KB,C~=KC, K∈Rl×l is some negative define matrix, ψi(y) is continuous, and there exists η>0 such that ψi(y)-ψj(y)∞≤η, i,j∈T, for all y∈Rl.
The equivalent characterization for (2) is that the agents achieve consensus value which minimizes the function ∑i=1mhi(yi), namely,(4)min∑i=1mhiyi,subjecttolimt→∞⁡yit-yjt=0,i,j∈T.Assumption 6.
Each setΩi={yi:∇hi(yi)=0},i∈T is nonempty; that is to say, there exists yi∗∈Rl such that hi(yi∗) is minimum.


## 4. Edge-Based Adaptive Designs

To solve problem (3), the edge-based adaptive algorithm for (1) is presented as follows:(5)uit=-∑j∈NiξijPyit-yjt-∑j∈Niςijsign⁡Pyit-yjt+ψiyi,(6)ξ˙ij=Pyit-yjt2-σijξij-ξ~ij,(7)ς˙ij=Pyit-yjt1-σijςij-ς~ij,(8)ξ~˙ijt=ρijξij-ξ~ij,ς~˙ij=ρijςij-ς~ij,where ξij,ςij are adaptive coupling strengths, Q is a feedback matrix, the initial states satisfy ξij(0)≥ξ~ij(0), and ςij(0)≥ς~ij(0).From (5), system (1) can be written as follows:(9)yit=Byit-C∑j∈NiξijPyit-yjt-C∑j∈Niςijsign⁡Pyit-yjt+Cψiyit,Denote y(t)=(y1(t)T,y2(t)T,…,ym(t)T)T and Ψ(t)=(ψ1T(y1(t)),ψ2T(y2(t)),⋯,ψmT(ym(t)))T. Thus, (9) can be represented by the compact form(10)y˙t=Im⊗Byt-DADT⊗CPyt-DB⊗Csign⁡DT⊗Pyt+M⊗CΨyt,where D is the incidence matrix, A=diag⁡{ξij}, and B=diag⁡{ςij}. The solution of the system (10) is understood by the sense of Filippov [23].Note thatMD=DM=D; multiplying both sides of (10) by M⊗Im, we get the error system(11)ϵ˙t=Im⊗Bϵt-DADT⊗CPϵt-DB⊗Csign⁡DT⊗Pϵt+M⊗CΨyt,where M=Im-1/m11T, ϵ(t)=(ϵ1(t)T,ϵ2(t)T,…,ϵm(t)T)T=(M⊗Im)y(t). Obviously, y1(t)=y2(t)⋯=ym(t) if and only if limt→∞⁡ϵ(t)=0.Theorem 7.
Under Assumptions1–6 and Lemma 3, problem (4) can be solved by algorithm (5), if there exists the feedback matrix P=CTQ, such that(12)QB+BTQ-QCCTQ<0,where Q is the positive-definite matrix. Meanwhile, as t→∞, we have ξij(t) and ξ~ij(t)(ςij(t)andς~ij(t)) will converge to the same positive number.Proof.
Choose the Lyapunov function candidate(13)Vt=ϵtTIm⊗Qϵt+12∑i=1m∑j∈Niξij-a2+∑i=1m∑j∈Niσij2ρijξ~ij-a2+12∑i=1m∑j∈Niςij-b2+∑i=1m∑j∈Niσij2ρijς~ij-b2,where a and b are the positive constants; Q is the positive-definite matrix.
TakeP=CTQ; we have(14)V˙t=ϵtTIm⊗QB+BTQ-2DADT⊗QCCTQϵt-2ϵtTDB⊗QCsign⁡DT⊗CTQϵt+2ϵtTM⊗QCΨyt+∑i=1m∑j∈Niξij-aξ˙ij+∑i=1m∑j∈Niσijρijξ~ij-aξ~˙ij+∑i=1m∑j∈Niςij-bς˙ij+∑i=1m∑j∈Niσijρijς~ij-bς~˙ij.From the third term in (14) and (M⊗Iq)Ψ(y(t)1≤η, we get(15)ϵtTM⊗QCΨyt≤M⊗CTQϵt1M⊗IqΨ(yt∞≤ηm∑i=1m∑j=1mCTQϵti-ϵtj1≤ηm∑i=1mmaxi⁡∑j=1mCTQϵti-ϵtj1=ηmaxi⁡∑j=1mCTQϵti-ϵtj1≤η2m-1∑i=1m∑j∈NiβijCTQϵit-ϵjt1.According to the fourth term in (14), we obtain (16)∑i=1m∑j∈Niξij-aξ˙ij+∑i=1m∑j∈Niσijρijξ~ij-aξ~˙ij=∑i=1m∑j∈Niξij-aPyit-yjt2-∑i=1m∑j∈Niσijξij-aξij-ξ~ij+∑i=1m∑j∈Niσijξ~ij-aξij-ξ~ij=ytT2DADT⊗QCCTQ-2aL⊗QCCTQyt-∑i=1m∑j∈Niσijξij-ξ~ij2=ϵtT2DADT⊗QCCTQ-2aL⊗QCCTQϵt-∑i=1m∑j∈Niσijξij-ξ~ij2.Note that(17)2ytTDB⊗QCsign⁡DT⊗CTQyt=∑i=1m∑j∈NiςijCTQyit-yjt1,(18)2ϵtTD⊗QCsign⁡DT⊗CTQϵt=∑i=1m∑j∈NiςijCTQϵit-ϵjt1,by the fourth term in (14), we obtain (19)∑i=1m∑j∈Niςij-bς˙ij+∑i=1m∑j∈Niσijρijς~ij-bς~˙ij=∑i=1m∑j∈Niςij-bPyit-yjt1-∑i=1m∑j∈Niσijςij-bςij-ς~ij-∑i=1m∑j∈Niσijς~ij-bςij-ς~ij=∑i=1m∑j∈Niςij-bPyit-yjt1-∑i=1m∑j∈Niσijςij-ς~ij2=ytTDB⊗QCsign⁡DT⊗CTQyt+ytTbD⊗QCsign⁡DT⊗CTQyt-∑i=1m∑j∈Niσijςij-ς~ij2=ϵtTDB⊗QCsign⁡DT⊗CTQϵt-b∑i=1m∑j∈NiCTQϵit-ϵjt1-∑i=1m∑j∈Niσijςij-ς~ij2.From (15), (16), and (19), we get(20)V˙t≤ϵtTIm⊗QB+BTQ-2aL⊗QCCTQϵt+ηm-1-b∑i=1m∑j∈NiCTQϵit-ϵjt1-∑i=1m∑j∈Niσijξij-ξ~ij2-∑i=1m∑j∈Niσijςij-ς~ij2,and choose a>1/2λ2, b≥η(m-1), due to (12),(21)V˙t≤ϵtTIm⊗QB+BTQ-2aλ2⊗QCCTQϵt≤ϵtTIm⊗QB+BTQ-QCCTQϵt≤0,i.e., V(t) is nonincreasing. Moreover, from (13), we have ϵ(t),ϵ˙(t),ξij,ξ~ij,ςij,ς~ij∈L∞. Meanwhile, integrating both sides of (21), one has ϵ(t)∈L2. Thus, ϵ(t)∈L2∩L∞. From Lemma 4, limt→∞⁡ϵ(t)=0; that is, limt→∞⁡(yi(t)-1/m∑i=1myi(t))=0.
Let consensus valuey∗(t)=1/m∑i=1myi(t); then (22)dy∗tdt=1m∑i=1mdyitdt=1m∑i=1mByit-C∑j∈NiξijPyit-yjt-C∑j∈Niςijsign⁡Pyit-yjt+Cψiyit=1m∑i=1mByit+Cψiyit,According to Assumption 5, we have(23)dy∗tdt=1mK-1∑i=1mB~y∗t+C~ψiy∗t=1mK-1∑i=1m∇hiy∗t,thus,(24)d∑i=1mhiy∗tdt=1m∑i=1m∇hiy∗tTdy∗tdt=1m∑i=1m∇hiy∗tTK-11m∑i=1m∇hiy∗t≤0.From Assumption 1, ∑i=1m(hi(y∗(t))) is bounded below; that is, limt→∞⁡d∑i=1mhi(y∗(t))/dt=0. Thus, we obtain limt→∞⁡1/m∑i=1m(∇hi(y∗(t)))=0. From Lemma 2, when t→∞, y∗(t) minimizes the cost function ∑i=1mhi(y(t)).
Letς^ij=ςij-ς~ij, then(25)ς^˙ij=ς˙ij-ς~˙ij=Pyit-yjt1-σijςij-ς~ij-ρijςij-ς~ij=Pyit-yjt1-σij+ρijς^ijTo solve (25), one has(26)ς^ijt=e-σij+ρijtς^ij0+∫0te-σij+ρijt-sPyis-yjs1ds=e-σij+ρijtς^ij0+∫0teσij+ρijsPyis-yjs1dsBy yi∈L2, we have ς^ij(t)∈L∞. From ςij(0)≥ς~ij(0), we obtain ς^ij(0)≥0. By (26), ς^ij(t)≥0. Now, let us prove limt→∞⁡ς^ij(t)=0. Consider the following two cases.
( 1 )  ∫0te(σij+ρij)sP(yi(s)-yj(s))1ds is bounded. Then, (27)limt→∞⁡ς^ijt=limt→∞⁡e-σij+ρijtς^ij0+∫0teσij+ρijsPyis-yjs1ds=0.
( 2 )  limt→∞⁡∫0te(σij+ρij)sP(yi(s)-yj(s))1ds=∞. Then, (28)limt→∞⁡ς^ijt=limt→∞⁡e-σij+ρijtς^ij0+∫0teσij+ρijsPyis-yjs1ds=limt→∞⁡ς^ij0+∫0teσij+ρijsPyis-yjs1dseσij+ρijt=limt→∞⁡Pyit-yjt1σij+ρij=0.Based on ς~ij(t)∈L∞ and ς~ij(t) is monotonically increasing, when t→∞, we acquire that ς~ij(t) will converge to some positive constant. From limt→∞⁡ς^ij(t)=0, we have ςij(t) and ς~ij(t) will converge to the same positive number. For ξij(t) and ξ~ij(t), we have the same results.Remark 8.
Here, damping termsξ~ij(t),ς~ij(t) are designed for the gain adaption law of the adaptive algorithm (5). ς~ij(t) increases monotonically and converges to a finite positive constant. Choosing ς^ij(0)=0, by (26), limt→∞⁡ς^ij(t)=0, and ς^ij(t)≥0, we have that ς^ij(t) will increase from zero and then decrease to zero. In other words, ςij(t) will increase at first and then decrease for some time upon the select of σij and ρij. For ξij(t), we have similar results. Compared with the adaptive law in [14, 15], the advantage of the adaptive law introducing the damping term is that the adaptive control gains and the amplitude of the control inputs are smaller; this makes our algorithm more robust.


## 5. Node-Based Adaptive Designs

To solve problem (3), the node-based protocol for (1) is proposed as follows:(29)uit=-ζisign⁡P∑j∈Niyit-yjt+ψiyi,(30)ζ˙i=P∑j∈Niyit-yjt1-σiζi-ζ~i,(31)ζ~˙i=ρiζi-ζ~i,where ζi are adaptive coupling strengths, Q is a feedback matrix, and the initial states satisfy ζi(0)≥ζ~i(0).From (1) and (29), the closed-loop system can be represented as follows:(32)yit=Byit-ζiCsign⁡P∑j∈Niyit-yjt+Cψiyit,where the first and third terms take the role to minimize the function hi(yi(t)), and the second term makes the agents achieve consensus.Denotey(t)=(y1(t)T,y2(t)T,…,ym(t)T)T, ζ=diag⁡ξij, and Ψ(t)=(ψ1T(y1(t)),ψ2T(y2(t)),…,ψmT(ym(t)))T; by (32) we obtain(33)y˙t=Im⊗Byt-ζ⊗Csign⁡L⊗Pyt+Im⊗CΨyt.Note that ML=DL=D; multiply both sides of (33) by M⊗Im; the following error system is obtained:(34)ϵ˙t=Im⊗Bϵt-ζ⊗Csign⁡L⊗Pϵt+Im⊗CΨyt,where M=Im-1/m11T, ϵ(t)=(ϵ1(t)T,ϵ2(t)T,…,ϵm(t)T)T=(M⊗Im)y(t).Theorem 9.
Under Assumptions1–6 and Lemma 3, problem (29) can be solved by the nosed-based algorithm (5) if P=CTQ, where Q>0 satisfies(35)QB+BTQ<0,Meanwhile, as t→∞, we have ζi(t) and ζ~i(t) will converge to the same positive number.Proof.
Choose the Lyapunov function candidate(36)Vt=ϵtTL⊗Qϵt+12∑i=1mζi-a2+∑i=1mσi2ρiζ~i-a2,where Q>0; a is a positive constant.
Calculate the derivative ofV(t) along system (34) and choose P=CTQ; we have(37)V˙t=ϵtTL⊗QB+BTQϵt+2ϵtTL⊗QCΨyt-2ϵtTL⊗QCsign⁡L⊗CTQϵt+∑i=1mζi-aζ˙i+∑i=1mσiρiζ~i-aζ~˙i.From the third term in (37) and (M⊗Iq)Ψ(y(t)1≤η, we have(38)ϵtTM⊗QCΨyt≤M⊗CTQϵt1M⊗IqΨ(yt1≤η∑i=1mζi∑j∈NiCTQϵit-ϵjt1.By the results(39)ytTL⊗QCζsign⁡L⊗CTQyt=∑i=1mζiCTQ∑j∈Niyit-yjt1,ϵtTaL⊗QCsign⁡L⊗CTQϵt=a∑i=1mCTQ∑j∈Niϵit-ϵjt1,we obtain(40)∑i=1mζi-aζ˙i+∑i=1mσiρiζ~i-aζ~˙i=∑i=1mζi-aP∑j∈Niyit-yjt1-∑i=1mσiζi-aζi-ζ~i+∑i=1mσiζ~i-aζi-ζ~i=∑i=1mζi-aP∑j∈Niyit-yjt1-∑i=1mσiζi-ζ~i2=ytTL⊗QCζsign⁡L⊗CTQyt+ytTaL⊗QCsign⁡L⊗CTQyt-∑i=1mσiζi-ζ~i2=ϵtTL⊗QCζsign⁡L⊗CTQϵt-a∑i=1mCTQ∑j∈Niϵit-ϵjt1,-∑i=1mσiζi-ζ~i2.From (37), (38), and (40), we have (41)V˙t≤ϵtTIm⊗QB+BTQϵt+η-a∑i=1m∑j∈NiCTQϵit-ϵjt1-∑i=1mσiζi-ζ~i2,Choose a>η, we get(42)V˙t≤ϵtTIm⊗QB+BTQϵtThus, similar to the proof of Theorem 7, the nosed-based algorithm (29) can solve the problem (29).Remark 10.
It is easy to see that the node-based algorithm is very different from the edge-based algorithm. The advantage is that the nosed-based algorithm has a less computation and more concise form than the edge-based algorithm. The disadvantage is that the nosed-based algorithm converges more slowly than the edge-based algorithm.Remark 11.
Based on the edge and node standpoints, two adaptive algorithms have been established for solving the distributed convex optimization problems; the algorithms are fully distributed without depending on any global information; that is, the adaptive algorithms can get the optimal solution via local information. Moreover, the connectivity of the networks takes a key role in the rate of convergence of the algorithms during the calculation process.


## 6. Simulations

Consider the following distributed optimization:(43)min∑i=16hiyisubjecttoyi=yj∈R2,i,j=1,…,6,where (44)hiyi=yi1yi2ψiT1-20-26-20-23yi1yi2ψi,ψi=i/2, i=1,2,…,6. Figure 1 is the communication topology. Choose(45)K=-100-12,thus,B=-121-3,C=01.Simulation results employing edge-based algorithm (5) and node-based algorithm (29) are presented in Figures 2–4 and Figures 5–7, respectively. In Figures 2 and 5, it can be observed that the states of consensus are achieved. In Figures 3 and 6, the adaptive control gains first increase, then decrease, and finally converge to some constants, which is consistent with our theoretical analysis in Remark 8. In Figures 4 and 7, the evolution of ∑i=16hi(yi) is presented, which reaches the optimal value 31.5.Figure 1
The communication topology for the distributed optimization.Figure 2
The state variablesy(t) under the edge-based algorithm.Figure 3
The adaptive law under the edge-based algorithm.Figure 4
The global cost function under the edge-based algorithm.Figure 5
The state variablesy(t) under the node-based algorithm.Figure 6
The adaptive law under the node-based algorithm.Figure 7
The global cost function under the node-based algorithm.


## 7. Conclusion

In this paper, two distributed adaptive algorithms to solve the distributed convex optimization problems are designed based on general linear multiagent systems from the edge-based and node-based standpoint. Compared with the existing algorithms, through introducing a damping term in the update law, the algorithms are robust in the face of input disturbances. In this paper, the multiagent networks are undirected graph. Next, we will focus on the case that the multiagent networks are directed graph.



---

*Source: 9181093-2019-08-01.xml*