矩陣模型修正中一類多約束矩陣逼近問(wèn)題

張 麗，周學(xué)林，李姣芬

(1.桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué) 教務(wù)處，廣西 桂林 541004)

矩陣模型修正在工程和動(dòng)力學(xué)系統(tǒng)等方面有非常重要的意義。文獻(xiàn)[1-2]利用交替投影算法研究矩陣模型修正中如下結(jié)構(gòu)約束矩陣逼近問(wèn)題：

(1)

其中‖·‖F(xiàn)為常用的矩陣Frobenius范數(shù)，y?Rn×n為閉凸集合，問(wèn)題(1)假定線性矩陣方程AXB+C=0是相容的。文獻(xiàn)[1-2]只討論了較簡(jiǎn)單的相容矩陣方程約束條件AXB+C=0，因交替投影算法需要給出在相容矩陣方程解集合中投影矩陣的具體解析表達(dá)式，故該算法并不能把問(wèn)題模型(1)推廣至更一般情形的相容矩陣方程約束條件。為此，利用目前較成熟的交替方向法[3-4]，討論如下具有更一般形式的多約束矩陣逼近問(wèn)題。

問(wèn)題1給定矩陣C∈Rm×s,G∈Rn×n和閉凸集合y?Rn×n，求X∈Rn×n，使得

(2)

其中A(X)：Rn×n→Rm×s表示具有一般形式的線性矩陣方程算子，其轉(zhuǎn)置(伴隨)算子記為AT(·)：Rm×s→Rn×n。同樣假定線性矩陣算子方程A(X)+C=0是相容的。對(duì)于閉凸集合y?Rn×n的選取，假定y上的投影矩陣Py(·)易求得。較常用的約束集合為對(duì)稱矩陣集合、Hankle型矩陣集合、非負(fù)矩陣集合、對(duì)稱半正定矩陣集合等。

1交替方向法求解問(wèn)題(2)

為方便求解，引入輔助變量Y∈Rn×n，將問(wèn)題(2)轉(zhuǎn)換成如下等價(jià)形式：

s.t.X-Y=0，X∈y,Y∈Ω。

(3)

其中Ω={Y∈Rn×n|A(Y)+C=0}為非空的仿射子空間。問(wèn)題(3)對(duì)應(yīng)的增廣拉格朗日函數(shù)為

(4)

其中β>0為罰參數(shù)，Z∈Rn×n為拉格朗日乘子矩陣。傳統(tǒng)的交替最小二乘法用以下迭代格式對(duì)式(4)進(jìn)行極小化求解，

其中(Xk,Yk,Zk)為給定的迭代步。上述求解方法忽略了目標(biāo)函數(shù)的可分離結(jié)構(gòu)特點(diǎn)，因此考慮充分利用其可分離結(jié)構(gòu)特點(diǎn)的交替方向法。先對(duì)X求極小化，再對(duì)Y求極小化，其迭代式為：

(5)

2 子問(wèn)題的求解

由式(5)可知，X和Y的子問(wèn)題可表示為：

對(duì)于X子問(wèn)題，參照文獻(xiàn)[4]的方法可得，

2tr(XT(G+βYk+Zk))+c}?

因假定y是具有特殊結(jié)構(gòu)的閉凸集，且易求得任意n×n矩陣在集合y內(nèi)的投影矩陣，故可得式(5)中X子問(wèn)題的具體解析表達(dá)式，

(6)

對(duì)于Y子問(wèn)題，同樣可得

2tr(YT(G-βXk+1+Zk))+c}?

(7)

因?yàn)榧俣ǚ律渥涌臻gΩ={Y∈Rn×n|A(Y)+C=0}是非空的，且易知其上的最佳逼近解是唯一的。但由于線性矩陣算子A(Y)的一般性，故Ω上的投影矩陣的具體表達(dá)式不易求得，因此迭代式(5)中Y子問(wèn)題不能求得其解析表達(dá)式。為此，從構(gòu)建內(nèi)迭代算法的角度求得Y子問(wèn)題的近似解，即求在非空仿射子空間Ω上最佳逼近問(wèn)題(7)的近似解。求解思路是將求式(7)的唯一最佳逼近解等價(jià)轉(zhuǎn)化為求一個(gè)相容線性矩陣算子方程的唯一最小范數(shù)解。首先，將式(7)等價(jià)轉(zhuǎn)換為

(8)

因?yàn)?/p>

(9)

的唯一的最小范數(shù)解。記方程(9)的唯一最小范數(shù)解為Z*，最佳逼近問(wèn)題(8)的唯一解可表示為

對(duì)于相容線性矩陣方程的求解或其最小范數(shù)解，近年來(lái)已有非常豐富的研究成果[5-6]。參照文獻(xiàn)[5]的矩陣形式的共軛梯度算法求解相容線性矩陣方程(9)，并通過(guò)選取特定的初始矩陣得到方程(9)的唯一最小范數(shù)解。

對(duì)于算法1，可以證明該算法具有有限步終止特性[5]。

引理1[5]對(duì)于相容線性矩陣方程(9)，任意給定初始矩陣Z1∈Rn×n，迭代算法1經(jīng)過(guò)有限步迭代可得到方程(9)的一個(gè)解。

若取特定的初始矩陣，則由算法1可得到方程(9)的唯一的最小范數(shù)解[4]。

由引理2可知，問(wèn)題(8)的唯一最佳逼近解

(10)

算法2取罰參數(shù)β>0，給定當(dāng)前迭代步(Xk,Yk,Zk)∈(y,Ω,Rn×n)，則生成新的更新迭代步(Xk+1,Yk+1,Zk+1)∈(y,Ω,Rn×n)：

1)按式(6)生成Xk+1，即

3)更新乘子矩陣Zk+1=Zk-β(Xk+1-Yk+1)。

算法2的終止條件為：

max{‖Xk+1-Xk‖F(xiàn),‖Yk+1-Yk‖F(xiàn),

‖Zk+1-Zk‖F(xiàn)}≤ε，

其中ε為給定的正常數(shù)。

3 收斂性分析

(11)

將式(11)變分不等式寫(xiě)成一種緊湊形式

V(f,F,M):f(U)-f(U*)+

〈W-W*,F(W*)〉≥0,?W∈M，

其中

(12)

得到緊形式

f(U)-f(Uk+1)+〈W-Wk+1,F(Wk+1)+

η(Yk,Yk+1)+H0(Vk+1-Vk)〉≥0，

(13)

其中

(14)

引理3在式(12)中定義的映射F(W)滿足

定理1由式(2)生成的序列{Xk+1}滿足

(15)

證明從H與H0之間的關(guān)系可得

(Wk+1-W*)TH0(Xk-Xk+1)=

〈Xk+1-X*,H(Xk-Xk+1)〉，

在式(13)中令W=W*，可得

〈Xk+1-X*,H(Xk-Xk+1)〉≥

〈Wk+1-W*,η(Yk,Yk+1)〉+f(Uk+1)-

f(U*)+〈Wk+1-W*,F(Wk+1)〉≥

〈Wk+1-W*,η(Yk,Yk+1)〉。

(16)

對(duì)于鞍點(diǎn)(X*,Y*)有X*-Y*=0，由Zk+1的迭代，得

〈Wk+1-W*,η(Yk,Yk+1)〉=

〈Yk-Yk+1,β{(-Xk+1+Yk+1)+

(X*-Y*)}〉=

〈Yk-Yk+1,-η(Xk+1-Yk+1)〉=

〈Yk-Yk+1,Zk+1-Zk〉，

在式(11)的第2個(gè)不等式中令Y=Yk，得到

f2(Yk)-f2(Yk+1)+〈Yk-Yk+1,Zk+1〉≥0，

(17)

即

f2(Y)-f2(Yk)+〈Y-Yk,Zk〉≥0。

令Y=Yk+1，可得

f2(Yk+1)-f2(Yk)+〈Yk+1-Yk,Zk〉≥0，

(18)

式(17)、(18)相加可得，

〈Yk-Yk+1,Zk+1-Zk〉≥0?

〈Xk+1-X*,H(Xk-Xk+1)〉≥0。

因此以下不等式成立，

2〈Xk+1-X*,H(Xk-Xk+1)〉≥

4 Nesterov加速策略

文獻(xiàn)[7-8]將梯度下降法的Nesterov加速策略應(yīng)用于交替投影方向法，其核心是引入預(yù)估校正型的加速步。文獻(xiàn)[6]將Nesterov加速策略應(yīng)用于求解核范數(shù)和譜范數(shù)的廣義Sylvester方程最小二乘問(wèn)題，其數(shù)值實(shí)驗(yàn)部分驗(yàn)證了該加速方案是切實(shí)可行的。因此，將帶“重啟規(guī)則”Nesterov加速策略應(yīng)用于算法2的交替方向法。

4)若ck<ηck-1，則令

5 結(jié)束語(yǔ)

針對(duì)矩陣模型修正中一類多約束矩陣逼近問(wèn)題，利用交替方向法，通過(guò)引入輔助變量將問(wèn)題等價(jià)轉(zhuǎn)化為可分離變量的矩陣優(yōu)化問(wèn)題，并利用投影和構(gòu)造內(nèi)迭代算法，求出子問(wèn)題的解析表達(dá)式，應(yīng)用相關(guān)矩陣?yán)碚撟C明了算法的收斂性定理。對(duì)于給出的帶“重啟規(guī)則”的Nesterov加速策略，今后將通過(guò)數(shù)值實(shí)驗(yàn)來(lái)研究加速策略的加速效果。