楊澈洲, 賀月紅, 龍憲軍

(重慶工商大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 重慶 400067)

設(shè)H為實(shí)Hilbert空間,C?H是非空閉凸子集,〈·,·〉和‖·‖分別表示H中的內(nèi)積和范數(shù).設(shè)x∈H,PC(x)表示向量x在C上的投影,F:H→H是一個(gè)映射.本文考慮如下變分不等式問(wèn)題：尋找點(diǎn)x*∈C,使得

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

(1)

(2)

該算法每次迭代需要計(jì)算2次到C上的投影和映射F在2個(gè)點(diǎn)的函數(shù)值.若C是一個(gè)一般的閉凸集或者F的值比較復(fù)雜,則會(huì)影響算法的計(jì)算效率.為了克服這一缺點(diǎn),Censor等[6]提出了次梯度外梯度算法,該算法通過(guò)投影到一個(gè)半空間，簡(jiǎn)化了算法(2)中第二次投影的計(jì)算量,但在每次迭代時(shí)仍然需要計(jì)算映射F在2個(gè)點(diǎn)的函數(shù)值.因此,為了進(jìn)一步減少計(jì)算成本,Malitsky等[7]提出了如下的修正次梯度外梯度算法

(3)

近年來(lái),為了解除Lipschitz常數(shù)對(duì)算法步長(zhǎng)的限制,學(xué)者們進(jìn)行了大量的研究,見(jiàn)文獻(xiàn)[8-9].Yang等[8]在如下算法中采用了一種新的自適應(yīng)步長(zhǎng)規(guī)則

(4)

其中

λn+1:=

該算法要求映射F是強(qiáng)單調(diào)且Lipschitz連續(xù)的,保持映射計(jì)算量的同時(shí),不要求Lipschitz常數(shù)已知.隨后,Hieu等[9]進(jìn)一步將映射F的強(qiáng)單調(diào)弱化為單調(diào),提出了如下算法

(5)

其中

λn+1:=

該算法要求映射F的Lipschitz連續(xù)性,但是在實(shí)際中許多函數(shù)并不是Lipschitz連續(xù)的.因此,如何在更弱的條件下給出新的投影算法并證明算法的收斂性是本文討論的重點(diǎn).

受文獻(xiàn)[7-9]的啟發(fā),本文提出了一種新的次梯度外梯度算法求解變分不等式問(wèn)題.該算法引入Armijo線性搜索準(zhǔn)則,在映射F是單調(diào)和一致連續(xù)的假設(shè)下,證明了由算法產(chǎn)生的無(wú)窮序列弱收斂到變分不等式問(wèn)題的解,并用數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的適用性.本文所得結(jié)果改進(jìn)和推廣了文獻(xiàn)[7-9]中相應(yīng)的結(jié)果.

1 相關(guān)定理及引理

設(shè)C?H是非空閉凸子集,x∈H,定義

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

為x在集合C上的投影.

定義 1.1[10]設(shè)F:H→H是映射,如果對(duì)任意的x,y∈H,有

〈F(x)-F(y),x-y〉≥0,

則稱F是單調(diào)的.

引理 1.1[11]設(shè)C?H是非空閉凸子集,則:

(i) 對(duì)任意的x∈H,y∈C,有

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

(ii) 對(duì)任意的x∈H,y∈C,有

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

引理 1.2[8]設(shè){an}、{bn}是2個(gè)非負(fù)實(shí)序列,?N>0,?n>N,滿足an+1≤an-bn,則{an}有界且

引理 1.3[12]設(shè)C?H是非空閉凸子集,F:C→H為單調(diào)連續(xù)算子，則x*∈VI(F,C)當(dāng)且僅當(dāng)

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

引理 1.4[7]設(shè)H中的序列{xn}弱收斂于x∈H,則對(duì)任意的y∈H{x},有

2 算法及收斂性證明

為了引入本文的算法,需要下述條件:

條件 2.1C為非空閉凸集.

條件 2.2VI(F,C)非空,即VI(F,C)≠?.

條件 2.3F:H→H是單調(diào)的,在C中的有界集上是一致連續(xù)的且在C上是弱序列連續(xù)的.

步驟1計(jì)算

并給定xn、yn-1、yn和αn,構(gòu)造半空間

Hn={z∈H:〈xn-αnF(yn-1)-yn,

z-yn〉≤0},

轉(zhuǎn)步驟2.

步驟2取αn為最大的

α∈{λθln|ln∈N0∪{0},n≥0},

其中l(wèi)n是使得下式成立的最小非負(fù)整數(shù)

λθln〈F(yn-1)-F(yn),xn+1(α)-yn〉≤

(6)

其中

xn+1(α)=PHn(α)(xn-αF(yn)),

Hn(α)=

{z∈H:〈xn-αF(yn-1)-yn,z-yn〉≤0},

轉(zhuǎn)步驟3.

步驟3計(jì)算

若xn+1=xn且

yn+1=yn=yn-1,

則停止;否則,令n:=n+1,返回步驟1.

注 2.1容易得到C?Hn.事實(shí)上,假設(shè)z∈CHn,則

〈xn-αnF(yn-1)-yn,z-yn〉>0,

這與

yn=PC(xn-αF(yn-1))

矛盾,故C?Hn.

注 2.2若算法滿足停機(jī)準(zhǔn)則xn+1=xn且

yn+1=yn=yn-1,

則

yn∈VI(F,C).

證明若算法中xn+1=xn,則根據(jù)算法中

xn+1=PHn(xn-αnF(yn)),

可知存在如下關(guān)系式

〈xn+1-(xn-αnF(yn)),z-xn+1〉≥0,

?z∈C,xn+1∈C,

即

〈F(yn),x-xn〉≥0, ?x∈Hn.

由于xn+1∈Hn,yn=yn-1,同時(shí)根據(jù)算法中半空間所述不等式得

〈xn-αnF(yn)-yn,xn-yn〉≤0.

因此,有

〈αnF(yn),xn-yn〉≥

〈xn-yn,xn-yn〉≥0.

由于

〈F(yn),x-xn〉=〈F(yn),x-yn〉-

〈F(yn),xn-yn〉≥0, ?x∈Hn.

因此,有

〈F(yn),x-yn〉≥〈F(yn),xn-yn〉, ?x∈Hn,

所以yn∈C?Hn,即yn∈VI(F,C).

引理 2.1假設(shè)條件2.1～2.3成立,則Armijo線性搜索準(zhǔn)則(6)式有意義.

證明分如下2種情況討論:

(i) 若yn∈C,考慮yn∈VI(F,C),則

由F的一致連續(xù)性知

則算法中步驟2所述不等式顯然成立.

考慮yn?VI(F,C),則存在n≥0使得

λθln〈F(yn-1)-F(yn),xn+1(α)-yn〉>

(7)

由柯西-施瓦茨不等式有

λθln‖F(xiàn)(yn-1)-F(yn)‖·

‖xn+1(α)-yn‖≥

λθln〈F(yn-1)-F(yn),xn+1(α)-yn〉,

(8)

結(jié)合(7)和(8)式有

λθln‖F(xiàn)(yn-1)-F(yn)‖>

(9)

對(duì)(9)式取極限可得

則獲得了矛盾.

(ii) 若yn?C,則假設(shè)線性搜索不能有限步終止,即存在n≥0使得(7)式成立,令n→∞,通過(guò)與上述類似推理可以得到矛盾.因此,Armijo線性搜索準(zhǔn)則(6)式有意義.

引理 2.2設(shè){xn}和{yn}是由算法2.1生成的2個(gè)序列,z∈VI(F,C),則

‖xn+1-z‖2≤‖xn-z‖2-

(10)

證明因?yàn)閦∈VI(F,C)?Hn和

xn+1=PHn(xn-αnF(yn)),

由引理1.1知

‖xn+1-z‖2≤‖xn-αnF(yn)-z‖2-

‖xn-αnF(yn)-xn+1‖2=

‖xn-z‖2-‖xn-xn+1‖2-

2αn〈F(yn),xn+1-z〉.

(11)

根據(jù)F的單調(diào)性和z∈VI(F,C)可得

2αn〈F(yn),yn-z〉≥0.

(12)

將(12)式加到(11)式右邊可得

‖xn+1-z‖2≤‖xn-z‖2-‖xn-xn+1‖2-

2αn〈F(yn),xn+1-yn〉=

‖xn-z‖2-‖xn-yn‖2-‖xn+1-yn‖2-

2〈xn-yn,yn-xn+1〉-2αn〈F(yn),xn+1-yn〉=

‖xn-z‖2-‖xn-yn‖2-‖xn+1-yn‖2+

2αn〈F(yn-1)-F(yn),xn+1-yn〉+

2〈xn-αnF(yn-1)-yn,xn+1-yn〉.

(13)

又因?yàn)閤n+1∈Hn,則

〈xn-αnF(yn-1)-yn,xn+1-yn〉≤0.

(14)

另一方面,由(6)式和2ab≤a2+b2知

2αn〈F(yn-1)-F(yn),xn+1-yn〉≤

μ‖yn-1-yn‖·‖xn+1-yn‖≤

μ(‖yn-1-xn‖+‖xn-yn‖)‖xn+1-yn‖≤

2‖xn-yn‖·‖xn+1-yn‖)≤

2‖xn+1-yn‖2).

(15)

結(jié)合(13)～(15)式可得

‖xn+1-z‖2≤‖xn-z‖2-

(1-μ)‖xn+1-y

證畢.

證明首先證明序列{xn}的收斂性.由(10)式知?N≥0,?n≥N使得

‖x

‖x

(16)

令

則(16)式可表示為

an+1≤an-bn, ?n≥N.

再由引理1.2知,序列{an}有界且極限存在,由(16)式知,有界序列{an}是非增的,因?yàn)?/p>

故{an}為收斂序列.另一方面,由序列{bn}的定義知

(17)

則有

因?yàn)?/p>

故序列

{‖xn+1-yn‖2}

收斂.因?yàn)閧an}與{‖xn+1-yn‖2}收斂,故序列

{‖xn-z‖2}

收斂.由此知序列{xn}有界且存在弱收斂于z∈H的子列{xnk}.由(17)式有{ynk}弱收斂于z∈C.

下證z∈VI(F,C).由引理2.1及序列{yn}的定義可得

〈ynk+1-xnk+1+αnF(ynk),x-ynk+1〉≥

0, ?x∈C.

上式等價(jià)于

0≤〈ynk+1-xnk+1,x-ynk+1〉+

αn〈F(ynk),ynk-ynk+1〉+αn〈F(ynk),x-ynk〉.

令n→∞,由(17)式及{ynk}弱收斂于z∈C可知,αn〈F(ynk),x-ynk〉≥0,即

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

故z∈VI(F,C).

‖x

‖x

因此,對(duì)所有x∈VI(F,C)有

再由引理1.4可知

注 2.3本文從以下2個(gè)方面改進(jìn)了文獻(xiàn)[7]中的結(jié)果:

1)F的Lipschitz連續(xù)性弱化為一致連續(xù);

2) 本文采用Armijo線性搜索準(zhǔn)則避免要求Lipschitz常數(shù)已知這一假設(shè).

注 2.4本文從以下2個(gè)方面改進(jìn)了文獻(xiàn)[8]中的結(jié)果:

1)F的強(qiáng)單調(diào)性弱化為單調(diào)性;

2)F的Lipschitz連續(xù)性弱化為一致連續(xù).

注 2.5本文采用Armijo線性搜索準(zhǔn)則弱化了文獻(xiàn)[9]要求Lipschitz連續(xù)這一條件.

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

本文數(shù)值實(shí)驗(yàn)的測(cè)試環(huán)境為Matlab 2019a,Windows 10系統(tǒng)Intel(R)Core(TM)i7-6700HQ CPU@2.60 GHz和8.0 GB.為了體現(xiàn)本文算法的數(shù)值效果,采用2個(gè)例子進(jìn)行算法對(duì)比.這里“K”代表最大迭代次數(shù),“iter”代表迭代次數(shù),“time”代表程序的CPU運(yùn)行時(shí)間,單位為s.選取參數(shù)如下:

λ=0.5,θ=0.4,μ=0.45.

例 1考慮映射F:R2→R2滿足

F(x)=(x1+x2+sin(x1),-x1+x2+sin(x2)),

?(x1,x2)∈R2.

令

C={x=(x1,x2)∈R2|-2

初始點(diǎn)x1、x2隨機(jī)產(chǎn)生,選取

‖xn‖≤err=10-4

為停機(jī)條件.在此條件下,對(duì)幾種算法進(jìn)行比較,具體數(shù)值實(shí)驗(yàn)結(jié)果如表1所示.

表1 不同算法關(guān)于例1的比較

例 2現(xiàn)考慮

C:={x∈H:‖x‖≤2}.

令g:C→R有如下定義

g是Lipchitz連續(xù)且

考慮映射F:L2([0,1])→L2([0,1])是有界且單調(diào)的,同時(shí)滿足

?u∈L2([0,1]),t∈[0,1].

定義A:C→L2([0,1])滿足

A(u)(t):=g(u)F(u)(t), ?u∈C,t∈[0,1].

‖xn+1-xn‖≤err=10-4.

在此條件下,對(duì)幾種算法進(jìn)行比較,具體數(shù)值實(shí)驗(yàn)結(jié)果如表2所示.

表2 不同算法關(guān)于例2的比較

(i) 本文算法、文獻(xiàn)[8]算法、文獻(xiàn)[9]算法均收斂到變分不等式問(wèn)題的解,見(jiàn)表1和表2;

(ii) 從迭代次數(shù)以及程序CPU運(yùn)行時(shí)間來(lái)看,本文算法優(yōu)于文獻(xiàn)[9]算法和文獻(xiàn)[8]算法,尤其是本文算法充分體現(xiàn)了CPU運(yùn)行時(shí)間較少的優(yōu)勢(shì),見(jiàn)表1和表2;

(iii) 在適當(dāng)參數(shù)的選取下,對(duì)比例1和例2發(fā)現(xiàn)最大迭代次數(shù)K對(duì)本文算法的影響較小,見(jiàn)表2.

致謝重慶工商大學(xué)科研項(xiàng)目(ZDPTTD201908)對(duì)本文給予了資助，謹(jǐn)致謝意.