Locality in Network Optimization

网络优化中的局部性

• 批准号: 1609484
• 负责人: Sekhar Tatikonda
• 金额: $ 45万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1609484&HistoricalAwards=false
• 关键词: Locality; Network; Optimization

Many recent problems in control, communication, computation, and machine learning can be posed in the framework of network optimization. Despite the great number of algorithms that have been proposed to address modern large-scale problems there remains a crucial challenge of building computationally efficient, accurate, scalable, distributed procedures. A key issue is that of understanding locality. Locality is a structural property of optimization instances that captures the property that information need not propagate across the entire network but only across local portions of it. As a consequence decisions made at a node can be made based only on local information thus reducing both communication requirements and computational complexity. This research involves identifying when locality occurs, designing algorithms that take advantage of locality, and applying these algorithms to variety of applications. The project also provides an opportunity for training graduate students and postdoctoral researchers in the disciplines of optimization, networking, and control.Typically sensitivity results concern the objective function evaluated at the optimal solution not the optimal solution itself. Herein sensitivity is characterized by the change in the optimal solution at a given node given a change in a network parameter at another node. Locality holds when the sensitivity decays with the distance between the two nodes. The main objectives of this research project are: (1) Theoretical Analysis: developing a general theory to characterize the local sensitivity of optimal solutions in a variety of network optimization problems and developing analytic tools to quantify the rate at which sensitivity decays with distance; (2) Algorithm Development: developing computationally efficient local message-passing algorithms to solve a variety of network optimization problems; and (3) Applications: applying these algorithms to problems in network optimization, distributed computation, and cooperative control.

最近在控制、通信、计算和机器学习方面的许多问题都可以在网络优化的框架中提出。尽管已经提出了大量的算法来解决现代大规模的问题，但仍然存在一个关键的挑战，即构建计算效率高，准确，可扩展的分布式程序。一个关键问题是理解局部性。局部性是优化实例的一种结构属性，它捕获了信息不需要在整个网络中传播而只需要在局部网络中传播的属性。因此，在节点处做出的决策可以仅基于局部信息，从而降低了通信需求和计算复杂度。 这项研究涉及到确定何时发生局部性，设计算法，利用局部性，并将这些算法应用到各种应用程序。该项目还提供了一个机会，培养研究生和博士后研究人员在学科的优化，网络和控制。通常灵敏度结果关注的目标函数评估的最佳解决方案，而不是最佳解决方案本身。 这里，灵敏度的特征在于给定另一节点处的网络参数的变化的情况下，给定节点处的最优解的变化。 当灵敏度随两个节点之间的距离衰减时，局部性成立。 本研究计画的主要目标为：（1）理论分析：发展一个一般性的理论来描述各种网路最佳化问题中最佳解的局部敏感性，并发展分析工具来量化敏感性随距离衰减的速率;（2）演算法发展：发展计算效率高的局部讯息传递演算法来解决各种网路最佳化问题;（3）应用：将这些算法应用于网络优化、分布式计算和协同控制等问题。