求解擬單調(diào)變分不等式問題的交替慣性向前向后算法

聶佳琳,龍憲軍

(重慶工商大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,重慶 400067)

1.引言

設(shè)H是實(shí)Hilbert空間,C是H的一個非空閉凸子集,〈·,·〉和∥·∥分別表示H中的內(nèi)積和范數(shù).設(shè)x ∈H,PC(x)表示向量x在C上的投影.設(shè)F:H →H是一個映射.本文考慮如下變分不等式問題: 找到v ∈C,使得

記問題(1.1)的解集為S.記SD為如下對偶變分不等式問題的解集: 找到v ∈C,使得

如果F是一個連續(xù)映射,那么SD ?S.近年來,變分不等式問題在經(jīng)濟(jì)金融、交通運(yùn)輸、工程力學(xué)和博弈論等領(lǐng)域有著廣泛的應(yīng)用.[1-3]1976年,Korpelevich[4]最早提出了求解變分不等式問題的外梯度算法:

其中F是單調(diào)且Lipschitz連續(xù)的,γn ∈L為Lipschitz常數(shù).然而該算法在每次迭代時需計算兩次到可行集C上的投影.若集合C的結(jié)構(gòu)不夠簡單,則在C上的投影難以計算,從而影響算法的效率和適用性.為了克服這一缺點(diǎn),許多學(xué)者提出了不同的改進(jìn)方法.[5-9]特別地,Thong等[9]提出了改進(jìn)的Tseng外梯度算法,其中算法步長γn是最大的γ ∈{α,αl,αl2,···}滿足γ∥F(xn)-F(yn)∥≤μ∥xn{-yn∥,其具體算法如下

其中α>0,μ,l ∈(0,1).在映射F是單調(diào)且Lipschitz連續(xù)(L未知)的條件下,Thong等[9]獲得了算法解的弱收斂定理.另一方面,在實(shí)際中許多函數(shù)并不滿足單調(diào)性這一較強(qiáng)假設(shè).因此,為了削弱單調(diào)性假設(shè)從而擴(kuò)大算法的適用性,慣性方法由于其具有良好的加速性質(zhì)受到許多學(xué)者的關(guān)注.[10-12]最近,Lzuchukwu等[14]提出了帶有慣性項(xiàng)的自適應(yīng)向前向后算法:

本文受到文[9,14] 的啟發(fā),在映射F是擬單調(diào)且Lipschitz連續(xù)的假設(shè)下,通過線搜索方法和慣性項(xiàng)的靈活構(gòu)造,證明了由該算法產(chǎn)生的序列弱收斂到變分不等式問題的解.最后給出了數(shù)值實(shí)驗(yàn)結(jié)果.本文所得的結(jié)果改進(jìn)和推廣了文[14]中相應(yīng)結(jié)果.

2.預(yù)備知識

記xn ?v(n →∞)為{xn}弱收斂于v.

定義2.1設(shè)F:H →H是一個映射.

(i) 如果〈F(u)-F(v),u-v〉≥0,?u,v ∈H,則稱F是單調(diào)的.

(ii) 如果〈F(v),u-v〉>0?〈F(u),u-v〉≥0,?u,v ∈H,則稱F是擬單調(diào)的.

(iii) 如果∥F(u)-F(v)∥≤L ∥u-v∥,?u,v ∈H,其中L是Lipschitz常數(shù)且L>0,則稱F是Lipschitz連續(xù)的.

注2.1顯然,(i)?(ii),但是反之不成立,見文[13].

定義2.2任給v ∈H,則在C中存在唯一的一點(diǎn),使得該點(diǎn)與v的距離最近,稱這個點(diǎn)為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]設(shè)C是H中非空子集,{xn}是H中任意序列,若滿足下面兩個條件:

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

(ii){xn}中每個子列的弱聚點(diǎn)都屬于C.

則{xn}弱收斂到C中的一個點(diǎn).

本文提出如下假設(shè):

(C1)SD非空;

(C2)映射F滿足: 當(dāng){xn}?C且{xn}?v?時,有∥F(v?)∥≤

(C3)映射F在H上是擬單調(diào)的;

(C4)映射F在C上是Lipschitz連續(xù)的.

3.提出的算法與收斂性證明

本文提出如下算法:

令n:=n+1,轉(zhuǎn)到步1.

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

(ii) 假設(shè)(C2)比文[6]中的弱序列連續(xù)性更弱.比如F(v)=v∥v∥,?v ∈C,滿足假設(shè)(C2),但是不滿足弱序列連續(xù)性.

引理3.1假設(shè)(C1)和(C4)成立,則線搜索準(zhǔn)則(3.2)滿足

證證明過程類似于文[9]中引理3.1的證明過程,故這里不再贅述.

引理3.2假設(shè)(C1)和(C4)成立,則線搜索準(zhǔn)則(3.2)有限步終止.

證考慮下面兩種情形.

情形一 若∥xn+1(γ)-xn∥=0,由假設(shè)(C4)知0≤∥F(xn+1(γ))-F(xn)∥≤L ∥xn+1(γ)-xn∥=0,則∥F(xn+1(γ))-F(xn)∥=0,故線搜索準(zhǔn)則(3.2)成立.

情形二 若∥xn+1(γ)-xn∥>0,用反證法證明.假設(shè)線搜索準(zhǔn)則(3.2)在有限步不終止,則對任意的mn有

對上式兩端同時除以μ得

對上式取極限mn →∞得0≥∥xn+1(γ)-xn∥,這與條件∥xn+1(γ)-xn∥>0矛盾,故線搜索準(zhǔn)則(3.2)在有限步終止.

為了證明主要的收斂結(jié)果,我們需要如下的兩個引理.

引理3.3設(shè){xn}是由算法3.1產(chǎn)生的序列,假設(shè)(C1)成立,則序列{x2n}是有界的.

證取z ∈SD,則z ∈S ?C.由引理2.1和2.2(i)知

上式等價于

上式結(jié)合(3.5)式有

由(3.2)式知

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

由引理2.2(ii)知

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

上式等價于

為表述方便,定義

引理3.4設(shè){xn}是由算法3.1產(chǎn)生的序列,假設(shè)(C1)-(C4)成立.如果v?是{x2n}的弱聚點(diǎn),則v?∈SD或F(v?)=0.

證證明過程由注3.2結(jié)合文[14]中引理6.2的證明過程,故這里不再贅述.

定理3.1設(shè){xn}是由算法3.1產(chǎn)生的序列,假設(shè)(C1)-(C3)成立,且F(x) =0,?x ∈C.則{xn}弱收斂于SD ?S中的一個元素.

存在.

假設(shè)W(x2n)是{x2n}的所有弱聚點(diǎn)組成的集合,下面證明

接下來證明弱收斂點(diǎn)是唯一的.先假設(shè){x2n}分別滿足x2n ?v?,n →∞和x2n ?x?,n →∞,下證v?=x?.

顯然v?=x?,即弱收斂點(diǎn)是唯一的.

由x2n ?x?∈SD知,對?z ∈H且z0有

結(jié)合上式與(3.20)得

所以x2n+1?x?∈SD ?S.

因此xn ?x?∈SD ?S.證畢.

注3.3本文從以下三個方面改進(jìn)了文[9]中的結(jié)論:

1)F的單調(diào)性弱化為擬單調(diào)性.

2) 算法3.1只需計算一次F的函數(shù)值,而文[9]的算法中需要計算兩次.

3) 算法3.1增加了交替慣性項(xiàng)使算法的收斂速度更快.

注3.4與文[14]中的算法1相比,算法3.1中對慣性項(xiàng)進(jìn)行了靈活的構(gòu)造且采用了線搜索準(zhǔn)則來動態(tài)地確定算法的步長,可以顯著提高算法的收斂速度,見例4.2.

4.數(shù)值實(shí)驗(yàn)

本節(jié)給出數(shù)值實(shí)驗(yàn),通過兩個例子將本文算法3.1與文[14]中的算法1以及文[9]中的算法2進(jìn)行比較.所有代碼均在MATLAB R2018a和Windows10系統(tǒng)下運(yùn)行,計算機(jī)基本參數(shù)為Intel(R)Core(TM)i5-8250U CPU@1.60GHz.其中“iter”表示程序迭代次數(shù),“CPU time”表示程序運(yùn)行時間,單位為秒.所有算法的終止條件為∥xn+1-xn∥2≤err(err為提前設(shè)定的誤差).

參數(shù)選取如下:

文[9]中的算法2: 設(shè)μ=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ù)的對角矩陣.取可行集

可知映射F在C上是單調(diào)且Lipschitz連續(xù)的,相應(yīng)的變分不等式的唯一解是{0}.在此情況下,我們對比了三種算法在不同維數(shù)p,q下的數(shù)值效果,見表4.1和圖4.1.

圖4.1 m=30時三種算法的對比

表4.1 err=10-10時不同算法關(guān)于維度的比較

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

可知映射F在C上是擬單調(diào)且Lipschitz連續(xù)的.相應(yīng)的變分不等式的解集是SD={-1}和S={-1,0}.在此情況下,我們對比了兩種算法在不同初始值和不同誤差情況下的數(shù)值效果,見表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時不同算法關(guān)于初始值的比較

注4.1從數(shù)值實(shí)驗(yàn)的結(jié)果來看,我們有如下結(jié)論:

(i) 三種算法都收斂于變分不等式的解,見表4.1.

(ii) 從CPU運(yùn)行時間來看,算法3.1都略優(yōu)于其它兩種算法,尤其是在例4.1中遠(yuǎn)勝于文[14]中的算法1,見表4.1.

(iii) 從迭代次數(shù)來看,算法3.1較其它兩種算法具有優(yōu)越性,尤其是在例4.2中隨著精度的增加仍然表現(xiàn)出很強(qiáng)的穩(wěn)定性,見表4.3.

表4.3 x0=1,x1=2時不同算法關(guān)于終止條件精度的比較

(iv) 算法3.1優(yōu)于文[14]中的算法1和文[9]中的算法2,在單調(diào)與擬單調(diào)的條件下同樣適用.