一種求解單調(diào)包含問題的慣性混合鄰近外梯度算法

何明明, 彭建文

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

1 引言

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

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

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

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

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

初始化任取初始點x0∈X, 任意給定令k=1.

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

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

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

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

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

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

步驟2計算xk:

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

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

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

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

2 預備知識

若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是μ-強單調(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 是μ-強單調(diào)算子,B:X ?X 是單調(diào)算子, 則A+B也是μ-強單調(diào)算子.特別的, 兩個單調(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)算子當且僅當T(x)?T0(x).

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

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

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

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

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

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

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

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

算法1

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

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

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

步驟3計算xk

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

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

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

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

(iii) 當αk≡0 時, 算法1 退化為文獻[9]中的求解問題(3.1) 的算法1.

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

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

(vi) 當σk≡0 時, 算法1 退化為文獻[4]中的慣性鄰近點算法.

引理3.1令點列{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令點列{xk}, {yk}, {wk} 由算法1 生成, 則?x?∈(A+B)?1(0), 有

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

由(3.4) 式可知

從而由(3.10) 式有

事實上, (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令點列{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令點列{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]令點列使得其中如(3.15) 式所定義, 且滿足(3.19) 式.則?k≥1, 有

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

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

(i) 點列{xk?wk?1}, {yk?wk?1}, {xk?yk}, {vk} 和{εk} 強收斂到零;

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

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

即點列{xk?wk?1}, {yk?wk?1}, {vk} 和{εk} 強收斂到零, 從而{xk?yk} 也強收斂到零.

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

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

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

命題3.7令點列{xk}, {yk}, {wk} 由算法1 生成, 令且

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

因此點列{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} 是單增非負數(shù)列, 且因此

當η∈(0,1) 時, 即σ∈(0,1), 令解得

另一方面, 當η=1 時, 即解得

在上述兩種情況下, 當αk≤αk+1≤α<β時都有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 可知點列{xk} 弱收斂到單調(diào)包含問題(3.1) 的解.

注3.3(i) 當σ=0 時, 算法1 退化為慣性鄰近點算法, 條件(3.23) 式退化為進一步, 當μ=0 時, 有則條件(3.23) 式退化為因此命題3.7 對文獻[4]中的命題2.1 作了推廣.

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

推論3.8令點列{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令點列{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) 式可知, 對?k≥1存在i∈{1,...,k} 使得

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

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

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

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

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

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

算法2

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

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

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

步驟3計算xk

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

注4.1(i) 當αk≡0,時, 算法2 退化為文獻[12]中的算法2.

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

從而可知

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

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

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

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

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

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

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

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

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

其中T:X ?X 是實Hilbert 空間X 中的極大單調(diào)算子,V是閉子空間,V⊥是V的正交補空間.特別的, 當V=X 時, 問題(5.1) 退化為單調(diào)包含問題(1.1).假設(shè)T是κ-強單調(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⊥上的正交投影.

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

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

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

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

算法3

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

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

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

步驟3計算xk

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

注5.1(i) 當αk≡0 且μ=0 時, 算法3 退化為文獻[21]中的算法2.

(ii) 算法3 是算法1 在選定λk≡1 時的特殊情況.事實上, 在算法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令點列{xk} 由算法3 產(chǎn)生, 且{λk}, {vk} 和{yk} 如(5.6) 式所定義, 令其中x?是單調(diào)包含問題0 ∈TV(x?)的解.令

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

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

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

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

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

6 總結(jié)

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