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

黃 瑕， 夏福全， 張雙德

（四川師范大學 數學科學學院，四川成都610066）

0 引言

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

為簡單起見，記變分不等式問題（1）為VI（C，F），VI（C，F）的解集為SOL（C，F）.設映射S：C→C為非擴張映射，即

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

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

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

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

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

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

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

1 預備知識

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

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

為x在C上的投影.

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

引理1.2［18］設H為Hilbert空間，則

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

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

1）L-Lipschitz連續的，如果存在常數L＞0，滿足

2）單調的，如果

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

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

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

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

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

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

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

2 算法及收斂性分析

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

設序列｛βn｝滿足

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

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

假設以下條件成立.

條件2.1F：H→H是單調映射.

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

條件2.3Fix（S）∩SOL（C，F）≠?.

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

證明 令u∈SOL（C，F）∩Fix（S），由引理1.1以及F的假設條件有

因為F是單調的，可得

因為u∈SOL（C，F）∩Fix（S），可得

所以

而

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

因此

由（10）和（11）式可得

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

由（6）式可得

又

經整理后，可得

其中

根據ρn的定義，有

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

分別定義序列

結合｛αn｝的單調性和φn≥0，有

由（18）式可得

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

事實上，根據ρn的定義有

由（20）式知

又因為

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

由（21）和（22）式得

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

從而有

結合（24）和（25）式，有

從而

因此

又由（18）式得

因為ρnαn＜1，可得

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

由（26）式可得

進而有

又

可得

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

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

由（28）式可得

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

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

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

易知A（v）是極大單調算子，且A-1（0）＝SOL（C，F）.

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

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

或

因此，有

對（30）式兩邊關于j→∞取極限，得

因A是極大單調的，可得0∈A（＾x），即

又

有

由（27）式可得

又

可得

應用引理1.3，有＾x∈Fix（S），故

1）對任意p‖存在；

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

3 數值結果

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

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

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

表1 數值結果Tab.1 The numerical result

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