Abstract

We study distributed optimization over time-varying and random networks. First, we discuss some new establishments in the study of averaging dynamics over random graphs. In particular, we discuss a necessary condition for ergodicity of distributed averaging dynamics and discuss additional conditions that render this condition sufficient. Then, we consider one of the main applications of the distributed averaging dynamics, i.e., synthesis and analysis of distributed optimization algorithms. By introducing a new Martingale result, we prove the convergence of a random dynamics to a global minimizer of the distributed optimization problem. We discuss some of the consequences of this result in synthesizing fully distributed algorithms for distributed optimization.