王松華 黎勇 吳加其 陸乃暢
摘 要:為了更有效求解一類大規(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.