求解鞍點問題的修正MSOR-like方法

趙耿威，黃敬頻

(廣西民族大學(xué) 數(shù)學(xué)與物理學(xué)院， 南寧 530006)

0 引言

鞍點問題出現(xiàn)在許多計算科學(xué)與工程學(xué)領(lǐng)域[1-3]，比如大型稀疏矩陣壓縮存儲與求解[4]、約束最優(yōu)化計算[5]。文獻[6]指出高維非凸優(yōu)化問題之所以困難，是因為存在大量的鞍點而不是局部極值。這些鞍點通常被一個具有相同誤差的平面所包圍，使得各個維度上的梯度都趨于零且導(dǎo)致隨機梯度下降難于逃脫。鞍點矩陣一般是不定矩陣且具有較弱的譜條件，因此對鞍點問題的計算是困難而重要的研究領(lǐng)域。多年來，國內(nèi)外學(xué)者針對鞍點問題的研究提出了較多的研究方法，其中包括變尺度外梯度離散方法[7]、Uzawa類方法[8-9]、SOR類方法[10]和HSS類方法[11-12]等。此后一些學(xué)者又提出了改進的方法，如GSOR迭代法[13-14]、ASOR迭代法[15]等。

鞍點問題的一般形式為：

(1)

式中A∈Rm×m為非對稱正定矩陣，B∈Rm×n(m>n)為列滿秩矩陣，BT為B的轉(zhuǎn)置矩陣，x,f∈Rm且y,g∈Rn，這里f,g是已知向量，x,y是未知向量。

文獻[16]引入對稱正定矩陣Q∈Rn×n并對式(1)的系數(shù)矩陣作如下分解：

DM-LM-UM

(2)

并給出MSOR-like的迭代格式為[16]：

(3)

分析迭代(3)可知，MSOR-like迭代至少存在2個方面的缺陷：

1) 參變量正定矩陣Q在矩陣分裂(2)中不確定，使得應(yīng)用過程難以把握。

2) 單一松弛變量ω關(guān)聯(lián)系數(shù)矩陣的靈敏度低，不利于增強整體收斂速度。

針對上述問題，進一步改進MSOR-like迭代十分必要，從而提升式(1)的求解效率。

1 修正MSOR-like迭代構(gòu)建

為進一步改進MSOR-like迭代，在對矩陣A進行H，S分裂的基礎(chǔ)上，得到新的分解矩陣D，L，U，同時新增加2個參數(shù)來提高迭代關(guān)聯(lián)系數(shù)矩陣的靈敏度，以期提升迭代收斂速度。首先引入待定的對稱正定矩陣Q∈Rn×n及參數(shù)α和β，并對式(1)的系數(shù)矩陣分裂如下：

(4)

(5)

式中：ω>0,α>0,β≥0且D,L,U如式(4)所示。稱迭代(5)為修正MSOR-like方法，記為MMSOR-like。

顯然，當(dāng)α=1,β=0時，式(5)即為MSOR-like迭代(3)[16]；當(dāng)H=A,S=0時，式(5)即為SOR-like迭代[17]；當(dāng)H=A,S=0,α=1,β=0時，式(5)即為SOR-like迭代[18]；當(dāng)H=A,S=0,α=1時，式(5)即為SOR-like迭代[19]；當(dāng)H=A,S=0,β=1/2時，式(5)即為SOR-like迭代[20]。因此，新迭代格式(5)具有更廣泛的參數(shù)選取，從而進一步提升式(1)的求解效率。下面具體導(dǎo)出式(5)的求解格式。由于

(6)

根據(jù)矩陣H,Q的正定性和S的反對稱可知，矩陣D-ωL是非奇異的當(dāng)且僅當(dāng)ωβ≠1。因此假設(shè)ωβ≠1，并記

G=(D-ωL)-1[(1-ω)D+ωU]

T=ω(D-ωL)-1

通過簡單的計算可得

(7)

(8)

于是式(5)等價于

(9)

式中：G,T如式(7)和(8)所示。

2 MMSOR-like方法的收斂性

本節(jié)主要討論MMSOR-like迭代(9)的收斂性及相關(guān)參數(shù)的選取方法。用ρ(G)表示矩陣G的譜半徑，則由數(shù)值分析理論可知，迭代(9)收斂當(dāng)且僅當(dāng)ρ(G)<1。下面先給出幾個引理。

引理1設(shè)λ為矩陣(7)中G的非零特征值，則λ≠1。

證明由條件可設(shè)(xT,yT)T∈Rm+n為非零特征值λ對應(yīng)的特征向量，則有

G(xT,yT)T=λ(xT,yT)T

(10)

若λ=1，則把式(7)代入式(10)得

(11)

由式(11)及ω>0,可以導(dǎo)出

由于矩陣A是正定矩陣，B是列滿秩矩陣，從而方程(1)是非奇異的，所以有x=0,y=0，這與 (xT,yT)T是矩陣G的一個特征向量矛盾，因此λ≠1。證畢。

引理2設(shè)H∈Rm×m是一個對稱正定矩陣，S∈Rm×m是一個反對稱矩陣，非零向量x∈Rm，則H,S的Rayleigh商RH(x)>0,RS(x)=0。

證明根據(jù)Rayleigh商定義得

RH(x)=(xTHx)/(xTx)

由于H∈Rm×m是一個對稱正定矩陣，所以?0≠x∈Rm，xTHx>0，從而RH(x)>0。同理，當(dāng)S是反對稱矩陣時xTSx=0，所以RS(x)=0。證畢。

引理3設(shè)λ為式(7)中矩陣G的1個特征值且(xT,yT)T為λ對應(yīng)的特征向量，則x≠0。若y=0且限制0<αω<1，那么λ是實特征值且-1<λ<1。

證明設(shè)λ是G的特征值，(xT,yT)T為對應(yīng)的特征向量，則有等式(10)成立，把矩陣(7)代入式(10)可得

(12)

由式(12)可得

(13)

由式(13)可推知x≠0，否則由B列滿秩，從式(13)中第一式可得y=0，這與(xT,yT)T是矩陣G的一個特征向量相矛盾。若y=0，那么從式(13)中第一式可得

(14)

式(14)兩邊同時左乘xT/(xTx)得

(15)

引理4[21]實二次方程λ2-pλ+q=0的2個根的模均小于1，當(dāng)且僅當(dāng)|q|<1且|p|

定理1設(shè)式(7)中矩陣G的參數(shù)ω,α,β滿足以下條件：

(16)

式中：λmin[·]表示矩陣[·]的最小特征值，則求鞍點問題(1)的MMSOR-like迭代(9)收斂。

證明由引理1可得，迭代矩陣G的特征值λ≠1，因此當(dāng)0<ωβ<1時可以將特征方程(13)寫成如下形式：

(17)

將式(17)中的第二個等式y(tǒng)代入第一個等式，并兩邊同時左乘xT/(xTx)，可得

(18)

式中：a,b,c分別是矩陣H,S,BQ-1BT的Rayleigh商。注意到矩陣H對稱正定，S反對稱，BQ-1BT半正定，因此由引理2得a>0,b=0,c≥0。于是可將式(18)進一步化簡為：

(19)

又由式(19)及引理4得，若要滿足|λ|<1，當(dāng)且僅當(dāng)

(20)

從而由ω>0,0<ωβ<1求解不等式(20)可得

(21)

由式(21)的第二個不等式的右邊式子可知

所以有

(22)

(23)

(24)

式中：

將式(24)代入式(23)，并令u=Uv=(u1,u2,…,un)T得

λ1|u1|2+λ2|u2|2+…+λn|un|2

(25)

由于‖u‖2=‖Uv‖2=‖v‖2=1，故由式(25)可得

λ1(|u1|2+|u2|2+…+|un|2)=λ1

(26)

綜合式(22)和(26)可得，當(dāng)參數(shù)ω,α,β滿足不等式(16)時ρ(G)<1，即MMSOR-like迭代(9)收斂。證畢。

根據(jù)定理1，立即可得如下推論

(27)

3 預(yù)優(yōu)矩陣Q的選取

在矩陣分裂(4)中，引入了待定的對稱正定矩陣Q∈Rn×n，由于Q的不確定，導(dǎo)致應(yīng)用過程難以把握，因此在執(zhí)行迭代(9)之前，很有必要考慮Q的選取問題。根據(jù)定理1可知，參數(shù)α的選取范圍是

表1 預(yù)處理矩陣Q具體形式

4 數(shù)值實驗

考慮如下形式的鞍點問題[16]：

式中：

?表示克羅內(nèi)克積，取h=1/(p+1)為離散網(wǎng)絡(luò)值且m=2p2,n=p2。

分別用MMSOR-like和MSOR-like方法計算case 1和case 2，IT和CPU結(jié)果見表2和表3。

表2 Q=BT[diag(H)]-1B時2種迭代的IT和CPU(case 1)

表3 Q=BT[tridiag(H)]-1B時2種迭代的IT和CPU(case 2)

數(shù)值實驗結(jié)果表明，適當(dāng)選取對稱正定矩陣Q及參數(shù)ω,α,β時，所提的求解鞍點問題(1)的MMSOR-like方法相比文獻[16]所給的MSOR-like方法具有更快的收斂速度。

5 結(jié)論

為更高效求解鞍點問題，在MSOR-like迭代法的基礎(chǔ)上，提出了一種修正的迭代方法，即MMSOR-like迭代方法(9)。該方法在對矩陣A進行H,S分裂后，引入?yún)?shù)建立新的分解矩陣D,L,U，使得迭代格式適用范圍更廣。在定理1用特征值理論證明了迭代的收斂性，并獲得參數(shù)ω,α,β的選取范圍(16)；同時給出了預(yù)優(yōu)矩陣Q的2種選取方法，使得矩陣Q與矩陣A,B的關(guān)聯(lián)性強且易計算。數(shù)值實驗結(jié)果表明，適當(dāng)選取正定矩陣Q及相關(guān)參數(shù)ω,α,β，MMSOR-like方法能顯著提高收斂效率。