方長杰, 王 盈(重慶郵電大學(xué) 理學(xué)院, 重慶 400065)

?

Hilbert空間中變分不等式的一種新算法

方長杰, 王 盈
(重慶郵電大學(xué) 理學(xué)院, 重慶 400065)

提出在Hilbert空間中求解變分不等式問題的新的混合超梯度算法,在f是單調(diào)且連續(xù)的映射的假設(shè)下,證明由新的混合超梯度算法所生成迭代序列強(qiáng)收斂到變分不等式問題的解集與可數(shù)無限個非擴(kuò)張映射的不動點集合的公共元素.

變分不等式; 不動點; 非擴(kuò)張映射; 連續(xù)映射; 單調(diào)映射; 強(qiáng)收斂

變分不等式問題(簡記VI(f,K)):設(shè)K為實Hilbert空間上的一個非空閉凸集,f:K→K是一個連續(xù)映射.求x*∈K,使得

〈f(x*),x-x*〉≥0, ?x∈K.

(1)

本文中,K*表示VI(f,K)的解集并且假設(shè)它是非空的.

變分不等式理論已經(jīng)成為研究諸如障礙、單側(cè)、平衡問題等理論與應(yīng)用科學(xué)中問題的重要工具,例如參考文獻(xiàn)[1-8].G. M. Korpelevich[9]提出了求解變分不等式問題(1)的超梯度算法,M. V.Solodov等[10]提出了求解變分不等式問題(1)的二次投影方法,該方法的特點是下一步迭代點是當(dāng)前迭代點到超平面與可行集合交上的投影,且該超平面嚴(yán)格分離當(dāng)前迭代點與變分不等式的解集.W. Takahashi等[11]提出了求解變分不等式問題(1)的如下迭代算法:

xi+1=αixi+(1-αi)SΠK(xi-λif(xi)),

(2)

其中{αi}∈(0,1),{λi}∈(0,2λ),S:K→K是一個非擴(kuò)張映射,Fix(S)表示S的不動點集合.在假設(shè)K*∩Fix(S)≠?的條件下,文獻(xiàn)[11]證明了由(2)式生成的序列{xi}弱收斂到某點x*∈K*∩Fix(S).

受以上研究的啟發(fā),本文提出了求解變分不等式(1)的一個新的超梯度算法(見本文算法2.1),在所涉及映射是單調(diào)和連續(xù)的假定下,證明了算法所產(chǎn)生的序列強(qiáng)收斂到變分不等式問題(1)的解集與一族可數(shù)無限非擴(kuò)張映射不動點集合的公共元素.在算法2.1中，用Li代替文獻(xiàn)[6-7,11-12]中的非擴(kuò)張映射S(Li的定義見(4)和(5)式);與文獻(xiàn)[12]的算法A相比,增加了混合投影步驟(見算法2.1的步驟4),從而得到了算法的強(qiáng)收斂結(jié)果.此外,算法2.1和文獻(xiàn)[12]中算法A的Armijo線性搜索程序也是不同的.

1 預(yù)備知識

設(shè)H是實的Hilbert空間,其內(nèi)積和范數(shù)分別記為〈x,y〉和‖·‖.用xi?x和xi→x分別表示序列{xi}弱收斂和強(qiáng)收斂到x,I為K上的恒等映射.ΠK(x)表示H到K上的投影算子,即對任意的x∈H,存在唯一的ΠK(x)∈K使得

‖x-ΠK(x)‖=inf{‖x-y‖,y∈K}.

引理 1.1[13]1) 〈x-ΠK(x),ΠK(x)-y〉≥0,?x∈Rn,?y∈K;

2) ‖ΠK(x)-ΠK(y)‖≤‖x-y‖,?x,y∈Rn;

3) ‖ΠK(x)-y‖2≤‖x-y‖2-‖x-ΠK(x)‖2,?x∈Rn,?y∈K;

4) ‖ΠK(x)-ΠK(y)‖2≤‖x-y‖2-‖ΠK(x)-x+y-ΠK(y)‖2,?x,y∈Rn.

定義 1.1 稱映射f是:1) 單調(diào)的,如果

〈x-y,f(x)-f(y)〉≥0, ?x,y∈K;

2)α-Lipschitz連續(xù)的,如果存在常數(shù)α≥0,使得

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

定義 1.2 1) 定義f的圖像G(f)為

G(f)={(x,y)∈K×K:y=f(x)};

2) 稱映射S:K→K為非擴(kuò)張的,如果

‖S(x)-S(y)‖≤‖x-y‖, ?x,y∈K.

令

NK(v)={w∈H:〈v-u,w〉≥0,u∈K}.

(3)

定義

則T極大單調(diào)的,且0∈T(v)當(dāng)且僅當(dāng)v∈K*(見文獻(xiàn)[14]).

用ωw(xi)表示{xi}的弱聚點集合,即ωw(xi)={x∈H:{xij}弱收斂到x,其中{ij}是{i}的某個子序列}.

引理 1.3[17]設(shè)K是H的非空閉凸子集,{xi}是H中的一個序列且x∈H.令u=ΠK(x).如果ωω(xi)?K且‖xi-x‖≤‖x-u‖，i=1,2,…,那么xi→u.

Hilbert空間滿足Opial條件(參見文獻(xiàn)[18]),即如果{xi}弱收斂到x,那么

2 主要結(jié)果

令

(4)

(5)

對x∈K0,定義:

r(x):=x-ΠK0(x-f(x)).

(6)

顯然,有x∈K*當(dāng)且僅當(dāng)r(x)=0.

接下來介紹求解變分不等式(1)的如下混合超梯度算法

算法 2.1 選取x0∈K0,δ∈(0,1),λ∈(0,1).令i=0.

第1步:對xi∈K0,計算

yi=ΠK0(xi-f(xi)),zi=(1-ηi)xi+ηiyi,

其中ηi=γni，ni是滿足下面不等式的最小非負(fù)整數(shù)n:

〈f(xi)-f(xi-γnr(xi)),r(xi)〉≤δ‖r(xi)‖2.

(7)

第2步:計算ti=ΠHi∩K0(xi),其中

Hi={x∈K0|〈x-zi,f(zi)〉≤0}.

第3步:計算

wi=αix0+(1-αi)[βixi+(1-βi)Liti],

其中{αi}?(a,b),a,b∈(0,1)且當(dāng)i→∞時有αi→0,對c,d∈(0,1)有{βi}?[c,d].

第4步:計算xi+1=ΠQi∩Mi(x0),其中

Qi={x∈H:‖wi-x‖2≤‖xi-x‖2+

αi(‖x0‖2+2〈xi-x0,x〉)},

Mi={x∈H:〈xi-x,x0-xi〉≥0}.

第5步:若r(xi+1)=0，停止,否則,回到第1步.

以下的3個命題在證明由算法2.1所生成迭代序列的強(qiáng)收斂性中起著關(guān)鍵作用.

據(jù)調(diào)查，截至2015年，河南省外出務(wù)工人數(shù)達(dá)1 220萬，有82.7萬名農(nóng)村留守兒童。由于缺少父母的關(guān)心和引導(dǎo)，留守兒童在為人處世、與人交流及學(xué)習(xí)等方面都受到了影響。近年來，南陽市各區(qū)縣不斷采取相應(yīng)措施，加快農(nóng)村剩余勞動力向城市轉(zhuǎn)移。截至目前，南陽市離家務(wù)工者高達(dá)240萬人，造成了嚴(yán)重的留守兒童問題，所以選擇此地作為考查地點具有一定的可行性。

由(4)和(5)式知

現(xiàn)令x∈F.因?qū)λ械膉≥1有x∈Fix(Sj),故

故F?Fix(Li).

因為

命題 2.2 假設(shè)映射f:K0→H是單調(diào)和連續(xù)的,K*∩F≠?.若x*∈K*∩F,則對算法2.1生成的序列{xi}、{wi}、{ti}有

‖xi-x*‖]+αi(‖x0‖2+2〈xi-x0,x*〉),

(8)

‖wi-xi‖[‖wi-x*‖+‖xi-x*‖]+

αi(‖x0‖2+2〈xi-x0,x*〉).

(9)

證明 類似文獻(xiàn)[12]定理7的證明有

‖ti-x*‖2≤‖xi-x*‖2-‖xi-ti‖2+

(10)

因為zi=(1-ηi)xi+ηiyi,故

(11)

利用Cauchy-Schwarz不等式有

(12)

因此,由(10)～(12)式有

‖ti-x*‖2≤‖xi-x*‖2-‖xi-ti‖2-

由x*∈K*∩F和F?Fix(Li)知x*∈Fix(Li).所以

‖wi-x*‖2≤αi‖x0-x*‖2+(1-αi)βi‖xi-x*‖2+

(1-αi)(1-βi)‖Liti-x*‖2≤

αi‖x0-x*‖2+(1-αi)βi‖xi-x*‖2+

(1-αi)(1-βi)‖ti-x*‖2≤

αi‖x0-x*‖2+(1-αi)‖xi-x*‖2-

‖xi-x*‖2+αi(‖x0‖2+2〈xi-x0,x*〉)-

(13)

根據(jù)(13)式,對所有的i∈N有

‖xi-ti‖2≤‖xi-x*‖2-

‖wi-x*‖2+αi(‖x0‖2+2〈xi-x0,x*〉)≤

‖wi-xi‖[‖wi-x*‖+‖xi-x*‖]+

αi(‖x0‖2+2〈xi-x0,x*〉).

再次運(yùn)用Cauchy-Schwarz不等式得到

(14)

由此,從(10)、(11)和(14)式可得

‖wi-x*‖2≤αi‖x0-x*‖2+(1-αi)βi‖xi-x*‖2+

αi‖x0-x*‖2+(1-αi)‖xi-x*‖2-

‖xi-x*‖2+αi(‖x0-x*‖2-‖xi-x*‖2)-

‖xi-x*‖2+αi(‖x0‖2+2〈xi-x0,x*〉)-

(15)

因此,由(15)式得到不等式(9).

命題 2.3 若K*∩F≠?,則:

1)xi+1有定義;

2) ‖xi-x0‖≤‖xi+1-x0‖≤‖x0-ΠK*∩F(x0)‖.

證明 1) 只需證明Mi∩Qi是Hilbert空間中的非空閉凸集.首先,證明對任意的i∈N,Mi∩Qi是閉凸的.顯然，對任意的i∈N,Mi是閉凸的且Qi是閉的.因為

‖wi-x‖2≤‖xi-x‖2+

αi(‖x0‖2+2〈xi-x0,x〉),

等價于

〈(1-αi)xi+αix0-wi,x〉≤〈xi-wi,xi〉-

因此,Qi是凸的.接著證明Mi∩Qi是非空的.假設(shè)K*∩F?Mi.因為xi+1=ΠQi∩Mi(x0)，所以,對所有z∈K*∩F?Qi∩Mi有〈xi+1-x0,z-xi+1〉≥0,因此K*∩F?Mi+1.故得證.

2) 由于

〈xi-x,x0-xi〉≥0, ?x∈Mi,

所以xi=ΠMi(x0).由xi+1∈Mi知

‖xi-x0‖=‖ΠMi(x0)-x0‖≤‖xi+1-x0‖.

(16)

注意ΠK*∩F(x0)∈K*∩F?Mi+1,因此

‖xi+1-x0‖=‖ΠMi+1(x0)-x0‖≤

‖ΠK*∩F(x0)-x0‖.

(17)

故根據(jù)(16)和(17)式有

‖xi-x0‖≤‖xi+1-x0‖≤‖x0-ΠK*∩F(x0)‖.

下面的定理說明由算法2.1生成的序列{xi}強(qiáng)收斂到K*∩F的某個元素.

證明 根據(jù)引理1.3和命題2.3的2),只需證明ωω(xi)?K*∩F.分4步證明我們的結(jié)論.

第1步:‖xi+1-xi‖→0,‖wi-xi‖→0,‖xi-ti‖→0,‖Lixi-xi‖→0.

在引理1.1的3)中令y=xi+1和x=x0有

‖xi+1-xi‖2≤‖xi+1-x0‖2-‖xi-x0‖2.

(18)

因此

‖xi+1-xi‖→0,i→0.

(19)

由xi+1∈Qi有

‖wi-xi+1‖2≤‖xi-xi+1‖2+

αi(‖x0‖2+2〈xi-x0,xi+1〉).

(20)

因為{xi}有界且αi→0,i→0,所以由(19)和(20)式有‖wi-xi+1‖→0,i→0.從而

‖wi-xi‖→0.

(21)

由{xi}有界知{wi}有界.因為{αi}?(a,b)(a,b∈(0,1))且{βi}?[c,d](c,d∈(0,1)),所以,從(8)和(21)式可得

‖xi-ti‖→0.

(22)

因為

所以

(23)

由于Li是非擴(kuò)張的且x*∈Fix(Li),所以

‖Liti-x0‖≤‖Liti-x*‖+‖x*-x0‖≤

‖Liti-Lix*‖+‖x*-x0‖≤

‖ti-x*‖+‖x*-x0‖.

因此,從{ti}有界可知‖Liti-x0‖有界.從而由(23)式知

‖Liti-xi‖→0.

(24)

因為

‖Lixi-xi‖≤‖Lixi-Liti‖+‖Liti-xi‖≤

‖xi-ti‖+‖Liti-xi‖,

故從(22)和(24)式可知

‖Lixi-xi‖→0.

(25)

第2步:令(v,u)∈G(T),則u∈T(v)=NK(v)+f(v),從而u-f(v)∈NK(v).因此

〈v-x,u-f(v)〉≥0, ?x∈K.

(26)

令x=xi-f(xi)，y=v,由引理1.1的1)知〈xi-f(xi)-ΠK(xi-f(xi)),ΠK(xi-f(xi))-v〉≥0,即

〈xi-f(xi)-yi,yi-v〉≥0.

(27)

因為ti∈K,故由(26)式有

〈v-ti,u-f(v)〉≥0.

(28)

根據(jù){xi}的有界性和f的連續(xù)性知,{yi}、{zi}和{f(zi)}是有界的.根據(jù){αi}和{βi}的假設(shè),由(9)式知

‖r(xi)‖2=0.

(29)

‖xij-yij‖=0,

(30)

和

(31)

由于‖yij-tij‖≤‖yij-xij‖+‖xij-tij‖,故由(22)和(30)式知

‖yij-tij‖=0.

(32)

從而由(28)式可得

〈v-tij,u〉≥〈v-tij,f(v)〉≥〈v-tij,f(v)〉-

〈xij-f(xij)-yij,yij-v〉=

〈v-tij,f(v)-f(tij)〉+〈v-tij,f(tij)〉-

〈v-yij,yij-xij〉-〈v-yij,f(xij)〉≥

〈v-tij,f(tij)〉-〈v-yij,yij-xij〉-

〈v-yij,f(xij)〉,

(33)

其中最后一個不等式可根據(jù)f的單調(diào)性得到.

由于f是連續(xù)的,對(33)式取極限有

δ‖r(xi)‖2<〈f(xi)-f(xi-γni-1r(xi))〉=

〈f(xi)-f(xi-γ-1ηir(xi))〉.

(34)

(35)

‖Lixi-Txi‖=0.

(36)

因此由(25)和(36)式可得

矛盾,故得證.

矛盾,故得證.

[1] Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementary Problems[M]. New York:Springer-Verlag,2003.

[2] Fang C J, He Y R. A double projection algorithm for multi-valued variational inequalities and a unified framework of the method[J]. Appl Math Comput,2011,217:9543-9511.

[3] Fang C J, He Y R. An extragradient method for generalized variational inequality[J]. Pacific J Optimization,2013,9:47-59.

[4] Fang C J, Chen S L. A subgradient extragradient algorithm for solving multi-valued variational inequality[J]. Appl Math Comput,2014,229:123-130.

[5] Fang C J, Chen S L. A projection algorithm for set-valued variational inequalities on Hadamard manifolds[J]. Optimization Letters,2015,9:779-794.

[6] Iiduka H, Takahashi W. Strong convergence theorems for nonexpansive nonself-mappings and inverse-strongly-monotone mappings[J]. J Convex Analysis,2004,11(1):69-79.

[7] Nadezhkina N, Takahashi W. Strong convergence theorem by a hybrid method for nonexpansive mappings and Lipschitz-continuous monotone mappings[J]. SIAM J Optimization,2006,16(4):1230-1241.

[8] Thuy N T T. A new hybrid method for variational inequality and fixed point problems[J]. Vietnam J Mathematics,2013,41(3):353-366.

[9] Korpelevich G M. The extragradient method for finding saddle points and other problems[J]. Matecon,1976,12:747-756.

[10] Solodov M V, Svaiter B F. A new projection method for variational inequality problems[J]. SIAM J Control and Optimization,1999,37(3):765-776.

[11] Takahashi W, Toyoda M. Weak convergence theorems for nonexpansive mappings and monotone mappings[J]. J Optimization Theory and Applications,2003,118(2):417-428.

[12] Wang X, Li S, Kou X. An extension of subgradient method for variational inequality problems in Hilbert space[J]. Abstract and Applied Analysis,2013:2013.

[13] Zarantonello E H. Projections on Convex Sets in Hilbert Space and Spectral Theory:Contributions to Nonlinear Functional Analysis[M]. New York:Academic Press,1971.

[14] Rockafellar R T. On the maximality of sums of nonlinear monotone operators[J]. Transactions of the American Mathematical Society,1970,149:75-88.

[15] Bruck Jr R E. Properties of fixed point sets of nonexpansive mappings in Banach spaces[J]. Transactions of the American Mathematical Society,1973,179:251-262.

[16] He S, Guo J. Iterative algorithm for common fixed points of infinite family of nonexpansive mappings in Banach spaces[J]. J Appl Math,2012:2012.

[17] Goebel K, Kirk W A. Topics in Metric Fixed Point Theory[M]. Cambridge:Cambridge University Press,1990.

[18] Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings[J]. Bulletin of the American Mathematical Society,1967,73(4):591-597.

2010 MSC:49J40

(編輯 余 毅)

A New Algorithm for Variational Inequality Problems in a Hilbert Space

FANG Changjie, WANG Ying
(CollegeofScience,ChongqingUniversityofPostsandTelecommunications,Chongqing400065)

In this paper, we present a hybrid extragradient method for variational inequality problems in a Hilbert space. Under the assumption thatfis a continuous and monotone mapping, we prove that the sequence generated by our method converges strongly to the common element of solutions of the variational inequality problem and fixed point set of a countably infinite family of nonexpansive mappings in Hilbert spaces.

variational inequality; fixed point; nonexpansive mapping; continuous mappings; monotone mapping; strong convergence

2015-05-18

國家自然科學(xué)基金(11426055)、重慶市自然科學(xué)基金基礎(chǔ)與前沿研究計劃項目基金(CSTC2014JCYJA00044)

方長杰(1974—),男,副教授,主要從事非線性泛函方向的研究,E-mail:fangcj@cqupt.edu.cn

O177.92; O178

A

1001-8395(2015)06-0824-06

10.3969/j.issn.1001-8395.2015.06.006