王曉霞

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

0 引 言

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

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

1.1 希爾伯特空間中MSSFP問題的預備知識

(1)

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

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

(2)

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

(3)

‖xn-x*‖≤ωσn

(4)

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

τrds(x)≤dQ(Ax)

(5)

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

kerG={y∈H:Gy=0}

(6)

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

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

(7)

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

‖Gw‖≥v‖w‖

(8)

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

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

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

(9)

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

(10)

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

(11)

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

(12)

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

(13)

利用正交投影定理，即能求解出點Ci,n到點Qj,n之間的距離，大大降低了計算量。多集分裂可行性問題的逼近函數(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)中的每一個初始點x0∈C，序列{xn+1}由公式(19)生成。

xn+1=xn-

(19)

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

(20)

滿足公式(20)的同時，還應該滿足公式(21)。

(21)

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

(22)

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

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

2.1 SSPA算法的收斂性研究

為驗證SSPA算法是否具有收斂性利用Wolfram Mathematica軟件對算法的性能進行測試，測試結果如圖1所示。

圖1 SSPA算法的收斂性能

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

2.2 對SSPA算法的各項性能研究

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

圖2 SSPA算法的各項性能對比

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

2.3 SSPA算法的收斂速度研究

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

圖3 SSPA算法的收斂速度

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

3 結 語

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