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

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

CLC Number:

O221

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.

Trendmd

Figures/Tables 1

References 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]	HU Chao-Ming, WAN Zhong, WANG Xu. A New Nonmonotone Spectral Conjugate Gradient Algorithm [J]. Acta mathematica scientia,Series A, 2013, 33(1): 78-88.
[2]	SUN Qing-Ying, DONG Jie-Hong, SANG Zhao-Yang. A New Trust Region Algorithm with Simple Quadratic Models and Line Search [J]. Acta mathematica scientia,Series A, 2010, 30(6): 1562-1574.
[3]	SHI Zhen-Jun. A Nonlinear Conjugate Gradient Method under Exact Line Search [J]. Acta mathematica scientia,Series A, 2004, 4(6): 675-682.

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

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 1

References 26

Related Articles 3

Metrics

Comments

Recommended 10