矩陣模型修正中一類多約束矩陣逼近問題

張 麗，周學林，李姣芬

(1.桂林電子科技大學 數學與計算科學學院，廣西 桂林 541004；2.桂林電子科技大學 教務處，廣西 桂林 541004)

矩陣模型修正在工程和動力學系統等方面有非常重要的意義。文獻[1-2]利用交替投影算法研究矩陣模型修正中如下結構約束矩陣逼近問題：

(1)

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

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

(2)

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

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

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

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

(3)

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

(4)

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

其中(Xk,Yk,Zk)為給定的迭代步。上述求解方法忽略了目標函數的可分離結構特點，因此考慮充分利用其可分離結構特點的交替方向法。先對X求極小化，再對Y求極小化，其迭代式為：

(5)

2 子問題的求解

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

對于X子問題，參照文獻[4]的方法可得，

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

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

(6)

對于Y子問題，同樣可得

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

(7)

因為假定仿射子空間Ω={Y∈Rn×n|A(Y)+C=0}是非空的，且易知其上的最佳逼近解是唯一的。但由于線性矩陣算子A(Y)的一般性，故Ω上的投影矩陣的具體表達式不易求得，因此迭代式(5)中Y子問題不能求得其解析表達式。為此，從構建內迭代算法的角度求得Y子問題的近似解，即求在非空仿射子空間Ω上最佳逼近問題(7)的近似解。求解思路是將求式(7)的唯一最佳逼近解等價轉化為求一個相容線性矩陣算子方程的唯一最小范數解。首先，將式(7)等價轉換為

(8)

因為

(9)

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

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

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

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

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

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

(10)

算法2取罰參數β>0，給定當前迭代步(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,‖Yk+1-Yk‖F,

‖Zk+1-Zk‖F}≤ε，

其中ε為給定的正常數。

3 收斂性分析

(11)

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

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之間的關系可得

(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)

對于鞍點(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個不等式中令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加速策略

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

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

5 結束語

針對矩陣模型修正中一類多約束矩陣逼近問題，利用交替方向法，通過引入輔助變量將問題等價轉化為可分離變量的矩陣優化問題，并利用投影和構造內迭代算法，求出子問題的解析表達式，應用相關矩陣理論證明了算法的收斂性定理。對于給出的帶“重啟規則”的Nesterov加速策略，今后將通過數值實驗來研究加速策略的加速效果。