一类伪单调变分不等式的双投影算法

杨登炼, 张 燕, 张永乐

(四川师范大学 数学科学学院, 四川 成都 610066)

设C⊆Rn是一个非空闭凸集,F:Rn→Rn是连续映射.经典变分不等式问题:寻找x*∈C使得

〈F(x*),x-x*〉≥0, ∀x∈C,

(1)

其中〈·,·〉是欧几里得内积.为了便于表述,将问题(1)及其解集分别记为VI(C,F)和S.变分不等式作为非线性分析中的重要分支,它在工程、交通、数学规划等领域有广泛应用.因此,如何构造算法来求解变分不等式问题是值得研究的,而投影算法是解变分不等式的一类相对简单有效的方法,被广泛研究[1-8].最早的投影算法由Goldstein[2]提出

xk+1=PC(xk-λF(xk)),

(2)

其中λ>0为步长.该算法对映射F的要求为强单调和L-Lipschitz连续.虽然该算法的每一步迭代只需要一次投影,但强单调条件不容易满足,因此为了削弱F的强单调性,Korpelevich[3]提出了外梯度算法,其迭代形式为

yk=PC(xk-λF(xk)),

xk+1=PC(xk-λF(yk)).

(3)

在映射F满足单调和Lipschitz连续的条件时得到了该算法的收敛性.在此基础上,文献[5]通过引入Armijo线性搜索来削弱F是L-Lipschitz连续性.1999年,Solodov等[6]给出了一种利用二次投影求解VI(C,F)的算法,该算法采用Armijo线性搜索来确定步长,文献[7]说明了该算法能够得到一个较优的步长,从而在理论上优于其他投影算法.文献[6]的关键是在第二步投影中利用F(zk)构造了一个严格分离当前迭代点和解集的超平面,通过向该超平面与约束集的交上投影得到收敛到解的无穷迭代序列.2006年,He[8]利用F(zk)和rμ(xk)构造了一种新的超平面,进而提出了一种求解伪单调变分不等式的的双投影算法,该算法具有较好的数值计算结果.随后许多学者通过构造不同的超平面提出了不同的双投影算法[9-11].受此启发,本文利用F(zk)、F(xk)和rμ(xk)给出一类与以往不同的新的超平面,它能严格分离当前迭代点和解集,从而建立了一种新的双投影算法.在映射F连续和伪单调条件下建立了算法的收敛性,进一步假设F是Lipschitz连续的,进行了收敛性分析.最后,数值实验结果表明该算法是有效的.

1 基本准备

Rn是一个有限维的Hilbert空间,其内积和范数分别记为〈·,·〉和‖·‖.设C⊆Rn是一个非空闭凸集,对任意的z∈Rn,dist(z,C):=表示z到C的距离,

PC(z):=argmin{‖y-z‖|y∈C}

表示z在C上的投影,则有‖z-PC(z)‖=dist(z,C).对任意的μ>0,记rμ(x):=x-PC(x-μF(x)),称rμ(x)为自然残差函数.

定义 1.1设C⊆Rn是一个非空闭凸集.映射F:C→Rn,对任意的x,y∈C,若

1) 〈F(x)-F(y),x-y〉≥η‖x-y‖2,则称F在C上是强单调的,其中η>0称为F在C上的强单调系数.

2) 〈F(x)-F(y),x-y〉≥0,则称F在C上是单调的.

3) 〈F(x),y-x〉≥0⟹〈F(y),y-x〉≥0,则称F在C上是伪单调的.

定义 1.2设C⊆Rn是一个非空闭凸集,映射F:C→Rn,任意x,y∈C,若

‖F(x)-F(y)‖≤L‖x-y‖,

则称F在C上是L-Lipschitz连续的,其中L>0称为F在C上的Lipschitz系数.

以下为本文定理证明中需要用到的引理.

引理 1.1[12]设C是Rn上的一个非空闭凸集,对任意的x∈Rn,PC(x)为x在C上的投影,则对任意的y∈C,有下列不等式成立:

1) 〈x-PC(x),y-PC(x)〉≤0;

2) ‖y-PC(x)‖2≤‖x-y‖2-‖x-PC(x)‖2.

引理 1.2[13]设C⊆Rn是一个非空闭凸集,给定参数μ>0,则x*∈S当且仅当rμ(x*)=0.

引理 1.3[8]对任意x∈C,〈F(x),rμ(x)〉≥μ-1‖rμ(x)‖2.

引理 1.4[8]设C是Rn上的非空闭凸集,h(x)是C上的θ-Lipschitz连续实函数,K={x∈C|h(x)≤0}.若Lipschitz系数θ>0,则对任意的x∈C,dist(x,K)≥θ-1max{h(x),0}.

引理 1.5[14]设tk>0且满足

tk+1≤tk-βkt1+pk,βk≥0,p>0.

那么

tk≤t0(1+pt

特别的是,如果βk≡β,p=1,那么

t

2 主要结论

本文总假设以下条件成立:

(C1)S≠Ø；

(C2)F是连续和伪单调的.

2.1 双投影算法下面叙述算法的具体内容.

算法 2.1选取初始点x0∈C,σ>0,μ∈(0,σ-1),γ∈(0,1),a≥0,b∈[0,μ-1].设k=0.

步骤1计算rμ(xk)=xk-PC(xk-μF(xk)),如果rμ(xk)=0,停止;否则,转到步骤2.

步骤2计算zk=xk-ηkrμ(xk),其中ηk=γmk,mk是使得下面不等式成立的最小非负整数m,

〈F(xk)-F(xk-γmrμ(xk)),rμ(xk)〉≤

σ‖rμ(xk)‖2.

(4)

步骤3计算xk+1=PC∩Hk(xk),其中Hk:={v:hk(v)≤0},且函数

hk(v):=〈aF(xk)+F(zk)+bηkrμ(xk),

v-xk〉+(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2.

(5)

令k←k+1,转到步骤1.

注 2.1关于构成超平面的函数hk(v),通过比较发现,本文构造的超平面与已有文献中的超平面都不相同,并且包含某些已有超平面作为其特殊情形.如在文献[9]中,

hk(v)=〈αηkrμ(xk)+βF(xk)+αμF(zk),

v-xk〉+αηk(1-μσ)‖rμ(xk)‖2,

hk(v)=〈F(xk)+F(zk),v-xk〉+

ηk〈F(zk),rμ(xk)〉,

它是(5)式中a=1和b=0的特殊情形,但反之不成立,因为文献[11]中的超平面无‖rμ(xk)‖2这一项.

说明算法中(4)式是合理的.

引理 2.1对任意的k∈N+,当rμ(xk)≠0时,都存在非负整数m满足(4)式.

证明假设这样的m不存在,则存在k0∈N+,使得对所有的非负整数m,都有

〈F(xk0)-F(xk0-γmrμ(xk0)),rμ(xk0)〉>

σ‖rμ(xk0)‖2,

(6)

而F是连续的,且γ∈(0,1),则

〈F(xk0)-F(xk0-γmrμ(xk0)),

rμ(xk0)〉→0,m→∞.

由(6)式及σ>0可得矛盾式0<‖rμ(xk0)‖2≤0,则假设不成立,即存在非负整数m满足(4)式.

其次证明算法2.1中的超平面能严格分离当前迭代点和变分不等式的解集.

引理 2.2设x*∈S,hk(v)如(5)式所示,则有如下不等式成立:

(i)hk(xk)≥(μ-1-σ)ηk‖rμ(xk)‖2,特别地,如果rμ(xk)≠0,则hk(xk)>0;

(ii)hk(x*)≤0.

证明由hk(v)的定义可得

hk(xk)=(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

(1-bμ)ηk(〈F(xk),rμ(xk)〉-

σ‖rμ(xk)‖2)+b(1-μσ)ηk‖rμ(x

(1-bμ)ηk(μ-1‖rμ(xk)‖2-σ‖rμ(xk)‖2)+

b(1-μσ)ηk‖rμ(xk)‖2=

(μ-1-σ)ηk‖rμ(xk)‖2,

其中(a)是因为(1-bμ)ηk≥0和(4)式,(b)由引理1.3可得.若rμ(xk)≠0,由于(μ-1-σ)ηk>0,则hk(xk)>0,(i)得证.

因为rμ(xk)=xk-PC(xk-μF(xk)),则xk-rμ(xk)=PC(xk-μF(xk)).对任意的x*∈S,根据引理1.1的1)可得

〈rμ(xk)-μF(xk),x*-xk+rμ(xk)〉≤0,

即

〈rμ(xk)-μF(xk),x*-xk〉≤

μ〈F(xk),rμ(xk)〉-‖rμ(xk)‖2.

从而有

〈rμ(xk),x*-xk〉=〈rμ(xk)-μF(xk),

x*-xk〉+μ〈F(xk),x*-x

〈rμ(xk)-μF(xk),x*-xk〉≤

μ〈F(xk),rμ(xk)〉-‖rμ(xk)‖2,

(7)

其中(c)由条件(C2)可得.于是有

hk(x*)=〈aF(xk)+F(zk)+bηkrμ(xk),

x*-xk〉+(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

a〈F(xk),x*-xk〉+〈F(zk),x*-xk〉+

bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

〈F(zk),x*-xk〉+bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

(〈F(zk),x*-zk〉+〈F(zk),zk-xk〉)+

bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

〈F(zk),zk-xk〉+bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

-ηk〈F(zk),rμ(xk)〉+bηk〈rμ(xk),

x*-xk〉+(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

bηk〈rμ(xk),x*-xk〉-bμηk〈F(zk),

rμ(xk)〉+b(1-μσ)ηk‖rμ(x

bηk(μ〈F(xk),rμ(xk)〉-‖rμ(xk)‖2)-

bμηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

bμηk(〈F(xk)-F(zk),rμ(xk)〉-

σ‖rμ(x

其中(d)和(e)由条件(C2)可得,(f)由zk=xk-ηkrμ(xk)可得,(g)由(4)式可得,(h)由(4)式可得.证毕.

2.2 收敛性与收敛率分析下面分别对算法2.1的收敛性以及收敛率进行分析.

定理 2.1假设条件(C1)～(C2)成立,则算法2.1在有限步终止或生成一个无限序列{xk}收敛到S.

证明总假设算法2.1生成无限序列,即对任意的k∈N+,rμ(xk)≠0.否则必存在k1∈N+,使得rμ(xk1)=0,则xk1∈S.即算法在有限步终止.

对任意的x*∈S,由xk+1=PC∩Hk(xk),根据引理1.1的2)得

‖xk+1-x*‖2≤‖xk-x*‖2-‖xk+1-xk‖2=

‖xk-x*‖2-dist2(xk,C∩Hk),

(8)

从而可得序列{‖xk-x*‖2}是收敛的,因此{xk}有界.同时由(8)式有

dist(xk,C∩Hk)=0.

(9)

因为F(x)和rμ(x)关于x是连续的,于是{F(xk)}和{rμ(xk)}都是有界序列,进而有{zk}和{F(zk)}有界,则存在一个常数0

‖aF(xk)+F(zk)+bηkrμ(xk)‖≤M.

根据上式可知算法2.1中定义的hk(x)关于x在C上是Lipschitz连续的,且M为hk(x)的Lipschitz系数.于是由引理1.4以及xk∉C∩Hk有

dist(xk,C∩Hk)≥M-1hk(xk), ∀k∈N+.

结合上式以及引理2.2可得

dist(xk,C∩Hk)≥M-1hk(xk)≥

M-1(μ-1-σ)ηk‖rμ(xk)‖2,

(10)

σ‖rμ(xkj)‖2<〈F(xkj)-

F(xkj-γkj-1rμ(xkj)),rμ(xkj)〉=

〈F(xkj)-F(xkj-γ-1ηkrμ(xkj)),rμ(xkj)〉≤

‖F(xkj)-F(xkj-γ-1ηkrμ(xkj))‖‖rμ(xkj)‖,

∀j∈N+.

(11)

引理 2.3在定理2.1的假设条件下,进一步假设F是L-Lipschitz连续的,且存在常数α,δ>0以及任意的x,使得当rμ(x)≤δ时,有

dist(x,S)≤α‖rμ(x)‖,

(12)

则存在常数β>0使得对充分大的k有

dist(x

(13)

证明令η:=min先证明对任意的k∈N+,ηk>η成立.由ηk的构造可知ηk∈(0,1].若ηk=1,则显然有于是可假设ηk<1,则有最小非负整数mk≥1使得ηk=γmk.根据mk的最小性以及映射F的Lipschitz连续性,有

σ‖rμ(xk)‖2<

〈F(xk)-F(xk-γ-1ηkrμ(xk)),rμ(xk)〉≤

‖F(xk)-F(xk-γ-1ηkrμ(xk))‖‖rμ(xk)‖≤

Lγ-1ηk‖rμ(xk)‖2,

于是有ηk>L-1γσ≥η.

下证存在常数β>0使得对充分大的k,(13)式成立.设x*∈PS(xk),对于充分大的k,有以下不等式成立

dist2(xk+1,S)≤‖x

‖xk-x*‖2-dist2(xk,C∩H

‖xk-x*‖2-M-2(μ-1-σ)2ηk2‖rμ(xk)‖4≤

‖xk-x*‖2-M-2(μ-1-σ)2η2‖rμ(x

其中(a)由(8)式可得,(b)由(10)式可得,(c)由(12)式可得.记β=M-2(μ-1-σ)2η2α-4,根据引理1.5可得到

dist(x

(13)式得证.证毕.

3 数值实验

本节给出数值实验结果,在Windows 10,处理器为Intel(R) Core(TM)i5-4590 CPU@3.30 GHz的系统环境下,使用版本为R2019a的Matlab进行数值实验.调用quadprog函数计算向非空闭凸集的投影.将本文的算法2.1与文献[6]的算法2.2,文献[10]的算法2.1和文献[11]的算法3.1进行比较,并记录计算机实验结果.取‖rμ(x)‖≤10-4作为停机准则.x0表示初始点,nF表示计算F的次数,iter表示程序迭代的次数,time代表程序运行所需的时间.

例 3.1本例首先被文献[15]测试.令C=[0,1]n,考虑映射F(x)=Mx+d,其中

分别选取x0=(0,0,…,0)和x0=(1,1,…,1)为初始点,且参数选取如下:

1) 文献[6]的算法2.2:σ=0.3,γ=0.5,η-1=1,θ=4;

2) 文献[10]的算法3.1:σ=2.5,γ=0.9,μ=0.2,α=β=1;

3) 文献[11]的算法3.1:σ=6,γ=0.8,μ=0,15;

4) 算法2.1:σ=4,γ=0.8,μ=0.19,a=0.02,b=0.09.

前3种算法参数的选取与对应参考文献中推荐的一致.数值结果分别见表1与表2.

表1 例3.1中初始点为x0=(0,0,…,0)各算法的数值结果

表2 例3.1中初始点为x0=(1,1,…,1)各算法的数值结果

例 3.2Kojima-Shindo非线性互补问题(n=4)被文献[6]所考虑,其中函数F定义如下:

F(x1,x2,x3,x4)=

其可行集为

文献[10]的算法3.1中推荐的参数选取为σ=3,γ=0.9,μ=0.3,α=3,β=0.4.文献[6]的算法2.2、文献[11]的算法3.1和算法2.1推荐的参数选择与例1相同.分别选取不同的初始点进行数值实验,其结果见表3.

表3 例3.2中各算法的数值结果

通过数值实验对比可以看出,在适当的参数选取下,本文中的算法较其他3种算法更快,这表明了本文中的算法在一定程度上的有效性.