無(wú)約束優(yōu)化的超記憶梯度算法

1、2000年5月m ay 2000jou rn a l o f en g in e er in g m a th em a t ic s文章編號(hào): 100523085 (2000) 0220099206無(wú)約束優(yōu)化的超記憶梯度算法時(shí)貞軍(曲阜師范大學(xué)運(yùn)籌學(xué)研究所, 山東曲阜 273165) (大連理工大學(xué)應(yīng)用數(shù)學(xué)系, 遼寧大連 116024)摘要提出了一種無(wú)約束優(yōu)化超記憶梯度算法, 分析了算法的收斂性, 并對(duì)算法進(jìn)行了數(shù)值試驗(yàn), 結(jié)果表明算法比a rm ijo 搜索下的 fr 和 pr 共軛梯度法及 c auch y 方法有效, 特別適于求解大規(guī)模無(wú)約束最優(yōu)化問(wèn) 題。關(guān)鍵詞 無(wú)約束優(yōu)化, 超記憶梯

2、度法, 收斂性, 數(shù)值試驗(yàn)分類號(hào) am s (1991) 49m , 90c 45中圖分類號(hào): o 221. 2文獻(xiàn)標(biāo)識(shí)碼: a引言1考慮無(wú)約束優(yōu)化問(wèn)題:m in f (x ) ; x rn;其中 f : rn r1 , f c 1構(gòu)造迭代算法:x k + 1 = x k + k d k(1)(2)其中 d k 為搜索方向, k 為搜索步長(zhǎng)。對(duì) k 和 d k 的不同選擇就構(gòu)成了不同的迭代算法。在無(wú)約束優(yōu)化算法中, 一般要求 d k 為下降方向, 或者要求g tk d k 0;其中, g k = v f (x k ).若 d k = - g k , 則算法稱為 c auch y 方法1 。若

3、f (x )二階連續(xù)可微, d k = -2 f(x k ) - 1 g k; 則算法稱為 n ew ton 型方法 2 ;其中v2 fv(x k ) 非奇異。若 d k = - h k g k , 其中h k 為 v尺度方法2 。2 f(x k ) - 1 的某種近似, 這類方法稱為擬n ew ton 方法或變 收稿日期: 1999206207.基金項(xiàng)目: 國(guó)家自然科學(xué)基金基金項(xiàng)目( 19871049) ; 山東省自然科學(xué)基金資助項(xiàng)目(q 98a 06114) 。工程數(shù)學(xué)學(xué)報(bào)第 17 卷100前一類算法結(jié)構(gòu)簡(jiǎn)單, 每次迭代的計(jì)算工作量小, 但其收斂速度慢且易產(chǎn)生拉鋸現(xiàn)象,故不是一類理想算法。

4、后兩類算法在一定條件下收斂速度較快, 但每次迭代的計(jì)算工作量較 大, 不適于求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題。60 年代中期, f le tcher 等人3d k = - g k + k d k- 1;提出一種共軛梯度法, 其基本結(jié)構(gòu)是(3)當(dāng) k 選取不同的公式時(shí)就得到了不同的共軛梯度法4 ,三個(gè)有代表性的公式是fr22(f letch er - r eeves)(4)k = g k / g k- 1 ;g tk (g k- 1 / g k- 1 2;)(po lak 2r ib ie re)( )k =k =g k -g k -5g tk (g k- 1 / d t)k- 1 (g k - g k

5、- 1 ) ;(h e stenes2s t iefel)(6)這類方法適于求解大規(guī)模問(wèn)題, 由于共軛梯度法是針對(duì)正定二次函數(shù)設(shè)計(jì)的, 雖然在精確搜索下具有二次終止性, 但對(duì)一般非線性目標(biāo)函數(shù), 有些共軛梯度法不具有全局收斂性,有些則數(shù)值性能較差5 。近年來(lái), 文9分析了b ea le2pow ell 重新開始算法的收斂性, 所論算法具有很好的數(shù)值計(jì)算效果, 特別適于求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題。本文提出的超記憶梯度法, 不需要重新開始, 對(duì)非線性目標(biāo)函數(shù)不但具有全局收斂性, 而且具有良好的數(shù)值計(jì)算效果。通過(guò)與a rm ijo 搜索下 fr , pr 共軛梯度法及 c auchy 方法的 比較發(fā)現(xiàn)

6、超記憶梯度法具有明顯的優(yōu)越性。本文第 2 節(jié)敘述算法及其性質(zhì), 第 3 節(jié)分析算法的收斂性, 第 4 節(jié)對(duì)算法進(jìn)行數(shù)值試驗(yàn)和比較。算法及其性質(zhì)假設(shè) (h ) : 水平集l 0 =超記憶梯度法如下:2x rn f f (x ) f(x 1 ) 有界。0 2 1 ; x 1 rn; k = 1;初始步:0 1 1;2第一步: 若 g k =第二步:0, 停! 否則轉(zhuǎn)第二步;-g k;k = 1d k =其中g(shù) k + k g k- 1; k 2, bk ;ak , bk ;ak , ) ;(-k =0 0k k k = 這里 k 表示 g k 和 g k- 1 之間的夾角, 而 g k ak (1

7、 - co sk ) =, g k- 1 .g kbk (1 + co sk ) = g k- 1 1 , 1 ,第三步: x k+ 1 =k d k , 其中 k 為1, 中滿足下式的最大者,x k +(x k +222f (x k ) -d k ) - k 1 g t d k;(7)fk第四步: k = k + 1 轉(zhuǎn)第一步。首先證明算法的兩個(gè)性質(zhì): 1994-2013 china academic journal electronic publishing house. all rights reserved.第 2 期時(shí)貞軍: 無(wú)約束優(yōu)化的超記憶梯度

8、算法101引理 1假設(shè) (h ) 成立, 則對(duì) k 有 1g t2k d k -2 g k ( )8證明由 d k 之定義很容易驗(yàn)證 (8) 式成立, 此略。引理 2假設(shè) (h ) 成立, 若算法產(chǎn)生無(wú)窮點(diǎn)列x k , 則g tk d kco s (k ) = - g d (10)k k其中 k 為 - g k 與 d k 之間的夾角。證明由 k 的取法可知下式成立 g k 4 - 2k g k 2 (g t g k - 1 ) +2 (g t g k- 1 ) 2 - g k 2 g k- 1 2 0.kkk上式兩邊同乘以 1 - 2 可得2 ) g k 4 - 2 g k 2 (g t g

9、 k- 1 ) (1 -2 ) +(1 -k22 ) (g t g k - 1 ) 2 -(1 - 2 ) g k 2 g k - 1 2 0.k (1 - k由于 1 - 2 2 , 從而下式成立2 ) g k 4 - 2 g k 2 (g t g k- 1 ) (1 -2 ) +(1 -k2 t22 22k (g k g k- 1 ) - g k g k - 1 0經(jīng)整理得 g k 4 - 2k g k 2 (g t g k - 1 ) +2g t g k- 1 ) 2 2 g k 2 g k 2 -k (kk2k g t g k- 1 +2 g k- 1 2 .kk由于 g t d k

10、= - g k 2 + k g t g k- 1 , d k 2 = g k 2 - 2k g t g k- 1 +2 g k- 1 2 , 故kkkk(g t d k ) 2 2 g k 2 d k 2k由引理 1 可得- g t d k g k d k k從而 (10) 式成立。證畢全局收斂性3定理 1若假設(shè) (h ) 成立, 則算法或有限步終止于問(wèn)題的穩(wěn)定點(diǎn), 或產(chǎn)生無(wú)窮點(diǎn)列x k , 其任意極限點(diǎn)都是問(wèn)題的穩(wěn)定點(diǎn)。若有 g k = 0, 則 x k 為穩(wěn)定點(diǎn), 假設(shè)算法產(chǎn)生無(wú)窮點(diǎn)列x k , 設(shè) x 3 為其任意極限證明點(diǎn), 由假設(shè) (h ) 可知 x 3 為一有限點(diǎn)且存在無(wú)窮子列x

11、k kn子列。 x 3 , n 0 和 k n, 當(dāng) k k , k n 時(shí) 1994-2013 china academic journal electronic publishing house. all rights reserved. 工程數(shù)學(xué)學(xué)報(bào)第 17 卷102 g k 0由(11) 式可知(12)g tk k 0,k 0(k n)(13)由 k 的取法可知, 若令 = 2k 則(7) 式中的不等號(hào)應(yīng)反號(hào), 即(x k + 2k d k ) - 2k 1 g t d k;(x k ) -ffk亦可表示為f (x k ) -f (x k + 2k

12、) - 2g t k(14)k由(13) 式中第一式及引理 2 可得 k 0令 p k = d k / d k , 則(k n)(15)2k = 2 k p k = k p k ,其中k = 2 k 0 (k n) , 由(14) 式得f (x k ) - f (x k + k p k ) -g tk p k.k3由于 p k = 1, 即p k kn 有界, 因而存在無(wú)窮子列p k kn 1 p , 其中n 1 n 為無(wú)窮序列,令 k (k n 1 ) , 則有g(shù) 3 t p 31 g 3 t p 3- -從而g 3 t p 3(16)0另一方面由引理 2 可得- g t p k = -g

13、t d k / d k = g k co s (k ) g k g 3 , 與(16) 式相矛盾, 故必有 g 3kkg 3 t p 3= 0, 即 x 3 為問(wèn)題證畢令 k (k n 1 ) 可得 -之穩(wěn)定點(diǎn)。數(shù)值試驗(yàn)由 以上分析可知, 本文提出的算法是一個(gè)算法類, k 的選取范圍很廣, 我們選擇文4的幾個(gè)算例, 對(duì)本文算法進(jìn)行數(shù)值試驗(yàn), 并與a rm ijo 搜索下的共軛梯度法 (fr , pr ) 和最速 下降法進(jìn)行比較, 計(jì)算結(jié)果表明算法是有效的。4例 1例 2例 3例 4例 54 維 ro senb rock 函數(shù)4 .h e lica l 函數(shù)4 .二次型冪函數(shù)4 .在例 3 中取

14、 k = 0. 1, 0. 3, 0. 5, 0. 7, 0. 9.擴(kuò)展 pow e ll 函數(shù)4 .我們用 it 表示算法的迭代次數(shù), gm 表示最速下降法, fr 和 pr 分別表示 fr 和 pr 共軛梯度法, sg 表示本文之超記憶梯度法。表中數(shù)字為迭代中的目標(biāo)函數(shù)值, 舍入成小數(shù)點(diǎn)后 三位有效數(shù)字, 一維搜索全部采用a rm ijo 搜索, 且令 1 = 0. 75, = 0. 5。 1994-2013 china academic journal electronic publishing house. all rights reserved.

15、第 2 期時(shí)貞軍: 無(wú)約束優(yōu)化的超記憶梯度算法103表1 例1的計(jì)算結(jié)果在 sg 算法中若 bk 存在則取 k = bk , 否則取 k = 1.表2例2的計(jì)算結(jié)果表3 例3的計(jì)算結(jié)果表4 例4的計(jì)算結(jié)果表 3 中 k 表示例 3 中的冪次, 表中數(shù)字為目標(biāo)函數(shù)值小于 5 10- 5 時(shí)所用迭代次數(shù)。表5 例5的計(jì)算結(jié)果 ( n = 60)表6 例5的計(jì)算結(jié)果 ( n = 80)從以上數(shù)值試驗(yàn)和比較可以看出, sg 算法具有良好的計(jì)算效能, 特別適于求解大規(guī)模無(wú)約束最優(yōu)化問(wèn)題。 1994-2013 china academic journal electronic publishing hou

16、se. all rights reserved. itgmfrprsg0510404. 300 (3)1. 728 (2)1. 572 (0)1. 270 (- 3)4. 300 (3)6. 381 (2)8. 721 (0)8. 765 (- 3)4. 300 (3)8. 190 (1)6. 770 (- 1)1. 851 (- 4)4. 300 (3)6. 031 (1)8. 679 (- 2)6. 718 (- 6)itgmfrprsg0510403. 225 (3)6. 137 (1)1. 208 (1)7. 216 (- 4)3. 225 (3)8

17、. 796 (1)1. 776 (1)9. 118 (- 3)3. 225 (3)4. 017 (1)1. 010 (1)1. 820 (- 5)3. 225 (3)1. 210 (1)1. 886 (0)1. 717 (- 6)kgmfrprsg234530342850253026542523203020251824kgmfrprsgbound0. 10. 30. 50. 70. 980786053187773625122606859471630504237135 (- 2)5 (- 3)5 (- 5)5 (- 5)5 (- 5)itgmfrprsg0515402. 500 (3)3. 15

18、1 (0)6. 581 (- 1)8. 727 (- 5)2. 500 (3)6. 177 (2)6. 298 (1)3. 214 (- 5)2. 500 (3)8. 352 (0)3. 252 (- 1)6. 732 (- 6)2. 500 (3)2. 727 (0)6. 723 (- 3)1. 086 (- 6)itgmfrprsg01020601. 919 (4)3. 872 (1)2. 770 (0)1. 095 (- 3)1. 919 (4)9. 395 (1)6. 601 (1)6. 321 (1)1. 919 (4)9. 896 (0)7. 804 (0)1. 541 (- 2)

19、1. 919 (4)3. 593 (1)4. 917 (- 2)5. 025 (- 4)工程數(shù)學(xué)學(xué)報(bào)第 17 卷104作者感謝審稿人和編輯對(duì)本文提出的寶貴意見(jiàn)。參考文獻(xiàn)席少霖. 非線性最優(yōu)化方法. 北京: 高等教育出版社, 1992袁亞湘, 孫文瑜. 最優(yōu)化理論與方法. 北京: 科學(xué)出版社, 1997h u y f , s to rey c. g loba l conve rgence re su lt fo r con juga te g rad ien t m e thod s. jo ta , 1991; 71: 399 405l iu y, s to rey c. e ff icien

20、 t gene ra lizd con juga te g rad ien t a lgo r ithm s. p a r t i t h eo ry, jo ta , 1991; 1 ( 69) :129 137bo land w r , kow a lik j s. e x tended con juga te g rad ien t m e thod s w ith re sta r t s. jo ta , 1979; 28: 1 9d ixon l c w , con juga te d irect ion s w ithou t line sea rch. j in st m a

21、th s a pp lics, 1973; 11: 317 328h an j iye, l iu guangh u i, y in h ongx ia. conve rgence p rop e r t iie s of con juga te g rad ien t m e thod s w ith st rong. w o lfe line sea rch , sy stem s science and m a th em a t ica l science s, 1998; 2 (11) : 112 116yax iang yuan. a na ly sis on th e con j

22、uga te g rad ien t m e thod. o p t im iza t ion m e thod s and sof tw a re, 1993; 2:19 29d a i yuhong, yuan yax iang. conve rgence p rop e r t ie s of b ea le2pow e ll re sta r t a lgo r ithm. science in ch ina,1998; 11 (41) : 1142 115012345678911 趙慶禎. 一個(gè)改進(jìn)的超記憶梯度法的收斂性及斂速估計(jì). 應(yīng)用數(shù)學(xué)學(xué)報(bào), 1983; 3a superm em ory gra d i