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

数学物理学报 ›› 2022, Vol. 42 ›› Issue (2): 605-620.

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

袁功林¹(),吴宇伦^1,*(),PhamHongtruong²()

¹ 广西大学数学与信息科学学院&广西应用数学中心南宁 530004
² 泰阮大学经济与工商管理学院越南太原

收稿日期:2021-03-03 出版日期:2022-04-26 发布日期:2022-04-18
通讯作者: 吴宇伦 E-mail:glyuan@gxu.edu.cn;wuyulun@st.gxu.edu.cn;shanghaichina888@yahoo.com
作者简介:袁功林, E-mail: glyuan@gxu.edu.cn|Pham Hongtruong, E-mail: shanghaichina888@yahoo.com
基金资助:
国家自然科学基金(11661009);广西高校高水平创新团队和优秀学者计划([2019]52);广西自然科学重点基金(2017GXNSFDA198046);中央引导地方科技发展专项基金(ZY20198003);广西"八桂学者"专项

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

Gonglin Yuan¹(),Yulun Wu^1,*(),Hongtruong Pham²()

¹ Center for Applied Mathematics of Guangxi & College of Mathematics and Information Science, Guangxi University, Nanning 530004
² Thai Nguyen University of Economics and Business Administration, Thai Nguyen, Vietnam

Received:2021-03-03 Online:2022-04-26 Published:2022-04-18
Contact: Yulun Wu E-mail:glyuan@gxu.edu.cn;wuyulun@st.gxu.edu.cn;shanghaichina888@yahoo.com
Supported by:
the NSFC(11661009);the High Level Innovation Teams and Excellent Scholars Program in Guangxi Institutions of Higher Education([2019]52);the Guangxi Natural Science Key Fund(2017GXNSFDA198046);the Special Funds for Local Science and Technology Development Guided by the Central Government(ZY20198003);the Special Foundation for Guangxi Ba Gui Scholars

摘要/Abstract

摘要：

该文提出了一种求解图像恢复问题和无约束优化问题的改进的共轭梯度算法, 其中共轭梯度参数是修改过的HS和DY方法的共轭参数的凸组合形式, 新提出的共轭梯度参数比起经典的参数还包含了函数的信息. 该方法在不使用任何线性搜索技术的情况下, 就可以满足充分下降的性质. 此外, 在一定合理条件下, 该文证明了在非单调线性搜索下新方法的全局收敛性. 最后, 在无约束优化和图像恢复问题上的实验表明, 新方法与其他共轭梯度算法相比, 具有良好的竞争力和应用前景.

关键词: 共轭梯度法, 全局收敛性, 无约束优化, 非单调线性搜索, 图像恢复

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

中图分类号:

O221

袁功林,吴宇伦,PhamHongtruong. 基于非单调线搜索的HS-DY形共轭梯度方法及在图像恢复中的应用[J]. 数学物理学报, 2022, 42(2): 605-620.

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.

图/表 7

图 1

图 2

图 3

图 4

图 5

图 6

表 1

参考文献 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]	江羡珍,廖伟,简金宝,毋晓迪. 一个带重启步的改进PRP型谱共轭梯度法[J]. 数学物理学报, 2022, 42(1): 216-227.
[2]	朱志斌,耿远航. 一个改进的WYL型三项共轭梯度法[J]. 数学物理学报, 2021, 41(6): 1871-1879.
[3]	马国栋. 强Wolfe线搜索下的修正PRP和HS共轭梯度法[J]. 数学物理学报, 2021, 41(3): 837-847.
[4]	刘月园,王凯,秦树娟,李姣芬. 列正交约束下广义Sylvester方程极小化问题的有效算法[J]. 数学物理学报, 2021, 41(2): 479-495.
[5]	杨柳,邓醉茶. 退化抛物型方程的一个初值反演问题[J]. 数学物理学报, 2020, 40(4): 891-903.
[6]	马国栋. 一般约束极大极小优化问题一个强收敛的广义梯度投影算法[J]. 数学物理学报, 2020, 40(3): 641-649.
[7]	李向利,师娟娟,董晓亮. 一类修正的非单调谱共轭梯度法及其在非负矩阵分解中的应用[J]. 数学物理学报, 2018, 38(5): 954-962.
[8]	宋卫红, 张凯院, 聂玉峰. 离散对偶代数Riccati方程异类约束解的双迭代算法[J]. 数学物理学报, 2014, 34(6): 1440-1449.
[9]	胡朝明, 万中, 王旭. 一种新的非单调谱共轭梯度算法[J]. 数学物理学报, 2013, 33(1): 78-88.
[10]	邢丽丽, 李维国. 图像恢复问题中减少梯子现象的一种新模型[J]. 数学物理学报, 2009, 29(4): 882-890.
[11]	周长银; 贺国平; 王永丽. 基于有效约束识别技术的一个SSLE算法及其收敛性分析[J]. 数学物理学报, 2007, 27(3): 535-540.
[12]	王长钰;宇振盛. 求解非线性系统的有效集信赖域方法[J]. 数学物理学报, 2006, 26(2): 223-232.
[13]	时贞军. 精确搜索下的非线性共轭梯度法[J]. 数学物理学报, 2004, 4(6): 675-682.
[14]	高自友, 任华玲, 贺国平. 无严格互补松驰条件的序列线性方程组新算法[J]. 数学物理学报, 2004, 24(3): 275-284.
[15]	施保昌, 陈珽, 祝世京. 多目标决策的中心方法之统一探讨[J]. 数学物理学报, 1997, 17(S1): 15-22.