多約束條件下矩陣方程AXAT=B的最小二乘解

屈紅利,彭振赟

(桂林電子科技大學數學與計算科學學院,廣西桂林 541004)

多約束條件下矩陣方程AXAT=B的最小二乘解

屈紅利,彭振赟

(桂林電子科技大學數學與計算科學學院,廣西桂林 541004)

為了求解大型矩陣方程的多約束優化問題,基于Dykstra交替投影算法和相關的矩陣分解理論,提出了求解矩陣方程AXAT=B的多約束條件下的最小二乘解的迭代算法,并討論了算法的收斂性。數值實驗驗證了算法的有效性。

矩陣方程;迭代算法;Dykstra交替投影算法;最小二乘解

約束矩陣方程問題是在給定約束矩陣集合中探求某類結構矩陣最優化問題有解的條件下,設計計算可行解的有效算法的問題。在統計學和經濟數學等領域[1],不同的約束矩陣集合類、不同的矩陣方程或相同的矩陣方程滿足不同的約束條件,均會構成不同類型的約束矩陣方程問題。約束矩陣方程問題引起了國內外學者的重視,并取得了一系列的進展。其中,許多研究人員研究了關于矩陣方程X-A=0、AX-B=0等類型的約束矩陣優化問題[1-6]。

對于矩陣方程AXAT=B最優化問題,求X∈Rn×n,使得

X滿足約束條件:

其中:A∈Rm×n,且A為列滿秩矩陣;B∈Rm×m;L∈Rn×n,U∈Rn×n,L、U為邊界矩陣;ε為給定的常數; λmin(X)為矩陣X的最小特征值;Rm×n為m×n實矩陣集合,SRn×n為n×n實對稱矩陣的集合。矩陣不等式A≥B表示矩陣A-B為非負矩陣。矩陣空間Rm×n定義內積為〈A,B〉=tr(ATB),由此導出的矩陣范數為Frobenius范數,記‖·‖F。

1 交替投影算法

Dykstra交替投影算法[7-8]是求解最優化問題(2)的最有效方法,

給定Rn上的非空閉凸集Ω和向量ξ,問題(2)存在唯一解x*,并且稱x*為向量ξ在閉凸集Ω上的投影,記為PΩ(ξ)。投影x*的數學特征滿足Kolmogorov準則:

利用Dykstra交替投影算法求解問題(2)時將產生迭代序列{}和增量序列{}。對于初始條件= ξ=0,其遞歸公式為:

其中:i=1,2,…,m;k=1,2,3,…。

1)在投影之前通常先減去前一步迭代得到的與Ωi相關的增量,對于每個Ωi只需存儲最后一個增量。

2)如果Ωi是一個閉的仿射子空間,那么,PΩi為線性算子。因此,在第k步迭代中,在投影之前減去增量。對于仿射子空間Dykstra交替投影算法,即Von-Neumann迭代投影算法[9]。此時,PΩi() =0。

3)k=1,2,3,…,i=1,2,…,m,式(4)滿足下列關系:

定理1[2,7]若Ω1,Ω2,…,Ωm為Rn上的閉凸集,Ω=Ωi≠?,則對任意i=1,2,…,m及任意ξ∈Rn,由式(4)產生的投影點列{xik}收斂到問題(2)的唯一解。

2 關于矩陣方程AXAT=B最優化問題的迭代解法

定義

那么,問題(1)等價于:

其中Ω為矩陣空間Rn×n的閉子空間。當A為列滿秩矩陣時,問題(10)有唯一解。

定義

那么,求解問題(10)等價于求解矩陣最優化問題:

基于Dykstra交替投影算法,可得求解問題(11)的算法為:

由于M和εpsd為凸集,則M′、ε′psd也為凸集。當A為列滿秩矩陣時,M′和ε′psd為閉集。因此,當A為列滿秩矩陣且式(11)中Ω′非空時,由定理1可知,由式(12)～(16)產生的矩陣序列{}(i=1,2)收斂到問題(11)的唯一解。若求得問題(11)的唯一解Z*,那么,問題(1)的唯一解X*可通過求解相容矩陣方程AXAT=Z*得到。

式(13)、(14)分別等價于:

因此,關鍵問題是求解

使得X滿足X∈M或X∈εpsd。

設列滿秩矩陣A的奇異值分解為

其中:P=(P1,P2)∈Rm×m,P1∈Rm×n;Q∈Rn×n為正交矩陣;Σ=diag(σ1,σ2,…,σn),σ1≥σ2≥…≥σn＞0。則由Frobenius范數的正交不變性有

因此,問題(17)等價于

其中B11=。

為求解問題(19),首先給出如下引理。

引理1[2]給定N∈Rn×n,則N在凸集M上的投影,即問題‖X-N‖F的唯一解PM(N)可以表示為:

引理2[10]給定N∈Rn×n,Σ=diag(σ1,σ2,…, σn),其中σi＞0 i(=1,2,…,n),則問題‖ΣYΣ-N‖F的解唯一,且其解為

其中

引理3[11]給定N∈SRn×n,設N譜分解為N= D diag(λ1,λ2,…,λn)DT,其中D為正交矩陣,則問題‖Y-N‖F的唯一解Y*=D diag(d1,d2,…, dn)DT,其中

對于問題

的解X*的計算方法為:首先,按引理1把矩陣QΣ-1B11Σ-1QT投影到凸集M上,以獲得X*∈[L, U]。然后,Z*=ΣQTX*QΣ。

對于問題

的解X*的計算方法為:按引理2計算問題‖ΣYΣ-B11‖F的解Y*,按引理3計算問題‖W-Y*‖F的解W*,則X*=QW*QT,并令Z*= ΣQTX*QΣ。

3 數值實驗

數值實驗在Matlab 7.0環境下實現。在問題(1)中取ε=0.1。算法(12)～(16)的終止準則為‖-‖F≤T=10-10。

給定矩陣

利用算法(12)～(16)迭代2次得到問題(1)的唯一解為:

計算X*的譜σ(X*)={9.147 3,0.699 3,0.417 6, 0.100 0,0.100 0,0.100 0,0.100 0,0.100 0}。

4 結束語

基于Dykstra交替投影算法,結合相關的矩陣分解理論,求解多約束條件下矩陣方程AXAT=B的最小二乘解的迭代算法是有效的,且定理1確保了算法的收斂性。

[1] Hu H,Olkin I.A numerical procedure for finding the positive definite matrix closest to a patterned matrix [J].Statistics&Probability Letters,1991,12(6):511-515.

[2] Escalante R,Raydan M.Dykstra’s algorithm for a constrained least-squares matrix problem[J].Numerical Linear Algebra with Applications,1996,3(6):459-471.

[3] Higham N J.Computing a nearest symmetric positive semidefinite matrix[J].Linear Algebra and its Applications,1988,103:103-118.

[4] Hayden T L,Wells J.Approximation by matrices positive semidefinite on a subspace[J].Linear Algebra and its Applications,1988,109:115-130.

[5] Allwright J C.Positive semidefinite matrices:characterization via conical hulls and least-squares solution of a matrix equation[J].SIAM Journal on Control and Optimization,1988,26(3):537-556.

[6] Suffridge T J,Hayden T L.Approximation by a Hermitian positive semidefinite Toeplitz matrix[J].SIAM Journal on Matrix Analysis and Applications,1993,14 (3):721-734.

[7] Boyle J P,Dykstra R L.A method for finding projections onto the intersection of convex sets in Hilbert spaces [J].Advances in Order Restricted Statistical Inference Lecture Notes in Statistics,1986,37:28-47.

[8] Dykstra R L.An algorithm for restricted least-squares regression[J].Journal of the American Statistical Association,1983,78(384):837-842.

[9] Von-Neumann J.Functional Operators:Volume II:the Geometry of Orthogonal Spaces[M].Princeton:Princeton University Press,1950.

[10] 孫繼廣.實對稱矩陣的兩類逆特征值問題[J].計算數學,1988,10(3):282-290.

[11] 李姣芬.兩類矩陣逆問題和幾類約束矩陣方程問題的理論和新算法[D].長沙:湖南大學,2010:25-39.

編輯:曹壽平

Multiple constrained least squares solution of the matrix equation AXAT=B

Qu Hongli,Peng Zhenyun
(School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004,China)

In order to solve the multiple constrained optimization problem of the large-scale matrix equation,based on Dykstra’s alternating projection algorithm and the relevant matrix decomposition theory,an iteration algorithm is proposed to solve the multiple constrained matrix equation least squares solution.The convergence properties of the algorithm are discussed,and the numerical experiments show that the algorithm is effective.

matrix equation;iterative method;Dykstra’s algorithm;least squares solution

O241.6

A

1673-808X(2015)02-0166-04

2015-01-20

國家自然科學基金(11261014,11301107);廣西研究生教育創新計劃(YCSZ2014137)

彭振赟(1963-),男,湖南邵東人,教授,博士,研究方向為數值代數。E-mail:yunzhenp@163.com

屈紅利,彭振赟.多約束條件下矩陣方程AXAT=B的最小二乘解[J].桂林電子科技大學學報,2015,35(2):166-169.