一種帶對(duì)數(shù)二次鄰近項(xiàng)定制臨近點(diǎn)的算法

李思吉，申 遠(yuǎn)

（南京財(cái)經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，江蘇 南京 210023）

對(duì)于傳統(tǒng)的帶有線性等式約束的凸優(yōu)化問題

其中θ(x) :Rn→R 是一個(gè)凸函數(shù)。A∈Rm×n，B∈Rm，χ?Rn是非空閉凸集。問題（1）的解集用χ*來表示，并且假設(shè)χ*非空。這是一個(gè)簡(jiǎn)單的1-block凸優(yōu)化問題，很多實(shí)際問題如壓縮傳感、圖像處理、機(jī)器學(xué)習(xí)等，都可以轉(zhuǎn)化成問題（1）的形式來求解。

處理問題（1）的算法有很多，最基礎(chǔ)的是增廣拉格朗日方法（ALM），是由Magnus 等[1-2]于1969 年提出。增廣拉格朗日函數(shù)將約束條件合并到目標(biāo)函數(shù)中，在拉格朗日函數(shù)基礎(chǔ)上添加了一個(gè)懲罰項(xiàng)，問題（1）的增廣拉格朗日函數(shù)為

相應(yīng)的增廣拉格朗日方法的迭代格式如下

其中λ∈Rm，是拉格朗日乘子，x∈χ，β＞0 是線性約束的罰參數(shù)。

另一個(gè)處理線性凸優(yōu)化問題的有效方法是鄰近點(diǎn)算法（Proximal Point Algorithm，PPA），該方法最早是由Moreau在1965年提出來的[3]。1976年，Rockafellar指出ALM方法和PPA方法之間的關(guān)系：ALM方法是應(yīng)用到模型對(duì)偶問題上的PPA方法[4]。1999年，Alfred 論證了ALM 算法與PPA 算法之間的關(guān)系[5]，但是在該論證中并沒有提及PPA 算法的收斂率。2019 年，顧國(guó)勇等對(duì)經(jīng)典PPA 算法進(jìn)行了嚴(yán)格的證明，并得出該算法具有次線性收斂率[6]。

然而經(jīng)典PPA算法局限于處理無約束優(yōu)化問題，要處理帶約束的問題就需要對(duì)它進(jìn)行改進(jìn)。2009年，何炳生提出帶有二次鄰近項(xiàng)的LPPA算法[7]；2013年，何炳生等又提出了可以處理帶有線性等式約束的定制鄰近點(diǎn)算法(Customized Proximal Point Algorithm，簡(jiǎn)稱CPPA方法)，通過數(shù)值實(shí)驗(yàn)顯示當(dāng)目標(biāo)函數(shù)簡(jiǎn)單時(shí)CPPA方法比ALM方法更加高效[8]。

求解問題（1）的CPPA方法的迭代格式如下

其中x∈χ，ω:=(x,λ)T，是二次鄰近正則項(xiàng)。2014 年，顧國(guó)勇探討了CPPA 方法的更多細(xì)節(jié)[9]；2020年，鄧康等提出了gCPPA方法與eCPPA方法[10]。這些方法的共同特點(diǎn)是都帶有會(huì)使子問題復(fù)雜二次鄰近正則項(xiàng)，尤其當(dāng)變量x≥0 時(shí)，帶有二次正則項(xiàng)的CPPA 子問題更不容易求解。對(duì)于子問題不易解的問題，可以運(yùn)用對(duì)數(shù)二次鄰近項(xiàng)（logarithmic-quadratic proximal terms，LQP）替換二次正則項(xiàng)，利用LQP良好的內(nèi)點(diǎn)性質(zhì)和可分性質(zhì)，極大地降低了求解難度。LQP 是由Auslender 在1999 年提出的[11]，之后在求解兩塊的分離結(jié)構(gòu)變分不等式問題上得到了廣泛的應(yīng)用，例如文獻(xiàn)[12]通過將LQP 和ADM方法結(jié)合，利用LQP項(xiàng)的內(nèi)點(diǎn)性質(zhì)降低子問題的復(fù)雜程度。2014 年，Bnouhachem 將LQP-ADM 擴(kuò)展，提出了不精確的LQP-ADM 方法[13]；2020 年，他又進(jìn)一步提出了解決3塊可分離結(jié)構(gòu)變分不等式的下降LQP-ADM方法[14]。

本文主要考慮的問題是求解變量非負(fù)的帶有線性等式約束的凸優(yōu)化問題

其中θ(x) :Rn→R 是一個(gè)凸函數(shù)。A∈Rm×n，B∈Rm，χ?Rn是非空閉凸集。我們將LQP與CPPA算法結(jié)合，提出一種新算法——LQP-CPPA方法，該方法用LQP 正則項(xiàng)代替?zhèn)鹘y(tǒng)的二次鄰近正則項(xiàng)，使它的每個(gè)子問題都可解并且證明此算法的全局收斂性。本文的LQP-CPPA 方法利用LQP 項(xiàng)降低了CPPA子問題的求解難度，并且將非負(fù)約束的優(yōu)化問題轉(zhuǎn)化為無約束問題。

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

1.1 對(duì)數(shù)二次鄰近正則項(xiàng)（LQP）

對(duì)任意的z∈，LQP正則項(xiàng)定義為

關(guān)于引理1的證明見文獻(xiàn)[8]。

1.2 等價(jià)的變分不等式

由問題（1）的一階最優(yōu)條件得到，求解問題（1）等價(jià)于求解

其 中f(x*)∈?θ(x*)，并且通過令u=(x,λ)T，F(xiàn)(u)=(f(x)-ATλ,Ax-b)T和Ω=χ×Rm，式（11）可以寫成等價(jià)的變分不等式問題（VI(Ω,F)）：

?u∈Ω，找到u*∈Ω和f(x*) ∈?θ(x*)，使得(u-u*)TF(u*)≥0 成立。

我們用LQP 正則項(xiàng)去替換式（4）中的二次鄰近項(xiàng)，得到新的生成預(yù)測(cè)點(diǎn)的迭代格式（12）。

2 對(duì)于求解變分不等式問題的LQP-CPPA方法

Step1通過求解非線性方程得到預(yù)測(cè)點(diǎn)

Step2更新拉格朗日乘子

Step3生成校正點(diǎn)

3 新算法的一些重要性質(zhì)

在證明新算法的全局收斂性之前，我們先證明一些簡(jiǎn)單的引理，這些引理將在證明新算法的全局收斂性時(shí)起到重要的作用。

定理1關(guān)于給定的xk由新算法生成的新的迭代點(diǎn)xk+1，對(duì)于任意的x*∈χ*，得到

證畢。定理1 說明，由新算法生成的序列{xk}是Fejer單調(diào)的。

定理2對(duì)于給定的λk，由新算法生成的λk+1滿足對(duì)任意的λ*∈Λ*，有

證畢。定理2說明，由新算法生成的序列{λk} 也是Fejer單調(diào)的。

定理3對(duì)于給定的uk，由新算法生成的uk+1對(duì)于任意的u*∈Ω*，有

證明：由u的定義，有

將定理1和定理2應(yīng)用到式（34）中，得到

證畢。定理3 說明，由新算法生成的序列{uk}是Fejer單調(diào)的。

4 全局收斂性

定理4由LQP-CPPA 算法生成的序列{uk} 收斂到某個(gè)u∞，其中u∞是式（11）的解。

證明：由定理1-3，序列{xk},{λk},{uk} 都是有界的，并且

另一方面，有

并且由有界序列必有收斂子列知{uk}至少有一個(gè)聚點(diǎn)，令u∞是{uk} 的一個(gè)聚點(diǎn)，則存在子列收斂到u∞，這樣在式（40）中代入k=kj-1，有

令j→∞對(duì)兩端取極限，由極限的保號(hào)性有

這是式（11）的解，又因?yàn)槎ɡ?對(duì)所有解集中的點(diǎn)都成立，所以有

因此，序列{uk}收斂到u∞，并且u∞是式（11）的u∞解，(x∞,λ∞)是VI(Ω,F)的解。這樣，就得到了算法LQP-CPPA的全局收斂性。

5 結(jié)論

本文主要考慮解決變量非負(fù)的帶有線性等式約束凸優(yōu)化問題的算法，通過將傳統(tǒng)的CPPA 方法中的二次正則項(xiàng)替換為L(zhǎng)QP 項(xiàng)，將傳統(tǒng)的CPPA 方法與LQP 方法相結(jié)合得到新的解決變量非負(fù)的帶有線性等式約束凸優(yōu)化問題的LQP-CPPA 算法，新算法求解時(shí)的子問題中不再含有二次項(xiàng)，而是含有非線性項(xiàng)，使得需要求解的子問題變成了解一個(gè)非線性方程，將變量非負(fù)的約束轉(zhuǎn)為無約束，這樣克服了CPPA方法對(duì)要求變量非負(fù)的問題失靈的不足，它比帶有二次項(xiàng)的子問題好解，并且我們證明了新算法的一些性質(zhì)和全局收斂性。