A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
复制标题
DOI：
--
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Mingyi Hong
中科院分区：
文献类型：
--
作者：
Mingyi Hong
乘法器的交替方向法（ADMM）已被广泛应用于求解许多凸或非凸信号处理问题。本文研究了ADMM的异步实现，用于求解目标为若干分量函数之和的非凸非光滑优化问题。该算法允许以分布式、异步和增量的方式解决问题。首先，组件功能可以分布到不同的计算节点，这些计算节点可以异步执行更新，而无需相互协调。我们的算法涵盖了两种异步来源：一种是由计算节点的异构性引起的，另一种是由不可靠的通信链路引起的。其次，该算法可以被视为实现增量算法，其中每一步仅更新组件函数子集的（可能延迟的）梯度d。我们表明，当在异步级别上放置某些界限时，所提出的算法收敛于平稳解集（见第1章）。最优解)的非凸(resp。凸)的问题。据我们所知，在所有已知的ADMM异步变体中，建议的ADMM实现可以容忍最高程度的异步。此外，它是第一个可以同时处理非凸性和异步性的ADMM实现。
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 the 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, who 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 update d. We show that when certain bounds are put on the level of asynchrony, the proposed algorithm converges to the set of stationary solutions (resp. optimal solutions) for the nonconvex (resp. convex) problem. To the best of our knowledge, the proposed ADMM implementation can tolerate the highest degree of asynchrony, among all known asynchronous variants of the ADMM. Moreover, it is the first ADMM implementation that can deal with nonconvexity and asynchrony at the same time.