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.