求解變分不等式問題的一類新型算法及其應(yīng)用

唐艷周海云荊平

(1.重慶工商大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 400067;2.中國人民解放軍陸軍工程大學(xué)數(shù)學(xué)學(xué)院,河北 石家莊 050003;3.四川大學(xué)數(shù)學(xué)學(xué)院,四川 成都 610065)

1 引言

眾所周知,變分不等式

是偏微分方程,網(wǎng)絡(luò)平衡問題,互補(bǔ)性問題等非線性問題的核心,可應(yīng)用于經(jīng)濟(jì)領(lǐng)域的均衡問題,運(yùn)籌學(xué)問題及城市交通網(wǎng)絡(luò)建模問題等.變分不等式(1)的解集通常記作V I(C,A).

在求解變分不等式(1)的過程中,人們提出了多種迭代算法,具體來看主要有兩大類.一是投影法.Goldstein[1]首先提出了Goldstein-Levitin-Polyak投影方法:

其中PC是到C上Euclidean最小距離投影.假設(shè)算子A是Lipschitz連續(xù)強(qiáng)單調(diào)的,那么投影方法(2)收斂.1976年,在一般單調(diào)性假設(shè)下,Korpelevich[2]提出了外梯度投影方法:

該方法保證了序列的收斂性.但是,如果C是一般的閉凸集,方法(3)需要較高的計(jì)算成本.為此,Tseng[3]提出了一種新型梯度投影方法:

如果V I(C;A),則通過方法(4)生成的序列弱收斂到V I(C;A)中的某個(gè)元素.關(guān)于投影梯度法的更多細(xì)節(jié)和結(jié)果,還可以參考Thong和Hieu等人[4]的描述.

二是慣性算法.慣性法的描述來源于Alvarez和Attouch等[5]對二階動力系統(tǒng)的重球法.受此思想的影響,Bot和Csetnek,Solodov等提出了慣性混合逼近迭代算法[6-8].此方法在一定程度上可以加快算法的收斂速度,目前已經(jīng)受到了越來越多學(xué)者的關(guān)注.

雖然關(guān)于變分不等式(1)的研究已經(jīng)獲得了不少的成果,但在現(xiàn)實(shí)生活中,人們更傾向于尋找變分不等式(1)和非線性算子不動點(diǎn)問題的公共解,即,找到點(diǎn)u∈C使得

其中T:C→C是一個(gè)非線性算子,F(T)={x:Tx=x}是T的不動點(diǎn)集.

信號處理、經(jīng)濟(jì)規(guī)劃、網(wǎng)絡(luò)資源分配和圖像恢復(fù)等均可以描述為問題(5).目前,關(guān)于問題 (5)的研究,主要集中在兩點(diǎn).一是非線性算子T的類型,從 Alakoya[9],Dong[10],Zhou[11-12]等眾多文獻(xiàn)構(gòu)造的不同迭代算法來看,涉及的非線性算子主要為非擴(kuò)張算子及擬非擴(kuò)張算子;二是迭代算法的創(chuàng)新構(gòu)造及收斂性分析.另外,大部分迭代算法生成的序列只得到弱收斂的結(jié)果.

因此,自然地提出了以下這個(gè)問題:(Q)能否建立新的方法更快更好地強(qiáng)收斂于更廣義的非線性算子不動點(diǎn)問題與變分不等式問題的公共解呢？

受Thong[4],Alakoya[9],Dong[10],Gibali[13]等研究成果的啟發(fā),本文將繼續(xù)致力于問題(5)的數(shù)值求解并對上面的問題給予肯定的回答.

2 預(yù)備知識

3 自適應(yīng)步長慣性投影法

在這個(gè)部分,基于Tseng新型梯度投影方法和Halpern迭代算法,針對半壓縮映射不動點(diǎn)問題與變分不等式問題的公共解問題,提出兩個(gè)新的慣性型投影算法.另外,假設(shè)H是一個(gè)實(shí)Hilbert空間,C是H的非空閉凸子集.設(shè)A:H→H是單調(diào)Lipschitz連續(xù)算子.設(shè)T:H→H是一個(gè)τ-半壓縮映射且0<τ<1.

半壓縮映射不動點(diǎn)問題與變分不等式問題的公共解,是指,找到點(diǎn)u∈C使得

并記問題(8)的解集為

3.1 算法 3.1及弱收斂定理

由于Armijo搜索方法可以使步長不依賴于Lipschitz常數(shù),因此在Tseng新型梯度投影方法和慣性型投影算法的基礎(chǔ)上結(jié)合Armijo搜索方法提出了下面的算法3.1并研究了其弱收斂性.

3.2 算法 3.2及強(qiáng)收斂定理

由于算法3.1產(chǎn)生的序列只能弱收斂于問題的解,而在實(shí)際應(yīng)用中,強(qiáng)收斂性的需求更為迫切.所以在這個(gè)部分,結(jié)合Tseng新型梯度投影方法,Halpern迭代算法和慣性型投影算法提出了下面的算法3.2,并對其強(qiáng)收斂性做了分析.

4 數(shù)值仿真及比較

為了評估本文算法的性能,將給出數(shù)值實(shí)驗(yàn)來進(jìn)行仿真、演示和比較.

例 4.1本例中考慮一個(gè)Harker[17]等人研究過的互補(bǔ)問題,該問題也曾多次被其他學(xué)者仿真過,比如,Hieu[18]等.設(shè)算子A:Rm→Rm定義為Ax=Mx+q,其中q∈Rm.M=NNT+S而N是一個(gè)m×m矩陣,S是一個(gè)m×m斜對稱矩陣.顯然A是單調(diào) Lipschitz連續(xù)的,其 Lipschitz常數(shù)L=∥M∥.設(shè)算子T:Rm→Rm定義為,則它為的半收縮映射.另設(shè)可行集C?Rm為C:={x∈Rm|∥x∥≤r},其中r是隨機(jī)選擇的半徑.

本例將對算法3.1,算法3.2,Thong[4]的自適應(yīng)Tseng外梯度法,Shehu[19]的次梯度 -外梯度粘性方法在?=0.001,μ=0.1和?=0.01,μ=0.2及m=20,50,100等不同情況下進(jìn)行比較.本例設(shè)置Dk=∥xk+1?xk∥≤10?4作為停止標(biāo)準(zhǔn).圖1和表1列出了每種方法的收斂情況.

圖1 算法3.1,算法3.2,Thong[4]算法及Shehu[17]算法,m=100.

表1 例1-數(shù)值結(jié)果

注 4.1從圖1和表1可看出,因?yàn)楸疚奶岢龅乃惴?.1,算法3.2加入了慣性項(xiàng),所以收斂速度遠(yuǎn)高于文獻(xiàn)[4,19]所列的算法;同時(shí),基于相同的停機(jī)準(zhǔn)則,本文的算法能夠達(dá)到更高的精確度;另外,值得強(qiáng)調(diào)的是,相比文獻(xiàn)[4,19]的單調(diào)算子,本文研究的偽單調(diào)算子可應(yīng)用于解決更廣泛的問題.綜上,本文提出的算法3.1,算法3.2是可行的,也表明慣性算法在一定程度上會有更快更好的收斂結(jié)果.

5 結(jié)語

本文基于著名的測度投影算法和慣性算法,在Hilbert空間中給出了變分不等式問題與非線性算子不動點(diǎn)問題公共數(shù)值解的兩種新迭代方法,并在一定的條件下,證明了算法的強(qiáng)、弱收斂性.另外,分別在有限維空間和無限維空間中進(jìn)行了具體的數(shù)值仿真實(shí)驗(yàn),其中包含互補(bǔ)問題的仿真實(shí)驗(yàn)數(shù)據(jù),驗(yàn)證了所列出的算法的有效性和潛在的實(shí)用性.通過和已有的某些算法比較,可以看到,本文所列出的算法有兩個(gè)優(yōu)點(diǎn):(1)適用于半壓縮映射類,這類映射比現(xiàn)有文獻(xiàn)中的非擴(kuò)張映射,直接映射及擬偽壓縮映射等非線性映射更為廣義;(2)使用的步長不需要預(yù)先估算Lipschitz常數(shù),這意味著收斂速度會更快.在后續(xù)研究中,將著力于空間的改進(jìn),例如在更一般的Banach空間上研究變分不等式問題的解.