¹西安工程大学，理学院，陕西 西安

²琼台师范学院，体育学院，海南 海口

收稿日期：2023年12月13日；录用日期：2023年12月18日；发布日期：2024年1月26日

摘要

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

关键词

交替方向乘子法，收敛性，线性约束凸优化问题，惯性对称交替方向乘子法

Inertial Symmetric Alternating Direction Multiplier Algorithm

Mingzhu Tian¹, Meng Wen¹, Jun Li²

¹School of Science, Xi’an Polytechnic University, Xi’an Shaanxi

²College of Physical Education, Qiongtai Normal University, Haikou Hainan

Received: Dec. 13^th, 2023; accepted: Dec. 18^th, 2023; published: Jan. 26^th, 2024

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 proposed algorithm converges to the optimal solution of the original problem, and finally, the effectiveness and superiority of the proposed algorithm is verified through the data analysis.

Keywords:Alternating Direction Multiplier Method, Convergence, Linearly Constrained Convex Optimization Problems, Inertially Symmetric Alternating Direction Multiplier Method

Copyright © 2024 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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所示。

表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)