一种基于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.

1. 引言

本文考虑如下具有线性约束的可分凸优化问题：

$\min \left\{f\left(x\right)+g\left(y\right)|Ax+By=b,x\in X,y\in Y\right\}$ (1)

其中 $f：R^{n_1}\to R$ 和 $g：R^{n_2}\to R$ 是凸函数(但不一定光滑)， $A\in R^{m\times n_1},B\in R^{m\times n_2},b\in R^m,X\subseteq R^{n_1}$ 和 $Y\subseteq R^{n_2}$ 是闭凸集。

众所周知，交替方向乘子法是求解(1)的有效方法，该方法最早由Gabay和Mercier，Glowinski [1] 以及Marrocco [2] 提出，该方法是一种求解具有可分离的凸优化问题的重要方法，由于其收敛速度快、收敛性能好，在求解可分离凸优化问题上具有简单、灵活、实用性强的特点，可以将大规模问题拆分成两个甚至多个小规模的子问题，随后交替求解各个小规模子问题，从而提高了求解的速率，其优势在于利用对偶上升算法的可分离性，后来被广泛研究与应用。

为了提高ADMM的适用性，一些学者提出了许多改进的ADMM方法。He等人在文献 [3] 中提出了不定临近线性化ADMM。Gao [4] 提出了如下一个带不定临近正则项的线性化ADMM。Fang [5] 将增广Lagrange函数中的惩罚项采用M-范数，M是一个是对称正定矩阵。将2-范数形式改进为M-范数形式，弱化了惩罚项的条件。因为2-范数形式的惩罚项是矩阵范数M-范数的一种特殊形式，所以M-范数的使用范围更广。

基于上述讨论，本文结合半正定临近项和基于M-范数的惩罚项，提出了一种求解可分凸优化问题(1)的基于M-范数惩罚项的带半正定临近项的线性化ADMM算法。新方法在y-子问题中引入了一个半正定临近项，进而将M-范数惩罚项转化为2范数惩罚项。该方法同时具备弱化的惩罚项的条件和半正定临近项的优势，具有更广的适用性和更高的求解效率。针对所提出的算法，本文基于变分不等式和最优化理论给出了严格的收敛性分析以及收敛速率分析，并通过数值实验验证了算法的有效性。

2. 一种基于M范数惩罚项的ADMM算法

假设 $f:R^n\to R\cup +\infty$ 和 $g:R^n\to R\cup +\infty$ 是合适的、闭的、凸函数。

本文提出的算法如下：

算法1. 一种基于M范数惩罚项的ADMM算法

输入： $x^0，y^0，{\lambda }^0$

计算： $x^{k+1}，y^{k+1}，{\lambda }^{k+1}$

$x^{k+1}=\arg {\min }_x{L}_{\beta }\left(x,y^k,{\lambda }^k\right)$

$y^{k+1}=\arg {\min }_y{L}_{\beta }\left(x^{k+1},y,{\lambda }^k\right)+1/2{\Vert y-y^k\Vert }_D^2$

${\lambda }^{k+1}={\lambda }^k-\beta M\left(A{x}^{k+1}+B{y}^{k+1}-b\right)$

若满足停止准则，则输出： $x^{k+1}，y^{k+1}，{\lambda }^{k+1}$ ，其中 $L_{\beta }\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)-{\lambda }^T\left(Ax+By-b\right)+\beta /2{\Vert Ax+By-b\Vert }_M^2$ ，M是一个正定矩阵， $D=sI-\beta B^{T}MB\left(s\ge \Vert \beta B^{T}MB\Vert \right)$ 是一个半正定矩阵。

3. 收敛性分析

引理3.1. 设序列 $w^k$ 由算法1迭代产生，令 $u=\left(\begin{array}{c}x\\ y\end{array}\right)$ ， $\theta \left(u\right)=f\left(x\right)+g\left(y\right),w=\left(\begin{array}{c}x\\ y\\ \lambda \end{array}\right)$ 。

那么有 $w^\left(k+1\right)\in \Omega$ ，

$\theta \left(u\right)-\theta \left(u^{k+1}\right)+\left(w-w^{k+1}\right)\left\{\begin{array}{c}F\left(w^{k+1}\right)+\beta \left(\begin{array}{c}{A}^T\\ B^T\\ O\end{array}\right)MB\left(y^k-y^{k+1}\right)\\ +\left(\begin{array}{cc}\beta B^{T}MB+D& O\\ O& \frac{1}{\beta }{M}^{-1}\end{array}\right)\left(\begin{array}{c}{y}^{k+1}-y^k\\ {\lambda }^{k+1}-{\lambda }^k\end{array}\right)\end{array}\right\}\ge 0$ (2)

其中 $F\left(w^{k+1}\right)=\left(\begin{array}{c}-A^T{\lambda }^{k+1}\\ -B^T{\lambda }^{k+1}\\ A{x}^{k+1}+B{y}^{k+1}-b\end{array}\right)$ 。

引理3.2. 设序列 $w^k$ 由算法1迭代产生，则

$w^{k+1}\in \text{Ω}$ ，

$\theta \left(u\right)-\theta \left(u^{k+1}\right)+\left(w-w^{k+1}\right)\left\{F\left(w\right)+\beta \left(\begin{array}{c}{A}^T\\ B^T\end{array}\right)MB\left(y^k-y^{k+1}\right)\right\}\ge \left(v-v^{k+1}\right)G\left(v-v^{k+1}\right),\forall w\in \text{Ω}$ (3)

其中 $G=\left(\begin{array}{cc}\beta B^{T}MB+D& O\\ O& \frac{1}{\beta }{M}^{-1}\end{array}\right),v=\left(\begin{array}{c}y\\ \lambda \end{array}\right)$ 。

证明：因为 ${\left(w-w^{k+1}\right)}^T\left(F\left(w\right)-F\left(w^{k+1}\right)\right)\ge 0,\forall w\in \text{Ω}$ ，所以F是单调算子。

由(2)可得，(3)成立。

引理3.3. 设序列 $w^k$ 由算法1迭代产生，其中 $w^{*}\in {\text{Ω}}^{*},{\text{Ω}}^{*}$ 为变分不等式的解集，那么有

${\left(v^{k+1}-v^{*}\right)}^{T}G\left(v^k-v^{k+1}\right)\ge {\left({\lambda }^k-{\lambda }^{k+1}\right)}^{T}B\left(y^k-y^{k+1}\right)$ (4)

证明：

${\left(v^{k+1}-v^{*}\right)}^{T}G\left(v^k-v^{k+1}\right)$

$\begin{array}{l}\ge \theta \left(u^{k+1}\right)-\theta \left(u^{*}\right)+{\left(w^{k+1}-w^{*}\right)}^{T}F\left(w^{*}\right)+\beta {\left(\begin{array}{c}{x}^{k+1}-x^{*}\\ y^{k+1}-y^{*}\end{array}\right)}^T\left(\begin{array}{c}{A}^T\\ B^T\end{array}\right)MB\left(y^k-y^{k+1}\right)\\ \ge \beta \left(\begin{array}{c}{x}^{k+1}-x^{*}\\ y^{k+1}-y^{*}\end{array}\right)\left(\begin{array}{c}{A}^T\\ B^T\end{array}\right)MB\left(y^k-y^{k+1}\right)\\ =\beta {\left[\left(A{x}^{k+1}-A{x}^{*}\right)+\left(B{y}^{k+1}-B{y}^{*}\right)\right]}^{T}B\left(y^k-y^{k+1}\right)={\left({\lambda }^k-{\lambda }^{k+1}\right)}^{T}B\left(y^k-y^{k+1}\right)\end{array}$

引理3.4. 设序列 $w^k$ 由算法1迭代产生，那么有：

${\left({\lambda }^k-{\lambda }^{k+1}\right)}^{T}B\left(y^k-y^{k+1}\right)\ge \frac{1}{2}{\Vert y^k-y^{k+1}\Vert }_D^2-\frac{1}{2}{\Vert y^{k-1}-y^k\Vert }_D^2$ (5)

证明：对于算法1，由变分不等式可得：

$y^{k+1}\in Y,g\left(y^k\right)-g\left(y^{k+1}\right)+{\left(y^k-y^{k+1}\right)}^T-B^T{\lambda }^{k+1}+D\left(y^{k+1}-y^k\right)\ge 0,\forall y^k\in Y$

$y^k\in Y,g\left(y^{k+1}\right)-g\left(y^k\right)+{\left(y^{k+1}-y^k\right)}^T-B^T{\lambda }^k+D\left(y^k-y^{k-1}\right)\ge 0,\forall y^{k+1}\in Y$

两式相加可得： ${\left(y^k-y^{k+1}\right)}^T{B}^T\left({\lambda }^k-{\lambda }^{k+1}\right)+D\left[\left(y^{k+1}-y^k\right)-\left(y^k-y^{k-1}\right)\right]\ge 0$ ，所以 ${\left(y^k-y^{k+1}\right)}^T{B}^T\left({\lambda }^k-{\lambda }^{k+1}\right)\ge {\left(y^k-y^{k+1}\right)}^{T}D\left[\left(y^k-y^{k+1}\right)-\left(y^{k-1}-y^k\right)\right]$ 。

由柯西不等式可得：

${\left(y^k-y^{k+1}\right)}^{T}D\left[\left(y^k-y^{k+1}\right)-\left(y^{k-1}-y^k\right)\right]\ge \frac{1}{2}{\Vert y^k-y^{k+1}\Vert }_D^2-\frac{1}{2}{\Vert y^{k-1}-y^k\Vert }_D^2$

故(5)得证。

引理3.5. 设序列 $w^k$ 由算法1迭代产生，那么有：

${\left(v^{k+1}-v^{*}\right)}^{T}G\left(v^k-v^{k+1}\right)\ge \frac{1}{2}{\Vert y^k-y^{k+1}\Vert }_D^2-\frac{1}{2}{\Vert y^{k-1}-y^k\Vert }_D^2$ (6)

证明：

$\begin{array}{c}{\Vert v^k-v^{*}\Vert }_G^2={\Vert \left(v^{k+1}-v^{*}\right)+\left(v^k-v^{k+1}\right)\Vert }_G^2\\ \ge {\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert v^k-v^{k+1}\Vert }_G^2+2\left(v^{k+1}-v^{*}\right)G\left(v^k-v^{k+1}\right)\\ \ge {\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert v^k-v^{k+1}\Vert }_G^2+{\Vert y^k-y^{k+1}\Vert }_D^2-{\Vert y^{k-1}-y^k\Vert }_D^2\end{array}$

显然，(6)式成立。

定理3.1.对于任意的 $w^{*}\in {\text{Ω}}^{*}$ ，序列 ${\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert y^k-y^{k+1}\Vert }_D^2$ 是单调递减的。

证明：由引理3.5可得：

${\Vert v^k-v^{k+1}\Vert }_G^2\le \left({\Vert v^k-v^{*}\Vert }_G^2+{\Vert y^{k-1}-y^k\Vert }_D^2\right)-\left({\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert y^k-y^{k+1}\Vert }_D^2\right)$

因为 ${\Vert v^k-v^{k+1}\Vert }_G^2\ge 0$ ，所以 ${\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert y^k-y^{k+1}\Vert }_D^2\le {\Vert v^k-v^{*}\Vert }_G^2+{\Vert y^{k-1}-y^k\Vert }_D^2$ 。

故序列 ${\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert y^k-y^{k+1}\Vert }_D^2$ 是单调递减的。

定理3.2. 设序列 $w^k$ 由算法1迭代产生，那么序列 $v^{k_j}$ 收敛到 $v^{\infty }$ 。

证明：因为 ${\Vert v^k-v^{k+1}\Vert }_G^2\le \left({\Vert v^k-v^{*}\Vert }_G^2+{\Vert y^{k-1}-y^k\Vert }_D^2\right)-\left({\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert y^k-y^{k+1}\Vert }_D^2\right)$ 。

对上式求和可得： ${{\displaystyle {\sum }_{k=1}^{\infty }\Vert v^k-v^{k+1}\Vert }}_G^2\le {\Vert v^1-v^{*}\Vert }_G^2+{\Vert y^0-y^1\Vert }_D^2$ 。

因为G是正定的，所以 ${{\displaystyle {\sum }_{k=1}^{\infty }\Vert v^k-v^{k+1}\Vert }}_G^2$ 是正项级数。

由正项级数收敛的必要条件可知： $\underset{k\to \infty }{\lim }{\Vert v^k-v^{k+1}\Vert }_G^2=0$ 。

因为 $0\le {\Vert v^k-v^{k+1}\Vert }_G^2\le \left({\Vert v^k-v^{*}\Vert }_G^2+{\Vert y^{k-1}-y^k\Vert }_D^2\right)-\left({\Vert v^{k+1}-v^{*}\Vert }_G^2+{\Vert y^k-y^{k+1}\Vert }_D^2\right)$ 。

所以 ${\Vert v^{k+1}-v^{*}\Vert }_G^2\le {\Vert v^k-v^{*}\Vert }_G^2+{\Vert y^{k-1}-y^k\Vert }_D^2\le {\Vert v^1-v^{*}\Vert }_G^2+{\Vert y^0-y^1\Vert }_D^2,\forall k\ge 1$ 。

所以序列 $v^k$ 是有界的并且至少存在一个聚点 $v^{\infty }$ ，存在一个子列 $v^{k_j}$ 收敛到 $v^{\infty }$ 。

即 $\underset{k\to \infty }{\lim }{v}^{k_j}=v^{\infty }$ ，其中 $v^{\infty }=\left(\begin{array}{c}{y}^{\infty }\\ {\lambda }^{\infty }\end{array}\right)\in V^{*}$ 。

定理3.3. $w^{\infty }$ 是(1)的一个解。

证明：因为 $\underset{k\to \infty }{\lim }{\Vert v^k-v^{k+1}\Vert }_G^2=0$ ，所以 $\underset{k\to \infty }{\lim }\left(y^k-y^{k+1}\right)=0$ 和 $\underset{k\to \infty }{\lim }\left({\lambda }^k-{\lambda }^{k+1}\right)=0$ 。

由变分不等式可知：

$\begin{array}{l}{w}^{k+1}\in \text{Ω},\theta \left(u\right)-\theta \left(u^{k+1}\right)\\ +{\left(w-w^{k+1}\right)}^T\left\{\begin{array}{l}F\left(w^{k+1}\right)+\beta \left(\begin{array}{c}{A}^T\\ B^T\\ O\end{array}\right)MB\left(y^k-y^{k+1}\right)\\ +\left(\begin{array}{cc}\beta B^{T}MB+D& O\\ O& \frac{1}{\beta }{M}^{-1}\end{array}\right)\left(\begin{array}{c}{y}^{k+1}-y^k\\ {\lambda }^{k+1}-{\lambda }^k\end{array}\right)\end{array}\right\}\ge 0,\forall w\in \text{Ω}\end{array}$

令上式中 $k\to \infty$ ，可得： $\theta \left(u\right)-\theta \left(u^{\infty }\right)+{\left(w-w^{\infty }\right)}^{T}F\left(w^{\infty }\right)\ge 0$ ，故 $w^{\infty }$ 是(1)的解。

4. 数值实验

统计中的LASSO问题如下：

$\underset{x,y}{\min }\frac{1}{2}{\Vert Ax-b\Vert }_2^2+\mu {\Vert y\Vert }_{1}s.t.x=y$ (7)

其中 $A\in R^{m\times n},b\in R^m,x\in R^n,y\in R^n$ 。

使用算法1求解(7)得到 $x$ 子问题： $x^{k+1}=\frac{1}{\delta }\left[A^{T}b+{\lambda }^k+\left(\delta I-A^{T}A\right)y^k\right]$ 。

并且y子问题的闭式解是： $y^{k+1}=shrink\left(y^k-\frac{1}{\delta }\left[{\lambda }^k+M\left(y^k-x^{k+1}\right)\right],\frac{\mu }{\beta \delta }\right)$ 。

$\lambda$ 子问题的解为： ${\lambda }^{k+1}={\lambda }^k-\beta M\left(x^{k+1}-y^{k+1}\right)$ ，其中 $M=\delta I-A^{T}A,D=A^{T}A$ 。

本文通过数值实验比较了算法1和线性化DMM算法的迭代次数。

将每个算法的参数设置如下：

算法1： $\delta =\Vert A^{T}A\Vert +0.001,\beta =1,\mu =0.1{\Vert A^{T}b\Vert }_{\infty }$ 。

Linearized ADMM: $\delta =\Vert A^{T}A\Vert +0.001,\beta =1,\mu =0.1{\Vert A^{T}b\Vert }_{\infty }$ ， $D=\delta I-A^{T}A$ 。

停止准则是： $\Vert x^{k+1}-y^{k+1}\Vert <{\epsilon }^{pri},\Vert \beta \left(y^{k+1}-y^k\right)\Vert <{\epsilon }^{dual}$ ，其中 ${\epsilon }^{pri}=\sqrt{n}{\epsilon }^{abs}+{\epsilon }^{rel}\max \left(\Vert x^{k+1}\Vert ，\Vert y^{k+1}\Vert ，{\epsilon }^{dual}=\sqrt{n}{\epsilon }^{abs}+{\epsilon }^{rel}\Vert y^{k+1}\Vert \right)$ 。

${\epsilon }^{pri}$ 和 ${\epsilon }^{dual}$ 被设置为 ${10}^{-4}$ 和 ${10}^{-2}$ 。

对于给定的维度 $m\times n$ ，我们随机生成数据，如下所示：

$p=\frac{1}{n},x^0=sprandn\left(n,1,p\right),A=randn\left(m,n\right),b=A\ast x^0+sqrt\left(0.001\right)\ast randn\left(m,1\right)$

二种算法的实验结果如表1所示：

Table 1. Comparison of the number of iterations between Algorithm 1 and Linearized ADMM

表1. 算法1和Linearized ADMM的迭代次数比较

实验结果表明，算法1的迭代次数少。因此，算法1是有可比较性的。

5. 结论

在本文中，我们提出了一种基于M范数罚项的具有半正定邻近项的广义线性化ADMM算法，对其进行了全局收敛性分析。最后，通过数值实验验证了算法的有效性。