擬單調(diào)變分不等式的新雙慣性次梯度外梯度算法

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

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

O178; O221

A

0406-11

03.012

1 引言及研究背景

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

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

（1）

其中，C是H中的一個(gè)非空閉凸子集，F(xiàn)：H→H是一個(gè)映射.記問題（1）的解集為S.該問題在優(yōu)化理論、非線性分析、微分方程等領(lǐng)域發(fā)揮著重要的作用^[1-4].

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

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

（2）

記問題（2）的解集為SD.由文獻(xiàn)[5]引理2.1易知，當(dāng)映射F是連續(xù)并且集合C是凸集時(shí)，SDS.當(dāng)映射F是偽單調(diào)和連續(xù)時(shí)，SD=S.

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

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

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

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為偽單調(diào)Lipschitz連續(xù)的假設(shè)條件下，在Hilbert空間中建立了算法（3）的弱收斂性結(jié)果.在映射F為強(qiáng)偽單調(diào)的條件下，得到算法（3）在Hilbert空間中的強(qiáng)收斂定理.最后在一些附加假設(shè)下，得到了算法（3）特殊情況下線性收斂率的結(jié)果.

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

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

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

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

2 預(yù)備知識(shí)

本節(jié)回憶一些基本的定義及結(jié)論.

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

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

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

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

其中，λ是任意的正實(shí)數(shù).

與文獻(xiàn)[18，22]中定義2.1類似，有以下定義.

定義 2.1

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

（i） 強(qiáng)單調(diào)的，若存在γgt;0，使得

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

（ii） 單調(diào)的，若

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

（iii） 強(qiáng)偽單調(diào)的，若存在ηgt;0，使得

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

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

（iv） 偽單調(diào)的，若

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

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

（v） 擬單調(diào)的，若

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

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

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

引理 2.1^[23]

設(shè)CH是一個(gè)非空閉凸集，下列結(jié)論成立：

（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是一個(gè)常數(shù)，則

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

（4）

引理 2.2^[24]

設(shè)非負(fù)的實(shí)序列{sn}、{tn}和{γn}，滿足n≥1，

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

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

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

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

引理 2.3^[25]

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

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

（ii） {xn}的所有弱聚點(diǎn)都在C中，

則{xn}弱收斂到集合C中一點(diǎn).

命題 2.1^[26]

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

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

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

（iii） 映射F在C上是擬單調(diào)的，F(xiàn)≠0，并且集合C是有界集;

（iv） 映射F在C上是擬單調(diào)的，F(xiàn)≠0，并且存在一個(gè)正實(shí)數(shù)r，使得對于x∈C滿足‖x‖≥r，都存在y∈C，使得‖y‖≤r和〈F（x），y-x〉≤0;

（v） 映射F在C上是擬單調(diào)的，集合C的內(nèi)部非空，且存在F（x*）≠0，

則SD是非空的.

3 算法及收斂性分析

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

算法 1

初始

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

∑∞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）.

設(shè)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：計(jì)算

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

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

Step 3：計(jì)算

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(xiàn)（yn）-F（yn-1）‖，λn+dn}，

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

λn+dn， 其他.

（7）

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

注 3.1

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

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

條件 （C1） SD非空;

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

‖F(xiàn)（x）-F（y）‖≤L‖x-y‖， x，y∈H;

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

當(dāng){xn}弱收斂到x時(shí)，有{F（xn）}弱收斂F（x）;

（C4） 映射F：H→H是擬單調(diào)映射;

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

（C6） 選取實(shí)數(shù)序列滿足下述條件：

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

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

注 3.2

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

為了書寫簡便，記

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

先證明一些引理.

引理 3.1

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

引理 3.1的證明見文獻(xiàn)[17]引理3.1.

注 3.3

自適應(yīng)步長序列λn是非單調(diào)的，使算法減小了對初始步長λ0的依賴.λn在迭代中可以是逐步增大的，但是當(dāng)n比較大時(shí)，步長序列λn可能是非增的.原因是∑∞n=0dn=dlt;∞，那么有l(wèi)imn→∞"" dn=0.

引理 3.2

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

（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.

證明

根據(jù)算法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個(gè)不等式是由引理2.1（ii）可得，第2個(gè)不等式是由式（10）可得，第3個(gè)不等式是由un∈Tn可得.

當(dāng)F（yn）≠F（yn-1）時(shí)，根據(jù){λn}的定義，有

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

2λn‖F(xiàn)（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個(gè)不等式是由Cauchy-Schwarz不等式可得，第2個(gè)不等式是由λn的定義可得，第3個(gè)不等式是因?yàn)?/p>

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

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

當(dāng)F（yn）=F（yn-1）時(shí)，式（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個(gè)不等式由Cauchy-Schwarz不等式可得，第2個(gè)不等式成立是因?yàn)?/p>

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）

進(jìn)一步，式（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-μ）），存在正整數(shù)N1，使得當(dāng)ngt;N1時(shí)，有

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

（22）

故當(dāng)ngt;N1時(shí)，可知

n≥0，

那么根據(jù)式（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）

進(jìn)一步可知

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

（25）

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

（26）

根據(jù)引理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）

根據(jù)式（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個(gè)不等式由式（21）可得，第2個(gè)不等式是由θn≤1可得，第3個(gè)不等式是由α≤αn≤可得，第4個(gè)不等式是由式（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）

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

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

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

（33）

上式兩邊同時(shí)取極限可以得到

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）

又因?yàn)?/p>

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）可以推出結(jié)論（c）成立.

引理 3.3

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

證明

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

下面分2種情況進(jìn)行討論.

情形 1

當(dāng)lim supk→∞‖F(xiàn)（ynk）‖=0時(shí)，有

limk→∞‖F(xiàn)（ynk）‖=lim infk→∞‖F(xiàn)（ynk）‖=0.

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

0≤‖F(xiàn)（x*）‖≤lim infk→∞‖F(xiàn)（ynk）‖=0.

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

情形 2

當(dāng)lim supk→∞‖F(xiàn)（ynk）‖gt;0時(shí)，那么存在一個(gè)常數(shù)K∈N，使得‖F(xiàn)（ynk）‖gt;0.

因ynk-1∈Tn，x∈C有

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

并且λnkgt;0，因此上式等價(jià)于

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

進(jìn)一步有

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

（38）

由引理3.1和引理3.2（c）可知，當(dāng)k→∞時(shí)，有λnk→λ，‖wnk-ynk‖2→0.根據(jù)前面假設(shè)可知{ynk}是{yn}的弱收斂子列，則{ynk}是有界的，又因?yàn)橛成銯是Lipschitz連續(xù)的，故{F（ynk）}也是有界的.由引理3.2（c）可知，當(dāng)k→∞時(shí)，有‖ynk-ynk-1‖→0，再由映射F是Lipschitz連續(xù)的，從而有

‖F(xiàn)（ynk）-F（ynk-1）‖→0， k→∞.

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

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

（39）

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

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

那么存在正整數(shù)N2使得

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

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

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

當(dāng)lim supk→∞〈F（ynk），x-ynk〉=0時(shí)，根據(jù)式（39）可以推出lim infk→∞〈F（ynk），x-ynk〉=0，那么有

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

因此，設(shè)

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

那么有

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

令vk=F（ynk）‖F(xiàn)（ynk）‖2，那么〈F（ynk），vk〉=1，

可得

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

由于映射F是擬單調(diào)的，根據(jù)擬單調(diào)的定義可知

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

等價(jià)于

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

x+kvk-ynk〉-

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

（40）

下面說明limk→∞kvk=0.

因?yàn)橛成銯是序列弱連續(xù)的，并且{ynk}弱收斂到x*，所以{F（ynk）}弱收斂到F（x*）.

再由范數(shù)映射的弱下半連續(xù)性可知

0≤‖F(xiàn)（x*）‖≤lim infk→∞‖F(xiàn)（ynk）‖.

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

0≤lim supk→∞‖kvnk‖=lim supk→∞k‖F(xiàn)（ynk）‖≤lim supk→∞klim infk→∞‖F(xiàn)（ynk）‖=0.

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

在式（40）兩邊同時(shí)取下極限有

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產(chǎn)生的序列{xn}只有有限個(gè)弱聚點(diǎn)，且所有的弱聚點(diǎn)均在S中.

證明

先證明在SD中至多有一個(gè)弱聚點(diǎn).

假設(shè){xnj}為{xn}的另一收斂子列，當(dāng)j→∞時(shí)，有xnj，并且≠x*，根據(jù)引理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-‖.

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

定理 3.1

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

證明

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

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）

因此，存在正整數(shù)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，那么可知存在正整數(shù)N4gt;N3gt;N1，使得

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

（46）

接下來將證明{xn}在S中僅有一個(gè)弱聚點(diǎn).

假設(shè)序列{xn}在S中至少有2個(gè)弱聚點(diǎn)，那么存在正整數(shù)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）相加，再根據(jù)式（48），可得

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

（51）

產(chǎn)生矛盾.于是可知{xn}在S中僅有一個(gè)弱聚點(diǎn).因此，序列{xn}弱收斂到S中一點(diǎn).

當(dāng)映射F滿足文獻(xiàn)[27]中所提的強(qiáng)擬單調(diào)時(shí)，可以得到算法1在Hilbert空間中的強(qiáng)收斂定理.假設(shè)有下述條件成立：

條件 （C7）

映射F：H→H是強(qiáng)擬單調(diào)映射，即：存在ηgt;0，使得

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

注 3.4

當(dāng)映射F是強(qiáng)偽單調(diào)時(shí)，映射F也是強(qiáng)擬單調(diào)的，反之則不成立，并且根據(jù)強(qiáng)擬單調(diào)的定義可知，強(qiáng)擬單調(diào)的映射也是擬單調(diào)的.

定理 3.2

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

證明

設(shè)x*是解集S中的一點(diǎn)，由條件（C7）可以得到

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

ηgt;0是一個(gè)常數(shù).將un代入后，有

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

移項(xiàng)后可以得到

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

（52）

再根據(jù)引理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個(gè)不等式由引理2.1（ii）可得，第2個(gè)不等式由范數(shù)的性質(zhì)可得，第3個(gè)不等式由條件（C7）可得，第4個(gè)不等式由范數(shù)的性質(zhì)可得，最后一個(gè)不等式由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）

進(jìn)一步有

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）可知，當(dāng)ngt;N1時(shí)，有α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存在，根據(jù)假設(shè)條件（C6）可知σn是有界的.結(jié)合式（28）和（30）可得

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

對式（57）右側(cè)取極限，有

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.

根據(jù)引理3.2（c）可知

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

可得

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

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

4 算法的計(jì)算機(jī)檢驗(yàn)

本節(jié)計(jì)算機(jī)檢驗(yàn)的結(jié)果都是用MATLAB在CPU型號為Intel（R） Core（TM） i7-8565U（8核，主頻1.8 GHz）和內(nèi)存為16 GB的筆記本電腦上運(yùn)行的.選取‖yn-xn‖≤作為算法的停止標(biāo)準(zhǔn)，用T記算法CPU運(yùn)行所花費(fèi)時(shí)間，用I記迭代次數(shù).

例 1

考慮一個(gè)映射F：R2→R2，其中

z=（x，y），

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

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

注 4.1

容易驗(yàn)證例1中的映射F在集合C上是單調(diào)Lipschitz連續(xù)的.

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

1） Alg.M的參數(shù)選?。害?13.01L，L為Lipschitz常數(shù).

2） Alg.G的參數(shù)選?。害?15L，θ=0.4.

3） Alg.Y的參數(shù)選?。害?=1.1，μ=0.9，θn=0.9，αn=0.33，δ=0.000 2.

4） Alg.1的參數(shù)選?。害?=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的參數(shù)選?。害?=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對本例進(jìn)行數(shù)值實(shí)驗(yàn)，可發(fā)現(xiàn)：本文的Alg.1所需的迭代次數(shù)和運(yùn)行時(shí)間都要明顯少于以上3個(gè)算法.

例 2

設(shè)C=[-1，1]，

F（x）=

2x-1， xgt;1，

x2， x∈[-1，1]，

-2x-1， xlt;-1.

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

1） Alg.L的參數(shù)選?。害?=1.1，μ=0.9，dn=1（1+n）1.1.

2） Alg.O的參數(shù)選?。害?=1.1，μ=0.9，θn=3n+110n+5，αn=1，dn=1（1+n）1.1.

3） Alg.1的參數(shù)選?。害?=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的參數(shù)選取：λ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是擬單調(diào)Lipschitz連續(xù)的，并且有SD={-1}，S={-1，0}，本例中Alg.M、Alg.G和Alg.Y不再適用.將Alg.L、Alg.O和本文中的Alg.1，對本例進(jìn)行數(shù)值實(shí)驗(yàn)，可發(fā)現(xiàn)：本文的Alg.1所需的迭代次數(shù)和運(yùn)行時(shí)間都要明顯少于以上2個(gè)算法.

參考文獻(xiàn)

[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] 賈倩倩，高興慧. 變分不等式問題不動(dòng)點(diǎn)問題和零點(diǎn)問題的公共元的強(qiáng)收斂定理[J]. 貴州師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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]陳林，葉明露. 求解偽單調(diào)變分不等式的一種自適應(yīng)投影算法[J]. 四川師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，46（4）：503-511.

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

[21] 楊志，夏福全. 變分不等式的慣性次梯度外梯度算法[J]. 四川師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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

（編輯 陶志寧）