Locality in Network Optimization

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

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.