Semidefinite Programming for Weight Design in Fast Converging Distributed Algorithms

随着集成电路和传感器、无线通信和其他技术的不断扩展，越来越多的计算和通信智能可以内置到嵌入式处理器、传感器和执行器中，以在网络环境中执行协调任务。本文提出了一种分析和设计此类网络中某些迭代分布式算法的新方法。该方法融合了控制系统分析和设计，优化和图论的思想，并基于使用新的优化方法来调整分布式算法的速度和鲁棒性。初步结果表明，该方法（或有待开发的扩展）可以在分布式传感器融合、分布式优化和资源分配、马尔可夫链蒙特卡罗模拟和线性方程的分布式解等多个应用领域产生重大影响。分布式算法设计和分析是一个研究得很好的主题，有文献可以追溯到20世纪70年代（甚至更早），我们将从中汲取。自20世纪70年代（或更早）以来，算法已被提出用于分布式共识平均，优化和资源定位，网络中的路由和拥塞控制，控制（通常是车队）以及传感和估计。虽然算法的细节各不相同，但它们都是局部的（相对于底层图而言），并且通常根据其邻居值的某个函数更新一些变量（或价格，在某些情况下）。这类算法的典型经典结果表明，如果底层通信图是连通的，并且某些更新权值或增益足够小且为正，则算法收敛。底层图的拉普拉斯特征值在收敛性分析中经常起作用。知识价值。PI提出的一般问题是，给定特定的问题类别和底层图，找到产生最快可能收敛（以及可能的其他规范，如鲁棒性或单调收敛）的权重。初步结果表明，分析和最优权值综合可以在线性矩阵不等式和半定规划的框架下进行，因此很容易计算（也以分布式方式），并且最优权值可以给出比经典（未加权）更快的收敛算法。这些初步结果只是触及了这个主题的表面；还有大量的工作要做。通过调整权重可以改进哪些（进一步的）分布式方法？可以处理哪些类型的规范？该方法可以扩展到异步方法吗？该方法能否推广到一般李雅普诺夫函数的收敛分析？这些算法的鲁棒性如何？如何有效地计算最优权重？能否以分布式方式计算最优权重？PI将在提议的研究计划中考虑这些问题和其他问题，利用控制系统分析和设计（线性矩阵不等式，李雅普诺夫分析），优化（半定规划，对偶分解）和分布式算法的技术。广泛的影响。如果成功，这项研究工作将导致一种新的方法，将控制系统和优化的思想融合到分布式算法的设计和优化中，其应用包括传感器网络，分散协调控制和分布式计算。这些材料将完全整合到PI的控制和优化课程中

As integrated circuits and sensors, wireless communications, and other technologies continueto scale, more and more computational and communication intelligence can be built into embed-ded processors, sensors and actuators to perform coordinated tasks in a networked environment.This proposal concerns a new method for analyzing and designing certain iterative, distributedalgorithms in such networks. The method blends ideas from control system analysis and design,optimization, and graph theory, and is based on using new optimization methods to tune distributedalgorithms for speed and robustness. Preliminary results hint that the method (or extensions tobe developed) could have large impact on several application areas, including distributed sensorfusion, distributed optimization and resource allocation, Markov Chain Monte Carlo simulation,and distributed solution of linear equations.Distributed algorithm design and analysis is a well researched subject, with a literature go-ing back into the 1970s (and earlier), which we will draw from. Since the 1970s (amd earlier)algorithms have been proposed for distributed consensus averaging, optimization and resource al-location, routing and congestion control in networks, control (typically of a fleet of vehicles), andsensing and estimation. While the details of the algorithms differ, they are all local (with respect toan underlying graph), and typically update some variables (or prices, in some cases) proportionalto some function of its neighbors' values. Typical classical results for such algorithms state thatthe algorithm converges provided the underlying communication graph is connected, and certainupdating weights or gains are small enough and positive. The eigenvalues of the Laplacian of theunderlying graph often play a role in the convergence analysis.Intellectual merit. The PI poses the general question of finding weights that yield the fastestpossible convergence (and possibly other specifications, such as robustness, or monotone conver-gence), given the particular problem class and the underlying graph. Preliminary results show thatthe analysis, and optimal weight synthesis, can be framed in terms of linear matrix inequalities andsemidefinite programming and therefore readily computed (also in a distributed fashion), and thatthe optimal weights can give far faster converging algorithms than the classical (unweighted) ones.These preliminary results have just touched the surface of this topic; there is an enormous amountstill to do. What (further) distributed methods can be improved by adjusting weights? Whattypes of specifications can be handled? Can the method extend to asynchronous methods? Canthe method be extended to general Lyapunov functions for convergence analysis? What robust-ness can be built into these algorithms? How can optimal weights be computed efficiently? Canoptimal weights be computed in a distributed fashion? The PI will consider these questions andothers in the proposed research program, drawing on techniques from control system analysis anddesign (linear matrix inequalities, Lyapunov analysis), optimization (semidefinite programming,dual decomposition), and distributed algorithms.Broad impact. If successful, this research effort would lead to a new approach, blending ideasfrom control systems and optimization, to the design and optimization of distributed algorithms,with applications including sensor networks, decentralized coordinated control, and distributedcomputation. The material will be fully integrated into the PI's courses on control and optimization.1