无约束优化的超记忆梯度算法

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文章编号: 100523085 (2000) 0220099206无约束优化的超记忆梯度算法时贞军(曲阜师范大学运筹学研究所, 山东曲阜 273165) (大连理工大学应用数学系, 辽宁大连 116024)摘要提出了一种无约束优化超记忆梯度算法, 分析了算法的收敛性, 并对算法进行了数值试验, 结果表明算法比a rm ijo 搜索下的 fr 和 pr 共轭梯度法及 c auch y 方法有效, 特别适于求解大规模无约束最优化问 题。关键词 无约束优化, 超记忆梯

2、度法, 收敛性, 数值试验分类号 am s (1991) 49m , 90c 45中图分类号: o 221. 2文献标识码: a引言1考虑无约束优化问题:m in f (x ) ; x rn;其中 f : rn r1 , f c 1构造迭代算法:x k + 1 = x k + k d k(1)(2)其中 d k 为搜索方向, k 为搜索步长。对 k 和 d k 的不同选择就构成了不同的迭代算法。在无约束优化算法中, 一般要求 d k 为下降方向, 或者要求g tk d k 0;其中, g k = v f (x k ).若 d k = - g k , 则算法称为 c auch y 方法1 。若

3、f (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.基金项目: 国家自然科学基金基金项目( 19871049) ; 山东省自然科学基金资助项目(q 98a 06114) 。工程数学学报第 17 卷100前一类算法结构简单, 每次迭代的计算工作量小, 但其收敛速度慢且易产生拉锯现象,故不是一类理想算法。

4、后两类算法在一定条件下收敛速度较快, 但每次迭代的计算工作量较 大, 不适于求解大规模无约束优化问题。60 年代中期, f le tcher 等人3d k = - g k + k d k- 1;提出一种共轭梯度法, 其基本结构是(3)当 k 选取不同的公式时就得到了不同的共轭梯度法4 ,三个有代表性的公式是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)这类方法适于求解大规模问题, 由于共轭梯度法是针对正定二次函数设计的, 虽然在精确搜索下具有二次终止性, 但对一般非线性目标函数, 有些共轭梯度法不具有全局收敛性,有些则数值性能较差5 。近年来, 文9分析了b ea le2pow ell 重新开始算法的收敛性, 所论算法具有很好的数值计算效果, 特别适于求解大规模无约束优化问题。本文提出的超记忆梯度法, 不需要重新开始, 对非线性目标函数不但具有全局收敛性, 而且具有良好的数值计算效果。通过与a rm ijo 搜索下 fr , pr 共轭梯度法及 c auchy 方法的 比较发现

6、超记忆梯度法具有明显的优越性。本文第 2 节叙述算法及其性质, 第 3 节分析算法的收敛性, 第 4 节对算法进行数值试验和比较。算法及其性质假设 (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, 停! 否则转第二步;-g k;k = 1d k =其中g 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 转第一步。首先证明算法的两个性质: 1994-2013 china academic journal electronic publishing house. all rights reserved.第 2 期时贞军: 无约束优化的超记忆梯度

8、算法101引理 1假设 (h ) 成立, 则对 k 有 1g t2k d k -2 g k ( )8证明由 d k 之定义很容易验证 (8) 式成立, 此略。引理 2假设 (h ) 成立, 若算法产生无穷点列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经整理得 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若假设 (h ) 成立, 则算法或有限步终止于问题的稳定点, 或产生无穷点列x k , 其任意极限点都是问题的稳定点。若有 g k = 0, 则 x k 为稳定点, 假设算法产生无穷点列x k , 设 x 3 为其任意极限证明点, 由假设 (h ) 可知 x 3 为一有限点且存在无穷子列x

11、k kn子列。 x 3 , n 0 和 k n, 当 k k , k n 时 1994-2013 china academic journal electronic publishing house. all rights reserved. 工程数学学报第 17 卷102 g k 0由(11) 式可知(12)g tk k 0,k 0(k n)(13)由 k 的取法可知, 若令 = 2k 则(7) 式中的不等号应反号, 即(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 有界, 因而存在无穷子列p k kn 1 p , 其中n 1 n 为无穷序列,令 k (k n 1 ) , 则有g 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 为问题证毕令 k (k n 1 ) 可得 -之稳定点。数值试验由 以上分析可知, 本文提出的算法是一个算法类, k 的选取范围很广, 我们选择文4的几个算例, 对本文算法进行数值试验, 并与a rm ijo 搜索下的共轭梯度法 (fr , pr ) 和最速 下降法进行比较, 计算结果表明算法是有效的。4例 1例 2例 3例 4例 54 维 ro senb rock 函数4 .h e lica l 函数4 .二次型幂函数4 .在例 3 中取

14、 k = 0. 1, 0. 3, 0. 5, 0. 7, 0. 9.扩展 pow e ll 函数4 .我们用 it 表示算法的迭代次数, gm 表示最速下降法, fr 和 pr 分别表示 fr 和 pr 共轭梯度法, sg 表示本文之超记忆梯度法。表中数字为迭代中的目标函数值, 舍入成小数点后 三位有效数字, 一维搜索全部采用a rm ijo 搜索, 且令 1 = 0. 75, = 0. 5。 1994-2013 china academic journal electronic publishing house. all rights reserved.

15、第 2 期时贞军: 无约束优化的超记忆梯度算法103表1 例1的计算结果在 sg 算法中若 bk 存在则取 k = bk , 否则取 k = 1.表2例2的计算结果表3 例3的计算结果表4 例4的计算结果表 3 中 k 表示例 3 中的幂次, 表中数字为目标函数值小于 5 10- 5 时所用迭代次数。表5 例5的计算结果 ( n = 60)表6 例5的计算结果 ( n = 80)从以上数值试验和比较可以看出, sg 算法具有良好的计算效能, 特别适于求解大规模无约束最优化问题。 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)工程数学学报第 17 卷104作者感谢审稿人和编辑对本文提出的宝贵意见。参考文献席少霖. 非线性最优化方法. 北京: 高等教育出版社, 1992袁亚湘, 孙文瑜. 最优化理论与方法. 北京: 科学出版社, 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 赵庆祯. 一个改进的超记忆梯度法的收敛性及敛速估计. 应用数学学报, 1983; 3a superm em ory gra d i