求解單調(diào)變分不等式的新次梯度外梯度算法

楊澈洲, 賀月紅, 龍憲軍

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

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

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

(1)

(2)

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

(3)

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

(4)

其中

λn+1:=

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

(5)

其中

λn+1:=

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

受文獻(xiàn)[7-9]的啟發(fā),本文提出了一種新的次梯度外梯度算法求解變分不等式問題.該算法引入Armijo線性搜索準(zhǔn)則,在映射F是單調(diào)和一致連續(xù)的假設(shè)下,證明了由算法產(chǎn)生的無窮序列弱收斂到變分不等式問題的解,并用數(shù)值實驗驗證了算法的適用性.本文所得結(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是映射,如果對任意的x,y∈H,有

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

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

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

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

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

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

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

引理 1.2[8]設(shè){an}、{bn}是2個非負(fù)實序列,?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,則對任意的y∈H{x},有

2 算法及收斂性證明

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

條件 2.1C為非空閉凸集.

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

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

步驟1計算

并給定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計算

若xn+1=xn且

yn+1=yn=yn-1,

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

注 2.1容易得到C?Hn.事實上,假設(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,同時根據(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)

對(9)式取極限可得

則獲得了矛盾.

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

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

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

(10)

證明因為z∈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)

又因為xn+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}是非增的,因為

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

(17)

則有

因為

故序列

{‖xn+1-yn‖2}

收斂.因為{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.

上式等價于

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

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

再由引理1.4可知

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

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

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

注 2.4本文從以下2個方面改進(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ù)值實驗的測試環(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個例子進(jìn)行算法對比.這里“K”代表最大迭代次數(shù),“iter”代表迭代次數(shù),“time”代表程序的CPU運行時間,單位為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

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

‖xn‖≤err=10-4

為停機(jī)條件.在此條件下,對幾種算法進(jìn)行比較,具體數(shù)值實驗結(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)的,同時滿足

?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.

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

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

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

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

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

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