列正交约束下广义Sylvester方程极小化问题的有效算法

数学物理学报 ›› 2021, Vol. 41 ›› Issue (2): 479-495.

列正交约束下广义Sylvester方程极小化问题的有效算法

刘月园,王凯,秦树娟,李姣芬*()

^{桂林电子科技大学数学与计算科学学院, 广西高校数据分析与计算重点实验室&广西自动检测技术与仪器重点实验室广西桂林 541004}

收稿日期:2020-03-26 出版日期:2021-04-26 发布日期:2021-04-29
通讯作者: 李姣芬 E-mail:lixiaogui1290@163.com
基金资助:
国家自然科学基金(11761024);国家自然科学基金(11561015);国家自然科学基金(11961012);桂林电子科技大学院级研究生优秀学位论文培育项目(2019YJSPY03);院级研究生创新项目(2020YJSCX02);广西自然科学基金(2017GXNSFBA198082)

An Effective Algorithm for Generalized Sylvester Equation Minimization Problem Under Columnwise Orthogonal Constraints

Yueyuan Liu,Kai Wang,Shujuan Qin,Jiaofen Li*()

^{School of Mathematics and Computational Science, Guilin University of Electronic Technology, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guangxi Guilin 541004}

Received:2020-03-26 Online:2021-04-26 Published:2021-04-29
Contact: Jiaofen Li E-mail:lixiaogui1290@163.com
Supported by:
the NSFC(11761024);the NSFC(11561015);the NSFC(11961012);the GUET Excellent Graduate Thesis Program(2019YJSPY03);the GUET Graduate Innovation Project(2020YJSCX02);the NSF of Guangxi Province(2017GXNSFBA198082)

摘要/Abstract

摘要：

研究列正交约束下广义Sylvester方程极小化问题的有效算法.基于Stiefel流形的几何性质和欧氏空间中的MPRP共轭梯度法，构造一类黎曼MPRP共轭梯度迭代求解算法，给出算法全局收敛性.该迭代格式得到的搜索方向总能保证该目标函数下降.数值实验和数值比较验证所提出算法对于问题模型是高效可行的.

关键词: 广义Sylvester方程, 极小化问题, 列正交约束, 黎曼共轭梯度法

Abstract:

This paper presents an efficient algorithm for solving the generalized Sylvester equation minimization problem under columnwise orthogonal constraints. Based on some geometric properties of the Stiefel manifold and the MPRP conjugate gradient method in Euclidean space, a Riemannian MPRP conjugate gradient algorithm with Armijo-type line search is proposed to solve the presented problem, and its global convergence is also established. An attractive property of the proposed method is that the direction generated by the method is always a descent direction for the objective function. Some numerical tests are given to show the efficiency of the proposed method. Comparisons with some existing methods are also given.

Key words: Generalized Sylvester equation, Minimization problem, Columnwise orthogonal constraint, Riemannian conjugate gradient method

中图分类号:

O151.1

刘月园,王凯,秦树娟,李姣芬. 列正交约束下广义Sylvester方程极小化问题的有效算法[J]. 数学物理学报, 2021, 41(2): 479-495.

Yueyuan Liu,Kai Wang,Shujuan Qin,Jiaofen Li. An Effective Algorithm for Generalized Sylvester Equation Minimization Problem Under Columnwise Orthogonal Constraints[J]. Acta mathematica scientia,Series A, 2021, 41(2): 479-495.

图/表 2

表 1

算法1与其它几类算法的数值比较结果"

	l, n, p, s	CPU(s)	IT	\|\|grad f(X_k)\|\|	f(X_k)	X_feasi
Algo.1		0.134	183	7.202×10^-4	0	9.744×10^-16
OptStiefel		0.282	246	9.431×10^-4	0	4.220×10^-15
Mixed	15, 200, 10, 5	0.532	568	8.770×10^-4	0	2.048×10^-15
SOC		3.775	196	9.278×10^-4	0	3.593×10^-2
ADM		3.485	49	9.823×10^-4	0	5.866×10^-2
Major		11.784	20000	6.235×10^-2	0.0003	5.209×10^-15
Algo.1		0.205	170	7.973×10^-4	0	1.324×10^-15
OptStiefel		0.904	271	5.123×10^-4	0	1.832×10^-14
Mixed	30, 300, 15, 5	1.524	956	9.914×10^-4	0	2.808×10^-15
SOC		15.229	219	9.536×10^-4	0	3.578×10^-2
ADM		14.663	206	9.741×10^-4	0	3.356×10^-2
Major		32.982	20000	3.500×10^-1	0.0018	6.742×10^-15
Algo.1		0.673	486	5.942×10^-4	0	1.595×10^-15
OptStiefel		1.154	356	5.515×10^-4	0	1.449×10^-15
Mixed	45, 400, 20, 5	4.586	1393	8.224×10^-4	0	4.064×10^-15
SOC		54.639	116	9.679×10^-4	0	5.821×10^-2
ADM		31.334	37	9.979×10^-4	0	1.635×10^-1
Major		114.029	20000	4.797	0.2222	8.883×10^-15
Algo.1		0.647	293	4.311×10^-4	0	1.277×10^-15
OptStiefel		1.216	364	9.407×10^-4	0	1.277×10^-15
Mixed	50, 500, 20, 5	5.546	1156	7.179×10^-4	0	3.165×10^-15
SOC		72.800	51	8.914×10^-4	0	1.201×10^-1
ADM		72.570	46	8.835×10^-4	0	1.313×10^-1
Major		185.344	20000	2.804	0.0429	7.434×10^-15
Algo.1		0.609	239	5.557×10^-1	0.0001	2.313×10^-15
OptStiefel		1.125	398	1.635×10^-2	0	1.524×10^-15
Mixed	60, 400, 30, 5	9.036	2072	1.069×10^-3	0	4.994×10^-15
SOC		88.718	56	9.967×10^-4	0	9.761×10^-2
ADM		105.745	99	9.206×10^-4	0	1.023×10^-1
Major		217.668	20000	1.224×10¹	0.7462	9.998×10^-15
Algo.1		1.866	636	7.307×10^-4	0	1.272×10^-15
OptStiefel		1.846	518	9.739×10^-4	0	8.997×10^-16
Mixed	70, 500, 15, 5	8.198	1966	5.506×10^-4	0	2.639×10^-15
SOC		58.076	97	8.202×10^-4	0	1.162×10^-1
ADM		57.401	83	9.283×10^-4	0	1.065×10^-1
Major		130.671	20000	7.300	0.4279	5.167×10^-15
Algo.1		1.289	645	5.152×10^-4	0	1.798×10^-15
OptStiefel		1.985	669	9.542×10^-4	0	1.287×10^-15
Mixed	80, 500, 20, 5	11.044	2311	8.951×10^-4	0	3.750×10^-15
SOC		126.369	92	8.061×10^-4	0	2.926×10^-1
ADM		186.829	198	8.944×10^-4	0	7.416×10^-2
Major		183.599	20000	1.009×10¹	0.5858	7.192×10^-15

表 1

图 1

参考文献 28

1	Dehghan M , Hajarian M . An iterative method for solving the generalized coupled Sylvester matrix equations over generalized bisymmetric matrices. Applied Mathematical Modelling, 2010, 34 (3): 639- 654 doi: 10.1016/j.apm.2009.06.018
2	Hajarian M . Developing BiCOR and CORS methods for coupled Sylvester-transpose and periodic Sylvester matrix equations. Applied Mathematical Modelling, 2015, 39 (19): 6073- 6084 doi: 10.1016/j.apm.2015.01.026
3	Hajarian M . Extending the CGLS algorithm for least squares solutions of the generalized Sylvester-transpose matrix equations. Journal of the Franklin Institute, 2016, 353 (5): 1168- 1185 doi: 10.1016/j.jfranklin.2015.05.024
4	Li S K , Huang T Z . LSQR iterative method for generalized coupled Sylvester matrix equations. Applied Mathematical Modelling, 2012, 36 (8): 3545- 3554 doi: 10.1016/j.apm.2011.10.030
5	Ding F , Chen T . On iterative solutions of general coupled matrix equations. SIAM Journal on Control and Optimization, 2006, 44 (6): 2269- 2284 doi: 10.1137/S0363012904441350
6	Bouhamidi A , Jbilou K , Raydan M . Convex constrained optimization for large-scale generalized Sylvester equations. Computational Optimization and Applications, 2011, 48 (2): 233- 253 doi: 10.1007/s10589-009-9253-6
7	Bouhamidi A , Enkhbat R , Jbilou K . Conditional gradient Tikhonov method for a convex optimization problem in image restoration. Journal of Computational and Applied Mathematics, 2014, 255, 580- 592 doi: 10.1016/j.cam.2013.06.011
8	Li J F , Li W , Huang R . An efficient method for solving a matrix least squares problem over a matrix inequality constraint. Computational Optimization and Applications, 2016, 63 (2): 393- 423 doi: 10.1007/s10589-015-9783-z
9	Escalante R , Raydan M . Dykstra's algorithm for a constrained least-squares matrix problem. Numerical Linear Algebra with Applications, 1996, 3 (6): 459- 471 doi: 10.1002/(SICI)1099-1506(199611/12)3:6<459::AID-NLA82>3.0.CO;2-S
10	Escalante R , Raydan M . Dykstra's algorithm for constrained least-squares rectangular matrix problems. Computers & Mathematics with Applications, 1998, 35 (6): 73- 79
11	Monsalve M , Moreno J , Escalante R , Raydan M . Selective alternating projections to find the nearest SDD+ matrix. Applied Mathematics and Computation, 2003, 145 (2/3): 205- 220
12	Li J F , Hu X Y , Zhang L . Dykstra's algorithm for constrained least-squares doubly symmetric matrix problems. Theoretical Computer Science, 2010, 411 (31-33): 2818- 2826 doi: 10.1016/j.tcs.2010.04.011
13	Li J F , Li W , Vong S W , et al. A Riemannian optimization approach for solving the generalized eigenvalue problem for nonsquare matrix pencils. Journal of Scientific Computing, 2020, 82 (3): 1- 43 doi: 10.1007/s10915-020-01173-5
14	Meng C , Hu X , Zhang L . The skew-symmetric orthogonal solutions of the matrix equation AX=B. Linear Algebra and its Applications, 2005, 402, 303- 318 doi: 10.1016/j.laa.2005.01.022
15	Kiers H A . Setting up alternating least squares and iterative majorization algorithms for solving various matrix optimization problems. Computational statistics & data analysis, 2002, 41 (1): 157- 170
16	Kanamori T , Takeda A . Numerical study of learning algorithms on Stiefel manifold. Computational Management Science, 2014, 11 (4): 319- 340 doi: 10.1007/s10287-013-0181-7
17	Lai R , Osher S . A splitting method for orthogonality constrained problems. Journal of Scientific Computing, 2014, 58 (2): 431- 449 doi: 10.1007/s10915-013-9740-x
18	Chen W , Ji H , You Y . An augmented Lagrangian method for 1-regularized optimization problems with orthogonality constraints. SIAM Journal on Scientific Computing, 2016, 38 (4): B570- B592 doi: 10.1137/140988875
19	Sato H , Iwai T . A Riemannian optimization approach to the matrix singular value decomposition. SIAM Journal on Optimization, 2013, 23 (1): 188- 212 doi: 10.1137/120872887
20	Zhu X . A Riemannian conjugate gradient method for optimization on the Stiefel manifold. Computational Optimization and Applications, 2017, 67 (1): 73- 110 doi: 10.1007/s10589-016-9883-4
21	Vandereycken B . Low-rank matrix completion by Riemannian optimization. SIAM Journal on Optimization, 2013, 23 (2): 1214- 1236 doi: 10.1137/110845768
22	Zhao Z , Jin X Q , Bai Z J . A geometric nonlinear conjugate gradient method for stochastic inverse eigenvalue problems. SIAM Journal on Numerical Analysis, 2016, 54 (4): 2015- 2035 doi: 10.1137/140992576
23	Yao T T , Bai Z J , Zhao Z , Ching W K . A Riemannian Fletcher-Reeves conjugate gradient method for doubly stochastic inverse eigenvalue problems. SIAM Journal on Matrix Analysis and Applications, 2016, 37 (1): 215- 234 doi: 10.1137/15M1023051
24	Yao T T , Bai Z J , Zhao Z . A Riemannian variant of the Fletcher-Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata. Numerical Linear Algebra with Applications, 2019, 26 (2): e2221 doi: 10.1002/nla.2221
25	Zhang L , Zhou W , Li D H . A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence. IMA Journal of Numerical Analysis, 2006, 26 (4): 629- 640 doi: 10.1093/imanum/drl016
26	Absil P A , Mahony R , Sepulchre R . Optimization Aalgorithms on Matrix Manifolds. Princeton: Princeton University Press, 2009
27	Wen Z , Yin W . A feasible method for optimization with orthogonality constraints. Mathematical Programming, 2013, 142 (1/2): 397- 434
28	Oviedo H , Lara H , Dalmau O . A non-monotone linear search algorithm with mixed direction on Stiefel manifold. Optimization Methods and Software, 2019, 34 (2): 437- 457 doi: 10.1080/10556788.2017.1415337

[1]	谷龙江, 孙志禹, 曾小雨. 一类约束变分问题极小元的存在性及其集中行为[J]. 数学物理学报, 2017, 37(3): 510-518.
[2]	朱莉, 夏福全. 广义混合变分不等式的Levitin-Polyak适定性[J]. 数学物理学报, 2012, 32(4): 633-643.
[3]	彭建文;朱道立. 严格 B -预不变凸函数[J]. 数学物理学报, 2006, 26(2): 200-206.