Continuous-time distributed optimization and tradeoffs of optimality and heterogeneity

这一研究计划将通过开发数学工具来分析大规模网络上互联的(子)系统的稳定性并通过反馈影响它们的行为，从而进一步有助于理解集体行为和信息聚集的基础。这些现象广泛存在于各种学科中，包括工程系统(例如，振荡器同步、分布式机器人网络、电力系统中的分布式传感和控制)、生物系统以及社会学习和经济学。这些系统中的互连性质多种多样，通常很难以任何有用的方式对它们进行分类。一种方法是通过使用依赖于相邻子系统所采取的行动的收益函数来规定每个个体的行为。然后，每个子系统的目标是最大化其收益功能。在大多数工程场景中，设计人员的目标是分配适当的此类功能，以确保某些全局性能，同时仍允许以分散的方式执行。 在研究程序的第一部分，我们重点研究所谓的分布式优化问题，其中一组代理的目标是最大化(凹)函数的和，而每个代理只能访问这些函数中的一个。我们提出了一类可证明收敛的分布式优化连续时间鞍点算法。该方法的新奇之处在于它适用于信息流是单向的场景。这些算法的各种性质，包括稳健性和有限时间收敛，将是研究的主题。目前正在研究的应用包括电源定位、稳健估计、配电网中的市场设计和能量调度、竞争性经济网络中的影响-级联动力学、流形上的优化和在线分布式优化。在第二部分中，我们将注意力转向现有分布式优化协议的可扩展性问题。特别是，现有的大多数算法都依赖于使用代理之间的通信来估计最优解。当优化变量是网络的状态时，这样的算法不能很好地随网络的大小而扩展。为了解决这个问题，基于游戏和系统中的学习理论与控制之间有趣的相互作用，该研究计划将提出一个动态系统目录，该目录将捕获网络上战略交互的各种实例。有趣的是，受短视连续时间集值最优响应动力系统的启发，所提出的动力系统套件可以被描述为逼近感兴趣的优化问题的快速收敛的分布式算法。异质性价格这一新颖的概念体现了这些近似的质量。该研究项目的性质是多学科的，技术方法结合了最优化、博弈论、网络和通信、非光滑分析、随机分析和控制理论工具的思想。 该研究计划对经济、社会网络和生物学问题的更广泛影响，以及该研究项目的算法方面，将提供具有相当科学意义的各种应用，并将引起包括加拿大环境部和国防部在内的各种政府实验室的极大兴趣。除了有希望的M.Sc.该项目的教育部分包括在女王学院建立一个新的网络控制系统研究小组，并设计新的本科生和研究生课程。

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.