Continuous-time distributed optimization and tradeoffs of optimality and heterogeneity

连续时间分布式优化以及最优性和异质性的权衡

• 批准号: RGPIN-2014-05387
• 负责人: Gharesifard, Bahman
• 金额: $ 2.19万
• 依托单位: Queen's University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=567137
• 关键词: Continuous; time; distributed; optimization; tradeoffs

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.

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