一種帶強Wolfe線搜索的CD和LS混合共軛梯度算法*

馬 爍

(荊州理工職業(yè)學院， 湖北 荊州 434000)

0 引 言

考慮無約束優(yōu)化問題

(1)

其中f：Rn→R連續(xù)可微.

共軛梯度法是求解無約束優(yōu)化問題(1)的一類有效算法，它的迭代公式形如

xk+1=xk+αkdk

(2)

其中，αk由某種線性搜索決定，dk為第k次搜索方向，由式(3)計算

(3)

共軛梯度法的關鍵是選取αk和βk，不同的αk和βk決定了不同的共軛梯度算法.βk的選取公式常用的有

采用強Wolfe線搜索，受文獻[7-11]的啟發(fā)，步長因子αk同時滿足

(4)

(5)

其中δ和σ是滿足0<δ<σ<1/2的常數(shù).結合CD方法和LS方法提出了一類具有良好收斂性和數(shù)值表現(xiàn)的混合共軛梯度法.在強Wolfe線搜索下，證明了算法具有下降性，并給出了算法具有全局收斂性的證明，數(shù)值結果表明算法的有效性.此處提出一類新的βk公式

(6)

1 新的共軛梯度算法及其下降性

為了后面證明的需要，給出假設H：

(i) 水平集L1={x∈Rn|f(x)≤f(x1)}有界，其中x1為初始點；

(ii) 在水平集L1的一個鄰域U內，f(x)是連續(xù)可微的，其梯度g(x)是lipschitz連續(xù)的，即存在常數(shù)L>0，使

‖g(x)-g(y)‖≤L‖x-y‖，?x，y∈U

(7)

求解無約束問題的新算法NCDLS.

步1 給定初始點x1∈Rn，ε>0，d1=-g1，令k：=1；

步2 若‖gk‖≤ε，則停止迭代；否則，由強Wolfe線搜索式(4)、式(5)計算步長因子αk，計算xk+1=xk+αkdk，k：=k+1；

步3 利用式(6)計算βk+1，計算dk+1=-gk+1+βk+1dk，置k：=k+1，轉步2.

證明用數(shù)學歸納法證明.

由式(5)，有

2 新算法的全局收斂性分析

(8)

對式(8)從k=1，2，…求和并考慮假設條件H，即得引理2.

證明由式(3)得 dk+gk=βkdk-1，兩邊同時取平方得

(9)

3 數(shù)值試驗

用文獻[12]，[13]中的測試函數(shù)檢驗本算法，并將結果與標準CD方法和標準LS方法進行比較.所有實驗均采用強Wolfe線搜索，均不采用重新開始策略.測試環(huán)境為MATLAB7.9.0，運行環(huán)境為內存4.00 GB，CPU為2.60 GHz的個人計算機.參數(shù)設置如下：δ=0.1，σ=0.45，μ=0.9，終止條件為‖gk‖≤10-6或It-limit>9 999，計算得到3種方法的數(shù)值結果如表1所示.

表1中“Prolem”表示測試函數(shù)的名稱，“DIM”表示測試函數(shù)的維數(shù) “NI/NF/NG/T”依次表示迭代的次數(shù)、函數(shù)值計算的次數(shù)、梯度值計算的次數(shù)及CPU計算時間，“F”表示迭代失敗.

表1 數(shù)值測試結果及其比較

通過對7個問題的測試可以看出，此處提出的NCDLS算法的CPU時間要比LS方法少，對于最后一個測試函數(shù)，該算法總體要比LS好很多，而CD方法幾乎都失敗了，這是因為CD方法產生連續(xù)的小步長而無法恢復.所測試的函數(shù)均能說明新方法的可行性.但為了能得到更好的數(shù)值效果，還需要進一步研究方法中參數(shù)的選取和搜索條件的選擇.實驗結果顯示，該算法是有效的.

參考文獻：

[1] FLETCHER R，REEVES C.Function Minimization by Conjugate Gradients[J].Computer Journal，1964(7)：149-154

[2] POLAK E，RIBIERE G.Note Sur La Convergence De Dirctions Conjugees[J].Rev Fran-caise Informat Recherche Opertionelle，3e Annee，1969(16)：35-43

[3] HESTENES M R，SRIEFEL E L.Methods of Conjugate Gradient for Solving Linear Systems[J].Journal of Research of the National Bureau of Standards，1952，6(49)：40-43

[4] FLETCHER R.Practical Methods Optimization[C]∥John Wiley&sons：Unconstrained optimization.New York，1987

[5] LIU Y，STOREY C. Effcient Generalized Conjugate Gradient Algorithms[J].Journal of Optimiztion Theory and Applicatons，1991，69：129-137

[6] DAI Y H，YUAN Y. A nonlinear Conjugate Gradient with A Strong Global Conver-gence Property[J].SIAM Journal on Optimizton，2000(10)：177-182

[7] 王開榮，曹偉，王銀河.Armijo型線搜索下的譜CD共軛梯度法[J].山東大學學報：理學版，2010，45(11)：104-108

[8] 李敏.改進的LS共軛梯度法及其收斂性[J].懷化學院學報，2011，30(8)：1-4

[9] 王董曉亮.Armijo搜索下改進的LS共軛梯度法[J].陜西理工學院學報：自然科學版，2013，29(3)：49-53

[10] 敖衛(wèi)斌.一種修正的DY共軛梯度法的全局收斂性[J].重慶工商大學學報：自然科學版，2013，30(10)：17-20

[11] 張雁，單銳，王換鵬，等.一類混合CD-LS共軛梯度法的全局收斂性[J].遼寧工程技術大學學報：自然科學版，2013，32(3)：409-412

[12] MORE J J，GARBOW B S，HILLSTROME K E.Testing Unconstrained Optimization Software[J].ACM Trans Math Software，1981(7)：17-41

[13] WOLFE M A.Numerical Methods for Unconstrained Optimization[M].An Introduction，Van Nostrand Reinhold，London，1978