Designing Fast Distributed Iterations via Semidefinite Programming

L. Xiao and S. Boyd

Talk presented at Workshop on large scale nonlinear and semidefinite programming, Waterloo, 51404

The general setting we consider involves a process, iteration, or method in which the computation or communication at each step is local, determined by a given graph, and involves some parameters or coefficients that affect its convergence speed. Examples include a Markov chain on a graph, where the transition probabilities affect the mixing rate of the chain; distributed averaging, where the local weights affect the global speed of convergence to the average; and distributed weighted gradient methods for resource allocation, where the weights affect the speed of convergence to the optimal allocation. We show how semidefinite programming can be used to choose the coefficients or parameters in these methods to yield fastest (or in some cases, just fast) convergence. We also show how weights suggested by the celebrated Metropolis-Hastings algorithm (for fast convergence in Monte Carlo Markov Chain simulation) transcribe well to other applications, such as distributed averaging.