一類偽單調變分不等式的投影算法

楊軍劉紅衛張哲

(1.咸陽師范學院數信院,陜西 咸陽 712000;2.西安電子科技大學數統院,陜西 西安 710162)

1 引言

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

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

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

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

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

2 相關定義與引理

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

則稱F是單調映射.

(ii)若映射F滿足

則稱F是偽單調映射.

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

則稱F是利普西茨映射.

顯然單調映射是偽單調映射,反之不成立.令Fix(T)表示映射T的不動點集合,現給出下面的定義.

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

則稱I?T在0點是半閉的.

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

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

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

同時也等價于

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

引理2.2對于任意的u,v∈Rn.則

引理2.3[12]設{an}和{bn}是兩個非負數列,而且滿足

同時

則

引理2.4[13]設{anj}是非負實序列{an}的子列,而且子列滿足對于任意j∈N,成立anj

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

3 算法與收斂性證明

算法3.1

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

步驟2 計算

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

步驟3 計算

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

引理3.1[9]設F是Rn上的利普西茨連續映射,則算法3.1產生的步長序列{λn}單調遞減且有下界.

容易看出,

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

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

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

則

注意到yn=PC(xn?λnF(xn)),用引理2.1,得到

即

從而得到

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

由于

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

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

注意到?n≥N,

從而?n≥N,

故序列{xn}有界.進一步得到{zn}有界.

定理3.1設,則算法 3.1產生的序列{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,則

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

即

故

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

故

進一步有

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

從而得到z0∈S.又由于

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

由于

得到

情形2若存在的子列,有

用引理2.4,存在單調遞增的mk滿足且對于任意的k∈N成立:

進一步有

故

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