论文标题
迭代复杂性及其对乘数的线性化通用交替方向方法与多块情况的应用
Iterative Complexity and Its Applications of Linearized Generalized Alternating Direction Method of Multipliers with Multi-block Case
论文作者
论文摘要
我们考虑使用线性约束的多块可分离凸优化问题，其中目标函数是m个单个凸函数的总和而无需重叠变量。乘数（L-GADMM）的广义交替方向方法的线性化版本对于两个可分离的凸编程问题特别有效，并且当两个变量块被更新时，证明了其收敛性。但是，L-GADMM的扩展（M> = 3）的收敛性和一些实际应用仍处于起步阶段。在本文中，我们将该算法扩展到了目标函数由M-Block凸函数总和组成的一般情况。从理论上讲，我们证明了新方法的全局收敛性，并为所提出的算法建立了在ergodic和非癌变感中的最坏情况收敛速率。通过对相关矩阵校准的数值结果进一步证明了新方法的效率。
We consider a multi-block separable convex optimization problem with the linear constraints, where the objective function is the sum of m individual convex functions without overlapping variables. The linearized version of the generalized alternating direction method of multipliers (L-GADMM) is particularly efficient for the two-block separable convex programming problem and its convergence was proved when two blocks of variables are alternatively updated. However,the convergence and some practical applications of the extension (m>=3) of the L-GADMM is still in its infancy. In this paper, we extend this algorithm to the general case where the objective function consists of the sum of m-block convex functions. Theoretically, we prove global convergence of the new method and establish the worst-case convergence rate in the ergodic and nonergodic senses for the proposed algorithm. The efficiency of the new method is further demonstrated through numerical results on the calibration of the correlation matrices.
