屈紅利,彭振赟

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

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

屈紅利,彭振赟

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

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

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

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

對(duì)于矩陣方程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實(shí)矩陣集合,SRn×n為n×n實(shí)對(duì)稱矩陣的集合。矩陣不等式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)時(shí)將產(chǎn)生迭代序列{}和增量序列{}。對(duì)于初始條件= ξ=0,其遞歸公式為:

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

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

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

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

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

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

定義

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

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

定義

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

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

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

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

因此,關(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)等價(jià)于

其中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,其中

對(duì)于問題

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

對(duì)于問題

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

3 數(shù)值實(shí)驗(yàn)

數(shù)值實(shí)驗(yàn)在Matlab 7.0環(huán)境下實(shí)現(xiàn)。在問題(1)中取ε=0.1。算法(12)～(16)的終止準(zhǔn)則為‖-‖F(xiàn)≤T=10-10。

給定矩陣

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

計(jì)算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] 孫繼廣.實(shí)對(duì)稱矩陣的兩類逆特征值問題[J].計(jì)算數(shù)學(xué),1988,10(3):282-290.

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

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

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

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