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.