一種修正的三項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.