Semidefinite Programming for Weight Design in Fast Converging Distributed Algorithms

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

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