Semidefinite Programming for Weight Design in Fast Converging Distributed Algorithms

点击翻译按钮获取中文摘要

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