惯性对称交替方向乘子算法

Inertial Symmetric Alternating Direction Multiplier Algorithm

摘要: 在本文中提出一种惯性对称交替方向乘子法求解两分块凸极小化优化问题，文章中证明了所提算法收敛到原问题的最优解，最后通过数据分析，验证所提算法的有效性和优越性。

Abstract: In this paper, an inertial symmetric alternating direction multiplier method is proposed to solve the two-partite convex miniaturization optimization problem, in which it is proved that the pro-posed algorithm converges to the optimal solution of the original problem, and finally, the effec-tiveness and superiority of the proposed algorithm is verified through the data analysis.

1. 引言

在本文中主要考虑以下复合优化问题：

$\begin{array}{l}\min \left\{f\left(x\right)+g\left(y\right)\right\}\\ \text{s}\text{.t}.Ax+By=b\end{array}$ (1)

其中 $f:F\to \left(-\infty ,+\infty \right]$ 和 $g:G\to \left(-\infty ,+\infty \right]$ 是正则下半连续凸函数， $A:F\to H$ 和 $B:G\to H$ 是非零有界线性算子， $F,G,H$ 是实Hilbert空间， $b\in H$ 。

交替方向乘子法(ADMM)是求解问题(1)的一种常用算法，ADMM最早是由Gabay [1] 、Glowinski [2] 提出，ADMM算法的迭代步骤为

$\{\begin{array}{l}{x}^{k+1}=\underset{x}{\arg \min }\left\{f\left(x\right)+\langle {\lambda }^k,Ax+B{y}^k-b\rangle +\frac{\beta }{2}{\Vert Ax+B{y}^k-b\Vert }^2\right\}\\ y^{k+1}=\underset{y}{\arg \min }\left\{g\left(y\right)+\langle {\lambda }^k,A{x}^{k+1}+By-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+By-b\Vert }^2\right\}\\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\end{array}$ (2)

Lorenz [3] 提出了向前向后分裂算法，随后在文献 [4] [5] [6] 的基础上结合Nesterov加速方法对算法进行改进，求解两分块问题的方法还有惯性Douglas-Rachford算子分裂算法 [7] 、惯性ADMM [8] 、惯性三算子分裂算法 [9] 等算法。Chen [10] 等人通过结合邻近ADMM [11] 算法提出求解带有线性约束可分离凸优化问题的惯性邻近ADMM算法，并证明了算法的收敛性，薛中会等人 [12] 对可分离凸优化问题采用惯性技术，同时引入随机加速的随即变量更新步长，提出了惯性近似松弛交替方向乘子法。

Tseng [13] 中提出了交替极小化算法(AMA)，迭代步骤如下

$\{\begin{array}{l}{x}^{k+1}=\underset{x}{\arg \min }\left\{f\left(x\right)-\langle {\lambda }^k,Ax\rangle \right\}\\ y^{k+1}=\underset{y}{\arg \min }\left\{g\left(y\right)-\langle {\lambda }^k,By\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+By-b\Vert }^2\right\}\\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\end{array}$ (3)

为了加速(3)，Goldstein在FISTA的基础上求解(1)的对偶问题，得到加速AMA，迭代步骤如下

$\{\begin{array}{l}{x}^{k+1}=\underset{x}{\arg \min }\left\{f\left(x\right)-\langle {\tilde{\lambda }}^k,Ax\rangle \right\}\\ y^{k+1}=\underset{y}{\arg \min }\left\{g\left(y\right)-\langle {\tilde{\lambda }}^k,By\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+By-b\Vert }^2\right\}\\ {\lambda }^{k+1}={\tilde{\lambda }}^k-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\\ {\alpha }_{k+1}=\frac{1+\sqrt{1+4{\alpha }_k^2}}{2}\\ {\tilde{\lambda }}^{k+1}={\lambda }^k+\frac{{\alpha }_k-1}{{\alpha }_{k+1}}\left({\lambda }^k-{\lambda }^{k-1}\right)\end{array}$ (4)

其中Chambolle [14] 证明了迭代序列 $\left\{{\lambda }^k\right\}$ 的收敛性。吴双双在 [15] 中提出了一种惯性的交替极小化算法用来解决问题(1)算法迭代步骤如下

$\{\begin{array}{l}{\tilde{\lambda }}^k={\lambda }^k+{\alpha }_k\left({\lambda }^k-{\lambda }^{k-1}\right)\\ x^{k+1}=\underset{x}{\arg \min }\left\{f\left(x\right)-\langle {\tilde{\lambda }}^k,Ax\rangle \right\}\\ y^{k+1}=\underset{y}{\arg \min }\left\{g\left(y\right)-\langle {\tilde{\lambda }}^k,By\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+By-b\Vert }^2\right\}\\ {\lambda }^{k+1}={\tilde{\lambda }}^k-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)n\end{array}$ (5)

其中 $\left\{\beta \right\}\subseteq \left(0,\frac{2\sigma }{{\Vert A\Vert }^2}\right)$ 。

问题(1)的特例有许多，例如财务和统计问题 [16] ，资源分配问题 [17] ，闭凸集交集上的投影问题 [18] [19] ，具有约束的全变分图像去噪问题 [20] [21] [22] 等。下面介绍一下具有约束的全变分图像去噪问题：

$\begin{array}{l}\underset{x}{\min }\frac{1}{2}{\Vert x-u\Vert }^2+\lambda {\Vert x\Vert }_{TV}\\ \text{s}\text{.t}.x\in C\end{array}$ (6)

(6)式是有约束的，通过加入示性函数 ${\zeta }_C\left(x\right)$ ，由于 ${\Vert x\Vert }_{TV}=\phi \left(Lx\right)$ ，(6)可以表示为

$\underset{x}{\min }\frac{1}{2}{\Vert x-u\Vert }^2+\lambda {\Vert x\Vert }_{TV}+{\zeta }_C\left(x\right)$ (7)

设 $f\left(x\right)=\frac{1}{2}{\Vert x-u\Vert }^2+{\zeta }_C\left(x\right)$ ， $y=Lx$ ，因此(7)可以表示为

$\begin{array}{l}\underset{x,y}{\min }f\left(x\right)+\lambda \phi \left(y\right)\\ \text{s}\text{.t}\text{.}y=Lx\end{array}$ (8)

上述问题没有引入对称步，因此本文考虑，在吴 [5] 的基础上，引入一步对称步骤求解问题(1)，本文证明所提算法的收敛到问题(1)的最优解，通过数据分析，与已有的ADMM算法比较，验证新算法的有效性和优越性。

下面给出文章中会用到的一些符号，如表1所示。

Table 1. Symbol cross-reference

表1. 符号对照表

2. 预备知识

定义1. 给定一个正常凸函数 $f:H\to \bar{R}$ ，它在点x处的次微分定义为：

$\partial f\left(x\right)=\left\{g\in H:f\left(y\right)\ge f\left(x\right)+\langle g,y-x\rangle ,\forall y\in H\right\}$

其中 $\partial f\left(x\right)$ 里的元素称为函数f在点x处的次梯度，如果 $\partial f\left(x\right)\ne \varnothing$ ，称函数f在点x处是可微的。

定义2. 设凸函数 $f:\epsilon \to \left(-\infty ,+\infty \right]$ ，定义f在点 $y\in \epsilon$ 的Fenchel共轭函数：

$f^{*}\left(y\right):=\underset{x}{\sup }\left\{\langle x,y\rangle -f\left(x\right)\right\}=-\underset{x}{\inf }\left\{f\left(x\right)-\langle x,y\rangle \right\}$ , $\forall y\in \epsilon$

可知共轭函数 $f^{*}\left(y\right)$ 是闭凸函数。

定义3. 对任意 $y\in \epsilon$ ，令 $f:\epsilon \to \left(-\infty ,+\infty \right]$ 是闭凸函数，若满足

$f\left(y\right)\ge f\left(x\right)+\langle x^{*},y-x\rangle$

则称 $x^{*}$ 为f在点 $x\in \epsilon$ 处的次梯度，f在x处次梯度的全体称为f在x处的次微分，记为 $\partial f\left(x\right)$ 。

3. 惯性对称ADMM算法收敛性分析

在本节中，给出具体求解问题(1)的新算法，具体格式如下：

定理1 假设拉格朗日函数的鞍点是非空的，且 $\left\{x^k\right\}$ ， $\left\{y^k\right\}$ ， $\left\{{\lambda }^k\right\}$ 是由算法1生成的序列，如果 $\beta$ 满足下列条件，存在 $\gamma >0$ ，使得 $\beta \in \left(\gamma ,\frac{2\sigma }{{\Vert A\Vert }^2}-\gamma \right)$ ， $\alpha <1$ ， ${\alpha }_k\in \left[0,\alpha \right]$ 是非递减序列且满足

${\displaystyle \underset{k=0}{\overset{+\infty }{\sum }}{\alpha }_k}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2<+\infty$

则存在拉格朗日函数的一组鞍点 $\left(x^{*},y^{*},{\lambda }^{*}\right)$ ，使得

① $x^{k+1}\to x^{*}$

② $y^{k+1}\to y^{*}$

③ ${\lambda }^{k+1}\to {\lambda }^{*}$

④ $\underset{k\to +\infty }{\lim }f\left(x^{k+1}\right)+g\left(y^{k+1}\right)=f\left(x^{*}\right)+g(\; y\; *\; )$

证明

问题(1)的拉格朗日函数为

$L\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)-{\lambda }^{\text{T}}\left(Ax+By-b\right)$ (9)

其中 $\lambda \in R^l$ 是拉格朗日乘子。

问题(1)的增广拉格朗日函数为

$L\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)-{\lambda }^{\text{T}}\left(Ax+By-b\right)+\frac{\beta }{2}{\Vert Ax+By-b\Vert }^2$ (10)

问题(1)的对偶问题为

$\underset{\lambda }{\max }q\left(\lambda \right)=-f^{*}\left(A^{*}\lambda \right)-g^{*}\left(B^{*}\lambda \right)+\langle \lambda ,b\rangle$ (11)

其中 $f^{*},g^{*}$ 分别是f和g的Fenchel共轭。

应用惯性邻近梯度算法求解(4)

$\{\begin{array}{l}{\tilde{\lambda }}^k={\lambda }^k+{\alpha }_k\left({\lambda }^k-{\lambda }^{k-1}\right)\hfill \\ {\lambda }^{k+1}=pro{x}_{\beta h}\left({\tilde{\lambda }}^k-\beta A\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)\right)\hfill \end{array}$ (12)

其中， $h\left(\lambda \right)=g^{*}\left(B^{*}\lambda \right)-\langle \lambda ,b\rangle$

设 $x^{k+1}=\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)$ ，则有

$\begin{array}{l}{A}^{*}{\tilde{\lambda }}^k\in \partial f\left(x^{k+1}\right)\\ 0\in \partial f\left(x^{k+1}\right)-A^{*}{\tilde{\lambda }}^k\end{array}$

等价于

$x^{k+1}=\underset{x}{\arg \min }\left\{f\left(x\right)-\langle {\tilde{\lambda }}^k,Ax\rangle \right\}$ (13)

将 $h\left(\lambda \right)=g^{*}\left(B^{*}\lambda \right)-\langle \lambda ,b\rangle$ 代入(12)且有邻近算子定义可得

$\begin{array}{c}{\lambda }^{k+1}=pro{x}_{\beta h}\left({\tilde{\lambda }}^k-\beta A\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)\right)\\ =\underset{\lambda }{\arg \min }\left\{\beta h\left(\lambda \right)+\frac{1}{2}{\Vert \lambda -\left({\tilde{\lambda }}^k-\beta A\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)\right)\Vert }^2\right\}\\ =\underset{\lambda }{\arg \min }\left\{\beta \left(g^{*}\left(B^{*}\lambda \right)-\langle \lambda ,b\rangle \right)+\frac{1}{2}{\Vert \lambda -{\tilde{\lambda }}^k+\beta A\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)\Vert }^2\right\}\\ =\underset{\lambda }{\arg \min }\left\{\beta g^{*}\left(B^{*}\lambda \right)-\beta \langle \lambda ,b\rangle +\frac{1}{2}{\Vert \lambda -{\tilde{\lambda }}^k+\beta A\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)\Vert }^2\right\}\end{array}$ (14)

又 $x^{k+1}=\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)$ ，所以(14)可以化为

$\begin{array}{l}\underset{\lambda }{\arg \min }\left\{\beta g^{*}\left(B^{*}\lambda \right)-\beta \langle \lambda ,b\rangle +\frac{1}{2}{\Vert \lambda -{\tilde{\lambda }}^k+\beta A\nabla f^{*}\left(A^{*}{\tilde{\lambda }}^k\right)\Vert }^2\right\}\\ =\underset{\lambda }{\arg \min }\left\{\beta g^{*}\left(B^{*}\lambda \right)-\beta \langle \lambda ,b\rangle +\frac{1}{2}{\Vert \lambda -{\tilde{\lambda }}^k+\beta A{x}^{k+1}\Vert }^2\right\}\end{array}$ (15)

上述一阶优化条件可得

$0\in \beta \partial g^{*}\left(B^{*}{\lambda }^{k+1}\right)-\beta b+\left({\lambda }^{k+1}-{\tilde{\lambda }}^k+\beta A{x}^{k+1}\right)$ (16)

设 $y^{k+1}\in \beta \partial g^{*}\left(B^{*}{\lambda }^{k+1}\right)$ ，可以得到

$0\in \partial g\left(y^{k+1}\right)-B^{*}{\lambda }^{k+1}$ (17)

对(17)进行变形可以得到

$\begin{array}{l}0\in \partial g\left(y^{k+1}\right)-B^{*}{\lambda }^{k+1}-B^{*}\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)+B^{*}\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\\ 0\in \partial g\left(y^{k+1}\right)-B^{*}\left({\lambda }^{k+1}+\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\right)+B^{*}\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\end{array}$ (18)

由算法第6步可以得到(17)等价于

$0\in \partial g\left(y^{k+1}\right)-B^{*}{\lambda }^{k+\frac{1}{2}}+B^{*}\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)$ (19)

因此

$y^{k+1}=\underset{y}{\arg \min }\left\{g\left(y\right)-\langle {\lambda }^{k+\frac{1}{2}},By\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+By-b\Vert }^2\right\}$ (20)

这是新算法的第5步。

新算法的第3步和第5步由一阶优化条件可以得到

$A^{*}{\tilde{\lambda }}^k\in \partial f\left(x^{k+1}\right)$ (21)

$B^{*}{\lambda }^{k+\frac{1}{2}}-B^{*}\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\in \partial g\left(y^{k+1}\right)$ (22)

由f和g单调有

$\langle x^{k+1}-x^{*},A^{*}\left({\tilde{\lambda }}^k-{\lambda }^{*}\right)\rangle \ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2$ (23)

$\langle y^{k+1}-y^{*},B^{*}\left({\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\right)-\beta B^{*}\left(A{x}^{k+1}+B{y}^{k+1}-b\right)\rangle \ge 0$ (24)

现在将(12)和(13)两式相加可以得到

$\langle x^{k+1}-x^{*},A^{*}\left({\tilde{\lambda }}^k-{\lambda }^{*}\right)\rangle +\langle y^{k+1}-y^{*},B^{*}\left({\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\right)-\beta B^{*}\left(A{x}^{k+1}+B{y}^{k+1}-b\right)\rangle \ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2$ (25)

整理可得

$\begin{array}{l}\langle x^{k+1}-x^{*},A^{*}\left({\tilde{\lambda }}^k-{\lambda }^{*}\right)\rangle +\langle y^{k+1}-y^{*},B^{*}\left({\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\right)-\beta B^{*}\left(A{x}^{k+1}+B{y}^{k+1}-b\right)\rangle \ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\\ \langle {\tilde{\lambda }}^k-{\lambda }^{*},A\left(x^{k+1}-x^{*}\right)\rangle +\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},B\left(y^{k+1}-y^{*}\right)\rangle -\langle \beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right),B\left(y^{k+1}-y^{*}\right)\rangle \ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$ (26)

由算法第4步、算法第6步和 $A{x}^{*}+B{y}^{*}=b$ 可以得到

$\begin{array}{l}\langle {\tilde{\lambda }}^k-{\lambda }^{*},A\left(x^{k+1}-x^{*}\right)\rangle +\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},B\left(y^{k+1}-y^{*}\right)\rangle \\ =\langle {\lambda }^{k+\frac{1}{2}}-\beta \left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)-{\lambda }^{*},A\left(x^{k+1}-x^{*}\right)\rangle +\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},B\left(y^{k+1}-y^{*}\right)\rangle \\ =\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}-\beta \left(A{x}^{k+1}+B{\tilde{y}}^k-b\right),A\left(x^{k+1}-x^{*}\right)\rangle +\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},B\left(y^{k+1}-y^{*}\right)\rangle \\ =\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},A\left(x^{k+1}-x^{*}\right)+B\left(y^{k+1}-y^{*}\right)\rangle -\beta \langle A\left(x^{k+1}-x^{*}\right),\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\rangle \\ =\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},A{x}^{k+1}+B{y}^{k+1}-b\rangle -\beta \langle A\left(x^{k+1}-x^{*}\right),\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\rangle \\ =\frac{1}{\beta }\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},{\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\rangle -\beta \langle A\left(x^{k+1}-x^{*}\right),\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\rangle \end{array}$ (27)

将(26)代入(25)可以得到

$\begin{array}{l}\frac{1}{\beta }\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},{\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\rangle -\beta \langle A\left(x^{k+1}-x^{*}\right),\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\rangle \\ -\langle \beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right),B\left(y^{k+1}-y^{*}\right)\rangle \ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$ (28)

根据余弦等式，可以将(27)化简为

$\begin{array}{l}\frac{1}{\beta }\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},{\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\rangle -\beta \langle A\left(x^{k+1}-x^{*}\right),\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\rangle \\ -\beta \langle \left(A{x}^{k+1}+B{y}^{k+1}-b\right),B\left(y^{k+1}-y^{*}\right)\rangle \ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$ (29)

现在分开算(28)左边第一项等于

$\begin{array}{c}\frac{1}{\beta }\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},{\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\rangle =-\frac{1}{\beta }\langle {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*},{\lambda }^{k+1}-{\lambda }^{k+\frac{1}{2}}\rangle \\ =-\frac{1}{2\beta }\left({\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\Vert }^2\right)\end{array}$ (30)

左边第二项等于

$\begin{array}{c}-\beta \langle A\left(x^{k+1}-x^{*}\right),\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\rangle =\beta \langle A{x}^{k+1}-A{x}^{*},\left(b-B{\tilde{y}}^k\right)-A{x}^{k+1}\rangle \\ =\frac{\beta }{2}\left({\Vert A{x}^{*}+B{\tilde{y}}^k-b\Vert }^2-{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2-{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\right)\end{array}$ (31)

左边第三项等于

$\begin{array}{c}-\langle \beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right),B\left(y^{k+1}-y^{*}\right)\rangle =\beta \langle B{y}^{k+1}-\left(b-A{x}^{k+1}\right),B{y}^{*}-B{y}^{k+1}\rangle \\ =\frac{\beta }{2}\left({\Vert b-A{x}^{k+1}-B{y}^{*}\Vert }^2-{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\right)\end{array}$ (32)

将(29) (30) (31)相加并代入(28)可以得到

$\begin{array}{l}-\frac{1}{2\beta }\left({\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\Vert }^2\right)\\ +\frac{\beta }{2}\left({\Vert A{x}^{*}+B{\tilde{y}}^k-b\Vert }^2-{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2-{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\right)\\ +\frac{\beta }{2}\left({\Vert b-A{x}^{k+1}-B{y}^{*}\Vert }^2-{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\right)\ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$ (33)

继续化简(32)

$\begin{array}{l}-\frac{1}{2\beta }\left({\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\Vert }^2\right)-\frac{\beta }{2}{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2\\ +\frac{\beta }{2}\left({\Vert A{x}^{*}-A{x}^{k+1}\Vert }^2-{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\right)\ge \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$ (34)

$\begin{array}{l}-\left({\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\Vert }^2\right)-{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2\\ +{\beta }^2\left({\Vert A{x}^{*}-A{x}^{k+1}\Vert }^2-{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\right)\ge 2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\\ -{\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2+{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\Vert }^2-{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2\\ +{\beta }^2{\Vert A{x}^{*}-A{x}^{k+1}\Vert }^2-{\beta }^2{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\ge 2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$

$\begin{array}{l}{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\Vert }^2-{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert A{x}^{*}-A{x}^{k+1}\Vert }^2\\ -{\beta }^2{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2-2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\ge {\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2\\ {\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2\le {\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\Vert }^2-{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert A{x}^{*}-A{x}^{k+1}\Vert }^2\\ -{\beta }^2{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2-2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$ (35)

$\begin{array}{c}{\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2\le {\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^{k+\frac{1}{2}}-\left({\lambda }^{k+\frac{1}{2}}-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\right)\Vert }^2\\ -{\beta }^2{\Vert A\Vert }^2{\Vert x^{k+1}-x^{*}\Vert }^2+{\beta }^2{\Vert A\Vert }^2{\Vert x^{*}-x^{k+1}\Vert }^2-{\beta }^2{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2\\ -{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2-2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\\ {\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2\le {\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2+{\beta }^2{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\beta }^2{\Vert A\Vert }^2{\Vert x^{k+1}-x^{*}\Vert }^2\\ +{\beta }^2{\Vert A\Vert }^2{\Vert x^{*}-x^{k+1}\Vert }^2-{\beta }^2{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2\end{array}$ (36)

因此可以得到

$\begin{array}{c}{\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2\le {\Vert {\lambda }^{k+\frac{1}{2}}-{\lambda }^{*}\Vert }^2-2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ ={\Vert {\tilde{\lambda }}^k+\beta \left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)-{\lambda }^{*}\Vert }^2-2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ ={\Vert {\tilde{\lambda }}^k-{\lambda }^{*}\Vert }^2+{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2+2\beta \langle {\tilde{\lambda }}^k-{\lambda }^{*},A{x}^{k+1}+B{\tilde{y}}^k-b\rangle \\ -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\end{array}$ (37)

根据算法第二步可以得到

$\begin{array}{l}{\Vert {\tilde{\lambda }}^k-{\lambda }^{*}\Vert }^2+{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2+2\beta \langle {\tilde{\lambda }}^k-{\lambda }^{*},A{x}^{k+1}+B{\tilde{y}}^k-b\rangle -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ ={\Vert {\lambda }^k+{\alpha }_k\left({\lambda }^k-{\lambda }^{k-1}\right)-{\lambda }^{*}\Vert }^2+{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\\ +2\beta \langle {\tilde{\lambda }}^k-{\lambda }^{*},A{x}^{k+1}+B{\tilde{y}}^k-b\rangle -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ ={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k{}^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+2{\alpha }_k\langle {\lambda }^k-{\lambda }^{*},{\lambda }^k-{\lambda }^{k-1}\rangle +{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\\ +2\beta \langle {\tilde{\lambda }}^k-{\lambda }^{*},A{x}^{k+1}+B{\tilde{y}}^k-b\rangle -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\end{array}$

$\begin{array}{l}={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-2{\alpha }_k\langle {\lambda }^k-{\lambda }^{*},{\lambda }^{k-1}-{\lambda }^k\rangle +{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\\ +2\beta \langle {\tilde{\lambda }}^k-{\lambda }^{*},A{x}^{k+1}+B{\tilde{y}}^k-b\rangle -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ ={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-\left({\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\right)+{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\\ +2\beta \langle {\tilde{\lambda }}^k-{\lambda }^{*},A{x}^{k+1}+B{\tilde{y}}^k-b\rangle -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ ={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\\ +2\langle {\tilde{\lambda }}^k-{\lambda }^{*},{\lambda }^{k+\frac{1}{2}}-{\tilde{\lambda }}^k\rangle -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\end{array}$ (38)

$\begin{array}{l}{\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-b\Vert }^2\\ ={\beta }^2{\Vert A{x}^{k+1}+B{\tilde{y}}^k-A{x}^{*}-B{y}^{*}\Vert }^2={\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}+B{\tilde{y}}^k-B{y}^{*}\Vert }^2\\ ={\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{\tilde{y}}^k-B{y}^{*}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \\ ={\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B\left(y^k+{\alpha }_k\left(y^k-y^{k-1}\right)\right)-B{y}^{*}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \\ ={\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}+B{\alpha }_k\left(y^k-y^{k-1}\right)\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \end{array}$

$\begin{array}{l}={\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\beta }^2{\alpha }_k{}^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2\\ -2{\alpha }_k\langle B{y}^k-B{y}^{*},B{y}^{k-1}-B{y}^k\rangle +{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \\ ={\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\beta }^2{\alpha }_k^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2\\ +{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \end{array}$ (39)

将(38)代入(37)

$\begin{array}{l}{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\\ +{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\beta }^2{\alpha }_k^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2\\ +{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \\ +{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \end{array}$

$\begin{array}{l}={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\\ +{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\beta }^2{\alpha }_k^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2\\ +{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \\ +{\Vert {\lambda }^{*}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\Vert {\tilde{\lambda }}^k-{\lambda }^{*}\Vert }^2-{\Vert {\tilde{\lambda }}^k-{\lambda }^{k+\frac{1}{2}}\Vert }^2-2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\end{array}$

$\begin{array}{l}={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\\ +{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\beta }^2{\alpha }_k^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2\\ +{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \\ +{\Vert {\lambda }^{*}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\Vert {\lambda }^k+{\alpha }_k\left({\lambda }^k-{\lambda }^{k-1}\right)-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^k+{\alpha }_k\left({\lambda }^k-{\lambda }^{k-1}\right)-{\lambda }^{k+\frac{1}{2}}\Vert }^2\\ -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\end{array}$

$\begin{array}{l}={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\\ +{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\beta }^2{\alpha }_k^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2\\ +{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \\ +{\Vert {\lambda }^{*}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\Vert {\lambda }^k+{\alpha }_k\left({\lambda }^k-{\lambda }^{k-1}\right)-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^k+{\alpha }_k\left({\lambda }^k-{\lambda }^{k-1}\right)-{\lambda }^{k+\frac{1}{2}}\Vert }^2\\ -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\end{array}$ (40)

因此(36)等价于

$\begin{array}{c}{\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2\le {\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2\\ +{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\beta }^2{\alpha }_k^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2\\ +{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle +{\Vert {\lambda }^{*}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2\\ -{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2-{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k+\frac{1}{2}}\Vert }^2\\ -{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\alpha }_k{\Vert {\lambda }^{k-1}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{k+\frac{1}{2}}\Vert }^2\\ -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\end{array}$ (41)

$\begin{array}{c}{\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2\le {\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2-{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\Vert {\lambda }^{*}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2-{\alpha }_k^2{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\\ -{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k+\frac{1}{2}}\Vert }^2+{\beta }^2{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2+{\beta }^2{\Vert B{y}^k-B{y}^{*}\Vert }^2\\ +{\beta }^2{\alpha }_k^2{\Vert B{y}^k-B{y}^{k-1}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{*}\Vert }^2+{\alpha }_k{\Vert B{y}^k-B{y}^{k-1}\Vert }^2\\ -2\beta \sigma {\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2+{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle \end{array}$ (42)

由 $A{x}^{*}+B{y}^{*}=b$ 以及算法的第1步可以得到

$\begin{array}{c}{\beta }^2\langle A{x}^{k+1}-A{x}^{*},B{\tilde{y}}^k-B{y}^{*}\rangle ={\beta }^2\langle A{x}^{k+1}-\left(b-B{x}^{*}\right),B{\tilde{y}}^k-B{y}^{*}\rangle ={\beta }^2\langle B{x}^{*}-\left(b-A{x}^{k+1}\right),B{\tilde{y}}^k-B{y}^{*}\rangle \\ =\frac{{\beta }^2}{2}\left({\Vert b-A{x}^{k+1}-B{\tilde{y}}^k\Vert }^2-{\Vert B{x}^{*}-\left(b-A{x}^{k+1}\right)\Vert }^2-{\Vert B{x}^{*}-B{\tilde{y}}^k\Vert }^2\right)\\ =\frac{{\beta }^2}{2}{\Vert b-A{x}^{k+1}-B{\tilde{y}}^k\Vert }^2-\frac{{\beta }^2}{2}{\Vert B{x}^{*}-\left(b-A{x}^{k+1}\right)\Vert }^2-\frac{{\beta }^2}{2}{\Vert B{x}^{*}-B{\tilde{y}}^k\Vert }^2\\ =\frac{{\beta }^2}{2}{\Vert A{x}^{*}-A{x}^{k+1}-\left(B{\tilde{y}}^k-B{y}^{*}\right)\Vert }^2-\frac{{\beta }^2}{2}{\Vert A{x}^{k+1}-A{x}^{*}\Vert }^2-\frac{{\beta }^2}{2}{\Vert B{x}^{*}-B{\tilde{y}}^k\Vert }^2\\ =-{\beta }^2\langle A{x}^{*}-A{x}^{k+1},B{\tilde{y}}^k-B{y}^{*}\rangle \end{array}$ (43)

所以(41)可以化为

$\begin{array}{c}{\Vert {\lambda }^{k+1}-{\lambda }^{*}\Vert }^2\le {\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+\left(1-{\alpha }_k^2-{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+{\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2\\ +{\Vert {\lambda }^{*}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k+\frac{1}{2}}\Vert }^2+\left({\beta }^2-2\beta \sigma \right){\Vert A\Vert }^2{\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ +\left({\beta }^2+{\alpha }_k\right){\Vert B{y}^k-B{y}^{*}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2+\left({\beta }^2{\alpha }_k^2+{\alpha }_k\right){\Vert B{y}^k-B{y}^{k-1}\Vert }^2\end{array}$ (44)

由算法的第4步和第6步可得

$\begin{array}{l}{\Vert {\lambda }^{*}-{\lambda }^{k+\frac{1}{2}}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k+\frac{1}{2}}\Vert }^2\\ ={\Vert {\lambda }^{*}-{\lambda }^{k+1}-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k+1}-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\Vert }^2\\ ={\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2+2\langle {\lambda }^k-{\lambda }^{*},{\lambda }^{k+\frac{1}{2}}-{\lambda }^{k+1}\rangle \\ ={\Vert {\lambda }^{*}-{\lambda }^{k+1}\Vert }^2-{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2+2\langle {\lambda }^k-{\lambda }^{*}\text{£,}{\tilde{\lambda }}^k+\beta \left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)-{\lambda }^{k+1}\rangle \end{array}$

(45)

代入(1.33)可得

$\begin{array}{c}{\Vert {\lambda }^{k+1}-{\lambda }^{*}\Vert }^2\le \left(1-{\alpha }_k^2-2{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-2{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+\left(1+{\alpha }_k\right){\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2\\ -2{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2+\left({\beta }^2-2\beta \sigma \right){\Vert A\Vert }^2{\Vert x^{k+1}-x^{*}\Vert }^2-{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ +\left({\beta }^2+{\alpha }_k\right){\Vert B{y}^k-B{y}^{*}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2+\left({\beta }^2{\alpha }_k^2+{\alpha }_k\right){\Vert B{y}^k-B{y}^{k-1}\Vert }^2\end{array}$ (46)

由于 $\beta \in \left(0,\frac{2\sigma }{{\Vert A\Vert }^2}\right)$

所以(45)可以化为

${\Vert {\lambda }^{k+1}-{\lambda }^{*}\Vert }^2\le \left(1-{\alpha }_k^2-2{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-2{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+\left(1+{\alpha }_k\right){\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2$ (47)

设 $P^k={\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2$ ，所以(46)可以化为

$\begin{array}{l}{P}^{k+1}\le \left(1-{\alpha }_k^2-2{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-2{\alpha }_k{P}^k+\left(1+{\alpha }_k\right)P^{k-1}\\ P^{k+1}+2{\alpha }_k{P}^k-\left(1+{\alpha }_k\right)P^{k-1}\le \left(1-{\alpha }_k^2-2{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\\ P^{k+1}+{\alpha }_k{P}^k+{\alpha }_k{P}^k-P^{k-1}-{\alpha }_k{P}^{k-1}\le \left(1-{\alpha }_k^2-2{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\\ P^{k+1}-P^{k-1}+{\alpha }_k{P}^k+{\alpha }_k\left(P^k-P^{k-1}\right)\le \left(1-{\alpha }_k^2-2{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\le {\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\end{array}$ (48)

对(45)进行整理可得

$\begin{array}{l}-\left({\beta }^2-2\beta \sigma \right){\Vert A\Vert }^2{\Vert x^{k+1}-x^{*}\Vert }^2+{\beta }^2{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2\\ \le \left(1-{\alpha }_k^2-2{\alpha }_k\right){\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2-2{\alpha }_k{\Vert {\lambda }^k-{\lambda }^{*}\Vert }^2+\left(1+{\alpha }_k\right){\Vert {\lambda }^{*}-{\lambda }^{k-1}\Vert }^2-2{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2\\ -{\Vert {\lambda }^{k+1}-{\lambda }^{*}\Vert }^2+\left({\beta }^2+{\alpha }_k\right){\Vert B{y}^k-B{y}^{*}\Vert }^2-{\alpha }_k{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2+\left({\beta }^2{\alpha }_k^2+{\alpha }_k\right){\Vert B{y}^k-B{y}^{k-1}\Vert }^2\end{array}$ (49)

对(48)两边同时求和

$\begin{array}{l}\left(2\beta \sigma -{\beta }^2\right){\Vert A\Vert }^2{\displaystyle \underset{k=0}{\overset{N}{\sum }}{\Vert x^{k+1}-x^{*}\Vert }^2}+{\beta }^2{\displaystyle \underset{k=0}{\overset{N}{\sum }}{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2}\\ \le \left(-1-{\alpha }_k^2-2{\alpha }_k\right){\displaystyle \underset{k=0}{\overset{N}{\sum }}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2}-2{\alpha }_k{\Vert {\lambda }^N-{\lambda }^{*}\Vert }^2+\left(1+{\alpha }_k\right){\Vert {\lambda }^{*}-{\lambda }^{N-1}\Vert }^2-{\Vert {\lambda }^{N+1}-{\lambda }^{*}\Vert }^2\\ +\left({\beta }^2+{\alpha }_k\right){\displaystyle \underset{k=0}{\overset{N}{\sum }}{\Vert B{y}^k-B{y}^{*}\Vert }^2}-{\alpha }_k{\displaystyle \underset{k=0}{\overset{N}{\sum }}{\Vert B{y}^{*}-B{y}^{k-1}\Vert }^2}+\left({\beta }^2{\alpha }_k^2+{\alpha }_k\right){\displaystyle \underset{k=0}{\overset{N}{\sum }}{\Vert B{y}^k-B{y}^{k-1}\Vert }^2}\end{array}$ (50)

上式两边同时取极限可以得到

$\underset{k\to +\infty }{\lim }{\Vert x^{k+1}-x^{*}\Vert }^2=0,\underset{k\to +\infty }{\lim }{\Vert B{y}^{k+1}-B{y}^{*}\Vert }^2=0$ (51)

因此

$x^{k+1}\to x^{*},y^{k+1}\to y^{*}$

①②得证。

由于 $L\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)\ge L\left(x^{*},y^{*},{\lambda }^{*}\right)$

由(12)式可得

$\begin{array}{l}f\left(x^{k+1}\right)+g\left(y^{k+1}\right)-\langle {\lambda }^{k+1},A{x}^{k+1}+B{y}^{k+1}-b\rangle \ge f\left(x^{*}\right)+g\left(y^{*}\right)-\langle {\lambda }^{*},A{x}^{*}+B{y}^{*}-b\rangle \\ f\left(x^{k+1}\right)+g\left(y^{k+1}\right)\ge f\left(x^{*}\right)+g\left(y^{*}\right)+\langle {\lambda }^{k+1},A{x}^{k+1}+B{y}^{k+1}-b\rangle \end{array}$ (52)

又 $\underset{k\to +\infty }{\lim }\left(A{x}^{k+1}+B{y}^{k+1}-b\right)=0$ ，所以(51)可以化为

$f\left(x^{k+1}\right)+g\left(y^{k+1}\right)\ge f\left(x^{*}\right)+g\left(y^{*}\right)$ (53)

由算法1第3步、第5步的一阶优化条件可得

$\begin{array}{l}0\in \partial f\left(x^{k+1}\right)-A^{*}{\tilde{\lambda }}^k\\ 0\in \partial g\left(y^{k+1}\right)-A^{*}{\tilde{\lambda }}^k+\beta B^{*}\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\end{array}$ (54)

即

$\begin{array}{l}{A}^{*}{\tilde{\lambda }}^k\in \partial f\left(x^{k+1}\right)\\ A^{*}{\tilde{\lambda }}^k-\beta B^{*}\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right)\in \partial g\left(y^{k+1}\right)\end{array}$ (55)

根据次微分定义可以得到

$\begin{array}{l}f\left(x^{*}\right)\ge f\left(x^{k+1}\right)+\langle A^{*}{\tilde{\lambda }}^k,x^{*}-x^{k+1}\rangle \\ g\left(y^{*}\right)\ge g\left(y^{k+1}\right)+\langle B^{*}{\tilde{\lambda }}^k-\beta B^{*}\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right),y^{*}-y^{k+1}\rangle \end{array}$ (56)

现在将(55)中两式相加可得

$f\left(x^{*}\right)+g\left(y^{*}\right)\ge f\left(x^{k+1}\right)+g\left(y^{k+1}\right)+\langle A^{*}{\tilde{\lambda }}^k,x^{*}-x^{k+1}\rangle +\langle B^{*}{\tilde{\lambda }}^k-\beta B^{*}\left(A{x}^{k+1}+B{\tilde{y}}^k-b\right),y^{*}-y^{k+1}\rangle$ (57)

又因为 $x^{k+1}\to x^{*}$ ， $y^{k+1}\to y^{*}$ ，所以(56)可以化为

$f\left(x^{*}\right)+g\left(y^{*}\right)\ge f\left(x^{k+1}\right)+g\left(y^{k+1}\right)$ (58)

结合(52)和(57)可以得到

$\underset{k\to +\infty }{\lim }f\left(x^{k+1}\right)+g\left(y^{k+1}\right)=f\left(x^{*}\right)+g\left(y^{*}\right)$ (59)

综上，定理1得证。

4. 数据分析

在本节中，我们将给出所提算法的数值分析，具体来说，我们比较了ADMM算法和惯性对称ADMM算法，我们采用以下目标函数和约束条件：

$\begin{array}{l}\underset{x,y}{\min }\left\{{\left(x-1\right)}^2+{\left(y-2\right)}^2\right\}\\ \text{s}\text{.t}.0\le x\le 3\\ 1\le y\le 4\\ 2x+3y=5\end{array}$ (60)

上式(60)的拉格朗日表达式为

$L\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)+{\lambda }^{\text{T}}\left(2x+3y-5\right)+\frac{\rho }{2}{\Vert 2x+3y-5\Vert }^2$ (61)

在迭代次数为30的情况下，ADMM和惯性对称ADMM算法如下图1所示。

Figure 1. Plot of results comparing ADMM and inertial ADMM

图1. ADMM和惯性ADMM比较结果图

注：由图可知本文新算法较ADMM在相同迭代次数下其目标函数值收敛速度相对较快。

5. 结论

提出求解目标函数的惯性对称ADMM算法，并进行了收敛性分析，最后，数值实验表明，新算法与ADMM算法相比较优越。