下降對稱的Polak-Ribiere-Polyak共軛梯度法

劉東毅，邵 琛

(1. 天津大學(xué)理學(xué)院，天津 300072；2. 天津大學(xué)電氣與自動化工程學(xué)院，天津 300072；3. 哈爾濱理工大學(xué)應(yīng)用科學(xué)學(xué)院，哈爾濱 150080)

不同參數(shù)βk對應(yīng)不同的算法，如常見的Hestenes-Stiefel(HS)算法[1]，F(xiàn)letcher-Reeves(FR)算法[2]，Polak-Ribiere-Polyak(PRP)算 法[3]和 Dai-Yuan(DY)算法[4]等．共軛梯度法還需要一維搜索，如廣泛使用的強Wolfe線性搜索算法，即步長kα滿足

為了保證共軛梯度法的全局收斂性，通常需要搜索方向kd滿足下降性質(zhì)，即

式中： c＞0 ；上標(biāo)T表示矩陣或向量轉(zhuǎn)置．與擬牛頓法不同，共軛梯度法對于不精確線搜索一般不滿足式(5)或式(6)．因此，許多學(xué)者致力于研究對于任何線搜索都滿足下降性質(zhì)的算法．Shanno[7]基于 Perry[8]的思想，運用擬牛頓方程和自調(diào)比技術(shù)，提出了無記憶擬牛頓法和自調(diào)比共軛梯度法．Touati-Ahmed和Storey[9]組合了 FR算法和 PRP算法，并提出了一些混合共軛梯度法．Liu和 Storey[10]提出了 LS算法．最近的研究進展參見文獻[11-14]．

本文應(yīng)用對稱化技術(shù)[15]于 PRP算法，獲得一種對稱的 PRP算法，它們對于任何線搜索都滿足下降性質(zhì)式(5)和式(6)．更重要的是，這種思想可以應(yīng)用到其他共軛梯度法中．

1 對稱的共軛梯度法

按照 Perry[8]的建議，經(jīng)典的 HS共軛梯度法[1]的搜索方向1k+d 寫成

2 下降對稱PRP算法

3 DSPRP算法的全局收斂性

證明 根據(jù) DSPRP算法構(gòu)造，由式(14)～式(16)可知，它產(chǎn)生的搜索方向1k+d 滿足充分下降條件式(6)，再由強Wolfe線性搜索式(3)和式(5)，可得到

4 數(shù)值試驗

通過一些試驗函數(shù)來驗證DSPRP算法的數(shù)值效果，并與PR+算法[6]作比較來說明DSPRP算法的優(yōu)越性和實用性．試驗函數(shù)見表1．

表1 試驗函數(shù)Tab.1 Test functions

自變量的個數(shù)n分別取為1,000和10,000(除函數(shù)4與6外)．初始點由文獻提供．根據(jù)定理3，試驗使用強 Wolfe線性搜索，并且其子程序根據(jù)文獻[16]第3章中的算法編寫．記α0,1為線搜索第1次迭代初始試探步長，α0,k+1為線搜索隨后的第k+1次迭代初始試探步長．在DSPRP算法中，取γ= 10-4，δ= 1 0-4，μ= 0 .1，σk≡ 1．?dāng)?shù)值試驗分成如下4組．

表2 DSPRP算法的數(shù)值結(jié)果Tab.2 Numerical results of the DSPRP algorithm

表3 PR+算法的數(shù)值結(jié)果Tab.3 Numerical results of the PR+ algorithm

從表 2和表 3中可以看出，當(dāng)線搜比較精確時(20.1c= )，DSPRP算法與 PRP+算法不論從迭代次數(shù)還是 nfg的數(shù)值上比較，二者的性能均相差不多，但當(dāng)線搜比較粗糙時(20.9c= )，DSPRP算法要比 PRP+算法的效果好得多．例如：與 PR+1相比，G1和 G2只失敗了3次，而PR+1失敗了8次；與PR+2相比，G3和G4分別失敗了5次和3次，PR+2卻失敗了20次．因此，可以看出DSPRP算法更實用和穩(wěn)健．

5 結(jié) 語

筆者利用的對稱化思想也可以應(yīng)用到其他共軛梯度法中，如 HS法和 FR法等．在全局收斂性證明中，迭代矩陣譜的分布情況起了很重要的作用，由此得到的收斂性結(jié)論是=0．在數(shù)值試驗中γ和μ的值取得很小，這主要是為了考察對稱化的效果，而試驗結(jié)果正好驗證其良好的效果．

［1］Hestenes M R，Stiefel E. Methods of conjugate gradients for solving linear systems [J].Journal of Research of the National Bureau of Standards，1952，49(6)：409-439.

［2］Fletcher R，Reeves C. Function minimization by conjugate gradients [J].Computer Journal，1964，7(2)：149-154.

［3］Polyak B T. The conjugate gradient method in extreme problems [J]. USSRComputation Math and Math Physics，1969，9(4)：94-112.

［4］Dai Yuhong，Yuan Yaxiang. A nonlinear conjugate gradient method with a strong global convergence property[J].SIAM Journal on Optimization，1999，10(1)：177-182.

［5］Al-Baali M. Descent property and global convergence of the Fletcher-Reeves method with inexact line-search [J].IMA Journal of Numerical Analysis，1985，5(1)：121-124.

［6］Gilbert J C，Nocedal J. Global convergence properties of conjugate gradient methods for optimization [J].SIAM Journal on Optimization，1992，2(1)：21-42.

［7］Shanno D F. Conjugate gradient methods with inexact searches [J].Mathematics of Operations Research，1978，3(3)：244-256.

［8］Perry A. A modified conjugate gradient algorithm [J].Operations Research Technical Notes，1978，26(6)：1073-1078.

［9］Touati-Ahmed D，Storey C. Efficient hybrid conjugate gradient techniques [J].Journal of Optimization Theory and Applications，1990，64(2)：379-397.

［10］Liu Y，Storey C. Efficient generalized conjugate gradient algorithms [J].Journal of Optimization Theory andApplications，1991，69(1)：129-137.

［11］Hager W W，Zhang Hongchao. A new conjugate gradient method with guaranteed descent and an efficient line search [J].SIAM Journal on Optimization，2005，16(1)：170-192.

［12］Yu Gaohang，Zhao Yanlin，Wei Zengxin. A descent nonlinear conjugate gradient method for large-scale unconstrained optimization [J].Applied Mathematics and Computation，2007，187(2)：636-643.

［13］Zhang Li，Zhou Weijun，Li Donghui. Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search [J].Numerische Mathematik，2006，104(4)：561-572.

［14］Andrei N. Another hybrid conjugate gradient algorithm for unconstrained optimization [J].Numerical Algorithms，2008，47(2)：143-156.

［15］Powell M J D. A new algorithm for unconstrained optimization [C]//Rosen J B，Mangasarian O L，Ritter K．Nonlinear Programming.New York：Academic Press，1970：31-66.

［16］Nocedal J，Wright S J.Numerical Optimization[M].2nd ed．New York：Springer Science +Business Media，Inc，2006.

［17］Buckley A，Lenir A. QN-like variable storage conjugate gradients[J]．Mathematical Programming，1983，27(2)：155-175.

［18］Moré J J，Garbow B S，Hillstrom K E. Testing unconstrained optimization software [J].ACM Transactions on Mathematical Software，1981，7(1)：17-41.

［19］Grippo L，Lampariello F，Lucidi S A. Truncated Newton method with nonmonotone line search technique for unconstrained optimization [J].Journal of Optimization Theory and Applications，1989，60(3)：401-419.

［20］Raydan M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem [J].SIAM Journal on Optimization，1997，7(1)：26-33.