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

唐艷周海云荊平

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

1 引言

眾所周知,變分不等式

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

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

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

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

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

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

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

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

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

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

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

2 預備知識

3 自適應步長慣性投影法

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

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

并記問題(8)的解集為

3.1 算法 3.1及弱收斂定理

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

3.2 算法 3.2及強收斂定理

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

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

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

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

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

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

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

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

5 結(jié)語

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