TY - GEN
T1 - Linear convergence rate for distributed optimization with the alternating direction method of multipliers
AU - Iutzeler, F.
AU - Bianchi, P.
AU - Ciblat, Ph
AU - Hachem, W.
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/1/1
Y1 - 2014/1/1
N2 - Consider the problem of distributed optimization where a network of N agents cooperate to solve a minimization problem of the form infx equation 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 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.
AB - Consider the problem of distributed optimization where a network of N agents cooperate to solve a minimization problem of the form infx equation 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 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.
KW - Alternating Direction Method of Multipliers
KW - Consensus algorithms
KW - Distributed optimization
UR - https://www.scopus.com/pages/publications/84931846498
U2 - 10.1109/CDC.2014.7040177
DO - 10.1109/CDC.2014.7040177
M3 - Conference contribution
AN - SCOPUS:84931846498
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 5046
EP - 5051
BT - 53rd IEEE Conference on Decision and Control,CDC 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Y2 - 15 December 2014 through 17 December 2014
ER -