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

聶佳琳,龍憲軍

(重慶工商大學數學與統計學院,重慶 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,在單調與擬單調的條件下同樣適用.