Linearized Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming
Linearized Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming
复制标题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
B. He;Xiaoming Yuan
中科院分区：
文献类型：
--
作者：
B. He;Xiaoming Yuan
最近，我们提出了将交替方向法（ADM）与高斯反代法相结合的方法来求解具有线性约束的凸极小化模型和一般可分离的目标函数，即目标函数是多个不耦合变量的函数的和。在本文中，我们进一步研究了这一主题，并表明通过线性化模型线性约束上的增广拉格朗日惩罚所产生的二次项，可以大大减轻ADM过程中分解的子问题。当目标中可分离函数的解算符具有闭形式表示时，必须将线性化嵌入到ADM子问题中，以产生具有闭形式解的简单子问题。因此，我们从理论上证明了ADM，高斯回代和线性化的混合对考虑的可分离凸最小化模型有效。
Recently, we have proposed to combine the alternating direction method (ADM) with a Gaussian back substitution procedure for solving the convex minimization model with linear constraints and a general separable objective function, i.e., the objective function is the sum of many functions without coupled variables. In this paper, we further study this topic and show that the decomposed subproblems in the ADM procedure can be substantially alleviated by linearizing the involved quadratic terms arising from the augmented Lagrangian penalty on the model's linear constraints. When the resolvent operators of the separable functions in the objective have closed- form representations, embedding the linearization into the ADM subproblems becomes necessary to yield easy subproblems with closed-form solutions. We thus show theoretically that the blend of ADM, Gaussian back substitution and linearization works effectively for the separable convex minimization model under consideration.