一类修正的非单调谱共轭梯度法及其在非负矩阵分解中的应用

数学物理学报 ›› 2018, Vol. 38 ›› Issue (5): 954-962.

一类修正的非单调谱共轭梯度法及其在非负矩阵分解中的应用

李向利^1,*(),师娟娟²,董晓亮³

¹ 桂林电子科技大学, 数学与计算科学学院, 广西密码学与信息安全重点实验室广西桂林 541004
² 桂林电子科技大学, 数学与计算科学学院, 广西自动检测技术与仪器重点实验室广西桂林 541004
³ 北方民族大学数学与信息科学学院银川 750021

收稿日期:2016-10-24 出版日期:2018-11-09 发布日期:2018-11-09
通讯作者: 李向利 E-mail:lixiangli@guet.edu.cn
基金资助:
国家自然科学基金(71561008);国家自然科学基金(11601012);广西自然科学基金(2018GXNSFAA138169);广西自动检测技术与仪器重点实验室基金(YQ16112);广西密码学与信息安全重点实验室研究课题(GCIS201708);宁夏自然科学基金(NZ17103)

A Class of Modified Non-Monotonic Spectral Conjugate Gradient Method and Applications to Non-Negative Matrix Factorization

Xiangli Li^1,*(),Juanjuan Shi²,Xiaoliang Dong³

¹ School of Mathematics and Computing Science, Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guangxi Guilin 541004
² Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guilin University of Electronic Technology, Guangxi Guilin 541004
³ School of Mathematics and Information Science, North Minzu University, Yinchuan 750021

Received:2016-10-24 Online:2018-11-09 Published:2018-11-09
Contact: Xiangli Li E-mail:lixiangli@guet.edu.cn
Supported by:
the NSFC(71561008);the NSFC(11601012);the Guangxi Natural Science Foundation(2018GXNSFAA138169);the Guangxi Key Laboratory of Automatic Detection Technology and Instruments(YQ16112);the Guangxi Key Laboratory of Cryptography Security(GCIS201708);the Natural Science Foundation of Ningxia(NZ17103)

摘要/Abstract

摘要：

谱共轭梯度算法是一类解决无约束优化问题的有效方法，它以共轭梯度法为基础，结合谱方法，保持了两种方法的计算优点.该文提出了一类修正的非单调谱共轭梯度算法，在满足一定的假设下，证明了算法的收敛性.此外，该文将所提出的算法应用于非负矩阵分解中，数值实验表明算法的效果是值得肯定的.

关键词: 无约束优化, 谱共轭梯度法, 非单调线搜索, 非负矩阵分解

Abstract:

Spectral conjugate gradient algorithm is an effective method to solve unconstrained optimization problems. It is based on the conjugate gradient method and combines the spectral method to maintain the advantages of the two methods. In this paper, we propose a class of modified non-monotonic spectral conjugate gradient algorithm, under certain assumptions, the convergence of the algorithm is proved. In addition, we applied the algorithm to the nonnegative matrix factorization, and the numerical results show that the algorithm is effective.

Key words: Unconstrained optimization, Spectral conjugate gradient method, Non monotone line search, Non negative matrix factorization

中图分类号:

O221

李向利,师娟娟,董晓亮. 一类修正的非单调谱共轭梯度法及其在非负矩阵分解中的应用[J]. 数学物理学报, 2018, 38(5): 954-962.

Xiangli Li,Juanjuan Shi,Xiaoliang Dong. A Class of Modified Non-Monotonic Spectral Conjugate Gradient Method and Applications to Non-Negative Matrix Factorization[J]. Acta mathematica scientia,Series A, 2018, 38(5): 954-962.

图/表 1

参考文献 26

1	Sun W , Yuan Y X . Optimization Theory and Methods. New York: Springer, 2006: 175- 200
2	Vrahatis M N , Androulakis G S , Lambrinos J N , et al. A class of gradient unconstrained minimization algorithms with adaptive stepsize. Journal of Computational and Applied Mathematics, 2000, 114 (2): 367- 386
3	Shi Z J , Guo J . A new family of conjugate gradient methods. Journal of Computational & Applied Mathematics, 2009, 224 (1): 444- 457
4	Yuan G , Wei Z , Li G . A modified Polak-Ribière-Polyak conjugate gradient algorithm for nonsmooth convex programs. Journal of Computational and Applied Mathematics, 2014, 255: 86- 96 doi: 10.1016/j.cam.2013.04.032
5	Jiang X Z , Jian J B . Two modified nonlinear conjugate gradient methods with disturbance factors for unconstrained optimization. Nonlinear Dynamics, 2014, 77 (1/2): 387- 397
6	Yuan G , Wei Z , Zhao Q . A modified Polak-Ribière-Polyak conjugate gradient algorithm for large-scale optimization problems. ⅡE Transactions, 2014, 46 (4): 397- 413
7	Itoh S , Sugihara M . Formulation of a preconditioned algorithm for the conjugate gradient squared method in accordance with its logical structure. Applied Mathematics, 2015, 06 (8): 1389- 1406 doi: 10.4236/am.2015.68131
8	Yuan G , Zhang M . A three-terms Polak-Ribière-Polyak conjugate gradient algorithm for large-scale nonlinear equations. Journal of Computational and Applied Mathematics, 2015, 286 (3): 186- 195
9	Yuan G , Meng Z , Li Y . A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations. Journal of Optimization Theory and Applications, 2016, 168 (1): 129- 152 doi: 10.1007/s10957-015-0781-1
10	胡朝明, 万中, 王旭. 一种新的非单调谱共轭梯度算法. 数学物理学报, 2013, 33A (1): 78- 88 doi: 10.3969/j.issn.1003-3998.2013.01.010
	Hu C M , Wan Z , Wang X . A new nonmonotone spectral conjugate gradient algorithm. Acta Math Sci, 2013, 33A (1): 78- 88 doi: 10.3969/j.issn.1003-3998.2013.01.010
11	Chen Q , Jiang X Z . A spectral conjugate gradient method for unconstrained optimization. Applied Mathematics and Optimization, 2001, 43 (2): 117- 128 doi: 10.1007/s00245-001-0003-0
12	Zhang B , Zhu Z , Li S . A modified spectral conjugate gradient projection algorithm for total variation image restoration. Applied Mathematics Letters, 2014, 27 (1): 26- 35
13	李董辉, 童小娇, 万中. 数值最优化算法与理论. 北京: 科学出版社, 2011: 71- 87
	Li D H , Tong X J , Wan Z . Numerical Optimization Algorithms and Theory. Beijing: Science Press, 2011: 71- 87
14	Gao H , Zhang H B , Li Z B , et al. A nonmonotone inexact Newton method for unconstrained optimization. Optimization Letters, 2017, 11 (5): 947- 965 doi: 10.1007/s11590-015-0976-2
15	Dai Y H . Convergence properties of the BFGS algoritm. Siam Journal on Optimization, 2002, 13 (3): 693- 701 doi: 10.1137/S1052623401383455
16	Zhang H , Ni Q . A new regularized quasi-Newton algorithm for unconstrained optimization. Applied Mathematics and Computation, 2015, 259: 460- 469 doi: 10.1016/j.amc.2015.02.032
17	沈洁, 郭方芳, 庞丽萍. 非光滑凸规划不可行拟牛顿束方法的收敛性分析. 数学进展, 2016, 46 (2): 299- 308
	Shen J , Guo F F , Pang L P . Convergence analysis of an infeasible quasi-Newton bundle method for nonsmooth convex programming. Advances in Mathematics, 2016, 46 (2): 299- 308
18	Polyak B T . The conjugate gradient method in extremal problems. Ussr Computational Mathematics and Mathematical Physics, 1969, 9 (4): 94- 112 doi: 10.1016/0041-5553(69)90035-4
19	Cardenas S . Efficient generalized conjugate gradient algorithms. Ⅰ. Theory Journal of Optimization Theory and Applications, 1991, 69 (1): 129- 137 doi: 10.1007/BF00940464
20	Hestenes M R , Stiefel E . Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 1952, 49 (6): 409- 436 doi: 10.6028/jres.049.044
21	万中, 冯冬冬. 一类非单调保守BFGS算法研究. 计算数学, 2011, 33 (4): 387- 396
	Wan Z , Fen D D . Investigation on a class of nonmonotone cautious BFGS algorithms. Mathematica Numerica Sinica, 2011, 33 (4): 387- 396
22	Ahookhosh M , Amini K , Bahrami S . A class of nonmonotone Armijo-type line search method for unconstrained optimization. Optimization, 2012, 61 (4): 387- 404
23	Lee D D , Seung H S . Learning the parts of objects by non-negative matrix factorization. Nature, 1999, 401: 788- 791 doi: 10.1038/44565
24	Liu H , Li X . Modified subspace Barzilai-Borwein gradient method for non-negative matrix factorization. Computational Optimization and Applications, 2013, 55 (1): 173- 196 doi: 10.1007/s10589-012-9507-6
25	Paatero P , Tapper U . Positive matrix factorization:A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 1994, 5 (5): 111- 126
26	Cichocki A , Zdunek R , Phan A H , et al. Nonnegative matrix and tensor factorizations:applications to exploratory multi-way data analysis and Blind Source separation. Wiley Publishing, 2009, 25 (2): 1- 3

$(m, n, r)$	算法	fun	opt	time
(50, 50, 2)	ncg	6.660e-003	6.756e-001	6.578
	算法1	8.426e-001	8.636e-001	1.594
	算法2	3.741e+000	6.857e-001	1.297
(50, 50, 4)	ncg	6.883e-002	2.564e+000	108.016
	算法1	1.954e+000	1.015e+001	37.969
	算法2	5.520e-002	2.840e+000	38.969
(100, 50, 4)	ncg	5.817e-002	2.260e+000	57.031
	算法1	1.708e+000	1.587e+001	48.141
	算法2	9.582e-006	2.010e-002	20.609
(100, 50, 5)	ncg	8.217e-004	3.638e-001	190.438
	算法1	7.022e-001	7.183e+000	30.547
	算法2	3.400e-002	3.823e+000	31.906
(100, 100, 4)	ncg	1.463e-003	6.988e-001	35.922
	算法1	2.605e+000	2.415e+001	32.750
	算法2	2.297e-007	8.993e-003	3.781
(100, 100, 5)	ncg	2.323e-002	1.247e+001	300.094
	算法1	2.484e+000	2.508e+001	54.281
	算法2	3.359e-002	5.040e+000	76.109

[1]	倪铁, 刘晓红. 基于尺度中心路径的求解SCLP的非单调光滑牛顿算法[J]. 数学物理学报, 2014, 34(2): 378-392.
[2]	胡朝明, 万中, 王旭. 一种新的非单调谱共轭梯度算法[J]. 数学物理学报, 2013, 33(1): 78-88.
[3]	时贞军. 精确搜索下的非线性共轭梯度法[J]. 数学物理学报, 2004, 4(6): 675-682.