用于求解多块可分凸优化问题的惯性临近严格收缩PRSM

Inertial Proximal Strictly Contractive PRSM for Solving Multi-Block Separable Convex Optimization

摘要: 近年来，PRSM成为了处理具有线性约束的两部分可分凸优化问题的一个热门研究方向。本研究聚焦于目标函数由三个解耦变量函数之和构成的可分凸优化问题。单纯地运用PRSM可能无法保证其收敛性。因此，我们引入了一种带有惯性项和临近项的严格收缩PRSM。借助变分不等式、临近点算法以及基本不等式，我们对所提出的方法进行了全局收敛性的分析。此外，我们将这种新方法应用于鲁棒主成分分析(PCA)问题的求解，并提供了一些初步的数值结果，用以展示该方法的可行性和有效性。

Abstract: In recent years, PRSM has become a popular research direction for dealing with two-block separable convex optimization problems with linear constraints. This study focuses on separable convex optimization problems where the objective function is composed of the sum of three decoupled variable functions. Simply applying the PRSM may not guarantee its convergence. Therefore, we introduce a strictly contractive PRSM with inertial and proximal terms. By means of variational inequalities, the proximal point algorithm, and fundamental inequalities, we have analyzed the global convergence of the proposed method. In addition, we applied this new method to the solution of the Robust Principal Component Analysis (PCA) problem and provided some preliminary numerical results to demonstrate the feasibility and effectiveness of the method.

1. 介绍

我们研究以下的可分凸规划模型

$\min \left\{{\theta }_1\left(x_1\right)+{\theta }_2\left(x_2\right)+{\theta }_3\left(x_3\right)|A_1{x}_1+A_2{x}_2+A_3{x}_3=b,x_i\in {\mathcal{X}}_i,i=1,2,3\right\}，$ (1)

其中，${\theta }_i:{ℝ}^{n_i}\to ℝ\cup \left\{\text{+}\infty \right\}\left(i=1,2,3\right)$ 是闭合凸函数(可能是非光滑的)，${\mathcal{X}}_i\subset {ℝ}^{n_i}\left(i=1,2,3\right)$ 是非空闭凸集，$A_i\in {ℝ}^{l\times n_i}$ 是线性算子，$b\in {ℝ}^l$ 是一个给定的向量。可分离问题(1)在许多领域有着广泛的应用，例如图像处理[1] [2]、统计学习[3] [4]以及矩阵分解[5]。

方程(1)的增广拉格朗日函数是

$\begin{array}{c}{L}_{\beta }\left(x_1,x_2,x_3,\lambda \right)={\theta }_1\left(x_1\right)+{\theta }_2\left(x_2\right)+{\theta }_3\left(x_3\right)-{\lambda }^{\text{T}}\left(A_1{x}_1+A_2{x}_2+A_3{x}_3-b\right)\\ +\frac{\beta }{2}{\Vert A_1{x}_1+A_2{x}_2+A_3{x}_3-b\Vert }^2,\end{array}$ (2)

其中$\lambda \in {ℝ}^l$ 是拉格朗日乘数，$\beta >0$ 是惩罚参数。

问题(1)可以通过使用许多经典方法有效解决，例如Hestenes [6]和Powell [7]的乘子法，特别是增广拉格朗日方法(ALM) [8]，Douglas-Rachford分裂方法(DRSM) [9]，交替方向乘子法(ADMM) [10] [11]，PRSM [12]以及前向–后向分裂方法[13]。在本文中，我们将专注于PRSM。

为了确保PRSM生成的迭代序列具有严格的收缩性，He等人[14]开发了一种严格收缩的Peaceman-Rachford分裂方法(SCPRSM)，并建立了全局收敛性。惯性可以提高算法的计算效率，惯性起源于动态系统，可以追溯到20世纪60年代的重球方法[15]。多块可分离凸优化问题是一个热门话题。Wu等人[16]提出了一个临近PRSM来解决多块可分离凸最小化问题，其中一些子问题可以并行求解。对于其他多块可分离凸优化问题的研究，我们请读者参考[17]。

在本文中，提出了一种带有不确定项的惯性临近严格收缩的PRSM，用于解决多块可分离凸优化问题。

$\{\begin{array}{l}\left({\overline{x}}_1^k,{\overline{x}}_2^k,{\overline{x}}_3^k,{\overline{\lambda }}^k\right)=\left(x_1^k,x_2^k,x_3^k,{\lambda }^k\right)+{\rho }_k\left(x_1^k-x_1^{k-1},x_2^k-x_2^{k-1},x_3^k-x_3^{k-1},{\lambda }^k-{\lambda }^{k-1}\right),\hfill \\ x_1^{k+1}=\underset{x_1\in {\chi }_1}{\arg \min }\{{\theta }_1\left(x_1\right)-{\left({\overline{\lambda }}^k\right)}^{\text{T}}{A}_1{x}_1+\frac{\beta }{2}{\Vert A_1{x}_1+A_2{\overline{x}}_2^k+A_3{\overline{x}}_3^k-b\Vert }^2+\frac{1}{2}{\Vert x_1-{\overline{x}}_1^k\Vert }_B^2\},\hfill \\ x_2^{k+1}=\underset{x_2\in {\chi }_2}{\arg \min }\{{\theta }_2\left(x_2\right)-{\left({\overline{\lambda }}^k\right)}^{\text{T}}{A}_2{x}_2+\frac{\beta }{2}{\Vert A_1{x}_1{}^{k+1}+A_2{x}_2+A_3{\overline{x}}_3^k-b\Vert }^2+\frac{1}{2}{\Vert x_2-{\overline{x}}_2^k\Vert }_C^2\},\hfill \\ {\lambda }^{k+\frac{1}{2}}={\overline{\lambda }}^k-\alpha \beta \left(A_1{x}_1^{k+1}+A_2{x}_2^{k+1}+A_3{\overline{x}}_3^k-b\right),\hfill \\ x_3^{k+1}=\underset{x_3\in {\chi }_3}{\arg \min }\{{\theta }_3\left(x_3\right)-{\left({\lambda }^{k+\frac{1}{2}}\right)}^{\text{T}}{A}_3{x}_3+\frac{\beta }{2}{\Vert A_1{x}_1^{k+1}+A_2{x}_2^{k+1}+A_3{x}_3-b\Vert }^2+\frac{1}{2}{\Vert x_3-{\overline{x}}_3^k\Vert }_D^2\},\hfill \\ {\lambda }^{k+1}={\lambda }^{k+\frac{1}{2}}-\alpha \beta \left(A_1{x}_1^{k+1}+A_2{x}_2^{k+1}+A_3{x}_3^{k+1}-b\right),\hfill \end{array}$ (3)

其中${\rho }_k\in [0,1/3)$ 是一个惯性参数，$\alpha \in \left(0,\left(1+\sqrt{17}\right)/8\right)$ 是一个步长参数，$\beta >0$ 是一个惩罚参数和

$B=r_1{I}_{n_1}-\beta A_1^{\text{T}}{A}_1,C=r_2{I}_{n_2}-\beta A_2^{\text{T}}{A}_2,D=\tau r_3{I}_{n_3}-\beta A_3^{\text{T}}{A}_3,$ (4)

其中$r_1\ge \beta \Vert A_1^{\text{T}}{A}_1\Vert ,r_2\ge \beta \Vert A_2^{\text{T}}{A}_2\Vert ,r_3>\beta \Vert A_3^{\text{T}}{A}_3\Vert$ 。

在上述描述中，$r_1\ge \beta \Vert A_1^{\text{T}}{A}_1\Vert$ 意味着矩阵$B$ 是半正定的，$r_2\ge \beta \Vert A_2^{\text{T}}{A}_2\Vert$ 意味着矩阵$C$ 是半正定的，而$\tau \in \left(\left(1+\alpha \right)/2,1\right)$ 表示矩阵$D$ 的不定性。

本文的其余部分组织如下。在第2节中，我们总结了一些为进一步分析所需的预备知识。然后，在第3节中，我们对惯性临近严格收缩的Peaceman-Rachford分裂方法(IPSCPRSM)的预测–校正进行重新表述，以通过变分不等式建立全局收敛性。在第4节中，我们进行了一些数值模拟来说明所提出方法的有效性。第5节得出了一些结论。

2. 预备知识

在这一部分，我们提供一些预备知识和简单的结果，以便进行进一步的分析。首先，我们用$ℝ$ 来表示通常的欧几里得空间，并用$\Vert .\Vert$ 和$\langle .,.\rangle$ 来表示$ℝ$ 中的欧几里得范数和内积。如果$x$ 是${ℝ}^n$ 中的一个向量，$D$ 是一个$n\times n$ 的对称矩阵，我们使用记号${\Vert x\Vert }_D^2=x^{\text{T}}Dx$ 来表示D-范数。

接下来，我们引入一些辅助序列和矩阵：

$x=\left(\begin{array}{l}{x}_1\hfill \\ x_2\hfill \\ x_3\hfill \end{array}\right),w=\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ \lambda \end{array}\right),F\left(w\right)=\left(\begin{array}{c}-A_1^{\text{T}}\lambda \\ -A_2^{\text{T}}\lambda \\ -A_3^{\text{T}}\lambda \\ r\end{array}\right),r=A_1{x}_1+A_2{x}_2+A_3{x}_3-b,$ (5)

和

${\tilde{w}}^k=\left(\begin{array}{l}{\tilde{x}}_1^k\hfill \\ {\tilde{x}}_2^k\hfill \\ {\tilde{x}}_3^k\hfill \\ {\tilde{\lambda }}^k\hfill \end{array}\right)=\left(\begin{array}{c}{x}_1^{k+1}\\ x_2^{k+1}\\ x_3^{k+1}\\ {\overline{\lambda }}^k-\beta \left(A_1{x}_1^{k+1}+A_2{\overline{x}}_2^k+A_3{\overline{x}}_3^k-b\right)\end{array}\right).$ (6)

令

$Q=\left(\begin{array}{cccc}B& 0& 0& 0\\ 0& \beta A_2^{\text{T}}{A}_2+C& 0& 0\\ 0& \left(1+\alpha \right)\beta A_2{A}_3^{\text{T}}& \beta A_3^{\text{T}}{A}_3+D& 0\\ 0& -A_2& -A_3& \frac{1}{\beta }{I}_l\end{array}\right),$ (7)

$M=\left(\begin{array}{cccc}{I}_{n_1}& 0& 0& 0\\ 0& I_{n_2}& 0& 0\\ 0& 0& I_{n_3}& 0\\ 0& -2\alpha \beta A_2& -\alpha \beta A_3& 2\alpha I_l\end{array}\right),$ (8)

$H=\left(\begin{array}{cccc}B& 0& 0& 0\\ 0& r_2{I}_{n_2}& 0& 0\\ 0& \left(1+\alpha \right)\beta A_2{A}_3^{\text{T}}& \tau r_3{I}_{n_3}& 0\\ 0& 0& -\frac{1}{2}{A}_3& \frac{1}{2\alpha \beta }{I}_l\end{array}\right),$ (9)

$G=\left(\begin{array}{cccc}B& 0& 0& 0\\ 0& \left(1-2\alpha \right)\beta A_2^{\text{T}}{A}_2+C& \left(1-\alpha \right)\beta A_2{A}_3^{\text{T}}& \left(2\alpha -1\right)A_2\\ 0& -\alpha \beta A_2{A}_3^{\text{T}}& \left(1-\alpha \right)\beta A_3^{\text{T}}{A}_3+D& \left(\alpha -1\right)A_3\\ 0& \left(2\alpha -1\right)A_2& \left(2\alpha -1\right)A_3& \frac{\left(2-2\alpha \right)}{\beta }{I}_l\end{array}\right).$ (10)

定义

$D_0=r_3{I}_{n_3}-\beta A_3^{\text{T}}{A}_3,$

从问题(4)中，我们可以得出结论，矩阵$D_0$ 是正定的，并且

$D=\tau D_0-\left(1-\tau \right)\beta A_3^{\text{T}}{A}_3.$ (11)

变分不等式特征描述

设方程(1)的拉格朗日函数为

$L\left(x_1,x_2,x_3,\lambda \right)={\theta }_1\left(x_1\right)+{\theta }_2\left(x_2\right)+{\theta }_3\left(x_3\right)-{\lambda }^{\text{T}}\left(A_1{x}_1+A_2{x}_2+A_3{x}_3-b\right),$

其定义域为$\text{Ω}:={\mathcal{X}}_1\times {\mathcal{X}}_2\times {\mathcal{X}}_3\times R^l$ 。如果它满足条件，我们称$w^{*}=\left(x_1^{*},x_2^{*},x_3^{*},{\lambda }^{*}\right)\in \Omega$ 为拉格朗日函数的鞍点。

$L\left(x_1^{*},x_2^{*},x_3^{*},\lambda \right)\le L\left(x_1^{*},x_2^{*},x_3^{*},{\lambda }^{*}\right)\le L_{x_i\in {\chi }_i,(i=1,2,3)}\left(x_1,x_2,x_3,{\lambda }^{*}\right).$

相应地，我们推导出以下不等式：

$\{\begin{array}{l}{\theta }_1\left(x_1\right)-{\theta }_1\left(x_1^{\ast }\right)+{\left(x_1-x_1^{\ast }\right)}^{\text{T}}\left(-A_1^{\text{T}}{\lambda }^{\ast }\right)\ge 0,\forall x_1\in {\mathcal{X}}_1,\hfill \\ {\theta }_2\left(x_2\right)-{\theta }_2\left(x_2^{\ast }\right)+{\left(x_2-x_2^{\ast }\right)}^{\text{T}}\left(-A_2^{\text{T}}{\lambda }^{\ast }\right)\ge 0,\forall x_2\in {\mathcal{X}}_2,\hfill \\ {\theta }_3\left(x_3\right)-{\theta }_3\left(x_3^{\ast }\right)+{\left(x_3-x_3^{\ast }\right)}^{\text{T}}\left(-A_3^{\text{T}}{\lambda }^{\ast }\right)\ge 0,\forall x_3\in {\mathcal{X}}_3,\hfill \\ {(\lambda -{\lambda }^{\ast })}^{\text{T}}\left(A_1{x}_1^{\ast }+A_2{x}_2^{\ast }+A_3{x}_3^{\ast }-b\right)\ge 0,\forall \lambda \in R^l.\hfill \end{array}$ (12)

变分不等式(12)可以通过引用(5)以以下紧凑的形式表达出来：

$\text{VI}\left(\text{Ω},F,\theta \right):\theta \left(x\right)-\theta \left(x^{\ast }\right)+{\left(w-w^{\ast }\right)}^{\text{T}}F\left(w^{\ast }\right)\ge 0,\forall w\in \text{Ω},$ (13)

其中

$\theta \left(x\right)=\theta \left(x_1\right)+\theta \left(x_2\right)+\theta \left(x_3\right).$

根据映射$F$ 在(5)中的定义，我们有：

${\left(w_1-w_2\right)}^{\text{T}}F\left(w_1\right)\ge {\left(w_1-w_2\right)}^{\text{T}}F\left(w_2\right),\forall w\in \text{Ω}.$ (14)

我们用${\Omega }^{*}$ 表示变分不等式$\text{VI}\left(\Omega ,F,\theta \right)$ 的解集，这个解集是非空的。如果$w^{*}=\left(x_1^{*},x_2^{*},x_3^{*},{\lambda }^{*}\right)\in {\Omega }^{*}$ ，那么$\left(x_1^{*},x_2^{*},x_3^{*}\right)$ 就是问题(1)的一个解。

我们在下面的引理中总结了上述定义的矩阵的一些性质。

引理 2.1. 设$\alpha \in \left(0,\left(1+\sqrt{17}\right)/8\right)$ ，$\tau \in \left(\left(1+\alpha \right)/2,1\right)$ ，则分别在(7)、(8)和(9)中定义的矩阵$Q$ ，$M$ 和$H$ 满足：

$H\succcurlyeq 0,HM=Q,$ (15)

和

$G\succcurlyeq 0,G=Q^{\text{T}}+Q-M^{\text{T}}HM.$ (16)

证明。利用$B\succcurlyeq 0$ ，$C\succcurlyeq 0$ 和$r_3>\beta \Vert A_3^{\text{T}}{A}_3\Vert$ 。

$\tilde{H}=\left(\begin{array}{cccc}B& 0& 0& 0\\ 0& \beta A_2^{\text{T}}{A}_2& 0& 0\\ 0& \left(1+\alpha \right)\beta A_2{A}_3^{\text{T}}& \tau \beta A_3^{\text{T}}{A}_3& 0\\ 0& 0& -\frac{1}{2}{A}_3& \frac{1}{2\alpha \beta }{I}_l\end{array}\right),$

是半正定的。注意，$\tilde{H}$ 可以表示为：

$\tilde{H}=\frac{1}{2}\left(\begin{array}{cccc}{I}_{n_1}& 0& 0& 0\\ 0& A_2^{\text{T}}& 0& 0\\ 0& A_3^{\text{T}}& A_3^{\text{T}}& 0\\ 0& 0& 0& I\end{array}\right)\left(\begin{array}{cccc}2B& 0& 0& 0\\ 0& 2\beta & 0& 0\\ 0& 2\alpha \beta & 2\tau \beta & 0\\ 0& 0& -1& \frac{1}{\alpha \beta }\end{array}\right)\left(\begin{array}{cccc}{I}_{n_1}& 0& 0& 0\\ 0& A_2& 0& 0\\ 0& 0& A_3& 0\\ 0& 0& 0& I\end{array}\right).$

由于$\alpha \in \left(0,\left(1+\sqrt{17}\right)/8\right)$ ，我们只需要检查

$\left(\begin{array}{cccc}2B& 0& 0& 0\\ 0& 2\beta & 0& 0\\ 0& 2\alpha \beta & 2\tau \beta & 0\\ 0& 0& -1& \frac{1}{\alpha \beta }\end{array}\right)\succcurlyeq \left(\begin{array}{cccc}2B& 0& 0& 0\\ 0& 2\beta & 0& 0\\ 0& 2\alpha \beta & 2\tau \beta & 0\\ 0& 0& -1& \frac{1}{\beta }\end{array}\right)\succcurlyeq 0,$

回顾$\tau \in \left(\left(1+\alpha \right)/2,1\right)$ ，我们随后明确得到了H的半正定性。

因此，我们将证明在方程(10)中定义的矩阵$G$ 是一个半正定矩阵。同样，通过使用 $\tau >\left(1+\alpha \right)/2,r_2\ge \beta \Vert A_2^{\text{T}}{A}_2\Vert$ 和$r_3>\beta \Vert A_3^{\text{T}}{A}_3\Vert$ ，我们知道，如果以下矩阵是半正定的，那么$G\succcurlyeq 0$ 是有保证的。

$\tilde{G}=\left(\begin{array}{cccc}B& 0& 0& 0\\ 0& \left(1-2\alpha \right)\beta A_2^{\text{T}}{A}_2& \left(1-\alpha \right)\beta A_2{A}_3^{\text{T}}& \left(2\alpha -1\right)A_2\\ 0& -\alpha \beta A_2{A}_3^{\text{T}}& \frac{\left(1-\alpha \right)}{2}\beta A_3^{\text{T}}{A}_3& \left(\alpha -1\right)A_3\\ 0& \left(2\alpha -1\right)A_2& \left(2\alpha -1\right)A_3& \frac{\left(2-2\alpha \right)}{\beta }{I}_l\end{array}\right)\succcurlyeq 0.$

并等价地证明以下方程

$f\left(\alpha \right)=-2{\alpha }^2+\frac{1}{2}\alpha +\frac{1}{2},$

因此，我们得到对于任意$\alpha \in \left(0,\left(1+\sqrt{17}\right)/8\right)$ ，矩阵$G$ 的正半定性自然得以确立。

3. 收敛性分析

在本节中，我们将基于变分不等式建立IPSCPRSM(3)的全局收敛性，并展示它如何被重写为He等人[18] [19]提出的预测–校正框架。最终，我们将展示IPSCPRSM(3)的全局收敛性。

3.1. 预测–校正重构

假设 3.1. 设${\left\{{\rho }_k\right\}}_{k=0}^{\infty }$ 被选择使得：(i) 对于所有$k\ge 0,0\le {\rho }_k\le \rho$ 其中$\rho \in \left[0,1/3\right)$ ，(ii) 由IPSCPRSM(3)生成的序列$\left\{w^k\right\}$ 满足

${\displaystyle \sum _{k=0}^{\infty }{\rho }_k{\Vert w^k-w^{k-1}\Vert }_H^2}<\infty .$ (17)

确保假设3.1的一种方式是选择

${\rho }_k=\min \left\{\rho ,1/{\left(k{\Vert w^k-w^{k-1}\Vert }_H\right)}^2\right\}$

假设3.2. 设问题(1)的解集非空。

辅助变量$\left\{{\tilde{w}}^k\right\}$ 表示预测变量，而$\left\{w^{k+1}\right\}$ 表示校正变量。下面，我们展示IPSCPRSM (3)的预测步骤的结果。

$\theta \left(x\right)-\theta \left({\tilde{x}}^k\right)+{\left(w-{\tilde{w}}^k\right)}^{\text{T}}F\left({\tilde{w}}^k\right)\ge {\left(w-{\tilde{w}}^k\right)}^{\text{T}}Q\left({\overline{w}}^k-{\tilde{w}}^k\right),\forall w\in \Omega .$ (18)

其中$Q$ 在(7)中定义。

证明。基于(3)中$x_1$ 子问题的一阶最优性条件，我们得到

${\theta }_1\left(x_1\right)-{\theta }_1\left({\tilde{x}}_1^k\right)+{\left(x_1-{\tilde{x}}_1^k\right)}^{\text{T}}\left[-A_1^{\text{T}}{\tilde{\lambda }}^k+B\left({\tilde{x}}_1^k-{\overline{x}}_1^k\right)\right]\ge 0,\forall x_1\in {\mathcal{X}}_1\text{.}$ (19)

类似地，结合最优性条件和(5)，我们得到${\tilde{x}}_2^k\in {\mathcal{X}}_2$和

${\theta }_2\left(x_2\right)-{\theta }_2\left({\tilde{x}}_2^k\right)+{\left(x_2-{\tilde{x}}_2^k\right)}^{\text{T}}\left[-A_2^{\text{T}}{\overline{\lambda }}^k+\beta A_2^{\text{T}}\left(A_1{x}_1^{k+1}+A_2{x}_2^{k+1}+A_3{\overline{x}}_3^k-b\right)+C\left(x_2^{k+1}-{\overline{x}}_2^k\right)\right]\ge 0,\forall x_2\in {\mathcal{X}}_2\text{.}$

从方程(6)我们推导出

$\beta \left(A_1{x}_1^{k+1}+A_2{x}_2^{k+1}+A_3{\overline{x}}_3^k-b\right)=\left({\overline{\lambda }}^k-{\tilde{\lambda }}^k\right)+\beta A_2\left(x_2^{k+1}-{\overline{x}}_2^k\right).$ (20)

将方程(20)代入上述不等式中，我们得到

${\theta }_2\left(x_2\right)-{\theta }_2\left({\tilde{x}}_2^k\right)+{\left(x_2-{\tilde{x}}_2^k\right)}^{\text{T}}\left[-A_2^{\text{T}}{\tilde{\lambda }}^k+\left(\beta A_2^{\text{T}}{A}_2+C\right)\left({\tilde{x}}_2^k-{\overline{x}}_2^k\right)\right]\ge 0,\forall x_2\in {\chi }_2.$ (21)

类似地，我们有

$\begin{array}{l}{\theta }_3\left(x_3\right)-{\theta }_3\left({\tilde{x}}_3^k\right)+{\left(x_3-{\tilde{x}}_3^k\right)}^{\text{T}}\left[-A_3^{\text{T}}{\lambda }^{k+\frac{1}{2}}+\beta A_3^{\text{T}}\left(A_1{\tilde{x}}_1^k+A_2{\tilde{x}}_2^k+A_3{\tilde{x}}_3^k-b\right)+D\left({\tilde{x}}_3^k-{\overline{x}}_3^k\right)\right]\ge 0,\forall x_3\in {\chi }_3.\hfill \end{array}$

根据(6)中对${\tilde{w}}^k$ 的定义和(3)中的方案，我们推导出

${\lambda }^{k+\frac{1}{2}}={\overline{\lambda }}^k+\alpha \left({\tilde{\lambda }}^k-{\overline{\lambda }}^k\right)-\alpha \beta A_2\left(x_2^{k+1}-{\overline{x}}_2^k\right).$ (22)

将方程(22)和${\tilde{\lambda }}^k={\overline{\lambda }}^k-\beta \left(A_1{\tilde{x}}_1^k+A_2{\overline{x}}_2^k+A_3{\overline{x}}_3^k-b\right)$ 代入上述不等式中，我们得到

$\begin{array}{l}\begin{array}{l}{\theta }_3\left(x_3\right)-{\theta }_3\left({\tilde{x}}_3^k\right)+{\left(x_3-{\tilde{x}}_3^k\right)}^{\text{T}}\left[-A_3^{\text{T}}{\tilde{\lambda }}^k+\left(1+\alpha \right)\beta A_2{A}_3^{\text{T}}\left({\tilde{x}}_2^k-{\overline{x}}_2^k\right)+\left(\beta A_3^{\text{T}}{A}_3+D\right)\left({\tilde{x}}_3^k-{\overline{x}}_3^k\right)-A_3^{\text{T}}\alpha \left({\tilde{\lambda }}^k-{\overline{\lambda }}^k\right)\right]\ge 0,\\ \forall x_3\in {\chi }_3.\end{array}\hfill \end{array}$(23)

最后，我们可以将(6)中的关系式${\tilde{\lambda }}^k={\overline{\lambda }}^k-\beta \left(A_1{x}_1^{k+1}+A_2{\overline{x}}_2^k+A_3{\overline{x}}_3^k-b\right)$ 重写为

${\left(\lambda -{\tilde{\lambda }}^k\right)}^{\text{T}}\left[{\tilde{r}}^k-A_2\left({\tilde{x}}_2^k-{\overline{x}}_2^k\right)-A_3\left({\tilde{x}}_3^k-{\overline{x}}_3^k\right)+\frac{1}{\beta }\left({\tilde{\lambda }}^k-{\overline{\lambda }}^k\right)\right]\ge 0,\forall \lambda \in R^l.$ (24)

结合(19)、(21)、(23)和(24)，我们可以直接得到断言(18)。

现在我们来说明如何使用预测变量${\tilde{w}}^k$ 和前一个点${\overline{w}}^k$ 来构造校正点$w^{k+1}$ 。

引理3.2. 设$\left\{w^k\right\}$ 由IPSCPRSM(3)生成，$\left\{{\tilde{w}}^k\right\}$ 在(6)中定义。那么，我们有

${\overline{w}}^k-w^{k+1}=M\left({\overline{w}}^k-{\tilde{w}}^k\right),$ (25)

其中M在(8)中定义。

证明。根据(6)

${\overline{\lambda }}^k-{\tilde{\lambda }}^k=\beta \left(A_1{x}_1^{k+1}+A_2{\overline{x}}_2^k+A_3{\overline{x}}_3^k-b\right).$

利用${\tilde{w}}^k$ 的表示，以及(3)、(5)和(22)，我们得出结论

${\lambda }^{k+1}={\overline{\lambda }}^k-\left[2\alpha \left({\overline{\lambda }}^k-{\tilde{\lambda }}^k\right)-2\alpha \beta A_2\left({\overline{x}}_2^k-{\tilde{x}}_2^k\right)-\alpha \beta A_3\left({\overline{x}}_3^k-{\tilde{x}}_3^k\right)\right].$

因此，我们有以下关系

$\left(\begin{array}{l}{x}_1^{k+1}\hfill \\ x_2^{k+1}\hfill \\ x_3^{k+1}\hfill \\ {\lambda }^{k+1}\hfill \end{array}\right)=\left(\begin{array}{l}{\overline{x}}_1^k\hfill \\ {\overline{x}}_2^k\hfill \\ {\overline{x}}_3^k\hfill \\ {\overline{\lambda }}^k\hfill \end{array}\right)-\left(\begin{array}{cccc}{I}_{n_1}& 0& 0& 0\\ 0& I_{n_2}& 0& 0\\ 0& 0& I_{n_3}& 0\\ 0& -2\alpha \beta A_2& -\alpha \beta A_3& 2\alpha I_l\end{array}\right)\left(\begin{array}{l}{\overline{x}}_1^k-{\tilde{x}}_1^k\hfill \\ {\overline{x}}_2^k-{\tilde{x}}_2^k\hfill \\ {\overline{x}}_3^k-{\tilde{x}}_3^k\hfill \\ {\overline{\lambda }}^k-{\tilde{\lambda }}^k\hfill \end{array}\right),$

它可以被改写成一个简洁的形式

$w^{k+1}={\overline{w}}^k-M\left({\overline{w}}^k-{\tilde{w}}^k\right),$

其中M在式(8)中定义。

3.2. 全局收敛性

在本节中，我们展示了IPSCPRSM (3)的全局收敛性，并考察了其迭代复杂度。

引理3.3. 设$\left\{w^k\right\}$ 由IPSCPRSM (3)生成，$\left\{{\tilde{w}}^k\right\}$ 在(6)中定义。那么对于任何${\tilde{w}}^k\in \Omega$ ，我们有

${\left(w-{\tilde{w}}^k\right)}^{\text{T}}Q\left({\overline{w}}^k-{\tilde{w}}^k\right)=\frac{1}{2}\left({\Vert w-w^{k+1}\Vert }_H^2-{\Vert w-{\overline{w}}^k\Vert }_H^2\right)+\frac{1}{2}{\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_G^2.$ (26)

证明。结合$Q=HM$ (15)和$\left({\overline{w}}^k-w^{k+1}\right)=M\left({\overline{w}}^k-{\tilde{w}}^k\right)$ (25)，我们推导出

${\left(w-{\tilde{w}}^k\right)}^{\text{T}}Q\left({\overline{w}}^k-{\tilde{w}}^k\right)={\left(w-{\tilde{w}}^k\right)}^{\text{T}}HM\left({\overline{w}}^k-{\tilde{w}}^k\right)={\left(w-{\tilde{w}}^k\right)}^{\text{T}}H\left({\overline{w}}^k-w^{k+1}\right).$

对于一个对称矩阵$H$ 和向量$a,b,c,d\in R^t$ ，它遵循以下恒等式

${\left(a-b\right)}^{\text{T}}H\left(c-d\right)=\frac{1}{2}\left({\Vert a-d\Vert }_H^2-{\Vert a-c\Vert }_H^2\right)+\frac{1}{2}\left({\Vert c-b\Vert }_H^2-{\Vert d-b\Vert }_H^2\right).$

应用上述恒等式，令$a=w,b={\tilde{w}}^k,c={\overline{w}}^k,d=w^{k+1}$ ，得到

$\begin{array}{l}{\left(w-{\tilde{w}}^k\right)}^{\text{T}}H\left({\overline{w}}^k-w^{k+1}\right)=\frac{1}{2}\left({\Vert w-w^{k+1}\Vert }_H^2-{\Vert w-{\overline{w}}^k\Vert }_H^2\right)\\ +\frac{1}{2}\left({\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_H^2-{\Vert w^{k+1}-{\tilde{w}}^k\Vert }_H^2\right)\text{.}\end{array}$ (27)

对于(27)中的最后一项，我们可以推导出

$\begin{array}{l}{\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_H^2-{\Vert w^{k+1}-{\tilde{w}}^k\Vert }_H^2\\ ={\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_H^2-{\Vert \left({\overline{w}}^k-{\tilde{w}}^k\right)-M\left({\overline{w}}^k-{\tilde{w}}^k\right)\Vert }_H^2\\ ={\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_G^2.\end{array}$ (28)

现在，结合(10)、(27)和(28)，我们得到断言(26)。

有了3.1和3.3两个引理，我们可以得到以下结果。

引理3.4. 设$\left\{w^k\right\}$ 由IPSCPRSM (3)生成，$\left\{{\tilde{w}}^k\right\}$ 在(6)中定义。那么，我们有

$\theta \left(x\right)-\theta \left({\tilde{x}}^k\right)+{\left(w-{\tilde{w}}^k\right)}^{\text{T}}F\left({\tilde{w}}^k\right)\ge \frac{1}{2}\left({\Vert w-w^{k+1}\Vert }_H^2-{\Vert w-{\overline{w}}^k\Vert }_H^2\right)+\frac{1}{2}{\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_G^2,\forall w\in \Omega .$ (29)

证明。通过关联(18)和(26)来验证恒等式(29)。

引理3.5. 设$\left\{w^k\right\}$ 由IPSCPRSM (3)生成，那么对于任何$w^{k+1}\in \Omega$ ，我们有

$\begin{array}{l}\theta \left(x\right)-\theta \left(x^{k+1}\right)+{\left(w-w^{k+1}\right)}^{\text{T}}\left[F\left(w^{k+1}\right)+H\left(w^{k+1}-{\overline{w}}^k\right)\right]\hfill \\ \ge \beta {\left(r^{k+1}\right)}^{\text{T}}{A}_2\left({\overline{x}}_2^k-x_2^{k+1}\right)+\left(1-\alpha \right)\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_3\left({\overline{x}}_3^k-x_3^{k+1}\right)+\left(1-2\alpha \right)\beta {\Vert r^{k+1}\Vert }^2.\hfill \end{array}$ (30)

其中$r$ 在(5)中定义。

借助引理3.5，我们使用基本不等式推导出下一个引理。

引理3.6. 设$\left\{w^k\right\}$ 由IPSCPRSM (3)生成，那么对于任何$w^{k+1}\in \Omega$ ，我们有

$\begin{array}{l}-\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_2\left({\overline{x}}_2^k-x_2^{k+1}\right)-\left(1-\alpha \right)\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_3\left({\overline{x}}_3^k-x_3^{k+1}\right)-\left(1-2\alpha \right)\beta {\Vert r^{k+1}\Vert }^2\\ \le \frac{1}{2}{\Vert w^{k+1}-{\overline{w}}^k\Vert }_{M_0}^2.\end{array}$ (31)

其中

$M_0=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& \beta A_2^{\text{T}}{A}_2+C& 0& 0\\ 0& \left(1+\alpha \right)\beta A_2{A}_3^{\text{T}}& \beta A_3^{\text{T}}{A}_3+D& 0\\ 0& 0& -\frac{1}{2}{A}_3& \frac{1}{2\alpha \beta }{I}_l\end{array}\right),$ (32)

和

$H_0=\left(\begin{array}{ccc}\beta A_2^{\text{T}}{A}_2& 0& 0\\ \left(1+\alpha \right)\beta A_2{A}_3^{\text{T}}& \beta A_3^{\text{T}}{A}_3& 0\\ 0& -\frac{1}{2}{A}_3& \frac{1}{2\alpha \beta }{I}_l\end{array}\right).$ (33)

证明。根据(32)的定义，我们有

$\frac{1}{2}{\Vert w^{k+1}-{\overline{w}}^k\Vert }_{M_0}^2=\frac{1}{2}{\Vert v^{k+1}-{\overline{v}}^k\Vert }_{H_0}^2+\frac{1}{2}{\Vert x_2^{k+1}-{\overline{x}}_2^k\Vert }_C^2+\frac{1}{2}{\Vert x_3^{k+1}-{\overline{x}}_3^k\Vert }_D^2.$

类似地，根据(33)中$H_0$ 的关系，我们得到

$\begin{array}{l}\frac{1}{2}{\Vert v^{k+1}-{\overline{v}}^k\Vert }_{H_0}^2\\ =\frac{1}{2}\beta A_2^2{\left(x_2^{k+1}-{\overline{x}}_2^k\right)}^2+\frac{1}{2}\left(1+\alpha \right)\beta A_2{A}_3^{\text{T}}{\left(x_2^{k+1}-{\overline{x}}_2^k\right)}^{\text{T}}\left(x_3^{k+1}-{\overline{x}}_3^k\right)\\ +\frac{1}{2}\beta A_3^2{\left(x_3^{k+1}-{\overline{x}}_3^k\right)}^2-\frac{1}{4}{A}_3{\left(x_3^{k+1}-{\overline{x}}_3^k\right)}^{\text{T}}\left({\lambda }^{k+1}-{\overline{\lambda }}^k\right)+\frac{1}{4\alpha \beta }{\left({\lambda }^{k+1}-{\overline{\lambda }}^k\right)}^2.\end{array}$

通过使用(4)中$C,D$ 的定义以及$\tau >\left(1+\alpha \right)/2，\alpha \in \left(0,\left(1+\sqrt{17}\right)/8\right)$ ，我们推导出

$\begin{array}{l}\frac{1}{2}{\Vert w^{k+1}-{\overline{w}}^k\Vert }_{M_0}^2\\ \ge \alpha \beta {\left(r^{k+1}\right)}^2+\frac{1-\alpha }{4}\beta A_3^2{\left(x_3^{k+1}-{\overline{x}}_3^k\right)}^2-\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_2\left({\overline{x}}_2^k-x_2^{k+1}\right).\end{array}$ (34)

由于$\alpha \in \left(0,\left(1+\sqrt{17}\right)/8\right)$ ，应用$a^{\text{T}}b\le a^2+\frac{1}{4}{b}^2$ 与$a=r^{k+1}$ 和$b=A_3\left(x_3^{k+1}-{\overline{x}}_3^k\right)$ 的不等式，我们可以得出

$-\left(1-\alpha \right)\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_3\left({\overline{x}}_3^k-x_3^{k+1}\right)-\left(1-2\alpha \right)\beta {\Vert r^{k+1}\Vert }^2\le \alpha \beta {\Vert r^{k+1}\Vert }^2+\frac{1-\alpha }{4}\beta {\Vert A_3\left(x_3^{k+1}-{\overline{x}}_3^k\right)\Vert }^2.$ (35)

将(34)和(35)结合起来，我们可以直接得到断言(31)。

参考(9)中$H$ 的定义，(32)中$M_0$ 的定义，以及(4)中矩阵$B$ 的正半定性，还有矩阵$C$ 和$D$ 的定义，我们得到$M_0\preccurlyeq H$ 。

引理3.7. 设$\left\{w^k\right\}$ 由IPSCPRSM (3)生成，则对于任何$w^{*}\in {\Omega }^{*}$ ，我们有${\displaystyle {\sum }_{k=0}^{\infty }{\Vert w^k-w^{*}\Vert }_H^2}<\infty$ 。

证明。通过将$w=w^{k+1}$ 代入(16)中，以及将$w=w^{*}$ 代入(30)中，我们得到

$\theta \left(x^{k+1}\right)-\theta \left(x^{*}\right)+{\left(w^{k+1}-w^{*}\right)}^{\text{T}}F\left(w^{*}\right)\ge 0.$

和

$\begin{array}{l}\theta \left(x^{*}\right)-\theta \left(x^{k+1}\right)+{\left(w^{*}-w^{k+1}\right)}^{\text{T}}\left[F\left(w^{k+1}\right)+H\left(w^{k+1}-{\overline{w}}^k\right)\right]\hfill \\ \ge \beta {\left(r^{k+1}\right)}^{\text{T}}{A}_2\left({\overline{x}}_2^k-x_2^{k+1}\right)+\left(1-\alpha \right)\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_3\left({\overline{x}}_3^k-x_3^{k+1}\right)+\left(1-2\alpha \right)\beta {\Vert r^{k+1}\Vert }^2.\hfill \end{array}$

将它们相加并结合(14)，我们得到

$\begin{array}{l}{\left(w^{k+1}-w^{*}\right)}^{\text{T}}H\left(w^{k+1}-{\overline{w}}^k\right)+\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_2\left({\overline{x}}_2^k-x_2^{k+1}\right)\\ +\left(1-\alpha \right)\beta {\left(r^{k+1}\right)}^{\text{T}}{A}_3\left({\overline{x}}_3^k-x_3{}^{k+1}\right)+\left(1-2\alpha \right)\beta {\Vert r^{k+1}\Vert }^2\le 0.\end{array}$ (36)

通过回顾(3)，我们有

${\overline{w}}^k=w^k+{\rho }_k\left(w^k-w^{k-1}\right).$ (37)

因此可以得出

$\begin{array}{l}{\left(w^{k+1}-w^{*}\right)}^{\text{T}}H\left(w^{k+1}-{\overline{w}}^k\right)\\ ={\phi }_{k+1}-{\phi }_k-{\rho }_k\left({\phi }_k-{\phi }_{k-1}\right)+\frac{1}{2}{\Vert w^{k+1}-w^k\Vert }_H^2-\frac{{\rho }_k}{2}{\Vert w^k-w^{k-1}\Vert }_H^2\\ -{\rho }_k{\left(w^{k+1}-w^k\right)}^{\text{T}}H\left(w^k-w^{k-1}\right).\end{array}$ (38)

结合(31)、(36)和(38)，我们得到

$\begin{array}{l}{\phi }_{k+1}-{\phi }_k-{\rho }_k\left({\phi }_k-{\phi }_{k-1}\right)\\ \le -\frac{1}{2}{\Vert w^{k+1}-w^k\Vert }_H^2+\frac{{\rho }_k}{2}{\Vert w^k-w^{k-1}\Vert }_H^2\\ \text{ +}{\rho }_k{\left(w^{k+1}-w^k\right)}^{\text{T}}H\left(w^k-w^{k-1}\right)+\frac{1}{2}{\Vert w^{k+1}-{\overline{w}}^k\Vert }_{M_0}^2.\end{array}$ (39)

将此与关系式(37)结合起来，注意$M_0\preccurlyeq H$ ，我们得出

${\phi }_{k+1}-{\phi }_k-{\rho }_k\left({\phi }_k-{\phi }_{k-1}\right)\le \frac{{\rho }_k+{\rho }_k{}^2}{2}{\Vert w^k-w^{k-1}\Vert }_H^2.$

因为${\rho }_k\in \left[0,1/3\right)$ ，这意味着$\left({\rho }_k+{\rho }_k^2\right)/2\le {\rho }_k$ ，那么我们有

${\phi }_{k+1}-{\phi }_k-{\rho }_k\left({\phi }_k-{\phi }_{k-1}\right)\le {\rho }_k{\Vert w^k-w^{k-1}\Vert }_H^2.$ (40)

令${\theta }_k={\phi }_k-{\phi }_{k-1}，{\delta }_k={\rho }_k{\Vert w^k-w^{k-1}\Vert }_H^2$ ，关系(40)表明${\theta }_{k+1}\le {\rho }_k{\theta }_k+{\delta }_k\le \rho {[{\theta }_k]}_{+}+{\delta }_k,$

注意$w^0=w^{-1}$ ，那么${\theta }_0={\left[{\theta }_0\right]}_{+}=0$ ，${\delta }_0=0$ 。通过假设3.1，我们得到

${\displaystyle \sum _{k=0}^{\infty }{\left[{\theta }_k\right]}_{+}}\le \frac{1}{1-\rho }{\displaystyle \sum _{k=0}^{\infty }{\delta }_k}=\frac{1}{1-\rho }{\displaystyle \sum _{k=1}^{\infty }{\delta }_k}<\infty .$ (41)

令$m_k={\phi }_k-{\displaystyle \sum _{j=1}^k{\left[{\theta }_j\right]}_{+}}$ ，结合(41)和${\phi }_k\ge 0$ ,我们得到了序列$\left\{m_k\right\}$ 的下界。另一方面

$m_{k+1}={\phi }_{k+1}-{\left[{\theta }_{k+1}\right]}_{+}-{\displaystyle \sum _{j=1}^k{\left[{\theta }_j\right]}_{+}}\le {\phi }_{k+1}-{\theta }_{k+1}-{\displaystyle \sum _{j=1}^k{\left[{\theta }_j\right]}_{+}}={\phi }_k-{\displaystyle \sum _{j=1}^k{\left[{\theta }_j\right]}_{+}}=m_k.$

这意味着$\left\{m_k\right\}$ 是一个单调非增序列，因此$\left\{m_k\right\}$ 收敛到

$\underset{k\to \infty }{\lim }{\phi }_k={\displaystyle \sum _{j=1}^{\infty }{\left[{\theta }_j\right]}_{+}}+\underset{k\to \infty }{\lim }{m}_k.$

因此，$\left\{{\phi }_k\right\}$ 收敛，并且作为结果，${\displaystyle {\sum }_{k=0}^{\infty }{\Vert w^k-w^{*}\Vert }_H^2}<\infty$ 也成立。引理3.7得证。

接下来的引理总结了有助于分析式(3)收敛性的几个关键事实。

引理3.8. 设$\left\{w^k\right\}$ 由IPSCPRSM (3)生成，则对于任何$w^{k+1}\in \Omega$ ，我们有

${\displaystyle \sum _{k=0}^{\infty }{\Vert w^{k+1}-{\overline{w}}^k\Vert }_G^2}<\infty ,\forall w\in \Omega .$ (42)

证明。利用$F$ 的单调性，可以得到

${\left(w-{\tilde{w}}^k\right)}^{\text{T}}F\left(w\right)\ge {\left(w-{\tilde{w}}^k\right)}^{\text{T}}F\left({\tilde{w}}^k\right).$

将上述不等式代入方程(18)，我们得到

$\theta \left(x\right)-\theta \left({\tilde{x}}^k\right)+{\left(w-{\tilde{w}}^k\right)}^{\text{T}}F\left(w\right)\ge {\left(w-{\tilde{w}}^k\right)}^{\text{T}}Q\left({\overline{w}}^k-{\tilde{w}}^k\right),\forall w\in \Omega .$

设置$w=w^{*}$ 和式(13)，我们得到

${\left({\tilde{w}}^k-w^{*}\right)}^{\text{T}}Q\left({\overline{w}}^k-{\tilde{w}}^k\right)\ge 0,\forall w\in \Omega .$

将$w=w^{*}$ 代入(26)中，我们得到

${\left(w^{*}-{\tilde{w}}^k\right)}^{\text{T}}Q\left({\overline{w}}^k-{\tilde{w}}^k\right)=\frac{1}{2}\left({\Vert w^{*}-w^{k+1}\Vert }_H^2-{\Vert w^{*}-{\overline{w}}^k\Vert }_H^2\right)+\frac{1}{2}{\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_G^2.$

因为${\left({\tilde{w}}^k-w^{*}\right)}^{\text{T}}Q\left({\overline{w}}^k-{\tilde{w}}^k\right)\ge 0$，我们有

${\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_G^2\le -{\Vert w^{k+1}-w^{*}\Vert }_H^2+{\Vert {\overline{w}}^k-w^{*}\Vert }_H^2.$

根据${\overline{w}}^k$ 的定义以及关系式${\Vert a+b\Vert }_H^2\le 2{\Vert a\Vert }_H^2+2{\Vert b\Vert }_H^2$ ，我们有

${\Vert {\overline{w}}^k-{\tilde{w}}^k\Vert }_G^2\le 2{\Vert w^k-w^{*}\Vert }_H^2-{\Vert w^{k+1}-w^{*}\Vert }_H^2+2{\Vert {\rho }_k\left(w^k-w^{k-1}\right)\Vert }_H^2.$

从$k=0$ 到$k=\infty$ 对两边求和。回顾假设3.1、引理3.7和式(41)，引理3.8得证。

借助引理3.7和3.8，以下定理证明了由IPSCPRSM (3)生成的序列的渐近可行性以及目标函数的收敛性定理。

定理3.1. 设${\left\{{\alpha }_k\right\}}_{k=0}^{\infty }$ 满足假设3.1，$\alpha \in \left(0,\left(1+\sqrt{17}\right)/8\right)$ ，$\beta >0$ 。由IPSCPRSM (3)生成的无限序列是${\left\{w^k\right\}}_{k=0}^{\infty }$ ，因此我们有

(i) ${\displaystyle \sum _{k=1}^{\infty }{\Vert r^k\Vert }^2}<\infty$ ，因此$\underset{k\to \infty }{\lim }\Vert r^k\Vert =0$ ，其中$r^k=A_1{x}_1^k+A_2{x}_2^k+A_3{x}_3^k-b$ ；

(ii) 当$k\to \infty$ 时，目标函数值${\theta }_1\left(x_1^k\right)+{\theta }_2\left(x_2^k\right)+{\theta }_3\left(x_3^k\right)$ 收敛到(1)的最优值；

(iii) 序列$\left\{w^k\right\}$ 收敛到${\Omega }^{*}$ 中的点$w^{\infty }$ 。

以下定理为所提出的IPSCPRSM (3)提供了特定的渐近复杂度结果。我们展示了IPSCPRSM (3)能够找到一个近似解，该解对于变分不等式$\text{VI}\left(\Omega ,F,\theta \right)$ 的精度为$o\left(1/\sqrt{k}\right)$ 。我们给出以下定理

定理3.2. 假设序列$\left\{w^k\right\}$ 由IPSCPRSM (3)生成，当$k\to \infty$ 时。

(i) ${\min }_{1\le i\le k}{\Vert w^i-{\overline{w}}^{i-1}\Vert }_G=o\left(1/\sqrt{k}\right)$ ；

(ii) ${\min }_{1\le i\le k}\Vert r^i\Vert =o\left(1/\sqrt{k}\right)$ ；

(iii) ${\min }_{1\le i\le k}\left|{\theta }_1\left(x_1^i\right)+{\theta }_2\left(x_2^i\right)+{\theta }_3\left(x_3^i\right)-{\theta }_1\left(x_1^{*}\right)-{\theta }_2\left(x_2^{*}\right)-{\theta }_3\left(x_3^{*}\right)\right|=o\left(1/\sqrt{k}\right)$ 。

4. 数值实验

在这一部分，我们通过将IPSCPRSM应用于一个特定用例：鲁棒PCA，来展示其实际效果。我们展示了IPSCPRSM的初始数值结果，并将其性能与VASALM [20]和EADMM [21]进行了评估。

我们可以使用以下鲁棒PCA模型来描述它。

$\begin{array}{l}\min {\Vert X\Vert }_{*}+\tau {\Vert Y\Vert }_1+\frac{1}{2\mu }{\Vert P_{\Omega }\left(Z\right)\Vert }_F^2,\\ \text{s}.\text{t}.X+Y+Z=N,\end{array}$ (43)

其中$N\in {ℝ}^{g\times n},{\Vert .\Vert }_{*}$ 表示核范数(一个矩阵所有奇异值的和)，${\Vert .\Vert }_1$ 表示促进稀疏性的$l_1$ 范数，定义为所有条目的绝对值之和，并且$\tau >0$ 是一个平衡参数，$\mu >0$ 是一个控制高斯噪声包含的小常数。$\Omega$ 是集合$\left\{1,2,\cdots ,g\right\}\times \left\{1,2,\cdots ,n\right\}$ 的一个子集，而$P_{\Omega }(\cdot ):{ℝ}^{g\times n}\to {ℝ}^{g\times n}$ 是对应的投影算子。

然后，我们可以将(43)重新表述，使其适合于可分离的凸优化(1)的范畴。具体来说，设

$\left(x_1,x_2,x_3\right)=\left(X,Y,Z\right),A_i=I_p,i=1,2,3,b=N,$

和

${\theta }_1\left(x_1\right)={\Vert X\Vert }_{*},{\theta }_2\left(x_2\right)=\tau {\Vert Y\Vert }_1,{\theta }_3\left(x_3\right)=\frac{1}{2\mu }{\Vert P_{\Omega }\left(Z\right)\Vert }_F^2.$

因此，所提出的IPSCPRSM是适用的。首先，让我们引入两个重要的算子。这些算子对于获得封闭形式的解是有用的。设$c>0$ 为一个常数，$E\in {ℝ}^{g\times n}$ 为一个给定的矩阵。对于矩阵变量的收缩算子$\text{shrink}\left(\cdot ,\cdot \right)$ 定义如下：

${\left(\text{shrink}\left(E,c\right)\right)}_{ij}:=\text{sign}\left(E_{ij}\right)\cdot \max \left\{\left|E_{ij}\right|-c,0\right\},1\le i\le g,1\le j\le n.$

此外，我们在奇异值域中定义算子$S_c(\cdot ):{ℝ}^{g\times n}\to {ℝ}^{g\times n}$ 如下：

$S_c\left(E\right)=U\text{diag}\left(\text{shrink}\left(\Sigma ,c\right)\right)V^{\text{T}},\forall E\in {ℝ}^{g\times n}.$

设$\Lambda \in {ℝ}^{g\times n}$ 是与问题(43)中的线性约束相关联的拉格朗日乘子。接下来，我们将详细说明应用IPSCPRSM到问题(43)时产生的子问题的显式表述。

$X$ 子问题可以通过以下方式显式求解：

$\begin{array}{l}{X}^{k+1}=\arg \underset{X}{\min }\left\{{\Vert X\Vert }_{*}-{\left({\overline{\lambda }}^k\right)}^{\text{T}}X+\frac{\beta }{2}{\Vert X+{\overline{Y}}^k+{\overline{Z}}^k-N\Vert }^2+\frac{1}{2}{\Vert X-{\overline{X}}^k\Vert }_B^2\right\}\\ =S_{\frac{1}{r_1}}\left[\frac{1}{r_1}\left(\left(r_1-\beta \right){\overline{X}}^k-\beta {\overline{Y}}^k-\beta {\overline{Z}}^k+{\overline{\lambda }}^k+\beta N\right)\right].\end{array}$

$Y$ 子问题可以通过以下方式求解：

$\begin{array}{l}{Y}^{k+1}=\arg \underset{Y}{\min }\left\{\tau {\Vert Y\Vert }_1-{\overline{\lambda }}^{k}Y+\frac{\beta }{2}{\Vert X^{k+1}+Y+{\overline{Z}}^k-N\Vert }^2+\frac{1}{2}{\Vert Y-{\overline{Y}}^k\Vert }_C^2\right\}\hfill \\ =\text{shrink}\left(\frac{1}{r_2}\left(\beta N+\left(r_2-\beta \right){\overline{Y}}^k-\beta {\overline{Z}}^k-\beta X^{k+1}+{\overline{\lambda }}^k\right),\frac{\tau }{r_2}\right).\hfill \end{array}$

更新拉格朗日乘子${\Lambda }^{k+\frac{1}{2}}$ 通过

${\Lambda }^{k+\frac{1}{2}}={\overline{\Lambda }}^k-\alpha \beta \left(X^{k+1}+Y^{k+1}+{\overline{Z}}^k-N\right).$

$Z$ 子问题可以通过以下方式求解：

$\begin{array}{l}{Z}^{k+1}=\arg \underset{Z}{\min }\left\{\frac{1}{2\mu }{\Vert P_{\Omega }\left(Z\right)\Vert }_F^2-{\left({\lambda }^{k+\frac{1}{2}}\right)}^{\text{T}}Z+\frac{\beta }{2}{\Vert X^{k+1}+Y^{k+1}+Z-N\Vert }^2\right\}\\ +\frac{1}{2}{\Vert Z-{\overline{Z}}^k\Vert }_D^2.\end{array}$

其中${\tilde{\Lambda }}^k={\Lambda }^{k+\frac{1}{2}}-\beta \left(X^{k+1}+Y^{k+1}+{\overline{Z}}^k-N\right)$。那么，$\text{Z}$ 的封闭形式解描述如下：

$\begin{array}{l}{Z}_{ij}^k=\{\begin{array}{l}\frac{\mu \tau r_3}{1+\mu \tau r_3}{\tilde{Z}}_{ij}^k,\text{ if}\left(i,j\right)\in \Omega \hfill \\ {\tilde{Z}}_{ij}^k,\text{ otherwise}\hfill \end{array}\hfill \end{array}$

其中${\tilde{Z}}^k={\overline{Z}}^k+\frac{1}{\tau r_3}{\tilde{\Lambda }}^k$。

对偶变量${\Lambda }^{k+1}$ 可以更新为

${\Lambda }^{k+1}={\Lambda }^{k+\frac{1}{2}}-\alpha \beta \left(X^{k+1}+Y^{k+1}+Z^{k+1}-N\right)$ .

为了展示所提出方法解决(43)问题的可行性和有效性。在这一部分中，我们将使用合成数据测试我们的算法，正如[20]中所测试的那样。具体来说，设$N=X^{*}+Y^{*}$ 为观测矩阵，其中$X^{*}$ 和$Y^{*}$ 分别是$N$ 的待恢复的低秩和稀疏分量。$X^{*}$ 是作为$X^{*}=L^{\text{T}}R$ 生成的，其中$L$ 和$R$ 是两个全行秩矩阵，$L$ 和$R$ 的条目是独立同分布的高斯值，均值为零，方差为单位方差。对于稀疏分量$Y^{*}$ ，其非零条目在区间$\left[-\text{500,500}\right]$ 内均匀随机生成。索引集$\Omega$ 是随机确定的，有一个预设的样本比率(用sr表示)，定义为$sr=\left(\left|\Omega \right|/gn\right)$ ，其中$\left|\Omega \right|$ 是$\Omega$ 的基数。设$\text{rr}$ 为低秩比率(定义为$rr=\vartheta /g$ )，并且设$\text{spr}$ 为稀疏比率($spr={\Vert Y^{*}\Vert }_0/gn$ ，其中${\Vert .\Vert }_0$ 表示非零条目的数量)。最后，观测数据被均值为零、标准差$\sigma ={10}^{-3}$ 的高斯噪声污染。在实验中，我们设定了$\tau =1/\sqrt{g}$ 和$\mu =\sqrt{g+\sqrt{8g\delta }}/10$ 。对于测试数据，在本节中，我们只考虑样本比率$\text{sr = 80\%}$ 和$g=n\in \{500,1000\}$ 的情况。相应地，我们分别测试了两个场景，其中$rr\in \left\{0.05,0.10\right\}$ 和三个场景，其中$spr\in \left\{0.05,0.10,0.15\right\}$ 。

在我们的实验中，所有变量都初始化在原点。整个实验过程中，停止准则是

$\max \left\{\frac{{\Vert X^{k+1}-X^k\Vert }_F}{1+{\Vert X^k\Vert }_F},\frac{{\Vert Y^{k+1}-Y^k\Vert }_F}{1+{\Vert Y^k\Vert }_F}\right\}<tol.$

其中$\text{tol > 0}$ 是一个容差参数，我们设定$tol:={10}^{-4}$ 。

在我们的实验中，所有变量都初始化为原点。在实验中，惩罚参数$\beta$ 是通过$\beta =\widehat{t}\left|\Omega \right|/{\Vert P_{\Omega }\left(N\right)\Vert }_1$ 来确定的，对于所有测试的方法，其中$\widehat{t}$ 分别对应于$\text{spr = 0}\text{.05,0}\text{.10}$ 和0.15的情况，取值为0.05,0.10和0.20。

为了说明效率，我们将所提出的IPSCPRSM与[20]中的VASALM和[21]中的EADMM进行了比较。对于VASALM，我们设定$\eta =2.01$ 。对于我们的方法，我们设定$\alpha =\left(1+\sqrt{17}\right)/8$ ，并且对于IPSCPRSM，我们设定${\rho }_k=0.3$ 。数值结果在表1中给出，其中Iter.、Time和Tol分别代表迭代次数、计算时间(以秒为单位)以及恢复的低秩分量的相对误差(即${\Vert X^k-X^{*}\Vert }_F/{\Vert X^{*}\Vert }_F$ )。

表1中的结果表明，在大多数情况下，IPSCPRSM在迭代次数和CPU时间方面都比VASALM更快。IPSCPRSM的相对误差也优于VASALM。初看表1中的结果似乎表明，EADMM在迭代次数最少方面优于其他两种方法。然而，EADMM得到的相对误差结果也比其他所有方法的结果更差。事实上，所提出的IPSCPRSM算法在所有测试案例中都获得了最佳的相对误差结果。EADMM在最后阶段的收敛速度可能非常慢。因此，EADMM通常需要许多次迭代才能将相对误差结果提高到与IPSCPRSM方法相当的水平。

Table1. Numerical comparisons of different algorithms for solving the robust PCA

表1. 解决鲁棒主成分分析问题的不同算法的数值比较

					IPSCPRSM				EADMM			VASALM
g	spr		rr		Iter.		Time	Tol	Iter.	Time	Tol	Iter.	Time	Tol
100	0.05		0.05		104		1.8	6.19e−04	147	1.2	6.40e−04	146	1.4	6.34e−04
	0.05		0.10		389		3.4	5.87e−03	505	4.3	6.66e−03	505	4.2	6.65e−03
	0.10		0.05		115		1.0	6.29e−04	149	1.1	6.63e−04	148	1.2	6.58e−04
	0.10		0.10		358		3.4	2.44e−03	477	4.4	3.08e−03	477	4.5	3.07e−03
	0.15		0.05		154		2.0	4.18e−04	170	1.9	5.71e−04	166	1.0	5.65e−04
	0.15		0.10		757		6.6	7.01e−02	790	6.7	7.09e−02	796	6.1	7.08e−02
500		0.05		0.05		57	10.1	1.01e−04	52	9.0	1.01e−04	58	9.7	1.02e−04
		0.05		0.10		60	10.9	1.20e−04	48	8.5	1.98e−04	71	12.4	1.39e−04
		0.10		0.05		81	15.6	1.11e−04	50	9.5	1.99e−04	62	10.9	1.89e−04
		0.10		0.10		86	16.6	1.25e−04	62	10.3	3.66e−04	82	14.7	2.30e−04
		0.15		0.05		79	15.8	1.02e−04	38	6.7	1.82e−04	78	15.0	9.45e−05
		0.15		0.10		104	21.1	1.75e−04	78	13.7	3.27e−04	91	16.7	1.79e−04
1000		0.05		0.05		66	72.8	5.86e−05	46	46.2	8.85e−05	69	71.5	6.55e−05
		0.05		0.10		70	78.8	6.31e−05	48	50.4	1.26e−04	77	79.4	9.55e−05
		0.10		0.05		81	111.2	6.18e−05	50	76.6	1.09e−04	76	119.6	8.25e−05
		0.10		0.10		87	105.2	7.32e−05	59	68.4	1.45e−04	87	134.5	9.64e−05
		0.15		0.05		105	171.1	5.94e−05	45	49.3	9.61e−05	94	107.9	6.63e−05
		0.15		0.10		114	205.1	6.56e−05	63	132.2	1.21e−04	118	190.6	7.81e−05

最后，为了进一步观察所提方法的收敛性，在图1中，我们绘制了恢复的低秩和稀疏成分的相对误差演变曲线、$X^k$ 的秩以及$Y^k$ 的稀疏性随迭代计数器$k$ 的变化情况，其中$g=500,spr\in \left\{0.10,0.15\right\},rr=0.10$ 。VASALM和IPSCPRSM具有全局收敛保证，而EADMM则没有。图1中的结果表明，我们所提出的IPSCPRSM方法能够以更少的迭代次数收敛到期望的最优解，从而比VASALM和EADMM得到更好的解。

Figure 1. Evolution of relative errors of the recovered low-rank and sparse components (the left four subplots), the rank of $X^k$ and sparsity of $Y^k$ (the right four subplots) with respect to the number of iterations

图1. 恢复的低秩和稀疏成分的相对误差演变(左侧四个子图)、$X^k$ 的秩和$Y^k$ 的稀疏性(右侧四个子图)随迭代次数的变化

5. 结论

在本文中，我们考虑了具有线性约束的可分离凸最小化问题，其目标函数是两个以上不含耦合变量的函数之和。为了解决这个问题，我们考虑了一种带有不定邻近项的惯性邻近严格压缩Peaceman-Rachford分裂方法，并且结合惯性项和不定线性化技术，提高了算法的计算效率。此外，我们证明了该方法的全局收敛性和$o\left(1/\sqrt{k}\right)$ 收敛速率。最后，我们将所提出的算法应用于鲁棒主成分分析的求解，并验证了其可行性和有效性。

基金项目

国家级大学生创新创业训练计划项目(编号：202210488007)。