廣義混合變分不等式問題的投影算法

楊 博, 夏福全

(四川師范大學 數學與軟件科學學院, 四川 成都 610066)

本文總假設Rn是一個n維歐氏空間,它的內積和范數分別記為〈·,·〉和‖·‖.設f:Rn→Rn∪{+∞}是真凸下半連續泛函,dom(f)={x∈Rn:f(x)<+∞}表示f的有效域.設F:Rn?Rn是連續集值映射,Dom(F)={x∈Rn|F(x)≠?}表示F的有效域.設K?Rn是非空閉凸子集,IK(x)表示集合K的指示映射,即

本文考慮廣義混合變分不等式問題(簡稱GMVI(F,f)):求x∈dom(f),對?y∈dom(f),使得存在ξ∈F(x)滿足

〈ξ,y-x〉+f(y)-f(x)≥0.

(1)

令S表示問題(1)的解集,本文總假設S非空.

若φ(x):Rn→Rn是連續凸函數,

F(x)=?φ(x),

其中?φ(x)表示φ在x點處的次微分,那么對于x∈dom(f),問題(1)退化為下面的凸優化問題

min{f(x)+φ(x)}.

如果問題(1)中F為單值映射且f(x)=IK(x),則問題(1)退化為下面的經典變分不等式問題：求x∈K滿足

〈F(x),y-x〉≥0, ?y∈K.

(2)

關于問題(2)的各類算法中,投影算法因其有效性而得到廣泛研究,參見文獻[1-6],其中,文獻[1]提出了一種求解變分不等式(2)的二次投影算法.該算法首先利用當前點xi得到zi,其中的迭代步長滿足Armijo線性搜索,然后利用zi構造了一個分離當前點和解集的超平面.然后,將當前點xi投影到可行集K和超平面的交集上得到下一步迭代點xi+1,在假設F是連續和偽單調的條件下,文獻[1]證明了該算法生成的無窮序列收斂到變分不等式的一個解.此外,在文獻[1]的基礎上,文獻[4]提出了新的Armijo線搜索過程并構造了不同的分離超平面,與文獻[1]相同的假設條件下,給出了該算法的收斂性定理.

若F為集值映射,則問題(2)變為集值變分不等式問題：求x∈K,存在ξ∈F(x)滿足

〈ξ,y-x〉≥0, ?y∈K.

(3)

許多文獻對問題(3)提出了各類算法,參見文獻[7-14],其中,文獻[14]推廣了文獻[1]的Armijo線搜索和超平面,提出了問題(3)的投影算法,給出了算法收斂性的證明,并在F是Lipschitz連續單值映射等假設條件下,獲得了算法的收斂率.此后,文獻[8]提出了與文獻[14]不同的Armijo線搜索過程并構造不同的分離超平面,在假設集值映射F是緊凸值且連續的條件下,證明了算法生成的無窮序列具有全局收斂性,并給出了與文獻[14]的數值對比,表明了這種算法是有意義的.

如果F是一個單值映射,則GMVI(F,f)退化為：求x∈dom(f),對?y∈dom(f)滿足

〈F(x),y-x〉+f(y)-f(x)≥0.

(4)

對于變分不等式的問題(4),文獻[15]給出了問題(4)的一類新的投影算法,并在一定的條件下,獲得了該算法的收斂性定理.同時,在假設F是Lipschitz連續的條件下分析了迭代序列的收斂率.此外,文獻[16]提出了與文獻[15]不同的線搜索過程并選取了不同的半空間,在文獻[15]相同的假設條件下,證明了算法產生的無窮序列是收斂的.

在此之后,文獻[17]通過選取一種新的Armijo線搜索方法,并以此構造分離超平面,提出了問題(1)的投影算法.在一定的條件下,證明了算法生成的無窮序列具有全局收斂性,并給出了數值計算結果,表明了這種算法是有意義的.

受文獻[4,8,14-17]研究工作的啟發,本文構造了廣義混合變分不等式的一類新的投影算法.該算法與文獻[17]的算法相比,提出了不同的Armijo線搜索過程,本文的線搜索過程中不含有擾動項,使得Armijo線搜索過程變得更加簡潔,并由此構造了不同的分離超平面.最后,本文給出了與文獻[8,17]的數值對比,表明這種算法的意義.

1 預備知識

下面給出一些有用的結論和概念.

定義1.1令f:Rn→Rn∪{+∞}是真凸下半連續泛函,稱集值映射F:Rn?Rn是:

(i) 單調的,如果對?x,y∈Rn,u∈F(x),v∈F(y)有

〈u-v,y-x〉≥0;

(ii) 偽單調的,如果對?x,y∈Rn,u∈F(x),v∈F(y)有

〈u,y-x〉≥0→〈v,y-x〉≥0;

(iii)f-偽單調的,如果?x,y∈Rn,u∈F(x),v∈F(y)有

〈u,y-x〉+f(y)-f(x)≥0→
〈v,y-x〉+f(y)-f(x)≥0.

定義1.2[18]設A:Rn?Rn為極大單調算子,A關于參數λ的預解算子定義為

其中λ>0,I:Rn→Rn表示恒等映射.

設f:Rn→Rn∪{+∞}是真凸下半連續泛函,f在x∈dom(f)的次微分為

?f(x):={ξ∈Rn:f(y)-f(x)≥
〈ξ,y-x〉,?y∈Rn}.

定義1.3令f:Rn→R∪{+∞}是真凸下半連續泛函,且K為dom(f)的一個非空子集.稱f是K上的δ-Lipschitz連續函數,如果滿足

|f(x)-f(y)|≤δ‖x-y‖, ?x,y∈K.

定義1.4稱集值映射F:Rn?Rn是上半連續的,如果對任意的x∈Rn和F(x)的任意鄰域V?Rn,存在x的鄰域U,使得對任意的z∈U有F(z)?V.

定義1.5[19]稱集值映射F:Rn?Rn在x∈Dom(F)處下半連續當且僅當對任意的y∈F(x)和收斂到x的任意序列{xn}?Dom(F),存在yn∈F(xn),使得序列{yn}收斂到y.

‖x-PK(x)‖=dist(x,K).

引理1.1設K?Rn為非空閉凸子集,則對任意的x,y∈Rn,z∈K,有

‖PK(x)-z‖2≤‖x-z‖2-‖PK(x)-x‖2.

為簡化記號,對任意的x∈Rn,ξ∈F(x),分別記:

p(x)=(I+?f)-1(x-ξ),

則顯然有命題1.1成立.

命題1.1如果x*∈dom(f)是廣義混合變分不等式問題的解當且僅當

其中ξ*∈F(x*).

引理1.2[15]設h:Rn→Rn是真凸函數,K={x∈Rn:h(x)≤0}?D?dom(f),如果h在D上是θ-Lipschitz的連續函數,則

dist(x,K)≥θ-1max{h(x),0}, ?x∈D.

2 算法

首先敘述算法的具體內容,并證明算法的良定性和一些引理.

算法2.1選取初始點x0∈dom(f)和參變量γ,σ∈(0,1),取i=0.

步驟1 任意選取ξi∈F(xi),計算p(xi)和r1(xi,ξi),如果r1(xi,ξi)=0,停止;否則,轉到下一步.

步驟2 計算ηi=γki和zi=xi-ηir1(xi,ξi),其中,ki是滿足下面不等式的最小非負整數

〈ξi-yi,r1(xi,ξi)〉≤σ‖r1(xi,ξi)‖2,yi=PF(xi-γkir1(xi,ξi))(ξi).

(5)

步驟3 計算xi+1=PHi(xi),其中v∈dom(f),

Hi:={v|hi(v)≤0},

(6)

hi(v):=〈ηir1(xi,ξi)+yi,v-zi〉+f(v)-

f(zi)+ηi[f(p(xi))-f(xi)]+ηi(1-ηi)×
‖r1(xi,ξi)‖2-ηi〈ξi,r1(xi,ξi)〉.

(7)

讓i=i+1,回到步驟1.

的上確界,并滿足

yi∈argmax{〈y,r(xi,1,ξi〉|y∈F(zi)},

而算法2.1中yi=PF(zi)(ξi)；

(ii) 當f(x)=IK(x)且F為單值映射時,算法2.1的Armijo線性搜索過程和半空間與文獻[4]的相同.

引理2.1如果集值映射F:Rn?Rn是下半連續的,若r1(xi,ξi)≠0,則算法2.1中滿足(5)式的最小非負整數ki存在.

證明若r1(xi,ξi)≠0,假設對任意的k∈N+都不滿足(5)式,則

〈ξi-yk,r1(xi,ξi)〉>σ‖r1(xi,ξi)‖2,

(8)

因為F是下半連續映射,ξi∈F(xi)且k→∞時,

xi-γkr1(xi,ξi)→xi,

則存在uk∈F(xi-γkr1(xi,ξi)),使得

又因yk=PF(xi-γkr1(xi,ξi))(ξi),當k→∞時,則

‖yk-ξi‖≤‖uk-ξi‖→0.

(9)

0=〈ξi-yk,r1(xi,ξi)〉≥σ‖r1(xi,ξi)‖2>0,

矛盾.所以,假設不成立原命題成立.

引理2.2設f:Rn→R∪{+∞}是真凸下半連續泛函,集值映射F:Rn?Rn是f-偽單調的,若x*是GMVI(F,f)的解,函數hi由(7)式定義,則

hi(xi)≥ηi(1-σ)‖r1(xi,ξi)‖2,

且hi(x*)≤0.特別地,如果r1(x1,ξ1)≠0,則hi(xi)>0.

證明

hi(xi)=〈ηir1(xi,ξi)+yi,xi-zi〉+

f(xi)-f(zi)+ηi[f(p(xi))-f(xi)]+

ηi(1-ηi)‖r1(xi,ξi)‖2-ηi〈ξi,r1(xi,ξi)〉=

f(xi)-f(zi)+ηi[f(p(xi))-f(xi)]+

ηi(1-ηi)‖r1(xi,ξi)‖2-ηi〈ξi,r1(xi,ξi)〉≥

ηi‖r1(xi,ξi)‖2-ηiσ‖r1(xi,ξi)‖2+

f(xi)-f(zi)+ηi[f(p(xi))-f(xi)],

由zi=xi-ηir1(xi,ξi)且r1(xi,ξi)=xi-p(xi),f為真凸泛函可得

f(xi)-f(zi)≥ηi(f(xi)-f(p(xi))).

從而

hi(xi)≥ηi(1-σ)‖r1(xi,ξi)‖2.

(10)

特別地,因為σ∈(0,1)且r1(xi,ξi)≠0,則hi(xi)>0.

又因p(xi)=(I+?f)-1(xi-ξi),則由次微分的定義得

〈ξi-r1(xi,ξi),y-xi+r1(xi,ξi)〉+
f(y)-f(p(xi))≥0, ?y∈Rn.

取y=x*,則有

〈ξi-r1(xi,ξi),x*-xi+r1(xi,ξi)〉+
f(x*)-f(p(xi))≥0.

(11)

又因為,x*∈S且集值映射F是f-偽單調的,由此可得

〈ξi,xi-x*〉+f(xi)-f(x*)≥0,?ξi∈F(xi).

(12)

將(11)和(12)式相加可得

〈ξi,r1(xi,ξi)〉≥〈r1(xi,ξi),x*-xi+
r1(xi,ξi)〉+f(p(xi))-f(xi).

因此

hi(x*)=〈ηir1(xi,ξi)+yi,x*-zi〉+f(x*)-

f(zi)+ηi[f(p(xi))-f(xi)]+ηi(1-ηi)×

‖r1(xi,ξi)‖2-ηi〈ξi,r1(xi,ξi)〉≤

ηi〈r1(xi,ξi),x*-zi〉+〈yi,x*-zi〉+

f(x*)-f(zi)+ηi[f(p(xi))-f(xi)]+

ηi(1-ηi)‖r1(xi,ξi)‖2+ηi〈r1(xi,ξi),

xi-x*-r1(xi,ξi)〉+ηi[f(xi)-f(p(xi))]=

ηi〈r1(xi,ξi),xi-zi〉+〈yi,x*-zi〉+f(x*)-

f(zi)+ηi(1-ηi)‖r1(xi,ξi)‖2-

ηi‖r1(xi,ξi)‖2=

ηi2‖r1(xi,ξi)‖2+〈yi,x*-zi〉+f(x*)-

f(zi)+ηi(1-ηi)‖r1(xi,ξi)‖2-

ηi‖r1(xi,ξi)‖2≤0.

3 算法的收斂性

下面在適當的條件下證明算法2.1產生的序列{xi}是全局收斂的.

定理3.1設廣義混合變分不等式問題的解集S非空,如果：

(i) F:Rn?Rn是具有緊凸值的連續且f-偽單調的集值映射；

(ii)f:Rn→R∪{+∞}是真凸泛函且在dom(f)上是β-Lipschitz的連續映射.

那么算法2.1或在有限步迭代后終止,或者產生一個收斂于解點的無窮序列.

證明若算法2.1在有限步后終止,那么終止點即為解點.假設算法2.1產生一個無窮序列{xi},則對每一個i,

r1(x1,ξi)≠0.

x*∈S是GMVI(F,f)的一個解,又由引理2.2知x*∈Hi.又因xi+1=PHi(xi),故由引理1.1可得

‖xi+1-x*‖2≤‖xi-x*‖2-
‖xi+1-xi‖2=
‖xi-x*‖2-dist2(xi,Hi).

(13)

因此數列{‖xi-x*‖}是單調遞減的收斂數列.由此可得,{xi}是有界序列且

(14)

〈ξi-ui,r1(xi,ξi)〉>σ‖r1(xi,ξi)‖2,?ui=PF(xi-γki-1r1(xi,ξi))(ξi).

如果kij→∞,則令

〈ξij-uij,r1(xij,ξij)〉>σ‖r1(xij,ξij)‖2.

F(xi-γkir1(xi,ξi))≠F(xi),

則yi=PF(xi-γkir1(xi,ξi))(ξi)≠ξi.

則由上面的不等式可知,存在M>0使得

因此,序列{p(xi)},{r1(xi,ξi)}是有界的,故存在α>0,使得‖r1(xi,ξi)‖≤α.又因,

zi=xi-ηir1(xi,ξi).

所以,序列{zi}是有界的.由文獻[20]的命題3.1可得{F(zi):i∈N}是有界集,所以序列{yi}是有界的,故存在τ>0,使得‖yi‖≤τ,則對任意的

x,y∈dom(f),‖hi(x)-hi(y)‖=
‖〈ηir1(xi,ξi)+yi,x-y〉+f(x)-f(y)‖≤
‖ηi‖·‖r1(xi,ξi)‖·‖yi‖·‖x-y‖+
‖f(x)-f(y)‖≤
ατ‖x-y‖+β‖x-y‖=(ατ+β)‖x-y‖.

因此,每一泛函hi在dom(f)上是(ατ+β)-Lipschitz的連續函數.注意到xi?Hi,運用引理1.2可得

dist(xi,Hi)≥(ατ+β)-1hi(xi)≥
(ατ+β)-1·ηi(1-σ)‖r1(xi,ξi)‖2.

結合(14)式有

(15)

由{ηi}的有界性,考慮下面2種情況.

1) 若

則由(15)式可知

由ki的定義可知

〈ξi-ui,r1(xi,ξi)〉>σ‖r1(xi,ξi)‖2,?ui=PF(xi-γki-1r1(xi,ξi))(ξi).

σ‖r1(xij,ξij)‖2<〈ξij-uij,r1(xij,ξij)〉≤
‖ξij-uij‖·‖r1(xij,ξij)‖.

4 數值實驗

首先利用一個廣義混合變分不等式問題(例4.1)來測試算法2.1,并與文獻[17]的算法2.1做了比較.其次,給出了算法2.1在問題(3)上的計算機檢驗結果,并與文獻[8]的算法2.2做了對比.

在CPU型號為Intel(R)Core(TM)i5CPUM430@2.27GHZ的計算機上運行算法的程序代碼,其Matlab使用版本為7.12.0.635(R2011a),其優化工具為ToolboxVersion6.0.

在下列數值表格中,iter表示迭代的步數,CPU表示計算機運行所需要的時間,inf表示F被賦值的次數,表示停機準則,即標準||r1(x,ξ)||≤.

例4.1令n=4,集合

定義函數f為

定義集值映射F:K?Rn為

由定義可知F和K滿足定理3.1的條件且x=(0,0,0,0)T是廣義混合變分不等式的解.

f(x)=‖x‖2,z=(I+?f)-1(g),

對任意的x、g∈Rn,有下面的關系

z=(I+?f)-1(g)→g∈z+(?f+?IK)(z)?
g-3z∈?IK(z)=NK(z)，

其中NK(z)表示集合K在z處的法錐,即

NK(z)={y∈Rn|〈y,x-z〉≤0,x∈K}.

由最優性條件可得

〈3z-g,y-z〉≥0, ?y∈K.

因此,求z=(I+?f)-1(g)等價于求解F(x)=3x-g的變分不等式問題,使用文獻[1]的算法2.2來計算z.例4.1中,分別選取參數為σ=0.5,γ=0.4和σ=0.5,γ=0.9計算算法2.1和文獻[17]的算法3.3,得到的數值結果(見表1).

表 1 例4.1的數值實驗

例4.2令n=4,集合

集值映射F:K?Rn為

令f(x)=IK(x),則問題(1)退化為問題(3).由K和F的定義可知滿足定理3.1的條件且x=(1,0,0,0)T是集值變分不等式的解.在例4.2中,分別選取σ=0.9,γ=0.5和σ=0.5,γ=0.8計算算法2.1和文獻[8]的算法2.2,得到的數值結果(見表2).

表 2 例4.2的數值實驗

[1] SOlODOV M V, SVAITER B F. A new projection method for variational inequality problems[J]. SIAM J Control Optim,1999,37(3):765-776.

[2] YUAN X M, LIN M. An lqp-based decomposition for solving a class of variational inequalities[J]. SIAM J Optim,2011,21(4):1309-1318.

[3] IUSEM A N, SVAITER B F. A variant of kopelevich's method for variational inequalities with inequalities[J]. J Comput Appl Math,1997,42(4):309-321.

[4] HE Y R. A new double projection algorithm for variational inequalities[J]. J Comput Appl Math,2006,185(1):166-173.

[5] HASSINA G, DJAMEl B. New effective projection method for variational inequalities problem[J]. Rairo-oper Res,2015,49(4):805-820.

[6] ZHENG L. The subgradient double projection method for variational inequlities in a Hilbert space[J]. Fixed Point Theory Appl,2013,2013(1):1-14.

[7] ANH P N, LE D M, STROSIOT J J. Generalized projection method for non-lipschitz multivalued monotone variational inequalities[J]. Acta Math Vietnam,2009,34(1):67-79.

[8] FANG C J, HE Y R. A new projection algorithm for generalized variational inequality[J]. J Inequal Appl,2010,2010(1):1-8.

[9] XIA F Q, HUANG N J. A projection-proximal point algorithm for solving generalized variational inequalities[J]. J Optim Theory Appl,2011,150(1):98-117.

[10] FANG C J, CHEN S L. A subgradient algorithm for solving multi-valued variational inequality[J]. Appl Math Comput,2014,229(1):123-130.

[11] CHEN H B, WANG Y J, WANG G. Strong convergence of extragradient method for gengeralized variational inequalities in Hilbert space[J]. J Inequal Appl,2014,2014(1):1-11.

[12] 陳方琴,夏福全. Hilbert空間中廣義變分不等式的近似-似投影算法[J]. 四川師范大學學報(自然科學版),2012,35(3):297-302.

[13] ANH P N, MUU L D, NGUYEN V H, et al. Using the banach contraction principle to implement the proximal point method for multi-valued monotone variational inequalities[J]. J Optim Theory Appl,2005,124(2):285-306.

[14] LI F, HE Y R. An algorithm for generlized variational inequality with pseudomonotone mapping[J]. J Comput Appl Math,2009,228(1):212-218.

[15] HE Y R. A new projection algorithm for mixed variational inequalities[J]. Acta Math Sci,2007,A27(2):215-220.

[16] TANG G J, ZHU M, LIU H W. A new extragradient-type method for mixed varaitional inequalities[J]. Oper Res Lett,2015,43(6):567-572.

[17] TU K, XIA F Q. A projection-type algorithm for solving generalized mixed variational inequalities[J]. Acta Math Sci,2016,B36(6):1619-1630.

[18] BREZIS H. Operateurs Maximaux Monotone et Semi-groupes De Contractions Sans Les Espaces De Hilbert[M]. Amsterdam:North-Holland Publishing Company,1973.

[19] AUBIN J P, FRANKOWSKA H. Set-Valued Analysis[M]. Boston:Birkhause,1990.

[20] AUBIN J P, EKELAND I. Applied Nonlinear Analysis[M]. New York:John Wiley and Sons Incorporated,1984.