Zero-gradient-sum algorithms for distributed convex optimization: The continuous-time case

This paper presents a family of continuous-time distributed algorithms called Zero-Gradient-Sum (ZGS) algorithms, which solve unconstrained, separable, convex optimization problems over undirected networks with fixed topologies. The ZGS algorithms are derived using a Lyapunov function candidate that exploits convexity, and get their name from the fact that they yield nonlinear networked dynamical systems whose states slide along an invariant, zero-gradient-sum manifold and converge asymptotically to the unknown minimizer. We also present a systematic way to construct ZGS algorithms, show that a subset of them converge exponentially, and obtain lower bounds on their convergence rates in terms of the convexity characteristics of the problem and the network topology, including its algebraic connectivity. Finally, we show that some of the well-studied continuous-time distributed consensus algorithms are special cases of ZGS algorithms and discuss the ramifications.