求解凸优化问题的改进对称交替方向乘子法

A modified symmetric alternating direction method of multipliers for convex optimization problems

对称交替方向乘子法(简称S-ADMM算法)是求解可分离凸优化问题的一种有效方法。该算法利用目标函数的可分离性,将原问题分解成多个极小化子问题,然后交替求解。能否有效地求解子问题对算法的有效性有重要影响。在很多实际应用中,不能精确地求解子问题,或者精确求解子问题花费代价较大。为解决这一问题,提出了一种改进的对称交替方向乘子法(简称MSADMM算法)。与一般的S-ADMM算法相比,该算法在x子问题中引入一个半近邻项,近似地求解x子问题,克服了之前算法的不足。在适当的假设下,证明了其收敛性。最后,通过数值计算说明了该算法的有效性。

Symmetric alternating direction method of multipliers(S-ADMM)is an efficient method for convex optimization problems with separable structure.The algorithm makes use of the separability of the objective function to decompose the original problem into several minimization subproblems and to solve them alternately.Whether the subproblems can be effectively solved affects the effectiveness of the algorithm.In many practical applications,subproblems cannot be solved precisely,or the cost of solving subproblems precisely is relatively high.To solve this problem,a modified symmetric alternating direction method of multipliers(MS-ADMM)is proposed.Compared to the general symmetric ADMM,this algorithm adds a semi-proximal term to x-subproblem which is then solved approximately.This overcomes the shortcoming of the previous algorithm.The convergence of the sequence generated by the proposed algorithm is proved under some suitable assumptions.Preliminary numerical experiments illustrate the effectiveness of proposed algorithm.