对于非凸非光滑不可分离问题的并行式惯性近端非精确ADMM算法

Parallel Inertial Proximal Inexact ADMM Algorithm for Nonconvex Nonsmooth and Nonseparable Problems

摘要: 交替方向乘子法(ADMM)作为一种简单有效的求解可分离问题方法，已经被广泛应用于信号处理、并行计算、机器学习等许多领域。但是当目标函数较为复杂时，ADMM算法的收敛性就会难以保证。针对一类复杂的非凸非光滑不可分离的优化问题，提出了一种非精确的并行式惯性近端交替乘子法(PIPI-ADMM)，在简单的参数假设下，算法产生的迭代序列收敛到增广拉格朗日函数的稳定点。另外，当增广拉格朗日函数满足Kurdyka-Lojasiewicz性质时，算法具有强收敛性。最后，数值实验结果表明，算法的迭代策略对求解具有显著的加速作用。

Abstract: The Alternating Direction Method of Multipliers (ADMM) has been widely applied in various fields such as signal processing, parallel computing, and machine learning due to its simplicity and effectiveness in solving separable problems. However, the convergence of the ADMM algorithm becomes challenging to guarantee when dealing with complex objective functions. For a class of complex, non-convex, non-smooth, and non-separable optimization problems, a novel Parallel Inexact Proximal Inertial Alternating Direction Method of Multipliers (PIPI-ADMM) is proposed. Under reasonable assumptions, the iterative sequence converges to a stationary point of the augmented Lagrange function. Moreover, with the help of Kurdyka-Lojasiewicz property, the proposed algorithm is strongly convergent. The numerical results show that the iterative strategy has significant acceleration.

1. 引言

本文考虑如下问题：

$\begin{array}{l}\underset{x,y,z}{\min }f\left(x\right)+g\left(y\right)+h\left(x,y,z\right)\\ \text{s}\text{.t}\text{.}Ax+By+Cz=b,\end{array}$ (1.1)

其中，$x\in {ℝ}^r,y\in {ℝ}^s,z\in {ℝ}^t$ 是函数变量，$f:{ℝ}^m\to ℝ\cup +\infty$ 和$g:{ℝ}^n\to ℝ\cup +\infty$ 是下半连续函数(可能非凸非光滑)，$h:{ℝ}^r\times {ℝ}^s\times {ℝ}^t\to ℝ$ 是连续可微函数，$A\in {ℝ}^{m\times s},B\in {ℝ}^{m\times s},C\in {ℝ}^{m\times t}$ 是给定的矩阵，$b\in {ℝ}^m$ 是给定的向量。问题(1.1)的增广拉格朗日函数(ALF)为

$L_{\beta }\left(x,y,z,\lambda \right)=f\left(x\right)+g\left(y\right)+h\left(x,y,z\right)-\langle \lambda ,A_1{x}_1+\cdots A_n{x}_n+By-b\rangle +\frac{\beta }{2}{\Vert Ax+By+Cz-b\Vert }^2,$ (1.2)

其中，$\lambda$ 是拉格朗日乘子，$\beta >0$ 是罚参数。

问题(1.1)是一类经典的具有线性约束的优化问题，广泛应用于压缩感知、稀疏信号恢复、图像处理、机器学习、矩阵分解等多个领域。在实际应用中，许多优化问题涉及非凸非光滑函数。非凸函数通常具有多个最小值和鞍点，这使得求解过程变得十分困难；非光滑函数往往在一些点不可微，甚至无法求导。因此，研究非凸非光滑情形下优化问题的求解方法具有重要的理论和实践意义。

交替方向乘子法(ADMM)作为一种高效求解具有多变量的约束优化算法，因其灵活度高，简单，处理速度快而被广泛使用于图像处理、统计学习等领域[1] [2]。在问题(1.1)中，当目标函数为凸函数时，ADMM算法及其扩展研究已经较为完善[3]-[5]。近年来，人们更加关注目标函数非凸时ADMM算法的收敛性以及求解速度问题。一些关于两块非凸问题的ADMM算法的收敛性研究已经被证明[6]-[8]，但随着变量的增加，对于三块和多块非凸问题，ADMM算法的收敛性证明非常具有挑战性。陈等[9]提出了一个反例说明了直接将ADMM算法从两块问题扩展到三块问题是不收敛的。因此许多学者通过一些更强的假设或者对算法进行适当的改进以提高算法的收敛性。邓等[10]发现，当矩阵$A_i$ 是正交的并且列满秩时，通过扩展两块到多块的雅各比配置可以保证算法的收敛性，王等[11]通过在子问题中加入Bregman修正，来证明非凸情况下的收敛性。

与此同时，随着数据维度以及区块数量逐渐增加，基于ADMM的加速算法逐渐被深入研究。一些学者将惯性技术与ADMM算法结合起来对算法进行加速：惯性技术本质上是通过考虑前两次的迭代信息以计算下一次迭代点，这样就避免了相邻两次迭代之间剧烈的变化。Attouch [12]提出了惯性近端ADMM算法，其外推步结合了Nestrov的梯度加速算法。王等[13]使用了一种加权Frobenius范数的惯性形式，并使用了部分对称思想对算法进行加速。徐等[14]在ADMM算法中将Bregman距离和惯性技术结合起来解决非凸非光滑问题。

在求解过程中，当目标函数较为复杂时，ADMM算法可能无法推导出子问题的显示表达式或求解速度很慢。面对这种情况，一种思想是通过将一个困难的问题近似成为一个简单问题，通过牺牲求解的准确性以提高求解速度。目前，非精确的惯性ADMM算法[15]-[17]多用于求解可分离的凸优化问题，针对非凸同时具有不可分离结构的相关研究还很少，受以上文献启发，本文针对问题(1.1)，提出了一种并行式惯性近端非精确ADMM (PIPI-ADMM)算法，该算法在交替方向法的基础上，通过对每个子问题的增广拉格朗日函数进行部分一阶近似，使得近似信息可以并行发送到每个子问题的求解过程中。同时结合惯性技术与近端算法，分别在$x,y,z$ 子问题中加入近端项，在$x,y$ 子问题中引入惯性项来加速求解过程。此外，在简单合理的的假设下，当正则化的增广拉格朗日函数满足Kurdyka-Lojasiewicz性质时，文章证明了算法针对非凸非光滑问题的强收敛性。最后，文章总结了算法在鲁棒性主成分分析(Robust PCA)问题中的表现，验证了该算法的有效性。

本文的剩余部分组织结构如下：第2节给出了一些基础的定义以及与收敛性证明相关的预备知识；第3节提出了PIPI-ADMM算法，并证明了算法的收敛性；第4节是数值实验部分，通过分析算法在实际问题中的性能验证算法的有效性；最后在第5节得出了结论。

2. 预备知识

本节给出文中所用记号的意义以及相关概念与性质。

${ℝ}^n$ 表示$n$ 维欧氏空间，$\Vert ·\Vert$ 表示欧式范数，$\langle x,y\rangle =x^{\text{T}}y={\displaystyle {\sum }_{i=1}^n{x}_i{y}_i}$ ，对于矩阵$A$ ，其像空间被定义为$\mathrm{Im}A:=\left(Ax:x\in {ℝ}^n\right)$ ，表示在像空间$\mathrm{Im}A$ 上的欧式投影。文章使用${\delta }_{\min (A^{\text{T}}A)}$ 表示矩阵$A^{\text{T}}A$ 的最小特征值。设集合$S\subseteq {ℝ}^n$ ，点$x\in {ℝ}^n$ ，将点$x$ 到集合$S$ 的距离记作$d\left(x,S\right)=\underset{y\in S}{\inf }\Vert y-x\Vert .$ 当$S=\varnothing$ 时，定义$d\left(x,S\right)=+\infty$ 。对于函数$f$ ，其定义域记作$\text{dom}f$ ，即$\text{dom}f:=\left\{x\in {ℝ}^n:f\left(x\right)<+\infty \right\}$ 。函数$f$ 称为正常函数当且仅当$\text{dom}f\ne \varnothing$ 且$f>-\infty$ 。

定义2.1 [18]若函数$f$ 在$x_0$ 处满足$f\left(x_0\right)\le \underset{x\to x_0}{\lim \inf }f\left(x\right)$ ，则称函数$f$ 在$x_0$ 处下半连续。若函数$f$ 在$\mathrm{dom}f$ 内每点处均下半连续，则称$f$ 为下半连续函数。

定义2.2 [18]设函数$f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ 正常下半连续，则

i) 函数$f$ 在$x\in domf$ 处的Fréchet次微分记为

$\widehat{\partial }f\left(x\right)=\left\{x^{*}\in {ℝ}^n:\underset{y\ne x,y\to x}{\lim \inf }\frac{f\left(y\right)-f\left(x\right)-\langle x^{*},y-x\rangle }{\Vert y-x\Vert }\ge 0\right\},$

当$x\notin \mathrm{dom}f$ 时，记$\widehat{\partial }f\left(x\right)=\varnothing$ 。

ii) 函数在$x\in domf$ 处的极限次微分记为

$\partial f\left(x\right)=\left\{x^{*}\in {ℝ}^n:\exists x_k\to x,f\left(x_k\right)\to f\left(x\right),{\widehat{x}}_k\in \widehat{\partial }f\left(x_k\right),{\widehat{x}}_k\to x^{*}\right\}.$

注[18]：设$f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ 及$g:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ 为正常下半连续函数，则下列结论成立

1) $\forall x\in {ℝ}^n$ ，有$\widehat{\partial f}\left(x\right)\subseteq \partial f\left(x\right)$ ，其中$\widehat{\partial f}\left(x\right)$ 是闭凸的，而$\partial f\left(x\right)$ 是凸的。

2) 若$x_k^{*}\in \partial f\left(x_k\right)$ 且$\underset{k\to +\infty }{\lim }\left(x_k,x_k^{*}\right)=\left(x,x^{*}\right)$ ，则$x^{*}\in \partial f\left(x\right)$ ，这表明$\partial f\left(x\right)$ 是闭的。

3) 设$x\in {ℝ}^n$ 为$f$ 的极小值点，则$0\in \partial f\left(x\right)$ 。若$0\in \partial f\left(x\right)$ ，称$x$ 为$f$ 的稳定点，$f$ 的稳定点集记作$\text{crit}f.$

4) 若$g:{ℝ}^n\to ℝ$ 连续可微，则$\partial \left(f+g\right)=\partial f\left(x\right)+\nabla g\left(x\right),\forall x\in \mathrm{dom}f.$

定义2.3 $\left(x^{*},y^{*},{\lambda }^{*}\right)$ 为问题(1.1)的增广拉格朗日函数的稳定点，即$0\in \partial L_{\beta }\left({\omega }^{*}\right)$ ，当且仅当

$\{\begin{array}{l}-{\nabla }_{x}h\left(x^{\ast },y^{\ast },z^{*}\right)+A^{\text{T}}{\lambda }^{\ast }\in \partial f\left(x^{\ast }\right),\hfill \\ \begin{array}{l}-{\nabla }_{y}h\left(x^{\ast },y^{\ast },z^{*}\right)+B^{\text{T}}{\lambda }^{\ast }=\partial g\left(y^{\ast }\right),\\ -{\nabla }_{z}h\left(x^{\ast },y^{\ast },z^{*}\right)+C^T{\lambda }^{*}=0,\end{array}\hfill \\ A{x}^{\ast }+B{y}^{\ast }+C{z}^{*}-b=0.\hfill \end{array}$

定义2.4 [19] (Kurdyka-Lojasiewicz性质)设函数$f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ 为正常下半连续函数，若存在$\eta >0,x^{*}$ 的邻域$U$ 及连续凹函数$\phi :\left[0,\eta \right)\to {ℝ}^{+}$ 满足如下条件：

1)$\phi \left(0\right)=0$ ；

2) $\phi$ 在$\left(0,\eta \right)$ 连续可微的且在0处连续；

3) $\forall t\in \left(0,\eta \right)$ ，${\phi }^{\prime }\left(t\right)>0$ ；

4) $\forall x\in U\cap \left[f\left(x^{*}\right)<f\left(x\right)<f\left(x^{*}\right)+\eta \right]$ ，有如下Kurdyka-Lojasiewicz不等式成立：

${\phi }^{\prime }\left(f\left(x\right)-f\left(x^{*}\right)\right)d\left(0,\partial f\left(x\right)\right)\ge 1$ ,

则称函数$f$ 在$x^{\ast }\in \text{dom}\partial f$ 处具有Kurdyka-Lojasiewicz (KL)性质。

Kurdyka-Lojasiewicz (KL)性质主要适用于非凸非光滑优化问题。此类问题由于目标函数结构复杂，通常缺乏传统凸优化中的全局收敛性保证。KL性质通过对目标函数的局部增长特性进行限制，使得即便在非凸优化中也能获得一定的收敛性保证。对于特定结构的函数(例如半代数函数和半解析函数)，KL性质在其定义域上表现出良好的适用性。在实际应用中，很多函数都满足KL性质。例如$L_p$ 范数，Relu激活函数等都满足KL性质，这使得KL性质在非凸非光滑问题的收敛性证明中具有重要作用。

引理2.1 [20]设$A\in {ℝ}^{m\times n}$ 为非零矩阵，${\delta }_{\min (A^{\text{T}}A)}$ 为该矩阵得最小特征值，则

(2.1)

其中，表示在像空间上的欧氏投影。

引理2.2 若函数连续可微，且其梯度是-Lipschitz连续的，则

(2.2)

证明

如果取，由不等式，此时有

引理2.3 [21] (一致KL性质)设是紧集，函数是正常下半连续函数，若函数在上是常数且在上得每个点都满足KL性质，那么存在，，，使得对于任意以及有

3. 算法与其收敛性分析

本节将给出针对问题(1.1)的并行式惯性近端非精确ADMM算法(PIPI-ADMM)，并证明其收敛性。

3.1. 算法及假设

算法通过使用一阶近似的方法，非精确求解每一个子问题的值，进而达到对算法的加速效果。对于每个子问题，定义其增广拉格朗日函数在第k次迭代处的一种一阶近似为：

由此，算法的迭代框架如下：

(3.1)

(3.2)

(3.3)

算法1：并行式惯性近端非精确ADMM算法

a) 对于给定的使，其中，。

b) 依次迭代

(3.4)

c) 终止准则：计算

或$c_2=A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\le {\epsilon }_2.$

在下文中，为简便证明过程，记$\left\{{\omega }^k\right\}$ 为算法产生的迭代序列，且

$\begin{array}{l}u=\left(x,y,z\right),u^k=\left(x^k,y^k,z^k\right),\omega =\left(x,y,z,\lambda \right),{\omega }^k=\left(x^k,y^k,z^k,{\lambda }^k\right),{\omega }^{*}=\left(x^{*},y^{*},z^{*},{\lambda }^{*}\right),\\ \widehat{\omega }=\left(x,y,z,\lambda ,x^{\prime },y^{\prime },z^{\prime }\right),{\widehat{\omega }}^{k+1}=\left(x^{k+1},y^{k+1},z^{k+1},{\lambda }^{k+1},x^k,y^k,z^k\right)，\\ \Delta x^{k+1}={\Vert x^{k+1}-x^k\Vert }^2,\Delta y^{k+1}={\Vert y^{k+1}-y^k\Vert }^2,\Delta z^{k+1}={\Vert z^{k+1}-z^k\Vert }^2,\Delta u^{k+1}={\Vert u^{k+1}-u^k\Vert }^2\end{array}$ (3.5)

注：在算法设计中，我们采用了非精确求解思想和惯性思想来加速算法的迭代求解。非精确思想如(3.1)~(3.3)所示，在求解子问题过程中，不追求精确地求解每一个子问题的解，而是通过求解耦合项的一阶近似，来获得一个近似解，以此来加快求解速度。这种方法通常用于大型或复杂的优化问题中，能够在计算量较小的情况下实现快速求解。惯性近端思想被应用在了(3.4)的子问题中。其中，惯性近端项为：

$\frac{{\tau }_x^k}{2}{\Vert x-x^k\Vert }^2+{\rho }_x^k\left(x,x^k-x^{k-1}\right)和\frac{{\tau }_y^k}{2}{\Vert y-y^k\Vert }^2+{\rho }_y^k\left(y,y^k-y^{k-1}\right).$

惯性技术通过在第$k+1$ 次迭代过程中考虑前两次迭代的信息$x^k,y^k,x^{k-1},y^{k-1}$ ，使得算法可以加速向最优点逼近。特别是在面对非凸目标函数时，惯性技术可以更快速的跳过鞍点或局部最小值，在不增加计算量的前提下减少整体迭代次数，提升算法的性能。

下面，我们证明算法1的收敛性。首先，算法1的收敛性分析需要满足如下假设：

假设3.1

1) 函数$f:{ℝ}^m\to ℝ\cup +\infty$ 和$g:{ℝ}^n\to ℝ\cup +\infty$ 是正常下半连续函数；

2) 函数$h:{ℝ}^r\times {ℝ}^s\times {ℝ}^t\to ℝ$ 是连续可微函数且其梯度$\nabla h$ 是模$l_h$ -Lipschiz连续，即

$\nabla h\left(a\right)-\nabla h\left(b\right)\le \Vert a-b\Vert ;$

3) 矩阵$A,B,C$ 满足$C\ne 0$ ，且$\mathrm{Im}\left(C\right)\supset \left\{b\right\}\cup \mathrm{Im}\left(A\right)\cup \mathrm{Im}\left(B\right)$ ；

4) 算法参数选取满足：$\beta >l_h+{\left({\tau }_z^k\right)}^2/{\delta }_{\min (C^{T}C)}$ ，$\min \left\{{\tau }_x,{\tau }_y,{\tau }_z\right\}\ge l_h+2\max \left\{{\rho }_x,{\rho }_y\right\}+4$ 。

注：注意到，我们的算法的参数选择仅仅需要满足假设3.1(4)即可。该参数假设被使用在后文引理3.2的证明中，用以保证增广拉格朗日函数序列的单调性。在算法设计中，$l_h,{\rho }_x^0,{\rho }_y^0$ ，均为已知或已设置的常数，因此在参数选择中，我们只需令${\tau }_x^0,{\tau }_y^0,{\tau }_z^0$ 和$\beta$ 足够大，即可保证算法是收敛的。

3.2. 收敛性证明

引理3.1 在算法1中，对于任意的$k\in \mathbb{N}$ ，下列不等式成立：

${\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2\le \frac{3l_h}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_x^{k+1}+\frac{3l_h}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_y^{k+1}+\frac{3\left(l_h+{\left({\tau }_z^k\right)}^2\right)}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_z^{k+1}+\frac{3{\left({\tau }_z^k\right)}^2}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_z^k.$ (3.6)

证明 根据(3.4)中$z$ 子问题的最优条件得

$0={\nabla }_{z}h\left(x^k,y^k,z^k\right)-C^{\text{T}}{\lambda }^k+\beta C^{\text{T}}\left(A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\right)+{\tau }_z^k\left(z^{k+1}-z^k\right).$ (3.7)

将(3.4)中第四式代入(3.7)中，得到

$\begin{array}{l}{\Vert C^{\text{T}}{\lambda }^{k+1}-C^{\text{T}}{\lambda }^k\Vert }^2\\ ={\Vert {\nabla }_{z}h\left(x^k,y^k,z^k\right)-{\nabla }_{z}h\left(x^{k-1},y^{k-1},z^{k-1}\right)+{\tau }_z^k\Delta z^{k+1}-{\tau }_z^{k-1}\Delta y^k\Vert }^2\\ ={\Vert {\nabla }_{z}h\left(x^k,y^k,z^k\right)-{\nabla }_{z}h\left(x^{k-1},y^{k-1},z^{k-1}\right),{\tau }_z^{k-1}\Delta z^k\Vert }^2+{\Vert {\tau }_z^k\Delta z^{k+1}\Vert }^2+{\Vert {\tau }_z^{k-1}\Delta z^k\Vert }^2\\ -2\langle {\tau }_z^k\Delta z^{k+1},{\tau }_z^{k-1}\Delta z^k\rangle -2\langle {\nabla }_{z}h\left(x^k,y^k,z^k\right)-{\nabla }_{z}h\left(x^{k-1},y^{k-1},z^{k-1}\right),{\tau }_z^{k-1}\Delta z^k\rangle \end{array}$

$\begin{array}{l}+2\langle {\nabla }_{z}h\left(x^k,y^k,z^k\right)-{\nabla }_{z}h\left(x^{k-1},y^{k-1},z^{k-1}\right),{\tau }_z^k\Delta z^{k+1}\rangle \\ \le 3l_h^2{\Vert \Delta x^k\Vert }^2+3l_h^2{\Vert \Delta y^k\Vert }^2+3l_h^2{\Vert \Delta z^k\Vert }^2+3{\tau }_z^{k^2}{\Vert \Delta z^{k+1}\Vert }^2+3{\tau }_z^{k^2}{\Vert \Delta z^k\Vert }^2\end{array}$

根据引理2.1可得

${\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2\le \frac{3l_h}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_x^{k+1}+\frac{3l_h}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_y^{k+1}+\frac{3\left(l_h+{\left({\tau }_z^k\right)}^2\right)}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_z^{k+1}+\frac{3{\left({\tau }_z^k\right)}^2}{{\delta }_{\min (C^{\text{T}}C)}}{\Delta }_z^k.$

由此，引理得证。 □

为了证明收敛性，确定增广拉格朗日函数得单调性是非常必要的。但是由于算法添加了惯性项，直接证明增广拉格朗日函数单调非常困难。因此通过构建正则化的增广拉格朗日函数${\widehat{L}}_{\beta }\left({\widehat{\omega }}^{k+1}\right)$ ，借助${\widehat{L}}_{\beta }\left({\widehat{\omega }}^{k+1}\right)$ 的单调性来证明算法的收敛性。正则化的增广拉格朗日函数定义如下：

$\begin{array}{l}{\widehat{L}}_{\beta }\left({\widehat{\omega }}^{k+1}\right)={\widehat{L}}_{\beta }\left(u^{k+1},{\lambda }^{k+1},u^k\right)=L_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)+\alpha \left({\Vert u^{k+1}-u^k\Vert }^2\right).\hfill \end{array}$ (3.8)

其中，$\widehat{\omega }$ 的定义见式(3.5)。

引理3.2 对于算法1，选择足够大的$\beta ,{\tau }_x^0,{\tau }_y^0,{\tau }_z^0,$ 使得

$\begin{array}{l}\beta >l_h+{\left({\tau }_z^k\right)}^2/{\delta }_{\min (C^{T}C)},\\ \min \left\{{\tau }_x,{\tau }_y,{\tau }_z\right\}\ge l_h+2\max \left\{{\rho }_x,{\rho }_y\right\}+4,\end{array}$ (3.9)

则对于$\forall k\in \mathbb{N}$ ，有

$\begin{array}{l}{\widehat{L}}_{\beta }\left(u^{k+1},{\lambda }^{k+1},u^k\right)=L_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)+{\alpha }_1{\Delta }_u^{k+1}\\ \le L_{\beta }\left(u^k,{\lambda }^k\right)+{\alpha }_2{\Delta }_u^k\le L_{\beta }\left(u^k,{\lambda }^k\right)+{\alpha }_1{\Delta }_u^k={\widehat{L}}_{\beta }\left(u^k,{\lambda }^k,u^{k-1}\right),\end{array}$ (3.10)

其中，${\alpha }_1=\min \left\{\frac{{\tau }_x^k-l_h-{\rho }_x^k}{2}-1,\frac{{\tau }_y^k-l_h-{\rho }_y^k}{2}-1,\frac{{\tau }_z^k-l_h}{2}-1\right\},$ ${\alpha }_2=\max \left\{\frac{{\rho }_x^k}{2},\frac{{\rho }_y^k}{2},1\right\}.$

证明 根据(3.4)第一式得：

$\begin{array}{c}f\left(x^{k+1}\right)+g\left(y^k\right)+\langle {\nabla }_{x}h\left(x^k,y^k,z^k\right),x^{k+1}-x^k\rangle -\langle {\lambda }^k,A{x}^{k+1}+B{y}^k+C{z}^k-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^k+C{z}^k-b\Vert }^2+\frac{{\tau }_x^k}{2}{\Delta }_x^{k+1}+{\rho }_x^k\langle x^{k+1},x^k-x^{k-1}\rangle \\ \le f\left(x^k\right)+g\left(y^k\right)-\langle {\lambda }^k,A{x}^k+B{y}^k+C{z}^k-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^k+B{y}^k+C{z}^k-b\Vert }^2+{\rho }_x^k\langle x^k,x^k-x^{k-1}\rangle ,\end{array}$

根据(3.4)第二式得：

$\begin{array}{c}f\left(x^{k+1}\right)+g\left(y^{k+1}\right)+\langle {\nabla }_{y}h\left(x^k,y^k,z^k\right),y^{k+1}-y^k\rangle -\langle {\lambda }^k,A{x}^{k+1}+B{y}^{k+1}+C{z}^k-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}+C{z}^k-b\Vert }^2+\frac{{\tau }_y^k}{2}{\Delta }_y^{k+1}+{\rho }_y^k\langle y^{k+1},y^k-y^{k-1}\rangle \\ \le f\left(x^{k+1}\right)+g\left(y^k\right)-\langle {\lambda }^k,A{x}^{k+1}+B{y}^k+C{z}^k-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^k+C{z}^k-b\Vert }^2+{\rho }_y^k\langle y^k,y^k-y^{k-1}\rangle ,\end{array}$

根据(3.4)第三式得：

$\begin{array}{l}f\left(x^{k+1}\right)+g\left(y^{k+1}\right)+\langle {\nabla }_{z}h\left(x^k,y^k,z^k\right),z^{k+1}-z^k\rangle -\langle {\lambda }^k,A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\Vert }^2+\frac{{\tau }_z^k}{2}{\Delta }_z^{k+1}\\ \le f\left(x^{k+1}\right)+g\left(y^{k+1}\right)-\langle {\lambda }^k,A{x}^{k+1}+B{y}^{k+1}+C{z}^k-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}+C{z}^k-b\Vert }^2,\end{array}$

将上述三个不等式相加，得到

$\begin{array}{c}f\left(x^{k+1}\right)+g\left(y^{k+1}\right)-\langle {\lambda }^k,A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\Vert }^2\\ \langle {\nabla }_{y}h\left(x^k,y^k,z^k\right),y^{k+1}-y^k\rangle +\langle {\nabla }_{x}h\left(x^k,y^k,z^k\right),x^{k+1}-x^k\rangle +\langle {\nabla }_{z}h\left(x^k,y^k,z^k\right),z^{k+1}-z^k\rangle \\ +\frac{{\tau }_x^k}{2}{\Delta }_x^{k+1}+\frac{{\tau }_y^k}{2}{\Delta }_y^{k+1}+\frac{{\tau }_x^k}{2}{\Delta }_x^{k+1}\\ \le f\left(x^k\right)+g\left(y^k\right)-\langle {\lambda }^k,A{x}^k+B{y}^k+C{z}^k-b\rangle +\frac{\beta }{2}{\Vert A{x}^k+B{y}^k+C{z}^k-b\Vert }^2\\ +{\rho }_x^k\langle x^k-x^{k+1},x^k-x^{k-1}\rangle +{\rho }_y^k\langle y^k-y^{k+1},y^k-y^{k-1}\rangle .\end{array}$

根据三角不等式$\langle a,b\rangle \le \frac{1}{2}{\Vert a\Vert }^2+\frac{1}{2}{\Vert b\Vert }^2$ 得到

$\begin{array}{c}f\left(x^{k+1}\right)+g\left(y^{k+1}\right)-\langle {\lambda }^k,A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\Vert }^2\\ \langle {\nabla }_{y}h\left(x^k,y^k,z^k\right),y^{k+1}-y^k\rangle +\langle {\nabla }_{x}h\left(x^k,y^k,z^k\right),x^{k+1}-x^k\rangle +\langle {\nabla }_{z}h\left(x^k,y^k,z^k\right),z^{k+1}-z^k\rangle \\ +\frac{{\tau }_x^k}{2}{\Delta }_x^{k+1}+\frac{{\tau }_y^k}{2}{\Delta }_y^{k+1}+\frac{{\tau }_z^k}{2}{\Delta }_z^{k+1}\\ \le f\left(x^k\right)+g\left(y^k\right)-\langle {\lambda }^k,A{x}^k+B{y}^k+C{z}^k-b\rangle +\frac{\beta }{2}{\Vert A{x}^k+B{y}^k+C{z}^k-b\Vert }^2\\ +\frac{{\rho }_x^k}{2}{\Delta }_x^{k+1}+\frac{{\rho }_x^k}{2}{\Delta }_x^k+\frac{{\rho }_y^k}{2}{\Delta }_y^{k+1}+\frac{{\rho }_y^k}{2}{\Delta }_y^k.\end{array}$

通过变换得到

$\begin{array}{l}f\left(x^k\right)+g\left(y^k\right)+h\left(x^k,y^k,z^k\right)-\langle {\lambda }^k,A{x}^k+B{y}^k+C{z}^k-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^k+B{y}^k+C{z}^k-b\Vert }^2+\frac{{\rho }_x^k}{2}{\Delta }_x^{k+1}+\frac{{\rho }_x^k}{2}{\Delta }_x^k+\frac{{\rho }_y^k}{2}{\Delta }_y^{k+1}+\frac{{\rho }_y^k}{2}{\Delta }_y^k.\\ \ge f\left(x^{k+1}\right)+g\left(y^{k+1}\right)+h\left(x^{k+1},y^{k+1},z^{k+1}\right)-\langle {\lambda }^k,A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\Vert }^2\\ -\left(h\left(x^{k+1},y^{k+1},z^{k+1}\right)-h\left(x^k,y^k,z^k\right)-\langle {\left(\begin{array}{c}{\nabla }_{x}h\left(x^k,y^k,z^k\right)\\ {\nabla }_{y}h\left(x^k,y^k,z^k\right)\\ {\nabla }_{z}h\left(x^k,y^k,z^k\right)\end{array}\right)}^{\text{T}},\left(\begin{array}{c}{x}^{k+1}-x^k\\ y^{k+1}-y^k\\ z^{k+1}-z^k\end{array}\right)\rangle \right)+\frac{{\tau }_x^k}{2}{\Delta }_x^{k+1}+\frac{{\tau }_y^k}{2}{\Delta }_y^{k+1}+\frac{{\tau }_z^k}{2}{\Delta }_z^{k+1}\end{array}$

$\begin{array}{l}\ge f\left(x^{k+1}\right)+g\left(y^{k+1}\right)+h\left(x^{k+1},y^{k+1},z^{k+1}\right)-\langle {\lambda }^k,A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\Vert }^2\\ -\frac{l_h}{2}\left({\Delta }_x^{k+1}+{\Delta }_y^{k+1}+{\Delta }_z^{k+1}\right)+\frac{{\tau }_x^k}{2}{\Delta }_x^{k+1}+\frac{{\tau }_y^k}{2}{\Delta }_y^{k+1}+\frac{{\tau }_z^k}{2}{\Delta }_z^{k+1},\end{array}$

其中，最后一个不等式是由引理2.2得到的。由此得到

$\begin{array}{l}{L}_{\beta }\left(x^{k+1},y^{k+1},z^{k+1},{\lambda }^k\right)+\frac{{\tau }_x^k-l_h-{\rho }_x^k}{2}{\Delta }_x^{k+1}+\frac{{\tau }_y^k-l_h-{\rho }_y^k}{2}{\Delta }_y^{k+1}+\frac{{\tau }_z^k-l_h}{2}{\Delta }_z^{k+1}\\ \le L_{\beta }\left(x^k,y^k,z^k,{\lambda }^k\right)+\frac{{\rho }_x^k}{2}{\Delta }_x^k+\frac{{\rho }_y^k}{2}{\Delta }_y^k.\end{array}$ (3.11)

由(1.2)式，

$\begin{array}{l}{L}_{\beta }\left(x^{k+1},y^{k+1},z^{k+1},{\lambda }^{k+1}\right)-L_{\beta }\left(x^{k+1},y^{k+1},z^{k+1},{\lambda }^k\right)\\ =\langle {\lambda }^k-{\lambda }^{k+1},A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}\rangle =\frac{1}{\beta }{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2\\ \le \frac{l_h}{\beta {\delta }_{\min (C^{\text{T}}C)}}{\Delta }_x^{k+1}+\frac{l_h}{\beta {\delta }_{\min (C^{\text{T}}C)}}{\Delta }_y^{k+1}+\frac{l_h+{\left({\tau }_z^k\right)}^2}{\beta {\delta }_{\min (C^{\text{T}}C)}}{\Delta }_z^{k+1}+\frac{{\left({\tau }_z^k\right)}^2}{\beta {\delta }_{\min (C^{\text{T}}C)}}{\Delta }_z^k.\end{array}$ (3.12)

将(3.11)式与(3.12)式相加，得到

$\begin{array}{c}{L}_{\beta }\left(x^{k+1},y^{k+1},z^{k+1},{\lambda }^{k+1}\right)+\left(\frac{{\tau }_x^k-l_h-{\rho }_x^k}{2}-\frac{l_h}{\beta {\delta }_{\min (C^{\text{T}}C)}}\right){\Delta }_x^{k+1}+\left(\frac{{\tau }_y^k-l_h-{\rho }_y^k}{2}-\frac{l_h}{\beta {\delta }_{\min (C^{\text{T}}C)}}\right){\Delta }_y^{k+1}\\ +\left(\frac{{\tau }_z^k-l_h}{2}-\frac{l_h+{\left({\tau }_z^k\right)}^2}{\beta {\delta }_{\min (C^{\text{T}}C)}}\right){\Delta }_z^{k+1}\\ \le L_{\beta }\left(x^k,y^k,z^k,{\lambda }^k\right)+\frac{{\rho }_x^k}{2}{\Delta }_x^k+\frac{{\rho }_y^k}{2}{\Delta }_y^k+\frac{{\left({\tau }_z^k\right)}^2}{\beta {\delta }_{\min (C^{\text{T}}C)}}{\Delta }_z^k.\end{array}$

由于$\frac{3\left(l_h^2+{\left({\tau }_z^k\right)}^2\right)}{\beta {\delta }_{\min (C^{\text{T}}C)}}<\frac{3\left(l_h^2+{\left({\tau }_z^0\right)}^2\right)}{\beta {\delta }_{\min (C^{\text{T}}C)}}<1$ ，则

$\begin{array}{l}{L}_{\beta }\left(x^{k+1},y^{k+1},z^{k+1},{\lambda }^{k+1}\right)+\left(\frac{{\tau }_x^k-l_h-{\rho }_x^k}{2}-1\right){\Delta }_x^{k+1}+\left(\frac{{\tau }_y^k-l_h-{\rho }_y^k}{2}-1\right){\Delta }_y^{k+1}+\left(\frac{{\tau }_z^k-l_h}{2}-1\right){\Delta }_z^{k+1}\\ \le L_{\beta }\left(x^k,y^k,z^k,{\lambda }^k\right)+\frac{{\rho }_x^k}{2}{\Delta }_x^k+\frac{{\rho }_y^k}{2}{\Delta }_y^k+{\Delta }_z^k.\end{array}$

由于$\min \left\{{\tau }_x^0,{\tau }_y^0,{\tau }_z^0\right\}\ge l_h+2\max \left\{{\rho }_x^0,{\rho }_y^0\right\}+4,$ 由算法参数定义， $\min \left\{{\tau }_x^k,{\tau }_y^k,{\tau }_z^k\right\}\ge l_h+2\max \left\{{\rho }_x^k,{\rho }_y^k\right\}+4,$ 令${\alpha }_1=\min \left\{\frac{{\tau }_x^0-l_h-{\rho }_x^0}{2}-1,\frac{{\tau }_y^0-l_h-{\rho }_y^0}{2}-1,\frac{{\tau }_z^0-l_h}{2}-1\right\},$ ${\alpha }_2=\max \left\{\frac{{\rho }_x^0}{2}+1,\frac{{\rho }_y^0}{2}+1\right\}$ ，根据(3.9)式有

$L_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)+{\alpha }_2{\Vert \Delta u^{k+1}\Vert }^2+\nu {\Vert \Delta u^{k+1}\Vert }^2\le L_{\beta }\left(u^k,{\lambda }^k\right)+{\alpha }_2{\Vert \Delta u^k\Vert }^2.$

由于${\alpha }_2\le {\alpha }_1$ ，$\upsilon ={\alpha }_1-{\alpha }_2$ ，则$\nu >0$ 。在(3.8)式中，令$\alpha ={\alpha }_2,$ 则(3.10)式成立，引理得证。 □

引理3.3 考虑算法1生成的序列${\omega }^k$ ，存在常数$C>0$ 使得

$d\left(0,\partial L_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)\right)\le C\left(\Vert {\Delta }_x^{k+1}\Vert +\Vert {\Delta }_y^{k+1}\Vert +\Vert {\Delta }_z^{k+1}\Vert +\Vert {\Delta }_x^k\Vert +\Vert {\Delta }_y^k\Vert +\Vert {\Delta }_z^k\Vert \right)$ (3.13)

证明 根据增广拉格朗日函数的定义，得到

$\{\begin{array}{l}{\partial }_x{L}_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)=\partial f\left(x^{k+1}\right)+{\nabla }_{x}h\left(u^{k+1}\right)-A^{\text{T}}\left({\lambda }^{k+1}-\beta r^{k+1}\right),\\ {\partial }_y{L}_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)=\partial g\left(x^{k+1}\right)+{\nabla }_{y}h\left(u^{k+1}\right)-B^{\text{T}}\left({\lambda }^{k+1}-\beta r^{k+1}\right),\\ {\partial }_z{L}_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)={\nabla }_{z}h\left(u^{k+1}\right)-C^{\text{T}}\left({\lambda }^{k+1}-\beta r^{k+1}\right),\\ {\partial }_{\lambda }{L}_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)=r^{k+1}.\end{array}$

根据算法迭代的最优条件(3.4)，推出

$\{\begin{array}{l}0\in {\partial }_{x}f\left(x^{k+1}\right)+{\nabla }_{x}h\left(x^k,y^k,z^k\right)-A^{\text{T}}{\lambda }^k-\beta A^{\text{T}}\left(A{x}_1^{k+1}+B{y}^k+C{z}^k-b\right)+{\tau }_x^k\left(x^{k+1}-x^k\right)+{\rho }_x^k\left(x_{}^{k-1}-x_{}^k\right),\\ 0\in {\partial }_{y}g\left(y^{k+1}\right)+{\nabla }_{y}h(x^k,y^k,z^k)-B^{\text{T}}{\lambda }^k-\beta B^{\text{T}}\left(A{x}_1^{k+1}+B{y}^{k+1}+C{z}^k-b\right)+{\tau }_y^k\left(y^{k+1}-y^k\right)+{\rho }_y^k\left(y_{}^{k-1}-y_{}^k\right),\\ 0={\nabla }_{z}h\left(x^k,y^k,z^k\right)-C^{\text{T}}{\lambda }^k-\beta C^{\text{T}}\left(A{x}_1^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\right)+{\tau }_z^k\left(z^{k+1}-z^k\right),\\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+B{y}^{k+1}+C{z}^{k+1}-b\right)\end{array}$ (3.14)

将上述两个式子结合在一起，得到$\left({\zeta }_x^{k+1},{\zeta }_y^{k+1},{\zeta }_z^{k+1},{\zeta }_{\lambda }^{k+1}\right)\in \partial L_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)$ ，其中，

$\{\begin{array}{l}{\zeta }_x^{k+1}={\nabla }_{x}g\left(u^{k+1}\right)-{\nabla }_{x}g\left(u\right)-A^{\text{T}}\left({\lambda }^k-{\lambda }^{k+1}\right)+\beta A^{\text{T}}B\left(y^{k+1}-y^k\right)+\beta A^{\text{T}}C\left(z^{k+1}-z^k\right)\\ +{\tau }_x^k\left(x^{k+1}-x^k\right)+{\rho }_x^k\left(x_{}^{k-1}-x_{}^k\right)\\ {\zeta }_y^{k+1}={\nabla }_{y}g\left(u^{k+1}\right)-{\nabla }_{y}g\left(u\right)-B^{\text{T}}\left({\lambda }^k-{\lambda }^{k+1}\right)+\beta B^{\text{T}}C\left(z^{k+1}-z^k\right)+{\tau }_y^k\left(y^{k+1}-y^k\right)+{\rho }_y^k\left(y_{}^{k-1}-y_{}^k\right)\\ {\zeta }_z^{k+1}={\nabla }_{z}g\left(u^{k+1}\right)-{\nabla }_{z}g\left(u\right)-C^{\text{T}}\left({\lambda }^k-{\lambda }^{k+1}\right)\\ {\zeta }_{\lambda }^{k+1}=\frac{1}{\beta }\left({\lambda }^k-{\lambda }^{k+1}\right)\end{array}$

由于$\nabla \text{h}(\cdot )$ Lipschitz连续，根据假设3.1，结合引理3.1，存在$C>0$ 使得$d\left(0,\partial L_{\beta }\left(u^{k+1},{\lambda }^{k+1}\right)\right)$ $\le C\left(\Vert {\Delta }_x^{k+1}\Vert +\Vert {\Delta }_y^{k+1}\Vert +\Vert {\Delta }_z^{k+1}\Vert +\Vert {\Delta }_x^k\Vert +\Vert {\Delta }_y^k\Vert +\Vert {\Delta }_z^k\Vert \right)$ □

引理3.4 根据假设3.1，如果$L_{\beta }$ 是强制的，对于算法1生成的序列$\left\{{\omega }^k\right\}$ ，满足：

1) 序列$\left\{{\omega }^k\right\}$ 是有界的。

2)${\displaystyle \sum _{k=0}^{+\infty }{\Vert {\omega }^{k+1}-{\omega }^k\Vert }^2}<+\infty$ 。

证明1) 根据引理3.2和算法的定义，得到

$L_{\beta }\left({\omega }^k\right)\le ℒ\left(u^{k+1},{\lambda }^k,u^k\right)\le ℒ\left(u^0,{\lambda }^0,u^{-1}\right)=L_{\beta }\left({\omega }^0\right).$

根据$L_{\beta }$ 的强制性以及$\underset{\omega }{\inf }{L}_{\beta }\left(\omega \right)>-\infty$ ，序列$\left\{{\omega }^k\right\}$ 是有界的。

2) 因为$\left\{{\omega }^k\right\}$ 是有界的，则$\left\{{\widehat{\omega }}^k\right\}$ 也是有界的。因此其至少有一个聚点。假设${\widehat{\omega }}^{*}$ 是$\left\{{\widehat{\omega }}^k\right\}$ 的一个聚点，则必然存在一个子列$\left\{{\widehat{\omega }}^{k_j}\right\}$ 使得${\lim }_{j\to \infty }{\widehat{\omega }}^{k_j}={\widehat{\omega }}^{*}.$ 由于$f,g$ 是下半连续的，$h$ 是连续函数，则

$\underset{j\to \infty }{\lim }{\widehat{L}}_{\beta }\left({\widehat{\omega }}^{k_j}\right)\ge {\widehat{L}}_{\beta }\left({\widehat{\omega }}^{*}\right).$

因此，$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^{k_j}\right)\right\}$ 是有下界的。根据引理3.2，$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)\right\}$ 是单调递减的，因此函数列$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)\right\}$ 收敛且${\widehat{L}}_{\beta }\left({\widehat{\omega }}^{*}\right)\le {\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)$ 。同时有

$\nu {\Vert \Delta u^{k+1}\Vert }^2\le {\widehat{L}}_{\beta }\left(u^{k+1},{\lambda }^{k+1},u^k\right)-{\widehat{L}}_{\beta }\left(u^k,{\lambda }^k,u^{k-1}\right),$

将上述不等式从$k=0,\cdots ,M$ 相加，得

${\displaystyle \sum _{k=0}^M\nu {\Vert \Delta u^{k+1}\Vert }^2}\le L_{\beta }\left(u^0,{\lambda }^0\right)-{\tilde{L}}_{\beta }\left(u^{M+1},{\lambda }^{M+1},u^M\right)\le L_{\beta }\left(u^0,{\lambda }^0\right)-\inf {\tilde{L}}_{\beta }\left(\overline{\omega }\right)$

令$M\to \infty$ ，有${\displaystyle \sum _{k=0}^M\nu {\Vert \Delta u^{k+1}\Vert }^2}<+\infty$ ，结合引理3.1，即可得${\displaystyle {\sum }_{k=0}^{\infty }{\Vert {\omega }^{k+1}-{\omega }^k\Vert }^2<+\infty }.$ 引理得证。 □

定理3.1 对于算法1生成的序列$\left\{{\omega }^k\right\}$ ，令$\mathcal{S},\widehat{\mathcal{S}}$ 分别表示序列$\left\{{\omega }^k\right\}$ ，$\left\{{\widehat{\omega }}^k\right\}$ 聚点的集合。如果假设3.1成立，则下述结论成立

1) $\mathcal{S},\widehat{\mathcal{S}}$ 是非空紧集且${\lim }_{k\to \infty }d\left({\omega }^k,\mathcal{S}\right)={\lim }_{k\to \infty }d\left({\widehat{\omega }}^k,\widehat{\mathcal{S}}\right)=0.$

2) 如果$u^{*}=u^{*\text{'}}$ 并且${\omega }^{*}\in \mathcal{S}$ ，则。

3) $\mathcal{S}\subseteq crit{L}_{\beta }.$

4)序列$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)\right\}$ 收敛，且。

证明：1) 根据$\mathcal{S},\widehat{\mathcal{S}}$ 的定义，(1)显然成立。

2) 根据引理3.4和$\left\{{\omega }^k\right\}$ ，$\left\{{\widehat{\omega }}^k\right\}$ 的定义，显然(2)成立。

3) 对于${\omega }^{*}\in \mathcal{S}$ ，可以找到$\left\{{\omega }^k\right\}$ 的一个子列$\left\{{\widehat{\omega }}^{k_j}\right\}$ ，这个子列收敛到${\omega }^{*}$ 。根据引理3.4，得到这时有

$A{x}^{*}+B{y}^{*}+C{z}^{\ast }=b.$

因此$\left(x^{*},y^{*},z^{*}\right)$ 是问题(1.1)的可行点。由于$x^{k+1}$ 是$x$ 子问题的最小值，则

$\begin{array}{c}f\left(x^{k_j+1}\right)+g\left(y^{k_j}\right)+\langle {\nabla }_{x}h\left(x^{k_j},y^{k_j},z^{k_j}\right),x^{k_j+1}-x^{k_j}\rangle -\langle {\lambda }^{k_j},A{x}^{k_j+1}+B{y}^{k_j}+C{z}^{k_j}-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{k_j+1}+B{y}^{k_j}+C{z}^{k_j}-b\Vert }^2+\frac{{\tau }_x^{k_j}}{2}{\Delta }_x^{k_j+1}+{\rho }_x^{k_j}\langle x^{k_j+1},x^{k_j}-x^{k_j-1}\rangle \\ \le f\left(x^{*}\right)+g\left(y^{k_j}\right)+\langle {\nabla }_{x}h\left(x^{k_j},y^{k_j},z^{k_j}\right),x^{*}-x^{k_j}\rangle -\langle {\lambda }^{k_j},A{x}^{*}+B{y}^{k_j}+C{z}^{k_j}-b\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{*}+B{y}^{k_j}+C{z}^{k_j}-b\Vert }^2+\frac{{\tau }_x^{k_j}}{2}{\Vert x^{*}-x^{k_j}\Vert }^2+{\rho }_x^{k_j}\langle x^{*},x^{k_j}-x^{k_j-1}\rangle ,\end{array}$

考虑到得到

$\underset{j\to \infty }{\lim \sup }f\left(x_{}^{k_j}\right)\le f\left(x_{}^{\ast }\right).$

根据的下半连续性，有$f\left(x_{}^{\ast }\right)\le \lim {\inf }_{j\to \infty }f\left(x_{}^{k_j}\right).$ 因此

$\underset{j\to \infty }{\lim }f\left(x_{}^{k_j}\right)=f\left(x_{}^{\ast }\right).$ (3.15)

同理，有

$\underset{j\to \infty }{\lim }g\left(y_{}^{k_j}\right)=g\left(y_{}^{\ast }\right).$ (3.16)

由于集合$\partial f,\partial g$ 是闭的以及$\nabla h$ 的Lipschitz连续性，在式(3.14)取$k=k_j\to \infty$ ，得到

$\{\begin{array}{l}0\in {\partial }_{x}f\left(x^{*}\right)+{\nabla }_{x}h\left(x^{*},y^{*},z^{*}\right)-A^{\text{T}}{\lambda }^{*},\\ 0\in {\partial }_{y}g\left(y^{*}\right)+{\nabla }_{y}h\left(x^{*},y^{*},z^{*}\right)-B^{\text{T}}{\lambda }^{*},\\ 0={\nabla }_{z}h\left(x^{*},y^{*},z^{*}\right)-C^{\text{T}}{\lambda }^{*},\\ A{x}^{*}+B{y}^{*}+C{z}^{*}-b=0\end{array}$

根据定义2.1，${\omega }^{*}$ 是$L_{\beta }$ 的一个稳定点，即${\omega }^{*}\in \mathcal{S}\subseteq crit{L}_{\beta }.$

4) 由于${\widehat{\omega }}^k\in \widehat{\mathcal{S}}$ ，存在$\left\{{\widehat{\omega }}^{k_j}\right\}$ 使得根据式(3.15)和(3.16)，以及$h$ 的连续性，得到

(3.17)

考虑到，$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)\right\}$ 是单调的，所以$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)\right\}$ 收敛，因此

□

定理3.2 对于算法1生成的序列$\left\{{\omega }^k\right\}$ ，如果假设3.1成立且${\lim }_{j\to \infty }{\widehat{L}}_{\beta }\left(u^{k_j},{\lambda }^{k_j},u^{k_j-1}\right)$ 在$\left(u^{*},{\lambda }^{*},u^{*}\right)$ 具有Kurdyka-Lojasiewicz性质，这时，有

(3.18)

并且序列$\left\{{\omega }^k\right\}$ 收敛到$L_{\beta }(\cdot )$ 的稳定点。

证明 以下从两个方面来证明该定理

1) 基于式(3.17)，如果存在$\tilde{k}>0$ 使得${\widehat{L}}_{\beta }\left({\widehat{\omega }}^{\tilde{k}}\right)={\widehat{L}}_{\beta }\left({\widehat{\omega }}^{*}\right)$ ，对(3.10)式移项得

$\begin{array}{c}\alpha {\Delta }_u^{k+1}\le L_{\beta }\left({\widehat{\omega }}^{\tilde{k}}\right)-L_{\beta }\left({\widehat{\omega }}^{\tilde{k}+1}\right)\le L_{\beta }\left({\widehat{\omega }}^{\tilde{k}}\right)-L_{\beta }\left({\widehat{\omega }}^{\ast }\right).\end{array}$

由此可得，对任意$k>\tilde{k}$ ，都有$u^{k+1}=u^k$ 。进一步，根据式(3.4)，可得对于任意$k>\tilde{k}+1,$ 都有${\omega }^{k+1}={\omega }^k$ ，因此可以得到(3.18)。

2) 由于$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)\right\}$ 单调递减，因此有${\widehat{L}}_{\beta }\left({\widehat{\omega }}^{k+1}\right)>{\widehat{L}}_{\beta }\left({\widehat{\omega }}^{*}\right)$ 。从对任意常数$\eta \in ℝ$ ，存在常数$k_1>0$ ，当$k>k_1$ 时，${\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)<{\widehat{L}}_{\beta }\left({\widehat{\omega }}^{\ast }\right)+\eta .$ 根据定理3.1(2)，对于任意$\epsilon >0,$ 存在$k_2>0$ 使得对任意$k>k_2$ ，$d\left({\widehat{\omega }}^k,\widehat{\mathcal{S}}\right)\le \epsilon .$ 因此，对于任意$\epsilon ,\eta >0$ ，当$k>k\text{'}=\max \left\{k_1,k_2\right\}$ ，得到

因为$\widehat{\mathcal{S}}$ 是非空紧集并且$\left\{{\widehat{L}}_{\beta }\left({\widehat{\omega }}^k\right)\right\}\subseteq \widehat{\mathcal{S}}$ 。根据引理2.3，得到

${\phi }^{\prime }\left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)d\left(0,\partial L_{\beta }\left({\widehat{\omega }}^k\right)\right)\ge 1,\forall k>k\text{'}.$

由于${\phi }^{\prime }\left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)>0$ ，则

$\frac{1}{{\phi }^{\prime }\left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)}<d\left(0,\partial L_{\beta }\left({\widehat{\omega }}^k\right)\right)$ (3.19)

由函数$\phi$ 是凹函数，得到

$\phi \left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)\ge {\phi }^{\prime }\left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)\left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^k\right)\right)$

令$t_k=\Vert {\Delta }_x^{k+1}\Vert +\Vert {\Delta }_y^{k+1}\Vert +\Vert {\Delta }_z^{k+1}\Vert$ 根据式(3.13)和式(3.19)得到

$\begin{array}{l}{L}_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^k\right)\le \frac{\phi \left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)}{\phi \text{'}\left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)}\\ \le \left(\phi \left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)\right)d\left(0,\partial L_{\beta }\left({\widehat{\omega }}^k\right)\right)\\ \le \left(\phi \left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)\right)C\left(t_{k+1}+t_k\right).\end{array}$

由(3.10)和上述不等式，推出

$v{\Vert {\Delta }_u^{k+1}\Vert }^2\le \phi \left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)C\left(t_{k+1}+t_k\right)$

根据不等式$a+b+c\le \sqrt{3a^2+3b^2+3c^2}$ 得到

$t_{k+1}\le \sqrt{3{\Vert {\Delta }_u^{k+1}\Vert }^2}\le \sqrt{\frac{3C}{\nu }\phi \left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)\left(t_{k+1}+t_k\right)}$

根据不等式$\sqrt{ab}\le a+\frac{1}{4}b$ 得到

$t_{k+1}\le \sqrt{\frac{3C}{v}}\phi \left(L_{\beta }\left({\widehat{\omega }}^k\right)-L_{\beta }\left({\widehat{\omega }}^{\ast }\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^{k+1}\right)-L_{\beta }\left({\widehat{\omega }}^{\ast }\right)\right)+\frac{1}{4}\left(t_{k+1}+t_k\right)$

将上述不等式由$k=k\text{'}+2,\cdots ,M$ 相加，得到

${\displaystyle {\sum }_{k=k\text{'}+2}^M{t}_{}^{k+1}}\le \frac{C}{\nu }\phi \left(L_{\beta }\left({\widehat{\omega }}^{k\text{'}+2}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)-\phi \left(L_{\beta }\left({\widehat{\omega }}^M\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)+\frac{1}{4}{\displaystyle {\sum }_{k=k\text{'}+2}^M\left(t_{}^{k+1}+t_{}{}^k\right)}$

令$M\to +\infty$ ，得到

${\displaystyle \sum _{k=k\text{'}+2}^{+\infty }{t}_{k+1}}\le 2\left(\frac{c}{\nu }\phi \left(L_{\beta }\left({\widehat{\omega }}^{k^{\prime }+2}\right)-L_{\beta }\left({\widehat{\omega }}^{*}\right)\right)+t_{k^{\prime }+2}\right).$

由于$\nu ,C,>0$ 且为常数，得到

${\displaystyle \sum _{k=0}^{\infty }\Vert x^{k+1}-x^k\Vert }<+\infty ,{\displaystyle \sum _{k=0}^{\infty }\Vert y^{k+1}-y^k\Vert }<+\infty ,{\displaystyle \sum _{k=0}^{\infty }\Vert z^{k+1}-z^k\Vert }<+\infty .$

结合引理3.1，得到

则(3.18)式得证，因此序列$\left\{{\omega }^k\right\}$ 是收敛的，根据定理3.1，$\left\{{\omega }^k\right\}$ 收敛到$L_{\beta }(\cdot )$ 的稳定点${\omega }^{*}$ 。 □

4. 算法的应用

鲁棒主成分分析(Robust PCA)

Robust PCA问题[13]-[22]可以概括为

$\begin{array}{c}\min {\Vert X\Vert }_{\ast }+\alpha {\Vert Y\Vert }_1+\frac{\omega }{2}{\Vert Z-\mathcal{O}\Vert }_F^2,\text{s}.\text{t}.X+Y=Z,\end{array}$ (4.1)

其中，$\mathcal{O}\in {ℝ}^{p\times n}$ 是观测矩阵，$X,Y,Z\in {ℝ}^{p\times n}$ 是决策变量，定义${\Vert X\Vert }_{\ast }={\displaystyle {\sum }_{i=1}^{\min (p,n)}{\left|{\sigma }_i\left(X\right)\right|}^{\frac{1}{2}}}$ 为核范数，${\ell }_1$ 范数为${\Vert Y\Vert }_1={\displaystyle {\sum }_{i=1}^n{\displaystyle {\sum }_{i=1}^p\left|Y_{ij}\right|}},$ $\omega$ 是罚参数，$\alpha$ 是${\Vert X\Vert }_{\ast }$ 和${\Vert Y\Vert }_1$ 之间的权重参数，用$\lambda$ 表示拉格朗日乘子，则问题(4.1)的增广拉格朗日函数被定义为：

$L_{\beta }\left(X,Y,Z,\lambda \right)={\Vert X\Vert }_{\ast }+\alpha {\Vert Y\Vert }_1+\frac{\omega }{2}{\Vert Z-\mathcal{O}\Vert }_F^2-\langle \lambda ,X+Y-Z\rangle +\frac{\beta }{2}{\Vert X+Y-Z\Vert }_F^2,$ (4.2)

问题(4.1)可以被算法1通过如下迭代方式求解：

$\{\begin{array}{l}{X}^{k+1}\in \underset{X}{\arg \min }{ℒ}_{\beta }^{x^k}\left(x,y^k,z^k,{\lambda }^k\right)+\frac{{\tau }_x^k}{2}{\Vert X-X^k-\frac{1}{{\tau }_x^k}{\rho }_X^k\left(X^k-X^{k-1}\right)\Vert }_F^2,\\ Y^{k+1}\in \underset{Y}{\arg \min }{ℒ}_{\beta }^{y^k}\left(x^{k+1},y,z^k,{\lambda }^k\right)+\frac{{\tau }_y^k}{2}{\Vert Y-Y^k-\frac{1}{{\tau }_x^k}{\rho }_Y^k\left(Y^k-Y^{k-1}\right)\Vert }_F^2,\\ Z^{k+1}=\underset{Z}{\arg \min }{ℒ}_{\beta }^{z^k}\left(x^{k+1},y^{k+1},z,{\lambda }^k\right)+\frac{{\tau }_z^k}{2}{\Vert Z-Z^k\Vert }_F^2,\\ {\lambda }^{k+1}={\lambda }^k-\beta \left(X^{k+1}+Y^{k+1}-Z^{k+1}\right),\end{array}$

其中，${ℒ}_{\beta }^{}(\cdot )$ 为$L_{\beta }(\cdot )$ 的一阶近似，其定义见公式(3.1)~(3.3)。上述方程组的显式表达式为

$\{\begin{array}{l}{X}^{k+1}=\mathscr{H}\left(\frac{\beta \left(Z^k-Y^k\right)+{\lambda }^k+{\tau }_X^k{X}^k+{\rho }_X^k\left(X^k-X^{k-1}\right)}{\beta +{\tau }_X^k},\frac{1}{\beta +{\tau }_X^k}\right),\hfill \\ Y^{k+1}=\mathcal{S}\left(\frac{\beta \left(Z^k-X^{k+1}\right)+{\lambda }^k+{\tau }_Y^k{Y}^k+{\rho }_Y^k\left(Y^k-Y^{k-1}\right)}{\beta +{\tau }_Y^k},\frac{\alpha }{\beta +{\tau }_Y^k}\right),\hfill \\ Z^{k+1}=\frac{{\tau }_Z^k{Z}^k+\beta \left(X^{k+1}+Y^{k+1}\right)+\omega \mathcal{O}-{\lambda }^k}{\beta +\omega +1},\hfill \\ {\lambda }^{k+1}={\lambda }^k-\beta \left(X^{k+1}+Y^{k+1}-Z^{k+1}\right),\hfill \end{array}$

其中，$\mathscr{H}\left(\cdot ,\mu \right)$ 是奇异值阈值算子[23]，$\mathcal{S}\left(\cdot ,\mu \right)$ 是软阈值算子[24]。

在下述结果中，$r.\left(X\right),spr.\left(Y\right)$ 分别表示矩阵$X$ 的秩和矩阵$Y$ 的稀疏率，实验选取了三组不同维度的观测矩阵$\mathcal{O}$ 和两组不同的$\left(r.\left(X\right),spr.\left(Y\right)\right)$ 来进行矩阵分解。实验中，取$\begin{array}{c}\alpha =\frac{0.5}{\sqrt{p}},\omega =1.0,\end{array}$ 初始矩阵$X^0,$ $X^{-1},Y^0,Y^{-1},Z^0,Z^{-1}$ 均被设置为零矩阵。算法1的参数设置为$\beta =200,{\rho }_x{}^0={\rho }_y{}^0={\rho }_z{}^0=1$ ，${\tau }_x^0={\tau }_y^0={\tau }_z^0=6.$ 实验的终止准则为

$\text{RelChg}:=\frac{\left(X^{k+1},Y^{k+1},Z^{k+1}\right)-{\left(X^k,Y^k,Z^k\right)}_F}{{\Vert \left(X^k,Y^k,Z^k\right)\Vert }_F+1}\le {10}^{-6}.$

实验分别使用PIPI-ADMM和线性化ADMM算法(LADMM) [25]求解问题(4.1)。表1给出了两个算法求解该问题的数值结果，其中$Iters,Times\left(s\right),\left(r.\left(\widehat{X}\right),spr.\left(\widehat{Y}\right)\right)$ 分别表示迭代次数，求解时间以及分解后矩阵的秩和稀疏率。另外，使用

$\text{RelErr}:=\frac{{\Vert \left(\widehat{X},\widehat{Y},\widehat{Z}\right)-\left(X^{*},Y^{*},Z^{*}\right)\Vert }_F}{{\Vert \left(X^{*},Y^{*},Z^{*}\right)\Vert }_F+1},$

来衡量矩阵的数值解与原始矩阵的误差，其中，$X^{*},Y^{*},Z^{*}$ 表示原始矩阵，$\widehat{X},\widehat{Y},\widehat{Z}$ 表示问题(4.1)的数值解。从表1可以看出，PIPI-ADMM的迭代步数和计算时间明显小于LADMM算法，为更加直观展示结果，图1绘制了$p=100,n=200$ 式目标函数及其相关误差的变化趋势。上述实验结果验证了PIPI-ADMM算法的有效性，并且可以看出，PIPI-ADMM算法的数值效果明显优于LADMM算法。

Table.1. Numerical results of Robust PCA problem

表1. Robust PCA问题的数值结果

p	n	$\left(r.\left(X^{\text{*}}\right),spr.\left(Y^{\text{*}}\right)\right)$	PIPI-ADMM			LADMM
			Iters	Times (s)	$\left(r.\left(\widehat{X}\right),spr.\left(\widehat{Y}\right)\right)$	Iters	Times (s)	$\left(r.\left(\widehat{X}\right),spr.\left(\widehat{Y}\right)\right)$
100	200	(2, 0.05)	561	5.359	(2, 0.05)	624	5.901	(2, 0.05)
		(2, 0.1)	858	7.933	(2, 0.1)	905	9.315	(2, 0.1)
		(10, 0.05)	654	5.657	(10, 0.05)	686	5.849	(10, 0.05)
		(10, 0.1)	923	11.246	(10, 0.1)	1271	21.045	(10, 0.1)
500	1000	(2, 0.05)	1743	72.432	(2, 0.05)	1865	75.847	(2, 0.06)
		(2, 0.1)	2763	153.543	(2, 0.1)	3140	172.624	(2, 0.1)
		(10, 0.05)	1822	74.469	(10, 0.05)	1970	87.570	(10, 0.05)
		(10, 0.1)	3109	198.734	(10, 0.1)	3932	225.623	(10, 0.12)

Figure 1. The trends of $RelChg,RelErr,r.\left(X^k\right),$ and $spr.\left(Y^k\right)$ vary with the changes in number of $Iters$ when $p=100,n=200$ and $r.\left(X\ast \right)=10,spr.\left(Y\ast \right)=0.1$

图1. $p=100,n=200,r.\left(X\ast \right)=10,spr.\left(Y\ast \right)=0.1$ 时两种算法的$RelChg,RelErr,r.\left(X^k\right)$ 和$spr.\left(Y^k\right)$ 随迭代次数的变化情况

此外，我们还对PIPI-ADMM算法中惯性因子${\rho }_x^0={\rho }_y^0$ 的大小对算法的加速效果进行了探究。图2绘制了不同的惯性因子对算法收敛速度的影响。可以看出，当惯性因子越大时，达到终止准则所需要的迭代步数越少。因此，惯性技术对于ADMM算法的加速是非常有效的，惯性因子越大，收敛速度越快，算法性能越强。

Figure 2. The trends of $RelChg$ and $RelErr$ vary with the changes in number of $Iters$ when $p=100$ , and $n=200$ .$r.\left(X^{*}\right)=10,spr.\left(Y^{*}\right)=0.1$

图2. $p=100,n=200,r.\left(X\ast \right)=10,spr.\left(Y\ast \right)=0.1$ 时不同的惯性因子的$RelChg,RelErr$ ，随迭代次数的变化

5. 结论

本文针对具有不可分离结构的非凸非光滑问题，提出了并行式惯性近端非精确ADMM算法(PIPI-ADMM)。此算法结合了惯性技术与近端思想，通过非精确求解每个子问题的增广拉格朗日函数，以产生新的迭代点。同时，文章利用Kurdyka-Lojasiewicz性质证明了算法在非凸情形下的强收敛性。最后，数值实验结果说明，所提出的PIPI-ADMM算法具有更高的效率和更快的收敛速度。

NOTES

^*通讯作者。