Automatica, Vol.55, 209-216, 2015
On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems
In this paper we propose a fully distributed dual gradient algorithm for minimizing linearly constrained separable convex problems and analyze its rate of convergence. In particular, we prove that under the assumption of strong convexity and Lipschitz continuity of the gradient of the primal objective function we have a global error bound type property for the dual problem. Using this error bound property we devise a fully distributed dual gradient scheme, i.e. a gradient scheme based on a weighted step size, for which we derive global linear rate of convergence for both dual and primal suboptimality and for primal feasibility violation. Numerical simulations are also provided to confirm our theory. (C) 2015 Elsevier Ltd. All rights reserved.
Keywords:Separable convex problems;Error bound;Dual decomposition;Distributed gradient algorithm;Linear convergence