This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TAC.2014.2363299, IEEE Transactions on Automatic Control IEEE

Abstract—We study distributed optimization where nodes co-operatively minimize the sum of their individual, locally known, convex costs fi(x)’s, x ∈ Rd is global. Distributed augmented Lagrangian (AL) methods have good empirical performance on several signal processing and learning applications, but there is limited understanding of their convergence rates and how it depends on the underlying network. This paper establishes globally linear (geometric) convergence rates of a class of de-terministic and randomized distributed AL methods, when the fi’s are twice continuously differentiable and have a bounded Hessian. We give explicit dependence of the convergence rates on the underlying network parameters. Simulations illustrate our analytical findings