分裂可行問題自適應(yīng)步長慣性球松弛CQ算法

張雅軒，張亞龍

（中國民航大學(xué)理學(xué)院，天津 300300）

分裂可行性問題是指找一點x*，滿足x*∈C，Ax*∈Q，其中，C 和Q 分別是Hilbert 空間H1和H2中的非空閉凸子集，A 是H1→H2的有界線性算子。該問題首次由Censor 等[1]在有限維Hilbert 空間中提出，且得到了廣泛應(yīng)用。近年來，許多學(xué)者提出了求解分裂可行性問題的迭代算法，其中，被廣泛關(guān)注的一種是Byrne[2]提出的CQ 算法。但在算法實現(xiàn)中，一般閉凸子集上的投影不易計算，確定步長取值范圍的算子范數(shù)也難于估計。針對第一個問題，Yang[3]提出了半空間松弛CQ 算法，Yu 等[4]提出了另一種用閉球進行松弛的CQ 算法。針對第二個問題，López 等[5]提出用自適應(yīng)步長代替算法中的固定步長，Qu 等[6]將Armijo 線搜索用于分裂可行問題CQ 算法的步長設(shè)計。近年來慣性加速算法大量涌現(xiàn)，對算法收斂速度的提升效果明顯。Polyak[7]首次從微分方程角度提出慣性項，并將其用于光滑凸優(yōu)化問題求解加速，但沒有涉及慣性項在分裂可行性問題中的應(yīng)用。綜上所述，在經(jīng)典CQ 算法基礎(chǔ)上，采用自適應(yīng)步長及球松弛方法，并引入慣性項構(gòu)造新算法，用于求解分裂可行性問題，可有效加快算法的收斂速度。最后證明算法在無限維Hilbert 空間中強收斂。

1 預(yù)備知識

設(shè)H 是一個Hilbert 空間，稱T ∶H→H 為firmly非擴張映像，如果?x，y∈H

其中，T 為firmly 非擴張映像當(dāng)且僅當(dāng)I-T 也為firmly 非擴張映像。

設(shè)C 為H 中的非空閉凸子集，定義度量投影算子PC:H→C 為

投影算子為firmly 非擴張映像。

引理1[8]設(shè)數(shù)列{sn}和{cn}為非負(fù)實數(shù)列，滿足

其中：{an}?（0，1）；{cn}為實數(shù)列。假定則①如果bn≤anM（M＞0），則{sn}有界；②如果且則

引理2[9]設(shè){sn}為非負(fù)實數(shù)列，滿足

其中：{αn}?（0，1）；{ηn}是非負(fù)實數(shù)列。若{αn}、{ηn}和{γn}滿足：蘊含則有

2 算法及其強收斂性

假設(shè)集合C={x∈H1| c（x）≤0}，集合Q={y∈H2| q（y）≤0}，其中，c:H1→（-∞，+∞]，q:H2→（-∞，+∞]為下半連續(xù)的強凸函數(shù)。定義

其中：ξk∈?c（xk）；ηk∈?q（Axk）。如果c 和q 分別為α-強凸函數(shù)和β-強凸函數(shù)，可證明和為分別包含C，Q 的閉球[4]。

進一步假定H1：分裂可行性問題的解集用S 表示且非空，H2：c 和q 的次微分在有界集上有界。記

算法1任取u，x0，x1，假設(shè)αk∈（0，1），βk∈（0，1），有

定理1若：其中，β∈[0，1），‖xk-xk-1‖=0，則{xk}強收斂于PSu。

證明設(shè)x*=PSu，由I-與I-是firmly 非擴張映像，可得

則由式（3）及算法1 中λk的定義，有

由算法1 可知0＜ρk＜4，則

由式（5）和式（6）有

其中

由定理1 中條件③及引理1 中①表明，數(shù)列{xk}、{yk}、{Δfk（yk）}都有界。

另一方面

結(jié)合式（4）可得

綜合式（7）和式（8）可得

令

則式（9）可重寫為

根據(jù)引理2 及定理1 的條件②和③，要證明{xk}強收斂，只需證明蘊含

同理可知

根據(jù)投影算子的性質(zhì)，有

另一方面，由定理1 的條件③，有

從而有

由式（10）、（11）和（12）可得

證畢。

3 結(jié)語

針對分裂可行性問題，在有限維空間中自適應(yīng)步長的球松弛CQ 算法基礎(chǔ)上，添加了慣性項加快收斂速度；同時利用Halpern 迭代格式調(diào)整算法。最后，證明算法在無限維Hilbert 空間中強收斂。