On the linear convergence of the alternating direction method of multipliers
On the linear convergence of the alternating direction method of multipliers
复制标题
DOI：
10.1007/s10107-016-1034-2
复制
发表时间：
2017-03-01
影响因子：
2.7
通讯作者：
Luo, Zhi-Quan
中科院分区：
文献类型：
--
作者：
Hong, Mingyi;Luo, Zhi-Quan
分析了交替方向乘法器法求解线性约束下两个或多个非光滑凸可分离函数和的收敛速度。先前对ADMM的分析通常假设目标函数是定义在两个可分离变量块上的两个凸函数的和，即使该算法在三个或更多块的数值实验中效果良好。此外，对于目标函数不具有强凸性的ADMM，还没有对其收敛速度进行分析。在一定的误差界条件和对偶步长足够小的条件下，建立了任意凸可分函数和最小的ADMM的全局r -线性收敛性。当可行集为紧多面体，目标函数由一个线性映射组成的光滑严格凸函数和一个非光滑正则器组成时，即满足该误差界条件。这一结果表明，在不假设目标函数具有强凸性的情况下，ADMM对于LASSO等当代应用具有线性收敛性。
We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.