求解拟单调变分不等式问题的交替惯性向前向后算法

聂佳琳,龙宪军

(重庆工商大学数学与统计学院,重庆 400067)

1.引言

设H是实Hilbert空间,C是H的一个非空闭凸子集,〈·,·〉和∥·∥分别表示H中的内积和范数.设x ∈H,PC(x)表示向量x在C上的投影.设F:H →H是一个映射.本文考虑如下变分不等式问题: 找到v ∈C,使得

记问题(1.1)的解集为S.记SD为如下对偶变分不等式问题的解集: 找到v ∈C,使得

如果F是一个连续映射,那么SD ⊂S.近年来,变分不等式问题在经济金融、交通运输、工程力学和博弈论等领域有着广泛的应用.[1-3]1976年,Korpelevich[4]最早提出了求解变分不等式问题的外梯度算法:

其中F是单调且Lipschitz连续的,γn ∈L为Lipschitz常数.然而该算法在每次迭代时需计算两次到可行集C上的投影.若集合C的结构不够简单,则在C上的投影难以计算,从而影响算法的效率和适用性.为了克服这一缺点,许多学者提出了不同的改进方法.[5-9]特别地,Thong等[9]提出了改进的Tseng外梯度算法,其中算法步长γn是最大的γ ∈{α,αl,αl2,···}满足γ∥F(xn)-F(yn)∥≤µ∥xn{-yn∥,其具体算法如下

其中α>0,µ,l ∈(0,1).在映射F是单调且Lipschitz连续(L未知)的条件下,Thong等[9]获得了算法解的弱收敛定理.另一方面,在实际中许多函数并不满足单调性这一较强假设.因此,为了削弱单调性假设从而扩大算法的适用性,惯性方法由于其具有良好的加速性质受到许多学者的关注.[10-12]最近,Lzuchukwu等[14]提出了带有惯性项的自适应向前向后算法:

本文受到文[9,14] 的启发,在映射F是拟单调且Lipschitz连续的假设下,通过线搜索方法和惯性项的灵活构造,证明了由该算法产生的序列弱收敛到变分不等式问题的解.最后给出了数值实验结果.本文所得的结果改进和推广了文[14]中相应结果.

2.预备知识

记xn ⇀v(n →∞)为{xn}弱收敛于v.

定义2.1设F:H →H是一个映射.

(i) 如果〈F(u)-F(v),u-v〉≥0,∀u,v ∈H,则称F是单调的.

(ii) 如果〈F(v),u-v〉>0⇒〈F(u),u-v〉≥0,∀u,v ∈H,则称F是拟单调的.

(iii) 如果∥F(u)-F(v)∥≤L ∥u-v∥,∀u,v ∈H,其中L是Lipschitz常数且L>0,则称F是Lipschitz连续的.

注2.1显然,(i)⇒(ii),但是反之不成立,见文[13].

定义2.2任给v ∈H,则在C中存在唯一的一点,使得该点与v的距离最近,称这个点为v在C上的投影,记为PC(v),即

引理2.1[1]对任意的v ∈H,有

引理2.2[1]对任意的u,v ∈H,k ∈(0,1),有

(i)2〈u,v〉=∥u∥2+∥v∥2-∥u-v∥2=∥u+v∥2-∥u∥2-∥v∥2;

(ii)∥ku+(1-k)v∥2=k∥u∥2+(1-k)∥v∥2-k(1-k)∥u-v∥2.

引理2.3[9]设C是H中非空子集,{xn}是H中任意序列,若满足下面两个条件:

(i)对任意的v ∈C,存在;

(ii){xn}中每个子列的弱聚点都属于C.

则{xn}弱收敛到C中的一个点.

本文提出如下假设:

(C1)SD非空;

(C2)映射F满足: 当{xn}⊂C且{xn}⇀v∗时,有∥F(v∗)∥≤

(C3)映射F在H上是拟单调的;

(C4)映射F在C上是Lipschitz连续的.

3.提出的算法与收敛性证明

本文提出如下算法:

令n:=n+1,转到步1.

注3.1(i) 显然,算法3.1在每次迭代时只需计算一次到可行集C上的投影;

(ii) 假设(C2)比文[6]中的弱序列连续性更弱.比如F(v)=v∥v∥,∀v ∈C,满足假设(C2),但是不满足弱序列连续性.

引理3.1假设(C1)和(C4)成立,则线搜索准则(3.2)满足

证证明过程类似于文[9]中引理3.1的证明过程,故这里不再赘述.

引理3.2假设(C1)和(C4)成立,则线搜索准则(3.2)有限步终止.

证考虑下面两种情形.

情形一 若∥xn+1(γ)-xn∥=0,由假设(C4)知0≤∥F(xn+1(γ))-F(xn)∥≤L ∥xn+1(γ)-xn∥=0,则∥F(xn+1(γ))-F(xn)∥=0,故线搜索准则(3.2)成立.

情形二 若∥xn+1(γ)-xn∥>0,用反证法证明.假设线搜索准则(3.2)在有限步不终止,则对任意的mn有

对上式两端同时除以µ得

对上式取极限mn →∞得0≥∥xn+1(γ)-xn∥,这与条件∥xn+1(γ)-xn∥>0矛盾,故线搜索准则(3.2)在有限步终止.

为了证明主要的收敛结果,我们需要如下的两个引理.

引理3.3设{xn}是由算法3.1产生的序列,假设(C1)成立,则序列{x2n}是有界的.

证取z ∈SD,则z ∈S ⊂C.由引理2.1和2.2(i)知

上式等价于

上式结合(3.5)式有

由(3.2)式知

将(3.8)式代入(3.6)式得

由引理2.2(ii)知

将(3.10)和(3.11)式代入(3.9)式得

上式等价于

为表述方便,定义

引理3.4设{xn}是由算法3.1产生的序列,假设(C1)-(C4)成立.如果v∗是{x2n}的弱聚点,则v∗∈SD或F(v∗)=0.

证证明过程由注3.2结合文[14]中引理6.2的证明过程,故这里不再赘述.

定理3.1设{xn}是由算法3.1产生的序列,假设(C1)-(C3)成立,且F(x) =0,∀x ∈C.则{xn}弱收敛于SD ⊂S中的一个元素.

存在.

假设W(x2n)是{x2n}的所有弱聚点组成的集合,下面证明

接下来证明弱收敛点是唯一的.先假设{x2n}分别满足x2n ⇀v∗,n →∞和x2n ⇀x∗,n →∞,下证v∗=x∗.

显然v∗=x∗,即弱收敛点是唯一的.

由x2n ⇀x∗∈SD知,对∀z ∈H且z0有

结合上式与(3.20)得

所以x2n+1⇀x∗∈SD ⊂S.

因此xn ⇀x∗∈SD ⊂S.证毕.

注3.3本文从以下三个方面改进了文[9]中的结论:

1)F的单调性弱化为拟单调性.

2) 算法3.1只需计算一次F的函数值,而文[9]的算法中需要计算两次.

3) 算法3.1增加了交替惯性项使算法的收敛速度更快.

注3.4与文[14]中的算法1相比,算法3.1中对惯性项进行了灵活的构造且采用了线搜索准则来动态地确定算法的步长,可以显著提高算法的收敛速度,见例4.2.

4.数值实验

本节给出数值实验,通过两个例子将本文算法3.1与文[14]中的算法1以及文[9]中的算法2进行比较.所有代码均在MATLAB R2018a和Windows10系统下运行,计算机基本参数为Intel(R)Core(TM)i5-8250U CPU@1.60GHz.其中“iter”表示程序迭代次数,“CPU time”表示程序运行时间,单位为秒.所有算法的终止条件为∥xn+1-xn∥2≤err(err为提前设定的误差).

参数选取如下:

文[9]中的算法2: 设µ=0.1,α=1,l=0.5.

例4.1[14]若映射F:Rm →Rm满足F(x)=Mx+q,其中q ∈Rm且M=NN⊥+S+D,其中N,S,D ∈Rm×m,S为反对称矩阵,D为对角元素非负的对角矩阵.取可行集

可知映射F在C上是单调且Lipschitz连续的,相应的变分不等式的唯一解是{0}.在此情况下,我们对比了三种算法在不同维数p,q下的数值效果,见表4.1和图4.1.

图4.1 m=30时三种算法的对比

表4.1 err=10-10时不同算法关于维度的比较

例4.2[13]令C=[-1,1]

可知映射F在C上是拟单调且Lipschitz连续的.相应的变分不等式的解集是SD={-1}和S={-1,0}.在此情况下,我们对比了两种算法在不同初始值和不同误差情况下的数值效果,见表4.2,4.3和图4.2,4.3.

图4.2 x0=1,x1=2.4时两种算法的对比

图4.3 err=10-7时两种算法的对比

表4.2 err=10-5时不同算法关于初始值的比较

注4.1从数值实验的结果来看,我们有如下结论:

(i) 三种算法都收敛于变分不等式的解,见表4.1.

(ii) 从CPU运行时间来看,算法3.1都略优于其它两种算法,尤其是在例4.1中远胜于文[14]中的算法1,见表4.1.

(iii) 从迭代次数来看,算法3.1较其它两种算法具有优越性,尤其是在例4.2中随着精度的增加仍然表现出很强的稳定性,见表4.3.

表4.3 x0=1,x1=2时不同算法关于终止条件精度的比较

(iv) 算法3.1优于文[14]中的算法1和文[9]中的算法2,在单调与拟单调的条件下同样适用.