多约束条件下矩阵方程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.