变分不等式与不动点问题的非单调步长惯性投影算法
Projection Algorithms with Line Search Process for Variational Inequality and Fixed Point Problems
摘要: 文章针对实Hilbert空间中的单调变分不等式和不动点连续映射的凸可行性问题,提出了一种非单调步长算法来求解。该算法利用可行集的信息构造特殊半空间,以及结合外梯度方法构造半空间。每次向两个半空间作投影。同时结合惯性加速技巧与Mann迭代方法,在一定条件下,建立了所提算法的弱收敛性定理。最后,我们进行了一些计算测试,以证明所提算法的效率和优点,并与现有算法进行了比较。
Abstract: This paper presents a new inertial subgradient extragradient algorithm designed to solve variational inequalities and fixed point problems in real Hilbert spaces. Integrating the Mann iteration method with the subgradient extragradient approach and employing inertial acceleration techniques, the algorithm constructs a half-space using subgradient information and projects onto it. Step lengths are determined via a line search procedure, eliminating the need to compute the Lipschitz constant of the mapping. The algorithm’s weak convergence is established under assumptions like the pseudo-nonexpansiveness of the mappings. Finally, Numerical experiments additionally illustrate the algorithm’s advantages over existing approaches in the literature.
文章引用:杨志, 王仕伟, 冷震北, 匡艳. 变分不等式与不动点问题的非单调步长惯性投影算法[J]. 应用数学进展, 2025, 14(2): 228-243. https://doi.org/10.12677/aam.2025.142066

1. 引言

H 是实Hilbert空间, , 分别表示 H 中的内积与范数。关于变分不等式问题:求 u C 满足

F ( u ) , y u 0, y C , (1)

其中 F : H H 为映射,可行集 C H 中的非空闭凸子集。记问题(1)的解集为 V I ( F , C ) 。变分不等式理论来源于处理力学模拟的偏微分方程。自成立以来,由于该理论在经济学、信号处理、图像处理、优化和优化控制问题等方面的广泛应用,它已成为非线性分析的一个重要领域,详见参考文献[1]-[5]。在过去的几十年里,人们对开发有效和鲁棒的数值方法来解决变分不等式问题非常感兴趣,特别是对基于投影的方法及其变体非常感兴趣[6]-[11]

Korpelevich [12]提出了外梯度方法,即在每次迭代中需要对可行集进行两次投影计算。而次梯度外梯度方法[13]和Tseng的外梯度方法[14]只需要在可行集上进行一次投影。然而,当可行集结构复杂或投影难以计算时,计算在一个非空闭凸集上的投影并不容易。因此,这两种方法在实际应用中大大提高了算法的计算性能。

另一方面,不动点问题与变分不等式密切相关。即求 x H ,使得 T ( x ) = x ,则称点 x T 的不动点。记 F i x ( T ) T 不动点解集。本文主要是求解变分不等式问题和不动点问题的一般解。近年来,许多学者研究并提出了许多有效的迭代方法来求解变分不等式问题和不动点问题的公共解,例如,见文献[14]-[18]。最近,Kraikaew和Saejung [19]提出了一种寻找单调变分不等式和不动点问题的公共解的算法(SEGM),其算法的结构是:

{ y n = P C ( x n τ F ( x n ) ) , z n = θ n x 0 + ( 1 θ n ) P T n ( x n τ F ( y n ) ) , T n : = { x H : x n τ F ( x n ) y n , x y n 0 } , x n + 1 = γ n x n + ( 1 γ n ) T ( z n ) ,

其中 P C 代表 H C 上的度量投影, F : H H 为单调L-Lipschitz连续映射,步长 τ ( 0 , 1 L ) 的常数, T : H H 是拟扩张映射。适当的条件下,证明了该算法迭代序列 { x n } 的强收敛性。然而,该算法需要知道Lipschitz常数,从而限制一些相关算法的使用。为了克服这一困难,人们提出了大量的算法,通过一定的自适应标准来更新步长,例如,参见[20]-[22]。最近,Thong和Hieu [23]等提出如下算法(ISEGM):

{ y n = P C ( s n τ n F ( s n ) ) , z n = P T n ( s n τ n F ( y n ) ) , x n + 1 = ( 1 γ n ) ( s n ) + γ n T ( z n ) ,

其中 T , F : H H 的映射, s n = x n + α n ( x n x n 1 ) T n : = { x H : x n τ n F ( s n ) y n , x y n 0 } 。步长 τ n   将在每次迭代中自动更新,通过选择满足 τ F ( s n ) F ( y n ) μ s n y n 的最大 τ { ρ , ρ l , ρ l 2 , } 。算法ISEGM在映射是单调且L-Lipschitz连续时,生成的序列 { x n } 弱收敛于 F i x ( T ) V I ( F , C ) ,该算法利用线搜索过程选取步长,无需计算Lipschitz常数。最近,Tan和Fan [18]等提出如下算法(MTEA):

{ s n = x n + δ n ( x n x n 1 ) , y n = P C ( s n τ n F ( s n ) ) , z n = P T n ( s n τ n F ( y n ) ) , T n : = { x H : x n τ n F ( s n ) y n , x y n 0 } , x n + 1 = ( 1 γ n ) ( λ n z n ) + γ n T ( z n ) ,

其中 T , F : H H 的映射,步长 τ n 自动更新满足

τ n + 1 = { min { θ s n y n F ( s n ) F ( y n ) , τ n + ζ n } , F ( s n ) F ( y n ) τ n + ζ n                                         , 

算法MTEA在映射F是单调且L-Lipschitz连续时,生成的序列 { x n } 强收敛于 F i x ( T ) V I ( F , C ) 。通过以上结构得到了的步长有 lim n τ n = τ

当问题(1)的可行集为 C = { x H : c ( x ) 0 } 时,其中 c : H R 是一个凸函数。He和Wu [24]提出了一种新算法,其算法的结构如下:

{ y n = P C n ( x n τ n F ( x n ) ) , C n : = { x H : c ( x n ) + c ( x n ) , x x n 0 } , x n + 1 = P T n ( x n τ n F ( y n ) ) , T n : = { x H : x n τ n F ( x n ) y n , x y n 0 } , (2)

其中步长 λ n 由以下线搜索得到,即 λ n = σ ρ m n , σ > 0 , ρ ( 0 , 1 ) ,在适当的假设下,得到了算法生成的序列 { x n } 弱收敛于问题(1)的一个解。可以看到,该算法不再直接计算可行集上的投影,而是以函数次梯度信息构造超平面,从而替代可行集上的投影。

近年来,许多研究者采用了快速迭代算法,如次梯度算法、惯性加速算法和Mann迭代算法等。在文献[18] [24]的基础上,本文提出了非单调步长的惯性外梯度次梯度投影算法,算法在不预先知道映射的利普希茨常数的情况下运行,每次迭代中使用一个新的非单调步长,从而实现了算法的简便性。同时证明了该算法在Hilbert空间中的弱收敛性。数值实验表明,相较于文献[18] [24]中的算法,本文提出的算法更为有效。

2. 预备知识

在本文中,总是假设 H 表示一个希尔伯特空间, C 表示 H 的非空凸闭子集。序列 { x n } 强收敛与弱收敛分别记为 x n x x n x 。记变分不等式问题与不等点问题的解集分别为 V I ( F , C ) F i x ( T ) 。其公共解集为 F i x ( T ) V I ( F , C ) 。本文假设问题(1)的可行集具有下列结构:

C = { x H : c ( x ) 0 } , (3)

其中 c : H R 是一个凸函数。 x C 处的法锥 N C ( x ) 定义为 N C ( x ) : = { ς H : ς , z x , z C } 。对任意的 x , y H α 为实数,以下几种基本的不等式成立:

1) x + y 2 x 2 + 2 y , x + y

2) α x + ( 1 α ) y 2 = α x 2 + ( 1 α ) y 2 α ( 1 α ) x y 2

目前已知,投影 P C 具有以下基本性质:

3) x P C ( x ) , y P C ( x ) 0 y C

4) P C ( x ) P C ( y ) 2 P C ( x ) P C ( y ) , x y y H

定义2.1 F : H R 为凸函数。若 F x H 处次可微的,那么

F ( x ) = { ξ H : F ( y ) F ( x ) + ξ , x y , y H }

定义2.2 函数 F : H R x H 处称为Gateaux可微的,若存在 F ( x ) H 满足

lim x 0 F ( x + t μ ) F ( x ) t = μ , F ( x ) , μ H ,

其中 F ( x ) 称为 F x 处的Gateaux微分。称 F H 上是Gateaux可微的,如果任意 x H ,则 F x 上是Gateaux可微的。

定义2.3 对任意的 x , y H z F i x ( F ) 数,映射 F : H H

1) 单调映射,则有

F ( x ) F ( x ) , x y 0

2) L-Lipschitz是连续的,若 L > 0

F ( x ) F ( y ) L x y

3) 拟非扩张映射,如果

F ( x ) z x z

4) η-半压缩映射 η [ 0 , 1 ) ,若

F ( x ) z 2 x z 2 + η ( I F ) x 2 (4)

或者等价于

F ( x ) x , x z η 1 2 F ( x ) x 2 (5)

或者等价于

F ( x ) z , x z x z 2 + η 1 2 F ( x ) x 2 (6)

定义2.4 f : H ( , + ] x H ,序列 { x n } H ,若 x n x

f ( x ) lim inf x f ( x n )

则称 f x 处是弱下半连续的。若 f x H 都是弱下半连续,则称 f H 上是弱下半连续的。

定义2.5 G : H 2 H H 上的集值映射,若 G 是极大单调算子的充要条件为:

1) G 是单调算子,满足 υ v , x y 0 ,   υ G ( x ) , v G ( y )

2) 任意单调算子的图像不包含 G 的图像 g r a G : = { ( x , υ ) H × H : υ G ( x ) }

定义2.6 T : H H 是一个非线性算子且 F i x ( T ) ,若对任意的序列 { x n } H 有以下关系成立:

x n x ( I T ) x n 0 x F i x ( T )

则称 I T 在0点处是半闭的。

基于以上的定义,下面的引理对于证明本文主要结果的收敛性是至关重要的。

引理2.1 [25] x H ,对任意 { x n } H x n x ,则有

lim inf x x n x < lim inf x x n y , x y

引理2.2 [26]假设解集 V I ( F , C ) 非空且, C 是由式(3)定义,则 u V I ( F , C ) 当且仅当以下条件中的一个成立:

1) F ( u ) = 0

2) u C 且存在一个正常数 λ 满足 F ( u ) = λ c ( u )

引理2.3 [27] F : H H 是Lipschitz连续单调算子,定义

G ( x ) : = { F ( x ) + N C ( x ) , x C ; ,    x C .

G 是极大单调算子。 0 G ( x ) 当且仅当 x S O L ( F , C )

引理2.4 [28]假设 { a n } , { b n } , { d n } [ 0 , + ) 数列满足:

a n + 1 d n ( a n a n 1 ) + b n , n 1 , n = 1 b n < +

且对 n 1 存在实数 d 使得 0 d n d < 1 ,则下列结论成立:

1) n = 1 [ a n a n 1 ] + < + ,其中 [ m ] + : = max { m , 0 }

2) 存在 a * [ 0 , + ) 使得 lim n a n = a *

2.5 [29] (Opail)假设 C H 是非空闭子集,若序列 { x n } H 满足:

1) 对于 x C , lim x x n x 存在;

2) 序列 { x n } 任意弱聚点属于 C 中。

{ x n } 弱收敛于 C 中的一个点。

3. 非单调步长梯度外梯度算法

在本节中,提出了一种惯次梯度外梯度方法来解决变分不等式问题和不动点问题,并分析了它们的收敛性。特别地,增加了一个惯性项和一个新的非单调步长,使算法具有更快的收敛速度,并且不需要事先知道Lipschitz常数的先验信息。首先,假设提出的算法1满足随后的一个条件:

(C1) 映射 F : H H 是单调L-Lipschitz连续的;

(C2) 映射 T : H H η-半压缩映射且 ( I T ) 在0点是半闭的;

(C3) 解集非空,即 F i x ( T ) V I ( F , C )

(C4) 可行集 C = { x H : c ( x ) 0 } ,其中 c : H R 是一个连续的可微凸函数,且 c ( x ) L 1 -Lipschitz 连续的,其系数 L 1 > 0 。存在 L 2 > 0 使得 F ( x ) L 2 c ( x ) , x C ,其中 C 表示 C 的边界;

(C5) 假设 { ζ n } 是非负序列且满足 n = 1 ζ n < + 。记 lim n τ n = τ ,且 Q < 1 θ 2 τ ( Q 见下文)成立。假设正序列 { γ n } 满足 γ n ( a , b ) ( 0 , ( 1 η ) ( 1 α n ) ) ,   a > 0 , b > 0 。假设非负序列 { δ n } 满足 0 δ n δ < 1 3

本文算法结构如下:

算法1

初始化:设任意 x 0 , x 1 H 与参数 τ 1 > 0 , θ ( 0 , 1 ) , δ n [ 0 , 1 3 ) ,设 n = 1

步骤1:设 s n = x n + δ n ( x n x n 1 ) ,计算

y n = P C n ( s n τ n F ( s n ) ) ,

其中 C n = { x H : c ( s n ) + c ( s n ) , x s n 0 }

步骤2:计算

z n = P T n ( s n τ n F ( y n ) ) ,

其中 T n = { x H : s n τ n F ( s n ) y n , x y n 0 }

步骤3:计算 x n + 1 = ( 1 γ n ) z n + γ n T ( z n ) 并且步长 τ n + 1 更新如下:

τ n + 1 = { min { θ s n y n F ( s n ) F ( y n ) , τ n + ζ n } ,     F ( s n ) F ( y n ) τ n + ζ n                                          ,       (7)

如果 s n = y n = x n + 1 = z n 停止,否则,进入步骤4。

步骤4:令 n : = n +1 返回步骤1。

注1:在算法1中:1) C C n , n 1 。对任意的 x C ,由次梯度的定义有 c ( s n ) + c ( s n ) , x s n c ( x ) 0 。因此, x C n ,从而有 C C n 。2) C T n , n 1 。事实上,假设存在 z C n \ T n ,则有 S n τ n F ( s n ) y n , z y n > 0 y n = P C n ( s n τ n F ( s n ) ) 矛盾。因此 C n T n

3.1. 收敛性分析

引理3.1 若假设条件(C1)成立。则由式(7)生成的序列 { τ n } 是良性的,并且 lim n τ n = τ 以及 τ [ min { θ L , τ 1 } , τ 1 + ϕ ] ,其中 ϕ = n = 1 ζ n

证明:因为映射 F 单调 L -Lipschitz连续的,即有

θ s n y n F ( s n ) F ( y n ) θ s n y n L s n y n = θ L ,   F ( s n ) F ( y n )

因此, τ n min { θ L , τ 1 } ,由 τ n + 1 的定义有 τ n + 1 τ 1 + ϕ 。所以,由式(7)定义的序列 { τ n } 是有界的并且有 τ n [ min { θ L , τ 1 } , τ 1 + ϕ ] 。记 ( τ n + 1 τ n ) + : = max { 0 , τ n + 1 τ n } ( τ n + 1 τ n ) : = max { 0 , ( τ n + 1 τ n ) } 。通过 { τ n } 的定义,可得 n = 1 ( τ n + 1 τ n ) + n = 1 ζ n < + ,因此 n = 1 ( τ n + 1 τ n ) + 收敛。下面验证 n = 1 ( τ n + 1 τ n ) 的收敛性。假设 n = 1 ( τ n + 1 τ n ) = + ,因为

τ k + 1 τ 1 = n = 1 k ( τ n + 1 τ n ) = n = 1 k ( τ n + 1 τ n ) + n = 1 k ( τ n + 1 τ n )

对上式取 k + ,则有 lim k τ k ,这与假设矛盾。因此,有 lim n τ n = τ τ [ min { θ L , τ 1 } , τ 1 + ϕ ] 成立。

注2:值得注意的是,随着迭代次数的增加,算法1中生成的步长 τ n 可以增加。因此,使用这种类型的步长减少了对初始步长 τ 1 的依赖。

定理3.1 如果算法1中 s n = y n = x n + 1 = z n 成立,则有 s n F i x T V I ( F , C )

证明 因为 s n = y n ,于是 s n = P C n ( s n τ n F ( s n ) ) ,从而 s n C n 。由 C n 的定义可得

c ( s n ) = c ( s n ) + c ( s n ) , s n s n 0

因此 s n C

下面证明 s n V I ( F , C ) ,由 s n = P C n ( s n τ n F ( s n ) ) 可得

s n τ n F ( s n ) s n , y s n 0 ,   y C n

因此有

τ n F ( s n ) , y s n 0 ,   y C n

又根据注1可知 C C n ,且 τ n > 0 ,故有

F ( s n ) , y s n 0 ,   y C n

所以 s n V I ( F , C ) 。因为 s n = x n + 1 = z n ,则有 s n = ( 1 β n ) s n + β n T ( s n ) ,因此 T ( s n ) = s n ,即 s n F i x ( T ) ,所以 s n F i x ( T ) V I ( F , C )

引理3.2 假设(C1)~(C5)成立。令 { z n } 是由算法1生成的序列,对任意 u V I ( F , C ) 有下列不等式成立:

z n u 2 s n u 2 ( 1 θ τ n τ n + 1 ) y n z n 2 (8)

证明:因为 u V I ( F , C ) C T n ,由投影基本性质及 x n + 1 的定义有

2 z n u 2 = 2 P H n ( s n τ n F ( y n ) ) P H n ( u ) 2                   2 z n u , s n τ n F ( y n ) u                   = z n u 2 + s n τ n F ( y n ) u 2 z n s n + τ n F ( y n ) 2                   = z n u 2 + s n u 2 + τ n 2 F ( y n ) 2 2 τ n F ( y n ) , s n u                      z n s n 2 τ n 2 F ( y n ) 2 2 z n s n , τ n F ( y n )                   = z n u 2 + s n y n 2 z n s n 2 2 z n u , τ n F ( y n ) . (9)

于是有

z n u 2 s n y n 2 z n s n 2 2 z n u , τ n F ( y n ) . (10)

因为 u V I ( F , C ) ,所以 F ( u ) , y n u 0 。另外,因为 F 单调映射,则有 2 τ n F ( y n ) F ( u ) , y n u 0 ,于是将此项目添加到(10)的右侧

z n u 2 s n u 2 z n s n 2 2 z n u , τ n F ( y n )                  + 2 τ n y n u , F ( y n ) F ( u )                = s n u 2 z n s n 2 + 2 y n z n , τ n F ( y n )                   2 τ n F ( u ) , y n u                = s n u 2 z n s n 2 + 2 τ n y n z n , F ( y n ) F ( s n )                   + 2 τ n F ( s n ) , y n z n + 2 τ n F ( u ) , u y n (11)

注意到

2 τ n F ( y n ) F ( s n ) , y n z n 2 τ n F ( y n ) F ( s n ) y n z n 2 θ τ n τ n + 1 y n s n y n z n θ τ n τ n + 1 y n s n 2 + θ τ n τ n + 1 y n z n 2 . (12)

下面估计 2 τ n F ( s n ) , y n z n 。因为有 z n = P H n ( s n τ n F ( y n ) ) ,   z n H n

s n τ n F ( s n ) y n , z n y n 0 (13)

所以有

2 τ n F ( s n ) , y n z n 2 y n s n , z n y n                                  = z n s n 2 y n s n 2 z n y n 2 (14)

结合式(11)、(12)与(14)有

z n u 2 s n u 2 ( 1 θ τ n τ n + 1 ) y n s n 2 ( 1 θ τ n τ n + 1 ) y n z n 2 + 2 τ n F ( u ) , u y n (15)

F ( u ) 0 ,引理2.2有 F ( u ) = λ u c ( u ) u C 成立,从而 c ( u ) = 0 。因为 c ( x ) 为凸函数,于是

c ( y n ) c ( u ) + c ( u ) , y n u = 1 λ u F ( u ) , y n u

因此有

F ( u ) , u y n λ u c ( y n ) (16)

C n 的定义与 y n C n 可得

c ( s n ) + c ( s n ) , y n s n 0

另外,由次微分定义有

c ( y n ) , s n y n + c ( y n ) c ( s n )

通过以上两个不等式有

c ( y n ) c ( s n ) c ( y n ) , s n y n (17)

从而由假设(C4)与式(16)、(17)可知

F ( u ) , u y n λ u c ( y n ) λ u c ( s n ) c ( y n ) , s n y n                        λ u c ( s n ) c ( y n ) s n y n                        λ u L 1 s n y n 2 .

由引理2.2与假设(C4)有,则上式可为

F ( u ) , u y n λ u L 1 ω n y n 2 Q s n y n 2 (18)

Q = L 1 L 2 > 0   。因为假设(C5)成立,即 0 < Q < 1 θ 2 τ ,结合式(15)、(18)与引理3.1有

z n u 2 s n u 2 ( 1 θ τ n τ n + 1 ) y n z n 2 ( 1 θ τ n τ n + 1 2 M τ n ) y n s n 2               s n u 2 ( 1 θ τ n τ n + 1 ) y n z n 2 . (19)

如果 F ( u ) = 0 ,由式(15)知

z n u 2 s n u 2 ( 1 θ τ n τ n + 1 ) y n z n 2

综上引理3.2成立。

定理3.2 若假设条件(C1)~(C6)成立。则算法1生成的序列 { x n } 弱收敛于 F i x ( T ) V I ( F , C )

证明 通过引理3.2可知 lim n + ( 1 θ τ n τ n + 1 ) = 1 θ > 0 ,即存在 n 0 N 使得 ( 1 θ τ n τ n + 1 ) > 0 , n n 0 ,因此由引理3.2可得

z n u s n u ,    n n 0 (20)

接下来,将证明分成四个部分。

情形1. 序列 { x n } 是有界的。通过式(4)与(6)以及 x n + 1 = ( 1 γ n ) z n + γ n T ( z n ) 可知

x n + 1 u 2 = ( 1 γ n ) ( z n u ) + γ n ( T ( z n ) u ) 2 = ( 1 γ n ) 2 z n u 2 + γ n 2 T ( z n ) u 2 + 2 ( 1 γ n ) γ n z n u , T ( z n ) u ( 1 γ n ) 2 z n u 2 + γ n 2 z n u 2 + η γ n 2 T ( z n ) z n 2 + 2 ( 1 γ n ) γ n [ z n u 2 1 η 2 T ( z n ) z n 2 ]  = z n u 2 + γ n [ γ n ( 1 η ) T ( z n ) z n 2 ] (21)

因此,由 { γ n } ( 0 , 1 η ) 与式(20)有

x n + 1 u z n u s n u ,    n n 0 (22)

通过 s n 的定义有

s n u 2 = x n + δ n ( x n x n 1 ) u 2               = ( 1 + δ n ) ( x n u ) δ n ( x n 1 u ) 2               = ( 1 + δ n ) x n u 2 δ n x n 1 u 2 + ( 1 + δ n ) δ n x n x n 1 2 . (23)

另外有不等式

x n + 1 s n 2 = x n + 1 x n δ n ( x n x n 1 ) 2                   = x n + 1 x n 2 + δ n 2 x n x n 1 2 2 δ n x n + 1 x n , x n x n 1                   x n + 1 x n 2 + δ n 2 x n x n 1 2 2 δ n x n + 1 x n x n x n 1                   ( 1 δ n ) x n + 1 x n 2 + ( δ n 2 δ n ) x n x n 1 2 . (24)

结合式(22)、(23)和(24)整理可得

x n + 1 u 2 ( 1 + δ n ) x n u 2 δ n x n 1 u 2 + ( 1 + δ n ) δ n x n x n 1 2                      ( 1 δ n ) x n + 1 x n 2 ( δ n 2 δ n ) x n x n 1 2                        = ( 1 + δ n ) x n u 2 δ n x n 1 u 2 ( 1 δ n ) x n + 1 x n 2                     + [ δ n ( 1 + δ n ) ( δ n 2 δ n ) ] x n x n 1 2                 = ( 1 + δ n ) x n u 2 δ n x n 1 u 2 ( 1 δ n ) x n + 1 x n 2                     +2 δ n x n x n 1 2                  ( 1 + δ n + 1 ) x n u 2 δ n x n 1 u 2 ( 1 δ n ) x n + 1 x n 2                     +2 δ n x n x n 1 2 ,     n n 0 . (25)

从而由式(25)可得

x n + 1 u 2 δ n +1 x n u 2 +2 δ n + 1 x n + 1 u 2 x n u 2 δ n x n 1 u 2 + 2 δ n x n x n 1 2    +2 δ n + 1 x n + 1 x n 2 ( 1 δ n ) x n + 1 x n 2  ,   n n 0 . (26)

Ξ n = x n u 2 δ n x n 1 u 2 + 2 δ n x n x n 1 2 ,从而有

Ξ n + 1 Ξ n ( 1 δ n 2 δ n + 1 ) x n + 1 x n 2 (27)

由假设(C5) δ n [ 0 , 1 3 ) ,于是 1 δ n 2 δ n + 1 > 0 ,即有

Ξ n + 1 Ξ n σ x n + 1 x n 2 0 (28)

其中 σ = 1 3 δ > 0 。从而序列 Ξ n 是非增的,于是有

Ξ n = x n u 2 δ n x n 1 u 2 + 2 δ n x n x n 1 2       x n u 2 δ n x n 1 u 2 . (29)

通过式(29)可知

x n u 2 δ n x n 1 u 2 + Ξ n                δ x n u 2 + Ξ 1                δ 2 x n u 2 + Ξ 1 ( 1 + δ )                δ n x 0 u 2 + Ξ 1 ( 1 + δ + + δ n 1 )                δ n x 0 u 2 + Ξ 1 1 δ . (30)

因为 Ξ n +1 定义可知

Ξ n +1 = x n + 1 u 2 δ n + 1 x n u 2 + 2 δ n + 1 x n + 1 x n 2        δ n + 1 x n u 2 . (31)

整理式(30)与(31)得

Ξ n +1 δ n + 1 x n u 2 δ x n u 2 δ n + 1 x 0 u 2 + δ   Ξ 1 1 δ

结合上述不等式与式(28)有

σ n = 1 k x n + 1 x n 2 Ξ 1 Ξ k + 1                           δ k + 1 x 0 u 2 + Ξ 1 1 δ   x 0 u 2 + Ξ 1 1 δ . (32)

因此有

n = 1 x n + 1 x n 2 < + (33)

所以 lim x x n + 1 x n 2 = 0 ,由此可知 lim x x n + 1 x n = 0

因为 δ n 有界,通过式(25)有

x n + 1 u 2 ( 1 + δ n ) x n u 2 δ n x n 1 u 2 + 2 δ n x n x n 1 2                            = x n u 2 + δ n ( x n u 2 - x n 1 u 2 ) + 2 δ n x n x n 1 2 . (34)

由引理2.5与式(33)知 lim x x n u 2 存在,因此 lim x x n u 存在,进而序列 { x n } 是有界。

情形2. 序列存在且 lim x y n z n = 0 ,   lim x s n y n = 0 ,   lim x T ( z n ) z n = 0

由情形1的过程知 lim x x n + 1 x n = 0 ,通过 s n 的定义

x n + 1 s n = x n + 1 x n δ n ( x n x n 1 )                 x n + 1 x n + δ n x n x n 1                 x n + 1 x n + δ x n x n 1 . (35)

由式(35)知当 n 时, lim x x n + 1 s n = 0 。又因 lim x x n u 2 存在,所以取 n 。由式(23)有

lim x x n u 2 = lim x s n u 2 (36)

另外取 n 时,由式(22)结合式(36)有

lim x x n u 2 = lim x z n u 2 = lim x s n u 2 (37)

对式(8)取 n 时有 lim x z n y n 2 = 0 ,因此有

lim x z n y n = 0 (38)

通过式(19)可得

z n u 2 s n u 2 ( 1 θ τ n τ n + 1 ) y n z n 2 ( 1 θ τ n τ n + 1 2 M τ n ) y n s n 2

n 时,结合式(37)、(38)以及假设(C5)推出

lim x s n y n = 0 (39)

n 时,由引理3.1与式(21)有

lim x T ( z n ) z n = 0 (40)

情形3. 序列 { x n } 的弱聚点属于 F i x ( S ) 。因为 δ n 有界以及情形1知 lim x x n + 1 x n = 0 ,并且由 s n 的定义有

x n s n = δ n x n x n 1 0 (41)

此外,情形2结论,得出 lim x z n s n = 0 ,因此

lim x z n s n = 0 (42)

由情形1知 { x n } 是有界的序列,假设存在子列 { x n j } { x n } 使得 x n j p 。即有,

lim sup x u , u x n = lim x u , u x n j = u , u p

通过式(41)可以得到 s n j p 。同理由式(42)有 z n j p ,结合 lim x T z n z n = 0 ,所以 p F i x ( T )

情形4. 序列 { x n } 弱收敛于 V I ( F , C ) 。因为情形3与式(39)知 s n j p ,则有 y n j p 。由半空间 C n j 定义与 y n j C n j 可得

c ( s n j ) + c ( s n j ) , y n k s n j 0

因为 { x n } 有界,所以由式(41)可得 { s n } 是有界,并且由于 c ( s n ) 是Lipschitz连续的,从而知存在 M > 0 满足 c ( s n ) M 。因此由以上不等式可得

c ( s n j ) + c ( s n j ) y n j s n j M y n j s n j (43)

由假设(C4)知 c ( x ) 弱下半连续。结合式(43)、 s n j p lim x s n j y n j = 0 ,由定义2.4有

c ( p ) lim inf x c ( s n j ) lim inf x M s n j y n j = 0

因此由 C 的定义知 p C

下面证明 p V I ( F , C ) ,令

G ( x ) : = { F ( x ) + N C ( x )    x C ;                        x C ,

其中 N C ( x ) : = { ε H : ε , z x 0 , z C } 。由引理2.3知 G 是极大单调算子,则对任意 ( x , y ) g r a G ,通过定义2.5有

y G ( x ) = F ( x ) + N C ( x )

等价于

y F ( x ) N C ( x )

由法锥 N C ( x ) 的定义及 p C 可得

y F ( x ) , p x 0 ,   ( x , y ) g r a G

整理可得

y , x p F ( x ) , x p ,   ( x , y ) g r a G (44)

通过 T n 的定义有

s n j τ n j F ( s n j ) y n j , x y n j 0

因为 τ n j > 0 ,因此

s n j y n j τ n j F ( s n j ) , x y n j 0 (45)

结合式(44)与(45)可得

y , x p F ( x ) , x p + y n j s n j τ n k + F ( s n j ) , y n j x                 = F ( x ) , x y n j + y n j p + y n j s n j τ n k + F ( s n j ) , y n j x

由内积的性质有

F ( x ) , x y n j + F ( x ) , y n j p + F ( s n j ) , y n j x + y n j s n j τ n j , y n j x = F ( x ) F ( y n j ) , x y n j + F ( y n j ) F ( s n j ) , x y n j    + F ( x ) , y n j p + y n j s n j τ n k , y n j x

F 的单调性知

y , x p F ( x ) , y n j p + F ( y n j ) F ( s n j ) , x y n j + y n j s n j τ n j , y n j x (46)

因此有

y , x p F ( x ) , y n j p + F ( y n j ) F ( s n j ) , x y n k                    + 1 τ n k y n j s n j , y n j x (47)

由情形3过程有 s n j p y n j p ,从而有

y n j s n j , y n j x 0 ,   j (48)

因为 F 是Lipschitz连续,并且 y n j p x n j p ,于是有

F ( y n j ) F ( x n j ) , x y n j 0 ,   j (49)

又因 y n j p ,所以

F ( x ) , y n j p 0 ,   j (50)

通过式(48)-(50),当 j 时,由式(47)可得

y , x p 0 ,   ( x , y ) g r a G

因为 G 为极大单调算子,所以 0 G ( p ) ,从而 p G 1 ( 0 ) = V I ( F , C ) 。设序列 { x n } 存在子序列 { x n j } { x m j } 使得 x n j p x m j q ( p , q V I ( F , C ) ) 。任意给定 p V I ( F , C ) ,由情形1知 lim x x n p 存在,结合引理2.1有

lim x x n p = lim x x n j p = lim inf x x n j p                     < lim inf x x n j q = lim inf x x n j q                     = lim x x m q = lim x x m j q                     < lim inf x x n j p = lim x x m j p                     = lim x x n p .

从而有 lim x x n p < lim x x n p 不成立,故与假设矛盾,所以 p = q ,因此 { x n } 弱收敛于 V I ( F , C ) 。综合情形3与情形4有序列 { x n } 弱收敛于 F i x ( T ) V I ( F , C )

3.2. 数值结果

在本节研究中,我们利用例子3.1展示了算法3.1的计算机验证结果,并且在不同的拟非扩张映射下对其进行了测试,与文献[18][24]中的算法进行了比较。数值实验表明,引入惯性项和适当的拟非扩张映射能显著减少算法3.1的计算时间。所有实验均在一台装有AMD Ryzen7 4700U处理器和2.0 GB内存的笔记本电脑上,使用Matlab 2021 b进行。运行时间以CPU秒为单位表示,迭代步骤则用iter表示。

例3.1 定义 C = { x R + n : x 1 + x 2 + x 3 + + x n n } F ( x ) : = A x + q ,其中 A n × n 矩阵, q = ( 1 , 1 , , 1 )

A = ( 4    2 1     4    2       1    4    2                                       1     4 )

初始点: x 0 = ( 0 , 0 , , 0 ) ,   x 1 = ( 1 , 1 , , 1 ) 。取拟非扩张映射分别为 f ( x ) = 1 2 x ,集合 C 是非空闭凸集, F C 上单调且Lipschiz连续在本文的算法中,选取符合条件的如下参数: λ 0 = 1 , μ = 0.8 , α n = 0.25 , β n = 0.3 。算法3.1与文献[18]算法(3)和[24]算法(4)的比较结果如表1所示。

Table 1. The numerical result for example 3.1

1. 例3.1数值结果

n

ε

算法4 [24]

算法3 [18]

算法3.1

iter

CPU

iter

CPU

iter

CPU

5

10 4

20

0.034

21

0.035

19

0.027

10 5

28

0.041

25

0.036

25

0.038

10 6

32

0.048

31

0.046

30

0.044

50

10 4

45

0.076

22

0.039

30

0.041

10 5

58

0.089

29

0.043

39

0.045

10 6

71

0.109

35

0.058

48

0.055

500

10 4

77

1.223

22

0.641

40

0.618

10 5

99

1.778

29

0.841

51

0.808

10 6

122

1.958

35

0.984

62

0.966

由数值实验可见,本文算法相较于文献[18] [24]有一定的优越性,收敛效果更好。比如在维度为500的时候,本文算法相比于文献[18]中的算法,找到解的时间明显更快。对于精度,在同一维度与精度下,本文算法仍具有一定的优越性。

4. 结论

本文提出了一种新算法,用于在可行集为凸函数时求解变分不等式与不动点问题的公共解。该算法利用拟非扩张映射和惯性加速技术,已证明具有弱收敛性。本文采用线搜索程序来更新算法的步长,无须事先知道Lipschitz系数,并根据类Mann迭代生成新的迭代点。最后,通过数值实验验证了新算法的有效性。

基金项目

资助项目1:KYZK2024027:变分不等式与不动点问题非单调步长的惯性投影算法。

资助项目2:KYZK2024010:图像处理中的张量离散不适定问题及其高性能迭代算法研究。

资助项目3:KYZK2024003:变分不等式与不动点问题在NASH群体博弈的应用研究。

NOTES

*通讯作者。

参考文献

[1] Ansari, Q.H., Islam, M. and Yao, J. (2018) Nonsmooth Variational Inequalities on Hadamard Manifolds. Applicable Analysis, 99, 340-358.
https://doi.org/10.1080/00036811.2018.1495329
[2] Van Huy, P., Hien, N.D. and Anh, T.V. (2020) A Strongly Convergent Modified Halpern Subgradient Extragradient Method for Solving the Split Variational Inequality Problem. Vietnam Journal of Mathematics, 48, 187-204.
https://doi.org/10.1007/s10013-019-00378-y
[3] Sahu, D.R., Yao, J.C., Verma, M. and Shukla, K.K. (2020) Convergence Rate Analysis of Proximal Gradient Methods with Applications to Composite Minimization Problems. Optimization, 70, 75-100.
https://doi.org/10.1080/02331934.2019.1702040
[4] Nam, N.M., Rector, R.B. and Giles, D. (2017) Minimizing Differences of Convex Functions with Applications to Facility Location and Clustering. Journal of Optimization Theory and Applications, 173, 255-278.
https://doi.org/10.1007/s10957-017-1075-6
[5] Censor, Y., Gibali, A. and Reich, S. (2012) Extensions of Korpelevich’s Extragradient Method for the Variational Inequality Problem in Euclidean Space. Optimization, 61, 1119-1132.
https://doi.org/10.1080/02331934.2010.539689
[6] Shan, Z., Zhu, L., Wang, Y. and Yin, T. (2022) Modified Mann-Type Inertial Subgradient Extragradient Methods for Solving Variational Inequalities in Real Hilbert Spaces. Filomat, 36, 1557-1572.
https://doi.org/10.2298/fil2205557s
[7] Gibali, A. and Thong, D.V. (2020) A New Low-Cost Double Projection Method for Solving Variational Inequalities. Optimization and Engineering, 21, 1613-1634.
https://doi.org/10.1007/s11081-020-09490-2
[8] Gibali, A. and Shehu, Y. (2018) An Efficient Iterative Method for Finding Common Fixed Point and Variational Inequalities in Hilbert Spaces. Optimization, 68, 13-32.
https://doi.org/10.1080/02331934.2018.1490417
[9] Alber, Y.I. and Iusem, A.N. (2001) Extension of Subgradient Techniques for Nonsmooth Optimization in Banach Paces. Set-Valued Analysis, 9, 315-335.
https://doi.org/10.1023/a:1012665832688
[10] Liu, H. and Yang, J. (2020) Weak Convergence of Iterative Methods for Solving Quasimonotone Variational Inequalities. Computational Optimization and Applications, 77, 491-508.
https://doi.org/10.1007/s10589-020-00217-8
[11] Wang, Y., Fang, X., Guan, J.L., et al. (2020) On Split Null Point and Common Fixed Point Problems for Multivalued Demicontractive Mappings. Optimization, 4, 1-20.
[12] Korpelevich, G.M. (1976) An Extragradient Method for Finding Saddle Points and for Other Problems. Matecon, 12, 747-756.
[13] Tseng, P. (2000) A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings. SIAM Journal on Control and Optimization, 38, 431-446.
https://doi.org/10.1137/s0363012998338806
[14] Ceng, L., Petrușel, A., Yao, J. and Yao, Y. (2018) Hybrid Viscosity Extragradient Method for Systems of Variational Inequalities, Fixed Points of Nonexpansive Mappings, Zero Points of Accretive Operators in Banach Spaces. Fixed Point Theory, 19, 487-502.
https://doi.org/10.24193/fpt-ro.2018.2.39
[15] Shehu, Y. and Iyiola, O.S. (2017) Iterative Algorithms for Solving Fixed Point Problems and Variational Inequalities with Uniformly Continuous Monotone Operators. Numerical Algorithms, 79, 529-553.
https://doi.org/10.1007/s11075-017-0449-z
[16] Zhao, X. and Yao, Y. (2020) Modified Extragradient Algorithms for Solving Monotone Variational Inequalities and Fixed Point Problems. Optimization, 69, 1987-2002.
https://doi.org/10.1080/02331934.2019.1711087
[17] Shehu, Y. and Cholamjiak, P. (2015) Another Look at the Split Common Fixed Point Problem for Demicontractive Operators. Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas, 110, 201-218.
https://doi.org/10.1007/s13398-015-0231-9
[18] Tan, B., Fan, J. and Qin, X. (2021) Inertial Extragradient Algorithms with Non-Monotonic Step Sizes for Solving Variational Inequalities and Fixed Point Problems. Advances in Operator Theory, 6, Article No. 61.
https://doi.org/10.1007/s43036-021-00155-0
[19] Kraikaew, R. and Saejung, S. (2013) Strong Convergence of the Halpern Subgradient Extragradient Method for Solving Variational Inequalities in Hilbert Spaces. Journal of Optimization Theory and Applications, 163, 399-412.
https://doi.org/10.1007/s10957-013-0494-2
[20] Dong, Q., He, S. and Rassias, M.T. (2020) General Splitting Methods with Linearization for the Split Feasibility Problem. Journal of Global Optimization, 79, 813-836.
https://doi.org/10.1007/s10898-020-00963-3
[21] Shehu, Y. and Iyiola, O.S. (2016) Strong convergence result for monotone variational inequalities. Numerical Algorithms, 76, 259-282.
https://doi.org/10.1007/s11075-016-0253-1
[22] Tong, M.Y. and Tian, M. (2020) Strong Convergence of the Tseng Extragradient Method for Solving Variational Inequalities. Applied Set-Valued Analysis and Optimization, 2, 19-33.
[23] Thong, D.V. and Van Hieu, D. (2018) Some Extragradient-Viscosity Algorithms for Solving Variational Inequality Problems and Fixed Point Problems. Numerical Algorithms, 82, 761-789.
https://doi.org/10.1007/s11075-018-0626-8
[24] He, S. and Wu, T. (2017) A Modified Subgradient Extragradient Method for Solving Monotone Variational Inequalities. Journal of Inequalities and Applications, 2017, Article No. 89.
https://doi.org/10.1186/s13660-017-1366-3
[25] Opial, Z. (1967) Weak Convergence of the Sequence of Successive Approximations for Nonexpansive Mappings. Bulletin of the American Mathematical Society, 73, 591-597.
https://doi.org/10.1090/s0002-9904-1967-11761-0
[26] Ye, M. (2018) An Improved Projection Method for Solving Generalized Variational Inequality Problems. Optimization, 67, 1523-1533.
https://doi.org/10.1080/02331934.2018.1478971
[27] Rockafellar, R.T. (1970) On the Maximality of Sums of Nonlinear Monotone Operators. Transactions of the American Mathematical Society, 149, 75-88.
https://doi.org/10.1090/s0002-9947-1970-0282272-5
[28] He, S. and Xu, H. (2012) Uniqueness of Supporting Hyperplanes and an Alternative to Solutions of Variational Inequalities. Journal of Global Optimization, 57, 1375-1384.
https://doi.org/10.1007/s10898-012-9995-z
[29] Alvarez, F. and Attouch, H. (2001) An Inertial Proximal Method for Maximal Monotone Operators via Discretization of a Non-Linear Oscillator with Damping. Set-Valued Analysis, 9, 3-11.
https://doi.org/10.1023/a:1011253113155

Baidu
map