Linear Convergence Rate for Distributed Optimization with the Alternating Direction Method of Multipliers

Publication Type:

Conference Paper


IEEE Conference on Decision and Control (CDC) (2014)


Consider the problem of distributed optimization
where a network of N agents cooperate to solve a minimization
problem of the form infx
n=1 fn(x) where function fn is
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 fn
are twice differentiable at x? and verify $PN
n=1 ∇2
fn(x?) > 0$
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.

Full Text: