求解擬單調變分不等式的交替慣性自適應算法

楊文憶，葉明露

(西華師范大學 數學與信息學院，四川 南充 637009)

令H為實的希爾伯特空間，C?H為一個非空閉凸集，F：H→H為給定的一個連續映射。〈·，·〉和‖·‖分別表示H的內積和范數。變分不等式指的是：找到x*∈C，滿足

〈F(x*)，y-x*〉≥0,?y∈C。

(1)

令S為(1)的解集，SD為問題(1)的Minty解集，即：SD={x*∈C|〈F(y),y-x*〉≥0,?y∈C}。因為F在C上是連續的，且C是閉凸集，故有

SD?S，

(2)

若F是一個偽單調的連續映射，則有S?SD。因此有S=SD[2]。若F是一個擬單調的連續映射，則存在S≠SD的例子，參見Ye與He[3]文章中的例4.2。

變分不等式問題是優化理論的一個基本問題，因此求解變分不等式問題的方法受到了廣泛的關注。在1976年，Korpelevich[4]就提出了外梯度算法來求解單調且Lipschitz連續的變分不等式，算法如下：

yn=PC(xn-λF(xn))，xn+1=PC(xn-λF(yn))。

其中，PC(x)指點x向可行集C的正交投影。當λ∈(0，1/L)(L為F的利普希茨常數)時，證明了算法的全局收斂性。因此，該算法的收斂性是基于S=SD條件下得到的。此后在2000年，Tseng[5]對外梯度算法進行了改進，將新迭代點xn+1的計算修改為

xn+1=yn+λ(F(xn)-F(yn))，

并在與外梯度算法相同的假設條件下得到了算法的全局收斂性。新的算法在每次迭代中只需對可行集進行一次投影，從而節省了投影計算耗時。

為了削弱映射的單調性，2015年，Ye與He[3]介紹了一種雙投影算法，即：

r(xk)=xk-zk，yk=xk-ηkr(xk),ηk=γmk，

其中mk為滿足〈F(xk)-F(xk-γmr(xk)),r(xk)〉≤σ‖r(xk)‖2的最小非負整數，

最近，Liu與Yang[1]結合Tseng[5]的算法，在F是利普希茨連續的條件下介紹了一種求解擬單調(或無單調)變分不等式問題的投影算法，該算法如下：

yn=PC(xn-λnF(xn))，xn+1=yn+λn(F(xn)-F(yn))，

隨著變分不等式的數值算法的不斷發展，應用慣性思想來加速變分不等式的算法成為研究的一個熱點。但慣性方法如何保證所生成的序列具有Fejer單調性沒有得到證明。因此，Shehu和Iyiola[6]介紹了一種交替慣性的外梯度投影算法，可以保證該算法生成序列的偶數項具有Fejer單調性。本文主要考慮了擬單調變分不等式的算法，受Shehu和Iyiola的啟發，提出了一種利用交替慣性的方法來加速Liu和Yang[1]文中算法，在與Liu和Yang[1]相同的假設條件下得到了算法的全局收斂性。

1 預備知識

定義1設H為實希爾伯特空間，F:H→H為一個連續映射，故F在H上有如下定義：

1)γ-強單調，若存在常數γ>0，使得〈F(x)-F(y),x-y〉≥γ‖x-y‖，?x,y∈H；

2)單調，若〈F(x)-F(y),x-y〉≥0，?x,y∈H；

3)偽單調，若〈F(y),x-y〉≥0?〈F(x),x-y〉≥0，?x,y∈H；

4)擬單調，若〈F(y),x-y〉>0?〈F(x),x-y〉≥0，?x,y∈H；

5)利普希茨連續，若存在L>0，使得‖F(x)-F(y)‖≤L‖x-y‖，?x,y∈H。

由上述定義可知：1)?2)?3)?4)，但反之不成立。本文在與Liu與Yang[1]相同的條件下來考慮擬變分不等式問題。該假設如下：

A1)SD≠?；

A2)F是利普希茨連續的，且利普希茨連續常數為L；

A3)F是弱序連續的，即對序列{xn}，若{xn}弱收斂到x，則{F(xn)}弱收斂到F(x)；

A4)F在H上擬單調；

A5)集合{z|F(z)=0}SD為有限集。

引理1[1]令F為實的希爾伯特空間H中的一個連續映射，C是H中的非空閉凸集，若下列說法成立，則SD非空：

1)F在C上偽單調且S≠?；

2)F是G的梯度，其中G是一個在開集K?C上的可微擬凸函數，且在C上達到全局最小值；

3)F在C上擬單調，F≠0在C上，C有界；

4)F在C上擬單調，F≠0在C上，且存在一個正數r使得對?x∈C，有‖x‖≥r，那么存在y∈C，使得‖y‖≤r且〈F(x),y-x〉≤0；

5)F在C上擬單調,intC≠?,存在x*∈S，使得F(x*)≠0，則SD非空。

dist(x,C)=‖x-PCx‖。

引理2[7]令C為實的希爾伯特空間H中的非空閉凸集，則對任意x∈H，滿足

〈x-PCx,PCx-y〉≥0,?y∈C。

(3)

引理3[8]設H為實的希爾伯特空間，以下結論在希爾伯特空間中成立：

1)‖x+y‖2=‖x‖2+2〈x,y〉+‖y‖2，?x,y∈H；

2)‖x+y‖2≤‖x‖2+2〈y,x+y〉，?x,y∈H；

3)‖αx+βy‖2=α(α+β)‖x‖2+β(α+β)‖y‖2-αβ‖x-y‖2，?x,y∈H,?α,β∈。

定義3[8]設H為實希爾伯特空間，{xn}?H，S?H，序列{xn}對于集合S來說是Fejer單調的，若存在非負整數N,‖xn+1-z‖≤‖xn-z‖,?z∈S,?n≥N。

引理4[8](Opial)對希爾伯特空間中的任意序列{xn}，若xn弱收斂到x，則

2 算法及其主要結果

算法1

第二步：計算

yn=PC(ωn-λnF(ωn))，

(4)

(5)

若‖ωn-yn‖=0或‖F(yn)‖=0，則停止迭代；否則繼續。

第三步：計算

xn+1=yn+λn(F(ωn)-F(yn))。

(6)

第四步：令n=n+1，返回第二步。

證明參考Liu與Yang[1]中引理3.1的證明過程。

引理6假設A1)—A4)成立,設{xn}是由算法1生成的序列，則下列結論成立：

(7)

b)存在非負整數N1，使得

(8)

證明a)任取x*∈SD，則由(6)式知

‖xn+1-x*‖2=‖yn+λn(F(ωn)-F(yn))-x*‖2

=‖ωn-x*‖2+‖yn-ωn‖2+2〈yn-ωn,ωn-x*〉+

=‖ωn-x*‖2+‖ωn-yn‖2+2〈yn-ωn,ωn-yn〉+2〈yn-ωn,yn-x*〉+

=‖ωn-x*‖2-‖ωn-yn‖2+2〈yn-ωn,yn-x*〉+

(9)

另一方面，由yn=PC(ωn-λnF(ωn))及引理2可得〈yn-ωn+λnF(ωn),yn-x*〉≤0，即

〈yn-ωn,yn-x*〉≤-λn〈F(ωn),yn-x*〉。

(10)

從而由(9)和(10)式知

≤‖ωn-x*‖2-‖ωn-yn‖2+λn2‖F(yn)-F(ωn)‖2。

(11)

其中第二個不等式由x*∈SD,yn∈C可得。故a)結論成立。

b)分以下情況來證明(8)式成立：

b1)若F(yn)≠F(ωn),此時，結合λn+1的定義知

(12)

‖xn+1-x*‖2≤‖ωn-x*‖2-‖ωn-yn‖2+γn2μ2‖yn-ωn‖2

=‖ωn-x*‖2-(1-γn2μ2)‖ωn-yn‖2。

(13)

由(6)式知，

‖xn+1-yn‖=‖yn+λn(F(ωn)-F(yn))-yn‖=λn‖F(ωn)-F(yn)‖≤γnμ‖ωn-yn‖，

(14)

其中最后一個不等式由(12)式可得。由此，結合三角不等式可知

‖xn+1-ωn‖≤‖xn+1-yn‖+‖yn-ωn‖≤(1+γnμ)‖ωn-yn‖。

(15)

(16)

b2)若F(yn)=F(ωn)，此時由(6)式可得，xn+1=yn。從而由a)可得‖xn+1-x*‖2≤‖ωn-x*‖2-‖ωn-xn+1‖2。結合0<1-γn<1知，(16)式成立。

綜上所述，b)結論成立。

c)由b)可知

(17)

由引理3可知

‖ω2n+1-x*‖2=‖x2n+1+α2n+1(x2n+1-x2n)-x*‖2=‖(1+α2n+1)(x2n+1-x*)-α2n+1(x2n-x*)‖2

=(1+α2n+1)‖x2n+1-x*‖2-α2n+1‖x2n-x*‖2+α2n+1(1+α2n+1)‖x2n+1-x2n‖2。

(18)

又結合b)可知，對?n≥N1都有

(19)

所以，根據(18)(19)式，對?n≥N1都有

α2n+1‖x2n-x*‖2+α2n+1(1+α2n+1)‖x2n+1-x2n‖2

(20)

現將(20)式代入(17)式得

(21)

因為

(22)

(23)

由此結合(21)可知

‖x2n+2-x*‖≤‖x2n-x*‖，?n≥N2。

(24)

(25)

b){xn}，{ωn}與{yn}是有界點列,且均有相同的弱聚點。

(26)

由ωn的定義可知，

‖ωn-x*‖2=‖xn+αn(xn-xn-1)-x*‖2=‖(1+αn)(xn-x*)-αn(xn-1-x*)‖2

=(1+αn)‖xn-x*‖2-αn‖xn-1-x*‖2+αn(1+αn)‖xn-xn-1‖2。

(27)

故由(26)與(27)式可得，對于任意n≥N1，

‖xn+1-x*‖2≤(1+αn)‖xn-x*‖2-αn‖xn-1-x*‖2+αn(1+αn)‖xn-xn-1‖2-εn‖xn+1-ωn‖2。

(28)

又因為

‖xn+1-ωn‖2=‖xn+1-xn-αn(xn-xn-1)‖2

(29)

結合(28)以及(29)式可得，

‖xn+1-x*‖2≤(1+αn)‖xn-x*‖2-αn‖xn-1-x*‖2+αn(1+αn)‖xn-xn-1‖2-

=(1+αn)‖xn-x*‖2-αn‖xn-1-x*‖2-εn(1-αn)‖xn+1-xn‖2+

=(1+αn)‖xn-x*‖2-αn‖xn-1-x*‖2-ηn‖xn+1-xn‖2+θn‖xn-xn-1‖2，

(30)

令Γn=‖xn-x*‖2-αn‖xn-1-x*‖2+θn‖xn-xn-1‖2，則有

Γn+1-Γn=‖xn+1-x*‖2-(1+αn+1)‖xn-x*‖2+αn‖xn-1-x*‖2+θn+1‖xn+1-xn‖2-θn‖xn-xn-1‖2

≤‖xn+1-x*‖2-(1+αn)‖xn-x*‖2+αn‖xn-1-x*‖2+θn+1‖xn+1-xn‖2-θn‖xn-xn-1‖2

≤-(ηn-θn+1)‖xn+1-xn‖2，

(31)

其中第一個不等式由{αn}是遞增的可得，第二個不等式由(30)式可得。

(32)

從而由ηn與θn的定義可知

≥-(1-ε)α2-(1+2ε)α+ε，

(33)

ηn-θn+1>δ,?n≥N3，

(34)

其中2δ=-(1-ε)α2-(1+2ε)α+ε>0。結合(31)與(34)式可知

Γn+1-Γn≤-δ‖xn+1-xn‖2，?n≥N3。

(35)

因此，

Γn+1-Γn≤0，?n≥N3。

(36)

另一方面，

Γn=‖xn-x*‖2-αn‖xn-1-x*‖2+θn‖xn-xn-1‖2≥‖xn-x*‖2-αn‖xn-1-x*‖2。

(37)

那么，當n≥N3時，有

‖xn-x*‖2≤αn‖xn-1-x*‖2+Γn

≤α‖xn-1-x*‖2+ΓN3≤…≤αn-N3‖xN3-x*‖2+ΓN3(αn-N3-1+…+1)

(38)

Γn+1=‖xn+1-x*‖2-αn+1‖xn-x*‖2+θn+1‖xn+1-xn‖2≥-αn+1‖xn-x*‖2，?n≥N3。

(39)

故由(38)與(39)式可得

根據(35)式可得，

由引理6 a)可知

證明由引理7結合文獻[1]中的引理3.3、引理3.4、引理3.5及定理3.1知結論成立。由于內容完全類似，故略去證明。

3 結 語

本文研究了一類利用交替慣性方法來加速求解擬變分不等式問題的算法，其中映射是利普希茨連續的擬單調映射，但本文可以不考慮映射的利普希茨連續常數，還保證了生成序列偶數項的Fejer單調。