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

屈紅利,彭振赟

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

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

屈紅利,彭振赟

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

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

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

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

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

X滿足約束條件:

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

1 交替投影算法

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

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

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

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

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

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

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

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

2 關(guān)于矩陣方程AXAT=B最優(yōu)化問題的迭代解法

定義

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

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

定義

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

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

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

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

因此,關(guān)鍵問題是求解

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

設(shè)列滿秩矩陣A的奇異值分解為

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

因此,問題(17)等價于

其中B11=。

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

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

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

其中

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

對于問題

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

對于問題

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

3 數(shù)值實驗

數(shù)值實驗在Matlab 7.0環(huán)境下實現(xiàn)。在問題(1)中取ε=0.1。算法(12)～(16)的終止準(zhǔn)則為‖-‖F(xiàn)≤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 結(jié)束語

基于Dykstra交替投影算法,結(jié)合相關(guān)的矩陣分解理論,求解多約束條件下矩陣方程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].計算數(shù)學(xué),1988,10(3):282-290.

[11] 李姣芬.兩類矩陣逆問題和幾類約束矩陣方程問題的理論和新算法[D].長沙:湖南大學(xué),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

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

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

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