一种修正的三项PRP共轭梯度法

王松华 黎勇 吴加其 陆乃畅

摘 要：为了更有效求解一类大规模无约束优化问题，克服其他算法普遍存在的算法较为复杂，存储量大和计算机编程难等不足，在传统三项PRP共轭梯度法的基础上，结合近年来关于三项共轭梯度法和新型线搜索的研究成果，定义了一种新的搜索方向，并采用一种新型的线搜索构建了算法，证明了其具有自动充分下降和信赖域的性质，并在适当的条件下证明了其全局收敛性。数值试验结果表明，在求解一类大规模无约束优化问题上新算法比传统三项PRP共轭梯度法更具有竞争性。具有良好收敛性质的新算法为解决一类求解大规模无约束优化问题提供了更高效的算法依据。

关键词：最優化;无约束优化;共轭梯度法;充分下降性;全局收敛性

中图分类号：O224 MSC（2010）主题分类：49J25 文献标志码：A

文章编号：1008-1542（2018）06-0518-09

为更直观地反映出这2个算法的性能差异，采用文献[23]提出的比较方法，根据表1的数值结果，分别作出算法1和算法2的4类目标性能比较图，详见图1-图4。根据图1-图4性能比较综合分析，对给定的35个测试问题，算法1在迭代次数、目标函数值、迭代时间及函数梯度值的总计算次数等方面，其效率和稳定性都优于算法2。所以，算法1是有效的，是对传统三项PRP共轭梯度的一种改进。

4 结 语

笔者提出了一种改进的PRP三项共轭梯度算法，用于大规模优化问题，新算法具有如下特点：

1）修正的PRP三项共轭梯度具有充分下降性等性质，使得一般函数的全局收敛性变得容易。然而，包括许多其他共轭梯度公式的传统PRP公式没有这个特征，这可能是一般函数全局收敛的关键点。

2）测试问题的最大维数为9 000个变量，数值结果表明，笔者提出的算法比传统方法更具有竞争力。未来将进行更多的试验来证明所提出的算法的性能。

参考文献/References：

[1] FLETCHER R， REEVES C M. Function minimization by conjugate gradients[J]. Compute Journal， 1964， 7（2）： 149-154.

[2] POLAK E， RIBIERE G. Note Sur la convergence de méthodes de directions conjugées[J]. Rev Franaise Informat Recherche Opérationnelle， 2009， 16（16）： 35-43.

[3] HESTENES MR， STIEFEL E. Method of conjugate gradients for solving linear systems[J]. Journal of Research of the National Bureau of Standards， 1952， 49（6）： 409-436.

[4] LIU Y， STOREY C. Efficient generalized conjugate gradient algorithms， part 1： Theory [J].Journal of Optimization  Theory and Applications， 1991， 69（1）： 129-137.

[5] BEALE E M L. A derivative of conjugate gradient[J]. Numerical Methods for Nonlinear Optimization， 1972，12（3）：39-43.

[6] MEGUIRE M F， WOLFE P. Evaluating a restart procedures for conjugate gradients[J].

IBM Research Center Report，1973，14（1）：41-49.

[7] POWELL M J D. Restart procedures for the conjugate gradient method[J]. Mathematical Programming， 1977， 12（1）：241-254.

[8]  DAI Yuhong， YUAN Yaxiang. Convergence properties of Beale-Powell restart algorithm[J]. Science China Mathematics ， 1998， 41（11）：1142-1150.

[9] DAI Yuhong， YUAN Yaxiang. Convergence of three-term conjugate gradient methods[J]. Mathematica Numerica Sinica， 1999（3）：355-362.

[10]ZHANG L， ZHOU W， LI D H. A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence[J]. Ima Journal of Numerical Analysis， 2006， 26（4）： 629-640.

[11]GILBERT J C， NOCEDAL J. Global convergence properties of conjugate gradient methods for optimization[J].SIAM Journal on Optimization， 1990， 2（1）： 21-42.

[12]AHMED-TOUATI D， STOREY C. Efficient hybrid conjugate gradient techniques[J]. Journal of Optimization Theory and Applications， 1990， 64（2）：379-397.

[13]ALBAALI M. Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J].  Ima Journal of Numerical Analysis， 2015， 5（1）： 121-124.

[14]简金宝， 江羡珍， 尹江华. 非线性共轭梯度法研究进展[J]. 玉林师范学院学报（自然科学）， 2016， 37（2）：3-10.

JIAN Jinbao， JIANG Xianzhen， YIN Jianghua. Research progress in nonlinear Gonjugate gradient method[J]. Journal of Yulin Normal University（Natural Science）， 2016， 37（2）：3-10.

[15] 董晓亮， 李卫军. 一类新的WYL型共轭梯度法及其全局收敛性[J]. 河南师范大学学报（自然科学版） ，2018，46（4）：107-112.

DONG Xiaoliang， LI Weijun. Global convergence of a new Wei-Yao-Liu type conjugate gradient method[J]. Journal of Henan Normal University（Natural Science Edition），2018，46（4）：107-112.

[16] 黎勇， 王松华. 求解非光滑优化问题的修正HS三项共轭梯度法[J]. 河北科技大学学报， 2018， 39（2）：     142-148.

LI Yong， WANG Songhua. A modified three-term HS conjugate gradient method for solving nonsmooth minimizations[J]. Journal of Hebei University of Science and Technology， 2018， 39（2）： 142-148.

[17]王博朋， 袁功林， 胡午杰. 求解非線性方程组的一种新共轭梯度法[J]. 井冈山大学学报（自然科学版）， 2017， 38（3）：1-5.

WANG Bopeng， YUAN Gonglin， HU Wujie. A new conjugate gradient method for solving nonlinear equations[J]. Journal of Jinggangshan University（Natural Science）， 2017， 38（3）：1-5.

[18]戴彧虹，袁亚湘.非线性共轭梯度法[M]. 上海： 上海科技出版社， 1999.

[19]YUNA G， WEI Z， LU X. Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search[J]. Applied Mathematical Modeling， 2017， 47： 811-825..

[20]ZHANG Li， ZHOU Weijun， LI Donghui. A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence[J]. Ima Journal of Numerical Analysis， 2006， 26（4）： 629-640.

[21]BONGARTZ I， CONN A R， GOUNLD N， et al. CUTE： Constrained and unconstrained testing environment[J]. Acm Transactions on Mathematical Software， 1993， 50（124）：123-160.

[22]ANDREI N. An unconstrained optimization test functions collection[J]. Environmental Science and Technology， 2008， 10（1）：6552-6558.

[23]DOLAN E D， MOR J J. Benchmarking optimization software with performance profiles[J]. Mathematical Programming， 2001， 91（2）： 201-213.