Continuous-time distributed optimization and tradeoffs of optimality and heterogeneity

点击翻译按钮获取中文摘要

This research program will further contribute to the understanding of the underpinnings of collective behavior and information aggregation in (sub)systems interconnected over large-scale networks by developing mathematical tools for analyzing their stability properties and influencing their behaviors by feedbacks. These phenomena are widespread in a variety of disciplines including engineering systems (e.g., oscillator synchronization, distributed robotic networks, and distributed sensing and control in electrical energy systems), biological systems, and social learning and economics. The diverse nature of interconnections in these systems usually makes it difficult to classify them in any useful manner. One approach is to prescribe the behavior of each individual by using a payoff function which is dependent on the actions taken by neighboring subsystems. Each subsystem then aims to maximize its payoff function. In most engineering scenarios, there is a designer whose objective is to assign appropriate such functions to ensure certain global performances, while still allowing for execution in a decentralized manner.In the first part of the research program, we focus on the so-called distributed optimization problem, where a group of agents aim to maximize a sum of (concave) functions, while each agent has only access to one of these functions. We propose a catalog of provably convergent continuous-time saddle point algorithms for distributed optimization. The novelty of the approach is in its applicability to scenarios where the information flow is unidirectional. Various properties of these algorithms, including robustness and finite-time convergence, will be the subjects of study. Current applications under study include source localization, robust estimation, market design and energy dispatch in power distribution networks, influence-cascade dynamics in competitive economic networks, optimization on manifolds, and online distributed optimization. In the second part, we turn our attention to the issue of scalability of the existing distributed optimization protocols. In particular, most of the existing algorithms rely on estimating the optimal solution using communications between agents. When the optimization variable is the state of a network, such algorithms do not scale well with the size of the network. In order to address this issue, building on the intriguing interplay between the theory of learning in games and systems and control, this research program will propose a catalog of dynamical systems which will capture various instances of strategic interactions over networks. Interestingly, the proposed suite of dynamical systems, inspired by myopic continuous-time set-valued best-response dynamical systems, can be cast as fast converging distributed algorithms which approximate interesting optimization problems. The novel notion of the price of heterogeneity captures the quality of these approximations. The research program is multidisciplinary by its nature and the technical approach combines ideas from optimization, game theory, networks and communications, nonsmooth analysis, stochastic analysis, and control theoretic tools. The broader impacts of the research program on problems in economy, social networks, and biology, along with the algorithmic aspects of this research project will provide a variety of applications with considerable scientific significance, and will be of great interest to various governmental labs, including Environment Canada and National Defence. In addition to promising M.Sc. and Ph.D. theses, the educational component of the project consists of establishing a new research group on Networked Control Systems at Queen's and the design of new undergraduate and graduate courses.