Distributed optimization of multi-agent with communication delay and directed network

YANG Zheng-quanPAN Xiao-fangZHANG QingCHEN Zeng-qiang

(1.Airport Comprehensive Transportation Research Institute,Civil Aviation University of China,Tianjin 300300,China;2.College of Science,Civil Aviation University of China,Tianjin 300300,China;3.College of Artificial Intelligence,Nankai University of China,Tianjin 300350,China)

Abstract:This paper studies the distributed optimization problem for the first-order multi-agent systems in unbalanced directed topology.Each agent has a time delay in the communication process with its neighbors.Our goal is to find a state of the agent that minimizes the objective function f(x) A controller based on the left eigenvector corresponding to the zero eigenvalue of L of the graph G and the local information of each agent is proposed.In this study,the bounded requirement of the gradient of fi(xi)is removed,and it does not require the network to be balanced.Under some assumptions,all agents reach the same state while minimizing the objective functionFinally,a numerical simulation illustrates the results of this article.

Key words:communication delay;multi-agent systems;distributed optimization;unbalanced directed network

1 Introduction

More and more scientists in the control field have studied the distributed optimization of multi-agent systems[1–9].The purpose of the optimization is to make these agents reach a common state by using neighbor information,and the common state is the optimal solution of a functionf(x),where the functionf(x) is a sum of the functionfi(xi).In other words,it focuses on guiding all agents to cooperatively solve the global optimization problem.Distributed optimization is widely used in industry,technology,economic,and social fields,such as machine learning,smart grid,resource allocation,etc.[10–13].

In the past,consensus is a fundamental and meaningful research topic in the field of control,which focuses on designing appropriate controllers to make multiple agents reach a common state[14–17].Furthermore,a large number of distributed optimization control strategies based on consensus have been obtained and analyzed.For example,a method based on consensus is proposed to compute the intersection of convex sets in [2].Ning et al.[4]studied the optimization strategy of multiple agents based on the fixed-time consensus method in a distributed manner.In some practical systems,the algorithm for optimizing the systems has been studied in different ways such as sub-gradient,gradient and zero-gradient sum[1–9].For continuous time dynamic systems,Nedic et al.[5]and Gharesifard et al.[6]developed a new control framework to handle the optimization problem of the multi-agent systems.In some weight-balanced directed topological networks,Kia et al.[7]designed a continuous-time consensus control law to handle the optimization problem with discrete communication in a distributed way.

In reality,in the process of information transmission,the communication delay between agents is inevitable,especially when the number of agents is large.In order to solve this problem,some distributed optimization schemes with communication delay are proposed in [18–25].For example,in [18–20],some consensus-based methods are developed to deal with the optimization in presence of communication delay.In some practical applications,Chen et al.[21]and Yang et al.[22]proposed the economic dispatch schemes with delay effect,and these methods solve the economic dispatch problem on time-varying digraphs.Moreover,focus on a system composed of multiple agents with constraint sets and delays,a distributed method was proposed to do with optimization problems on weightbalance directed graphs in [23].Guo et al.[24]further proposed the algorithms based on zero-gradient-sum approach to successfully deal with distributed optimization problems under fixed and time-varying delays respectively,and gave the upper bounds of their delays.Delays can be arbitrary,time-varying but bounded.

The actual network environment is changeable and complex,and the communication between nodes is directed and asymmetric.Accordingly,unbalanced directed network is more challenging than the weightbalanced case and undirected case.It is meaningful to handle distributed optimization problem of multi-agent systems with communication delays in unbalanced directed networks.To achieve this,three challenges will be faced.Firstly,the stability analysis is usually complex when the network is directed.Secondly,the analysis is more difficult to overcome the unbalance of the network.Thirdly,once the communication delay is introduced,the analysis becomes much more complex.Most of the existing work has solved the optimization of a system composed of multiple agents with communication delays in a distributed manner,but they are only aimed at undirected and weight-balanced networks.

This paper proposes a new distributed optimization controller which not only has communication delay but also has unbalanced directed topology.Compared with the existing relevant results,the contributions of this note are summarized as follows.Compared with the distributed controller without the communication delay[1–9],this paper considers the multi-agent with communication delay,and removes the bounded requirement of the gradient offi(xi).Compared with[24],the optimization problem under directed topology is studied.Compared with [18–24],the communication delay is time varying,the bounded requirement of the gradient offi(xi) is removed,and it does not require the network to be balanced.In conclusion,compared with previous research results,the main innovations of this study are as follows.Firstly,the controller has varying time communication delay.Secondly,the network topology is directed and unbalance.Thirdly,the controller relaxes the assumption of the local functionfi(xi).

The basic structure of this article is as follows.In Sec.2,we introduce the basic principles and the statement of graph theory.In Sec.3,the theoretical results of this study are given.In Sec.4,we present a simulation result of this research.In Sec.5,we give the conclusion of this article.

2 Notations and Preliminaries

In this section,we give some concepts used in this article.Let R be the sets of real numbers,Rmrepresents the column vector ofm-dimensional,1N ∈RNrepresents the column vector of N-dimensional whose element is 1,Rn×mis the matrix of sizen×m,PX(s)denotes the projection of the vectorsonto the closed convex setX,i.e.,PX(s)x −s‖.If a functionf(s):Rm →R satisfies:f(bs1+(1−b)s2)≤bf(s1)+(1−b)f(s2),∀s1,s2∈Rm,b ∈(0,1),f(s)is convex function.∇f(x)is the partial derivative off(x).τ(t)is a function of communication delay and arbitrary.

In this paper,we regard the information communication between multi-agents as a directed graphG.The directed graphGis considered with the node setV{1,2,...,N},the edge setEand the adjacency matrixA[aij]∈RN×N.If there is communication from agentjto agenti,(j,i)∈E.The adjacency matrixA[aij]∈RN×Nof the graphGis defined as 1)aii0;2)aji1 if (i,j)∈E;3)aji0 if(i,j)/∈E.Furthermore,L[lij]N×Nis called the Laplacian matrix of the graphGwhich is denoted aslij−aij,ifij,otherwise

The eigenvalues ofLis need to satisfy 0λ1(L)≤λ2(L)≤···≤λN(L),and the eigenvalues ofLTLis need to satisfy 0λ1(LTL) ≤λ2(LTL) ≤···≤λN(LTL).P[p1p2··· pN]Tis the left eigenvector corresponding to the zero eigenvalue ofL,which satisfiesPTL0;pirepresents theith element of thePvector,diag{p1,p2,···,pN}is a diagonal matrix withp1,p2,···,pNas the elements on the diagonal.liirepresents the out-degree of agentiandrepresents the in-degree of agenti.IfGis a balanced graph,otherwiseGis an unbalanced graph.The graphGcontaining at least one spanning tree is connected.If there is always a path between any two nodes in graphG,then the graphGis strongly connected.

On those topics,we study a system of multiple agents composed of N agents(indexed by 1,2,···,N).The dynamic description of each agent in the system is as follows

wherexi(t)∈Rn,ui(t)∈Rnrepresent the state and the controller of agentirespectively.

Our goal is to design a controller for the system(1)so that each agent can track a common state and optimize the global objective function.In other words,this problem can be expressed as

wherexi(t)∈Rnis the state vector of the agenti,fi(xi) :Rn →R represents the local objective function of the agenti.

In order to solve the above-mentioned distributed optimization problem,the following lemmas and assumptions are needed.

Lemma1[26]Given a positive matrixϕ ∈RN×N,∀a ∈RN,b ∈RN,it has that

In particular,whenϕ ∈RN×Nis an identity matrix,2ab≤aTa+bTb.

Lemma 2[27]LetDbe a symmetric matrix,it is represented as

Lemma 4[29]The continuously convex and differentiable functionf(s)is minimized iff∇f(s)0.

Lemma 5LetXbe a convex and closed set andfi(s)is a convex function,from the convexity offi(s),the following inequality hold

wherex ∈Rnandy ∈X.

Assumption 1Letτ(t) be a continuously differentiable function,and it satisfies 0 ≤τ(t) ≤dand ˙τ(t)≤h≤1.

Assumption 2The graphGis a connected and unbalanced directed graph.

Assumption 4LetX{s2∈Rn|0}be a closed convex and nonempty set.

Assumption 5In this paper,α(t)is need to satisfy the following conditions:

It follows from Lemma 2 that (7) is equivalent to the following inequality:

From Lemma 2,it is clear that the above formula holds.

Remark 1In this study,the communication delay is considered.Compared with[18–24],the bounded requirement of the gradient offi(xi(t))is removed,and it does not require the network to be balanced.

You want to get rid of your fish’s tail, and to have two supports instead of it, like human beings on earth, so that the young prince may fall in love with you, and that you may have an immortal soul

3 Main results

In this section,we design a novel optimization controller to make all agents realize consensus and minimize the global objective functions.The controller has two parts.The first part is the summation function,which is used to achieve consistency.The second part is the sub-gradient to achieve global optimization.The distributed controller is given by:

whereτ(t) is the time-varying communication delay;xi(t −τ(t))∈Rnrepresents the state vector of the agentiat timet −τ(t);α(t) is a function that is required to meet Assumption 6;∇fi(xi) is the gradient offi(xi);p[p1p2··· pN]TsatisfiespTL0 andpT1N1;piis theith element of thep.Thepiin the controller is to eliminate imbalance of graphG.

Then,according topTL0 andpTL1,from (1)and(8),we have

the equation of(9)can be written as

Below,we will give the main theorem and prove it.

Theorem 1If Assumption 1–5 are satisfied,the control law(8)solve the optimization problem(2)in a distributed way.

ProofFirstly,in order to prove that each agent asymptotically reaches the same state,a Lyapunov-Krasovskii functional is selected.

where the positive definite functionsV1(t),V2(t),V3(t)are defined as

whereτ(t) is a function of communication delay and arbitrary and satisfies 0 ≤τ(t) ≤d;dis the upper bound ofτ(t);˙τ(t) is the derivative ofτ(t) and satisfies ˙τ(t) ≤h≤1;Λis a diagonal matrix,andΛdiag{p1,p2,···,pN}.

The derivatives ofV1(t),V2(t)andV3(t)along the system(1)are given by

Next,we will prove that this state is the optimal state such that minimizesf(x).

Construct a positive condition function as follows

The time derivative ofW(t)is

4 Numerical simulations and application

Obviously,each local objective function is continuously convex and differentiable.Therefore,the objective functionf(x)is also continuously convex and differentiable,and the optimal solution is unique.According to Lemma 4 and by using simple calculations,we can get the optimal valuex∗that minimizes the global objective function.Figure 1 shows the motion trajectories of 8 agents under the action of the controller (1).It is clear to see that 8 agents tend to the same position and the state of 8 agents converge to the optimal point.

Fig.1 The states of 8 agents

5 Conclusion

We study the optimization problem of a first-order system composed of multiple agents with communication delay and directed topology.The communication network does not require to be balanced.Each agent has states information from its neighborhood.The goal is to find the common state of all agents that minimizes the objective functionf(x).Based on the characteristics ofPand the local communication of neighborhood,we propose a controller to do with the optimization problem.Under Assumptions 1–5 and from the convexity offi(xi),all agents reach consensus while minimizing the functionf(x).Finally,a simulation is given to illustrate the theoretical results of this article.

References:

[1] NEDI´C A,OZDAGLAR A.Distributed sub-gradient methods for multi-agent optimization.IEEE Transactions on Automatic Control,2009,54(1):48–61.

[2] SHI G,JOHANSSON K H,HONG Y.Reaching an optimal consensus:Dynamical systems that compute intersections of convex sets.IEEE Transactions on Automatic Control,2013,58(3):610–622.

[3] LU J,TANG C Y.Zero-gradient-sum algorithms for distributed convex optimization:the continuous-time case.IEEE Transactions on Automatic Control,2012,57(9):2348–2354.

[4] NING B,HAN L,ZUO Z.Distributed optimization for multiagent systems:an edge-based fixed-time consensus approach.IEEE Transactions on Cybernetics,2019,49(1):122–132.

[5] NEDI´C A,OZDAGLAR A.Distributed optimization over timevarying directed graphs.IEEE Transactions on Automatic Control,2015,60(3):601–615.

[6] GHARESIFARD B,CORT´ES J.Distributed continuous-time convex optimization on weight-balanced digraphs.IEEE Transactions on Automatic Control,2014,59(3):781–786.

[7] KIA S,CORT´ES J.Distributed convex optimization via continuoustime coordination algorithms with discrete-time communication.Automatica,2015,55(5):254–264.

[8] LIN P,REN W,FARRELL A.Distributed continuous-time optimization:nonuniform gradient gains,finite-time convergence,and convex constraint set.IEEE Transactions on Automatic Control,2016,62(5):2239–2253.

[9] CHEN W,REN W.Event-triggered zero-gradient-sum distributed consensus optimization over directed networks.Automatica,2016,65:90–97.

[10] DENG Z,LIANG S,HONG Y.Distributed continuous-time algorithms for resource allocation problems over weight-balanced digraphs.IEEE Transactions on Cybernetics,2018,48(11):3116–3125.

[11] LIN P,REN W,SONG Y.Distributed multi-agent optimization subject to nonidentical constraints and communication delays.Automatica,2016,65:120–131.

[12] QIU Z,XIE L,HONG Y.Distributed optimal consensus of multiple double integrators under bounded velocity and acceleration.Control Theory and Technology,2019,17(1):85–98.

[13] CHEN F,REN W.Sign projected gradient flow:a continuous-time approach to convex optimization with linear equality constraints.Automatica,2020,120:109156.

[14] DING L,HAN Q L,X GE,et al.An overview of recent advances in event-triggered consensus of multiagent systems.IEEE Transactions on Cybernetics,2018,48(4):1110–1123.

[15] HOU W,FU M,ZHANG H,et al.Consensus conditions for general second-order multi-agent systems with communication delay.Automatica,2017,75:293–298.

[16] ZHU W,JIANG Z-P.Event-based leader-following consensus of multi-agent systems with input time dela.IEEE Transactions on Automatic Control,2015,60(5):1362–1367.

[17] MA D,TIAN R,ZULFIQAR,et al.Bounds on delay consensus margin of second-order multi-agent systems with robust position and velocity feedback protocol.IEEE Transactions on Automatic Control,2019,64(9):3780–3787.

[18] WANG H,LIAO X,HUANG T,et al.Cooperative distributed optimization in multi-agent networks with delays.IEEE Transactions on Systems,Man and Cybernetics,2015,45(2):363–369.

[19] TSIANOS K I,RABBAT M G.Distributed dual averaging for convex optimization under communication delays.American Control Conference.Montreal:IEEE,2012:1067–1072.

[20] YANG S,LIU Q,J WANG.Distributed optimization based on a multiagent system in the presence of communication delays.IEEE Transactions on Systems,Man and Cybernetics,2017,47(5):717–728.

[21] CHEN G,ZHAO Z.Delay effects on consensus-based distributed economic dispatch algorithm in microgrid.IEEE Transactions on Power Systems,2018,33(1):602–612.

[22] YANG T,LU J,WU D,et al.A distributed algorithm for economic dispatch over time-varying directed networks with delays.IEEE Transactions on Industrial Electronics,2017,64(6):5095–5106.

[23] WANG D,WANG Z,CHEN M,et al.Distributed optimization for multi-agent systems with constraints set and communication timedelay over a directed graph.Information Sciences,2018,438:1–14.

[24] GUO Z,CHEN G.Distributed zero-gradient-sum algorithm for convex optimization with time-varying communication delays and switching networks.International Journal of Robust and Nonlinear Control,2018,28:4900–4915.

[25] YANG Z,ZHANG Q,CHEN Z.Adaptive distributed convex optimization for multi-agent and its application in flocking behavior.Journal of the Franklin Institute,2018,356:1038–1050.

[26] MOON Y S,PARK P,KWON W H,et al.Delay dependent robust stabilization of uncertain state-delayed systems.International Journal of Control,2010,74(14):1447–1455.

[27] HORN R A,JOHSON C R.Matrix Analysis.Cambridge,UK:Cambridge University Press,1985.

[28] LI Z,DUAN Z.Cooperative Control of Multi-Agent Systems:A Consensus Region Approach.New York:CRC Press,2014.

[29] BOYD S,VANDENBERGHE L.Convex Optimization.New York,NY:Cambridge University Press,2004.