一种新的求解拟单调变分不等式的惯性投影算法

A New Inertial Projection Algorithm for Solving Quasimonotone Variational Inequalities

摘要: 2023年，叶和邓[运筹学学报，2023，27(01)：127-137]提出了一种新的求解拟单调变分不等式的压缩投影算法(简称NPCA)。NPCA结合了向前向后分裂算法(简称FBSA)和压缩投影算法(简称PCA)来减少算法的迭代步数。在此基础上，本文提出了惯性的NPCA算法，简称为INPCA，并在与NPCA相同的假设条件下，证明了INPCA的全局收敛性。数值实验结果表明惯性方法能进一步加速NPCA。

Abstract: In 2023, Ye and Deng [Operations Research Transactions, 2023, 27(01): 127-137] introduced a new projection and contraction algorithm (NPCA) for solving quasimonotone variational inequalities. NPCA combines the forward backward splitting algorithm (FBSA) and the projection and contraction algorithm (PCA) to reduce iterations numbers. By incorporating an inertial step, we extend it to the inertial NPCA (INPCA). The global convergence is proven under the original assumptions, and numerical experiments confirm that the inertial step accelerates convergence.

1. 引言

令${ℝ}^n$ 是$n$ 维欧式空间，本文考虑经典的变分不等式问题(Variational Inequality Problem，简称VIP)：找$x^{\text{*}}\in C$ 使得

$\langle F\left(x^{\text{*}}\right),y-x^{\text{*}}\rangle \ge 0,\forall y\in C,$ (1.1)

其中$C$ 是${ℝ}^n$ 中的非空闭凸子集，$F$ 是从$C$ 到${ℝ}^n$ 的一个连续映射，$\langle \cdot ,\cdot \rangle$ 表示${ℝ}^n$ 中的内积。我们用$S$ 来表示VIP的解集。$S_D$ 来表示VIP的对偶变分不等式的解集，即

$S_D:=\left\{x\in C|\langle F\left(y\right),y-x\rangle \ge 0,\forall y\in C\right\}.$

VIP最早由Hartman和Stampacchia [1]在1966年提出，用于研究偏微分方程的解的存在性和唯一性。随后，变分不等式逐渐发展成为解决均衡问题，优化问题和不动点问题的有力工具[2]-[4]。

Goldstein-Levitin-polyak [5] [6]在1964年提出了投影算法，其算法具体结构如下：

$x^{k+1}=P_C\left(x^k-\beta F\left(x^k\right)\right),$

其中$P_C(\cdot )$ 为投影算子，该算法的收敛性需要$F$ 在$C$ 上强单调且Lipschitz连续。为了削弱$F$ 的强单调性，1976年Korpelevich [7]和Khobotov [8]提出了外梯度投影算法(EGA)，其算法具体结构如下：

$y^k=P_C\left(x^k-\beta F\left(x^k\right)\right),x^{k+1}=P_C\left(x^k-\beta F\left(y^k\right)\right).$

EGA的收敛性只需要$F$ 在$C$ 上单调且$L$ -Lipschitz连续。但EGA的每次迭代需要计算两次向$C$ 的投影，这导致当向$C$ 的投影不易实施时，EGA的效率不高。

为了在每次迭代中减少一次向$C$ 的投影，Solodov和Tseng [9]介绍了压缩投影算法(简称PCA，该类算法的进展还可参见He [10]，Ye [11])；Tseng [12]提出了向前向后分裂算法(简称FBSA)，其算法具体结构如下：

$y_n=P_C\left(x_n-\lambda F\left(x_n\right)\right),x_{n+1}=y_n+\lambda \left(F\left(x_n\right)-F\left(y_n\right)\right),$

并在$F$ 伪单调且Lipschitz连续的条件下证明了算法的全局收敛性。

最近，Liu和Yang [13]介绍了一种自适应的FBSA (简称LYA)来求解拟单调变分不等式，其自适应步长为：

${\lambda }_{n+1}=\{\begin{array}{ll}\text{min}\left\{\frac{\mu \Vert x_n-y_n\Vert }{\Vert F\left(x_n\right)-F\left(y_n\right)\Vert },{\lambda }_n+p_n\right\},\hfill & 若F\left(x_n\right)-F\left(y_n\right)\ne 0;\hfill \\ {\lambda }_n+p_n,\hfill & 其他,\hfill \end{array}$

其中$\left\{p_n\right\}$ 是非负实数列，满足${\displaystyle {\sum }_{n=0}^{\infty }{p}_n}<+\infty$ 。

Ye和Deng [14]将FBSA与PCA结合，提出了一种新的求解拟单调变分不等式的压缩投影算法，其下一个迭代点的形式为：

$x^{k+1}=P_{H_k}\left(y^k-{\lambda }_k\left(F\left(x^k\right)-F\left(y^k\right)\right)\right).$

在映射$F$ 在$R^n$ 上连续、拟单调，$S_D\ne \varnothing$ 且$A=\left\{z\in C:F\left(z\right)=0\right\}\backslash S_D$ 是有限集的条件下，证明了算法的全局收敛性。

Polyak [15]提出了惯性方法，利用前一个迭代点来加速凸优化算法。此后，惯性方法也被用来加速非凸优化算法，例如文献[16] [17]。在映射为Lipschitz连续条件下的惯性算法得到了广泛的研究，其中求解伪单调VIP的有[18]-[20]；求解拟单调VIP的有惯性次梯度外梯度法[21]、惯性Tseng方法[22]等。但在映射仅连续条件下的求解拟单调变分不等式的惯性算法比较少。

受文献[12]-[15]的启发，本文提出了一种求解拟单调变分不等式的惯性向前向后分裂算法(INPCA)。在与文献[14]相同的假设条件下，证明了新算法的全局收敛性。数值实验结果表明，与NPCA和LYA相比，在低维实例下INPCA具有较少的迭代次数；在高维实例下，INPCA具有较少的迭代次数、投影次数和CPU耗时。

2. 预备知识

本节中，我们回顾一些基本的定义、性质和一些引理。

${\mathbb{N}}^{\text{*}}$ 表示正整数，$\Vert \cdot \Vert$ 表示${ℝ}^n$ 中的范数，$\text{dist}\left(x,C\right)$ 表示向量$x$ 到集合$C$ 的距离，即

$\text{dist}\left(x,C\right):=\text{inf}\left\{\Vert x-y\Vert :y\in C\right\}.$

$P_C\left(x\right)$ 表示向量$x$ 集合$C$ 的正交投影，即

$P_C\left(x\right):=\text{argmin}\left\{\Vert y-x\Vert :y\in C\right\}.$

从而向量$x$ 到集合$C$ 的距离等于$\Vert x-P_C\left(x\right)\Vert$ 。对$\forall x\in {ℝ}^n$ 及$\lambda >0$ ，令$r\left(x,\lambda \right)$ 为问题(1.1)的自然残差函数，即

$r\left(x,\lambda \right):=x-P_C\left(x-\lambda F\left(x\right)\right).$

定义1 设$C$ 是${ℝ}^n$ 中的集合，映射$F:C\to {ℝ}^n$ ，

(1) 若存在常数$\gamma >0$ ，使得

$\langle F\left(x\right)-F\left(y\right),x-y\rangle \ge \gamma {\Vert x-y\Vert }^2,\forall x,y\in C,$

则称$F$ 在$C$ 上是$\gamma$ -强单调的。

(2) 若

$\langle F\left(x\right)-F\left(y\right),x-y\rangle \ge 0,\forall x,y\in C,$

则称$F$ 在$C$ 上是单调的。

(3) 若

$\langle F\left(x\right),y-x\rangle \ge 0\Rightarrow \langle F\left(y\right),y-x\rangle \ge 0,\forall x,y\in C,$

则称$F$ 在$C$ 上是伪单调的。

(4) 若

$\langle F\left(x\right),y-x\rangle >0\Rightarrow \langle F\left(y\right),y-x\rangle \ge 0,\forall x,y\in C,$

则称$F$ 在$C$ 上是拟单调的。

根据上述定义，自然的有：(1)$\Rightarrow$ (2)$\Rightarrow$ (3)$\Rightarrow$ (4)。

引理1 [23]设$\left\{{\phi }_k\right\},\left\{{\alpha }_k\right\},\left\{{\delta }_k\right\}$ 为非负序列使得

${\phi }_{k+1}\le {\phi }_k+{\alpha }_k\left({\phi }_k-{\phi }_{k-1}\right)+{\delta }_k,{\displaystyle \sum _{k=1}^{+\infty }{\delta }_k}<+\infty ,$

并且存在一个正数$\alpha$ ，使得 $0\le {\alpha }_k\le \alpha <1,\forall k\in {\mathbb{N}}^{\text{*}}$ ，则存在${\phi }^{\text{*}}\in \left[0,+\infty \right)$ 使得

$\underset{k\to +\infty }{\text{lim}}{\phi }_k={\phi }^{\text{*}}.$

引理2 [2] [24]设$C\subset {ℝ}^n$ 是非空闭凸集，则有以下不等式成立。

(1) $\langle P_C\left(x\right)-x,y-P_C\left(x\right)\rangle \ge 0,\forall x\in {ℝ}^n,\forall y\in C$ ；

(2) $\Vert P_C\left(x\right)-P_C\left(y\right)\Vert \le \Vert x-y\Vert ,\forall x,y\in {ℝ}^n$ ；

(3) ${\Vert P_C\left(x\right)-y\Vert }^2\le {\Vert x-y\Vert }^2-{\Vert P_C\left(x\right)-x\Vert }^2,\forall x\in {ℝ}^n,\forall y\in C$ ；

(4) ${\Vert ax+\left(1-a\right)y\Vert }^2=a{\Vert x\Vert }^2+\left(1-a\right){\Vert y\Vert }^2-a\left(1-a\right){\Vert x-y\Vert }^2,\forall a\in ℝ,x,y\in C$ 。

引理3 [25]设$x$ 是${ℝ}^n$ 中任一向量，$H:=\{x\in {ℝ}^n|\langle u,x\rangle \le a\}$ 是一个半空间，则

$P_H\left(x\right)=x-\text{max}\left\{\frac{\langle u,x\rangle -a}{{\Vert u\Vert }^2},0\right\}u$

特别地，当$x\notin H$ 时，可得

$P_H\left(x\right)=x-\frac{\langle u,x\rangle -a}{{\Vert u\Vert }^2}u.$

引理4 [2]若$\lambda >0$ ，则$x^{\text{*}}\in S$ 的充要条件是$\Vert r\left(x^{\text{*}},\lambda \right)\Vert =0$ 。

引理5 [26]对任意的$x\in {ℝ}^n$ 及任意的$0<{\lambda }_1<{\lambda }_2$ ，有

$\Vert r\left(x,{\lambda }_1\right)\Vert \le \Vert r\left(x,{\lambda }_2\right)\Vert ;$

$\frac{\Vert r\left(x,{\lambda }_1\right)\Vert }{{\lambda }_1}\ge \frac{\Vert r\left(x,{\lambda }_2\right)\Vert }{{\lambda }_2}.$

引理6 [18]对任意的$x\in {ℝ}^n$ 及任意的实数$\lambda >0$ ，有

$\text{min}\left(1,\lambda \right)\Vert r\left(x,1\right)\Vert \le \Vert r\left(x,\lambda \right)\Vert \le \text{max}\left(1,\lambda \right)\Vert r\left(x,1\right)\Vert .$

引理7 [27]设$C\subset {ℝ}^n$ 是非空闭凸集，$F$ 是$C$ 上的映射。若下列条件之一成立：

$F$ 在$C$ 上是伪单调的，且$S\ne \varnothing$ ；

$F$ 是$f$ 的梯度，其中$f$ 是包含$C$ 的开集$K$ 上的可微拟凸函数，且在$C$ 上可取得其全局最小值；

$F$ 在$C$ 上是拟单调的，$F\ne 0$ 且$C$ 有界；

$F$ 在$C$ 上是拟单调的，$F$ 在$C$ 上不为零，且存在正数$r$ ，使得对任意$x\in C$ ，当$\Vert x\Vert >r$ 时，存在$y\in C$ 满足$\Vert y\Vert \le r$ 且$\langle F\left(x\right),y-x\rangle \le 0$ ；

$F$ 在$C$ 上是拟单调的，且$S\backslash S_T\ne \varnothing$ ，其中$S_T:=\left\{x\in C:\langle F\left(x\right),y-x\rangle =0,\forall y\in C\right\}$ ；

$F$ 在$C$ 上是拟单调的，$\text{int}\left(C\right)$ 非空，且存在$x^{\text{*}}\in S$ 使得$F\left(x^{\text{*}}\right)\ne 0$ ，

则$S_D$ 非空。

3. 主要内容

在本节中，首先介绍求解拟单调变分不等式的惯性投影算法INPCA，再证明算法的合理性和生成序列的收敛性。

首先介绍INPCA，其具体结构如下：

算法3.1

步骤0 选取初始点$x^0,x^{-1}\in {ℝ}^n$ ，选取参数$0<{\alpha }_l<{\alpha }_u$ ，$\eta ,\theta \in \left(0,1\right)$ 和$\sigma \in \left(0,1\right)$ ，选取正数列$\left\{{\epsilon }_k\right\}$ 满足${\displaystyle {\sum }_{k=1}^{\infty }{\epsilon }_k}<+\infty$ ，设$k=0$ 。

步骤1 计算

${\omega }^k=x^k+{\theta }_k\left(x^k-x^{k-1}\right),$

其中

${\theta }_k:=\{\begin{array}{ll}\text{min}\left\{\frac{{\epsilon }_k}{{\Vert x^k-x^{k-1}\Vert }^2},\theta \right\},\hfill & 若\Vert x^k-x^{k-1}\Vert \ne 0;\hfill \\ \theta ,\hfill & 其他.\hfill \end{array}$ (3.1)

步骤2 (线搜索)选取${\alpha }_k^0\in \left[{\alpha }_l,{\alpha }_u\right]$ ，寻找最小的非负整数$m_k$ 使得

${\alpha }_k^0{\eta }^{m_k}\Vert F\left({\omega }^k\right)-F\left(P_C\left({\omega }^k-{\alpha }_k^0{\eta }^{m_k}F\left({\omega }^k\right)\right)\right)\Vert \le \sigma \Vert {\omega }^k-P_C\left({\omega }^k-{\alpha }_k^0{\eta }^{m_k}F\left({\omega }^k\right)\right)\Vert .$ (3.2)

令${\lambda }_k={\alpha }_k^0{\eta }^{m_k}$ ，$y^k=P_C\left({\omega }^k-{\lambda }_{k}F\left({\omega }^k\right)\right)$ 并转到下一步。

步骤3 计算$r\left({\omega }^k,{\lambda }_k\right)={\omega }^k-y^k$ ，若$r\left({\omega }^k,{\lambda }_k\right)=0$ ，停止(${\omega }^k$ 解)；否则转到下一步。

步骤4 令$H_k=\left\{u\in {ℝ}^n|h_k\left(u\right)\le 0\right\}$ ，其中

$h_k\left(u\right)=\langle {\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right),u-y^k\rangle$ . (3.3)

计算

$x^{k+1}:=P_{H_k}\left(y^k-{\lambda }_k\left(F\left(y^k\right)-F\left({\omega }^k\right)\right)\right).$ (3.4)

步骤5 令$k=k+1$ ，并返回步骤1。

注1. 由引理3可知$\left\{x^{k+1}\right\}$ 具体形式为：

$x^{k+1}=\{\begin{array}{ll}{v}^k,\hfill & 如果v^k\in H_k;\hfill \\ v^k-\frac{\langle u^k,v^k-y^k\rangle }{{\Vert u^k\Vert }^2}{u}^k,\hfill & 其他,\hfill \end{array}$

其中$v^k:=y^k-{\lambda }_k\left(F\left(y^k\right)-F\left({\omega }^k\right)\right)$ ，$u^k:={\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)$ 。

引理8 设$\left\{{\theta }_k\right\}$ 由INPCA所生成的数列，则对$\forall k\in {\mathbb{N}}^{\text{*}}$ 都有：

(1) $0\le {\theta }_k\le \theta <1$ ；

(2) ${\displaystyle \sum _{k=1}^{\infty }{\theta }_k}{\Vert x^k-x^{k-1}\Vert }^2\le {\displaystyle \sum _{k=1}^{\infty }{\epsilon }_k}<+\infty$ ，进而有$\underset{k\to \infty }{\text{lim}}{\theta }_k{\Vert x^k-x^{k-1}\Vert }^2=0$ 。

证明 (1) 由$\theta$ 和${\theta }_k$ 的定义可知结论成立。

(2) 由式(3.1)分类讨论可知: ${\theta }_k{\Vert x^k-x^{k-1}\Vert }^2\le {\epsilon }_k$ 。这结合${\epsilon }_k$ 的定义可知${\displaystyle \sum _{k=1}^{\infty }{\theta }_k}{\Vert x^k-x^{k-1}\Vert }^2\le {\displaystyle \sum _{k=1}^{\infty }{\epsilon }_k}<+\infty$ 成立。

我们为了说明INPCA的合理性，需要说明INPCA中提到的线搜索可以在有限步内停止，并且对于每个$k$ ，都有由(3.3)定义的半空间$H_k$ 是非空闭凸集。下面我们先介绍INPCA中的线搜索可以在有限步内停止。

引理9 若$F$ 在${ℝ}^n$ 上连续，则对任意的$\omega \in {ℝ}^n$ ，$\alpha >0$ 及$\eta \in \left(0,1\right)$ ，存在有限的非负整数$m$ 使得下式成立：

$\alpha {\eta }^m\Vert F\left(\omega \right)-F\left(P_C\left(\omega -\alpha {\eta }^{m}F\left(\omega \right)\right)\right)\Vert \le \sigma \Vert \omega -P_C\left(\omega -\alpha {\eta }^{m}F\left(\omega \right)\right)\Vert .$ (3.5)

证明：因为线搜索(3.5)与文献[28]中的线搜索一致，故由文献[28]的引理10知结论成立。

接着，我们用下面的引理来说明(3.3)中由$h_k(\cdot )$ 定义的半空间$H_k$ 非空，从而由(3.4)可以生成点$x^{k+1}$ 。

引理10 若$F$ 在${ℝ}^n$ 上连续且$S_D\ne \varnothing$ ，$\left\{x^k\right\}$ ，$\left\{y^k\right\}$ ，$\left\{{\omega }^k\right\}$ 和$\left\{{\lambda }_k\right\}$ 是由INPCA所生成的无穷序列，$h_k(\cdot )$ 是由(3.3)所定义的函数，则对任意的$k$ 都有

(1) $h_k\left(x^{\text{*}}\right)\le 0,\forall x^{\text{*}}\in S_D$ ；

(2) $h_k\left({\omega }^k\right)\ge \left(1-\sigma \right){\Vert r\left({\omega }^k,{\lambda }_k\right)\Vert }^2>0$ 。

进而对任意的$k$ 有$\varnothing \ne S_D\subset H_k$  及${\omega }^k\notin H_k$ 。

证明：(1) 设$x^{\text{*}}\in S_D$ ，由$h_k(\cdot )$ 的定义可得

$\begin{array}{c}{h}_k\left(x^{\text{*}}\right)=\langle {\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right),x^{\text{*}}-y^k\rangle \\ =\langle {\omega }^k-y^k-{\lambda }_{k}F\left({\omega }^k\right),x^{\text{*}}-y^k\rangle +{\lambda }_k\langle F\left(y^k\right),x^{\text{*}}-y^k\rangle \\ \le \langle {\omega }^k-y^k-{\lambda }_{k}F\left({\omega }^k\right),x^{\text{*}}-y^k\rangle \le 0,\end{array}$

其中第一个不等式由$x^{\text{*}}\in S_D$ 且$y^k\in C$ 可得，最后一个不等式由引理2 (1)，$y^k$ 的定义以及$x^{\text{*}}\in C$ 可得。这证明了(1)。

(2) 由$h_k(\cdot )$ 的定义可知

$\begin{array}{c}{h}_k\left({\omega }^k\right)=\langle {\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right),{\omega }^k-y^k\rangle \\ ={\Vert {\omega }^k-y^k\Vert }^2-{\lambda }_k\langle F\left({\omega }^k\right)-F\left(y^k\right),{\omega }^k-y^k\rangle \\ \ge {\Vert r\left({\omega }^k,{\lambda }_k\right)\Vert }^2-{\lambda }_k\Vert F\left({\omega }^k\right)-F\left(y^k\right)\Vert \Vert {\omega }^k-y^k\Vert \\ \ge {\Vert r\left({\omega }^k,{\lambda }_k\right)\Vert }^2-\sigma {\Vert r\left({\omega }^k,{\lambda }_k\right)\Vert }^2\\ =\left(1-\sigma \right){\Vert r\left({\omega }^k,{\lambda }_k\right)\Vert }^2>0,\end{array}$

其中第一个不等式由Cauchy-Schwartz不等式可得，第二个不等式由(3.2)式可得，最后一个不等式由$\Vert r\left({\omega }^k,{\lambda }_k\right)\Vert >0$ 和$\sigma \in \left(0,1\right)$ 可得。这完成了(2)的证明。

最后，我们对INPCA的收敛性进行分析。

引理11 若$F$ 在${ℝ}^n$ 上连续且$S_D\ne \varnothing$ ，$\left\{x^k\right\}$ ，$\left\{y^k\right\}$ ，$\left\{{\omega }^k\right\}$ 和$\left\{{\lambda }_k\right\}$ 是由INPCA所生成的无穷序列，则对任意的$x^{\text{*}}\in S_D$ ，有

(1) ${\Vert x^{k+1}-x^{\text{*}}\Vert }^2\le {\Vert {\omega }^k-x^{\text{*}}\Vert }^2-\left(1-{\sigma }^2\right){\Vert {\omega }^k-y^k\Vert }^2$ 成立；

(2) ${\lim }_{k\to \infty }\Vert x^k-x^{*}\Vert$ 存在，且$\underset{k\to \infty }{\text{lim}}\Vert {\omega }^k-x^k\Vert =\underset{k\to \infty }{\text{lim}}\Vert {\omega }^k-y^k\Vert =\underset{k\to \infty }{\text{lim}}\Vert y^k-x^k\Vert =0$ ，进而有$\left\{x^k\right\}$ ，$\left\{y^k\right\}$ ，$\left\{{\omega }^k\right\}$ ，$\left\{F\left(x^k\right)\right\}$ 及$\left\{F\left({\omega }^k\right)\right\}$ 均有界。

证明 (1) 由引理10 (2)知：$\varnothing \ne S_D\subset H_k$ ，任取$x^{\text{*}}\in S_D$ ，有

$\begin{array}{c}{\Vert x^{k+1}-x^{\text{*}}\Vert }^2={\Vert P_{H_k}\left(y^k-{\lambda }_k\left(F\left(y^k\right)-F\left({\omega }^k\right)\right)\right)-P_{H_k}\left(x^{\text{*}}\right)\Vert }^2\\ \le {\Vert y^k-x^{\text{*}}-{\lambda }_k\left(F\left(y^k\right)-F\left({\omega }^k\right)\right)\Vert }^2\\ ={\Vert {\omega }^k-x^{\text{*}}-\left({\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\right)\Vert }^2\\ ={\Vert {\omega }^k-x^{\text{*}}\Vert }^2-2\langle {\omega }^k-x^{\text{*}},{\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle \\ +{\Vert {\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\Vert }^2,\end{array}$ (3.6)

其中第一个不等式由引理2(2)可得。

另一方面，我们有

$\begin{array}{l}\langle {\omega }^k-x^{\text{*}},{\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle \\ =\langle {\omega }^k-y^k,{\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle +\langle y^k-x^{\text{*}},{\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle \\ \ge \langle {\omega }^k-y^k,{\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle ,\end{array}$

其中不等式由$x^{\text{*}}\in H_k$ 及$H_k$ 的定义可得。这结合(3.6)可知

$\begin{array}{c}{\Vert x^{k+1}-x^{*}\Vert }^2\le {\Vert {\omega }^k-x^{*}\Vert }^2-2\langle {\omega }^k-y^k,{\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle \\ +{\Vert {\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\Vert }^2\\ ={\Vert {\omega }^k-x^{*}\Vert }^2-2\langle {\omega }^k-y^k,{\omega }^k-y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle +{\Vert {\omega }^k-y^k\Vert }^2\\ -2\langle {\omega }^k-y^k,{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle +{\Vert {\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\Vert }^2\\ ={\Vert {\omega }^k-x^{*}\Vert }^2-{\Vert {\omega }^k-y^k\Vert }^2+{\Vert {\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\Vert }^2\\ \le {\Vert {\omega }^k-x^{*}\Vert }^2-{\Vert {\omega }^k-y^k\Vert }^2+{\sigma }^2{\Vert {\omega }^k-y^k\Vert }^2\\ ={\Vert {\omega }^k-x^{*}\Vert }^2-\left(1-{\sigma }^2\right){\Vert {\omega }^k-y^k\Vert }^2,\end{array}$

其中第二个不等式由(3.2)可得。这就完成了(1)的证明。

(2)由(1)，$\sigma \in \left(0,1\right)$ ，${\omega }^k$ 的定义和引理2 (4)可知

$\begin{array}{c}{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\le {\Vert {\omega }^k-x^{\text{*}}\Vert }^2={\Vert \left(1+{\theta }_k\right)\left(x^k-x^{\text{*}}\right)-{\theta }_k\left(x^{k-1}-x^{\text{*}}\right)\Vert }^2\\ =\left(1+{\theta }_k\right){\Vert x^k-x^{\text{*}}\Vert }^2-{\theta }_k{\Vert x^{k-1}-x^{\text{*}}\Vert }^2+\left(1+{\theta }_k\right){\theta }_k{\Vert x^k-x^{k-1}\Vert }^2\\ \le {\Vert x^k-x^{\text{*}}\Vert }^2+{\theta }_k\left({\Vert x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k-1}-x^{\text{*}}\Vert }^2\right)+\left(1+\theta \right){\theta }_k{\Vert x^k-x^{k-1}\Vert }^2,\end{array}$

其中第二个不等式由$0\le {\theta }_k\le \theta$ 可得。由此，令

${\phi }_k={\Vert x^k-x^{\text{*}}\Vert }^2$ ，${\alpha }_k={\theta }_k$ ，${\delta }_k=\left(1+\theta \right){\theta }_k{\Vert x^k-x^{k-1}\Vert }^2$ ，

则由引理8 (2)及引理1可知$\underset{k\to \infty }{\text{lim}}{\phi }_k$ 存在，即$\left\{�x^k-x^{\text{*}}�\right\}$ 收敛。进而知$\left\{x^k\right\}$ 有界。

结合${\omega }^k$ 的定义及引理8可知

$0\le {\Vert {\omega }^k-x^k\Vert }^2={\theta }_k^2{\Vert x^k-x^{k-1}\Vert }^2\le \theta {\theta }_k{\Vert x^k-x^{k-1}\Vert }^2\le \theta {\epsilon }_k\to 0,k\to 0.$ (3.7)

另一方面，由(1)还可得

$\begin{array}{c}0\le \left(1-{\sigma }^2\right){\Vert {\omega }^k-y^k\Vert }^2\le {\Vert {\omega }^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\\ ={\Vert {\omega }^k-x^k+x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\\ ={\Vert {\omega }^k-x^k\Vert }^2+2\langle {\omega }^k-x^k,x^k-x^{\text{*}}\rangle +{\Vert x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\\ \le {\Vert {\omega }^k-x^k\Vert }^2+2\Vert {\omega }^k-x^k\Vert \Vert x^k-x^{\text{*}}\Vert +{\Vert x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2,\end{array}$

其中最后一个不等式由Cauchy-Schwartz不等式可得。对上式取极限，结合(3.7)，$\left\{x^k\right\}$ 的有界性，$0<\sigma <1$ ，$\underset{k\to \infty }{\text{lim}}\left({\Vert x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\right)=0$ 可知：

$\underset{k\to \infty }{\text{lim}}\Vert {\omega }^k-y^k\Vert =\underset{k\to \infty }{\text{lim}}\Vert r\left({\omega }^k,{\lambda }_k\right)\Vert =0.$ (3.8)

这结合(3.7)可得

$\underset{k\to \infty }{\text{lim}}\Vert x^k-y^k\Vert =0.$

由$\left\{x^k\right\}$ 的有界性，(3.7)以及(3.8)可知$\left\{{\omega }^k\right\}$ ，$\left\{y^k\right\}$ 也均有界。这结合$F(\cdot )$ 的连续性还可得$\left\{F\left(x^k\right)\right\}$ ，$\left\{F\left({\omega }^k\right)\right\}$ 和$\left\{F\left(y^k\right)\right\}$ 也均有界。这完成了(2)的证明。

引理12 若$F$ 在${ℝ}^n$ 上连续且$S_D\ne \varnothing$ ，$\left\{x^k\right\}$ ，$\left\{y^k\right\}$ ，$\left\{{\omega }^k\right\}$ 和$\left\{{\lambda }_k\right\}$ 是由INPCA所生成的无穷序列，则有

$\underset{k\to \infty }{\text{lim}}\Vert x^{k+1}-x^k\Vert =0.$ (3.9)

证明：由三角不等式可知

$\Vert x^{k+1}-x^k\Vert \le \Vert x^{k+1}-y^k+{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\Vert +\Vert x^k-y^k+{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\Vert ,$ (3.10)

另一方面，由(3.2)和引理11(2)可知

$\begin{array}{c}\Vert x^k-y^k+{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\Vert \le \Vert x^k-y^k\Vert +{\lambda }_k\Vert F\left({\omega }^k\right)-F\left(y^k\right)\Vert \\ \le \Vert x^k-y^k\Vert +\sigma \Vert {\omega }^k-y^k\Vert \to 0,k\to \infty .\end{array}$ (3.11)

另一方面，对$x^{\text{*}}\in S_D$ ，由$x^{k+1}$ 的定义及引理2(3)可得

$\begin{array}{l}{\Vert x^{k+1}-\left(y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\right)\Vert }^2\le {\Vert y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)-x^{*}\Vert }^2-{\Vert x^{k+1}-x^{*}\Vert }^2\\ ={\Vert y^k-x^{*}\Vert }^2-2\langle y^k-x^{*},{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\rangle +{\lambda }_k^2{\Vert F\left({\omega }^k\right)-F\left(y^k\right)\Vert }^2-{\Vert x^{k+1}-x^{*}\Vert }^2\\ \le {\Vert y^k-x^{*}\Vert }^2+2{\lambda }_k\Vert y^k-x^{*}\Vert \Vert F\left({\omega }^k\right)-F\left(y^k\right)\Vert +{\lambda }_k^2{\Vert F\left({\omega }^k\right)-F\left(y^k\right)\Vert }^2-{\Vert x^{k+1}-x^{*}\Vert }^2\\ \le {\Vert y^k-x^{*}\Vert }^2+2\sigma \Vert y^k-x^{*}\Vert \Vert {\omega }^k-y^k\Vert +{\sigma }^2{\Vert {\omega }^k-y^k\Vert }^2-{\Vert x^{k+1}-x^{*}\Vert }^2,\end{array}$ (3.12)

最后一个不等式由${\lambda }_k\Vert F\left({\omega }^k\right)-F\left(y^k\right)\Vert \le \sigma \Vert {\omega }^k-y^k\Vert$ 可得(参见(3.2))。

此外，还有

$\begin{array}{c}{\Vert y^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2={\Vert y^k-x^k+x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\\ ={\Vert y^k-x^k\Vert }^2+{\Vert x^k-x^{\text{*}}\Vert }^2+2\langle y^k-x^k,x^k-x^{\text{*}}\rangle -{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\\ \le {\Vert y^k-x^k\Vert }^2+2\Vert y^k-x^k\Vert \Vert x^k-x^{\text{*}}\Vert +{\Vert x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2.\end{array}$

将此式代入(3.12)可得

$\begin{array}{c}{\Vert x^{k+1}-\left(y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\right)\Vert }^2\le 2\sigma \Vert y^k-x^{\text{*}}\Vert \Vert {\omega }^k-y^k\Vert +{\sigma }^2{\Vert {\omega }^k-y^k\Vert }^2+{\Vert y^k-x^k\Vert }^2\\ +2\Vert y^k-x^k\Vert \Vert x^k-x^{\text{*}}\Vert +{\Vert x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2.\end{array}$

令$k\to \infty$ ，结合引理11(2)以及$\underset{k\to \infty }{\text{lim}}\left({\Vert x^k-x^{\text{*}}\Vert }^2-{\Vert x^{k+1}-x^{\text{*}}\Vert }^2\right)=0$ 可得

${\Vert x^{k+1}-\left(y^k-{\lambda }_k\left(F\left({\omega }^k\right)-F\left(y^k\right)\right)\right)\Vert }^2\to 0,k\to \infty .$

这结合(3.10)和(3.11)可知(3.9)成立。

定理1 若$F$ 在${ℝ}^n$ 上连续，拟单调且$S_D\ne \varnothing$ ，$\left\{x^k\right\}$ ，$\left\{y^k\right\}$ ，$\left\{{\omega }^k\right\}$ 和$\left\{{\lambda }^k\right\}$ 是由INPCA所生成的无穷序列，则对$\left\{x^k\right\}$ 的任意聚点$\overline{x}$ 都有$\overline{x}\in S$ 。并且还满足$F\left(\overline{x}\right)=0$ 或者$\overline{x}\in S_D$ 。

证明：设$\overline{x}$ 为$\left\{x^k\right\}$ 的聚点。则存在子列$\left\{x^{k_i}\right\}$ 满足

$\underset{i\to \infty }{\text{lim}}{x}^{k_i}=\overline{x}.$

这结合引理11(2)可得

$\underset{i\to \infty }{\text{lim}}{y}^{k_i}=\overline{x},\underset{i\to \infty }{\text{lim}}{\omega }^{k_i}=\overline{x}.$ (3.13)

从而由$\left\{y^{k_i}\right\}\subset C$ 及$C$ 是闭集可知$\overline{x}\in C$ 。利用(3.13)以及文献[14]中的定理1 (将$x^{k_i}$ 替换为${\omega }^{k_i}$ )可知结论成立。

定理2 若$F$ 在${ℝ}^n$ 上连续，拟单调且$S_D\ne \varnothing$ 且满足$\left\{z\in C:F\left(z\right)=0\right\}\backslash S_D$ 为有限集。设$\left\{x^k\right\}$ 是INPCA生成的无穷序列，则$\left\{x^k\right\}$ 收敛到$S$ 中的一点。

证明：设$X$ 为$\left\{x^k\right\}$ 的所有聚点构成的集合，则由定理1可知$X\subset S$ 。我们按以下情况进行分类讨论。

情况一 若存在$\tilde{x}\in X$ 使得$\tilde{x}\in S_D$ 。此时，由引理11(2)可知$\underset{k\to \infty }{\text{lim}}\Vert x^k-\tilde{x}\Vert$存在。这结合$\tilde{x}$ 为序列$\left\{x^k\right\}$ 的聚点可知

$\underset{k\to \infty }{\text{lim}}\Vert x^k-\tilde{x}\Vert =0,$

即$\left\{x^k\right\}$ 收敛到$S$ 中一点。

情况二 若对任意的$\tilde{x}\in X$ 都有$\tilde{x}\notin S_D$ ，则由定理1可知$F\left(\tilde{x}\right)=0$ 且$\tilde{x}\notin S_D$ 。因此，我们有$X\subset \left\{z\in C:F\left(z\right)=0\right\}\backslash S_D$ 。这结合题设可知$X$ 为有限集。因此，文献[13]中的引理3.5成立。进而，结合式(3.9)中

$\underset{k\to \infty }{\text{lim}}\Vert x^{k+1}-x^k\Vert =0,$

以及文献[13]中的定理3.1可知$\left\{x^k\right\}$ 收敛到$S$ 中一点。

综上，定理2成立。

4. 数值实验

在本节中，我们用数值实验来验证INPCA的有效性。我们将Ye和Deng [14]中的算法1称为NPCA，将Liu和Yang [13]的算法3.1称为LYA。所有实验均在Intel(R) Core(TM) Ultra 5 125H 3.60 GHz和内存为32.00GB的笔记本电脑上使用MATLAB R2023b进行。

INPCA的参数设置为：$\sigma =0.99$ ，$\eta =0.5$ ，$\theta =0.5$ ，${\alpha }_0^0=1$ ，以及对$k\ge 1$ 取

${\alpha }_k^0=\{\begin{array}{ll}{P}_{\left[{10}^{-10},{10}^{10}\right]}\left(\frac{{\Vert {\omega }^k-{\omega }^{k-1}\Vert }^2}{\langle {\omega }^k-{\omega }^{k-1},F\left({\omega }^k\right)-F\left({\omega }^{k-1}\right)\rangle }\right),\hfill & 若\langle {\omega }^k-{\omega }^{k-1},F\left({\omega }^k\right)-F\left({\omega }^{k-1}\right)\rangle >{10}^{-4};\hfill \\ P_{\left[{10}^{-10},{10}^{10}\right]}\left(1.6{\lambda }_{k-1}\right),\hfill & 其他情�.\hfill \end{array}$

其中${\alpha }_k^0$ 的选择是对Ye [29]中的参数调整所得。NPCA与LYA的参数选取分别与文献[14]和[13]中一致，即NPCA为$\alpha =10$ ，$\sigma =0.99$ ，$\eta =0.5$ ；LYA为$\mu =0.5$ ，$p_n=\frac{100}{{\left(n+1\right)}^{1.1}}$ ，${\lambda }_0=1$ 。

例1 此例被Ye和He [27]及Ye和Deng [14]测试。令$C=\left\{x\in {ℝ}^n:x_i\ge 0,i=1,\cdots ,n,{\displaystyle \sum }_{i=1}^n{x}_i=a,a>0\right\}$ ，且$F\left(x\right)={\left(F_1\left(x\right),\cdots ,F_n\left(x\right)\right)}^{\text{T}}$ ，其中

$F_i\left(x\right)=\frac{h{x}_i{\displaystyle \sum _{i=1}^n{x}_i}-\frac{1}{2}h{\displaystyle \sum _{i=1}^n{x}_i^2}-1}{{\left({\displaystyle \sum _{i=1}^n{x}_i}\right)}^2},\forall i,$

$h$ 在$\left(0.1,1.6\right)$ 内随机生成，则$S=S_D=\left\{\left(\frac{a}{n},\cdots ,\frac{a}{n}\right)\right\}$ 。此例的停止准则如下:

$\text{dist}\le {10}^{-4},$

其中dist表示当前迭代点到解集的距离。对于例1，我们首先在$n=5$ 时测试此算例，在表1中给出了初始点$x^0$ ，$a$ ，迭代次数iter，投影次数np，CPU时间(单位：秒)；当$n\ge 100$ 时，初始点$x^0$ 按文献[14]中的方式生成，即

$z=\text{rand}\left(n,1\right),bb=\text{sum}\left(z\right),x^0=\frac{az}{bb}\in C.$

在表2中给出$n$ ，iter，np和CPU情形($a=n$ )，其结果为10次实验的平均值。

Table 1. Numerical experimental results of example 1 when $n=5$

表1. 例1在$n=5$ 时的数值实验结果

$x^0$	a		iter				np				CPU
			INPCA		NPCA	LYA	INPCA		NPCA	LYA	INPCA		NPCA		LYA
(0, 0, 0, 0, 5)	5		18		29	41	56		99	42	0.02328		0.04841		0.02845
(0, 0, 5, 0, 0)	5		18		29	41	56		99	42	0.02356		0.03950		0.02452
(0, 2, 0, 2, 1)		5		15	26	36	43	84	37	0.01897		0.03312		0.01985
(1, 1, 1, 1, 6)		10		23	28	39	68	59	40	0.02824		0.02484		0.02837
(5, 0, 0, 0, 5)		10		21	37	40	63	78	41	0.02356		0.02397		0.02354

Table 2. Numerical experimental results of example 1 when $n\ge 100$

表2. 例1在$n\ge 100$ 的数值实验结果

n	iter			np			CPU
	INPCA	NPCA	LYA	INPCA	NPCA	LYA	INPCA	NPCA	LYA
100	23	121	42	65	243	43	0.05039	0.10313	0.03740
200	26	254	57	73	510	58	0.10220	0.53385	0.13586
500	28	671	93	79	1343	94	0.76908	9.86117	1.56018
1000	29	1388	147	80	2778	148	4.12551	103.61323	12.92367

例2 此例被Sun [30]和Malitsky [31]用于算法测试。令$C={ℝ}_{+}^n$ ，$F\left(x\right):=F_1\left(x\right)+F_2\left(x\right)$ ，其中$F_1\left(x\right):=\left(f_1\left(x\right),f_2\left(x\right),\cdots ,f_n\left(x\right)\right)$ ，$f_i\left(x\right)=x_{i-1}^2+x_i^2+x_{i-1}{x}_i+x_i{x}_{i+1},\forall i$ 且$x^0=x^{n+1}=0$ ；$F_2\left(x\right):=Ex+c$ ，$c=\left(-1,-1,\cdots ,-1\right)$ ，$E\in {ℝ}^{n\times n}$ 的元素$e_{i,j}$ 满足

$e_{i,j}:=\{\begin{array}{ll}4,\hfill & i=j,\hfill \\ 1,\hfill & i-j=1,\hfill \\ -2,\hfill & i-j=-1,\hfill \\ 0,\hfill & 其他情�.\hfill \end{array}$

此例的停止准则为：

$\Vert r\left(m^k,{\lambda }_k\right)\Vert \le {10}^{-4}.$

其中，在NPCA和LYA中，$m^k=x^k$ ，在INPCA中，$m^k={\omega }^k$ 。我们在表3中给出$n$ ，iter，np和CPU，结果为10个随机初始点的平均值。

Table 3. Numerical experimental results of example 2

表3. 例2的数值实验结果

n	iter			np			CPU
	INPCA	NPCA	LYA	INPCA	NPCA	LYA	INPCA	NPCA	LYA
1000	22	31	204	66	266	205	0.00954	0.02860	0.04241
3000	22	33	235	68	288	236	0.08062	0.32705	0.54946
5000	23	34	259	71	297	260	0.33722	1.34843	2.37148

注3 由表1~3可知，在低维算例中，INPCA的迭代次数比NPCA、LYA少，投影次数和CPU耗时与NPCA、LYA基本相当。在高维算例中，INPCA的迭代次数，投影次数和CPU耗时均少于NPCA、LYA。

致 谢

衷心感谢我的导师叶明露教授。从读文献都生涩，到完成论文；从选题迷茫到终稿落定，每一步都离不开他的悉心指引。他治学严谨、眼中有光，这份态度与热忱，深深影响了我，并将成为我前行路上长久的光亮。

基金项目

国家自然科学基金面上项目(No. 11871059)，西华师范大学培育项目(No. 20A024)。

NOTES

^*通讯作者。