杨 博, 夏福全

(四川师范大学 数学与软件科学学院, 四川 成都 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.