一类变分不等式的惯性黄金比例算法的研究

Research on the Inertial Golden Ratio Algorithm for a Class of Variational Inequalities

摘要: 变分不等式是优化理论中的重要问题，在许多实际问题中都有广泛应用。传统求解变分不等式的方法有：投影外梯度法、镜像梯度法、邻近点算法、交替方向法、黄金比例算法等。黄金比例算法相较于投影梯度算法在每次迭代的过程中减少了一次投影的运算，因而提高了收敛速度。本文旨在研究一类变分不等式的黄金比例算法，在已有的一步惯性算法的基础上提出两步惯性黄金比例算法，并证明了在适当的参数条件下该算法的弱收敛性。最后通过数值实验比较了Malitsky的算法，Yang和Liu的算法，Chinedu和Yekini的算法以及我们所提出的算法在迭代时间和迭代步数上的性能差异，验证了本文所提出算法的优异性。

Abstract: Variational inequality is an important problem in optimization theory. The traditional methods for solving variational inequalities include: extragradient method, mirror gradient method, proximity point algorithm, alternating direction method, golden ratio algorithm, etc. Compared with the projection gradient algorithm, the golden ratio algorithm reduces the operation of one projection in the process of each iteration, so as to improve the convergence speed. The purpose of this thesis is to study a kind of golden ratio algorithm for variational inequality, and to propose a two-step inertial golden ratio algorithm based on the one-step ones. The weak convergence of the algorithm is proved under the appropriate parameter conditions. Finally, numerical experiments are carried out to compare the performance differences of Malitsky’s algorithm, Yang and Liu’s algorithms, Chinedu and Yekini’s algorithms, and the proposed algorithm in terms of iteration time and iteration steps, which verifies the superiority of the proposed algorithm.

1. 引言

变分不等式问题自从20世纪60年代由Stampacchia首次提出以来，已经发展成为了数学规划和非线性分析领域的重要理论基础。变分不等式问题是[1]：设$H$ 是实Hilbert空间，$\langle \cdot ,\cdot \rangle$ 和$\Vert \cdot \Vert$ 分别表示内积和范数。$C$ 是$H$ 的闭凸子集，$F:H\to H$ 是非线性映射。经典的变分不等式是指：寻找$x^{\ast }\in C$ 满足

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

该问题的解集记为$S$ 。

国内外学者对变分不等式问题的研究集中在许多个方面，首先是解的存在性与唯一性，其次是求解算法的探索。在解决变分不等式问题的算法中，其最经典的算法是投影梯度法[2]。此方法的局限性在于要求算子具有强单调性且Lipschitz连续，否则不能保证其收敛性，并且该算法在单调情形下可能振荡，因而Korpel-Evich (1976)提出外推投影梯度算法[3]，该算法仅要求算子单调且Lipschitz连续。传统外推投影梯度算法虽然解决了单调变分不等式的收敛问题，但存在两个关键缺陷，其一是计算成本高，每次迭代需计算两次投影及函数值，其二是固定步长限制。

投影梯度类算法的收敛速度是受限于问题条件数，尤其是在非强单调或者高维问题中表现尤为不佳。黄金比例算法通过引入历史信息加权和最优步长设计，突破经典方法的收敛速率瓶颈。Malitsky [4]提出了具有完全自适应步长的黄金比例算法，该算法在每次迭代仅需要计算一次函数值以及一次投影。此外，

步长是自适应确定的。完全自适应步长的黄金比例算法有遍历性的$O\left(\frac{1}{k}\right)$ 收敛速率和$R$ 线性收敛速率。

之后Yang和Liu [5]提出了对黄金比例算法的修改，将算子推广到伪单调情形。但该算法中要求步长是递减的，Chinedu和Yekini [6]在此算法的基础上提出完全自适应算法：一步向后惯性黄金比例算法。算法的优点是加入惯性项，对算法进行加速。

本文在一步惯性黄金比例算法的基础上提出了两步惯性自适应黄金比例算法，使之更充分应用前面的迭代信息，加快了收敛速度。其方法较Nesterov重球法更一般化，数值实验也验证了算法的优异性。

2. 预备知识

文中，我们使用符号$x_k\rightharpoonup \tilde{v}$ 表示序列$\left\{x_k\right\}$ 弱收敛到$\tilde{v}$ 。

定义2.1 [6]:

1) $L$ -Lipschitz连续，存在$L>0$ ，如果对于任意$\tilde{u},\tilde{v}\in H$ ，使得

$\Vert F\left(\tilde{u}\right)-F\left(\tilde{v}\right)\Vert \le L\Vert \tilde{u}-\tilde{v}\Vert .$

2) 序列弱–强连续，如果对于任意的序列$\left\{u_n\right\}$ 弱收敛于$\tilde{v}$ ，我们有$\left\{F\left(u_n\right)\right\}$ 强收敛于$F\left(\tilde{v}\right)$ 。

3) 序列弱连续，如果对于任意序列$\left\{u_n\right\}$ 弱收敛于$\tilde{v}$ ，我们有$\left\{F\left(u_n\right)\right\}$ 弱收敛于$F\left(\tilde{v}\right)$ 。

定义2.2 [6]:

1) $\rho$ -强单调，存在$\rho >0$ ，如果对于任意$\tilde{u},\tilde{v}\in H$ ，使得

$\langle F\left(\tilde{u}\right)-F\left(\tilde{v}\right),\tilde{u}-\tilde{v}\rangle \ge \rho {\Vert \tilde{u}-\tilde{v}\Vert }^2.$

2) 单调，如果对于任意$\tilde{u},\tilde{v}\in H$

$\langle F\left(\tilde{u}\right)-F\left(\tilde{v}\right),\tilde{u}-\tilde{v}\rangle \ge 0.$

3) 拟单调，对于任意$\tilde{u},\tilde{v}\in H$

$\langle F\left(\tilde{v}\right),\tilde{u}-\tilde{v}\rangle >0\Rightarrow \langle F\left(\tilde{u}\right),\tilde{u}-\tilde{v}\rangle \ge 0.$

引理2.1 (Minty) [6]：设$F:C\to H$ 为连续单调映射，则$x^{\ast }$ 是(1-1)的解当且仅当$x^{\ast }$ 是下列问题的解

$存在x\in C,�足\langle F\left(x^{\ast }\right),x^{\ast }-x\rangle \ge 0,\forall x^{\ast }\in C.$

该问题的解集被指定为$S_D$ ，我们知道$S_D$ 是$C$ 的一个闭的凸子集，根据$C$ 的凸性和映射$F$ 的连续性可得$S_D\subset S$ 。

引理2.2 [6]：以下等式成立：

1) $2\langle \tilde{u},\tilde{v}\rangle ={\Vert \tilde{u}\Vert }^2+{\Vert \tilde{v}\Vert }^2-{\Vert \tilde{u}-\tilde{v}\Vert }^2={\Vert \tilde{u}+\tilde{v}\Vert }^2-{\Vert \tilde{u}\Vert }^2-{\Vert \tilde{v}\Vert }^2,\forall \tilde{u},\tilde{v}\in H$ ；

2) ${\Vert \left(1+\tilde{\alpha }\right)\tilde{u}-\tilde{\alpha }\tilde{v}\Vert }^2=\left(1+\tilde{\alpha }\right){\Vert \tilde{u}\Vert }^2-\tilde{\alpha }{\Vert \tilde{v}\Vert }^2+\tilde{\alpha }\left(1+\tilde{\alpha }\right){\Vert \tilde{u}-\tilde{v}\Vert }^2$ 。

引理2.3 [6]：若$C\subseteq H$ 是一个非空闭凸子集，$\left\{x_k\right\}$ 是$H$ 中的序列，满足：

1) $\forall x\in C$ ，$\underset{k\to \infty }{\lim }\Vert x_k-x\Vert$ 存在；

2) $\left\{x_k\right\}$ 的所有弱聚点都在$C$ 中。

则$\left\{x_k\right\}$ 弱收敛到集合$C$ 中一点。

3. 主要结论

3.1. 算法描述

在一步惯性黄金比例算法的基础上我们提出两步惯性黄金比例算法。

算法3-1：(两步惯性黄金比例算法)

假设参数$\delta \in \left[\left(\sqrt{5}-1\right)/2,1\right)$ 和$\theta \in \left(-1/2,0\right]$ 满足以下条件：

$\delta \left(1+\delta \right)\left(1+\theta \right)\ge 1.$ (3-1)

1. 选择${\lambda }_0,\overline{\lambda }>0,x_{-1},x_0,y_0,y_1,w_0\in C,\delta \in \left[\left(\sqrt{5}-1\right)/2,1\right)$ 和$-1/2<\theta <\eta \le 0$ 。

2. 设${\theta }_0=1,\rho =\delta \left(1+\delta \right)\left(1+\theta \right)$ 和$k=1$ ，求步长

${\lambda }_k=\min \left\{\rho {\lambda }_{k-1},\frac{{\theta }_{k-1}}{4{\lambda }_{k-1}\delta }\frac{{\Vert y_k-y_{k-1}\Vert }^2}{{\Vert F\left(y_k\right)-F\left(y_{k-1}\right)\Vert }^2},\overline{\lambda }\right\}.$ (3-2)

3. 计算

$\{\begin{array}{l}{x}_k=\left(1-\delta \right)y_k+\delta w_{k-1},\\ w_k=x_k+\theta \left(x_k-x_{k-1}\right)+\eta \left(x_{k-1}-x_{k-2}\right),\\ y_{k+1}=P_C\left(w_k-{\lambda }_{k}F\left(y_k\right)\right),\end{array}$ (3-3)

其中${\theta }_k=\frac{{\lambda }_k}{{\lambda }_{k-1}\delta }$ 。

4. 令$k\leftarrow k+1$ ，转到2。

注3.1：

(1) 我们所提出的算法是基于Chinedu和Yekini的一步惯性黄金比例算法所提出的两步惯性黄金比例算法，其中$\delta =1/\varphi$ ，$\varphi =\left(\sqrt{5}+1\right)/2$ 。

(2) 我们的算法中的惯性因子是非正的。这是不同于文献[7] [8]中惯性因子通常为非负的特征。这种负值特性可能源于算法的特质，因此我们的算法可以看作是自适应黄金比例具有向后惯性步长$w_k=x_k+\theta \left(x_k-x_{k-1}\right)+\eta \left(x_{k-1}-x_{k-2}\right)$ 的算法。并且在数值算例4.1中比较了惯性步长$\theta ,\eta <0$ 时在迭代步数和收敛速度的优越性。

(3) 在Yang和Liu [5]提出的算法中，作者所定义的步长是非递增的。因此，它们是限制性的。但我们在公式(3-2)中所给出的步长是不需要非递增的；相反，${\lambda }_k$ 可以大于${\lambda }_{k-1}$ (由于$\delta >\left(\sqrt{5}-1\right)/2$ 和$\theta >1/\delta \left(1+\delta \right)-1$ ，我们有$\rho >1$ )和$\left\{{\lambda }_k\right\}$ 是有界的。

(4) 对于算法3-1当$\eta =0$ 时，其相当于Chinedu和Yekini的一步惯性黄金比例算法；当$\eta =\theta =0$ 时，其相当于Malitsky [4]提出了具有完全自适应步长的黄金比例算法。

我们做出以下假设以确保我们提出的算法的弱收敛。

假设3.1：

(1) $S_D\ne \varnothing$ 。

(2) $F$ 在$C$ 中是局部Lipschitz连续的，意味着$F$ 在$C$ 的任何有界子集中是Lipschitz连续。

(3) 当$\left\{y_k\right\}\subset C$ 和$y_k\rightharpoonup v^{\ast }$ ，我们有$\Vert F\left(v^{\ast }\right)\Vert \le \lim \underset{n\to \infty }{\inf }\Vert F\left(y_k\right)\Vert$ 。

(4) $F$ 是在$H$ 上的拟单调算子。

注3.2：在假设3.1(3)中，我们施加了一个比文献[9]中对序列弱连续性要求更弱的条件。

对于公式(3-2)，我们分两种情况讨论：

情况1：当${\lambda }_k\le \rho {\lambda }_{k-1}$ 时，因此我们有

${\theta }_k\le \rho /\delta$ . (3-4)

情况2：当$\frac{{\theta }_{k-1}}{{\lambda }_{k-1}\delta }=\frac{{\theta }_k{\theta }_{k-1}}{{\lambda }_k}$ ，我们得到

${\lambda }_k^2{\Vert F\left(y_k\right)-F\left(y_{k-1}\right)\Vert }^2\le \frac{{\theta }_k{\theta }_{k-1}}{4}{\Vert y_k-y_{k-1}\Vert }^2.$ (3-5)

应用和文献[4]中的引理2相似的思想，我们可以证明当序列$\left\{y_k\right\}$ 是有界的时，序列$\left\{{\lambda }_k\right\}$ 和$\left\{{\theta }_k\right\}$ 都是有界的，并且远离零。在这一论断下面的引理中得到详细阐述。

引理3.1：若假设3.1(2)成立，则$\left\{{\lambda }_k\right\}$ 和$\left\{{\theta }_k\right\}$ 是远离零且有界的成立条件是$\left\{y_k\right\}$ 是有界的。

证明：对于公式(3-2)，我们得到${\lambda }_k\le \overline{\lambda }$ ，由于$\left\{y_k\right\}$ 是有界的，我们看到假设3.1的(2)存在$L>0$ 使得$\Vert F\left(y_k\right)-F\left(y_{k-1}\right)\Vert \le L\Vert y_k-y_{k-1}\Vert$ 。取一个足够大的$L$ 使得

${\lambda }_j\ge \frac{1}{4L^2{\delta }^2\lambda },j=0,1.$

我们现在假设${\lambda }_j\ge \frac{1}{4L^2{\delta }^2\lambda }$ ，$j=0,1,\cdots ,k-1$ 。则下列两种情况必有其一($\rho >0$ )：

${\lambda }_k=\rho {\lambda }_{k-1}\ge {\lambda }_{k-1}\ge \frac{1}{4L^2{\delta }^2\overline{\lambda }}.$ (3-6)

或者

${\lambda }_k=\frac{1}{4{\delta }^2{\lambda }_{k-2}}\frac{{\Vert y_k-y_{k-1}\Vert }^2}{{\Vert F\left(y_k\right)-F\left(y_{k-1}\right)\Vert }^2}\ge \frac{1}{4L^2{\delta }^2{\lambda }_{k-2}}\ge \frac{1}{4L^2{\delta }^2\overline{\lambda }}.$ (3-7)

由公式(3-6)和公式(3-7)可得：

${\lambda }_k\ge \frac{1}{4L^2{\delta }^2\overline{\lambda }}.$

因此，可以得出结论$\left\{{\theta }_k\right\}$ 是有界远离零的。

3.2. 两步惯性黄金比例算法的弱收敛性

下面证明两步惯性黄金比例算法的弱收敛性。

引理3.2：在满足假设3.1(1)和(2)的情况下，算法产生的序列$\left\{x_k\right\}$ 和$\left\{y_k\right\}$ 是有界的。

证明：对于$y_{k+1}=P_C\left(w_k-{\lambda }_{k}F\left(y_k\right)\right)$ ，有

$\langle y_{k+1}-w_k+{\lambda }_{k}F\left(y_k\right),y-y_{k+1}\rangle \ge 0$ .(3-8)

同理我们有$y_k=P_C\left(w_{k-1}-{\lambda }_{k-1}F\left(y_{k-1}\right)\right)$ 则有

$\langle y_k-w_{k-1}+{\lambda }_{k-1}F\left(y_{k-1}\right),y-y_k\rangle \ge 0$ .(3-9)

在公式(3-8)中，令$y=\overline{x}\in S_D$ ，公式(3-9)中，令$y=y_{k+1}$ ，则有

$\langle y_{k+1}-w_k+{\lambda }_{k}F\left(y_{k-1}\right),\overline{x}-y_{k+1}\rangle \ge 0$ .(3-10)

$\langle y_k-w_{k-1}+{\lambda }_{k-1}F\left(y_{k-1}\right),y_{k+1}-y_k\rangle \ge 0$ .(3-11)

由$x_k=\left(1-\delta \right)y_k+\delta w_{k-1}$ ，我们有

$y_k-x_k=\frac{\delta }{1-\delta }\left(x_k-w_{k-1}\right)=\delta \left(y_k-w_{k-1}\right)$ .(3-12)

将公式(3-12)代入公式(3-11)，我们有

$\langle \frac{1}{\delta }\left(y_k-x_k\right)+{\lambda }_{k-1}F\left(y_{k-1}\right),y_{k+1}-y_k\rangle \ge 0$ .(3-13)

对于公式(3-10)，由于$\delta >0$ ，则有

$\frac{1}{\delta }\langle y_{k+1}-w_k+{\lambda }_{k}F\left(y_k\right),\overline{x}-y_{k+1}\rangle \ge 0$ .(3-14)

再由公式(3-13)，我们有

$\langle \frac{{\theta }_k}{\delta }\left(y_k-x_k\right)+{\theta }_k{\lambda }_{k-1}F\left(y_{k-1}\right),y_{k+1}-y_k\rangle \ge 0$ .(3-15)

将公式(3-14)和公式(3-15)相加，得到

$\begin{array}{l}\frac{1}{\delta }\langle y_{k+1}-w_k,\overline{x}-y_{k+1}\rangle +\frac{{\lambda }_k}{\delta }\langle F\left(y_k\right),\overline{x}-y_{k+1}\rangle +\frac{{\theta }_k}{\delta }\langle y_k-x_k,y_{k+1}-y_k\rangle \\ +{\theta }_k{\lambda }_{k-1}\langle F\left(y_{k-1}\right),y_{k+1}-y_k\rangle \ge 0.\end{array}$

将上式同时乘以$\delta$ ，且由已知条件可知${\theta }_k=\frac{{\lambda }_k}{{\lambda }_{k-1}\delta }\Rightarrow \delta {\theta }_k{\lambda }_{k-1}={\lambda }_k$ ，得

$\begin{array}{l}{\lambda }_k\langle F\left(y_k\right),\overline{x}-y_{k+1}\rangle +{\lambda }_k\langle F\left(y_{k-1}\right),y_{k+1}-y_k\rangle \\ \ge \langle w_k-y_{k+1},\overline{x}-y_{k+1}\rangle +{\theta }_k\langle x_k-y_k,y_{k+1}-y_k\rangle .\end{array}$ (3-16)

我们注意到

$\langle w_k-y_{k+1},\overline{x}-y_{k+1}\rangle =\frac{1}{2}\left[{\Vert w_k-y_{k+1}\Vert }^2+{\Vert y_{k+1}-\overline{x}\Vert }^2-{\Vert w_k-\overline{x}\Vert }^2\right].$ (3-17)

${\theta }_k\langle x_k-y_k,y_{k+1}-y_k\rangle =\frac{{\theta }_k}{2}\left[{\Vert x_k-y_k\Vert }^2+{\Vert y_{k+1}-y_k\Vert }^2-{\Vert x_k-y_{k+1}\Vert }^2\right].$ (3-18)

把公式(3-17)和公式(3-18)代入公式(3-16)，得到

$\begin{array}{c}\frac{1}{2}{\Vert y_{k+1}-\overline{x}\Vert }^2\le \frac{1}{2}{\Vert w_k-\overline{x}\Vert }^2-\frac{1}{2}{\Vert w_k-y_{k+1}\Vert }^2-\frac{{\theta }_k}{2}{\Vert x_k-y_k\Vert }^2-\frac{{\theta }_k}{2}{\Vert y_{k+1}-y_k\Vert }^2\\ +\frac{{\theta }_k}{2}{\Vert x_k-y_{k+1}\Vert }^2+{\lambda }_k\langle F\left(y_k\right)-F\left(y_{k+1}\right),y_k-y_{k+1}\rangle .\end{array}$(3-19)

而

$\begin{array}{c}2{\lambda }_k\langle F\left(y_k\right)-F\left(y_{k+1}\right),y_k-y_{k+1}\rangle \le 2{\lambda }_k\Vert F\left(y_k\right)-F\left(y_{k+1}\right)\Vert \cdot \Vert y_k-y_{k+1}\Vert \\ \le 2{\lambda }_{k}L\Vert y_k-y_{k+1}\Vert \cdot \Vert y_k-y_{k+1}\Vert \\ \le \sqrt{{\theta }_k{\theta }_{k-1}}\Vert y_k-y_{k+1}\Vert \cdot \Vert y_k-y_{k+1}\Vert \\ \le \frac{{\theta }_k}{2}{\Vert y_k-y_{k+1}\Vert }^2+\frac{{\theta }_{k-1}}{2}{\Vert y_k-y_{k+1}\Vert }^2.\end{array}$ (3-20)

将公式(3-20)代入公式(3-19)，我们有

$\begin{array}{c}{\Vert y_{k+1}-\overline{x}\Vert }^2\le {\Vert w_k-\overline{x}\Vert }^2-{\Vert w_k-y_{k+1}\Vert }^2-{\theta }_k[{\Vert x_k-y_k\Vert }^2+{\Vert y_{k+1}-y_k\Vert }^2\\ -{\Vert x_k-y_{k+1}\Vert }^2]+\frac{{\theta }_k}{2}{\Vert y_k-y_{k+1}\Vert }^2+\frac{{\theta }_{k-1}}{2}{\Vert y_k-y_{k+1}\Vert }^2.\end{array}$(3-21)

由$x_k=\left(1-\delta \right)y_k+\delta w_{k-1}$ ，则有

$y_{k+1}=\frac{1}{1-\delta }{x}_{k+1}-\frac{\delta }{1-\delta }{w}_k.$ (3-22)

$\begin{array}{c}{\Vert y_{k+1}-\overline{x}\Vert }^2={\Vert \frac{1}{1-\delta }\left(x_{k+1}-\overline{x}\right)-\frac{\delta }{1-\delta }\left(w_k-\overline{x}\right)\Vert }^2\\ =\frac{1}{1-\delta }{\Vert x_{k+1}-\overline{x}\Vert }^2-\frac{\delta }{1-\delta }{\Vert w_k-\overline{x}\Vert }^2+\frac{\delta }{{\left(1-\delta \right)}^2}{\Vert x_{k+1}-w_k\Vert }^2\\ =\frac{1}{1-\delta }{\Vert x_{k+1}-\overline{x}\Vert }^2-\frac{\delta }{1-\delta }{\Vert w_k-\overline{x}\Vert }^2+\delta {\Vert y_{k+1}-w_k\Vert }^2.\end{array}$ (3-23)

把公式(3-23)代入公式(3-21)中，我们有

$\begin{array}{c}\frac{1}{1-\delta }{\Vert x_{k+1}-\overline{x}\Vert }^2\le \frac{1}{1-\delta }{\Vert w_k-\overline{x}\Vert }^2-\left(1+\delta \right){\Vert y_{k+1}-w_k\Vert }^2+{\theta }_k{\Vert x_k-y_{k+1}\Vert }^2\\ -{\theta }_k{\Vert x_k-y_k\Vert }^2+\frac{{\theta }_{k-1}}{2}{\Vert y_k-y_{k-1}\Vert }^2-\frac{{\theta }_k}{2}{\Vert y_{k+1}-y_k\Vert }^2.\end{array}$(3-24)

由

$\begin{array}{c}{\Vert w_k-\overline{x}\Vert }^2=\left(1+\theta \right){\Vert x_k-\overline{x}\Vert }^2-\left(\theta -\eta \right){\Vert x_{k-1}-\overline{x}\Vert }^2-\eta {\Vert x_{k-2}-\overline{x}\Vert }^2\\ +\left(1+\theta \right)\left(\theta -\eta \right){\Vert x_k-x_{k-1}\Vert }^2+\eta \left(1+\theta \right){\Vert x_k-x_{k-2}\Vert }^2\\ -\eta \left(\theta -\eta \right){\Vert x_{k-1}-x_{k-2}\Vert }^2.\end{array}$(3-25)

$\begin{array}{c}{\Vert y_{k+1}-w_k\Vert }^2={\Vert \left(1+\theta \right)\left(y_{k+1}-x_k\right)-\left(\theta -\eta \right)\left(y_{k+1}-x_{k-1}\right)-\eta \left(y_{k+1}-x_{k-2}\right)\Vert }^2\\ =\left(1+\theta \right){\Vert y_{k+1}-x_k\Vert }^2-\left(\theta -\eta \right){\Vert y_{k+1}-x_{k-1}\Vert }^2\\ -\eta {\Vert y_{k+1}-x_{k-2}\Vert }^2+\left(1+\theta \right)\left(\theta -\eta \right){\Vert x_k-x_{k-1}\Vert }^2\\ +\eta \left(1+\theta \right){\Vert x_k-x_{k-2}\Vert }^2-\eta \left(\theta -\eta \right){\Vert x_{k-1}-x_{k-2}\Vert }^2.\end{array}$ (3-26)

代入公式(3-24)，整理并移项有

$\begin{array}{l}\frac{1}{1-\delta }{\Vert x_{k+1}-\overline{x}\Vert }^2-\frac{\theta }{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{\eta }{1-\delta }{\Vert x_{k-1}-\overline{x}\Vert }^2\\ +\frac{{\theta }_k}{2}{\Vert y_{k+1}-y_k\Vert }^2-\frac{{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }{\Vert x_k-x_{k-1}\Vert }^2\\ \le \frac{1}{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{\theta }{1-\delta }{\Vert x_{k-1}-\overline{x}\Vert }^2-\frac{\eta }{1-\delta }{\Vert x_{k-1}-\overline{x}\Vert }^2\\ +\frac{{\theta }_{k-1}}{2}{\Vert y_{k+1}-y_k\Vert }^2-\frac{{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2\\ +\left[\frac{{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }-\frac{\eta \left(\theta -\eta \right)}{1-\delta }+\left(1+\delta \right)\eta \left(\theta -\eta \right)\right]{\Vert x_{k-1}-x_{k-2}\Vert }^2\\ +\left[\frac{\eta \left(1+\theta \right)}{1-\delta }-\left(1+\delta \right)\eta \left(1+\theta \right)\right]{\Vert x_k-x_{k-2}\Vert }^2\\ +\left[{\theta }_k-\left(1+\delta \right)\left(1+\theta \right)\right]{\Vert x_k-y_{k+1}\Vert }^2+\left(1+\delta \right)\left(\theta -\eta \right){\Vert y_{k+1}-x_{k-1}\Vert }^2\\ +\left(1+\delta \right)\eta {\Vert y_{k+1}-x_{k-2}\Vert }^2-{\theta }_k{\Vert x_k-y_k\Vert }^2.\end{array}$(3-27)

令

$\begin{array}{l}{\Gamma }_k=\frac{1}{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{\theta }{1-\delta }{\Vert x_{k-1}-\overline{x}\Vert }^2-\frac{\eta }{1-\delta }{\Vert x_{k-2}-\overline{x}\Vert }^2\\ +\frac{{\theta }_{k-1}}{2}{\Vert y_k-y_{k-1}\Vert }^2-\frac{{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2.\end{array}$

则上式变为

$\begin{array}{l}{\Gamma }_{k+1}\le {\Gamma }_k+\frac{{\delta }^2\left(\theta -\eta \right)\left(1+\theta -\eta \right)}{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2+\frac{\eta \left(1+\theta \right){\delta }^2}{1-\delta }{\Vert x_k-x_{k-2}\Vert }^2\\ +\left[{\theta }_k-\left(1+\delta \right)\left(1+\theta \right)\right]{\Vert x_k-y_{k+1}\Vert }^2+\left(1+\delta \right)\left(\theta -\eta \right){\Vert y_{k+1}-x_{k-1}\Vert }^2\\ +\left(1+\delta \right)\eta {\Vert y_{k+1}-x_{k-2}\Vert }^2-{\theta }_k{\Vert x_k-y_k\Vert }^2.\end{array}$ (3-28)

下面我们说明${\Gamma }_k\ge 0$ 。注意到

${\Vert x_{k-1}-\overline{x}\Vert }^2\le 2{\Vert x_{k-2}-x_{k-1}\Vert }^2+2{\Vert x_{k-2}-\overline{x}\Vert }^2,$

则

$\begin{array}{c}{\Gamma }_k\ge \frac{1}{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{2\theta }{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2-\frac{2\theta }{1-\delta }{\Vert x_{k-2}-\overline{x}\Vert }^2\\ -\frac{\eta }{1-\delta }{\Vert x_{k-2}-\overline{x}\Vert }^2-\frac{{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2\\ =\frac{1}{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{2\theta +{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2-\frac{2\theta +\eta }{1-\delta }{\Vert x_{k-2}-\overline{x}\Vert }^2.\end{array}$

由算法3-1条件$-1/2<\theta <\eta \le 0$ ，可知$\theta -\eta <0,1+\theta -\eta >0,1+\theta >0,\text{2}\theta +\eta <0$ ，从而有

$\frac{{\delta }^2\left(\theta -\eta \right)\left(1+\theta -\eta \right)}{1-\delta }<0,\frac{\eta \left(1+\theta \right){\delta }^2}{1-\delta }<0,\left(1+\delta \right)\left(\theta -\eta \right)<0,\left(1+\delta \right)\eta <0.$

所以${\Gamma }_k\ge 0$ 。

比较公式(3-28)右侧各项系数，并注意到${\theta }_k\le \left(1+\delta \right)\left(1+\theta \right)$ (公式(3-3) (3-4)所得)${\theta }_k>0$ ，从而有${\Gamma }_{k+1}\le {\Gamma }_k$ 。所以$\left\{{\Gamma }_k\right\}$ 是非增的，且$\left\{{\Gamma }_k\right\}$ 是有界的。

由$\left\{{\Gamma }_k\right\}$ 极限存在，我们可以得到

$\begin{array}{l}\underset{k\to \infty }{\lim }\Vert y_{k+1}-x_k\Vert =0,\underset{k\to \infty }{\lim }\Vert x_{k-1}-x_{k-2}\Vert =0,\underset{k\to \infty }{\lim }\Vert x_k-x_{k-1}\Vert =0,\\ \underset{k\to \infty }{\lim }\Vert w_k-x_k\Vert =0,\underset{k\to \infty }{\lim }\Vert y_{k+1}-w_k\Vert =0,\underset{k\to \infty }{\lim }\Vert y_k-x_k\Vert =0,\\ \underset{k\to \infty }{\lim }\Vert y_{k+1}-y_k\Vert =0.\end{array}$

由上述结论，可知

$\underset{k\to \infty }{\lim }\left[\frac{1}{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{\theta }{1-\delta }{\Vert x_{k-1}-\overline{x}\Vert }^2-\frac{\eta }{1-\delta }{\Vert x_{k-2}-\overline{x}\Vert }^2\right]$

极限存在，因而

$\left\{\frac{1}{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{\theta }{1-\delta }{\Vert x_{k-1}-\overline{x}\Vert }^2-\frac{\eta }{1-\delta }{\Vert x_{k-2}-\overline{x}\Vert }^2\right\}$

是有界的。所以$\left\{x_k\right\}$ 有界，同时$\left\{y_k\right\}$ 也是有界的。

引理3.3：如果$v^{\ast }$ 是$\left\{y_k\right\}$ 的弱聚点，则在假设条件下，我们有$v^{\ast }\in S_D$ 或$F\left(v^{\ast }\right)=0$ 。

证明：由引理3.2可知$\left\{x_k\right\}$ 和$\left\{y_k\right\}$ 都是有界的，如果$v^{\ast }$ 是$\left\{y_k\right\}$ 的弱聚点则它也是$\left\{x_k\right\}$ 的弱聚点，因为，$\Vert x_k-y_k\Vert \to 0$ ，当$k\to \infty$ 时，因此存在$\left\{x_{k_j}\right\}\subset \left\{x_k\right\}$ ，使得$x_{k_j}\rightharpoonup v^{\ast }\in C$ 。

现在检查下面两种情形。

情况1：如果$\lim \underset{j\to \infty }{\sup }\Vert F\left(y_{k_j}\right)\Vert =0,\underset{j\to \infty }{\lim }\Vert F\left(y_{k_j}\right)\Vert =\lim \underset{j\to \infty }{\inf }\Vert F\left(y_{k_j}\right)\Vert =0.$

由假设3.1(3)我们有

$0\le \Vert F\left(v^{\ast }\right)\Vert \le \underset{j\to \infty }{\lim }\inf \Vert F\left(y_k\right)\Vert =0,$

因此我们可以得到$F\left(v^{\ast }\right)=0$ 。

情况2：如果

$\lim \underset{j\to \infty }{\sup }\Vert F\left(y_{k_j}\right)\Vert >0.$

不失一般性，我们选择$\left\{F\left(y_{k_j}\right)\right\}$ 的子列并仍然定义$\left\{F\left(y_{k_j}\right)\right\}$ 使得，

$\underset{j\to \infty }{\lim }\Vert F\left(y_{k_j}\right)\Vert =M_1>0.$

由投影性质对所有$y\in C$ ，有

$\begin{array}{c}0\le \langle y_{k_j}-w_{k_j}+{\lambda }_{kj}F\left(y_{k_j}\right),y-y_{k_{j+1}}\rangle \\ =\langle y_{k_{j+1}}-w_{k_j},y-y_{k_{j+1}}\rangle +{\lambda }_{k_j}\langle F\left(y_{k_j}\right),y_{k_j}-y_{k_{j+1}}\rangle +{\lambda }_{k_j}\langle F\left(y_{k_j},y-y_{k_j}\right)\rangle ,\end{array}$ (3-29)

因为$\underset{k\to \infty }{\lim }\Vert y_{k+1}-w_k\Vert =\underset{k\to \infty }{\lim }\Vert y_{k+1}-y_k\Vert =0$ ，因而有

$0\le \lim \underset{j\to \infty }{\inf }\langle F\left(y_{k_j},y-y_{k_j}\right)\rangle \le \lim \underset{j\to \infty }{\sup }\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle <\infty ,\forall y\in C,$ (3-30)

基于(3-30)我们继续预测情况2的两种情形。

情形(a)对所有的$y\in C$ ，我们假设$\lim \underset{j\to \infty }{\sup }\langle F\left(y_{k_j},y-y_{k_j}\right)\rangle >0$ ，我们选择$\left\{y_{k_{j_l}}\right\}$ ，使得$\underset{j\to \infty }{\lim }\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle >0$ 。因此$\exists l_0\ge 1$ ，使得$\langle F\left(y_{k_{j_l}}\right),y-y_{k_{j_l}}\rangle >0$ ，$\forall l\ge l_0$ ，因为$F$ 是拟单调的。我们有$\langle F\left(y\right),y-y_{k_{j_l}}\rangle \ge 0,\forall y\in C,l\ge l_0$ ，当$l\to \infty$ 我们有$\langle F\left(y\right),y-v^{\ast }\rangle \ge 0,\forall y\in C$ ，即$v^{\ast }\in S_D$ 。

情形(b)对所有的$y\in C$ 。我们假定$\lim \underset{j\to \infty }{\sup }\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle =0$ ，由公式(3-30)我们有

$\underset{j\to \infty }{\lim }\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle =0,\forall y\in C,$ (3-31)

意味着

$\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle +\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}>0,\forall y\in C.$ (3-32)

由于$\underset{j\to \infty }{\lim }\Vert F\left(y_{k_j}\right)\Vert =M_1>0$ ，则$\exists j_0\ge 1$ ，使得$\Vert F\left(y_{k_j}\right)\Vert >\frac{M_1}{2},\forall j\ge j_0$ 。我们令$b_{k_j}=\frac{F\left(y_{k_j}\right)}{{\Vert F\left(y_{k_j}\right)\Vert }^2},\forall j\ge j_0$ ，因而有$\langle F\left(y_{k_j}\right),b_{k_j}\rangle =1,\forall j\ge j_0$ 。

由公式(3-31)有

$\langle F\left(y_{k_j}\right),y+b_{k_j}\left[\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}\right]-y_{k_j}\rangle >0.$

结合上述不等式及$F$ 的拟单调性

$\langle F\left(y+b_{k_j}\left[\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}\right]\right),y+b_{k_j}\left[\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}-y_{k_j}\right]\rangle \ge 0.$

因此有

$\begin{array}{l}\langle F\left(y\right),y+b_{k_j}\left[\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}\right]-y_{k_j}\rangle \\ \ge \langle F\left(y\right)-F\left(y+b_{k_j}\left[\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}\right]\right),y+b_{k_j}\left[\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}\right]-y_{k_j}\rangle \\ \ge \frac{-L}{M_1}\left(\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle +\frac{1}{j+1}\right)\cdot M_2.\end{array}$ (3-33)

这里$M_2>0$ ，由于$\left\{y+b_{k_j}\left[\left|\langle F\left(y_{k_j}\right),y-y_{k_j}\rangle \right|+\frac{1}{j+1}\right]-y_{k_j}\right\}$ 是有界的，由公式(3-30)

$\underset{j\to \infty }{\lim }\left(\left|\langle F\left(y_{k_j}\right),y-y_k\rangle \right||+\frac{1}{j+1}\right)=0.$

由公式(3-33)可知，对所有的$y\in C$ ，有$\langle F\left(y\right),y-v^{\ast }\rangle \ge 0$ ，即$v^{\ast }\in S_D$ 。

定理3.1：在假设3.1成立及$F\left(x\right)\ne 0$ ，对于$\forall x\in C$ 条件下，序列$\left\{x_k\right\},\left\{y_k\right\}$ 弱收敛到变分不等式问题(1-1)的一个解。

证明：令$\left\{y_k\right\}$ 的弱聚点集为${\omega }_w\left(y_k\right)$ ，下面证明${\omega }_w\left(y_k\right)\subset S_D$ 。

令$v^{\ast }\in {\omega }_w\left(y_k\right)$ ，存在一个序列$\left\{y_{k_j}\right\}\subset \left\{y_k\right\}$ ，使得$y_{k_j}\rightharpoonup v^{\ast }$ ，当$j\to \infty$ 时，由$C$ 的弱闭性，则$v^{\ast }\in C$ ，对所有$x\in C$ 。$F\left(x\right)$ 是非零则$F\left(v^{\ast }\right)$ 也是非零的，由引理3.3得$v^{\ast }\in S_D$ ，因此${\omega }_w\left(x_k\right)\subset S_D$ 。

${\Vert x_{k-1}-\overline{x}\Vert }^2={\Vert x_{k-1}-x_k\Vert }^2+{\Vert x_k-\overline{x}\Vert }^2+2\langle x_{k-1}-x_k,x_k-\overline{x}\rangle .$

$\begin{array}{l}{\Vert x_{k-2}-\overline{x}\Vert }^2={\Vert x_{k-2}-x_{k-1}\Vert }^2+{\Vert x_{k-1}-x_k\Vert }^2+2\langle x_{k-2}-x_{k-1},x_{k-1}-x_k\rangle \\ +2\langle x_{k-2}-x_{k-1},x_k-\overline{x}\rangle +2\langle x_{k-1}-x_k,x_k-\overline{x}\rangle .\end{array}$

$\begin{array}{c}{\Gamma }_k=\frac{1}{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{\theta }{1-\delta }\left[{\Vert x_{k-1}-x_k\Vert }^2+2\langle x_{k-1}-x_k,x_k-\overline{x}\rangle \right]-\frac{\theta }{1-\delta }{\Vert x_k-\overline{x}\Vert }^2\\ -\frac{\eta }{1-\delta }[{\Vert x_{k-2}-x_{k-1}\Vert }^2+{\Vert x_{k-1}-x_k\Vert }^2+2\langle x_{k-2}-x_{k-1},x_{k-1}-x_k\rangle +2\langle x_{k-2}-x_{k-1},x_k-\overline{x}\rangle \\ +2\langle x_{k-1}-x_k,x_k-\overline{x}\rangle ]-\frac{\eta }{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-\frac{{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2\\ =\frac{1-\theta -\eta }{1-\delta }{\Vert x_k-\overline{x}\Vert }^2-a_k-b_k-c_k.\end{array}$

其中

$\begin{array}{l}{a}_k=\frac{\theta }{1-\delta }\left[{\Vert x_{k-1}-x_k\Vert }^2+2\langle x_{k-1}-x_k,x_k-\overline{x}\rangle \right],\\ b_k=\frac{\eta }{1-\delta }[{\Vert x_{k-2}-x_{k-1}\Vert }^2+{\Vert x_{k-1}-x_k\Vert }^2+2\langle x_{k-2}-x_{k-1},x_{k-1}-x_k\rangle \\ +2\langle x_{k-2}-x_{k-1},x_k-\overline{x}\rangle +2\langle x_{k-1}-x_k,x_k-\overline{x}\rangle ],\\ c_k=\frac{{\delta }^2\left(1+\theta \right)\left(\theta -\eta \right)}{1-\delta }{\Vert x_{k-1}-x_{k-2}\Vert }^2.\end{array}$

因为$\underset{k\to \infty }{\lim }\Vert x_k-x_{k-1}\Vert =\underset{k\to \infty }{\lim }\Vert x_{k-1}-x_{k-2}\Vert =0$ ，则$a_k\to 0,b_k\to 0,c_k\to 0$ 。且$\frac{1-\theta -\eta }{1-\delta }$ 有界，则$\underset{k\to \infty }{\lim }\Vert x_k-\overline{x}\Vert$ 存在，对所有的$\overline{x}\in S_D$ 。

由引理2.3得$\left\{x_k\right\}\rightharpoonup \overline{x}\in S_D$ ，此外$\Vert x_k-y_k\Vert \to 0$ ，有$\left\{y_k\right\}\rightharpoonup v^{\ast }\in S_D$ ，即证明完毕。

4. 数值实验

4.1. 有限维算例

例4.1设$C=\left[-1,1\right]$ ，定义$F$ 如下：

$F\left(v\right)=\{\begin{array}{l}2v-1,v>1,\\ v^2,v\in \left[-1,1\right],\\ -2v-1,v<-1.\end{array}$ (4-1)

在这种情况下$F$ 是拟单调且Lipschitz连续的，但既不是伪单调也不是单调的，此外，我们有$S_D=\left\{-1\right\}$ 和$S=\left\{-1,0\right\}$ 。

在计算过程中，选取如下参数：

Malitsky的算法：$\varphi =\phi =\left(\sqrt{5}+1\right)/2,{\lambda }_0=2,\overline{\lambda }=2$ 。

Yang和Liu的算法：

$\delta =0.5\left(\left(\sqrt{1+4\left(\alpha /\left(2-\theta \right)+1-\alpha \right)-1}\right)/2\right),\theta =1,\alpha =0.5,\mu =0.5,{\lambda }_1=2$ .

Chinedu和Yekini的算法：$\delta =0.618,\theta =-0.1,{\lambda }_0=2,\overline{\lambda }=2$ 。

算法3-1 (我们的算法)：$\delta =0.618,\theta =-0.2,\eta =-0.15,{\lambda }_0=2,\overline{\lambda }=2$ 。

我们使用停止准则$TO{L}_k:=\max \left\{{\Vert y_{k+1}-x_k\Vert }^2,{\Vert y_k-x_k\Vert }^2\right\}<\epsilon$ 对于所有算法，其中$\epsilon$ 是误差，我们选择$\epsilon ={10}^{-5}$ 。于是我们选择如下的初值$y_0,y_1,x_{-1},x_0,w_0$ ：

情况1：$y_0=0.1,y_1=0.2,x_{-1}=0.05,x_0=0.15,w_0=0.03$ ；

情况2：$y_0=0.2,y_1=0.2,x_{-1}=0.05,x_0=0.2,w_0=0.03$ ；

情况3：$y_0=0.2,y_1=-0.2,x_{-1}=0.05,x_0=0.2,w_0=0.03$ ；

情况4：$y_0=0.1,y_1=0.3,x_{-1}=0.05,x_0=0.25,w_0=0.03$ (见表1)。

Table 1. Comparative analysis results of various algorithms

表1. 各类算法的比较分析结果

Algorithm	Case 1		Case 2		Case 3		Case 4
	CPU	Iter	CPU	Iter	CPU	Iter	CPU	Iter
Malitsky算法	0.0027	63	0.0026	59	0.0027	59	0.0029	60
Yang & Liu算法	0.0034	244	0.0031	244	0.0021	6	0.0036	245
Chinedu & Yekini算法	0.0018	20	0.0014	24	0.0016	24	0.0016	21
算法3-1	0.0016	18	0.0013	22	0.0015	22	0.0014	19

注：CPU表示运行时间(s)，Iter表示迭代次数。

我们也将使用线性图来呈现上述四种情况的收敛速率以及迭代次数，其中横坐标表示迭代次数，纵坐标表示误差。如图1所示，由于算法3-1相较于其他算法采用了更多以前信息，使得在迭代中较好的修正迭代步长，且减少对初始值选取的依赖性。

Figure 1. Showing case 1 (a)，case 2 (b)，case 3 (c)，and case 4 (d)

图1. 分别表示情况1 (a)，情况2 (b)，情况3 (c)，情况4 (d)

4.2. 无限维算例

对任意$0<T\in ℝ$ ，设$L_2\left(\left[0,T\right],{ℝ}^m\right)$ 表示平方可积的Hilbert空间，可测向量函数$z:\left[0,T\right]\to {ℝ}^m$ ，定义：

$\langle z,v\rangle ={\displaystyle {\int }_0^T\langle z\left(t\right),v\left(t\right)\rangle \text{d}t.}$

相应的范数

${\Vert z\Vert }_2=\sqrt{\langle z,z\rangle }={\left({\displaystyle {\int }_0^T{\Vert z\left(t\right)\Vert }^2\text{d}t}\right)}^{\frac{1}{2}}<\infty .$

让我们研究一下最优控制问题

$z^{\ast }\left(t\right)=\arg \min \left\{f\left(z\right):z\in Z\right\}.$ (4-2)

假设存在这样的控制。在这种情况下，$Z$ 表示容许控制的集合：

$Z=\left\{z\left(t\right)\in L_2\left(\left[0,T\right],{ℝ}^m\right):z_i\left(t\right)\in \left[z_i^{-},z_i^{+}\right],i=1,2,3,\cdots ,m\right\}.$

因此，$Z$ 取$m$ 维盒的形状，并且它构成分段连续函数．特别地，控制可以是以分段常数函数为特征的开关式控制。

最终目标可以表示为：

$f\left(z\right)=g\left(w\left(T\right)\right).$

其中，$g$ 是定义在可行集上的可微凸函数．

考虑一种情形，其中轨迹$w\left(t\right)\in L_2\left(\left[0,T\right]\right)$ 满足由微分方程组表示的约束：

$\dot{w}\left(t\right)=D\left(t\right)w\left(t\right)+E\left(t\right)z\left(t\right),w\left(0\right)=w_0,t\in \left[0,T\right].$

其中$D\left(t\right)$ 和$E\left(t\right)$ 是连续矩阵对于每个$t\in \left[0,T\right]$ ，根据庞特里亚金最大值原理，我们可以找到一个函数$p^{\ast }\in L_2\left(\left[0,T\right]\right)$ ，为此解出$\left(w^{\prime },p^{\prime },z^{\prime }\right)$ ，对于几乎每个$t\in \left[0,T\right]$ 的方程组：

$\{\begin{array}{l}{\dot{w}}^{\ast }\left(t\right)=D\left(t\right)w^{\ast }\left(t\right)+E\left(t\right)z^{\ast }\left(t\right),\\ w^{\ast }\left(0\right)=w_{0.}\end{array}$ (4-3)

$\{\begin{array}{l}{\dot{p}}^{\ast }\left(t\right)=-D{\left(t\right)}^{\top }{p}^{\ast }\left(t\right),\\ p^{\ast }\left(T\right)=▽g\left(w\left(T\right)\right).\end{array}$ (4-4)

$0\in E{\left(t\right)}^{\top }{p}^{\ast }\left(t\right)+N_Z\left(z^{\ast }\left(t\right)\right).$ (4-5)

其中$N_Z\left(z\right)$ 表示从$Z$ 到$z$ 的法向圆锥。

对于$Gz\left(t\right):=E{\left(t\right)}^{\top }p\left(t\right)$ 很好地建立了表示目标成本函数的梯度，我们可以将(4-4)转换为下面的VIP：寻找$z\in Z$ ，使得

$\langle Gz,v-z\rangle \ge 0,\forall v\in Z.$ (4-6)

让我们通过选择一个自然数$N$ 来离散连续函数，其网格大小为$h:=T/N$ 。令$z^N:=\left(z_0,z_1,\cdots ,z_{N-1}\right)$ ，表示为它的分段常数扩张，用它的分段线性插值来表示任何离散化状态$w^N:=\left(w_0,w_1,\cdots ,w_N\right)$ ：

$w^N\left(t\right)=w_i+\frac{t-t_i}{h}\left(w_{i+1}-w_i\right)+\frac{t-t_{i-1}}{h}\left(w_i-w_{i-1}\right).$

其中$t\in \left[t_i,t_{i+1}\right),i=0,1,\cdots ,N-1$ 。

使用欧拉方法在每次迭代时求解常微分方程组

$\{\begin{array}{l}{w}_{i+1}^N=w_i^N+h\left[D\left(t_i\right)w_i^N+E\left(t_i\right)z_i^N\right],\\ w\left(0\right)=w_0.\end{array}$ (4-7)

$\{\begin{array}{l}{p}_i^N=p_{i+1}^N+hD{\left(t_i\right)}^{\text{T}}{p}_{i+1}^N,\\ P\left(N\right)=▽g\left(w_N\right).\end{array}$ (4-8)

例4.2谐振子的控制

我们需要最小化$w_2\left(3\pi \right)$ ，并满足动力学方程和约束条件：

动力学方程：

$\{\begin{array}{l}{\dot{w}}_1\left(t\right)=w_2\left(t\right),\\ {\dot{w}}_2\left(t\right)=-w_1\left(t\right)+z\left(t\right),\forall t\in \left[0,3\pi \right],\end{array}$ (4-9)

取初始条件$w\left(0\right)=0$ ，$z\left(t\right)\in \left[-1,1\right]$ 。

我们知道这个问题的精确最优控制是：

$z^{\ast }\left(t\right)=\{\begin{array}{l}1\text{, }如果t\in \left[0,\frac{\pi }{2}\right)\cup \left(\frac{3\pi }{2},\frac{5\pi }{2}\right),\\ -1,如果t\in \left(\frac{\pi }{2},\frac{3\pi }{2}\right)\cup \left(\frac{5\pi }{2},3\pi \right].\end{array}$

如图2所示，算法3-1的在谐振子控制案例中的稳定性十分良好，也从侧面反映出了算法3-1在无限维空间中具有良好的稳定性。

Figure 2. Calculated by Algorithm 3-1, on the left: the blue line represents the random initial control, and the red line represents the optimal control. On the right: shows the optimal trajectory

图2. 由算法3-1计算，在左侧：蓝线代表随机初始控制，而红线代表最优控制．在右侧：显示最佳轨迹

5. 结论

本文提出了一个两步惯性黄金比例算法来解决变分不等式问题。该算法充分应用了前面的迭代信息，达到了较快的收敛速率。数值实验结果也表明，所提出的两步惯性黄金比例算法(算法3-1)在测试中均展现出显著的性能优势。但对算法的强收敛性和遍历意义下序列收敛速率没有讨论。今后可以考虑变分包含问题中，两步惯性邻近点算法的应用，同时也可将该思想推广到向前–向后–向前算法，原始对偶算法等。

基金项目

国家自然科学基金：非光滑双稳定非线性能量阱靶向能量转移全局动力学和优化设计。项目编号：12172376。