A distributed, asynchronous, and incremental algorithm for nonconvex optimization: An ADMM approach

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

The alternating direction method of multipliers (ADMM) has been popular for solving many signal processing problems, convex or nonconvex. In this paper, we study an asynchronous implementation of ADMM for solving a nonconvex nonsmooth optimization problem, whose objective is the sum of a number of component functions. The proposed algorithm allows the problem to be solved in a distributed, asynchronous, and incremental manner. First, the component functions can be distributed to different computing nodes, which perform the updates asynchronously without coordinating with each other. Two sources of asynchrony are covered by our algorithm: One is caused by the heterogeneity of the computational nodes and the other arises from unreliable communication links. Second, the algorithm can be viewed as implementing an incremental algorithm where at each step the (possibly delayed) gradients of only a subset of component functions are updated. We show that when certain bounds are imposed on the level of asynchrony, the proposed algorithm converges to the set of stationary solutions (resp. optimal solutions) for the nonconvex (resp. convex) problem, with a global sublinear rate.

Original languageEnglish (US)
Article number7829332
Pages (from-to)935-945
Number of pages11
JournalIEEE Transactions on Control of Network Systems
Volume5
Issue number3
DOIs
StatePublished - Sep 2018
Externally publishedYes

Bibliographical note

Funding Information:
Manuscript received August 27, 2016; revised September 6, 2016 and December 1, 2016; accepted January 10, 2017. Date of publication January 23, 2017; date of current version September 17, 2018. This work was supported in part by the National Science Foundation under Grant CCF-1526078, and in part by the Air Force Office of Scientific Research under Grant 15RT0767. Recommended by Associate Editor M. Johansson.

Funding Information:
This work was supported in part by the National Science Foundation under Grant CCF- 1526078, and in part by the Air Force Office of Scientific Research under Grant 15RT0767

Publisher Copyright:
© 2014 IEEE.

Keywords

  • Alternating direction method of multipliers
  • asynchronous optimization
  • distributed optimization

Fingerprint

Dive into the research topics of 'A distributed, asynchronous, and incremental algorithm for nonconvex optimization: An ADMM approach'. Together they form a unique fingerprint.

Cite this