同時(shí)次梯度投影算法求解分裂可行性線性收斂性研究①

王曉霞

(齊齊哈爾大學(xué)理學(xué)院，黑龍江 齊齊哈爾 161000)

0 引 言

有限維歐式空間中的分裂可行性問題是一種實(shí)際工程中抽象出來的一種應(yīng)用廣泛的數(shù)學(xué)模型，在信號(hào)處理、圖像重建和醫(yī)學(xué)模擬等方面都發(fā)揮著重要的作用，備受相關(guān)學(xué)者關(guān)注[1]。多集分裂可行性問題(MSSFP)是分裂可行性問題的一個(gè)重要推廣，其本質(zhì)與分裂可行性問題的本質(zhì)相同，均為一種優(yōu)化問題。目前，針對多集分裂可行性問題，許多學(xué)者提出了不同的求解算法，均取得一定成效，但這些算法的收斂性不夠優(yōu)秀，收斂速度也無法得到保證[2]。使用動(dòng)態(tài)步長的方法來對傳統(tǒng)的梯度投影算法進(jìn)行優(yōu)化，利用帶有動(dòng)態(tài)步長的同時(shí)次梯度投影算法(SSPA)求解希爾伯特空間中的多集分裂可行性問題，并對該算法的收斂性與收斂速度進(jìn)行研究。研究結(jié)果表明，SSPA算法擁有優(yōu)秀的收斂性和較快的收斂速度，能夠高效求解多集分裂可行性問題，具有較高的實(shí)用價(jià)值。

1 SSPA算法對多集分裂可行性問題的求解

1.1 希爾伯特空間中MSSFP問題的預(yù)備知識(shí)

(1)

公式(1)中，x為H中的一個(gè)點(diǎn)。多集分裂可行性問題的解集能夠表示為公式(2)。

S:=C∩A-1Q={x∈C:Ax∈Q}

(2)

公式(2)中，S表示多集分裂可行性問題的解集。當(dāng)多集分裂可行性問題的解集連續(xù)時(shí)，則表示S為非空閉凸集合，則有公式(3)。

(3)

‖xn-x*‖≤ωσn

(4)

公式(4)中，xn為希爾伯特空間H中的一個(gè)數(shù)列，σ為收斂率，且取值范圍為0～1，x*表示序列的線性收斂極限ω>0，n為一個(gè)正整數(shù)。多集分裂可行性問題為有界線性正則，其具體描述為：若對于任意r>0都有一個(gè)對應(yīng)常數(shù)τr>0，使任意一個(gè)x∈C∩rB都有如公式(5)所示。

τrds(x)≤dQ(Ax)

(5)

公式(5)中，ds(x)表示點(diǎn)x到集合S的距離，dQ(Ax)表示點(diǎn)x到集合Q的距離。設(shè)G:H→H2為一個(gè)有界線性算子，則用kerG表示G的核，則有公式(6)。

kerG={y∈H:Gy=0}

(6)

kerG的正交補(bǔ)則表示為kerG⊥，其表達(dá)式如公式(7)所示。

kerG⊥={x∈H:〈y,x〉=0,?y∈kerG}

(7)

kerG與kerG⊥都是H的閉子集。設(shè)G:H→H2為一個(gè)有界線性算子，則G為單射且有閉值域，且G為下方有界，那么則有一個(gè)數(shù)v使得所有的w∈H都有公式(8)成立。

‖Gw‖≥v‖w‖

(8)

公式(8)中，v是一個(gè)正整數(shù)。設(shè){S′,kerG}為有界線性正則，且G有閉值域，則多集分裂可行性問題滿足有界線性正則的條件。結(jié)合上述公式與內(nèi)容，即可證明多集分裂可行性問題是有界線性正則的。

1.2 帶有動(dòng)態(tài)步長的同時(shí)次梯度投影算法

求解多集分裂可行性問題的核心思想即將待求解的問題轉(zhuǎn)化為最小化問題來進(jìn)行求解。對于多集分裂可行性問題，一般采用投影梯度法來進(jìn)行求解[4]，投影梯度法的迭代形式如公式(9)所示。

(9)

公式(9)中，Ω是一個(gè)輔助的簡單閉凸集合，且滿足Ω?RN，p(x)是一個(gè)函數(shù)，用來表示任意點(diǎn)x到所有集合的距離。投影梯度算法的計(jì)算量大，操作難度較高，因此有學(xué)者基于投影梯度算法，提出一種易于執(zhí)行、操作簡便的，利用正交投影到半空間來對多集分裂可行性問題進(jìn)行求解的同步次梯度投影算法[5-6]，如公式(10)所示。

(10)

公式(10)中，s∈(0,2)，ρ(A*A)是A*A的譜半徑，αi,βi均大于0。同步次梯度投影算法解決了投影梯度算法計(jì)算量大，執(zhí)行不便的缺點(diǎn)，但同步次梯度投影算法的步長為固定步長，因此算法的收斂速率較慢，求解多集分裂可行性問題的效率較低[7]。針對這一問題，有學(xué)者基于求解凸可行性問題的外推法提出一種同時(shí)次梯度投影算法，用以求解多集分裂可行性問題，該算法利用算法在迭代過程中的外推因子來提高收斂速率。為了進(jìn)一步提高算法的收斂性，研究提出一種帶有動(dòng)態(tài)步長的同時(shí)次梯度投影算法。設(shè)有兩個(gè)集合Ci,Qj，其表達(dá)式如公式(11)。

(11)

公式(11)中，ci:H1→R與qi:H2→R都是凸函數(shù)。假設(shè)ci與qj分別在H1與H2上均為次可微，且?ci和?qj在有界集上有界，根據(jù)次梯度的定義可以得到公式(12)。

(12)

公式(12)中，Ci,n為一個(gè)半空間，包含Ci，Qj,n為一個(gè)半空間，包含Qj。則有公式(13)。

(13)

利用正交投影定理，即能求解出點(diǎn)Ci,n到點(diǎn)Qj,n之間的距離，大大降低了計(jì)算量。多集分裂可行性問題的逼近函數(shù)如公式(14)所示。

(14)

公式(14)中，p(x,y)是多集分裂可行性問題的逼近函數(shù)，且對于任意的i與j，都有公式(15)。

(15)

根據(jù)公式(11)。即可得知函數(shù)p(x,y)具有是凸可微，并且具有梯度，如公式(16)。

(16)

基于公式(16)，提出一種新的迭代算法來求解多集分裂可行性問題，如公式(17)。

xn+1=xn-

(17)

公式(17)中，0

(18)

根據(jù)公式(17)，即可得到求解多集分裂可行性問題的SSPA算法。對于公式(11)中的每一個(gè)初始點(diǎn)x0∈C，序列{xn+1}由公式(19)生成。

xn+1=xn-

(19)

公式(19)在任意迭代次數(shù)n處應(yīng)滿足收斂性，如公式(20)。

(20)

滿足公式(20)的同時(shí)，還應(yīng)該滿足公式(21)。

(21)

在公式(21)中，αi應(yīng)滿足公式(22)。

(22)

SSPA算法能夠高效求解多集分裂可行性問題。

2 對SSPA算法求解MSSFP問題的性能研究

2.1 SSPA算法的收斂性研究

為驗(yàn)證SSPA算法是否具有收斂性利用Wolfram Mathematica軟件對算法的性能進(jìn)行測試，測試結(jié)果如圖1所示。

圖1 SSPA算法的收斂性能

從圖1(a)能夠看出，隨著迭代次數(shù)的增加，SSPA算法的均方誤差在減少，精度在上升，說明算法具有收斂性。SSPA算法在迭代171次時(shí)，誤差精度達(dá)到0.001，這說明 SSPA算法具有良好的收斂性。由圖1(b)能夠看出，處理的問題規(guī)模越大，算法需要的迭代次數(shù)越多。在處理問題規(guī)模為7時(shí)，SSPA需要迭代48次，在處理問題規(guī)模為11時(shí)，算法需要迭代146次，當(dāng)處理問題規(guī)模為14時(shí)，算法需要迭代270次，與實(shí)際情況相符合，說明算法具有實(shí)用性。

2.2 對SSPA算法的各項(xiàng)性能研究

在求解多集分裂可行性問題時(shí)，算法在迭代次數(shù)、計(jì)算次數(shù)以及運(yùn)算時(shí)間等方面的性能會(huì)對求解過程的速度、效率、以及求解結(jié)果的精度造成極大的影響。為驗(yàn)證SSPA算法能否滿足實(shí)際需求，將同時(shí)次梯度投影算法記為算法2，投影梯度算法記為算法3，測試并對比三種算法的性能，P為當(dāng)前算法在t倍最佳時(shí)間內(nèi)優(yōu)于其他算法的幾率，測試結(jié)果如圖2所示。

圖2 SSPA算法的各項(xiàng)性能對比

從圖2中能夠看出，SSPA算法在迭代次數(shù)、計(jì)算次數(shù)以及運(yùn)算時(shí)間等方面的性能的數(shù)值表現(xiàn)均優(yōu)于同時(shí)次梯度投影算法和投影梯度算法。從圖2(a)中可以看出，SSPA算法求解全部問題的迭代次數(shù)會(huì)明顯低于另外兩種算法；在一定時(shí)間內(nèi)，SSPA算法以最少的迭代次數(shù)能夠?qū)?4.9%的測試問題進(jìn)行成功求解；同時(shí)次梯度投影算法以最少的迭代次數(shù)能夠?qū)?8.2%的測試問題進(jìn)行成功求解，比SSPA算法少16.7%；投影梯度算法以最少的迭代次數(shù)能夠?qū)?8%的測試問題進(jìn)行成功求解，比SSPA算法少26.9%。從圖2(b)能夠看出，SSPA算法求解全部問題的計(jì)算次數(shù)明顯低于另外兩種算法，在25倍最佳時(shí)間內(nèi)，SSPA算法能夠以最少的計(jì)算次數(shù)求解98.7%的問題，比同時(shí)次梯度投影算法的93.6%高5.1%；比投影梯度算法的89%高9.7%。從圖2(c)能夠看出，改進(jìn)三項(xiàng)共軛梯度算法求解全部問題的運(yùn)算時(shí)間遠(yuǎn)少于另外兩種算法，在一定時(shí)間內(nèi)，SSPA算法能以最少的運(yùn)算時(shí)間求解74.8%的測試問題。

2.3 SSPA算法的收斂速度研究

為驗(yàn)證SSPA算法的收斂速度優(yōu)于同時(shí)次梯度投影算法和投影梯度算法，將同時(shí)次梯度投影算法記為算法2，投影梯度算法記為算法3，以同樣的多集分裂可行性問題測試三種算法的收斂速度，測試結(jié)果如圖3所示。

圖3 SSPA算法的收斂速度

從圖3中能夠看出，SSPA算法要使精度達(dá)到0.001需要迭代124次；同時(shí)次梯度投影算法要達(dá)到0.001的精度需要迭代261次，比SSPA算法多137次；而投影梯度算法迭代350次之后也未能達(dá)到0.001的精度。以上結(jié)果說明，SSPA算法的迭代速度更快，更適合用來求解多集分裂可行性問題。

3 結(jié) 語

目前針對多集分裂可行性問題的求解算法的收斂性不夠優(yōu)秀，收斂速度較慢。利用帶有動(dòng)態(tài)步長的同時(shí)次梯度投影算法多集分裂可行性問題，并對算法的性能進(jìn)行驗(yàn)證。結(jié)果表明，隨著迭代次數(shù)的增加，SSPA算法的精度在上升，說明算法具有收斂性；SSPA算法以最少的迭代次數(shù)能夠?qū)?4.9%的測試問題進(jìn)行成功求解，比算法2多16.7%，比算法3多26.9%；在25倍最佳時(shí)間內(nèi)，SSPA算法能夠以最少的計(jì)算次數(shù)求解98.7%的問題，比算法2多5.1%，比算法3多9.7%；在一定時(shí)間內(nèi)，SSPA算法能以最少的運(yùn)算時(shí)間求解74.8%的測試問題；，SSPA算法要使精度達(dá)到0.001需要迭代124次，比算法2少137次，算法3在350次迭代后未能達(dá)到目標(biāo)精度。以上結(jié)果說明，SSPA算法是一種收斂性優(yōu)秀，收斂速度快的算法，有較高的實(shí)用價(jià)值。接下來需要嘗試將SSPA算法與實(shí)際問題相聯(lián)系，提高其實(shí)用性。