Algorithm Design Of Distributed Optimization And Games Under Time-varying Digraphs

As the product of artificial intelligence and information age,multi-agent systems have received increasing attention of many researchers from control,computer,mathematics,physics,economics,social science and other disciplines.Distributed optimization and noncooperative games,as two important research topics in the field of coordination control for multi-agent systems,has been paid great attention in recent years because of its wide applications in power networks,sensor networks,transportation networks,communication networks,social networks and many other fields.In this thesis,based on the multi-agent systems,the distributed optimization and noncooperative games are studied by making comprehensive use of modern control theory,optimization theory,game theory,graph theory and Lyapunov stability theory.The main contributions of this thesis are presented as follows:(1)The distributed optimization problem is investigated by employing a continuous-time multi-agent system.The objective of agents is to cooperatively minimize the sum of local objective functions subject to a convex set.Unlike most of the existing works on distributed convex optimization,here we consider the case where the objective function is pseudoconvex.In order to solve this problem,we propose a continuous-time distributed project gradient algorithm.When running the presented algorithm,each agent uses only its own objective function,its own state information and the relative state information between itself and its neighbors to update its state value.The communication topology is represented by a time-varying digraph.Under mild assumptions on the graph and the objective functions,it shows that the multi-agent system asymptotically reaches consensus and the consensus state is the solution to the optimization problem.Two simulations are carried out to verify the correctness of our theoretical achievements.(2)We study the problem of online distributed seeking for Nash equilibria of noncooperative games with multiple clusters in dynamic environments.In this game,each cluster is composed of multiple players,whose goals are to cooperatively minimize the time-varying cost functions of their own cluster.Each player can only have access to its own cost function and action set,and can only communicate with its immediate neighbors in the same cluster through a time-varying digraph.Moreover,cost functions cannot be known by players in advance.Unlike existing studies on noncooperative games,the cost functions considered here are nonconvex.To address this challenge,an online distributed dual averaging algorithm is proposed.Interestingly enough,the performance of the algorithm is measured by regrets involving the first-order Nash equilibrium condition,and the sublinearity of the regrets is achieved under the proposed algorithm.The validity of the results is illustrated by a numerical example.(3)The problem of distributed resource allocation with coupled equality,nonlinear inequality and convex set constraints is studied.Each agent only has access to the information associated with its own cost function,inequality constraints,convex set constraint,and a local block of the coupled equality constraints.To address such problem,a new distributed primal-dual algorithm is proposed for a continuoustime multi-agent system under a time-varying graph.In the proposed algorithm,two consensus strategies are employed.One is used to estimate the coupled equality constraint function,and the other one is used to estimate corresponding optimal dual variable.Furthermore,a novel Lyapunov function is constructed based on a strongly convex function to analyze convergence of the algorithm.The results show that if the time-varying graph is balanced and the union in a certain period is strongly connected,the algorithm asymptotically converges,and the convergence state is the solution to the distributed resource allocation problem.A simulation example is worked out to demonstrate the effectiveness of our theoretical results.