求解變分不等式問題的慣性次梯度外梯度算法

米特特， 方長杰

（重慶郵電大學(xué) 理學(xué)院，重慶400065）

考慮如下變分不等式問題（VIP），即尋找點x*∈C使得

其中，A：H→H是一個連續(xù)映射，H為Hilbert空間，C?H是H中的非空閉凸集，〈·，·〉和‖·‖分別表示H中的內(nèi)積和范數(shù).記Ω為變分不等式問題（VIP）的解集，即點x*∈Ω滿足上式.用PC（x）表示點x到非空閉凸集C上的投影，即PC（x）＝argy∈mCi n ‖x-y‖.

變分不等式理論已廣泛應(yīng)用于障礙問題、力學(xué)中的單邊問題、平衡問題等，參見文獻［1-3］及其參考文獻.為了探索和分析相關(guān)的收斂結(jié)果與誤差界，求解變分不等式問題（VIP）算法的研究引起了許多學(xué)者的關(guān)注.例如外梯度算法［4］、次梯度外梯度算法［5-6］.另外，慣性算法在近些年也引起了大家的興趣，參見文獻［7-8］.

最近，Thong等［8］提出了求解變分不等式問題（VIP）的如下算法：

在映射A是單調(diào)且Lipschitz連續(xù)的假定下，證明了上述算法所產(chǎn)生的迭代序列｛xn｝強收斂到點p∈Ω，其中p＝PΩ?f（p）.

另外，Migórski等［9］提出了求解變分不等式問題（VIP）一種新的次梯度外梯度算法：

其中在映射A是單調(diào)且Lipschitz連續(xù)的假定下（Lipschitz常數(shù)不需要知道），他們證明了算法迭代所產(chǎn)生的序列｛xn｝強收斂到點p∈VI（C，A），其中p＝PVI（C，A）?f（p）.

Bot等［10］提出了Hilbert空間中求解變分不等式問題（VIP）的如下Tseng向前向后算法：

在映射為偽單調(diào)，Lipschitz連續(xù)且序列弱-弱連續(xù)的假定下，他們證明了由上述算法所產(chǎn)生的迭代序列｛xn｝弱收斂到點p∈Ω.

從以上工作中得到啟發(fā)，本文提出了求解變分不等式問題的一種慣性次梯度外梯度算法，并且在映射A是偽單調(diào)，Lipschitz連續(xù)的（Lipschitz常數(shù)不需要知道）且序列弱-弱連續(xù)的假定下，證明了算法所產(chǎn)生的迭代序列｛xn｝強收斂到點p∈Ω，其中p＝PΩ?f（p）.最后通過數(shù)值實驗將所提的算法與文獻［9］中的算法1和文獻［8］中的算法3.1進行了比較.與此同時，在文獻［8-9］中，映射A假定是單調(diào)的，而在我們的算法中，映射A只需要是偽單調(diào)的.相比較文獻［10］中的弱收斂性，得到了強收斂性的結(jié)果.

1 預(yù)備知識

本節(jié)將介紹一些將在下文中使用的引理.首先，有如下定義.

1）xn→x表示序列｛xn｝弱收斂到x；

2）xn→x表示序列｛xn｝強收斂到x.

定義1.1 設(shè)A：H→H為映射算子，則：（i）稱A是單調(diào)的，如果

（ii）稱A是偽單調(diào)的，如果對于?x，y∈H，都有

（iii）稱映射A是Lipschitz連續(xù)的，如果存在常數(shù)L＞0滿足下式

（iv）稱算子A是序列弱-弱連續(xù)的，如果對任意的序列｛xn｝弱收斂到x，則序列｛Axn｝弱收斂到Ax.

注1.1 在定義1.1（iii）中，如果L∈［0，1），則映射A稱為壓縮映射.

引理1.1［11］設(shè)H為實Hilbert空間，則有：

在證明以下算法2.1的收斂性時，以下2個引理起著十分重要的作用.

引理1.2［12］設(shè)｛an｝和｛αn｝為非負(fù)實序列且αn∈（0，1），∑∞n＝0αn＝ ∞.如果存在序列｛bn｝，limn→s∞u pbn≤0，當(dāng)N＞0時使得an+1≤（1-αn）an+αnbn，?n≥N成立，則有l(wèi)iman＝0.

2 主要結(jié)果

3 數(shù)值實驗

本節(jié)將對所提出的算法進行了一些對比數(shù)值實驗.MATLAB代碼運行在PC（AMD酷睿（TM）A8-4500M APU＠1.90 GHz）下，在Matlab版本8.4.0.150421（R2014b）Service Pack 1上運行.當(dāng)‖xn-x*‖≤ε時，迭代停止.用“ISEA”“iTEM”“MSEM”分別表示本文中算法2.1、文獻［8］中算法2.1和文獻［9］中算法1.

例3.1 設(shè)H＝Rn，n＝10且

定義映射A：Rn→Rn為A（x）＝Mx+d.M由下式隨機生成：

其中，N是n×n階矩陣，B是n×n階斜對稱矩陣，且矩陣N和B中的元素都屬于（-2，2）.矩陣D是n×n階對角矩陣，且對角線元素取值范圍為［0，2］.所以易證矩陣M是正定矩陣.方便起見，選取向量d為零向量.

例3.1能在文獻［18］中發(fā)現(xiàn)，其中算子A為單調(diào)的.由于矩陣M是正定矩陣，所以A是L-Lipschitz連續(xù)的且L＝‖M‖.取f（x）：＝x/2.迭代初始點為x0＝x1＝（1，0，…，0）∈Rn，容易證明x*＝0是變分不等式問題（VIP）的解.進一步，選取λ0＝τ＝0.9，μ＝0.5以及

針對文獻［8］中算法2.1，取λ＝0.8，αn、βn和上述相同.針對文獻［9］中算法1，選取αn＝0.53，γ＝0.4，λ0＝0.7.數(shù)值對比結(jié)果圖參見圖1.

圖1 例3.1中‖x n-x*‖隨時間變化曲線圖Fig.1 Time curve corresponding to‖x n-x*‖in Example 3.1

定義范數(shù)為

圖2 例3.2中‖x n-x*‖隨時間變化曲線圖Fig.2 Time curve corresponding to‖x n-x*‖in Example 3.2