求解單調變分不等式的新次梯度外梯度算法

2022-11-28 03:57:24楊澈洲賀月紅龍憲軍

四川師范大學學報(自然科學版) 2022年6期

楊澈洲, 賀月紅, 龍憲軍

(重慶工商大學數學與統計學院, 重慶 400067)

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

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

(1)

(2)

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

(3)

近年來,為了解除Lipschitz常數對算法步長的限制,學者們進行了大量的研究,見文獻[8-9].Yang等[8]在如下算法中采用了一種新的自適應步長規則

(4)

其中

λn+1:=

該算法要求映射F是強單調且Lipschitz連續的,保持映射計算量的同時,不要求Lipschitz常數已知.隨后,Hieu等[9]進一步將映射F的強單調弱化為單調,提出了如下算法

(5)

其中

λn+1:=

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

受文獻[7-9]的啟發,本文提出了一種新的次梯度外梯度算法求解變分不等式問題.該算法引入Armijo線性搜索準則,在映射F是單調和一致連續的假設下,證明了由算法產生的無窮序列弱收斂到變分不等式問題的解,并用數值實驗驗證了算法的適用性.本文所得結果改進和推廣了文獻[7-9]中相應的結果.

1 相關定理及引理

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

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

為x在集合C上的投影.

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

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

則稱F是單調的.

引理 1.1[11]設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]設{an}、{bn}是2個非負實序列,?N>0,?n>N,滿足an+1≤an-bn,則{an}有界且

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

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

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

2 算法及收斂性證明

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

條件 2.1C為非空閉凸集.

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

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

步驟1計算

并給定xn、yn-1、yn和αn,構造半空間

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

z-yn〉≤0},

轉步驟2.

步驟2取αn為最大的

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

其中ln是使得下式成立的最小非負整數

λθ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},

轉步驟3.

步驟3計算

若xn+1=xn且

yn+1=yn=yn-1,

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

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

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

這與

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

矛盾,故C?Hn.

注 2.2若算法滿足停機準則xn+1=xn且

yn+1=yn=yn-1,

則

yn∈VI(F,C).

證明若算法中xn+1=xn,則根據算法中

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

可知存在如下關系式

〈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,同時根據算法中半空間所述不等式得

〈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假設條件2.1～2.3成立,則Armijo線性搜索準則(6)式有意義.

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

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

由F的一致連續性知

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

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

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

(7)

由柯西-施瓦茨不等式有

λθln‖F(yn-1)-F(yn)‖·

‖xn+1(α)-yn‖≥

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

(8)

結合(7)和(8)式有

λθln‖F(yn-1)-F(yn)‖>

(9)

對(9)式取極限可得

則獲得了矛盾.

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

引理 2.2設{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)

根據F的單調性和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)

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

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

(1-μ)‖xn+1-y

證畢.

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

‖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∈VI(F,C)有

再由引理1.4可知

注 2.3本文從以下2個方面改進了文獻[7]中的結果:

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

2) 本文采用Armijo線性搜索準則避免要求Lipschitz常數已知這一假設.

注 2.4本文從以下2個方面改進了文獻[8]中的結果:

1)F的強單調性弱化為單調性;

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

注 2.5本文采用Armijo線性搜索準則弱化了文獻[9]要求Lipschitz連續這一條件.

3 數值實驗

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

λ=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隨機產生,選取

‖xn‖≤err=10-4

為停機條件.在此條件下,對幾種算法進行比較,具體數值實驗結果如表1所示.