基于非单调线搜索的HS-DY形共轭梯度方法及在图像恢复中的应用

Abstract

Abstract:

A modified conjugate gradient algorithm for solving image restoration problems and unconstrained optimization problems is proposed, where the conjugate gradient (CG) parameter is the convex combination of the improved HS and DY methods, and the CG parameter contains function information. In addition, the method does not require any line searches, and it can generate sufficient descent directions. Moreover, under certain conditions, the new method is globally convergent with nonmonotone line search. Finally, experiments on unconstrained optimization and image restoration problems show that the new method has good application prospects and advantages when compared with other conjugate gradient algorithms.

Key words: Conjugate gradient, Global convergence, Unconstrained optimization, Nonmonotone line search, Image restoration

CLC Number:

O221

Gonglin Yuan,Yulun Wu,Hongtruong Pham. A Modified HS-DY-Type Method with Nonmonotone Line Search for Image Restoration and Unconstrained Optimization Problems[J].Acta mathematica scientia,Series A, 2022, 42(2): 605-620.

Trendmd

Figures/Tables 7

References 45

1	Dai Y H . New properties of a nonlinear conjugate gradient method. Numerische Mathematik, 2001, 89 (1): 83- 98 doi: 10.1007/PL00005464
2	Grippo L , Lucidi S . A globally convergent version of the Polak-Ribière conjugate gradient method. Mathematical Programming, 1997, 78 (3): 375- 391 doi: 10.1007/BF02614362
3	Nocedal J , Wright S . Numerical Optimization. Berlin: Springer, 2006
4	Shi Z . Restricted PR conjugate gradient method and its global convergence. Advances in Mathematics, 2002, 31: 47- 55
5	Yuan G L , Wang X B , Sheng Z . Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions. Numerical Algorithms, 2002, 84 (3): 935- 956
6	Wei Z X , Yao S W , Liu L . The convergence properties of some new conjugate gradient methods. Applied Mathematics and Computation, 2006, 183 (2): 1341- 1350 doi: 10.1016/j.amc.2006.05.150
7	Zhou W . A short note on the global convergence of the unmodified PRP method. Optimization Letters, 2013, 7 (6): 1367- 1372 doi: 10.1007/s11590-012-0511-7
8	Yuan G L , Lu J Y , Wang Z . The PRP conjugate gradient algorithm with a modified WWP line search and its application in the image restoration problems. Applied Numerical Mathematics, 2002, 152: 1- 11
9	Zhou W , Wang F . A PRP-based residual method for large-scale monotone nonlinear equations. Applied Mathematics and Computation, 2015, 261: 1- 7 doi: 10.1016/j.amc.2015.03.069
10	Yuan G L , Wei Z X , Yang Y N . The global convergence of the Polak-Ribière-Polyak conjugate gradient algorithm under inexact line search for nonconvex functions. Journal of Computational and Applied Mathematics, 2019, 362: 262- 275 doi: 10.1016/j.cam.2018.10.057
11	Wen F , Yang X . Skewness of return distribution and coefficient of risk premium. Journal of Systems Science and Complexity, 2009, 22 (3): 360- 371 doi: 10.1007/s11424-009-9170-x
12	Andrei N . An unconstrained optimization test functions collection. Advanced Modeling Optimization, 2008, 10 (1): 147- 161
13	Gilbert J , Nocedal J . Global convergence properties of conjugate gradient methods for optimization. SIAM Journal on Optimization, 1992, 2 (1): 21- 42 doi: 10.1137/0802003
14	Wei Z X , Li G Y , Qi L Q . Global convergence of the Polak-Ribiere-Polyak conjugate gradient method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems. Mathematics of Computation, 2008, 77 (264): 2173- 2193 doi: 10.1090/S0025-5718-08-02031-0
15	Yu G , Guan L , Wei Z . Globally convergent Polak-Ribière-Polyak conjugate gradient methods under a modified Wolfe line search. Applied Mathematics and Computation, 2009, 215 (8): 3082- 3090 doi: 10.1016/j.amc.2009.09.063
16	Zhang L , Zhou W , Li D . Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search. Numerische mathematik, 2006, 104 (4): 561- 572 doi: 10.1007/s00211-006-0028-z
17	Li X , Ruan Q . A modified PRP conjugate gradient algorithm with trust region for optimization problems. Numerical Functional Analysis and Optimization, 2011, 32 (5): 496- 506 doi: 10.1080/01630563.2011.554948
18	Awwal A M , Kumam P , Wang L , et al. On the Barzilai-Borwein gradient methods with structured secant equation for nonlinear least squares problems. Optimization Methods and Software, 2020, doi: 10.1080/10556788.2020.1855170
19	Grippo L , Lampariello F , Lucidi S . A nonmonotone line search technique for Newton's method. SIAM Journal on Numerical Analysis, 1986, 23 (4): 707- 716 doi: 10.1137/0723046
20	Grippo L , Lampariello F , Lucidi S . A truncated Newton method with nonmonotone line search for unconstrained optimization. Journal of Optimization Theory and Applications, 1989, 60 (3): 401- 419 doi: 10.1007/BF00940345
21	Toint P L . An assessment of nonmonotone linesearch techniques for unconstrained optimization. SIAM Journal on Scientific Computing, 1996, 17 (3): 725- 739 doi: 10.1137/S106482759427021X
22	Yahaya M M , Kumam P , Awwal A M , et al. A structured quasi-Newton algorithm with nonmonotone search strategy for structured NLS problems and its application in robotic motion control. Journal of Computational and Applied Mathematics, 2021, 395 (5): 113582
23	Zhang H , Hager W W . A nonmonotone line search technique and its application to unconstrained optimization. SIAM Journal on Optimization, 2004, 14 (4): 1043- 1056 doi: 10.1137/S1052623403428208
24	Zhong W , Dong D F . Investigation on a class of nonmonotone cautious BFGS algorithms. Mathematica Numerica Sinica, 2011, 33 (4): 387- 396
25	Dai Y H . On the nonmonotone line search. Journal of Optimization Theory and Applications, 2002, 112 (2): 315- 330 doi: 10.1023/A:1013653923062
26	Amini K , Ahookhosh M , Nosratipour H . An inexact line search approach using modified nonmonotone strategy for unconstrained optimization. Numerical Algorithms, 2014, 66 (1): 49- 78 doi: 10.1007/s11075-013-9723-x
27	Zhang L , Zhou W , Li D . Global convergence of the DY conjugate gradient method with Armijo line search for unconstrained optimization problems. Optimisation Methods and Software, 2007, 22 (3): 511- 517 doi: 10.1080/10556780600795748
28	Huang S , Wan Z , Chen X . A new nonmonotone line search technique for unconstrained optimization. Numerical Algorithms, 2015, 68 (4): 671- 689 doi: 10.1007/s11075-014-9866-4
29	Hestenes M , Stiefel E . Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 1952, 49 (1): 409- 436
30	Fletcher R , Reeves C M . Function minimization by conjugate gradients. The Computer Journal, 1964, 7 (2): 149- 154 doi: 10.1093/comjnl/7.2.149
31	Polak E , Ribiere G . Note sur la convergence de méthodes de directions conjuguées. ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 1969, 3 (R1): 35- 43
32	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
33	Liu Y , Storey C . Efficient generalized conjugate gradient algorithms, part 1: theory. Journal of Optimization Theory and Applications, 1991, 69 (1): 129- 137 doi: 10.1007/BF00940464
34	Fletcher R . Practical Method of Optimization Vol I: Unconstrained Optimization. New York: John Wiley and Sons, 1987
35	Dai Y H , Yuan Y . A nonlinear conjugate gradient method with a strong global convergence property. SIAM Journal on Optimization, 1999, 10 (1): 177- 182 doi: 10.1137/S1052623497318992
36	Zoutendijk G. Nonlinear Programming, Computational Methods//Abadie J. Integer and Nonlinear Programming. Amersterdam: North-Hollend, 1970: 37-86
37	Powell M J D . Convergence properties of algorithms for nonlinear optimization. Siam Review, 1986, 28 (4): 487- 500 doi: 10.1137/1028154
38	Hager W W , Zhang H . A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM Journal on Optimization, 2005, 16 (1): 170- 192 doi: 10.1137/030601880
39	Dai Y , Yuan Y . An efficient hybrid conjugate gradient method for unconstrained optimization. Annals of Operations Research, 2001, 103 (1): 33- 47
40	Liu J , Feng Y . A derivative-free iterative method for nonlinear monotone equations with convex constraints. Numerical Algorithms, 2019, 82 (1): 245- 262 doi: 10.1007/s11075-018-0603-2
41	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
42	Abubakar A B , Kumam P , Ibrahim A H , et al. Derivative-free HS-DY-type method for solving nonlinear equations and image restoration. Heliyon, 2020, 6 (11): e05400 doi: 10.1016/j.heliyon.2020.e05400
43	Yuan G L , Wei Z X . Convergence analysis of a modified BFGS method on convex minimizations. Computational optimization and applications, 2010, 47 (2): 237- 255 doi: 10.1007/s10589-008-9219-0
44	Yuan Y , Sun W . Theory and Methods of Optimization. Beijing: Science Press, 1999
45	Dolan E D , Moré J J . Benchmarking optimization software with performance profiles. Mathematical Programming, 2002, 91 (2): 201- 213 doi: 10.1007/s101070100263

25%噪音浓度	Lena	Barbara	Man	Baboom	合计
方法1	6.016	31.188	7.781	7.281	52.266
方法4	6.563	33.094	8.641	7.75	56.048
方法5	6.359	33.578	8.859	7.515	56.311
50%噪音浓度	Lena	Barbara	Man	Baboom	合计
方法1	15.016	69.453	18.5	16.984	119.953
方法4	15.578	71.39	19.203	18.219	124.39
方法5	16.078	70.234	18.703	17.906	122.921
75% 噪音浓度	Lena	Barbara	Man	Baboom	合计
方法1	25.718	127.641	27.438	26.75	207.547
方法4	26.953	129.938	28.828	27.406	213.125
方法5	27.719	127.609	28.313	27.125	210.766

[1]	Xianzhen Jiang,Wei Liao,Jinbao Jian,Xiaodi Wu. An Improved PRP Type Spectral Conjugate Gradient Method with Restart Steps [J]. Acta mathematica scientia,Series A, 2022, 42(1): 216-227.
[2]	Zhibin Zhu,Yuanhang Geng. A Modified Three-Term WYL Conjugate Gradient Method [J]. Acta mathematica scientia,Series A, 2021, 41(6): 1871-1879.
[3]	Guodong Ma. Improved PRP and HS Conjugate Gradient Methods with the Strong Wolfe Line Search [J]. Acta mathematica scientia,Series A, 2021, 41(3): 837-847.
[4]	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.
[5]	Xiaoni Chi,Rong Zeng,Sanyang Liu,Zhibin Zhu. A Regularized Nonmonotone Inexact Smoothing Newton Algorithm for Weighted Symmetric Cone Complementarity Problems [J]. Acta mathematica scientia,Series A, 2021, 41(2): 507-522.
[6]	Liu Yang,Zuicha Deng. An Inverse Initial Value Problem for Degenerate Parabolic Equations [J]. Acta mathematica scientia,Series A, 2020, 40(4): 891-903.
[7]	Guodong Ma. A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints [J]. Acta mathematica scientia,Series A, 2020, 40(3): 641-649.
[8]	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.
[9]	SONG Wei-Hong, ZHANG Kai-Yuan, NIE Yu-Feng. Double Iterative Algorithm for Different Constrained Solution of Discrete Coupled Algebraic Riccati Equation [J]. Acta mathematica scientia,Series A, 2014, 34(6): 1440-1449.
[10]	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.
[11]	TANG Jing-Yong, HE Guo-Ping. A One-step Smoothing Newton Method for Second-order Cone Programming [J]. Acta mathematica scientia,Series A, 2012, 32(4): 768-778.
[12]	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.
[13]	Xing Li-Li, LI Wei-Guo. A New Model for Staircase Reduction in Image Restoration Problems [J]. Acta mathematica scientia,Series A, 2009, 29(4): 882-890.
[14]	Zhang Li; Zhou Weijun. On the Global Convergence of the Hager-Zhang Conjugate Gradient Method with Armijo Line Search [J]. Acta mathematica scientia,Series A, 2008, 28(5): 840-845.
[15]	Tong Xiaojiao ;He Wei. Lagrangian Globalization Projection Methods for Nonlinear Constrained Equations [J]. Acta mathematica scientia,Series A, 2008, 28(1): 96-108.

A Modified HS-DY-Type Method with Nonmonotone Line Search for Image Restoration and Unconstrained Optimization Problems

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 7

References 45

Related Articles 15

Metrics

Comments

Recommended 0