解變分不等式問題的一種半壓縮慣性投影算法

陳晶晶，王圓圓，楊延濤

（延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 延安 716000）

設(shè)H為實(shí)的Hilbert空間，和‖?‖分別表示H中的內(nèi)積和范數(shù)，C?H為非空閉凸子集，A：H→H是一個(gè)給定的映像，經(jīng)典變分不等式問題VI(C，A)就是尋求一 點(diǎn)x?∈C，滿足不等式A(x?)，x-x?≥0，?x∈C。如果A：H→H是一個(gè)單調(diào)映像，即Ax-Ay，x-y≥0，?x，y∈H，則稱變分不等式問題為單調(diào)變分不等式。

文獻(xiàn)［1-9］研究了變分不等式理論在解決科學(xué)問題中的應(yīng)用；文獻(xiàn)［10-12］提出了求解變分不等式問題的收縮投影算法；文獻(xiàn)［13-15］提出了求解變分不等式問題的次梯度超梯度算法；文獻(xiàn)［16-18］介紹了帶慣性項(xiàng)算法的起源及應(yīng)用；文獻(xiàn)［19-20］研究了不動(dòng)點(diǎn)集與變分不等式解集的公共元問題。

文獻(xiàn)［11］提出了求解變分不等式問題的慣性收縮投影算法：

并在適當(dāng)?shù)臈l件下證明了由迭代序列產(chǎn)生算法的弱收斂性。

最近文獻(xiàn)［13］引入了一種λ-半壓縮映像，證明了求解變分不等式問題的強(qiáng)收斂性，使得迭代算法更具有效性和實(shí)用性。本文受文獻(xiàn)［4，11-13］的啟發(fā)，提出了一種半壓縮慣性投影算法，用以尋找?guī)в邪雺嚎s映像的不動(dòng)點(diǎn)集與單調(diào)變分不等式解集的公共元。使用新的分析技巧，證明了所提出的算法強(qiáng)收斂于該公共元。最后，通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了該迭代算法的有效性和實(shí)用性。

1 預(yù)備知識(shí)

設(shè)H為實(shí)Hilbert空間，H中的內(nèi)積和范數(shù)分別表示為和‖?‖。用xn?x表示序列{xn}弱收斂到x，xn→x表示序列{xn}強(qiáng)收斂到x。設(shè)C為H中的非空閉凸子集，則?x∈H，C中存在唯一的最近點(diǎn)，用PC(x)表示，即。Fix(T)表示λ-半壓縮映像T：H→H的不動(dòng)點(diǎn)集，即Fix(T)={x∈H|T(x)=x}。

定義1.1［3］I-T在原點(diǎn)是次閉的：假設(shè)T：H→H為非線性算子并且Fix(T)≠?，若對(duì)?{xn}?H，滿足xn?x且(I-T)xn→0，則有x∈Fix(T)。

定義1.2［4］對(duì)映像A：H→H稱為

i）L-Lipschitz連續(xù)，如果存在常數(shù)L>0，滿足‖Ax-Ay‖≤L‖x-y‖，?x，y∈H；

ii）單調(diào)的，如果Ax-Ay，x-y≥0，?x，y∈H；

iii）λ-半壓縮，如果存在常數(shù)0≤λ≤1，對(duì)?x，y∈H，z∈Fix(A)，

引理1.1［5］設(shè)H為實(shí)的Hilbert空間，則

引理1.2［6］設(shè)C為H中的非空閉凸子集。對(duì)于距離投影PC：H→C有

引理1.3［7］設(shè){bk}為非負(fù)實(shí)序列，且存在子序列使得對(duì)?j∈N都成立，則存在非遞減序列使得，并且對(duì)k∈N充分大時(shí)都滿足如下性質(zhì)

其中mk是集合{1，2，…，k}中的最大數(shù)n，使得滿足bn

引理1.4［8］設(shè){an}和{θn}為非負(fù)實(shí)序列且{θn}。如果存在序列0，當(dāng)N>0時(shí)使得成立，則有。

引理1.5［9］假設(shè)T：H→H是λ-半壓縮的滿足。令Tη=ηT+(1-η)I，其中I是恒等映像，η∈(0，1-λ)，則有

iii）Fix(T)是一個(gè)閉凸集。

2 主要結(jié)果

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

（C1）算子A：H→H是L-Lipschitz連續(xù)的單調(diào)映像；

（C2）算子T：H→H是λ-半壓縮映像以及IT在原點(diǎn)次閉；

（C3）Fix(T)∩VI(C，A)≠?；

（C4）設(shè){εn}和{βn}為正序列，使得=0，并且序列{θn}?(0，1)，=0，，序 列{βn}滿 足{βn}?(a，b)?(0，(1-λ)(1-θn))，其中a>0，b>0。

算法2.1一種半壓縮慣性投影算法

步驟1選取初始點(diǎn)x0，x1∈C，令n=1。計(jì)算

步驟2計(jì)算yn=PC(wn-τn Awn)，其中τn為使τ∈{γ，γl，γl2，…}成立的最大的τ，參數(shù)γ>0，l∈(0，1)并且滿足，

步驟3計(jì)算dn=wn-yn-τn(Awn-Ayn)；

步驟4計(jì)算zn=wn-αηndn，

步驟5計(jì)算

步驟6令n=n+1且返回步驟1。

引理2.1［22］假設(shè)（C1）-（C3）成立，根據(jù)Armijo搜索程序有。

引理2.2設(shè){zn}由算法2.1迭代產(chǎn)生，假設(shè)(C1)成立，對(duì)于u∈VI(C，A)，有

證明由A的單調(diào)性及u∈VI(C，A)得

由zn，dn的定義，yn=PC(wn-τn Awn)，式（5）及引理1.2得

使用Cauchy-Schwarz不等式、dn的定義及式（2）得

由dn的定義、三角不等式‖x+y‖≤‖x‖+‖y‖及式（2）得

將式（7）與式（8）代入式（3）得

由zn的定義可得

將式（3）代入式（6），結(jié)合式（10）得

結(jié)合式（7）與式（9）得

定理2.1假設(shè)(C1)-(C4)成立，則由算法2.1產(chǎn)生的迭代序列{xn}依范數(shù)強(qiáng)收斂到

證明第一步證明序列{xn}、{wn}、{zn}有界。

利用引理2.2得

故?M1>0使得

由式（11）、式（13）和wn的定義得

使用xn+1的定義及三角不等式‖x+y‖≤‖x‖+得

由式（11），λ-半壓縮映像性質(zhì)以及βn?(0，(1-λ)(1-θn))得

將式（14）與式（16）代入式（15）得

因此序列{xn}是有界的，則{wn}和{zn}有界。

第二步證明

使用xn+1的定義、定義1.2、引理1.1及{xn}有界得

由引理1.1得

由引理2.2、式（19）及式（20）得

整理得

第三步證明

令Sn=(1-βn)zn+βnTzn，利用λ-半壓縮映像性質(zhì)，有

結(jié)合式（11）與式（22），有

由Sn=(1-βn)zn+βnTzn，有

使用xn+1的定義、引理1.1、Cauchy-Schwarz不等式、式（23）及式（24），有

情形1假設(shè)?N∈N，有，?n≥N。

由式（12）與式（18），有

使用引理2.2，有

結(jié)合式（12），有

故由‖wn-zn‖→0，有

使用三角不等式及式（28）得

使用wn的定義、Cauchy-Schwarz不等式以及式（1），有

結(jié)合式（21）與式（30），有

式（31）也可寫為

由于{xn}是有界的，則存在{xn}的子序列{xnj}有xnj?p，

由式（27）與式（33），有wnj?p。

下證p∈VI(C，A)。

由yn=PC(wn-τn Awn)，引理1.2得

由式（26）與式（34）得

由于wnj?p，故有

使用式（25）、式（36）及定義1.1得p∈Fix(T)，因此p∈Fix(T)∩VI(C，A)。

由u的定義得，

再使用式（32）與引理1.4得

因此證得xn→u，n→∞。

由引理1.3知存在一個(gè)非減序列{mk}有

由式（12）與式（18），有

再使用引理2.2，有

由式（12）、式（31）及式（37）得

3 數(shù)值實(shí)驗(yàn)

本節(jié)將對(duì)所提出的算法與已有算法進(jìn)行了一些對(duì)比數(shù)值實(shí)驗(yàn)。所有代碼均在MATLAB R2016a和windows10系統(tǒng)下運(yùn)行，當(dāng)‖xn-x?‖≤ε時(shí)，迭代停止。用“IPCM”、“TEGM”、“TIPCM”分別表示文獻(xiàn)［11］中的算法3.1、［22］中的算法2及本文的算法2.1。

例3.1定義算子A：Rn→Rn為A(x)=Mx+q，M=NNT+P+D，其中N是n×n階矩陣，P是n×n階斜對(duì)稱矩陣，D是n×n階對(duì)角矩陣，定義算子T：H→H為Tx=。

由此可見算子A是單調(diào)的并且Lipschitz連續(xù)，L=‖M‖，算子T：H→H為λ-半壓縮映像并且在原點(diǎn)次閉，當(dāng)可行集C={x=(x1，x2，…，x50)∈R50：-2≤xi≤2，i=1，2，…，50}時(shí)

即x?=(0，0，…，0)T。

例3.1來(lái)源于文獻(xiàn)［23］，選取ε為10-7迭代初始點(diǎn)為x0=x1=(1，1，…，1)T，矩陣N和P中的元素在[-2，2]隨機(jī)取值，對(duì)角矩陣D的對(duì)角元素在(0，2)中取值，選取q=0。

數(shù)值對(duì)比結(jié)果見圖1。

圖1 例3.1中‖xn-x*‖隨迭代時(shí)間變化圖

例3.2設(shè)H為實(shí)數(shù)空間，C?[-1，1]?H，定義算子A：H→H為，算子T：H→H為。

由此可見算子A是單調(diào)的并且Lipschitz連續(xù)，T為λ-半壓縮映像(λ∈(0，1))并且在原點(diǎn)次閉，F(xiàn)ix(T)∩VI(C，A)={0}即不動(dòng)點(diǎn)集與單調(diào)變分不等式解集的公共元為x*=0。

對(duì)例3.2選取ε為10-8，迭代初始點(diǎn)為

數(shù)值對(duì)比結(jié)果見圖2。

圖2 例3.2中‖xn-x*‖隨迭代次數(shù)變化圖

通過(guò)對(duì)算法2.1的數(shù)值實(shí)驗(yàn)結(jié)果與文獻(xiàn)［11］及［22］中的數(shù)值實(shí)驗(yàn)結(jié)果對(duì)比（見圖1，圖2），可以看出半壓縮慣性投影算法優(yōu)于IPCM算法和TEGM算法，并且在不需要預(yù)先知道Lipschitz常數(shù)的條件下，證明了算法2.1的強(qiáng)收斂性。由此進(jìn)一步驗(yàn)證了算法2.1的有效性和實(shí)用性。

4 結(jié)論

本文結(jié)合半壓縮映像和慣性收縮投影方法，借助Armijo線性搜索程序獲取步長(zhǎng)，提出了一種求解單調(diào)變分不等式問題的半壓縮慣性投影算法，用以尋找?guī)в邪雺嚎s映像的不動(dòng)點(diǎn)集與單調(diào)變分不等式解集的公共元。該算法的優(yōu)點(diǎn)是不需要預(yù)先知道Lipschitz常數(shù)，證明了所提的迭代算法強(qiáng)收斂于該公共元，同時(shí)通過(guò)數(shù)值實(shí)驗(yàn)證明了本文所提迭代算法的有效性。本文所得結(jié)論是對(duì)現(xiàn)有文獻(xiàn)結(jié)論的改進(jìn)和推廣。