何明明, 彭建文

(重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,重慶401331)

1 引言

對(duì)于單調(diào)包含問題, 即: 找到x?∈X 使得

其中B:X ?X 是極大單調(diào)算子, X 是實(shí)Hilbert 空間.凸優(yōu)化問題, 平衡問題和單調(diào)變分不等式等許多問題都可以歸結(jié)為單調(diào)包含問題(1.1).單調(diào)包含問題在圖像處理和聚類等實(shí)際問題中有著廣泛的應(yīng)用[1].

鄰近點(diǎn)算法是解單調(diào)包含問題的一類經(jīng)典算法, 它由Martinet[2]提出, Rockafellar[3]進(jìn)一步發(fā)展而成.其迭代格式為

其中正則參數(shù)λk>0,Id是單位算子.Alvarez 和Attouch 于2001 年在文獻(xiàn)[4]中提出解含有單調(diào)算子的廣義方程的慣性鄰近點(diǎn)算法, 并證明了該算法的弱收斂性.

混合鄰近外梯度算法是由Solodov 和Svaiter[5]在1999 年針對(duì)單調(diào)包含問題提出的另一類算法.即

初始化任取初始點(diǎn)x0∈X, 任意給定令k=1.

步驟1選擇容差參數(shù)并找到y(tǒng)k,vk∈X,εk≥0 使其滿足

步驟2執(zhí)行一個(gè)外梯度步:xk+1=xk?λkvk.令k:=k+1, 返回步驟1.

實(shí)質(zhì)上, 混合鄰近外梯度算法是鄰近點(diǎn)算法的一種不精確版本, 在每一次迭代中, 對(duì)應(yīng)的近似子問題都應(yīng)在一個(gè)相對(duì)誤差準(zhǔn)則內(nèi)求解, 這與Rockafellar 提出的鄰近點(diǎn)算法的可加誤差準(zhǔn)則不同.混合鄰近外梯度算法的另一個(gè)特點(diǎn)是它還允許通過文獻(xiàn)[6]中提出的極大單調(diào)算子的ε-enlargement 來松弛單調(diào)算子.

混合鄰近外梯度算法作為設(shè)計(jì)新方法和分析現(xiàn)有方法的復(fù)雜性的框架特別有用.例如Monteiro 和Svaiter[7]在2013 年提出塊狀分解混合鄰近外梯度算法, 并證明了該算法的迭代復(fù)雜性, 且在該算法的框架下證明了交替方向乘子法的遍歷迭代復(fù)雜度; Goncalves, Melo 和Monteiro[8]在2017 年提出一種新的正則化混合鄰近外梯度算法, 并建立了該算法的迭代復(fù)雜性, 且證明了交替方向乘子法的變體是該算法的特殊實(shí)例; Alves 和Svaiter[9]在2016 年提出了一種新的求解強(qiáng)單調(diào)包含問題的混合鄰近外梯度算法:

初始化任取初始點(diǎn)x0∈X, 任意給定σ∈[0,1),k=1.

步驟1選定0<λk≤λk?1, 并找到y(tǒng)k,vk∈X,εk≥0, 使得

步驟2計(jì)算xk:

并用混合鄰近外梯度算法的框架證明了Korpelevich 外梯度算法的迭代復(fù)雜性.

近年來, 慣性鄰近點(diǎn)類算法被大量用于設(shè)計(jì)和分析各種具有慣性的一階鄰近算法.例如Chen[10]等人提出求解具有可分結(jié)構(gòu)的線性約束凸優(yōu)化問題的慣性交替方向乘子法, 并建立了漸近收斂率和非漸近收斂率; Bot, Csetnek 和Hendrich 在文獻(xiàn)[11]中提出了求解單調(diào)包含問題的慣性Douglas-Rachford 分裂算法, 并證明了該算法在希爾伯特空間中的收斂性;Bot 和Csetnek[12]在2015 年提出求解單調(diào)包含問題的慣性混合鄰近外梯度算法, 并建立了該算法的弱收斂性和漸近收斂性; Alves 和Marcavillaca 于2018 年在文獻(xiàn)[1]中提出一種求解單調(diào)包含問題的新的慣性混合鄰近外梯度算法, 并得到了它的漸近收斂率和非漸近全局收斂率.

受上述文獻(xiàn)的啟發(fā), 本文提出了一種新的求解單調(diào)包含問題的慣性混合鄰近外梯度算法,并得到了它的收斂性和非漸近全局收斂率.不同的是, 本文中的慣性系數(shù)的范圍得到了擴(kuò)大,其系數(shù)區(qū)間為特別的, 當(dāng)μ=0 時(shí), 慣性區(qū)間為[0,1], 正好與文獻(xiàn)[12]中的區(qū)間一致.

本文結(jié)構(gòu)如下: 首先是預(yù)備知識(shí), 對(duì)概念和符號(hào)進(jìn)行說明, 并對(duì)證明過程中所需的定理進(jìn)行說明; 然后是本文的主要內(nèi)容, 本文提出了一種用于求解單調(diào)包含問題的慣性混合鄰近外梯度算法, 并證明了它的非漸近全局收斂率.最后本文提出了慣性混合鄰近外梯度算法的兩種特殊情況: 求解含有Lipschitz 連續(xù)算子的強(qiáng)單調(diào)包含問題的慣性Tseng’s 向前向后算法,并建立了該算法的弱收斂性和非漸近全局收斂率; 求解含有強(qiáng)單調(diào)算子和Lipschitz 連續(xù)算子的原始―對(duì)偶問題的慣性非精確Spingarn’s 部分逆算法, 并得到了該算法的弱收斂性和非漸近全局收斂率.

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

若S?1(v)={x:v∈S(x)}, 則稱S?1:X ?X 是集值算子S的逆.

本文主要研究單調(diào)包含問題的求解算法, 即含有(極大) 單調(diào)算子的包含問題.在本節(jié)接下來的內(nèi)容中將回顧一些基本概念和結(jié)論.

定義2.1[12]若集值算子A:X ?X 滿足

則稱算子A是μ-強(qiáng)單調(diào)的.特別地, 如果μ=0 則稱A是單調(diào)的.

定義2.2[12]設(shè)算子A:X ?X 是單調(diào)的, 如果不存在其他單調(diào)算子B真包含于A, 則稱算子A是極大單調(diào)的.即如果單調(diào)算子B:X ?X 滿足Gr(A)?Gr(B), 則A=B.

集值算子S,:X ?X 的和S+:X ?X 定義為

顯然, 如果A:X ?X 是μ-強(qiáng)單調(diào)算子,B:X ?X 是單調(diào)算子, 則A+B也是μ-強(qiáng)單調(diào)算子.特別的, 兩個(gè)單調(diào)算子的和也是單調(diào)算子.

定義2.3[6]設(shè)算子T:X ?X 是極大單調(diào)的, 如果T[ε]:X ?X 滿足

則稱算子T[ε]是極大單調(diào)算子T的ε-enlargement.

注意到T?T[ε],?x∈X.從而可以將T[ε]視為T的外延或近似.下面是關(guān)于T[ε]的性質(zhì)的結(jié)論.

命題2.1[13]令T,S:X ?X 是集值映射, 則下列論述成立

(i) 如果ε≤則

(iii)T是單調(diào)算子當(dāng)且僅當(dāng)T(x)?T0(x).

(iv)T是極大單調(diào)算子當(dāng)且僅當(dāng)T(x)=T0(x).

(v) 如果T是極大單調(diào)算子,點(diǎn)列{(yk,vk,εk)}使得對(duì)于任意的k≥1 有vk∈T[εk](yk),點(diǎn)列{yk} 弱收斂于點(diǎn)x, 點(diǎn)列{vk} 收斂于點(diǎn)v和點(diǎn)列{εk} 收斂于點(diǎn)ε, 則v∈T[ε](x).

定理2.2[12](Opial 定理)令若對(duì)于任意的x?∈? 和X 中的數(shù)列{xk} 使得存在.如果{xk} 的每個(gè)弱聚點(diǎn)都屬于?, 則數(shù)列{xk} 弱收斂到? 中的點(diǎn).

引理2.3[14]令c,d∈X,p∈R, 則

3 慣性混合鄰近外梯度算法

一般來說, 問題(1.1) 多半是不適定的, 而對(duì)于含有強(qiáng)單調(diào)算子的單調(diào)包含問題總是適定的.因此在實(shí)際應(yīng)用中, 通過正則化將問題(1.1) 近似為強(qiáng)單調(diào)包含問題, 這一技術(shù)可追溯到Tikhonov[15]的工作中.下面考慮強(qiáng)單調(diào)包含問題

其中A:X ?X 是極大μ-強(qiáng)單調(diào)算子,B:X ?X 是極大單調(diào)算子.假設(shè)問題(3.1) 有解.

下面給出求解問題(3.1) 的慣性混合鄰近外梯度算法.

算法1

步驟0任取初始點(diǎn)x0=x?1∈X, 任意給定α∈[0,1),α0∈[0,α],σ∈[0,1),k=1;

步驟1選定αk∈[αk?1,α], 計(jì)算

步驟2選定0<λk≤λk?1, 并找到y(tǒng)k,vk∈X,εk≥0, 使得

步驟3計(jì)算xk

令k:=k+1, 返回步驟1.

注3.1(i) 對(duì)單調(diào)包含問題(1.1) 進(jìn)行正則化處理

其中μ>0,x0是初始點(diǎn).令A(yù)(x)=μ(x?x0), 則算子A是極大μ-強(qiáng)單調(diào)算子.此時(shí)問題(3.5) 是問題(3.1) 的特殊情況.A是μ-強(qiáng)單調(diào)算子, 根據(jù)Minty 定理[16]可知它的解集是單點(diǎn)集, 記是它的解, 即∈(μ?1B+Id)?1(x0).當(dāng)μ接近于0 時(shí), 它近似于問題(1.1)的解.

(ii) 針對(duì)問題(3.1) 也可以用文獻(xiàn)[12]中的慣性混合鄰近外梯度算法, 此時(shí)慣性系數(shù)的范圍從[0,1[; 而算法1 通過正則化的技巧將慣性系數(shù)的范圍從[0,1]擴(kuò)大為加快了迭代速度.

(iii) 當(dāng)αk≡0 時(shí), 算法1 退化為文獻(xiàn)[9]中的求解問題(3.1) 的算法1.

(iv) 當(dāng)μ=0 且αk≡0 時(shí), 算法1 退化為文獻(xiàn)[5]中的求解問題(1.1) 的混合鄰近外梯度算法.

(v) 當(dāng)αk≡0 且σk≡0 時(shí),xk?1=wk?1由(3.3) 式可知εk≡0 和xk?1?λkvk=yk,從而由(3.4) 式可知xk=yk=xk?1?λkvk.此時(shí), 算法1 退化為經(jīng)典的鄰近點(diǎn)算法[3].

(vi) 當(dāng)σk≡0 時(shí), 算法1 退化為文獻(xiàn)[4]中的慣性鄰近點(diǎn)算法.

引理3.1令點(diǎn)列{xk}, {yk}, {wk}, {αk}由算法1 生成, 取x∈X, 則?k≥1, 有

證由(3.2) 式可得wk?1?x=(1+αk?1)(xk?1?x)?αk?1(xk?2?x).將p=αk?1,c=xk?2?x,d=xk?1?x代入(2.3) 式, 即得(3.6) 式.

命題3.2令點(diǎn)列{xk}, {yk}, {wk} 由算法1 生成, 則?x?∈(A+B)?1(0), 有

證由(3.4) 式可知wk?1=(1+2λkμ)xk?2λkμyk+λkvk, 事實(shí)上,?a,b,c∈X, 有從而可知

由(3.4) 式可知

從而由(3.10) 式有

事實(shí)上, (1 ?ρk)=2λkμρk, 從而由(3.10) 式可得

由(3.9), (3.11) 和(3.12) 式可得

并聯(lián)立(3.3) 和(3.8) 式可得

若?x?∈(A+B)?1(0), 則存在a?∈A(x?), ?a?∈B[εk](x?).由(3.3) 式可知: 存在ak∈A(yk),bk∈B[εk](yk), 使得vk=ak+bk.由(2.1) 與(2.2) 式可知

命題3.3令點(diǎn)列{xk}, {yk} 和{wk}由算法1 生成, 令且定義sk為

證由(3.4) 式及ρk的定義可知xk=ρk(wk?1?λkvk)+(1 ?ρk)yk, 故

從而由三角不等式可知

由(3.3) 式可知

從而

并由(3.7) 和(3.14) 式可得到(3.15) 式.

命題3.4令點(diǎn)列{xk}, {yk}, {wk} 由算法1 生成,sk由(3.15) 式所定義, 并且令

證將x=x?代入(3.6) 式并由(3.18) 式可得

并由(3.15) 式可知

注意到, 0<ρk≤1, 有?k??k?1≤?k?ρk?k?1, 故(3.19) 式成立.

引理3.5[4]令點(diǎn)列使得其中如(3.15) 式所定義, 且滿足(3.19) 式.則?k≥1, 有

命題3.6令點(diǎn)列{xk},{λk}和{αk}由算法1 產(chǎn)生,如果對(duì)于任意的滿足下面的條件

則有下面的結(jié)論成立

(i) 點(diǎn)列{xk?wk?1}, {yk?wk?1}, {xk?yk}, {vk} 和{εk} 強(qiáng)收斂到零;

(ii) 點(diǎn)列{xk}, {wk?1} 和{yk} 弱收斂到單調(diào)包含問題(3.1) 的解.

證由于則并由命題3.4 和引理3.5 可知?x?∈存在, 故點(diǎn)列{xk} 有界, 而且由(3.2), (3.3) 和(3.14) 式可知

即點(diǎn)列{xk?wk?1}, {yk?wk?1}, {vk} 和{εk} 強(qiáng)收斂到零, 從而{xk?yk} 也強(qiáng)收斂到零.

令x∞∈X 是點(diǎn)列{xk} 的弱聚點(diǎn), 并令子列使得又由(3.2) 和(3.22)式可得

故由命題2.1(v) 可知,x∞∈(A+B)?1(0), 故根據(jù)定理2.2 可知點(diǎn)列{xk} 弱收斂到單調(diào)包含問題(3.5) 的解.由于{xk?wk?1} 和{xk?yk} 強(qiáng)收斂到零, 因此{(lán)wk?1} 和{yk} 也弱收斂到單調(diào)包含問題(3.1) 的解.

注3.2由于慣性鄰近點(diǎn)算法是算法1 的特殊情況, 因此命題3.6 是文獻(xiàn)[4]中定理2.1的推廣.

命題3.7令點(diǎn)列{xk}, {yk}, {wk} 由算法1 生成, 令且

則有q(α)>0, 且?x?∈(A+B)?1(0), 有

因此點(diǎn)列{xk} 弱收斂到單調(diào)包含問題(3.1) 的解.

證由(3.2) 式可知xk?wk?1=(xk?xk?1)?αk?1(xk?1?xk?2), 故

并聯(lián)立(3.19) 式可得

又由于{ρk} 和{αk} 是單增非負(fù)數(shù)列, 且因此

當(dāng)η∈(0,1) 時(shí), 即σ∈(0,1), 令解得

另一方面, 當(dāng)η=1 時(shí), 即解得

在上述兩種情況下, 當(dāng)αk≤αk+1≤α<β時(shí)都有q(αk)≥q(α) >q(β)=0, 從而由(3.28) 式可知

由ξk的定義可得從而由(3.29) 式有

聯(lián)立(3.30) 和(3.31) 式可得(3.25) 式.

又由于αk∈[0,1), 從而由(3.25) 式可知(3.21) 式成立, 由命題3.6 可知點(diǎn)列{xk} 弱收斂到單調(diào)包含問題(3.1) 的解.

注3.3(i) 當(dāng)σ=0 時(shí), 算法1 退化為慣性鄰近點(diǎn)算法, 條件(3.23) 式退化為進(jìn)一步, 當(dāng)μ=0 時(shí), 有則條件(3.23) 式退化為因此命題3.7 對(duì)文獻(xiàn)[4]中的命題2.1 作了推廣.

(ii) 如果σ=1, 則對(duì)于任意的∈[0,1), 二次函數(shù)并不能滿足算法收斂的條件, 從而說明了容差參數(shù)σ的最大取值范圍為[0,1).

推論3.8令點(diǎn)列{xk}, {yk}, {wk} 由算法1 生成.令如(3.23) 式所定義如(3.24) 式所定義, 且x?∈(A+B)?1(0), 假設(shè)αk≤αk+1≤α<β.則?k≥1, 有

證由(3.20) 和(3.25) 式可得

從而由sk的定義可知, (3.32) 式成立.

由柯西不等式及(3.3) 式可知

由(3.32) 式可知(3.33) 式成立.

接下來, 本文給出算法1 的非漸近性全局收斂率.

定理3.9令點(diǎn)列{xk}, {yk}, {wk} 由算法1 生成, 令如(3.23)式所定義如(3.24)式所定義假設(shè)αk≤αk+1≤α<β.則?k≥1, 存在i∈{1,...,k} 使得vi∈A(yi)+B[εi](yi), 而且

證令x?∈(A+B)?1(0)使得由(3.32) 和(3.33) 式可知, 對(duì)?k≥1存在i∈{1,...,k} 使得

注3.4定理3.9 說明了算法1 的全局逐點(diǎn)收斂率為

4 求解單調(diào)包含問題的慣性Tseng’s 向前向后算法

在這部分, 本文考慮單調(diào)包含問題

其中F:X →X 是(單值) 強(qiáng)單調(diào)和L-Lipschitc 連續(xù)算子, 即存在μ≥0 和L>0 使得

T:X ?X 是極大單調(diào)算子.假設(shè)問題有解, 即(F+T)?1(0) 非空.

下面本文給出求解問題(4.1) 的慣性Tseng’s 向前向后算法.

算法2

步驟0任取初始點(diǎn)x0=x?1∈X, 任意給定α∈[0,1),α0∈[0,α],σ< 1,k=1, 令任意給定λ0∈[0,];

步驟1選定αk∈[αk?1,α], 定義

步驟2選定0<λk≤λk?1, 計(jì)算yk

步驟3計(jì)算xk

令k:=k+1, 返回步驟1.

注4.1(i) 當(dāng)αk≡0,時(shí), 算法2 退化為文獻(xiàn)[12]中的算法2.

(ii) 算法2 是算法1 在選定εk≡0 時(shí)的特殊情況.事實(shí)上, 在算法2 中定義:A:=F,B:=T, 且

從而可知

將(4.8) 式代入(4.6) 式可得

即算法1 的步驟3 滿足.綜上可知, 算法2 是算法1 的特殊情形.

由于算法2 是算法1 的特殊情況, 因此由命題3.6, 3.7 和定理3.9 可得到下面的結(jié)論.

命題4.1令點(diǎn)列{xk} 由算法2 產(chǎn)生, 令和{vk}如(4.7)式所定義,其中x?∈(F+T)?1(0),β如(3.23)式所定義如(3.24) 式所定義, 假設(shè)αk≤αk+1≤α<β.則有下面的結(jié)論成立

(i) 點(diǎn)列{xk} 弱收斂到單調(diào)包含問題(4.1) 的解.

(ii) 對(duì)任意的k≥1 存在i∈{1,...,k} 使得vi∈F(yi)+B[εi](yi), 而且

注4.2(i) 命題4.1 說明了算法2 的全局逐點(diǎn)收斂率為

5 求解原始―對(duì)偶問題的慣性非精確Spingarn’s 部分逆算法

接下來, 本文考慮原始―對(duì)偶問題[17].找到x,u∈X 使得

其中T:X ?X 是實(shí)Hilbert 空間X 中的極大單調(diào)算子,V是閉子空間,V⊥是V的正交補(bǔ)空間.特別的, 當(dāng)V=X 時(shí), 問題(5.1) 退化為單調(diào)包含問題(1.1).假設(shè)T是κ-強(qiáng)單調(diào)和L-Lipschitc 連續(xù)算子.

定義5.1[18]稱TV: X ?X 是極大單調(diào)算子T: X ?X 關(guān)于X 中的閉子空間V的Spingarn’s 部分逆算子, 如果TV滿足

其中PV和PV⊥分別是V和V⊥上的正交投影.

由定義可知, 原始―對(duì)偶問題(5.1) 等價(jià)于單調(diào)包含問題0 ∈TV(x), 而且若x?是單調(diào)包含問題0 ∈TV(x?) 的解, 則z?=PV(x?),u?=PV⊥(x?) 是原始―對(duì)偶問題(5.1) 的解.

引理5.2[19]令T:X ?X 是X 中的極大單調(diào)算子,V是X 中的閉子空間, 且ε>0, 則(TV)[ε]=(T[ε])V.

引理5.3[20]如果極大單調(diào)算子T是κ-強(qiáng)單調(diào)和L-Lipschitc 連續(xù)算子, 則它的關(guān)于V的部分逆TV是μ-強(qiáng)單調(diào)的, 其中

下面給出求解原始―對(duì)偶問題(5.1) 的慣性非精確Spingarn’s 部分逆算法如下

算法3

步驟0任取初始點(diǎn)x0=x?1∈X, 給定α∈[0,1),α0∈[0,α],σ∈[0,1),k=1;

步驟1選定αk∈[αk?1,α], 計(jì)算

步驟2找到zk,uk∈X,εk≥0, 使得

步驟3計(jì)算xk

令k:=k+1, 返回步驟1.

注5.1(i) 當(dāng)αk≡0 且μ=0 時(shí), 算法3 退化為文獻(xiàn)[21]中的算法2.

(ii) 算法3 是算法1 在選定λk≡1 時(shí)的特殊情況.事實(shí)上, 在算法3 中定義A:=TV,B:=0, 且

由引理5.2, (5.2) 及(5.4) 式可知

從而由(5.6) 式可知vk∈(TV)[εk](yk)=A[εk](yk)+B(yk), 且

由λk≡1, (5.6), (5.7) 及(5.4) 式可知

即算法1 的步驟2 滿足.由λk≡1, (5.6), (5.7) 及(5.5) 式可知

即算法1 的步驟3 滿足.故算法3 是算法1 的特殊情形.

由于算法3 是算法1 的特殊情況, 因此由命題3.6, 3.7 和定理3.9 可得到下面的結(jié)論.

命題5.1令點(diǎn)列{xk} 由算法3 產(chǎn)生, 且{λk}, {vk} 和{yk} 如(5.6) 式所定義, 令其中x?是單調(diào)包含問題0 ∈TV(x?)的解.令

定義實(shí)函數(shù)q() 為

假設(shè)αk≤αk+1≤α<β, 則有下面的結(jié)論成立

(i) 點(diǎn)列{xk} 弱收斂到單調(diào)包含問題0 ∈TV(x) 的解.

(ii) 對(duì)任意的k≥1 存在i∈{1,...,k} 使得vi∈(TV)[εi](yi), 而且

注5.2有序?qū)?PV(xk),PV⊥(xk)) 弱收斂到原始―對(duì)偶問題(5.1) 的解.

6 總結(jié)

本文提出了一種新的求解單調(diào)包含問題的慣性混合鄰近外梯度算法, 并得到了該算法在實(shí)希爾伯特空間中的弱收斂性和非漸近全局收斂率.慣性混合鄰近外梯度算法包含一些現(xiàn)有的算法, 例如Tseng’s 向前向后算法和Spingarn’s 部分逆算法等.利用該算法的框架可以設(shè)計(jì)求解優(yōu)化問題與變分不等式問題的新的算法.