王安平，陳 忠

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

其中：f：Rn→R為連續(xù)可微函數(shù).因為共軛梯度法具有算法簡單，易于編程及存儲空間小等優(yōu)點，所以共軛梯度法是求解無約束優(yōu)化問題（1）的一類重要方法，一般共軛梯度法的迭代公式為

其中：x1為初始點，dk為搜索方向，αk由某種線性搜索或由特定公式計算出的步長因子，βk為參數(shù)，gk＝▽f（xk）.

關(guān)于βk的著名公式有

其中：‖·‖為歐式范數(shù)，它們對應(yīng)的共軛梯度法依次稱為 FR［1］方法、PRP［2－3］方法、HS［4］方法、CD［5］和DY［6］方法.對于目標(biāo)函數(shù)非凸的情況下，這些共軛梯度方法的收斂性分析和數(shù)值表現(xiàn)差別較大，一般情況下，F(xiàn)R、CD和DY方法有較強的收斂性，HS和PRP方法卻有很好的數(shù)值實驗效果.作者繼續(xù)關(guān)注HS方法.許多學(xué)者從不同角度研究了HS共軛梯度法.文［7］提出了一種改進(jìn)的HS算法，并在Wolf e線搜索下證明該算法的全局收斂性，其中

文［8］提出了一種充分下降HS算法，并在強Wolfe線搜索下證明該算法的全局收斂性，其中

文［9］提出了一種充分下降的3項HS方法，并在Wolfe線搜索下證明該算法的全局收斂性，其中

文［10］提出了一種充分下降的PRP方法

其中

受上述文獻(xiàn)的啟發(fā)，作者嘗試對HS方法進(jìn)行改進(jìn)，希望獲得其更多優(yōu)點，在每一步迭代的搜索方向均為充分下降的.搜索方向dk利用式（7），其中

1 新算法及其全局收斂性分析

論文的步長策略為Wolfe 線搜索，即選取αk＞0，滿足

其中：δ和σ是滿足0＜δ＜σ＜1的常數(shù).

作者提出了一種修正的HS共軛梯度算法，記為WHS方法：

步驟1 給定初始點x1∈Rn及收斂精度ε＞0，d1＝－g1，令k：＝1；

步驟2 若‖gk‖≤ε，則停止迭代；否則由式（7）和（9）求得dk；

步驟3 按照 Wolfe線搜索式（10）、（11）來計算步長αk；

步驟4 計算xx＋1＝xk＋αkdk，置k：＝k＋1，轉(zhuǎn)步驟2.

為了證明論文算法的全局收斂性，作如下必要的假設(shè)：

（1）f（x）在水平集L1＝｛x∈Rn｜f（x）≤f（x1）｝有界，其中x1為初始點；

（2）f（x）在水平集L1的某個鄰域U 內(nèi)連續(xù)可微，其梯度g（x）是Lipschitz連續(xù)的，即存在常數(shù)L＞0，使得

引理1 設(shè)目標(biāo)函數(shù)f（x）滿足假設(shè)，αk滿足式（10）、（11），有

此關(guān)系式稱為Zoutendijk條件.

證明 由式（11）、（12），則有

再聯(lián)合式（10）可以得到

對式（15）兩端進(jìn)行累加，并注意到假設(shè)中（1），所以，有

定理1 設(shè)目標(biāo)函數(shù)f（x）滿足假設(shè)條件，迭代點列xk由式（2）確定，αk滿足式（10）和式（11），dk由式（7）和式（9）產(chǎn)生.假設(shè)存在一個正數(shù)α＊，滿足αk≥α＊，則有

證明 由假設(shè)中的（1），則存在一個常數(shù)M＞0，使得‖αkdk‖＝‖sk‖≤M，由式（18）和αk≥α＊，得到

由式（12）、（13）和－dTkgk＝‖gk‖2，可以得到式（17），即定理得證.

2 數(shù)值試驗

利用文［11－12］中的部分測試函數(shù)檢驗論文算法，并將結(jié)果與文［9］的方法和標(biāo)準(zhǔn)HS方法比較.所有實驗均采用Wolfe線搜索，均不采用重新開始策略.測試環(huán)境為MATLAB7.9.0，運行環(huán)境為內(nèi)存4.00 GB、CPU為2.60 GHz的個人計算機(jī).參數(shù)設(shè)置為：δ＝0.1，σ＝0.45，論文算法中μ＝0.3，終止條件為‖gk‖≤10－6或It－li mit＞9 999.計算得到3種方法的數(shù)值結(jié)果如表1所示.

通過測試可以看出，論文提出的WHS算法要比HS方法優(yōu)越很多，而且大部分算例的計算效果比文［9］中的方法更有效.總體上說，作者提出的共軛梯度法具有良好的數(shù)值性能.但為了能得到更好的數(shù)值效果，還有待進(jìn)一步研究搜索條件的選擇.

表1 數(shù)值測試結(jié)果及其比較Tab.1 The results of numerical test and comparison

致謝 作者感謝萬仲平教授在此論文寫作上的幫助.

［1］ Fletcher R，Reeves C.Function mini mization by conjugate gradients［J］.Co mputer Jour nal，1964（7）：149－154.

［2］ Polak B，Ribiere G.Note surla conver gence de directions conjugees［J］.Rev Fran－caise Infor mat Recherche Opertionelle，1969，16：35－43.

［3］ Polyak B T.The conjugate gradient method in extreme problems［J］.USSR Computational Mat hematics and Mathematical Physics，1969，9：94－112.

［4］ Hestenes M R，Sriefel E L.Methods of conjugate gradient for solving linear systems［J］.Jour nal of Research of the National Bureau of Standards，1952，49（6）：40－43.

［5］ Fletcher R.Practical methods opti mization［C］／／John Wiley ＆ Sons，Unconstrained Opti mization，1987：26－31.

［6］ Dai Y H，Yuan Y.A nonlinear conjugate gradient with a str ong global conver－gence pr operty［J］.SIA M Jour nal on Opti mizton，2000，10：177－182.

［7］ 王開榮，劉金魁，鄒黎敏.一種修正的HS共軛梯度法及全局收斂性［J］.高等學(xué)校計算數(shù)學(xué)學(xué)報，2010，32（2）：150－156.

［8］ Wei Z X，Huang H D，Tao Y R.A modified Hestenes－Stiefel conjugate gradient method and its convergence［J］.Journal of Mathematical Research and Exposition，2010，30（2）：297－308.

［9］ Zhang L，Zhou W，Li D.So me descent three－ter m conjugate gradient methods and their global convergence［J］.Optimisation Methods and Soft ware，2007，22（4）：697－711.

［10］ Chen Y Y，Du S Q.Nonliear conjugate gradient methods with Wolfe type line search［J］.Abstract and Applied Anlysis，2013，2：1－5.

［11］ More J J，Garbow B S，Hillstrome K E.Testing unconstrained opti mization soft ware［J］.ACM Trans Math Sofeware，1981，7：17－41.

［12］ Andrei N.An unconstrained opti mization test f unctions collection［J］.Advanced Modeling and Opti mization，2008，10（1）：147－161.