一个带重启步的改进PRP型谱共轭梯度法

数学物理学报 ›› 2022, Vol. 42 ›› Issue (1): 216-227.

一个带重启步的改进PRP型谱共轭梯度法

江羡珍(),廖伟(),简金宝*(),毋晓迪()

广西民族大学数学与物理学院, 应用数学与人工智能研究中心 & 广西混杂计算与集成电路设计分析重点实验室南宁 530006

收稿日期:2021-01-18 出版日期:2022-02-26 发布日期:2022-02-23
通讯作者: 简金宝 E-mail:yl2811280@163.com;1436134351@qq.com;jianjb@gxu.edu.cn;1710703068@qq.com
作者简介:江羡珍, E-mail: yl2811280@163.com|廖伟, E-mail: 1436134351@qq.com|毋晓迪, E-mail: 1710703068@qq.com
基金资助:
广西自然科学基金(2020GXNSFDA238017);广西自然科学基金(2018GXNSFAA281099);广西民族大学科研基金(2018KJQD02);广西民族大学研究生创新项目(gxun-chxp201909)

An Improved PRP Type Spectral Conjugate Gradient Method with Restart Steps

Xianzhen Jiang(),Wei Liao(),Jinbao Jian*(),Xiaodi Wu()

Center for Applied Mathematics and Artificial Intelligence & Guangxi Key Laboratory of Hybrid Compution and IC Design Analysis, College of Mathematics and Physics, Guangxi University for Nationalities, Nanning 530006

Received:2021-01-18 Online:2022-02-26 Published:2022-02-23
Contact: Jinbao Jian E-mail:yl2811280@163.com;1436134351@qq.com;jianjb@gxu.edu.cn;1710703068@qq.com
Supported by:
the NSF of Guangxi Province(2020GXNSFDA238017);the NSF of Guangxi Province(2018GXNSFAA281099);the Research Project of Guangxi University for Nationalities(2018KJQD02);the Innovation Project of Guangxi University for Nationalities Graduate Education(gxun-chxp201909)

摘要/Abstract

摘要：

Polak-Ribière-Polak（PRP）方法是经典共轭梯度法中数值表现较好的方法之一.结合Wolfe非精确线搜索准则对PRP公式进行改进，从而产生新的共轭参数，并基于新共轭参数设计新的谱参数，引入重启条件并构造新的重启方向，进而建立一个带重启步的谱共轭梯度算法.在常规假设及强Wolfe非精确线搜索步长准则下，算法具有充分下降性和全局收敛性.最后，对算法进行中大规模数值实验并与当前公认数值效果较好的同类方法进行比较，结果表明新算法是很有效的.

关键词: 无约束优化, 谱共轭梯度法, 重启方向, 强Wolfe线搜索

Abstract:

The Polak-Ribière-Polak algorithm is considered one of the most efficient methods among classical conjugate gradient methods (CGMs). To generate new conjugate parameter, an improved PRP formula is proposed by combining the strong Wolfe line search condition. Furthermore, a new spectral parameter and a new restart direction are designed, and thus a new spectral conjugate gradient method with restart steps is established. Using the strong Wolfe line search condition to yield the step length, the sufficient descent property and global convergence of the new algorithm are obtained under the general assumptions. Finally, for the proposed algorithm, a medium-large scale numerical experiments is performed, and compared with some existing efficient CGMs, the numerical results show that the proposed algorithm is very promising.

Key words: Unconstrained optimization, Spectral conjugate gradient method, Restart direction, Strong Wolfe line search

中图分类号:

O221

江羡珍,廖伟,简金宝,毋晓迪. 一个带重启步的改进PRP型谱共轭梯度法[J]. 数学物理学报, 2022, 42(1): 216-227.

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.

参考文献

1	Hestenes M R , Stiefel E . Method of conjugate gradient for solving linear equations. Journal of Research of National Bureau of Standards, 1952, 49: 409- 436
2	Fletcher R , Reeves C . Function minimization by conjugate gradients. Computer Journal, 1964, 7 (2): 149- 154
3	Polak E , Ribiére G . Note surla convergence de directions conjugées. Revue Francaise Informat Recherche Operationelle 3e Anneé, 1969, 16 (3): 35- 43
4	Polyak B T . The conjugate gradient method in extreme problems. USSR Computational Mathematics and Mathematical Physics, 1969, 9: 94- 112
5	Dai Y H , Yuan Y X . A nonlinear conjugate gradient method with a strong global convergence property. SIAM Journal on Optimization, 1999, 10 (1): 177- 182
6	Fletcher R. Unconstrained Optimization. Practical Methods of Optimization: Vol 1. New York: Wiley, 1987
7	Liu Y , Storey C . Efficient generalized conjugate gradient algorithms, part 1:theory. Journal of Optimization Theory and Applications, 1991, 69 (1): 129- 137
8	Gilbert J C , Nocedal J . Global convergence properties of conjugate gradient methods for optimization. SIAM Journal on Optimization, 1992, 2 (1): 21- 42
9	Powell M J D. Nonconvex Minimization Calculations and the Conjugate Gradient Method//Griffiths D F, et al. Numerical Analysis. Berlin: Springer, 1984: 122-141
10	Powell M J D . Convergence properties of algorithms for nonlinear optimization. SIAM Review, 1986, 28 (4): 487- 500
11	Jiang X Z , Jian J B , Song D , et al. An improved Polak-Ribiére-Polyak conjugate gradient method with an efficient restart direction. Computational and Applied Mathematics, 2021, 40 (5): 1- 24
12	Mtagulwa P , Kaelo P . An efficient modified PRP-FR hybrid conjugate gradient method for solving unconstrained optimization problems. Applied Numerical Mathematics, 2019, 145: 111- 120
13	Aminifard Z , Babaie-Kafaki S . A modified descent Polak-Ribi?e-Polyak conjugate gradient method with global convergence property for nonconvex functions. Calcolo, 2019, 56 (2): 1- 11
14	Liu J K , Feng Y M , Zou L M . A spectral conjugate gradient method for solving large-scale unconstrained optimization. Computers Mathematics with Applications, 2019, 77 (3): 731- 739
15	Dong X L . A modified nonlinear Polak-Ribiére-Polyak conjugate gradient method with sufficient descent property. Calcolo, 2020, 57 (3): 1- 14
16	Dai Z F , Tian B S . Global convergence of some modified PRP nonlinear conjugate gradient methods. Optimization Letters, 2011, 5 (4): 615- 630
17	Li M . A three term Polak-Ribiére-Polyak conjugate gradient method close to the memoryless bfgs quasi-newton method. Journal of Industrial Management Optimization, 2020, 16 (1): 245- 260
18	Li X L , Shi J J , Dong X L , et al. A new conjugate gradient method based on Quasi-Newton equation for unconstrained optimization. Journal of Computational and Applied Mathematics, 2019, 350: 372- 379
19	Dai Y H , Yuan Y X . A class of globally convergent conjugate gradient methods. Science in China Series A: Mathematics, 2003, 46 (2): 251- 261
20	Barzilai J , Borwein J M . Two-point step size gradient methods. IMA Journal of Numerical Analysis, 1988, 8 (1): 141- 148
21	Luengo F, Raydan M, Glunt W, et al. Preconditioned spectral gradient method for unconstrained optimization problems[R]. Technical Report 96-08, Escuela de Computación, Facultad de Ciencias, Universidad Central de Venezuela, 47002 Caracas 1041-A, Venezuela, 1996
22	Birgin E G , Martínez J M . A spectral conjugate gradient method for unconstrained optimization. Applied Mathematics and Optimization, 2001, 43 (2): 117- 128
23	Kou C X , Dai Y H . A modified self-scaling memoryless Broyden-Fletcher-Goldfard-Shanno method for unconstrained optimization. Journal of Optimization Theory and Applications, 2015, 165 (1): 209- 224
24	Dai Y H , Kou C X . A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search. SIAM Journal on Optimization, 2013, 23 (1): 296- 320
25	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
26	Gould N I M , Orban D , Toint P L . CUTEr and SifDec: A constrained and unconstrained testing environment, revisited. ACM Transactions on Mathematical Software (TOMS), 2003, 29 (4): 373- 394
27	Moré J J , Garbow B S , Hillstrom K E . Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 1981, 7 (1): 17- 41
28	Andrei N . An unconstrained optimization test functions collection. Advanced Modeling and Optimization, 2008, 10 (1): 147- 161
29	Dolan E D , Moré J J . Benchmarking optimization software with performance profiles. Mathematical Programming, 2002, 91 (2): 201- 213

[1]	蔡宇, 周光辉. 一种 WYL 型谱共轭梯度法的全局收敛性[J]. 数学物理学报, 2024, 44(1): 173-184.
[2]	刘鹏杰, 吴彦强, 邵枫, 张艳, 邵虎. 两个带重启方向的改进 HS 型共轭梯度法[J]. 数学物理学报, 2023, 43(2): 570-580.
[3]	袁功林,吴宇伦,PhamHongtruong. 基于非单调线搜索的HS-DY形共轭梯度方法及在图像恢复中的应用[J]. 数学物理学报, 2022, 42(2): 605-620.
[4]	朱志斌,耿远航. 一个改进的WYL型三项共轭梯度法[J]. 数学物理学报, 2021, 41(6): 1871-1879.
[5]	马国栋. 强Wolfe线搜索下的修正PRP和HS共轭梯度法[J]. 数学物理学报, 2021, 41(3): 837-847.
[6]	李向利,师娟娟,董晓亮. 一类修正的非单调谱共轭梯度法及其在非负矩阵分解中的应用[J]. 数学物理学报, 2018, 38(5): 954-962.
[7]	胡朝明, 万中, 王旭. 一种新的非单调谱共轭梯度算法[J]. 数学物理学报, 2013, 33(1): 78-88.
[8]	时贞军. 精确搜索下的非线性共轭梯度法[J]. 数学物理学报, 2004, 4(6): 675-682.