1. 引言
设
是实Hilbert空间,
和
分别表示
中的内积与范数。关于变分不等式问题:求
满足
(1)
其中
为映射,可行集
是
中的非空闭凸子集。记问题(1)的解集为
。变分不等式理论来源于处理力学模拟的偏微分方程。自成立以来,由于该理论在经济学、信号处理、图像处理、优化和优化控制问题等方面的广泛应用,它已成为非线性分析的一个重要领域,详见参考文献[1]-[5]。在过去的几十年里,人们对开发有效和鲁棒的数值方法来解决变分不等式问题非常感兴趣,特别是对基于投影的方法及其变体非常感兴趣[6]-[11]。
Korpelevich [12]提出了外梯度方法,即在每次迭代中需要对可行集进行两次投影计算。而次梯度外梯度方法[13]和Tseng的外梯度方法[14]只需要在可行集上进行一次投影。然而,当可行集结构复杂或投影难以计算时,计算在一个非空闭凸集上的投影并不容易。因此,这两种方法在实际应用中大大提高了算法的计算性能。
另一方面,不动点问题与变分不等式密切相关。即求
,使得
,则称点
为
的不动点。记
为
不动点解集。本文主要是求解变分不等式问题和不动点问题的一般解。近年来,许多学者研究并提出了许多有效的迭代方法来求解变分不等式问题和不动点问题的公共解,例如,见文献[14]-[18]。最近,Kraikaew和Saejung [19]提出了一种寻找单调变分不等式和不动点问题的公共解的算法(SEGM),其算法的结构是:
其中
代表
在
上的度量投影,
为单调L-Lipschitz连续映射,步长
的常数,
是拟扩张映射。适当的条件下,证明了该算法迭代序列
的强收敛性。然而,该算法需要知道Lipschitz常数,从而限制一些相关算法的使用。为了克服这一困难,人们提出了大量的算法,通过一定的自适应标准来更新步长,例如,参见[20]-[22]。最近,Thong和Hieu [23]等提出如下算法(ISEGM):
其中
的映射,
,
。步长
将在每次迭代中自动更新,通过选择满足
的最大
。算法ISEGM在映射是单调且L-Lipschitz连续时,生成的序列
弱收敛于
,该算法利用线搜索过程选取步长,无需计算Lipschitz常数。最近,Tan和Fan [18]等提出如下算法(MTEA):
其中
的映射,步长
自动更新满足
算法MTEA在映射F是单调且L-Lipschitz连续时,生成的序列
强收敛于
。通过以上结构得到了的步长有
。
当问题(1)的可行集为
时,其中
是一个凸函数。He和Wu [24]提出了一种新算法,其算法的结构如下:
(2)
其中步长
由以下线搜索得到,即
,在适当的假设下,得到了算法生成的序列
弱收敛于问题(1)的一个解。可以看到,该算法不再直接计算可行集上的投影,而是以函数次梯度信息构造超平面,从而替代可行集上的投影。
近年来,许多研究者采用了快速迭代算法,如次梯度算法、惯性加速算法和Mann迭代算法等。在文献[18] [24]的基础上,本文提出了非单调步长的惯性外梯度次梯度投影算法,算法在不预先知道映射的利普希茨常数的情况下运行,每次迭代中使用一个新的非单调步长,从而实现了算法的简便性。同时证明了该算法在Hilbert空间中的弱收敛性。数值实验表明,相较于文献[18] [24]中的算法,本文提出的算法更为有效。
2. 预备知识
在本文中,总是假设
表示一个希尔伯特空间,
表示
的非空凸闭子集。序列
强收敛与弱收敛分别记为
、
。记变分不等式问题与不等点问题的解集分别为
、
。其公共解集为
。本文假设问题(1)的可行集具有下列结构:
(3)
其中
是一个凸函数。
处的法锥
定义为
。对任意的
和
为实数,以下几种基本的不等式成立:
1)
;
2)
。
目前已知,投影
具有以下基本性质:
3)
;
4)
。
定义2.1 设
为凸函数。若
在
处次可微的,那么
定义2.2 函数
在
处称为Gateaux可微的,若存在
满足
其中
称为
在
处的Gateaux微分。称
在
上是Gateaux可微的,如果任意
,则
在
上是Gateaux可微的。
定义2.3 对任意的
、
数,映射
为
1) 单调映射,则有
2) L-Lipschitz是连续的,若
且
3) 拟非扩张映射,如果
4) η-半压缩映射
,若
(4)
或者等价于
(5)
或者等价于
(6)
定义2.4 若
且
,序列
,若
有
则称
在
处是弱下半连续的。若
在
都是弱下半连续,则称
在
上是弱下半连续的。
定义2.5 设
是
上的集值映射,若
是极大单调算子的充要条件为:
1)
是单调算子,满足
;
2) 任意单调算子的图像不包含
的图像
。
定义2.6 设
是一个非线性算子且
,若对任意的序列
有以下关系成立:
则称
在0点处是半闭的。
基于以上的定义,下面的引理对于证明本文主要结果的收敛性是至关重要的。
引理2.1 [25]若
,对任意
且
,则有
引理2.2 [26]假设解集
非空且,
是由式(3)定义,则
当且仅当以下条件中的一个成立:
1)
;
2)
且存在一个正常数
满足
。
引理2.3 [27]设
是Lipschitz连续单调算子,定义
则
是极大单调算子。
当且仅当
。
引理2.4 [28]假设
是
数列满足:
且对
存在实数
使得
,则下列结论成立:
1)
,其中
;
2) 存在
使得
。
引理2.5 [29] (Opail)假设
是非空闭子集,若序列
满足:
1) 对于
存在;
2) 序列
任意弱聚点属于
中。
则
弱收敛于
中的一个点。
3. 非单调步长梯度外梯度算法
在本节中,提出了一种惯次梯度外梯度方法来解决变分不等式问题和不动点问题,并分析了它们的收敛性。特别地,增加了一个惯性项和一个新的非单调步长,使算法具有更快的收敛速度,并且不需要事先知道Lipschitz常数的先验信息。首先,假设提出的算法1满足随后的一个条件:
(C1) 映射
是单调L-Lipschitz连续的;
(C2) 映射
是η-半压缩映射且
在0点是半闭的;
(C3) 解集非空,即
;
(C4) 可行集
,其中
是一个连续的可微凸函数,且
是
-Lipschitz 连续的,其系数
。存在
使得
,其中
表示
的边界;
(C5) 假设
是非负序列且满足
。记
,且
(
见下文)成立。假设正序列
满足
。假设非负序列
满足
。
本文算法结构如下:
算法1
初始化:设任意
与参数
,设
。
步骤1:设
,计算
其中
。
步骤2:计算
其中
。
步骤3:计算
并且步长
更新如下:
(7)
如果
停止,否则,进入步骤4。
步骤4:令
返回步骤1。
注1:在算法1中:1)
。对任意的
,由次梯度的定义有
。因此,
,从而有
。2)
。事实上,假设存在
,则有
与
矛盾。因此
。
3.1. 收敛性分析
引理3.1 若假设条件(C1)成立。则由式(7)生成的序列
是良性的,并且
以及
,其中
。
证明:因为映射
单调
-Lipschitz连续的,即有
因此,
,由
的定义有
。所以,由式(7)定义的序列
是有界的并且有
。记
与
。通过
的定义,可得
,因此
收敛。下面验证
的收敛性。假设
,因为
对上式取
,则有
,这与假设矛盾。因此,有
与
成立。
注2:值得注意的是,随着迭代次数的增加,算法1中生成的步长
可以增加。因此,使用这种类型的步长减少了对初始步长
的依赖。
定理3.1 如果算法1中
成立,则有
。
证明 因为
,于是
,从而
。由
的定义可得
因此
。
下面证明
,由
可得
因此有
又根据注1可知
,且
,故有
所以
。因为
,则有
,因此
,即
,所以
。
引理3.2 假设(C1)~(C5)成立。令
是由算法1生成的序列,对任意
有下列不等式成立:
(8)
证明:因为
,由投影基本性质及
的定义有
(9)
于是有
(10)
因为
,所以
。另外,因为
单调映射,则有
,于是将此项目添加到(10)的右侧
(11)
注意到
(12)
下面估计
。因为有
,
(13)
所以有
(14)
结合式(11)、(12)与(14)有
(15)
若
,引理2.2有
,
成立,从而
。因为
为凸函数,于是
。
因此有
(16)
由
的定义与
可得
另外,由次微分定义有
通过以上两个不等式有
(17)
从而由假设(C4)与式(16)、(17)可知
由引理2.2与假设(C4)有,则上式可为
(18)
记
。因为假设(C5)成立,即
,结合式(15)、(18)与引理3.1有
(19)
如果
,由式(15)知
综上引理3.2成立。
定理3.2 若假设条件(C1)~(C6)成立。则算法1生成的序列
弱收敛于
。
证明 通过引理3.2可知
,即存在
使得
,因此由引理3.2可得
(20)
接下来,将证明分成四个部分。
情形1. 序列
是有界的。通过式(4)与(6)以及
可知
(21)
因此,由
与式(20)有
(22)
通过
的定义有
(23)
另外有不等式
(24)
结合式(22)、(23)和(24)整理可得
(25)
从而由式(25)可得
(26)
令
,从而有
(27)
由假设(C5)
,于是
,即有
(28)
其中
。从而序列
是非增的,于是有
(29)
通过式(29)可知
(30)
因为
定义可知
(31)
整理式(30)与(31)得
结合上述不等式与式(28)有
(32)
因此有
(33)
所以
,由此可知
。
因为
有界,通过式(25)有
(34)
由引理2.5与式(33)知
存在,因此
存在,进而序列
是有界。
情形2. 序列存在且
。
由情形1的过程知
,通过
的定义
(35)
由式(35)知当
时,
。又因
存在,所以取
。由式(23)有
(36)
另外取
时,由式(22)结合式(36)有
(37)
对式(8)取
时有
,因此有
(38)
通过式(19)可得
即
时,结合式(37)、(38)以及假设(C5)推出
(39)
当
时,由引理3.1与式(21)有
(40)
情形3. 序列
的弱聚点属于
。因为
有界以及情形1知
,并且由
的定义有
(41)
此外,情形2结论,得出
,因此
(42)
由情形1知
是有界的序列,假设存在子列
使得
。即有,
通过式(41)可以得到
。同理由式(42)有
,结合
,所以
。
情形4. 序列
弱收敛于
。因为情形3与式(39)知
,则有
。由半空间
定义与
可得
因为
有界,所以由式(41)可得
是有界,并且由于
是Lipschitz连续的,从而知存在
满足
。因此由以上不等式可得
(43)
由假设(C4)知
弱下半连续。结合式(43)、
和
,由定义2.4有
因此由
的定义知
。
下面证明
,令
其中
。由引理2.3知
是极大单调算子,则对任意
,通过定义2.5有
等价于
由法锥
的定义及
可得
整理可得
(44)
通过
的定义有
因为
,因此
(45)
结合式(44)与(45)可得
由内积的性质有
由
的单调性知
(46)
因此有
(47)
由情形3过程有
,
,从而有
(48)
因为
是Lipschitz连续,并且
,
,于是有
(49)
又因
,所以
(50)
通过式(48)-(50),当
时,由式(47)可得
因为
为极大单调算子,所以
,从而
。设序列
存在子序列
和
使得
,
。任意给定
,由情形1知
存在,结合引理2.1有
从而有
不成立,故与假设矛盾,所以
,因此
弱收敛于
。综合情形3与情形4有序列
弱收敛于
。
3.2. 数值结果
在本节研究中,我们利用例子3.1展示了算法3.1的计算机验证结果,并且在不同的拟非扩张映射下对其进行了测试,与文献[18]和[24]中的算法进行了比较。数值实验表明,引入惯性项和适当的拟非扩张映射能显著减少算法3.1的计算时间。所有实验均在一台装有AMD Ryzen7 4700U处理器和2.0 GB内存的笔记本电脑上,使用Matlab 2021 b进行。运行时间以CPU秒为单位表示,迭代步骤则用iter表示。
例3.1 定义
,
,其中
为
矩阵,
,
初始点:
。取拟非扩张映射分别为
,集合
是非空闭凸集,
在
上单调且Lipschiz连续在本文的算法中,选取符合条件的如下参数:
。算法3.1与文献[18]算法(3)和[24]算法(4)的比较结果如表1所示。
Table 1. The numerical result for example 3.1
表1. 例3.1数值结果
|
|
算法4 [24] |
算法3 [18] |
算法3.1 |
iter |
CPU |
iter |
CPU |
iter |
CPU |
5 |
|
20 |
0.034 |
21 |
0.035 |
19 |
0.027 |
|
28 |
0.041 |
25 |
0.036 |
25 |
0.038 |
|
32 |
0.048 |
31 |
0.046 |
30 |
0.044 |
50 |
|
45 |
0.076 |
22 |
0.039 |
30 |
0.041 |
|
58 |
0.089 |
29 |
0.043 |
39 |
0.045 |
|
71 |
0.109 |
35 |
0.058 |
48 |
0.055 |
500 |
|
77 |
1.223 |
22 |
0.641 |
40 |
0.618 |
|
99 |
1.778 |
29 |
0.841 |
51 |
0.808 |
|
122 |
1.958 |
35 |
0.984 |
62 |
0.966 |
由数值实验可见,本文算法相较于文献[18] [24]有一定的优越性,收敛效果更好。比如在维度为500的时候,本文算法相比于文献[18]中的算法,找到解的时间明显更快。对于精度,在同一维度与精度下,本文算法仍具有一定的优越性。
4. 结论
本文提出了一种新算法,用于在可行集为凸函数时求解变分不等式与不动点问题的公共解。该算法利用拟非扩张映射和惯性加速技术,已证明具有弱收敛性。本文采用线搜索程序来更新算法的步长,无须事先知道Lipschitz系数,并根据类Mann迭代生成新的迭代点。最后,通过数值实验验证了新算法的有效性。
基金项目
资助项目1:KYZK2024027:变分不等式与不动点问题非单调步长的惯性投影算法。
资助项目2:KYZK2024010:图像处理中的张量离散不适定问题及其高性能迭代算法研究。
资助项目3:KYZK2024003:变分不等式与不动点问题在NASH群体博弈的应用研究。
NOTES
*通讯作者。