求解變分不等式問題和不動點問題公共點的慣性次梯度外梯度算法

黃 瑕， 夏福全， 張雙德

（四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川成都610066）

0 引言

設(shè)H是Hilbert空間，〈·，·〉和‖·‖分別表示H中的內(nèi)積和范數(shù)，C?H是一個非空閉凸集，映射F：H→H.經(jīng)典的變分不等式問題為：求x*∈C，使得

為簡單起見，記變分不等式問題（1）為VI（C，F(xiàn)），VI（C，F(xiàn)）的解集為SOL（C，F(xiàn)）.設(shè)映射S：C→C為非擴(kuò)張映射，即

用Fix（S）表示S的不動點集合，即Fix（S）＝｛x∈C：S（x）＝x｝.

本文考慮的問題為：求x*∈C，使得

為了在Hilbert空間中求Fix（S）與SOL（C，F(xiàn)）的公共點，很多學(xué)者提出多種迭代算法［1-8］.在2006年，Nadeshkine等［4］提出了一種求Fix（S）與SOL（C，F(xiàn)）的公共點的迭代算法其中，F(xiàn)：H→H為單調(diào)Lipschitz連續(xù)映射，Lipschitz常數(shù)為L＞0，且在

S：C→C為非擴(kuò)張映射的條件下，證明如果Fix（S）∩SOL（C，F(xiàn)）≠?，由該算法生成的序列｛xn｝弱收斂到z∈SOL（C，F(xiàn)）∩Fix（S）.注意到，該算法在每次迭代過程中都會計算2次到C上的投影，如果C是一般的非空閉凸集，投影難以實現(xiàn).Censor等［7］提出的修正的次梯度外梯度算法6.1，改進(jìn)了（4）式.他們將（4）式中第二個到C上的投影替換成到一個特定的半空間Tn上的投影，而在Tn上的投影有顯示表達(dá)式，容易計算.其算法（記為算法1）具體迭代如下：

Censor等［7］在SOL（C，F(xiàn)）非空和F是單調(diào)Lipschitz連續(xù)映射的條件下證明了該算法生成的序列｛xn｝弱收斂到Fix（S）與SOL（C，F(xiàn)）的公共點.

近年來，慣性型算法的研究備受人們的關(guān)注.慣性型算法起源于“帶摩擦的重球”動力系統(tǒng)，詳見文獻(xiàn)［9-10］，其主要特點是利用上一步迭代點以及當(dāng)前迭代點，通過迭代獲得下一步迭代點，目的是加快收斂速度［11-13］.許多學(xué)者將慣性算法應(yīng)用到不同的問題上，比如針對某些可分離的非凸優(yōu)化問題.Ochs等［14］提出了慣性forward-backward分裂法；針對強(qiáng)凸問題，Ochs等［15］提出了慣性近似算法；針對變分不等式問題，Dong等［16］提出了慣性收縮算法.

受以上文獻(xiàn)研究成果的啟發(fā)，本文將Censor等［7］介紹的修正的次梯度外梯度算法與慣性算法相結(jié)合，提出一種解變分不等式問題解集與非擴(kuò)張映射不動點集的公共點的慣性次梯度外梯度算法，并且在一定的條件下，證明由該算法生成的序列弱收斂到Fix（S）與SOL（C，F(xiàn)）的公共點.

1 預(yù)備知識

用xn→x表示序列｛xn｝∞n＝0強(qiáng)收斂到x，用xn?x表示序列｛xn｝∞n＝0弱收斂到x.首先給出本文會用到的定義和引理.

定義1.1設(shè)C?H為非空閉凸集，對?x∈H，定義

為x在C上的投影.

引理1.1［17］設(shè)C?H為非空閉凸集，x∈H，則

引理1.2［18］設(shè)H為Hilbert空間，則

引理1.3［18］設(shè)C?H為非空閉凸集，T：C→C是一個非擴(kuò)張映射，且Fix（T）≠?.如果C中序列｛xn｝滿足則有z＝T（z）.

定義1.2設(shè)映射F：H→H，映射S：C→C，其中C?H為非空閉凸集，稱F在集合C上是：

1）L-Lipschitz連續(xù)的，如果存在常數(shù)L＞0，滿足

2）單調(diào)的，如果

定義1.3令A(yù)：H→→2H是實Hilbert空間中的一個集值映射.如果A是單調(diào)的，即

〈w-v x-y〉≥0， ?w∈A（x），v∈A（y），且A的圖G（A）：＝｛（x，w）∈H×H：w∈A（x）｝沒有包含在任何其他單調(diào)算子的圖中，則稱A是極大單調(diào)算子.

很明顯，A是極大單調(diào)算子當(dāng)且僅當(dāng)對任意（x，w）∈H×H，如果〈w-vx-y〉≥0，?（v，y）∈G（A），則有w∈A（x）.

引理1.4［19］設(shè)｛φn｝、｛δn｝和｛αn｝是［0，+∞）中的序列，滿足

且對任意n≥1，存在一個實數(shù)α滿足0≤αn≤α＜1，則以下結(jié)論成立：

引理1.5［20］設(shè)C?H為非空閉凸集，｛xn｝是H中的一個序列，滿足以下2個條件：

2）｛xn｝的每個序列弱聚點都在C中.則｛xn｝弱收斂到C中一點.

2 算法及收斂性分析

設(shè)序列｛αn｝是非減的，0≤αn≤α＜1，選取σ，δ＞0，滿足

設(shè)序列｛βn｝滿足

注1顯然有βn∈（0，1）.

算法2選擇初始點x0，x1∈H，τ＞0，

假設(shè)以下條件成立.

條件2.1F：H→H是單調(diào)映射.

條件2.2F：H→H是Lipschitz連續(xù)映射，其Lipschitz常數(shù)為L＞0.

條件2.3Fix（S）∩SOL（C，F(xiàn)）≠?.

定理2.1假設(shè)條件2.1-2.3成立，則當(dāng)0＜時，由算法2生成的序列｛xn｝弱收斂于SOL（C，F(xiàn)）∩Fix（S）中的一點.

證明 令u∈SOL（C，F(xiàn)）∩Fix（S），由引理1.1以及F的假設(shè)條件有

因為F是單調(diào)的，可得

因為u∈SOL（C，F(xiàn)）∩Fix（S），可得

所以

而

由Tn的定義以及tn∈Tn，可得

因此

由（10）和（11）式可得

由（6）、（8）、（9）及（13）式有

由（6）式可得

又

經(jīng)整理后，可得

其中

根據(jù)ρn的定義，有

由（19）式以及βn∈（0，1），可得

分別定義序列

結(jié)合｛αn｝的單調(diào)性和φn≥0，有

由（18）式可得

根據(jù)δ和σ的選取以及βn所滿足的條件，可以證明

事實上，根據(jù)ρn的定義有

由（20）式知

又因為

可得（23）式中最右邊的不等式成立，因此，（22）式成立.

由（21）和（22）式得

故序列｛ξn｝是非增的.又｛αn｝是有界的，得

從而有

結(jié)合（24）和（25）式，有

從而

因此

又由（18）式得

因為ρnαn＜1，可得

由引理1.4知存在，可推出｛xn｝是有界的.又

由（26）式可得

進(jìn)而有

又

可得

因此，序列｛wn｝也是有界的.

因此，序列｛tn｝也是有界的.由（12）式，可得

由（28）式可得

又序列｛xn｝是有界的，則存在子序列｛xn j｝弱收斂于＾x.此外，也可得相應(yīng)子序列｛wn j｝、｛yn j｝也弱收斂于＾x.

接著證明＾x∈SOL（C，F(xiàn)）∩Fix（S）.定義算子

其中NC（v）稱為C在v處的法錐，即

易知A（v）是極大單調(diào)算子，且A-1（0）＝SOL（C，F(xiàn)）.

如果（v，w）∈G（A），則w-F（v）∈NC（v），有由yn j∈C，可得

由yn的定義和引理1.1，可得

或

因此，有

對（30）式兩邊關(guān)于j→∞取極限，得

因A是極大單調(diào)的，可得0∈A（＾x），即

又

有

由（27）式可得

又

可得

應(yīng)用引理1.3，有＾x∈Fix（S），故

1）對任意p‖存在；

2）如果xn j?p，有p∈SOL（C，F(xiàn)）∩Fix（S）.由引理1.5知｛xn｝弱收斂于SOL（C，F(xiàn)）∩Fix（S）中的一點.

3 數(shù)值結(jié)果

本節(jié)給出算法1和算法2在以下一個簡單例子中的計算機(jī)檢驗結(jié)果.這些結(jié)果都是用Matlab R2017a在CPU型號為Intel（R）Core（TM）i5-3230M（雙核，主頻為2.60 GHz）和內(nèi)存為4.0 GB的筆記本電腦上運行的.算法1和算法2選取的參數(shù)一致，均取0.4.算法的終止條件為max｛‖wn-tn‖，‖wn-xn+1‖｝≤?，分別取?＝10-4，?＝10-6和?＝10-8作為算法的停止標(biāo)準(zhǔn).用CPU記運行所花費的時間，用iter記迭代的步數(shù).

例1定義C＝｛x∈R2｜e0≤x≤e1｝，其中e0＝（-10，-10），e1＝（10，10）.設(shè)映射F：R2→R2，映射S：R2→R2，

容易證明（詳見文獻(xiàn)［16］），F(xiàn)是單調(diào)且Lipschitz連續(xù)的映射.以（1，3）為初始點，通過改變例子中?的取值來對比算法1與算法2，例子的數(shù)值結(jié)果見表1.

表1 數(shù)值結(jié)果Tab.1 The numerical result

注2從表1的數(shù)值實驗結(jié)果來看，在相同的精度條件下，算法2迭代的步數(shù)比算法1的少，運行所花費的時間也比算法1少.