申 遠(yuǎn)，陳智琦

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

本文考慮帶有線性約束的凸優(yōu)化問題，形式如下：

min{θ(x)|Ax=b,x∈χ}，

(1)

這里χ?Rn是有界閉凸集，θ:χ→R是一個凸函數(shù)(但不一定光滑)，以及A∈Rm×n，b∈Rm。問題(1)的解集記為χ*，并且假設(shè)其非空。

為了求解問題(1)，目前已經(jīng)有許多有效的算法，例如Powell[1]和Hestenes[2]提出的增廣拉格朗日乘子法(augmented Lagrangian method,簡稱ALM)是一種經(jīng)典的算法，其迭代格式如下：

(2)

β>0為懲罰參數(shù)。

由Moreau[3]提出的鄰近點算法(proximal point algorithm，簡稱PPA)，該算法由Kaplan和Tichatschke[4]，Martinet[5]等人推廣。何炳生[6]提出了帶線性鄰近項的鄰近點算法(Proximal-Point Algorithm Using a Linear Proximal Term，簡稱LPPA)，何炳生和袁曉明在[7]中將Chambolle[8]提出的原始對偶方法解釋為經(jīng)典PPA的應(yīng)用。在此基礎(chǔ)上，何炳生和袁曉明在[9]中提出了定制鄰近點算法(customized proximal point algorithm,簡稱CPPA)來求解問題(1)，其迭代格式如下：

(3)

松弛步驟為：

這里的γ為松弛因子，λ∈Rm是拉格朗日乘子，r,t>0是迭代參數(shù)。令ω:=(x,λ)，Ω:=χ×Rm。由(2)的一階最優(yōu)性條件和ωk+1∈Ω，可以得到：

θ(x)-θ(xk+1)+(ω-ωk+1)T[F(ωk+1)+Q(ωk+1-ωk)]≥0,ω∈Ω

(4)

(5)

本文將在第一章提出新的一種平衡定制鄰近點算法，第二章給出證明新算法收斂性所需要的一些引理，在第三章證明了新算法的全局收斂性，然后進(jìn)行數(shù)值實驗，最后給出全文的總結(jié)。

1 廣義平衡定制鄰近點算法

先介紹一些預(yù)備知識，然后給出本文提出新算法迭代以及框架。

問題(1)的拉格朗日函數(shù)為

L(x,λ)=θ(x)-λT(Ax-b)，

(6)

問題(1)的一階最優(yōu)性條件如下：

(7)

定義1以上變分不等式可簡記為：

VI(θ,F,Ω)θ(x)-θ(x*)+(ω-ω*)TF(ω*)≥0，?ω∈Ω，

(8)

本文提出的平衡定制鄰近點算法的迭代格式如下所示：

算法1廣義平衡定制鄰近點算法，GB-CPPA

給定ω∈Ω，由GB-CPPA所生成的新迭代ωk+1∈Ω通過如下步驟所得：

(9)

注記：

與GCPPA算法的參數(shù)條件進(jìn)行對比，當(dāng)γ=0時， BG-CPPA算法就是GCPPA算法。曲線越靠近坐標(biāo)軸，參數(shù)范圍越大(條件越放松)，圖一表明BG-CPPA曲線在GCPPA曲線的下方，更靠近坐標(biāo)軸，顯然參數(shù)條件更加放松。

圖1 參數(shù):

圖2 參數(shù):

由GB-CPPA的迭代(9)的一階最優(yōu)性條件可得：

因此對于?ω∈Ω，有如下的變分不等式：

將上式寫成緊湊的形式，如下所示：

(10)

2 新算法的引理和性質(zhì)

在證明GB-CPPA算法全局收斂性之前，本文先證明如下的幾個引理，這幾個引理將在本文所提出的新算法全局收斂性證明中起到重要作用。

引理1由定義1中(8)式所定義的解ω*∈Ω*，序列{ωk}是由GB-CPPA算法所生成的序列，因此成立下述不等式：

(11)

證明將x=x*，ω=ω*帶入(10)式中，可以得到：

(12)

因為F(ω)的仿射是斜對稱矩陣，所以映射F(ω)是單調(diào)的，因此

(ωk+1-ω*)TF(ωk+1)≥(ωk+1-ω*)TF(ω*),

(13)

這里ω*∈Ω*是(8)式的一個解，因此

θ(xk+1)-θ(x*)+(ωk+1-ω*)TF(ω*)≥0，

(14)

(13)式與(14)式相加，可得

θ(xk+1)-θ(x*)+(ωk+1-ω*)TF(ωk+1)≥0。

(15)

將(15)式代入(12)式中，可以得到(11)式。引理證明完畢。

下面證明Q是正定矩陣

由上式可知，矩陣Q與矩陣A合同，要證明Q是正定矩陣等價于證明矩陣A是正定矩陣。

令

M=rIn-α2AT(tIm+γATA)-1A。

(16)

引理2由GB-CPPA算法所生成的序列{ωk}滿足如下的不等式：

(17)

證明對于任意向量a，b，c，d∈Rn，成立下述恒等式：

令a=ω*，b=c=ωk+1，d=ωk帶入恒等式如下：

(18)

令a=λ*，b=c=λk+1，d=λk帶入恒等式如下：

(19)

將(18)式、(19)式帶入(11)式，整理如下：

(20)

根據(jù)式(10)所定義的矩陣Q，可以得到：

(21)

帶入(9)式中λ子問題的迭代，并且令K=tIm+γAAT，有如下公式：

(22)

將(22)式代入(21)式，可得：

(23)

把(23)帶入(20)式，即可得到(17)式。證明完畢。

3 GB-CPPA算法的收斂性

基于引理2，下面證明由GB-CPPA算法所生成的序列{ωk}的收斂性。

(24)

序列{ωk}收斂于(8)式的解集Ω*中的一個解。

(25)

將(17)式從k=0到k=K(K>1)求和，可得：

(26)

一方面，對于任意的K>1，合并(25)式和(26)式可知：

(27)

由于問題(1)的目標(biāo)函數(shù)是凸函數(shù)，它的解集Ω*是一個有界的非空閉凸集。

另一方面，對(26)式的左右兩端同時取極限，可得：

(28)

(29)

θ(x)-θ(x∞)+(ω-ω∞)TF(ω∞)≥0，?ω∈Ω。

因此ω∞∈Ω*是滿足(8)式的一個解。證明完畢。

4 數(shù)值實驗

我們將GB-CPPA算法與GCPPA算法通過數(shù)值實驗進(jìn)行比較，來研究新算法的實際計算效率，實驗測試在一臺配置為Intel(R) Core(TM) i7-7500U CPU 2.70GHz，8GB內(nèi)存，Windows10家庭中文版操作系統(tǒng),編程軟件為MatlabR2019b。

求解相關(guān)性矩陣校正問題，其形式如下：

(30)

對給定的(Xk,zk),由GB-CPPA算法產(chǎn)生新的迭代(Xk+1,zk+1)格式如下：

(31)

上式中x子問題等價形式如下：

對矩陣A做SVD分解:A=VΛVT, Λ=diag(λ1,λ2,…,λn),V是正交矩陣。

表1 GCPPA與GB-CPPA數(shù)值實驗結(jié)果

在迭代次數(shù)和運行時間兩方面，GB-CPPA算法的數(shù)值實驗效果均優(yōu)于GCPPA算法， GB-CPPA算法無論迭代次數(shù)還是計算時間均比GCPPA算法快5%～25%不等，平均大約快15%，具體實驗結(jié)果如圖3和圖4所示。從圖3和圖4的變化曲線可知，隨著矩陣維數(shù)的增長，GB-CPPA算法依然保持著穩(wěn)定的性能優(yōu)勢。

圖3 算法的迭代次數(shù)

圖4 算法的迭代時間

5 總結(jié)

在本文中，我們研究了具有線性等式約束的凸優(yōu)化問題，由于傳統(tǒng)的CPPA算法中的參數(shù)條件要求較嚴(yán)，基于GCPPA算法和BALM算法，進(jìn)一步放松了參數(shù)條件，提出了廣義平衡鄰近點算法。本文提出的新的算法，在各種應(yīng)用程序中更容易實現(xiàn)，在實際問題的應(yīng)用中更加廣泛，并且還證明了新算法的全局收斂性。