论文标题
可分离凸编程的乘数的近端版本的全局线性收敛速率
The global linear convergence rate of the proximal version of the generalized alternating direction method of multipliers for separable convex programming
论文作者
论文摘要
为了通过线性约束解决可分离的凸优化问题，Eckstein和Bertsekas引入了乘数的广义交替方向方法（简而言之，GADMM），这是Anternation Direction乘数的有效而简单的加速方案。最近，\ textbf {fang et。 Al}提出了乘数的通用交替方向方法的线性化版本（简而言之，L-GADMM），其中其一个子问题通过线性化策略近似，并通过迭代率在两种核能敏感的迭代复杂性中测量的含量均可测量的最差的$ \ Mathcal {O}（O}（1/T）$ CENCERT率。在本文中，我们介绍了乘数的普遍交替方向方法（简而言之，DL-GADMM）的双线性化版本，其中$ x $ ubproblem和$ y $ -subproblem均通过线性化策略近似。基于误差绑定方法，我们建立了L-GADMM和DL-GADMM的线性收敛速率，用于可分离的凸优化问题，即基础函数的细分是分段线性多功能。本文中的结果扩展，概括和改善了文献中的一些已知结果。
To solve the separable convex optimization problem with linear constraints, Eckstein and Bertsekas introduced the generalized alternating direction method of multipliers (in short, GADMM), which is an efficient and simple acceleration scheme of the aternating direction method of multipliers. Recently, \textbf{Fang et. al} proposed the linearized version of generalized alternating direction method of multipliers (in short, L-GADMM), where one of its subproblems is approximated by a linearization strategy, and proved its worst-case $\mathcal{O}(1/t)$ convergence rate measured by the iteration complexity in both ergodic and nonergodic senses. In this paper, we introduce the doubly linearized version of generalized alternating direction method of multipliers (in short, DL-GADMM), where both the $x$-subproblem and $y$-subproblem are approximated by linearization strategies. Based on the error bound approach, we establish the linear convergence rate of both L-GADMM and DL-GADMM for separable convex optimization problem that the subdifferentials of the underlying functions are piecewise linear multifunctions. The results in this paper extend, generalize and improve some known results in the literature.
