王霄婷， 龍憲軍， 彭再云

（1. 重慶工商大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 400067；2. 重慶交通大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 400074）

引 言

設(shè) H 是具有內(nèi)積 〈·,·〉和范數(shù) ‖·‖的實(shí) Hilbert 空間， C?H 是一個(gè)非空閉凸子集， F : H→H 是一個(gè)非線性算x?∈C 子.本文考慮的變分不等式問題是：尋找 ，滿足

記問題(1)的解集為 Sol(C,F).

變分不等式作為非線性分析中的重要分支，在交通、運(yùn)輸、博弈論、機(jī)器學(xué)習(xí)和網(wǎng)絡(luò)規(guī)劃等領(lǐng)域都有著廣泛的應(yīng)用[1-10].投影算法是求解變分不等式問題的一種主要方法，最早的投影算法由Goldstein[11]提出，在F是強(qiáng)單調(diào)且 Lipschitz連續(xù)的條件下，Goldstein證明了算法的收斂性.由于F的強(qiáng)單調(diào)性，算法的使用受到了限制.1976年，Korpelevich[12]提出了外梯度算法，在單調(diào)和 Lipschitz連續(xù)的假設(shè)下證明了算法的收斂性.1999年，Solodov和Svaiter[13]在有限維空間中提出了一種新的二次投影算法，在非單調(diào)和連續(xù)的假設(shè)下證明了算法的收斂性.在 Hilbert空間中，Vuong和Shehu[14]提出了Halpern型二次投影算法，在偽單調(diào)和一致連續(xù)的假設(shè)下證明了算法的收斂性.最近，Reich等[15]通過構(gòu)造一類新的嚴(yán)格分離當(dāng)前迭代和變分不等式解集的超平面，對(duì)文獻(xiàn)[14]中的算法進(jìn)行改進(jìn)，提出了兩種新的算法，并在偽單調(diào)和一致連續(xù)的假設(shè)下證明了其算法的收斂性.

本文受文獻(xiàn)[13-15]的啟發(fā)，提出了一種新的二次投影算法.在沒有單調(diào)性的假設(shè)下，證明了算法強(qiáng)收斂到變分不等式問題的解.

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

設(shè) H 是實(shí) Hilbert 空間， C?H 是非空閉凸子集.記 xn→x 為 {xn}強(qiáng)收斂于x， xn?x 為 {xn}弱收斂于x.對(duì)任意的u,v∈H,α∈(0,1)，有

任給x∈H，則存在C中唯一的最近點(diǎn)PC(x)滿足

‖x-PC(x)‖≤‖x-y‖, ?y∈C,

PC叫做H到C 上的投影，易知 PC為H到C 上的非擴(kuò)張映射.

定義1 設(shè) F : H→H 是一映射.

(ⅰ) 稱F是偽單調(diào)的，如果 〈F(x),y-x〉≥0?〈F(y),y-x〉≥0,?x,y∈H.

(ⅱ) 稱F是 Lipschitz連 續(xù)的，如果 ‖F(xiàn)(x)-F(y)‖≤L‖x-y‖,?x,y∈H ，這里L(fēng)為 Lipschitz常 數(shù)且 L＞0.

引理1[2]設(shè)C ?H 是非空閉凸子集，對(duì)任意的 x∈H，有

(ⅰ) 〈 x-y,PC(x)-PC(y)〉≥‖PCx-PCy‖2,?y∈H.

(ⅱ) ‖ PC(x)-y‖2≤‖x-y‖2-‖x-PC(x)‖2,?y∈C.

引理2[2]設(shè)C ?H 是非空閉凸子集.給定 x∈H,z∈C，則 z = PC(x)?〈x-z,z-y〉≥0,?y∈C.

引理3[3]設(shè) C?H 是非空閉凸子集， h(x)是H上的實(shí)值函數(shù)，定義集合 K := {x∈C : h(x)≤0}.如果K非空且 h(x)在C 上是 Lipschitz連續(xù)的，則

dist(x,K)≥θ-1max{h(x),0}, ?x∈C,

其中 dist(x,K)表示x到K的距離，θ為 Lipschitz常 數(shù)，且 θ＞0.

引理4[4]設(shè) {an}是非負(fù)實(shí)數(shù)序列，滿足以下關(guān)系：

an+1≤(1-ηn)an+ηnsn.

若{ηn}，{sn}滿足：(ⅰ) { ηn}?(0,1),; (ⅱ) l imsupn→∞sn≤0，則 limn→∞an= 0.

引理5[2]x?∈Vol(C,F)，當(dāng)且僅當(dāng) x?= PC(x?-λF(x?)).

本文假設(shè)

(C1)映射 F : H→H 在C 中的有界集上是一致連續(xù)的.

(C2)變分不等式解集 Sol(C,F)非空.

(C3)對(duì)于 x?∈Sol(C,F)都有

(C4)f :C→C 是一個(gè)壓縮映射且壓縮系數(shù)為 ρ∈[0,1).

(C5)序列 {αn}?(0,1)，且滿足

2 算法與收斂性證明

本文提出如下算法：

算法1選取 σ∈(0,1)， γ∈(0,1)， λ∈選取初始點(diǎn)x1∈C.

步驟1計(jì)算

如果r(xn) := xn-zn= 0，則算法停止，xn是變分不等式的解.否則，轉(zhuǎn)到步驟2.

步驟2計(jì)算

其中 τn:=γmn，mn是滿足下式的最小非負(fù)整數(shù)m：

步驟3計(jì)算

其中

令n = n+1，并回到步驟1.

注1 (ⅰ) 顯然由算法1產(chǎn)生的序列{xn},{yn},{zn}都屬于C.

(ⅱ) 假設(shè) (C1)~ (C4)成立，由引理5可知，若 r(xn) = 0，則 xn是變分不等式的解，算法停止.否則根據(jù)映射F在C 上的一致連續(xù)性以及引理1，可得

即〈F(xn),r(xn)〉≥λ-1‖r(xn)‖2λ∈.又因?yàn)閺亩?/p>

(ⅲ) 如果F是偽單調(diào)的，則式(2)成立，反之則不成立，具體例子可參見文獻(xiàn)[16]中的例3.1.由此說明假設(shè) (C3)比偽單調(diào)性更弱.

引理6假設(shè) (C1) ~ ( C4)成立，且函數(shù) hn(x)由式(5)定義.(ⅰ) 如果 r(xn)≠0，則 hn(xn)＞0；(ⅱ) 如果x?∈Sol(C,F)，則 hn(x?)≤0.

證明由 hn(x)定義知 hn(xn) =若r(xn)≠0，有 hn(xn)＞0.另一方面，

結(jié)合式(2)和(4)可得

從而引理6得證.

引理7 假設(shè) (C1) ~ ( C5)成立，則由算法1產(chǎn)生的序列 {xn}有界.

證明設(shè)p∈Sol(C,F)，由引理1(ⅱ)可得 ‖PCn(xn)- p‖2≤‖xn- p‖2-‖PCn(xn)-xn‖2.故 ‖PCn(xn)- p‖≤‖xn- p‖.結(jié)合 {xn+1}的定義知

這表明 {xn}有界.

引理8假設(shè) (C1) ~ ( C4)成立， {xn}為算法1產(chǎn)生的序列.如果 limn→∞τn‖xn-zn‖2= 0，則 limn→∞‖xn-zn‖= 0.

證明我們考慮以下兩種情形.

情形1若 liminfn→∞τn＞0，則 0≤‖r(xn)‖2=從而

因此limsupn→∞‖r(xn)‖= 0，即 limn→∞‖r(xn)‖= limn→∞‖xn-zn‖= 0.

情形2若 liminfn→∞τn= 0.不妨設(shè) limk→∞τnk= 0， limk→∞‖xnk-znk‖= a＞0.令

則

因?yàn)?{xnk}有界，所以 {znk}有界，則 {znk-xnk}有界且 limn→∞τnk= 0.由此可得 limn→∞(unk-xnk) = 0.根據(jù)線搜索規(guī)則(4)和 {unk}的定義可得

上式等價(jià)于

令δnk:= xnk-λF(xnk)，則

又因?yàn)?/p>

聯(lián)立式(6)和(7)有

又由F的一致連續(xù)性可得 limk→∞‖F(xiàn)(unk)-F(xnk)‖= 0.所以當(dāng) k→∞時(shí)不等式(8)右邊會(huì)趨近于(σλ-1)a2＜0，從而有

對(duì)于 ?= -(σλ-1)a2/2＞0，存在 N∈N，當(dāng) n≥N時(shí)有

故‖xnk-δnk‖＜‖znk-δnk‖，這與{zn}的定義矛盾.因此 limn→∞‖xn-zn‖= 0.證畢.

定理1 假設(shè)(C1)~ ( C5)成立，則由算法1產(chǎn)生的序列 {xn}強(qiáng)收斂于 p∈Sol(C,F)，這里 p := PSol(C,F)°f(p).

證明先證‖PCn(xn)-xn‖2≤‖xn- p‖2-‖xn+1- p‖2+2αn〈f(xn)- p,xn+1- p〉.事實(shí)上

由引理1(ⅱ)得

由此可得

這表明hn(x)是 Lipschitz連 續(xù)的，且 Lipschitz常數(shù)為M.由引理1、3和6可得

結(jié)合{xn+1}的定義知

所以

下面分兩種情形進(jìn)行討論.

情形3若存在正整數(shù) N ，當(dāng) n≥N 時(shí)有 ‖xn+1- p‖2≤‖xn- p‖2，這表明 limn→∞‖xn- p‖2存在.由式(10)可得，所以

由引理8知

又因?yàn)?{xn}有界，所以對(duì) {xn}的任一聚點(diǎn)z都 存在子列 {xnk}，有 limk→∞xnk= z .結(jié)合 PC和F的一致連續(xù)性可得

故r(z) = 0.又由引理5得 z∈Sol(C,F).另一方面

通過式(9)可得limn→∞‖PCn(xn)-xn‖= 0.因此

結(jié)合引理2及p := PSol(C,F)°f(p)有

所以有

則依據(jù)式(11)和引理4有xn→p(n→∞).

情形4假設(shè)不存在 n0∈N 使得是單調(diào)遞減序列.令 Γn=‖xn- p‖2且有映射 t : N→N 滿足對(duì)所有的 n≥n0(n0足夠大)都有

即 t(n)是1,2,···,n 中使得 Γk為遞增序列的最大值k .顯然t 是一個(gè)非遞減序列，且滿足 limn→∞t(n) =∞，以及

由Cauchy-Schwarz不等式以及式(9)可得

由式(10)可得

類似于情形3的證明可得

以及

由式(11)可得

因此limsupn→∞‖xt(n)+1- p‖2≤0

結(jié)合式(12)有 ，即

接下來，我們證明當(dāng)n≥n0時(shí)(n0足夠大)，有 0≤Γn≤Γt(n)+1.不難發(fā)現(xiàn)，當(dāng) n≥n0時(shí)有 t(n)≤n.考慮三種情況：當(dāng) t(n) = n 和 t(n) = n-1時(shí)，顯然有 Γn≤Γt(n)+1.現(xiàn)考慮 t(n)＜n-1.對(duì)任意的正整數(shù) n≥n0，由 t(n)的定義知，有Γj≥Γj+1，當(dāng) t(n)+1≤j≤n-1時(shí)，得到 Γt(n)+1≥Γt(n)+2≥···≥Γn-1≥Γn，因此當(dāng)n足 夠大時(shí)， 0≤Γn≤Γt(n)+1恒成立.聯(lián)立式(13)可知 limn→∞Γn= 0，即算法1迭代產(chǎn)生的序列xn強(qiáng)收斂于p.

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

在本節(jié)中給出了算法1在一個(gè)簡(jiǎn)單例子中的計(jì)算機(jī)檢驗(yàn)結(jié)果，并與文獻(xiàn)[14]中算法3.3及文獻(xiàn)[15]中算法4進(jìn)行比較.本文中所有代碼都是在MATLAB R2020a和Windows10系統(tǒng)下運(yùn)行的.計(jì)算機(jī)基本參數(shù)為Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz.此外，用“iter”表示算法迭代次數(shù)，“CPU time”表示程序運(yùn)算的時(shí)間，單位為s.參數(shù)選取如下：

例1設(shè)映射 F : Rm→Rm滿足 F(x) = Mx+q ，這里 q∈Rm且 M = NNT+S+ D，其中為反對(duì)稱矩陣，D為 對(duì)角矩陣且對(duì)角元素非負(fù).取可行集

容易得到F是一個(gè)單調(diào)且Lipschitz連續(xù)的映射，其中Lipschitz常 數(shù)L=‖M‖.對(duì)于q = 0，相應(yīng)的變分不等式的唯一解是{0}.

在本文的實(shí)驗(yàn)中，矩陣N,S中所有元素都在區(qū)間(-2,2)上隨機(jī)產(chǎn)生，矩陣D中的對(duì)角元素在(0,1)上隨機(jī)產(chǎn)生.此外，設(shè)置所有算法中最大迭代次數(shù)為，停機(jī)條件為，其中εerr為給定的誤差界.在此情況下，我們對(duì)比了不同的維數(shù)、不同的初始點(diǎn)以及不同的誤差界εerr三種算法的數(shù)值效果，具體如表1 ~ 3所示.通過觀察表中的數(shù)據(jù)可以發(fā)現(xiàn)，算法1在三個(gè)維度上的數(shù)值效果優(yōu)勢(shì)非常明顯.

表 1 εerr= 10-4時(shí)不同算法關(guān)于維數(shù)的比較Table 1 For εerr= 10-4, comparison of different algorithms about dimensions

表 2 εerr= 10-4時(shí)不同算法關(guān)于初始點(diǎn)的比較Table 2 For εerr= 10-4, comparison of different algorithms about the initial point

表 3 m = 100時(shí)不同算法關(guān)于允許誤差的比較Table 3 For m = 100, comparison of different algorithms about allowable errors

4 結(jié)論與展望

本文利用線搜索方法，提出了一種新的求解非單調(diào)變分不等式的二次投影算法，在映射是一致連續(xù)的條件下證明了算法的收斂性.本文所得結(jié)果改進(jìn)了文獻(xiàn)[14-15]中對(duì)應(yīng)的結(jié)果.數(shù)值實(shí)驗(yàn)展示了本文算法的優(yōu)勢(shì).本文主要對(duì)變分不等式問題的算法進(jìn)行了研究，如何將所得結(jié)果應(yīng)用于圖像處理以及網(wǎng)絡(luò)規(guī)劃等問題中，有待進(jìn)一步研究.