Explicit Convergence Rate of a Distributed Alternating Direction Method of Multipliers

DOI10.1109/TAC.2015.2448011MaRDI QIDQ2980596zbMATH OpenOpenAlexFDO

Authors Franck Iutzeler, Pascal Bianchi, Philippe Ciblat, W. Hachem

Publication date 3 May 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.1085

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Abstract: Consider a set of N agents seeking to solve distributively the minimization problem $in{f}_{x}su{m}_{n=1}^N{f}_n(x)$ where the convex functions $f_n$ are local to the agents. The popular Alternating Direction Method of Multipliers has the potential to handle distributed optimization problems of this kind. We provide a general reformulation of the problem and obtain a class of distributed algorithms which encompass various network architectures. The rate of convergence of our method is considered. It is assumed that the infimum of the problem is reached at a point $x_{s}tar$, the functions $f_n$ are twice differentiable at this point and $sumabl{a}^2{f}_n(x_{s}tar)>0$ in the positive definite ordering of symmetric matrices. With these assumptions, it is shown that the convergence to the consensus $x_{s}tar$ is linear and the exact rate is provided. Application examples where this rate can be optimized with respect to the ADMM free parameter $ho$ are also given.

Cited in

(19)

• Is ADMM always faster than average consensus?
• Convergence rate analysis of distributed optimization with projected subgradient algorithm
• Tight global linear convergence rate bounds for Douglas-Rachford splitting
• A distributed asynchronous method of multipliers for constrained nonconvex optimization
• A fully distributed asynchronous approach for multi-area coordinated network-constrained unit commitment
• Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
• Distributed decision-coupled constrained optimization via proximal-tracking
• Risk-averse stochastic programming and distributionally robust optimization via operator splitting
• A novel bound on the convergence rate of ADMM for distributed optimization
• Distributed support vector machine in master-slave mode
• Tracking-ADMM for distributed constraint-coupled optimization
• Multi-cluster distributed optimization via random sleep strategy
• Revisiting EXTRA for Smooth Distributed Optimization
• Linear time average consensus and distributed optimization on fixed graphs
• A generic online acceleration scheme for optimization algorithms via relaxation and inertia
• Decentralized consensus algorithm with delayed and stochastic gradients
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
• Relaxed hybrid consensus ADMM for distributed convex optimisation with coupling constraints

This page was built for publication: Explicit Convergence Rate of a Distributed Alternating Direction Method of Multipliers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980596)