一類偽單調(diào)變分不等式的雙投影算法

楊登煉, 張 燕, 張永樂

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

設(shè)C?Rn是一個(gè)非空閉凸集,F:Rn→Rn是連續(xù)映射.經(jīng)典變分不等式問題:尋找x*∈C使得

〈F(x*),x-x*〉≥0, ?x∈C,

(1)

其中〈·,·〉是歐幾里得內(nèi)積.為了便于表述,將問題(1)及其解集分別記為VI(C,F)和S.變分不等式作為非線性分析中的重要分支,它在工程、交通、數(shù)學(xué)規(guī)劃等領(lǐng)域有廣泛應(yīng)用.因此,如何構(gòu)造算法來求解變分不等式問題是值得研究的,而投影算法是解變分不等式的一類相對簡單有效的方法,被廣泛研究[1-8].最早的投影算法由Goldstein[2]提出

xk+1=PC(xk-λF(xk)),

(2)

其中λ>0為步長.該算法對映射F的要求為強(qiáng)單調(diào)和L-Lipschitz連續(xù).雖然該算法的每一步迭代只需要一次投影,但強(qiáng)單調(diào)條件不容易滿足,因此為了削弱F的強(qiáng)單調(diào)性,Korpelevich[3]提出了外梯度算法,其迭代形式為

yk=PC(xk-λF(xk)),

xk+1=PC(xk-λF(yk)).

(3)

在映射F滿足單調(diào)和Lipschitz連續(xù)的條件時(shí)得到了該算法的收斂性.在此基礎(chǔ)上,文獻(xiàn)[5]通過引入Armijo線性搜索來削弱F是L-Lipschitz連續(xù)性.1999年,Solodov等[6]給出了一種利用二次投影求解VI(C,F)的算法,該算法采用Armijo線性搜索來確定步長,文獻(xiàn)[7]說明了該算法能夠得到一個(gè)較優(yōu)的步長,從而在理論上優(yōu)于其他投影算法.文獻(xiàn)[6]的關(guān)鍵是在第二步投影中利用F(zk)構(gòu)造了一個(gè)嚴(yán)格分離當(dāng)前迭代點(diǎn)和解集的超平面,通過向該超平面與約束集的交上投影得到收斂到解的無窮迭代序列.2006年,He[8]利用F(zk)和rμ(xk)構(gòu)造了一種新的超平面,進(jìn)而提出了一種求解偽單調(diào)變分不等式的的雙投影算法,該算法具有較好的數(shù)值計(jì)算結(jié)果.隨后許多學(xué)者通過構(gòu)造不同的超平面提出了不同的雙投影算法[9-11].受此啟發(fā),本文利用F(zk)、F(xk)和rμ(xk)給出一類與以往不同的新的超平面,它能嚴(yán)格分離當(dāng)前迭代點(diǎn)和解集,從而建立了一種新的雙投影算法.在映射F連續(xù)和偽單調(diào)條件下建立了算法的收斂性,進(jìn)一步假設(shè)F是Lipschitz連續(xù)的,進(jìn)行了收斂性分析.最后,數(shù)值實(shí)驗(yàn)結(jié)果表明該算法是有效的.

1 基本準(zhǔn)備

Rn是一個(gè)有限維的Hilbert空間,其內(nèi)積和范數(shù)分別記為〈·,·〉和‖·‖.設(shè)C?Rn是一個(gè)非空閉凸集,對任意的z∈Rn,dist(z,C):=表示z到C的距離,

PC(z):=argmin{‖y-z‖|y∈C}

表示z在C上的投影,則有‖z-PC(z)‖=dist(z,C).對任意的μ>0,記rμ(x):=x-PC(x-μF(x)),稱rμ(x)為自然殘差函數(shù).

定義 1.1設(shè)C?Rn是一個(gè)非空閉凸集.映射F:C→Rn,對任意的x,y∈C,若

1) 〈F(x)-F(y),x-y〉≥η‖x-y‖2,則稱F在C上是強(qiáng)單調(diào)的,其中η>0稱為F在C上的強(qiáng)單調(diào)系數(shù).

2) 〈F(x)-F(y),x-y〉≥0,則稱F在C上是單調(diào)的.

3) 〈F(x),y-x〉≥0?〈F(y),y-x〉≥0,則稱F在C上是偽單調(diào)的.

定義 1.2設(shè)C?Rn是一個(gè)非空閉凸集,映射F:C→Rn,任意x,y∈C,若

‖F(xiàn)(x)-F(y)‖≤L‖x-y‖,

則稱F在C上是L-Lipschitz連續(xù)的,其中L>0稱為F在C上的Lipschitz系數(shù).

以下為本文定理證明中需要用到的引理.

引理 1.1[12]設(shè)C是Rn上的一個(gè)非空閉凸集,對任意的x∈Rn,PC(x)為x在C上的投影,則對任意的y∈C,有下列不等式成立:

1) 〈x-PC(x),y-PC(x)〉≤0;

2) ‖y-PC(x)‖2≤‖x-y‖2-‖x-PC(x)‖2.

引理 1.2[13]設(shè)C?Rn是一個(gè)非空閉凸集,給定參數(shù)μ>0,則x*∈S當(dāng)且僅當(dāng)rμ(x*)=0.

引理 1.3[8]對任意x∈C,〈F(x),rμ(x)〉≥μ-1‖rμ(x)‖2.

引理 1.4[8]設(shè)C是Rn上的非空閉凸集,h(x)是C上的θ-Lipschitz連續(xù)實(shí)函數(shù),K={x∈C|h(x)≤0}.若Lipschitz系數(shù)θ>0,則對任意的x∈C,dist(x,K)≥θ-1max{h(x),0}.

引理 1.5[14]設(shè)tk>0且滿足

tk+1≤tk-βkt1+pk,βk≥0,p>0.

那么

tk≤t0(1+pt

特別的是,如果βk≡β,p=1,那么

t

2 主要結(jié)論

本文總假設(shè)以下條件成立:

(C1)S≠?；

(C2)F是連續(xù)和偽單調(diào)的.

2.1 雙投影算法下面敘述算法的具體內(nèi)容.

算法 2.1選取初始點(diǎn)x0∈C,σ>0,μ∈(0,σ-1),γ∈(0,1),a≥0,b∈[0,μ-1].設(shè)k=0.

步驟1計(jì)算rμ(xk)=xk-PC(xk-μF(xk)),如果rμ(xk)=0,停止;否則,轉(zhuǎn)到步驟2.

步驟2計(jì)算zk=xk-ηkrμ(xk),其中ηk=γmk,mk是使得下面不等式成立的最小非負(fù)整數(shù)m,

〈F(xk)-F(xk-γmrμ(xk)),rμ(xk)〉≤

σ‖rμ(xk)‖2.

(4)

步驟3計(jì)算xk+1=PC∩Hk(xk),其中Hk:={v:hk(v)≤0},且函數(shù)

hk(v):=〈aF(xk)+F(zk)+bηkrμ(xk),

v-xk〉+(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2.

(5)

令k←k+1,轉(zhuǎn)到步驟1.

注 2.1關(guān)于構(gòu)成超平面的函數(shù)hk(v),通過比較發(fā)現(xiàn),本文構(gòu)造的超平面與已有文獻(xiàn)中的超平面都不相同,并且包含某些已有超平面作為其特殊情形.如在文獻(xiàn)[9]中,

hk(v)=〈αηkrμ(xk)+βF(xk)+αμF(zk),

v-xk〉+αηk(1-μσ)‖rμ(xk)‖2,

hk(v)=〈F(xk)+F(zk),v-xk〉+

ηk〈F(zk),rμ(xk)〉,

它是(5)式中a=1和b=0的特殊情形,但反之不成立,因?yàn)槲墨I(xiàn)[11]中的超平面無‖rμ(xk)‖2這一項(xiàng).

說明算法中(4)式是合理的.

引理 2.1對任意的k∈N+,當(dāng)rμ(xk)≠0時(shí),都存在非負(fù)整數(shù)m滿足(4)式.

證明假設(shè)這樣的m不存在,則存在k0∈N+,使得對所有的非負(fù)整數(shù)m,都有

〈F(xk0)-F(xk0-γmrμ(xk0)),rμ(xk0)〉>

σ‖rμ(xk0)‖2,

(6)

而F是連續(xù)的,且γ∈(0,1),則

〈F(xk0)-F(xk0-γmrμ(xk0)),

rμ(xk0)〉→0,m→∞.

由(6)式及σ>0可得矛盾式0<‖rμ(xk0)‖2≤0,則假設(shè)不成立,即存在非負(fù)整數(shù)m滿足(4)式.

其次證明算法2.1中的超平面能嚴(yán)格分離當(dāng)前迭代點(diǎn)和變分不等式的解集.

引理 2.2設(shè)x*∈S,hk(v)如(5)式所示,則有如下不等式成立:

(i)hk(xk)≥(μ-1-σ)ηk‖rμ(xk)‖2,特別地,如果rμ(xk)≠0,則hk(xk)>0;

(ii)hk(x*)≤0.

證明由hk(v)的定義可得

hk(xk)=(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

(1-bμ)ηk(〈F(xk),rμ(xk)〉-

σ‖rμ(xk)‖2)+b(1-μσ)ηk‖rμ(x

(1-bμ)ηk(μ-1‖rμ(xk)‖2-σ‖rμ(xk)‖2)+

b(1-μσ)ηk‖rμ(xk)‖2=

(μ-1-σ)ηk‖rμ(xk)‖2,

其中(a)是因?yàn)?1-bμ)ηk≥0和(4)式,(b)由引理1.3可得.若rμ(xk)≠0,由于(μ-1-σ)ηk>0,則hk(xk)>0,(i)得證.

因?yàn)閞μ(xk)=xk-PC(xk-μF(xk)),則xk-rμ(xk)=PC(xk-μF(xk)).對任意的x*∈S,根據(jù)引理1.1的1)可得

〈rμ(xk)-μF(xk),x*-xk+rμ(xk)〉≤0,

即

〈rμ(xk)-μF(xk),x*-xk〉≤

μ〈F(xk),rμ(xk)〉-‖rμ(xk)‖2.

從而有

〈rμ(xk),x*-xk〉=〈rμ(xk)-μF(xk),

x*-xk〉+μ〈F(xk),x*-x

〈rμ(xk)-μF(xk),x*-xk〉≤

μ〈F(xk),rμ(xk)〉-‖rμ(xk)‖2,

(7)

其中(c)由條件(C2)可得.于是有

hk(x*)=〈aF(xk)+F(zk)+bηkrμ(xk),

x*-xk〉+(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

a〈F(xk),x*-xk〉+〈F(zk),x*-xk〉+

bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

〈F(zk),x*-xk〉+bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

(〈F(zk),x*-zk〉+〈F(zk),zk-xk〉)+

bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

〈F(zk),zk-xk〉+bηk〈rμ(xk),x*-xk〉+

(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(x

-ηk〈F(zk),rμ(xk)〉+bηk〈rμ(xk),

x*-xk〉+(1-bμ)ηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

bηk〈rμ(xk),x*-xk〉-bμηk〈F(zk),

rμ(xk)〉+b(1-μσ)ηk‖rμ(x

bηk(μ〈F(xk),rμ(xk)〉-‖rμ(xk)‖2)-

bμηk〈F(zk),rμ(xk)〉+

b(1-μσ)ηk‖rμ(xk)‖2=

bμηk(〈F(xk)-F(zk),rμ(xk)〉-

σ‖rμ(x

其中(d)和(e)由條件(C2)可得,(f)由zk=xk-ηkrμ(xk)可得,(g)由(4)式可得,(h)由(4)式可得.證畢.

2.2 收斂性與收斂率分析下面分別對算法2.1的收斂性以及收斂率進(jìn)行分析.

定理 2.1假設(shè)條件(C1)～(C2)成立,則算法2.1在有限步終止或生成一個(gè)無限序列{xk}收斂到S.

證明總假設(shè)算法2.1生成無限序列,即對任意的k∈N+,rμ(xk)≠0.否則必存在k1∈N+,使得rμ(xk1)=0,則xk1∈S.即算法在有限步終止.

對任意的x*∈S,由xk+1=PC∩Hk(xk),根據(jù)引理1.1的2)得

‖xk+1-x*‖2≤‖xk-x*‖2-‖xk+1-xk‖2=

‖xk-x*‖2-dist2(xk,C∩Hk),

(8)

從而可得序列{‖xk-x*‖2}是收斂的,因此{(lán)xk}有界.同時(shí)由(8)式有

dist(xk,C∩Hk)=0.

(9)

因?yàn)镕(x)和rμ(x)關(guān)于x是連續(xù)的,于是{F(xk)}和{rμ(xk)}都是有界序列,進(jìn)而有{zk}和{F(zk)}有界,則存在一個(gè)常數(shù)0

‖aF(xk)+F(zk)+bηkrμ(xk)‖≤M.

根據(jù)上式可知算法2.1中定義的hk(x)關(guān)于x在C上是Lipschitz連續(xù)的,且M為hk(x)的Lipschitz系數(shù).于是由引理1.4以及xk?C∩Hk有

dist(xk,C∩Hk)≥M-1hk(xk), ?k∈N+.

結(jié)合上式以及引理2.2可得

dist(xk,C∩Hk)≥M-1hk(xk)≥

M-1(μ-1-σ)ηk‖rμ(xk)‖2,

(10)

σ‖rμ(xkj)‖2<〈F(xkj)-

F(xkj-γkj-1rμ(xkj)),rμ(xkj)〉=

〈F(xkj)-F(xkj-γ-1ηkrμ(xkj)),rμ(xkj)〉≤

‖F(xiàn)(xkj)-F(xkj-γ-1ηkrμ(xkj))‖‖rμ(xkj)‖,

?j∈N+.

(11)

引理 2.3在定理2.1的假設(shè)條件下,進(jìn)一步假設(shè)F是L-Lipschitz連續(xù)的,且存在常數(shù)α,δ>0以及任意的x,使得當(dāng)rμ(x)≤δ時(shí),有

dist(x,S)≤α‖rμ(x)‖,

(12)

則存在常數(shù)β>0使得對充分大的k有

dist(x

(13)

證明令η:=min先證明對任意的k∈N+,ηk>η成立.由ηk的構(gòu)造可知ηk∈(0,1].若ηk=1,則顯然有于是可假設(shè)ηk<1,則有最小非負(fù)整數(shù)mk≥1使得ηk=γmk.根據(jù)mk的最小性以及映射F的Lipschitz連續(xù)性,有

σ‖rμ(xk)‖2<

〈F(xk)-F(xk-γ-1ηkrμ(xk)),rμ(xk)〉≤

‖F(xiàn)(xk)-F(xk-γ-1ηkrμ(xk))‖‖rμ(xk)‖≤

Lγ-1ηk‖rμ(xk)‖2,

于是有ηk>L-1γσ≥η.

下證存在常數(shù)β>0使得對充分大的k,(13)式成立.設(shè)x*∈PS(xk),對于充分大的k,有以下不等式成立

dist2(xk+1,S)≤‖x

‖xk-x*‖2-dist2(xk,C∩H

‖xk-x*‖2-M-2(μ-1-σ)2ηk2‖rμ(xk)‖4≤

‖xk-x*‖2-M-2(μ-1-σ)2η2‖rμ(x

其中(a)由(8)式可得,(b)由(10)式可得,(c)由(12)式可得.記β=M-2(μ-1-σ)2η2α-4,根據(jù)引理1.5可得到

dist(x

(13)式得證.證畢.

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

本節(jié)給出數(shù)值實(shí)驗(yàn)結(jié)果,在Windows 10,處理器為Intel(R) Core(TM)i5-4590 CPU@3.30 GHz的系統(tǒng)環(huán)境下,使用版本為R2019a的Matlab進(jìn)行數(shù)值實(shí)驗(yàn).調(diào)用quadprog函數(shù)計(jì)算向非空閉凸集的投影.將本文的算法2.1與文獻(xiàn)[6]的算法2.2,文獻(xiàn)[10]的算法2.1和文獻(xiàn)[11]的算法3.1進(jìn)行比較,并記錄計(jì)算機(jī)實(shí)驗(yàn)結(jié)果.取‖rμ(x)‖≤10-4作為停機(jī)準(zhǔn)則.x0表示初始點(diǎn),nF表示計(jì)算F的次數(shù),iter表示程序迭代的次數(shù),time代表程序運(yùn)行所需的時(shí)間.

例 3.1本例首先被文獻(xiàn)[15]測試.令C=[0,1]n,考慮映射F(x)=Mx+d,其中

分別選取x0=(0,0,…,0)和x0=(1,1,…,1)為初始點(diǎn),且參數(shù)選取如下:

1) 文獻(xiàn)[6]的算法2.2:σ=0.3,γ=0.5,η-1=1,θ=4;

2) 文獻(xiàn)[10]的算法3.1:σ=2.5,γ=0.9,μ=0.2,α=β=1;

3) 文獻(xiàn)[11]的算法3.1:σ=6,γ=0.8,μ=0,15;

4) 算法2.1:σ=4,γ=0.8,μ=0.19,a=0.02,b=0.09.

前3種算法參數(shù)的選取與對應(yīng)參考文獻(xiàn)中推薦的一致.數(shù)值結(jié)果分別見表1與表2.

表1 例3.1中初始點(diǎn)為x0=(0,0,…,0)各算法的數(shù)值結(jié)果

表2 例3.1中初始點(diǎn)為x0=(1,1,…,1)各算法的數(shù)值結(jié)果

例 3.2Kojima-Shindo非線性互補(bǔ)問題(n=4)被文獻(xiàn)[6]所考慮,其中函數(shù)F定義如下:

F(x1,x2,x3,x4)=

其可行集為

文獻(xiàn)[10]的算法3.1中推薦的參數(shù)選取為σ=3,γ=0.9,μ=0.3,α=3,β=0.4.文獻(xiàn)[6]的算法2.2、文獻(xiàn)[11]的算法3.1和算法2.1推薦的參數(shù)選擇與例1相同.分別選取不同的初始點(diǎn)進(jìn)行數(shù)值實(shí)驗(yàn),其結(jié)果見表3.

表3 例3.2中各算法的數(shù)值結(jié)果

通過數(shù)值實(shí)驗(yàn)對比可以看出,在適當(dāng)?shù)膮?shù)選取下,本文中的算法較其他3種算法更快,這表明了本文中的算法在一定程度上的有效性.