擬單調變分不等式的新雙慣性次梯度外梯度算法

在實Hilbert空間中提出一種求解擬單調變分不等式問題的雙慣性次梯度外梯度算法.該算法每次迭代只計算一次映射值和一次向可行集上的投影，并且將雙慣性和松弛技術相結合，提高了次梯度外梯度方法求解變分不等式問題的收斂速度.在映射擬單調、Lipschitz連續和對偶變分不等式解集非空的假設條件下，獲得了該算法的弱收斂結果.同時，在強擬單調的假設下得到了算法在Hilbert空間中強收斂結果.最后，數值實驗表明該算法的有效性.

變分不等式; 擬單調; 次梯度外梯度算法; 雙慣性加速

O178; O221

A

0406-11

03.012

1 引言及研究背景

設H是實Hilbert空間，其內積和范數分別表示為〈·，·〉和‖·‖.變分不等式（VI）問題是：求x*∈C，滿足

〈F（x*），x-x*〉≥0， x∈C，

（1）

其中，C是H中的一個非空閉凸子集，F：H→H是一個映射.記問題（1）的解集為S.該問題在優化理論、非線性分析、微分方程等領域發揮著重要的作用^[1-4].

問題（1）的對偶變分不等式（DVI）問題是求x*∈C，滿足

〈F（x），x-x*〉≥0， x∈C.

（2）

記問題（2）的解集為SD.由文獻[5]引理2.1易知，當映射F是連續并且集合C是凸集時，SDS.當映射F是偽單調和連續時，SD=S.

近年來求解變分不等式問題的投影梯度算法^[6]被廣泛研究.為了求解變分不等式問題，文獻[7-8]提出了外梯度算法，文獻[9]提出了次梯度外梯度算法.文獻[10]綜合了文獻[8-9]所提算法的優點，提出修正的次梯度外梯度算法，在每次迭代中只需要計算一次映射F的取值和一次向可行集C的投影.文獻[11]采用了慣性技術來加速文獻[10]中的算法，以便于算法獲得更快的收斂速度，提出了帶有慣性項的次梯度外梯度算法.

文獻[12]討論了帶有多步慣性的迭代算法，其結果表明：多步慣性技巧可以提高求解優化問題的算法的收斂速度.此外，松弛技術也被證明是解決優化問題的一個重要方法.慣性技術和松弛技術都源于一個動力系統在時間上的顯式離散化^[13-14].許多研究^[13，15-16]已經考慮過將這2種技術相結合，并融入已知的算法中，以便算法獲得更快的收斂速度.文獻[16]在文獻[17]算法的基礎上，加入了慣性項和松弛項，提出一種自適應步長下帶有松弛項和慣性項的次梯度外梯度算法.其實驗結果表明，添加慣性項和松弛項提高了算法收斂的速度，減少所需的迭代次數和CPU運行時間.

最近，文獻[18]在文獻[9]算法的基礎上引入雙慣性項和松弛項，提出了自適應步長下帶有雙慣性項的次梯度外梯度算法：

zn=xn+δ（xn-xn-1），

wn=xn+θn（xn-xn-1），

yn=PC（wn-λnF（wn）），

Tn：={x∈H：〈wn-λnF（wn）-yn， x-yn〉≤0}，

xn+1=（1-αn）zn+αnPTn（wn- λnF（yn）），

（3）

其中

0≤θn≤θn+1≤1， 0≤δlt;min{ε-2εε，θ1}，

0lt;α≤αn≤αn+1lt;11+ε， ε∈（2，∞）.

在映射F為偽單調Lipschitz連續的假設條件下，在Hilbert空間中建立了算法（3）的弱收斂性結果.在映射F為強偽單調的條件下，得到算法（3）在Hilbert空間中的強收斂定理.最后在一些附加假設下，得到了算法（3）特殊情況下線性收斂率的結果.

需要注意的是，許多文獻^{[8-11，19-21]}中求解變分不等式問題的算法要求映射為單調或者偽單調.許多研究^[16-17，22]對映射的單調性條件進行了削弱，將映射削弱為擬單調.特別地，文獻[17]在Hilbert空間中提出了求解擬單調變分不等式問題的次梯度外梯度算法.

受文獻[17-18]的啟發，本文在Hilbert空間中提出一種求解問題（1）的雙慣性次梯度外梯度算法.在映射為擬單調、Lipschitz連續和對偶變分不等式解集非空的條件下，獲得了算法的弱收斂性結果;在映射滿足強擬單調的條件下，證明了算法所產生的序列的強收斂性.文末還給出了相關算法的數值實驗，表明了算法的有效性.

李 卓，等：擬單調變分不等式的新雙慣性次梯度外梯度算法

與文獻[10]相比，本文的算法采用了雙慣性和松弛技巧對算法進行了加速.同時，相比于文獻[10]中的常數步長，本文采用了自適應步長策略.此外，本文不僅在更弱的條件下獲得了算法在Hilbert空間中的弱收斂性結果，而且還獲得了算法在Hilbert空間中強收斂結果.與文獻[16]相比，本文的算法減少了映射的賦值次數，增加了一個慣性項，并獲得了在Hilbert空間中強收斂結果.與文獻[18]相比，本文的算法減少了映射的賦值次數，采用了不同的自適應步長策略，減小了算法對初始步長的依賴，慣性參數δn和松弛參數αn的取值范圍更廣.并且，本文在映射擬單調的條件下獲得了收斂性結果，削弱了文獻[18]中映射的單調性條件.在Hilbert空間中獲得強收斂的條件更弱，映射不再需要滿足強偽單調的條件.

2 預備知識

本節回憶一些基本的定義及結論.

在實Hilbert空間H中，序列{xn}弱收斂和強收斂到x，分別記作xnx和xn→x.對非空閉凸集CH，定義投影映射PC：H→C如下：

‖x-PC（x）‖=min{‖y-x‖：y∈C}， x∈H.

眾所周知，問題（1）等價于：找x*∈C，滿足

x*=PC（x*-λF（x*）），

其中，λ是任意的正實數.

與文獻[18，22]中定義2.1類似，有以下定義.

定義 2.1

稱映射F：C→H在C上是：

（i） 強單調的，若存在γgt;0，使得

〈F（y）-F（x），y-x〉≥γ‖y-x‖2， x，y∈C.

（ii） 單調的，若

〈F（y）-F（x），y-x〉≥0， x，y∈C.

（iii） 強偽單調的，若存在ηgt;0，使得

〈F（x），y-x〉≥0

〈F（y），y-x〉≥η‖y-x‖2， x，y∈C.

（iv） 偽單調的，若

〈F（x），y-x〉≥0

〈F（y），y-x〉≥0， x，y∈C.

（v） 擬單調的，若

〈F（x），y-x〉gt;0

〈F（y），y-x〉≥0， x，y∈C.

由上述定義可得（i）（ii）（iii）（iv）（v），反之則不成立.

引理 2.1^[23]

設CH是一個非空閉凸集，下列結論成立：

（i） y∈C，x∈H，則

〈PC（x）-x，y-PC（x）〉≥0;

（ii） y∈C，x∈H，則

‖y-PC（x）‖2≤‖x-y‖2-‖PC（x）-x‖2;

（iii） x，y∈H，α∈R是一個常數，則

‖αx+（1-α）y‖2=α‖x‖2+（1-α）‖y‖2-α（1-α）‖x-y‖2.

（4）

引理 2.2^[24]

設非負的實序列{sn}、{tn}和{γn}，滿足n≥1，

sn+1≤sn+γn（sn-sn-1）+tn， ∑∞n=1tnlt;∞，

其中，n∈N，0≤γn≤γlt;1，那么有以下結論成立：

（i） ∑∞n=0[sn-sn-1]+lt;∞，其中[s]+=max{s，0};

（ii） 存在s*∈[0，+∞），使得limn→∞sn=s*.

引理 2.3^[25]

若CH是一個非空閉凸子集，{xn}是H中的序列，滿足：

（i） x∈C，limn→∞‖xn-x‖存在;

（ii） {xn}的所有弱聚點都在C中，

則{xn}弱收斂到集合C中一點.

命題 2.1^[26]

若CH是一個非空閉凸子集，映射F：H→H連續，S表示變分不等式（1）的解集，SD表示對偶變分不等式（2）的解集，若有下面任意一條成立：

（i） 映射F在C上是偽單調的，并且S≠;

（ii） 映射F為映射G的梯度，其中映射G：K→R為可微擬凸函數，且在C上可達到全局最小值，K為包含集合C的開集;

（iii） 映射F在C上是擬單調的，F≠0，并且集合C是有界集;

（iv） 映射F在C上是擬單調的，F≠0，并且存在一個正實數r，使得對于x∈C滿足‖x‖≥r，都存在y∈C，使得‖y‖≤r和〈F（x），y-x〉≤0;

（v） 映射F在C上是擬單調的，集合C的內部非空，且存在F（x*）≠0，

則SD是非空的.

3 算法及收斂性分析

下面給出本文求解問題（1）的算法.

算法 1

初始

給定x0，x-1∈H，y0，y-1∈C.{dn}和{ξn}是非負實序列，且

∑∞n=0dnlt;∞， ∑∞n=0ξnlt;∞.

取λ0，θ0，δ0gt;0，0lt;μlt;1，{θn}∞n=0[0，+∞），{δn}∞n=0[0，+∞）.令

z0=x0+δ0（x0-x-1）， w0=x0+θ0（x0-x-1）.

設n=0.

迭代

Step 1： 選取αn，αn∈（0，n]，

νn=‖yn-yn-1‖2+‖xn-xn-1‖2，

其中

n=

min{ξnνn，}， 若νn≠0;

， 其他.

（5）

Step 2：計算

Tn：={x∈H：〈wn-λnF（yn-1）-yn，x-yn〉≤0}，

xn+1=（1-αn）zn+αnPTn（wn-λnF（yn））.

Step 3：計算

zn+1=xn+1+δn+1（xn+1-xn），

wn+1=xn+1+θn+1（xn+1-xn），

yn+1=PC（wn+1-λnF（yn）），

（6）

其中

λn+1=

min{μ‖yn-yn-1‖‖F（yn）-F（yn-1）‖，λn+dn}，

若F（yn）≠F（yn-1），

λn+dn， 其他.

（7）

若yn+1=wn+1=yn，則算法停止.否則，設n：=n+1并且返回Step1.

注 3.1

若yn+1=wn+1=yn，代入式（6）的最后一項，有yn=PC（yn-λnF（yn）），因此yn∈S.

為了獲得算法的收斂性，假設下述條件成立：

條件 （C1） SD非空;

（C2）" 映射F：H→H是Lipschitz連續的，其Lipschitz常數為Lgt;0，即：存在Lgt;0，使得

‖F（x）-F（y）‖≤L‖x-y‖， x，y∈H;

（C3） 映射F：H→H是序列弱連續的，即：

當{xn}弱收斂到x時，有{F（xn）}弱收斂F（x）;

（C4） 映射F：H→H是擬單調映射;

（C5） 集合A={z∈C：F（z）=0}＼SD是一個有限集;

（C6） 選取實數序列滿足下述條件：

（i） 0≤θn≤1，0≤δn≤δlt;1，δn≤θn，

（ii） 0lt;α≤αn≤，∈（0，1）.

注 3.2

條件（C1）～（C5）與文獻[16-17]中的假設一致，這些條件常見于求解擬單調變分不等式問題的算法研究中.與文獻[16]相比，本文的慣性參數θn與松弛參數αn的選取不需要驗證額外的假設條件.與文獻[18]相比，本文的慣性參數δn和松弛參數αn的取值范圍更廣.

為了書寫簡便，記

un：=PTn（wn-λnF（yn））.

先證明一些引理.

引理 3.1

算法1中生成的序列{λn}極限存在，并且有limn→∞λn=λ∈[min{μL，λ0}，λ0+d]，其中d=∑∞n=0dnlt;∞.

引理 3.1的證明見文獻[17]引理3.1.

注 3.3

自適應步長序列λn是非單調的，使算法減小了對初始步長λ0的依賴.λn在迭代中可以是逐步增大的，但是當n比較大時，步長序列λn可能是非增的.原因是∑∞n=0dn=dlt;∞，那么有limn→∞"" dn=0.

引理 3.2

假設條件（C1）～（C4）成立，{xn}、{yn}、{wn}、{zn}是由算法1生成的序列，則可得以下結論：

（a） 由算法1生成的序列{xn}有界;

（b） limn→∞‖xn-p‖2存在;

（c） limn→∞‖xn+1-xn‖2=0，limn→∞‖xn-yn‖2=0，limn→∞‖wn-xn‖2=0，limn→∞‖yn-wn‖2=0，

limn→∞‖yn-1-yn‖2=0.

證明

根據算法1可知

xn+1=（1-αn）zn+αnun，

故有

un-zn=1αn（xn+1-zn）.

任取p∈SD，由式（4）可得

‖xn+1-p‖2=‖（1-αn）（zn-p）+αn（un-p）‖2=

（1-αn）‖zn-p‖2+αn‖un-p‖2-αn（1-αn）‖zn-un‖2=

（1-αn）‖zn-p‖2+αn‖un-p‖2-1-αnαn‖xn+1-zn‖2.

（8）

類似地，由式（4）可得

‖zn-p‖2=‖xn+δn（xn-xn-1）-p‖2=

‖（1+δn）（xn-p）-δn（xn-1-p）‖2=

（1+δn）‖xn-p‖2-δn‖xn-1-p‖2+δn（1+δn）‖xn-xn-1‖2.

（9）

由于p∈SD，yn∈C，有〈F（yn），yn-p〉≥0，那么可以推出

〈F（yn），yn-un〉≥〈F（yn），p-un〉.

（10）

由引理2.1（ii）和式（10），可以得到

‖un-p‖2≤‖wn-λnF（yn）-p‖2-‖wn-λnF（yn）-un‖2=

‖wn-p‖2-‖wn-un‖2+

2λn〈F（yn），p-un〉≤

‖wn-p‖2-‖wn-un‖2+2λn〈F（yn），yn-un〉=

‖wn-p‖2-‖wn-yn‖2-‖yn-un‖2+

2〈wn-yn，un-yn〉+2λn〈F（yn），yn-un〉=

‖wn-p‖2-‖wn-yn‖2-‖yn-un‖2+

2〈wn-λnF（yn-1）-yn，un-yn〉+

2λn〈F（yn-1）-F（yn），un-yn〉≤

‖wn-p‖2-‖wn-yn‖2-‖yn-un‖2+

2λn〈F（yn-1）-F（yn），un-yn〉，

（11）

其中，第1個不等式是由引理2.1（ii）可得，第2個不等式是由式（10）可得，第3個不等式是由un∈Tn可得.

當F（yn）≠F（yn-1）時，根據{λn}的定義，有

2λn〈F（yn-1）-F（yn），un-yn〉≤

2λn‖F（yn-1）-F（yn）‖‖un-yn‖≤

2μλnλn+1‖yn-1-yn‖‖un-yn‖≤

μλnλn+1（‖yn-1-yn‖2+‖un-yn‖2），

（12）

其中，第1個不等式是由Cauchy-Schwarz不等式可得，第2個不等式是由λn的定義可得，第3個不等式是因為

2‖yn-1-yn‖‖un-yn‖≤

‖yn-1-yn‖2+‖un-yn‖2.

當F（yn）=F（yn-1）時，式（12）恒成立.

由式（11）和（12）可得

‖un-p‖2≤‖wn-p‖2+μλnλn+1‖yn-1-yn‖2-

（1-μλnλn+1）‖yn-un‖2-‖yn-wn‖2.

（13）

由式（4）可得

‖wn-p‖2=‖xn+θn（xn-xn-1）-p‖2=

‖（1+θn）（xn-p）-θn（xn-1-p）‖2=

（1+θn）‖xn-p‖2-θn‖xn-1-p‖2+θn（1+θn）‖xn-xn-1‖2.

（14）

由zn的定義，有

‖xn+1-zn‖2=‖xn+1-（xn+δn（xn-xn-1））‖2=

‖（xn+1-xn）-δn（xn-xn-1）‖2=

‖xn+1-xn‖2+δ2n‖xn-xn-1‖2-2δn〈xn+1-xn，xn-xn-1〉≥

‖xn+1-xn‖2+δ2n‖xn-xn-1‖2-2δn‖xn+1-xn‖‖xn-xn-1‖≥

（1-δn）‖xn+1-xn‖2+（δ2n-δn）‖xn-xn-1‖2，

（15）

其中，第1個不等式由Cauchy-Schwarz不等式可得，第2個不等式成立是因為

2‖xn+1-xn‖‖xn-xn-1‖≤

‖xn+1-xn‖2+‖xn-xn-1‖2.

將式（9）、（13）～（15）代入式（8）可得

‖xn+1-p‖2≤

（1-αn）[（1+δn）‖xn-p‖2-δn‖xn-1-p‖2+δn（1+δn）‖xn-xn-1‖2]+

αn[（1+θn）‖xn-p‖2-θn‖xn-1-p‖2+θn（1+θn）‖xn-xn-1‖2+

μλnλn+1‖yn-1-yn‖2-

‖yn-wn‖2-（1-μλnλn+1）‖yn-un‖2]-

（1-αn）（1-δn）αn‖xn+1-xn‖2-（1-αn）（δ2n-δn）αn‖xn-xn-1‖2.

（16）

進一步，式（16）可以寫為

‖xn+1-p‖2≤‖xn-p‖2+σn[‖xn-p‖2-

‖xn-1-p‖2]+φn-n，

（17）

其中

σn=（1-αn）δn+αnθn，

ρn=（1-αn）（1+δn）δn+

αnθn（1+θn）-（1-αn）（δ2n-δn）αn，

n=αn‖yn-wn‖2+αn（1-μλnλn+1）‖yn-un‖2+

（1-αn）（1-δn）αn‖xn+1-xn‖2，

（18）

φn=μαnλnλn+1‖yn-1-yn‖2+ρn‖xn-xn-1‖2.

（19）

接下來討論σn和ρn的取值范圍.

由條件（C6）可知α≤αn≤lt;1，0≤θn≤1，0≤δn≤δlt;1，δn≤θn，可以得到

σn=（1-αn）δn+αnθn≤

（1-）δ+lt;1，

（20）

以及

ρn=（1-αn）（1+δn）δn+αnθn（1+θn）-（1-αn）（δ2n-δn）αn≤

（1-αn）θn（1+θn）+αnθn（1+θn）+

（1-α）（1-δn）θnα≤

（2+1-αα）θn.

（21）

由引理3.1知λn極限存在，那么有

limn→∞（1-μλnλn+1）=1-μgt;0，

其中μ∈（0，1）.

對任意的c∈（0，α（1-μ）），存在正整數N1，使得當ngt;N1時，有

αn（1-μλnλn+1）gt;cgt;0.

（22）

故當ngt;N1時，可知

n≥0，

那么根據式（22）可知

‖xn+1-p‖2≤‖xn-p‖2+σn[‖xn-p‖2-‖xn-1-p‖2]+φn， ngt;N1.

（23）

由αn和ξn的定義可知

∑∞n=0αn（‖yn-1-yn‖2+‖xn-1-xn‖2）≤∑∞n=0ξnlt;+∞，

（24）

進一步可知

∑∞n=0αn‖yn-1-yn‖2lt;+∞，

（25）

∑∞n=0αn‖xn-1-xn‖2lt;+∞.

（26）

根據引理3.1可知λn有界，即存在m2gt;m1gt;0，使得λn∈[m1，m2]，再由式（25）可知

∑∞n=0μαnλnλn+1‖yn-1-yn‖2≤μm2m1∑∞n=0αn‖yn-1-yn‖2lt;+∞，

（27）

且有

limn→∞μαnλnλn+1‖yn-1-yn‖2=0.

（28）

根據式（21）和（26）可知

∑∞n=0ρn‖xn-xn-1‖2≤

（2+1-αα）∑∞n=0θn‖xn-xn-1‖2≤

（2+1-αα）∑∞n=0αnαn‖xn-xn-1‖2≤

（2+1-αα）∑∞n=0αnα‖xn-xn-1‖2=

（2α+1-αα2）∑∞n=0αn‖xn-xn-1‖2lt;+∞，

（29）

其中，第1個不等式由式（21）可得，第2個不等式是由θn≤1可得，第3個不等式是由α≤αn≤可得，第4個不等式是由式（26）可得，

并且有

limn→∞ρn‖xn-xn-1‖2=0.

（30）

由式（19）、（27）和（29）可知

∑∞n=0φn=∑∞n=0ρn‖xn-xn-1‖2+∑∞n=0μαnλnλn+1‖yn-1-yn‖2lt;+∞，

（31）

且有

limn→∞φn=0.

（32）

結合式（23）和（31），根據引理2.2可知limn→∞‖xn-p‖2存在，因此序列{xn}有界的，故結論（a）和（b）成立.由式（17）可知

n≤‖xn-p‖2-‖xn+1-p‖2+

σn[‖xn-p‖2-‖xn-1-p‖2]+φn，

（33）

上式兩邊同時取極限可以得到

limn→∞n=0.

由條件（C6）和式（22）可知

limn→∞‖xn+1-xn‖2=0， limn→∞‖yn-wn‖2=0，

limn→∞‖yn-un‖2=0.

（34）

由wn的定義和θn的取值范圍，可知

‖wn-xn‖=θn‖xn-xn-1‖≤‖xn-xn-1‖→0， n→∞.

（35）

因此，有

limn→∞‖wn-xn‖2=0.

（36）

又因為

limn→∞‖xn+1-xn‖2=0，

limn→∞‖yn-wn‖2=0，

可以得到

limn→∞‖yn-xn‖2=0，

limn→∞‖yn-yn-1‖2=0.

（37）

由式（34）、（36）和（37）可以推出結論（c）成立.

引理 3.3

在（C1）～（C4）和（C6）條件下，設{xn}是由算法1生成的序列，x*為{xn}的任一弱聚點，則x*∈C，并且有F（x*）=0或x*∈SD.

證明

已知{xn}有界，由引理3.2（c）知{yn}有界，設{xnk}和{ynk}分別為{xn}與{yn}的弱收斂子列，并且{xnk}弱收斂到x*.由引理3.2（c）可知limk→∞‖xnk-ynk‖2=0成立，可得ynk弱收斂到x*.由于{yn}C，且C為H中的非空閉凸子集，故有x*∈C.

下面分2種情況進行討論.

情形 1

當lim supk→∞‖F（ynk）‖=0時，有

limk→∞‖F（ynk）‖=lim infk→∞‖F（ynk）‖=0.

由于ynkx*∈C，k→∞并且映射F在C上序列弱連續，可以知道F（ynk）F（x*），k→∞.再由范數映射是弱下半連續的，可得

0≤‖F（x*）‖≤lim infk→∞‖F（ynk）‖=0.

因此，可得出F（x*）=0.

情形 2

當lim supk→∞‖F（ynk）‖gt;0時，那么存在一個常數K∈N，使得‖F（ynk）‖gt;0.

因ynk-1∈Tn，x∈C有

〈wnk-λnkF（ynk-1）-ynk，x-ynk〉≤0，

并且λnkgt;0，因此上式等價于

1λnk〈wnk-ynk，x-ynk〉≤〈F（ynk-1），x-ynk〉，

進一步有

1λnk〈wnk-ynk，x-ynk〉-〈F（ynk-1）-F（ynk），x-ynk〉≤〈F（ynk），x-ynk〉.

（38）

由引理3.1和引理3.2（c）可知，當k→∞時，有λnk→λ，‖wnk-ynk‖2→0.根據前面假設可知{ynk}是{yn}的弱收斂子列，則{ynk}是有界的，又因為映射F是Lipschitz連續的，故{F（ynk）}也是有界的.由引理3.2（c）可知，當k→∞時，有‖ynk-ynk-1‖→0，再由映射F是Lipschitz連續的，從而有

‖F（ynk）-F（ynk-1）‖→0， k→∞.

在式（38）的兩邊同時取下極限，有

0≤lim infk→∞〈F（ynk），x-ynk〉≤lim supk→∞〈F（ynk），x-ynk〉.

（39）

當lim supk→∞〈F（ynk），x-ynk〉gt;0時，則{ynk}存在子列{ynki}滿足

limi→∞〈F（ynki），x-ynki〉gt;0，

那么存在正整數N2使得

〈F（ynki），x-ynki〉gt;0， i≥N2.

再由映射F是擬單調的和序列{ynki}弱收斂到x*，可得

〈F（x），x-x*〉≥0， x∈C.

當lim supk→∞〈F（ynk），x-ynk〉=0時，根據式（39）可以推出lim infk→∞〈F（ynk），x-ynk〉=0，那么有

limk→∞〈F（ynk），x-ynk〉=0.

因此，設

k：=|〈F（ynk），x-ynk〉|+1k， k=1，2，…，

那么有

〈F（ynk），x-ynk〉+kgt;0.

令vk=F（ynk）‖F（ynk）‖2，那么〈F（ynk），vk〉=1，

可得

〈F（yk），x-yk+kvk〉gt;0， kgt;K.

由于映射F是擬單調的，根據擬單調的定義可知

〈F（x-kvk），x+kvk-ynk〉≥0， kgt;K，

等價于

〈F（x），x-ynk〉≥〈F（x）-F（x-kvk），

x+kvk-ynk〉-

〈F（x），kvk〉， kgt;K.

（40）

下面說明limk→∞kvk=0.

因為映射F是序列弱連續的，并且{ynk}弱收斂到x*，所以{F（ynk）}弱收斂到F（x*）.

再由范數映射的弱下半連續性可知

0≤‖F（x*）‖≤lim infk→∞‖F（ynk）‖.

由k的定義可知limkk→∞=0，那么

0≤lim supk→∞‖kvnk‖=lim supk→∞k‖F（ynk）‖≤lim supk→∞klim infk→∞‖F（ynk）‖=0.

這意味著lim supk→∞‖kvk‖=0，因此limk→∞kvk=0.

在式（40）兩邊同時取下極限有

lim infk→∞〈F（x），x-x*〉≥0， x∈C，

因此可得

〈F（x），x-x*〉=limk→∞〈F（x），x-ynk〉=lim infk→∞〈F（x），x-ynk〉≥0， x∈C，

所以有x*∈SD.

引理 3.4

在（C1）～（C6）的條件下，由算法1產生的序列{xn}只有有限個弱聚點，且所有的弱聚點均在S中.

證明

先證明在SD中至多有一個弱聚點.

假設{xnj}為{xn}的另一收斂子列，當j→∞時，有xnj，并且≠x*，根據引理3.3可知∈SD.

再由引理2.3和引理3.2（b），有

limn→∞‖xn-‖=limj→∞‖xnj-‖=

lim infj→∞‖xnj-‖lt;lim infj→∞‖xnj-x*‖=

limn→∞‖xn-x*‖=lim infk→∞‖xnk-x*‖lt;

lim infk→∞‖xnk-‖=limn→∞‖xn-‖.

產生矛盾！因此整個序列{xn}在SD中至多有一個弱聚點.由于A={z∈C：F（z）=0}＼SD是一個有限集，再由引理3.3，可知序列{xn}在S中有有限的弱聚點.

定理 3.1

在（C1）～（C6）條件下，算法1生成的序列{xn}弱收斂到S的中的一點.

證明

由引理3.4知序列{xn}在S中有有限的弱聚點.設{xink}為{xn}的子列，使得當k→∞時，有xinkxi，i=1，2，…，m，其中x1，x2，…，xm為{xn}的弱聚點，那么有

limk→∞〈xink，xi-xj〉=〈xi，xi-xj〉， i≠j.

（41）

由i≠j可知‖xi-xj‖≠0，那么

〈xi，xi-xj‖xi-xj‖〉=〈xi，xi-xj〉‖xi-xj‖=

‖xi‖2-〈xi，xj〉‖xi-xj‖=

1‖xi-xj‖[‖xi‖2-12‖xi‖2-12‖xj‖2+12‖xi-xj‖2]=

‖xi‖2-‖xj‖22‖xi-xj‖+12‖xi-xj‖gt;

‖xi‖2-‖xj‖22‖xi-xj‖+14‖xi-xj‖.

（42）

由式（41）和（42）可知

limk→∞〈xink，xi-xj‖xi-xj‖〉gt;

‖xi‖2-‖xj‖22‖xi-xj‖+14‖xi-xj‖.

（43）

對充分大的k，可得

xink∈{x：〈x，xi-xj‖xi-xj‖〉gt;‖xi‖2-‖xj‖22‖xi-xj‖+14‖xi-xj‖}.

（44）

因此，存在正整數N3gt;N1，使得

xink∈Bi=∩mj=1，j≠i{x：〈x，xi-xj‖xi-xj‖〉gt;

‖xi‖2-‖xj‖22‖xi-xj‖+ε0}， ngt;N3，

（45）

其中

ε0=min{14‖xi-xj‖：i=1，2，…，m;

j=1，2，…，m;i≠j}.

由引理3.2（c）可知limn→∞‖xn+1-xn‖=0，那么可知存在正整數N4gt;N3gt;N1，使得

‖xn+1-xn‖lt;ε0， ngt;N4.

（46）

接下來將證明{xn}在S中僅有一個弱聚點.

假設序列{xn}在S中至少有2個弱聚點，那么存在正整數N5gt;N4gt;N3gt;N1，使得xN5∈Bi并有xN5+1∈Bj，其中

Bj=∩mi=1，j≠i{x：〈-x，xi-xj‖xi-xj‖〉gt;-‖xi‖2-‖xj‖22‖xi-xj‖+ε0}，

i，j∈{1，2，…，m}， mgt;2.

（47）

再由式（46）可知

‖xN5+1-xN5‖lt;ε0.

（48）

由于xN5∈Bi，xN5+1∈Bj，可得

〈xN5，xi-xj‖xi-xj‖〉gt;‖xi‖2-‖xj‖22‖xi-xj‖+ε0，

（49）

〈-xN5+1，xi-xj‖xi-xj‖〉gt;-‖xi‖2-‖xj‖22‖xi-xj‖+ε0.

（50）

將式（49）與（50）相加，再根據式（48），可得

2ε0lt;〈xN5-xN5+1，xi-xj‖xi-xj‖〉≤‖xN5-xN5+1‖lt;ε0，

（51）

產生矛盾.于是可知{xn}在S中僅有一個弱聚點.因此，序列{xn}弱收斂到S中一點.

當映射F滿足文獻[27]中所提的強擬單調時，可以得到算法1在Hilbert空間中的強收斂定理.假設有下述條件成立：

條件 （C7）

映射F：H→H是強擬單調映射，即：存在ηgt;0，使得

〈F（x），y-x〉gt;0〈F（y），y-x〉≥η‖y-x‖2， x，y∈C.

注 3.4

當映射F是強偽單調時，映射F也是強擬單調的，反之則不成立，并且根據強擬單調的定義可知，強擬單調的映射也是擬單調的.

定理 3.2

在條件（C1）～（C3），（C5）～（C7）下，算法1生成的序列{xn}強收斂到解x*∈S.

證明

設x*是解集S中的一點，由條件（C7）可以得到

〈Fyn，yn-x*〉≥η‖yn-x*‖2，

ηgt;0是一個常數.將un代入后，有

〈F（yn），yn-un+un-x*〉≥η‖yn-x*‖2，

移項后可以得到

〈F（yn），x*-un〉≤-η‖yn-x*‖2+〈F（yn），yn-un〉.

（52）

再根據引理2.1（ii）有

‖un-x*‖2≤

‖wn-λnF（yn）-x*‖2-

‖wn-λnF（yn）-un‖2≤

‖wn-x*‖2-‖wn-un‖2+2λn〈F（yn），x*-un〉≤

‖wn-x*‖2-‖wn-un‖2+2λn〈F（yn），yn-un〉-2λnη‖yn-x*‖2≤

‖wn-x*‖2-‖wn-yn‖2-‖yn-un‖2+

2〈yn+λnF（yn）-wn，yn-un〉-2λnη‖yn-x*‖2=

‖wn-x*‖2-‖wn-yn‖2-‖yn-un‖2-

2λnη‖yn-x*‖2+

2〈yn+λnF（yn-1）-wn，yn-un〉+

2λn〈F（yn-1）-F（yn），un-yn〉≤

‖wn-x*‖2-‖wn-yn‖2-

‖yn-un‖2-2λnη‖yn-x*‖2+

2λn〈F（yn-1）-F（yn），un-yn〉，

（53）

其中，第1個不等式由引理2.1（ii）可得，第2個不等式由范數的性質可得，第3個不等式由條件（C7）可得，第4個不等式由范數的性質可得，最后一個不等式由un∈Tn可得.

令p=x*，由式（12）、（14）和（53）可知

‖un-x*‖2≤（1+θn）‖xn-x*‖2-θn‖xn-1-x*‖2+θn（1+θn）‖xn-xn-1‖2-

‖wn-yn‖2-‖yn-un‖2-2λnη‖yn-x*‖2+

μλnλn+1（‖yn-1-yn‖2+‖un-yn‖2）.

（54）

將式（9）、（15）和（54）代入式（8）有

‖xn+1-x*‖2≤

‖xn-x*‖2+

σn[‖xn-x*‖2-‖xn-1-x*‖2]+

ρn‖xn-xn-1‖2-

（1-αn）（1-δn）αn‖xn+1-xn‖2+

μαnλnλn+1‖yn-1-yn‖2-

‖yn-wn‖2-

αn（1-μλnλn+1）‖yn-un‖2-

2αnλnη‖yn-x*‖2，

（55）

進一步有

2αnλnη‖yn-x*‖2≤

‖xn-x*‖2-‖xn+1-x*‖2+σn[‖xn-x*‖2-‖xn-1-x*‖2]+

ρn‖xn-xn-1‖2-（1-αn）（1-δn）αn‖xn+1-xn‖2+

μαnλnλn+1‖yn-1-yn‖2-

‖yn-wn‖2-

αn（1-μλnλn+1）‖yn-un‖2.

（56）

由式（22）可知，當ngt;N1時，有αn（1-μλnλn+1）gt;0成立，并且由αn和δn的取值范圍可知（1-αn）（1-δn）αngt;0，因此有ngt;N1

2αnλnη‖yn-x*‖2≤

‖xn-x*‖2-‖xn+1-x*‖2+

σn[‖xn-x*‖2-‖xn-1-x*‖2]+

ρn‖xn-xn-1‖2+μαnλnλn+1‖yn-1-yn‖2.

（57）

由引理3.2（b）可知limn→∞‖xn-x*‖2存在，根據假設條件（C6）可知σn是有界的.結合式（28）和（30）可得

limn→∞ρn‖xn-xn-1‖2=0，limn→∞μαnλnλn+1‖yn-1-yn‖2=0.

對式（57）右側取極限，有

2αnλnη‖yn-x*‖2≤

‖xn-x*‖2-‖xn+1-x*‖2+σn[‖xn-x*‖2-‖xn-1-x*‖2]+

ρn‖xn-xn-1‖2+μαnλnλn+1‖yn-1-wn‖2→0， n→∞.

（58）

由αn和λn的定義可知

αnλnη‖yn-x*‖2≥αm1η‖yn-x*‖2≥0，

因此有

limn→∞‖yn-x*‖2=0.

根據引理3.2（c）可知

limn→∞‖yn-xn‖2=0，

可得

limn→∞‖xn-x*‖2=0.

所以有xn→x*，n→∞，完成了這一證明.

4 算法的計算機檢驗

本節計算機檢驗的結果都是用MATLAB在CPU型號為Intel（R） Core（TM） i7-8565U（8核，主頻1.8 GHz）和內存為16 GB的筆記本電腦上運行的.選取‖yn-xn‖≤作為算法的停止標準，用T記算法CPU運行所花費時間，用I記迭代次數.

例 1

考慮一個映射F：R2→R2，其中

z=（x，y），

F（z）=（x+y+ex，-x+y+ey）.

可行集定義為C={（x，y）∈R2：x2+y2≤1}.

注 4.1

容易驗證例1中的映射F在集合C上是單調Lipschitz連續的.

在本例中，將文獻[10]中的算法1（記為Alg.M）、文獻[11]中的算法3.1（記為Alg.G）、文獻[18]中的算法1（記為Alg.Y）和本文中的算法1（記為Alg.1）進行比較.各算法的參數選取如下：

1） Alg.M的參數選取：λ=13.01L，L為Lipschitz常數.

2） Alg.G的參數選取：λ=15L，θ=0.4.

3） Alg.Y的參數選取：λ0=1.1，μ=0.9，θn=0.9，αn=0.33，δ=0.000 2.

4） Alg.1的參數選取：λ0=1.1，μ=0.9，θn=0.9，ξn=1n2，=0.33，δn=0.000 2，dn=10（1+n）1.1.

5） Alg.1*表示Alg.1的參數選取：λ0=1.1，μ=0.9，θ0=δ0=0.9，θn=αn，ξn=1n2，=0.9，δn=0.15θn，dn=10（1+n）1.1.

注 4.2

將Alg.M、Alg.G、Alg.Y和本文中的Alg.1對本例進行數值實驗，可發現：本文的Alg.1所需的迭代次數和運行時間都要明顯少于以上3個算法.

例 2

設C=[-1，1]，

F（x）=

2x-1， xgt;1，

x2， x∈[-1，1]，

-2x-1， xlt;-1.

在本例中，將文獻[17]中的算法3.3（記為Alg.L）、文獻[16]中的算法3.4（記為Alg.O）和本文中的算法1（記為Alg.1）進行比較.各算法的參數選取如下：

1） Alg.L的參數選取：λ0=1.1，μ=0.9，dn=1（1+n）1.1.

2） Alg.O的參數選取：λ0=1.1，μ=0.9，θn=3n+110n+5，αn=1，dn=1（1+n）1.1.

3） Alg.1的參數選取：λ0=1.1，μ=0.9，θ0=δ0=0.2，θn=3n+110n+5，ξn=1n2，=0.99，δn=3n+110n+5，dn=1（1+n）1.1.

4） Alg.1*表示Alg.1的參數選取：λ0=1.1，μ=0.9，θ0=δ0=0.9，θn=αn，ξn=1n2，=0.9，δn=0.15θn，dn=10（1+n）1.1.

注 4.3

例2中映射F是擬單調Lipschitz連續的，并且有SD={-1}，S={-1，0}，本例中Alg.M、Alg.G和Alg.Y不再適用.將Alg.L、Alg.O和本文中的Alg.1，對本例進行數值實驗，可發現：本文的Alg.1所需的迭代次數和運行時間都要明顯少于以上2個算法.

參考文獻

[1]FACCHINEI F， PANG J S. Finite-dimensional variational inequalities and complementarity problems[M]. New York： Springer，2003.

[2] HARKER P T. A variational inequality approach for the determination of oligopolistic market equilibrium[J]. Mathematical Programming，1984，30（1）：105-111.

[3] IUSEM A N， SVAITER B F. A variant of Korpelevich’s method for variational inequalities with a new search strategy[J]. Optimization，1997，42（4）：309-321.

[4] 賈倩倩，高興慧. 變分不等式問題不動點問題和零點問題的公共元的強收斂定理[J]. 貴州師范大學學報（自然科學版），2020，38（05）：39-44.

[5] COTTLE R W， YAO J C. Pseudo-monotone complementarity problems in Hilbert space[J]. Journal of Optimization Theory and Applications，1992，75（2）：281-295.

[6] GOLDSTEIN A A. Convex programming in Hilbert space[J]. Bulletin of the American Mathematical Society，1964，70（5）：709-710.

[7] KORPELEVICH G M. An extragradient method for finding saddle points and for other problems[J]. Matecon，1976，12：747-756.

[8] POPOV L D. A modification of the Arrow-Hurwicz method for search of saddle points[J]. Mathematical Notes of the Academy of Sciences of the USSR，1980，28（5）：845-848.

[9] CENSOR Y， GIBALI A， REICH S. The subgradient extragradient method for solving variational inequalities in Hilbert space[J]. Journal of Optimization Theory and Applications，2011，148（2）：318-335.

[10]MALITSKY Y V， SEMENOV V V. An extragradient algorithm for monotone variational inequalities[J]. Cybernetics and Systems Analysis，2014，50（2）：271-277.

[11] GIBALI A， VAN HIEU D. A new inertial double-projection method for solving variational inequalities[J]. Journal of Fixed Point Theory and Applications，2019，21（4）：97.

[12] POLYAK B T. Introduction to optimization[M]. New York： Optimization Software Publications Division，1987.

[13] ATTOUCH H， CABOT A. Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions[J]. Applied Mathematics amp; Optimization，2019，80（3）：547-598.

[14] XIA Y， WANG J. A general methodology for designing globally convergent optimization neural networks[J]. IEEE Transactions on Neural Networks，1998，9（6）：1331-1343.

[15] ATTOUCH H， CABOT A. Convergence of a relaxed inertial proximal algorithm for maximally monotone operators[J]. Mathematical Programming，2020，184（1）：243-287.

[16]OGWO G N， IZUCHUKWU C， SHEHU Y， et al. Convergence of relaxed inertial subgradient extragradient methods for quasimonotone variational inequality problems[J]. Journal of Scientific Computing，2021，90（1）：10.

[17]LIU H W， YANG J. Weak convergence of iterative methods for solving quasimonotone variational inequalities[J]. Computational Optimization and Applications，2020，77（2）：491-508.

[18] YAO Y H， IYIOLA O S， SHEHU Y. Subgradient extragradient method with double inertial steps for variational inequalities[J]. Journal of Scientific Computing，2022，90（2）：71.

[19]陳林，葉明露. 求解偽單調變分不等式的一種自適應投影算法[J]. 四川師范大學學報（自然科學版），2023，46（4）：503-511.

[20] 楊澈洲，賀月紅，龍憲軍. 求解單調變分不等式的新次梯度外梯度算法[J]. 四川師范大學學報（自然科學版），2022，45（6）：766-771.

[21] 楊志，夏福全. 變分不等式的慣性次梯度外梯度算法[J]. 四川師范大學學報（自然科學版），2023，46（5）：591-600.

[22] WANG Z B， CHEN X， YI J， et al. Inertial projection and contraction algorithms with larger step sizes for solving quasimonotone variational inequalities[J]. Journal of Global Optimization，2022，82（3）：499-522.

[23] GOEBEL K， REICH S. Uniform convexity， hyperbolic geometry， and nonexpansive mappings[M]. New York： Marcel Dekker，1984.

[24] MAING P E. Convergence theorems for inertial KM-type algorithms[J]. Journal of Computational and Applied Mathematics，2008，219（1）：223-236.

[25] OPIAL Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings[J]. Bulletin of the American Mathematical Society，1967，73（4）：591-597.

[26] YE M L， HE Y R. A double projection method for solving variational inequalities without monotonicity[J]. Computational Optimization and Applications，2015，60（1）：141-150.

[27] WANG Z B， SUNTHRAYUTH P， ADAMU A， et al. Modified accelerated Bregman projection methods for solving quasi-monotone variational inequalities[J]. Optimization，2024，73（7）：2053-2087.

A New Double Inertial Subgradient Extragradient Algorithm for

Quasi-monotone Variational Inequalities

LI Zhuo， XIA Fuquan

（School of Mathematical Sciences， Sichuan Normal University， Chengdu 610066， Sichuan）

In this paper， we introduce a double inertial subgradient extragradient algorithm for solving quasi-monotone variational inequality problems in real Hilbert space. The advantage of this algorithm is that each iteration only calculates the mapping value once and the projection to the feasible set once， and combines the double inertial and relaxation techniques to improve the convergence speed of the subgradient extragradient method for solving variational inequality problems. Under the condition that the mapping is quasi-monotone and Lipschitz continuous， where the solution set of dual variational inequalities is non-empty， the weak convergence results of the algorithm are established. At the same time， the strong convergence results in Hilbert space are obtained under the assumption of strong quasi-monotone mapping. Finally， numerical experiments show the effectiveness of the algorithm.

variational inequality; quasi-monotone; subgradient extragradient algorithm; double inertial acceleration

2020 MSC：47J20; 49J40; 65K15; 90C25

（編輯 陶志寧）