一种基于M范数惩罚项的线性化ADMM算法

A Linearized ADMM Algorithm Based on M-Norm Penalty Terms

摘要: ADMM算法是求解两块可分凸优化问题的经典算法，主要思想是在增广拉格朗日乘子法的基础上，利用目标函数关于两块变量的可分性，降低了求解子问题的计算难度。当增广拉格朗日函数中的惩罚项是M范数时，求解子问题往往较为困难。因此，我们在增广拉格朗日函数的基础上，通过增加一个半正定或正定的临近项，将M范数的惩罚项变为2范数的惩罚项，这样，就可以很快得到子问题的闭形式解。该方法同时具备弱化的惩罚项的条件和半正定临近项的优势，具有更广的适用性和更高的求解效率。这种改进的新算法可以看成临近点算法，它的收敛性易于分析，且无需要较强的假设条件。实验结果表明，新算法和其他几种主流的高效算法相比，新算法是可行的。

Abstract: The ADMM algorithm is a conventional strategy for solving two separable convex optimization problems. Its fundamental idea is to use the objective function on the basis of augmented Lagrangian multiplier method, reducing the computing burden of addressing subproblems. When the penalty term in the augmented Lagrangian function is M-norm, it is generally more difficult to solve subproblems. As a consequence of augmented Lagrange function, we shift the penalty term of the M-norm to the penalty term of the 2-norm by adding a semipositive definite or positive definite proximity term, allowing us to rapidly find the closed form solution of the subproblem. This approach has the advantages of a weaker penalty term and a semipositive definite proximity term, which allows for a broader range of applications. This improved new algorithm can be viewed as a proximity point algorithm, which is easy to analyze in terms of convergence and does not require strong assumptions. Experimental results show that the new algorithm is feasible compared to several other mainstream efficient algorithms.