求解Banach空間中變分不等式新的單投影算法

周韻紅

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

0 引言

設(shè)E是一個(gè)實(shí)Banach空間，E*是其對(duì)偶空間，‖·‖和‖·‖E*分別是E和E*的范數(shù)，〈f,x〉是f∈E*在點(diǎn)x∈E處的函數(shù)值.設(shè)C是E中的一個(gè)非空閉凸子集，并且A:E→E*是一個(gè)Lipschitz連續(xù)映射.在本文中，考慮下面的變分不等式問(wèn)題(VIP)，即找x∈C，使得下面式子成立

〈Ax,y-x〉≥0，?y∈C.

(1)

用VI(A,C)來(lái)表示變分不等式問(wèn)題(1)，且用S表示它的解集.

變分不等式問(wèn)題是數(shù)學(xué)最優(yōu)化理論中一個(gè)有用而有效的工具.它統(tǒng)一了應(yīng)用數(shù)學(xué)中的幾個(gè)重要概念:必要條件、網(wǎng)絡(luò)平衡問(wèn)題、互補(bǔ)問(wèn)題和算子方程的方程組.對(duì)于VIP,最簡(jiǎn)單的投影方法是只在可行集上執(zhí)行一次投影的梯度方法，然而這種方法的收斂性需要一個(gè)輕微的強(qiáng)假設(shè)，即要求算子是強(qiáng)單調(diào)的或反強(qiáng)單調(diào)的.Korpelevich[1]提出了一個(gè)解決鞍點(diǎn)問(wèn)題的外梯(EGM)算法，它使我們避免了上述的強(qiáng)假設(shè).在那之后，它被發(fā)展并推廣到有限維和無(wú)限維的Hilbert空間中的VIP.在映射A是單調(diào)的和L-Lipschitz連續(xù)的假設(shè)下,保證了該方法的收斂性.該算法(EGM)的迭代格式如下：

(2)

(3)

(4)

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

本節(jié)給出一些概念和預(yù)備知識(shí).

設(shè)E是一個(gè)實(shí)的Banach空間，C是E中的一個(gè)非空閉凸子集.{xn}弱收斂到x表示為

xn→x(n→∞)(弱)，{xn}強(qiáng)收斂到x表示為xn→x(n→∞).

正規(guī)對(duì)偶映射J:E→E*定義為Jx={x*∈E*|〈x*,x〉=‖x*‖2=‖x‖2}.如果對(duì)所有的x,y∈SE,下式極限存在

(5)

如果存在c>0使得對(duì)于所有的ε∈[0,2]都有δE(ε)≥cε2，則稱空間E是2-一致凸的.顯然，所有的Hilbert空間都是2-一致光滑和2-一致光滑凸的.此外，所有的LP(1

引理1.1空間E是2-一致凸的當(dāng)且僅當(dāng)存在μE≥1，使得

(6)

對(duì)于所有的x,y∈E，所有滿足(6)式的μE≥1所構(gòu)成的集合中的最小值記為μ，稱為空間E的2-一致凸性系數(shù).顯然μ=1當(dāng)且僅當(dāng)E是Hilbert空間.

(i)E是2-一致凸的.

定義1.1假設(shè)C?E是一個(gè)非空集合，A:C→E*是一個(gè)連續(xù)映射，則有

(i)A是單調(diào)的當(dāng)且僅當(dāng)

〈Ax-Ay,x-y〉≥0,?x,y∈C;

(ii)A是L-Lipschitz連續(xù)的(L>0)，即存在常數(shù)L>0，使得

‖Ax-Ay‖≤L‖x-y‖,?x,y∈C.

下面介紹一個(gè)非常有用的函數(shù)，即Lyapunovfunctionalφ:E×E→R，其定義如下:

φ(x,y):=‖x‖2-2〈x,Jy〉+‖y‖2,?x,y∈E

顯然，φ(x,y)≥(‖x‖-‖y‖)2≥0.

SCADA系統(tǒng)是進(jìn)行電網(wǎng)數(shù)據(jù)采集與監(jiān)控的系統(tǒng)。通過(guò)SCADA系統(tǒng)檢驗(yàn)開(kāi)關(guān)狀態(tài)，去除不良數(shù)據(jù)，計(jì)算出比SCADA遙測(cè)數(shù)據(jù)更準(zhǔn)確的運(yùn)行方式，以及未裝量測(cè)的設(shè)備潮流和難以測(cè)量的電氣量。數(shù)據(jù)在SCADA中需有定義，沒(méi)有定義的數(shù)據(jù)不從SCADA獲取。

引理1.4令E是一個(gè)實(shí)的、一致凸的、光滑的Banach空間，則下面的式子成立：

(i)φ(x,y)=φ(x,z)+φ(z,y)+2〈x-z,Jz-Jy〉,?x,y,z∈E;

(ii)φ(x,y)+φ(y,x)=2〈x-y,Jx-Jy〉,?x,y∈E.

接下來(lái)介紹一個(gè)相關(guān)的函數(shù)，它對(duì)文章后面的收斂分析非常有用.假設(shè)C?E是實(shí)的、一致凸的Banach空間E的一個(gè)非空集合.則函數(shù)V:E×E*→R，其定義為：

如果算子ΠC：E→C?E將函數(shù)φ(y,z)的最小值點(diǎn)與任意固定點(diǎn)z∈E相聯(lián)系，即下面最小值問(wèn)題的解，則稱該算子稱為廣義投影算子，其定義如下

下面將介紹ΠC的一些性質(zhì).

引理1.5下述結(jié)論成立.

(ii)廣義投影算子產(chǎn)生了相關(guān)函數(shù)φ(w,z)的一個(gè)最優(yōu)值，即

(iii)V(x*,x)+2〈J-1x*-x,y*〉≤V(x*+y*,x),?x∈E,x*,y*∈E*.

引理1.6假設(shè)E是一個(gè)2-一致凸的Banach空間，則存在μ≥1使得

引理1.7令{an}是一個(gè)實(shí)數(shù)列，使得這里存在n的一個(gè)子序列{ni}滿足ani

amk≤amk+1且ak≤amk+1.實(shí)際上，mk={j≤k:aj

引理1.8令{an}是一個(gè)非負(fù)實(shí)數(shù)列并且滿足下面的關(guān)系：

則有an→0(n→∞).

引理1.9C是E一個(gè)非空閉凸子集.令A(yù):C→E*是一個(gè)連續(xù)單調(diào)算子并且z∈C，則有

z∈S?〈Ax,x-z〉≥0對(duì)所有的x∈C都成立.

2 結(jié)果

這一節(jié)介紹了求解Banach空間中單調(diào)變分不等式問(wèn)題的一種新的迭代算法.為了給出該算法并證明其收斂性，現(xiàn)作如下假設(shè):

假設(shè)1

(a)可行集C上是實(shí)的2-一致凸、光滑的Banach空間E的一個(gè)非空閉凸子集.

A：E→E*在C上是單調(diào)的且在E上是L-Lipshitz連續(xù)的.

(c)VI(A,C)的解集S是非空的.

現(xiàn)在，討論以下算法用來(lái)解決單調(diào)變分不等式的收斂性.該算法(算法A)如下：

(步驟0)令λ0>0，x0∈E是初始值，δ∈(0,1).

(步驟1)已知xn，計(jì)算yn=ΠCJ-1(Jxn-λnAxn)，如果xn=yn，則停止；否則轉(zhuǎn)向步驟2.

(步驟2)計(jì)算wn=J-1[Jyn-λn(Ayn-Axn)]和xn+1=J-1[αnJx1+(1-αn)Jwn].

(步驟3)計(jì)算

這里μ是E的2-一致凸性系數(shù)；κ是E*的2-一致光滑系數(shù).設(shè)n:=n+1返回步驟1.

下面給出算法的強(qiáng)收斂性.

引理2.1若假設(shè)1成立，xn,yn,λn是算法A產(chǎn)生的序列，則有下面的成立:

(1)對(duì)于某個(gè)n∈N,如果xn=yn，那么xn∈S;

證明(1)如果xn=yn，又由xn=ΠCJ-1(Jxn-λnAxn),所以xn∈C.由引理1.3(i),有

〈w-xn,Jxn-(Jxn-λnAxn)〉≥0,?w∈C,

由上式可得到λn〈Axn,w-xn〉≥0,?w∈C，因?yàn)棣薾>0,所以有xn∈S.

(2)顯然{λn}是一個(gè)遞減序列.因?yàn)锳是L-Lipschitz連續(xù)映射且L>0，

若‖Axn-Ayn‖>0，有

引理2.2若假設(shè)1成立，{xn}是由算法A產(chǎn)生的序列，并且αn?(0,1).那么序列{xn}是有界的.

證明令x*∈S.由φ的定義，得到

φ(x*,wn)=φ(x*,J-1(Jyn-λn(Ayn-Axn)))

=‖x*‖2-2〈x*,JJ-1(Jyn-λn(Ayn-Axn)〉+‖J-1(Jyn-λn(Ayn-Axn))‖2

=‖x*‖2-2〈x*,Jyn-λn(Ayn-Axn)〉+‖Jyn-λn(Ayn-Axn)‖2

=‖x*‖2-2〈x*,Jyn〉+2λn〈x*,Ayn-Axn〉+‖Jyn-λn(Ayn-Axn)‖2.

(7)

利用引理1.2，可得到E*是2-一致光滑的，再利用引理1.3,則得到

‖Jyn-λn(Ayn-Axn)‖2≤‖Jyn‖2-2〈yn,λn(Ayn-Axn)〉+2κ2‖λn(Ayn-Axn)‖2.

(8)

將(8)帶入(7)，可得到

φ(x*,wn)≤‖x*‖2-2〈x*,Jyn〉+2λn〈x*,Ayn-Axn〉+‖Jyn‖2-2λn〈yn,Ayn-Axn〉

+2κ2‖λn(Ayn-Axn)‖2=φ(x*,yn)-2λn〈yn-x*,Ayn-Axn〉

+2κ2‖λn(Ayn-Axn)‖2.

(9)

利用引理1.4(i)，得到

φ(x*,yn)=φ(x*,xn)+φ(xn,yn)+2〈x*-xn,Jxn-Jyn〉

=φ(x*,xn)+φ(xn,yn)+2〈xn-x*,Jyn-Jxn〉.

(10)

將(10)帶進(jìn)(9)，可得到

φ(x*,wn)≤φ(x*,xn)+φ(xn,yn)+2〈xn-x*,Jyn-Jxn〉-2λn〈yn-x*,Ayn-Axn〉

+2κ2‖λn(Ayn-Axn)‖2=φ(x*,xn)+φ(xn,yn)-2〈yn-xn,Jyn-Jxn〉

+2〈yn-x*,Jyn-Jxn〉-2λn〈yn-x*,Ayn-Axn〉

+2κ2‖λn(Ayn-Axn)‖2.

(11)

利用引理1.4(ii)，則得到：

-φ(yn,xn)+2〈yn-xn,Jyn-Jxn〉=φ(xn,yn)

(12)

結(jié)合(11)和(12)，得到

φ(x*,wn)≤φ(x*,xn)-φ(yn,xn)+2〈yn-x*,Jyn-Jxn〉

-2λn〈yn-x*,Ayn-Axn〉+2κ2‖λn(Ayn-Axn)‖2.

(13)

利用引理1.5(i)，得到〈Jxn-λnAxn-Jyn,x*-yn〉≤0,因?yàn)閤*∈C，這就意味著

〈Jyn-Jxn+λnAxn,yn-x*〉≤0,這就等價(jià)于

〈Jyn-Jxn,yn-x*〉≤-λn〈Axn,yn-x*〉.

(14)

將(14)帶入(13)，則得到：

φ(x*,wn)≤φ(x*,xn)-φ(yn,xn)-2λn〈Axn,yn-x*〉-2λn〈Ayn-Axn,yn-x*〉

+2κ2‖λn(Ayn-Axn)‖2=φ(x*,xn)-φ(yn,xn)-2λn〈Ayn,yn-x*〉

+2κ2‖λn(Ayn-Axn)‖2≤φ(x*,xn)-φ(yn,xn)+2κ2‖λn(Ayn-Axn)‖2

-2λn〈Ayn-Ax*,yn-x*〉-2λn〈Ax*,yn-x*〉.

(15)

因?yàn)锳是單調(diào)的且x*∈S，所以可得到〈Ayn-Ax*,yn-x*〉≥0和〈Ax*,yn-x*〉≥0，從(15)中有：

φ(x*,wn)≤φ(x*,xn)-φ(yn,xn)+2κ2‖λn(Ayn-Axn)‖2

(16)

(17)

利用xn+1的定義，對(duì)每個(gè)n>N0，有：

φ(x*,xn+1)=φ(x*,J-1(αnJx1+(1-αn)Jwn))=‖x*‖2-2〈x*,JJ-1(αnJx1+(1-αn)Jwn)〉

+‖J-1(αnJx1+(1-αn)Jwn)‖2=‖x*‖2-2〈x*,αnJx1

+(1-αn)Jwn〉+‖αnJx1+(1-αn)Jwn‖2≤‖x*‖2

-2αn〈x*,Jx1〉-2(1-αn)〈x*,Jwn〉+αn‖Jx1‖2+(1-αn)‖Jwn‖2

=αn‖x*‖2-2αn〈x*,Jx1〉+αn‖Jx1‖2+(1-αn)‖x*‖2

-2(1-αn)〈x*,Jwn〉+(1-αn)‖Jwn‖2=αnφ(x*,x1)+(1-αn)φ(x*,wn)

=αnφ(x*,x1)+(1-αn)φ(x*,xn)≤max{φ(x*,x1),φ(x*,xn)}

≤···

≤max{φ(x*,x1),φ(x*,x1)}=φ(x*,x1).

(18)

所以{φ(xn,x*)}有界，則有{xn}有界.

引理2.3若{xn}，{yn}是由算法A產(chǎn)生的序列，假設(shè)‖xn-yn‖→0,n→∞,p∈C是{xnk}的弱極限，這里k?N，那么有p∈S.

證明對(duì)任意的x∈C,利用引理1.5(i),則有(因?yàn)锳是單調(diào)的)

0≤〈Jynk-Jxnk+λnkAxnk,x-ynk〉

=〈Jynk-Jxnk,x-ynk〉+λnk〈Axnk,xnk-ynk〉+λnk〈Axnk,x-xnk〉

≤〈Jynk-Jxnk,x-ynk〉+λnk〈Axnk,xnk-ynk〉+λnk〈Ax,x-xnk〉

通過(guò)取極限，得到〈Ax,x-p〉≥0,?x∈C，利用引理1.9得到p∈S.

現(xiàn)在證明本文算法的強(qiáng)收斂性.

證明利用引理2.2,可知道{xn}有界，又由引理1.5(iii)則有

φ(z,xn+1)=φ(z,J-1(αnJx1+(1-αn)Jwn))

=V(z,αnJx1+(1-αn)Jwn)

≤V(z,αnJx1+(1-αn)Jwn-αn(Jx1-Jz))+2αn〈Jx1-Jz,xn+1-z〉

=V(z,αnJz+(1-αn)Jwn)+2αn〈Jx1-Jz,xn+1-z〉

≤αnV(z,Jz)+(1-αn)V(z,Jwn)+2αn〈Jx1-Jz,xn+1-z〉

=(1-αn)V(z,Jwn)+2αn〈Jx1-Jz,xn+1-z〉

≤(1-αn)V(z,Jxn)+2αn〈Jx1-Jz,xn+1-z〉

=(1-αn)φ(z,xn)+2αn〈Jx1-Jz,xn+1-z〉.

(19)

為了得到算法A的強(qiáng)收斂性，設(shè)an:=φ(z,xn)并且將證明分成兩個(gè)部分，如下：

φ(z,xn+1)≤αnφ(z,x1)+(1-αn)φ(z,wn)

(20)

又因?yàn)椤瑇n-yn‖→0,n→∞，所以從wn的定義可以得到：

這里M2>0，所以有‖wn-yn‖→0,n→∞.此外由xn+1的定義得到：

‖Jxn+1-Jwn‖=αn‖Jx1-Jwn‖≤αnM3→0(n→∞),

(21)

這里M3>0，因?yàn)镴-1在E*的有界子集上是范數(shù)到范數(shù)一致連續(xù)的，所以可以得到‖xn+1-wn‖→0,n→∞.

所以有‖xn+1-xn‖≤‖xn+1-wn‖+‖wn-yn‖+‖yn-xn‖→0,n→∞，因?yàn)閧xn}有界，所以我們可以選擇

{xn}的一個(gè)子序列{xnk}，使得{xnk}弱極限是p∈E，并且有：

因?yàn)閦=ΠCx1，所以有：

(22)

因此xn→z,n→∞.

φ(z,xnk)≤φ(z,xnk+1)andφ(z,xk)≤φ(z,xnk+1).

(23)

通過(guò)觀察，得到：

φ(z,xnk)≤φ(z,xnk+1)≤αnkφ(z,x1)+(1-αnk)φ(z,wnk)≤αnkφ(z,x1)+(1-αnk)φ(z,xnk).

xn→z,n→∞.‖xnk-ynk‖→0,k→∞,‖ynk-wnk‖→0,k→∞,‖xnk+1-xnk‖→0,k→∞.

類似地，可以推出：

(24)

從(19)和(20)得到：

φ(z,xnk+1)≤(1-αnk)φ(z,xnk)+2αnk〈Jx1-Jz,xnk+1-z〉

≤(1-αnk)φ(z,xnk+1)+2αnk〈Jx1-Jz,xnk+1-z〉.

因?yàn)棣羘k>0，所以有φ(z,xnk)≤φ(z,xnk+1)≤2〈Jx1-Jz,xnk+1-z〉，由(24)則有：

因此xk→z,k→∞.即證.