王松華 黎勇 吳加其 陸乃暢

摘 要：為了更有效求解一類大規(guī)模無約束優(yōu)化問題，克服其他算法普遍存在的算法較為復雜，存儲量大和計算機編程難等不足，在傳統(tǒng)三項PRP共軛梯度法的基礎上，結(jié)合近年來關于三項共軛梯度法和新型線搜索的研究成果，定義了一種新的搜索方向，并采用一種新型的線搜索構(gòu)建了算法，證明了其具有自動充分下降和信賴域的性質(zhì)，并在適當?shù)臈l件下證明了其全局收斂性。數(shù)值試驗結(jié)果表明，在求解一類大規(guī)模無約束優(yōu)化問題上新算法比傳統(tǒng)三項PRP共軛梯度法更具有競爭性。具有良好收斂性質(zhì)的新算法為解決一類求解大規(guī)模無約束優(yōu)化問題提供了更高效的算法依據(jù)。

關鍵詞：最優(yōu)化;無約束優(yōu)化;共軛梯度法;充分下降性;全局收斂性

中圖分類號：O224?MSC（2010）主題分類：49J25?文獻標志碼：A

文章編號：1008-1542（2018）06-0518-09

為更直觀地反映出這2個算法的性能差異，采用文獻[23]提出的比較方法，根據(jù)表1的數(shù)值結(jié)果，分別作出算法1和算法2的4類目標性能比較圖，詳見圖1-圖4。根據(jù)圖1-圖4性能比較綜合分析，對給定的35個測試問題，算法1在迭代次數(shù)、目標函數(shù)值、迭代時間及函數(shù)梯度值的總計算次數(shù)等方面，其效率和穩(wěn)定性都優(yōu)于算法2。所以，算法1是有效的，是對傳統(tǒng)三項PRP共軛梯度的一種改進。

4?結(jié)?語

筆者提出了一種改進的PRP三項共軛梯度算法，用于大規(guī)模優(yōu)化問題，新算法具有如下特點：

1）修正的PRP三項共軛梯度具有充分下降性等性質(zhì)，使得一般函數(shù)的全局收斂性變得容易。然而，包括許多其他共軛梯度公式的傳統(tǒng)PRP公式?jīng)]有這個特征，這可能是一般函數(shù)全局收斂的關鍵點。

2）測試問題的最大維數(shù)為9 000個變量，數(shù)值結(jié)果表明，筆者提出的算法比傳統(tǒng)方法更具有競爭力。未來將進行更多的試驗來證明所提出的算法的性能。

參考文獻/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] 董曉亮， 李衛(wèi)軍. 一類新的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] 黎勇， 王松華. 求解非光滑優(yōu)化問題的修正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.