Semidefinite Programming for Weight Design in Fast Converging Distributed Algorithms

Stanford University, Stanford CA

Investigators

Abstract

As integrated circuits and sensors, wireless communications, and other technologies continue to 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, distributed algorithms 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 distributed algorithms for speed and robustness. Preliminary results hint that the method (or extensions to be developed) could have large impact on several application areas, including distributed sensor fusion, 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), and sensing and estimation. While the details of the algorithms differ, they are all local (with respect to an underlying graph), and typically update some variables (or prices, in some cases) proportional to some function of its neighbors' values. Typical classical results for such algorithms state that the algorithm converges provided the underlying communication graph is connected, and certain updating weights or gains are small enough and positive. The eigenvalues of the Laplacian of the underlying graph often play a role in the convergence analysis. Intellectual merit. The PI poses the general question of finding weights that yield the fastest possible convergence (and possibly other specifications, such as robustness, or monotone conver- gence), given the particular problem class and the underlying graph. Preliminary results show that the analysis, and optimal weight synthesis, can be framed in terms of linear matrix inequalities and semidefinite programming and therefore readily computed (also in a distributed fashion), and that the 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 amount still to do. What (further) distributed methods can be improved by adjusting weights? What types of specifications can be handled? Can the method extend to asynchronous methods? Can the 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? Can optimal weights be computed in a distributed fashion? The PI will consider these questions and others in the proposed research program, drawing on techniques from control system analysis and design (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 ideas from control systems and optimization, to the design and optimization of distributed algorithms, with applications including sensor networks, decentralized coordinated control, and distributed computation. The material will be fully integrated into the PI's courses on control and optimization. 1