Xinghu WANG,Peng YI,Yiguang HONG

Key Laboratory of Systems and Control,Institute of Systems Science,Chinese Academy of Sciences,Beijing 100190,China

Dynamic optimization for multi-agent systems with external disturbances

Xinghu WANG?,Peng YI,Yiguang HONG

Key Laboratory of Systems and Control,Institute of Systems Science,Chinese Academy of Sciences,Beijing 100190,China

This paper studies the dynamic optimization problem for multi-agent systems in the presence of external disturbances.Different from the existing distributed optimization results,we formulate an optimization problem of continuous-time multi-agent systems with time-varying disturbance generated by an exosystem.Based on internal model and Lyapunov-based method,a distributed design is proposed to achieve the optimization.Finally,an example is given to illustrate the proposed optimization design.

Distributed optimization;Multi-agent systems;Disturbance rejection;Internal model

1 Introduction

The coordination of multi-agent systems has been studied increasingly with many significant results on consensus and formation for the past decade.In recent years,distributed optimization has attracted much attention to seek an optimal solution for multi-agent systems[1,2].Although most results on distributed optimization were based on discrete-time models,one of emerging topics on distributed optimization is how to design continuous-time systems to achieve the optimization[3-5].The convergence analysis was provided for a continuous-time algorithm with fixed undirected graph in[4],while a continuous-time dynamics was proposed for optimal computation of convex intersection with uniformly jointly strongly connected communication graph in[3].Moreover,a continuous-time system for the positive constrained optimization problem was investigated in[5],and a continuous optimization problem was studied with discrete-time communication in[6].The results show the advantages to employ continuous-time models for optimization:i)It is easy to study the case when practical systems such as robots are the agents to search the optimal solution in real time.ii)Many advanced control techniques can be usedto facilitate the analysis of convergence rate and disturbance rejection,and moreover,overcome the diminishing step-size problem in discrete-time algorithm.

In fact,more and more attention has been paid to multi-agent systems with disturbances.In reality,agents have to face various(environmental)disturbances.One of the effective methods was developed based on internal model principle from the viewpoint of output regulation[7].Also,distributed output regulation was studied[8-10]for multi-agent systems to track an active leader and/or reject a modeled disturbance.

The objective of this paper is to study the distributed optimization of continuous-time multi-agent systems with rejecting external disturbances.The motivation is as follows:i)the considered agents need to be equipped with disturbance rejection control scheme when they achieve their optimization in a region with disturbance;ii)the research is a combination of the new results of distributed optimization and distributed output regulation,which may provide a unified way to treat consensus,disturbance rejection,and distributed optimization in some sense.The contribution of the paper can be summarized as follows:

?We first give a problem formulation for the distributed optimization with rejecting the external disturbances during the optimization process;

?We employ the internal model technique to provide effective distributed protocol to achieve the exact optimization in the presence of external disturbances.

This paper is organized as follows.In Section 2,we formulate the dynamic optimization problem with rejecting external disturbances.Then,in Section 3,we present the main result of the paper,along with an illustrative example.In Section 4,some concluding remarks are given.

2 Preliminaries and formulation

In this section,we recall some preliminaries of graph theory and convex optimization,and then formulate our problem.

DenoteInas thenXnidentity matrix,1Nas the vector ofNentries equal to 1,and?as the matrix Kronecker product.Rndenotesn-dimensional Euclidean space.Moreover,for vectorsx1,...,xm,denote

Let us introduce some concepts related to convex functions[11].A differentiable functionf:Rn→R is strictly convex ifforx≠y∈Rn,andfis am-strongly convex(m>0)ifforA functiong:Rn→Rnis Lipschitz with constantM>0,or simplyM-Lipschitz if

Graph theory has been widely used for multi-agent control[12].A weighted digraph is described by a triplet G={V,?,A}where V={1,2,...,N}is the node set,??VXV is the edge set(without self-loops),andis the weighted adjacency matrix ofNXN.An edge of G is denoted by an ordered pair of nodes(j,i)∈? withjbeing a neighbor ofi.A directed path of G is an ordered sequence of distinct nodes in V such that any consecutive nodes in the sequence correspond to an edge of G.G is called strongly connected if there exists a directed path fromitojfor any two nodesi,j∈V.A is a nonnegative matrix withaij>0 if(j,i)∈ ?,i,j∈ V.The weighted in-degree and weighted out-degree of a nodeiare defined bydigraph is weight-balanced if for each nodei,The Laplacian matrix is L=D-A withNote that L1N=0.A digraph is weight-balanced if and only if

It is time to formulate our problem.Consider a network ofNagents with interaction topology described by a digraph G.Agentiis endowed with a local cost functionfi:Rn→R and a dynamics

wherexi∈Rnis its state,uiis its optimization protocol,anddi(t)is the local disturbance governed by the following exosystem:

whereis the exosystem state.It is assumed that all eigenvalues ofS∈RpXpare distinct lying on the imaginary axis,which means the boundedness of the disturbances.

The global cost functionf:Rn→R is defined as a sum of the local cost functions as usual[1]:

The aim of this paper is to design a protocoluiof the following form:

whereis the gradient information of agenti,andis the exchanged information with its neighbors,such that the multi-agent system(10)with(3)solves the following optimization problem

by drivingxitox?.

Remark 1The above problem can be referred to as the dynamic optimization problem with external disturbances in order to achieve the exact optimization in a distributed way.When the disturbances disappear,the problem discussed in this paper becomes the traditional distributed optimization problem in the continuous-time setup(referring to[3,4]).On the other hand,if we do not assign the cost functions to the agent network,the consensus problem with external disturbances can be solved with the help of distributed output regulation[8-10].Therefore,this problem provides a general framework somehow for the distributed optimization and distributed output regulation.

To proceed further,we introduce two basic conditions for the solvability of the problem,which was also used in[6].

Condition 1The digraph G is strongly connected and weight-balanced.

Remark 2Define

Under Condition 1,it is known[12]that 0 is the single eigenvalue of matrices L and Sym(L).Moreover,there is a matrixR∈RNX(N-1)withsuch that

for a positive real number λ0.

Condition 2Fori=1,...,N,the local cost functionfiismi-strongly convex and differentiable,and its gradient isMi-Lipschitz on Rn.DenotemT=min{m1,...,mN}andMT=max{M1,...,MN}.

3 Main result

In this section,we propose a distributed optimization design to achieve the exact optimization with disturbance rejection.Three subsections are given for the algorithm design,optimization analysis,and simulation.

3.1 Algorithm design

Due to the disturbancedi(t),existing results on distributed optimization are not applicable.To deal with the problem,we first make some transformation.Letbe the minimal polynomial ofSand τi=(τi1,...,τin)with

Define two matrices

By a direct computation,it can be seen that τijsatisfies

which implies

Since the pair(Ψ,Φ)is observable,there exists a matrixGsuch thatF=Φ+GΨ is Hurwitz.Thus,for agenti,an internal-model-based optimization protocol can be constructed as

Obviously,the proposed optimization protocol consists of three terms:the gradient-based optimization term to drive the agents to the optimization point,the consensus term for all agents to achieve the same point,and the internal model term to compensate the disturbancedi(t)asymptotically(referring to Chapter 6 of[7]for more details on internal model design).

for initial conditionsvi(0)∈Rnwith

The above observation is useful in analysis of the equilibrium point.Therefore,in this paper,we always set the initial conditionsvi(0)satisfying(9)by simply takingvi(0)=0 fori=1,...,N.

By addinguito the dynamics(1),we obtain the following closed-loop system:

To compensate the disturbances asymptotically,the termmust vanish asymptotically.Performing a transformationgives

Then,system(10)with the last equation replaced by(11)can be rewritten in the following compact form:

Remark 4Suppose that system(12)has an equilibrium point at(xo,vo,ˉηo).Then,(xo,vo,ˉηo)satisfies

3.2 Optimization analysis

Here,we prove the convergence of the proposed optimization design based on Lyapunov function.

To this end,we first define the following variables to obtain a standard stability problem:

In the new coordinate,

where

It is time to show our main result.

Theorem 1Under Conditions 1 and 2,there exist two constants α and β >0 such that algorithm(7)solves the distributed optimization problem in the presence of the disturbances.

ProofRecalling Remark 4,to obtain the conclusion,it is sufficient to show that there are two constantsα,β >0 such that the equilibrium pointof system(15)is exponentially stable.

For this purpose,we first perform the following transformation to simplify system(15)

whereTis defined by

withRspecified in Remark 2.Denote χ =(χ1,χ2:N),? =(?1,?2:N),where χ1,?1∈ Rnand χ2:N,?2:N∈ R(N-1)n.Then,from(15),we have

Similar to[6],we take the following Lyapunov function candidate:

with γ>0 to be determined.It can be verified that

Under Condition 2,we obtain

for a positive real number?0.

Take the following Lyapunov function candidate for the whole system

Then,we have

Taking α and β satisfying

gives

By Theorem 4.10 of[13],

Remark 5Note that the constructed Lyapunov functionVin(21)is independent of the interaction digraph.Hence,following a similar proof as in Theorem 1,the above result can be extended to switching case when the switching digraph G keeps strongly connected and weighted-balanced,with its adjacency matrix A piecewise constant between switchings.

3.3 Example

It is easy to see that the local cost functionfiismistrongly convex and its gradient isMi-Lipschitz on R with real numbersmi,Mi>0 fori=1,...,5,which implies Condition 2.The network topology is shown in Fig.1.We set all edge weights to be 1,which verifies Condition 1.The disturbance in agent dynamics is given bywhich can be generated by system(2)with

Fig.1 Interaction topology for the network.

Here,we set ω=1.Then,system(5)is given with

Figs.2 and 3 show that the state of each agent converges to the exact optimization pointx?=0.49.Moreover,a larger value of β results in faster convergence,which is consistent with the disturbance-free case discussed in[6].

Fig.2 Performance of(7)with α =1,β =1.

Fig.3 Performance of(7)with α =1,β =5.

4 Conclusions

The dynamic optimization problem with external disturbances has been studied in this paper.First,a new problem formulation was given to achieve the distributed optimization with disturbance rejection.Then,an internal-model-based algorithm was proposed to solve the problem.To our knowledge,this is the first effort to study the distributed optimization with external disturbance signals,and more complicated problems are still under investigation.

[1]A.Nedic,A.Ozdaglar.Distributed subgradient methods for multi-agent optimization.IEEE Transactions on Automatic Control,2009,54(1):48-61.

[2]Y.Lou,G.Shi,K.H.Johansson,et al.Reaching optimal consensus for multi-agent systems based on approximate projection.Proceedings of the 10th World Congress on Intelligent Control and Automation.Beijing:IEEE,2012:2794-2800.

[3]G.Shi,K.H.Johansson,Y.Hong.Reaching an optimal consensus:dynamical systems that compute intersections of convex sets.IEEE Transactions on Automatic Control,2013,58(3):610-622.

[4]J.Wang,N.Elia.A control perspective for centralized and distributed convex optimization.Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference.Orlando:IEEE,2011:3800-3805.

[5]K.Kvaternik,L.Pavel.A continuous-time decentralized optimization scheme with positivity constraints.Proceedings of the 51st IEEE Conference on Decision and Control,Maui:IEEE,2012:6801-6807.

[6]S.Kia,J.Cort'es,S.Mart'?nez.Distributed convex optimization via continuous-time coordinate alorithms with discrete-time communication.arXiv:1401.4432.2014:http://arxiv.org/pdf/1401.4432v2.pdf.

[7]J.Huang.Nonlinear Output Regulation:Theory and Applications.Philadelphia:SIAM,2004.

[8]Y.Hong,X.Wang,Z.Jiang.Distributed output regulation of leader-follower multi-agent systems.International Journal of Robust and Nonlinear Control,2013,23(1):48-66.

[9]X.Wang,Y.Hong,J.Huang,et al.A distributed control approach to a robust output regulation problem for multi-agent linear systems.IEEE Transactions on Automatic Control,2010,55(12):2891-2895.

[10]Y.Su,Y.Hong,J.Huang.A general result on the robust cooperative output regulation for linear uncertain multi-agent systems.IEEE Transactions on Automatic Control,2013,58(5):1275-1280.

[11]R.T.Rockafellar.Convex Analysis.Princeton:Princeton University Press,1972.

[12]C.Godsil,G.Royle.Algebraic Graph Theory.New York:Springer-Verlag,2001.

[13]H.K.Khalil.Nonlinear Systems.3rd ed.Upper Saddle River:Prentice Hall,2002.

18 March 2014;revised 28 March 2014;accepted 28 March 2014

DOI10.1007/s11768-014-0036-y

?Corresponding author.

E-mail:wxh@amss.ac.cn.Tel.:+86-10-62651449;fax:+86-10-62587343.

This work was supported by the National Natural Science Foundation of China(Nos.61174071,61333001).

?2014 South China University of Technology,Academy of Mathematics and Systems Science,CAS,and Springer-Verlag Berlin Heidelberg

Xinghu WANGreceived his B.S.and Ph.D.degrees from Shandong University,Weihai,and University of Science and Technology of China in 2007 and 2012,respectively.He is currently a postdoctoral fellow in Academy of Mathematics and Systems Science,Chinese Academy of Sciences.His research interests include nonlinear dynamics and control and multi-agent systems.E-mail:wxh@amss.ac.cn.

Peng YIreceived his B.S.degree from University of Science and Technology of China in 2011.He is currently a Ph.D.candidate in Academy of Mathematics and Systems Science,Chinese Academy of Sciences.His research interests include distribute optimization and multi-agent systems.E-mail:yipeng@amss.ac.cn.

Yiguang HONGreceived his B.S.and M.S.degrees from Department of Mechanics,Peking University,China,and Ph.D.degree from Chinese Academy of Sciences(CAS).He is currently a professor in Academy of Mathematics and Systems Science,CAS.His research interests include nonlinear dynamics and control,multi-agent systems,distributed optimization,and reliability of software and communication systems.E-mail:yghong@iss.ac.cn.