Asynchronous Distributed ADMM for Large-Scale Optimization - Part I: Algorithm and Convergence Analysis

Tsung Hui Chang, Mingyi Hong, Wei Cheng Liao, Xiangfeng Wang

Research output: Contribution to journalArticlepeer-review

65 Scopus citations

Abstract

Aiming at solving large-scale optimization problems, this paper studies distributed optimization methods based on the alternating direction method of multipliers (ADMM). By formulating the optimization problem as a consensus problem, the ADMM can be used to solve the consensus problem in a fully parallel fashion over a computer network with a star topology. However, traditional synchronized computation does not scale well with the problem size, as the speed of the algorithm is limited by the slowest workers. This is particularly true in a heterogeneous network where the computing nodes experience different computation and communication delays. In this paper, we propose an asynchronous distributed ADMM (AD-ADMM), which can effectively improve the time efficiency of distributed optimization. Our main interest lies in analyzing the convergence conditions of the AD-ADMM, under the popular partially asynchronous model, which is defined based on a maximum tolerable delay of the network. Specifically, by considering general and possibly non-convex cost functions, we show that the AD-ADMM is guaranteed to converge to the set of Karush-Kuhn-Tucker (KKT) points as long as the algorithm parameters are chosen appropriately according to the network delay. We further illustrate that the asynchrony of the ADMM has to be handled with care, as slightly modifying the implementation of the AD-ADMM can jeopardize the algorithm convergence, even under the standard convex setting.

Original languageEnglish (US)
Article number7423789
Pages (from-to)3118-3130
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume64
Issue number12
DOIs
StatePublished - Jun 15 2016

Bibliographical note

Funding Information:
T.-H. Chang is supported by NSFC, China, Grant No. 61571385. M. Hong is supported by NFS Grant No. CCF-1526078, and AFOSR, Grant No. 15RT0767. X. Wang is supported by Shanghai YangFan No. 15YF1403400 and NSFC No. 11501210. Part of this work was submitted to IEEE ICASSP, Shanghai, China, March 20-25, 2016 [1].

Keywords

  • ADMM
  • Distributed optimization
  • asynchronous
  • consensus optimization

Fingerprint Dive into the research topics of 'Asynchronous Distributed ADMM for Large-Scale Optimization - Part I: Algorithm and Convergence Analysis'. Together they form a unique fingerprint.

Cite this