一類偽單調(diào)變分不等式的投影算法

楊軍劉紅衛(wèi)張哲

(1.咸陽師范學(xué)院數(shù)信院,陜西 咸陽 712000;2.西安電子科技大學(xué)數(shù)統(tǒng)院,陜西 西安 710162)

1 引言

設(shè)Rn是n維歐幾里得空間,C是Rn的非空閉凸子集,分別表示定義在Rn中的內(nèi)積和范數(shù),Rn中的序列{xn}收斂于x記為xn?→x.令F:Rn?→Rn是給定的映射,變分不等式問題為:尋找x?∈C,滿足

變分不等式在物理、經(jīng)濟(jì)平衡理論、控制論、工程、優(yōu)化等許多方面都有重要的應(yīng)用,其理論和算法的研究在近幾十年得到了長(zhǎng)足的進(jìn)展.對(duì)于變分不等式的算法主要有正則化方法和投影算法兩種方法.但正則化投影不適用于偽單調(diào)映射情形[1].本文研究利普希茨偽單調(diào)映射變分不等式的投影算法.

設(shè)C是Rn的非空閉凸子集,x∈Rn,x在C上的投影定義為

眾所周知[2],對(duì)于任意正數(shù)λ,x?是變分不等式(1)的解當(dāng)且僅當(dāng)

為了計(jì)算單調(diào)變分不等式,文獻(xiàn)[3-4]給出了外梯度投影算法,在其算法中,每個(gè)迭代步需要計(jì)算兩次投影.若C較復(fù)雜,則在C的投影難以計(jì)算.2000年,文獻(xiàn)[5]給出了一種梯度投影算法,在其算法中,每個(gè)迭代步只需計(jì)算一次投影.然而,上述算法的步長(zhǎng)與映射的利普希茨常數(shù)有關(guān),而利普希茨常數(shù)通常難以計(jì)算或估計(jì).為了避免估算利普希茨常數(shù),通常的做法是用類Amjo型搜索得到步長(zhǎng)[6-7].最近,文獻(xiàn)[8-10]給出了單調(diào)利普希茨映射的投影算法,算法中步長(zhǎng)的計(jì)算方法無需類Amjo型搜索.本文在文獻(xiàn)[9]的基礎(chǔ)上,給出了一種偽單調(diào)利普希茨映射的投影算法,并且算法的解與不動(dòng)點(diǎn)有關(guān).

2 相關(guān)定義與引理

定義 2.1(i)若映射F滿足

則稱F是單調(diào)映射.

(ii)若映射F滿足

則稱F是偽單調(diào)映射.

(iii)若存在常數(shù)L>0,映射F滿足

則稱F是利普西茨映射.

顯然單調(diào)映射是偽單調(diào)映射,反之不成立.令Fix(T)表示映射T的不動(dòng)點(diǎn)集合,現(xiàn)給出下面的定義.

定義 2.2(i)若Rn上的映射T滿足 Fix(T)?=?,且對(duì)于{xn}?Rn,下面結(jié)論成立

則稱I?T在0點(diǎn)是半閉的.

(ii)設(shè)T是Rn上的映射且0≤α<1,若T滿足

則稱T是α-半壓縮映射.

容易證明(見文獻(xiàn)[11]),T是Rn上α-半壓縮映射等價(jià)于

同時(shí)也等價(jià)于

引理2.1設(shè)C是Rn的非空閉凸子集,?x∈Rn,則

引理2.2對(duì)于任意的u,v∈Rn.則

引理2.3[12]設(shè){an}和{bn}是兩個(gè)非負(fù)數(shù)列,而且滿足

同時(shí)

則

引理2.4[13]設(shè){anj}是非負(fù)實(shí)序列{an}的子列,而且子列滿足對(duì)于任意j∈N,成立anj

而且當(dāng)k充分大時(shí)有k∈N:amk≤amk+1,ak≤amk+1.事實(shí)上mk是集合中{1,2,···,k}滿足an

3 算法與收斂性證明

算法3.1

步驟1 選取λ0>0,x0∈Rn,μ∈(0,1).

步驟2 計(jì)算

如果xn=yn,停止,xn是解.否則,

步驟3 計(jì)算

令n:=n+1并回到步驟2.

引理3.1[9]設(shè)F是Rn上的利普西茨連續(xù)映射,則算法3.1產(chǎn)生的步長(zhǎng)序列{λn}單調(diào)遞減且有下界.

容易看出,

本文假設(shè)F是Rn上的利普西茨連續(xù)偽單調(diào)映射,U是Rn上的α-半壓縮映射,I?U在0點(diǎn)是半閉的且變分不等式解集S與U的不動(dòng)點(diǎn)交集非空.由文獻(xiàn)[11]知,Fix(U)是閉凸集,從而S∩Fix(U)也是閉凸集.

引理3.2設(shè){αn}?(0,1),{βn}?(a,b)?(0,(1?α)(1?αn)),則算法 3.1產(chǎn)生的序列{xn}是有界的.

證明令u∈S∩Fix(U),由于

則

注意到y(tǒng)n=PC(xn?λnF(xn)),用引理2.1,得到

即

從而得到

由于u∈S∩Fix(U),則,又F是Rn上的偽單調(diào)映射,故,從而

由于

即,?N≥0,?n≥N,滿足

從而?n≥N,∥zn?u∥≤∥xn?u∥.又?n≥N,

注意到?n≥N,

從而?n≥N,

故序列{xn}有界.進(jìn)一步得到{zn}有界.

定理3.1設(shè),則算法 3.1產(chǎn)生的序列{xn}收斂到集合S∩Fix(U)中.

證明由于S∩Fix(U)是Rn上的非空閉凸子集,令x?=PS∩Fix(U)0,則

顯然x?∈S∩Fix(U),用引理3.2,?N≥0,?n≥N,有.用引理2.2,則

結(jié)合序列{xn},{zn}的有界性與映射U的定義,令M為序列的上界,得到?n≥N,

即

故

情形1若存在N2∈N(N2≥N1),滿足

故

進(jìn)一步有

由于{xn}有界,則存在子列{xnk}收斂于z0,同時(shí){ynk}和{znk}也收斂于z0,并滿足

從而得到z0∈S.又由于

故z0∈Fix(U),從而z0∈S∩Fix(U).下證

由于

得到

情形2若存在的子列,有

用引理2.4,存在單調(diào)遞增的mk滿足且對(duì)于任意的k∈N成立:

進(jìn)一步有

故

從而xk收斂于x?.定理證畢.