Linear convergence rate for distributed optimization with the alternating direction method of multipliers
Franck Iutzeler, Pascal Bianchi, Ph. Ciblat, Walid Hachem · 2014
Consider the problem of distributed optimization where a network of N agents cooperate to solve a minimization problem of the form infxequation where function fnis convex and known only by agent n. The Alternating Direction Method of Multipliers (ADMM) has shown to be particularly efficient to solve this kind of problem. In this paper, we assume that there exists a unique minimum x*and that the functions fnare twice differentiable at x*and verify equation where the inequality is taken in the positive definite ordering. Under these assumptions, we prove the linear convergence of the distributed ADMM to the consensus over x*and derive a tight convergence rate. Finally, we give examples where one can derive the ADMM hyper-parameter ρ corresponding to the optimal rate.