（运筹学与控制论专业论文）新的共轭梯度法和谱梯度法的研究.pdf

新的共轭梯度法和谱梯度法的研究 摘要 本文给出求解大规模无约束优化问题新的共轭梯度法和谱梯度法，并探讨 用谱梯度投影法来求解闭凸集约束优化问题。在适当的条件下，证明了所提出 算法的全局收敛性。初步的数值结果表明所提出的算法是有效的。 第一章先回顾共轭梯度法和谱梯度法的一些发展历程，随后介绍有关投影 梯度法的相关知识。 经典的l s 共轭梯度法在实际计算中表现很好，但是采用传统的线性搜索 该方法尚未有全局收敛性结果。第二章给出求解无约束优化问题的一个修正 l s 共轭梯度法，在弱w o l f e - p o w e l l 线性搜索条件下，证明了所提出方法的全局 收敛性。该方法的主要优点是：( 1 ) 参数臃删的非负性与所使用的线性搜索无 关；( 2 ) 算法产生的方向在弱w o l f e - p o w e l l 线性搜索条件下满足充分下降条件。 初步的数值结果表明所提出的方法比经典的p r p 和l s 方法要好。 文 1 中给出的数值结果证实了谱梯度( b a r z i l a i b o r w e i n ) 法在实际计算中的 表现比一些著名的共轭梯度法要好。基于w e i 等在文 2 中提出的拟牛顿公式， 第三章给出谱梯度法的新步长公式。结合非单调线性搜索技术，在适当条件 下，证明了所提出方法的全局收敛性。新方法的特点是：同时利用梯度和函数 值的信息能更好地逼近目标函数的二阶曲率。初步的数值结果表明新方法比 b a r z i l a i b o r w e i n 方法更有效。 文 3 】的数值结果表明求解闭凸集约束优化问题的非单调谱投影梯度法 ( s p g 2 ) 是有效的。第四章给出求解大规模闭凸集约束优化问题新的非单调谱 投影梯度算法。在目标函数的梯度是一致连续的条件下，证明了所提出的算法 是全局收敛的。该证明不需要目标函数下方有界和极限点预先存在的条件。初 步的数值结果表明所提出的算法比s p g 2 方法要好。 关键词：大规模优化无约束优化共轭梯度法投影梯度法 b a r z i l a i b o r w e i n 方法非单调线性搜索全局收敛 r e s e a r c ho nan e wc o n j u ga t eg r a d i e n tm e t h o d a n ds p e c t r a lg r a d i e n tm e t h o d s a b s t r a c t t h i st h e s i sd e v e l o p san e wc o n j u g a t eg r a d i e n tm e t h o da n da s p e c t r a lg r a d i e n tm e t h o d f o rs o l v i n gl a r g e - s c a l eu n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s ，a n ds t u d i e ss p e c t r a lp r o j e c t e d g r a d i e n tm e t h o df o rt h em i n i m i z a t i o no fd i f f e r e n t i a b l ef u n c t i o n so nc l o s e dc o n v e xs e t s u n - d e rs o m em i l dc o n d i t i o n s ，t h eg l o b a lc o n v e r g e n c er e s u l t so ft h e s em e t h o d sa r ee s t a b l i s h e d p r e l i m i n a r yn u m e r i c a lr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o d sa r ee f f i c i e n t c h a p t e r1r e v i e w st h ed e v e l o p m e n to fc o n j u g a t eg r a d i e n tm e t h o d sa n ds p e c t r a lg r a d i e n tm e t h o d s l a t e r ，s o m eb a s i ck n o w l e d g ea b o u tp r o j e c t e dg r a d i e n tm e t h o d si si n t r o d u c e d c l a s s i c a ll i u - s t o r e y ( l s ) c o n j u g a t eg r a d i e n tm e t h o dp e r f o r m sv e r yw e l li np r a c t i c a l c o m p u t a t i o n ，b u ti th a sn og l o b a lc o n v e r g e n c er e s u l tu n d e rt r a d i t i o n a ll i n es e a r c h e s i n c h a p t e r2 ，am o d i f i e dl sc o n j u g a t eg r a d i e n tm e t h o di sp r e s e n t e da n d i t sg l o b a lc o n v e r g e n c e i sp r o v e dw h e nw e a kw o l f e - p o w e l ll i n es e a r c hc o n d i t i o n sa r es a t i s f i e d t h em a i na d v a n t a g e s o ft h i sm e t h o da x et h a t ( i ) t h ep a r a m e t e r 露伽k e e p sn o n n e g a t i v ei n d e p e n d e n to fl i n es e a r c h u s e d ；( i i ) t h ed i r e c t i o ng e n e r a t e db yt h ea l g o r i t h ma l w a y ss a t i s f i e st h es u f f i c i e n td e s c e n t c o n d i t i o n p r e l i m i n a r yn u m e r i c a lr e s u l t ss h o wt h a tt h i sm e t h o do u t p e r f o r m sc l a s s i c a ll s a n dp r pm e t h o d s t h es p e c t r a l ( b a x z i l a i b o r w e i n ) g r a d i e n tm e t h o dw a sp r o v e dt op e r f o r mb e t t e rt h a n s o m ew e l l k n o w nc o n j u g a t eg r a d i e n tm e t h o d s ( 1 i nc h a p t e r3 ，an e wc l a s so fs t e p s i z e s f o rs p e c t r a lg r a d i e n tm e t h o di sd e r i v e df r o ma p p r o a c h i n gt h en e wq u a s i n e w t o ne q u a t i o n g i v e ni nf 2 u n d e rs o m em i l dc o n d i t i o n s ，t h eg l o b a lc o n v e r g e n c er e s u l to ft h ep r o p o s e d s p e c t r a lg r a d i e n ta l g o r i t h mi nc o n j u n c t i o nw i t han o n m o n o t o n el i n es e a r c hi se s t a b l i s h e d i t sf e a t u r e sa r et h a tt h em e t h o dt a k e sb o t ha v a i l a b l eg r a d i e n ta n df u n c t i o nv a l u ei n f o r - m a r i o n ，a n da c h i e v e sb e t t e ra p p r o x i m a t i o nt ot h es e c o n d - o r d e rc u r v a t u r eo ft h eo b j e c t i v e f u n c t i o n p r e l i m i n a r yn u m e r i c a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi sb e t t e rt h a n t h eb a x z i l a i b o r w e i na p p r o a c h n o n m o n o t o n es p e c t r a lp r o j e c t e dg r a d i e n t ( s p g 2 ) m e t h o dc o m p a r e sf a v o r a b l yw i t h t h ew e l l k n o w np a c k a g el a n c e l o tf o rt h em i n i m i z a t i o no fd i f f e r e n t i a b l ef u n c t i o no n c l o s ec o n v e xs e t s 3 】i nc h a p t e r4 ，an e wn o n m o n o t o n es p e c t r a lp r o j e c t e dg r a d i e n ta l g o r i t h mi sd e v e l o p e d i ft h eg r a d i e n to fo b j e c t i v ef u n c t i o ni su n i f o r m l yc o n t i n u o u s ，t h eg l o b a l c o n v e r g e n c er e s u l to ft h ea l g o r i t h mi se s t a b l i s h e dw i t h o u tr e q u i r i n gb o u n d e d n e s sb e l o wo f ja n dp r i o re x i s t e n c eo ft h el i m i tp o i n t ，n u m e r i c a le x p e r i m e n t ss h o wt h a tt h ep r o p o s e d a l g o r i t h ma c h i e v e sb e t t e rp e r f o r m a n c et h a nt h es p g 2m e t h o d k e yw o r d s ：l a r g e - s c a l eo p t i m i z a t i o n ；u n c o n s t r a i n e do p t i m i z a t i o n ；c o n j u g a t e g r a d i e n tm e t h o d ；p r o j e c t e dg r a d i e n tm e t h o d ；b a r z i l a i - b o r w e i ng r a d i e n tm e t h o d ；n o n m o n o - t o n el i n es e a r c h ；g l o b a lc o n v e r g e n c e 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相关 知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究成 果，也不包含本人为获得其它学位而使用过的内容对本文的研究工作提供过重要帮助的 个人和集体，均已在论文中明确说明并致谢 论文作者签名：崔岁蟹东 2 0 0g 年6 月6 日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容 请选择发布时间： d 即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名： 黄岁萄糸 导师貅辛瞎放 础年石月日 广西大学硕士学位论文( 2 0 0 8 )新的共轭梯度法和谱梯度法的研究 c h a p t e r1 i n t r o d u c t i o n 1 1l a r g e - s c a l en o n l i n e a ro p t i m i z a t i o np r o b l e m s o p t i m i z a t i o np r o b l e m sh a v ev e r yw i d ea p p l i c a t i o n s ，s u c ha st r a n s p o r t a t i o n ，t e l e c o m - m u n i c a t i o na n do t h e rd o m a i n s h o w e v e r ，i np r a c t i c a ll e v e l ，a st h ep r o b l e ms i z ei n c r e a s e s ， t h ea m o u n to fn e c e s s a r yc a l c u l a t i o na l s og r o w se x p o n e n t i a l l y t h e r e f o r e ，i tr e q u i r e sn e w m e t h o d st os o l v et h el a r g e - s c a l en o n l i n e a ro p t i m i z a t i o np r o b l e m m i n f ( x ) jz q 蹰n ) ， w h e r e 厂：舻_ 跪i sac o n t i n u o u s l yd i f f e r e n t i a b l ef u n c t i o n ，a n dqi saf e a s i b l es e t ( 1 1 1 ) i fq = 渺，t h e nt h ep r o b l e m ( 1 1 1 ) i sc a l l e du n c o n s t r a i n e do p t i m i z a t i o np r o b l e m ， t h a ti s ， m i n f ( x ) lz 舻) ( 1 1 2 ) d i f f e r e n tm e t h o d sh a v eb e e nd e v e l o p e df o rs o l v i n gt h el a r g e s c a l eu n c o n s t r a i n e do p t i m i z a - t i o np r o b l e m ( 1 1 2 ) t w oc l a s s e so ft h em o s tp o p u l a rm e t h o d sa r ec o n j u g a t eg r a d i e n t m e t h o d sa n ds p e c t r a lg r a d i e n tm e t h o d s w er e v i e wt h ed e v e l o p m e n to ft h e s et w om e t h o d s a tf i r s t 1 2c o n j u g a t eg r a d i e n tm e t h o d s c o n j u g a t eg r a d i e n tm e t h o d sa r ea p p e a l i n gf o rs o l v i n gp r o b l e m ( 1 1 2 ) s i n c et h e yr e - q u i r el e s sc o m p u t e rm e m o r ye s p e c i a l l yw h e nt h en u m b e ro fv a r i a b l e ，n ，i sl a r g e t h e s e m e t h o d sc a nb ed e s c r i b e db yt h ei t e r a t i v er u l e ： x k + l2x k + s ka n ds k = a 克d 血， ( 1 2 1 ) w h e r et h ep o s i t i v es t e p - s i z e 口惫i so b t a i n e db ys o m el i n es e a r c h ，a n dt h ed i r e c t i o nd 七i sa s e a r c hd i r e c t i o nd e f i n e db y d = - - g k ；d 七一。篓竺三呈： h e r e8 ki sas c a l a ra n dg k = v ( x k ) s o m ew e l l - k n o w nf o r m u l a s 8 嚣s = 以，n ，一，1 、 3 k 3 托3 托一l ， ( 鲰一g k 一1 ) t d k 一1 闩f r u k 一 恢f | 2 l 一1 1 1 2 兄p ：堡! 墨二笠= 12 慨一1 1 2 ( 1 2 2 ) f o r8 ka r eg i v e nb e l o w ： ( h e s t e n e s s t i e f e l 4 】，1 9 5 2 ) ； ( f l e t c h e r r e e v e s 5 】j 19 6 4 ) ； ( p o l a k r i b i r e p o l y a k 6 ，7 ，1 9 6 9 ) ； 广西大学硕士学位论文( 2 0 0 8 ) 新的共轭梯度法和谱梯度法的研究 鳄。一悬( g 叨岫嬲c e m i s 1 9 8 7 ) ； f l 毒s = 一掣( 勘u - s t o r e y 【9 1 9 9 1 ) ； q d y 尸七一 i i g k l l 2 ( 夕_ j 一g k 一1 ) ? d k 一1 ( d 西一y u a n 【l o ，1 9 9 9 ) ， w h e r e d e n o t e st h e1 2 一n o r m t h ec o r r e s p o n d i n gc o n j u g a t eg r a d i e n tm e t h o d sc a nb e a b b r e v i a t e da sh s ，f r ，p r p , c d ，l sa n dd ym e t h o d s a l t h o u g ht h e s em e t h o d sa r e i d e n t i c a lw h i l e i sas t r o n gc o n v e xq u a d r a t i cf u n c t i o na n dl i n es e a r c hi se x a c t it h e yh a v e d i f f e r e n tp e r f o r m a n c e sw h e na p p l i e dt om i n i m i z i n gg e n e r a ln o n l i n e a rf u n c t i o n sw i t hi n e x a c t l i n es e a r c h e s t h ec o n v e r g e n c ep r o p e r t i e so fa b o v ec o n ju g a t e g r a d i e n tm e t h o d sh a v eb e e ne x t e n s i v e l y s t u d i e d f o rt h ef rm e t h o d ，i fab a dd i r e c t i o na n dat i n n ys t e pf r o mx k 一1t ox ka r e g e n e r a t e d ，t h en e x td i r e c t i o nd ka n dt h en e x ts t e p8 ka r ea l s ol i k e l y t ob ep o o ru n l e s s ar e s t a r ta l o n gt h eg r a d i e n td i r e c t i o ni sp e r f o r m e d i ns p i t eo fs u c hd e f e a t z o u t e n d i j k 11 】p r o v e dt h a tt h ef r m e t h o di sg l o b a l l yc o n v e r g e n tf o rt h eg e n e r a lf u n c t i o n su n d e rt h e f o l l o w i n ge x a c tl i n es e a r c h ，( z 七一c z k d k ) = m 口) i n uf ( z k a d k ) ( 1 2 3 ) as u r p r i s i n gf a c ta b o u tp r pm e t h o di st h a tt h ee x a c tl i n es e a r c hc o n d i t i o n ( 1 2 3 ) d o e s n o tg u a r a n t e et h a tt h ep r pm e t h o di sg l o b a l l yc o n v e r g e n tf o rg e n e r a lf u n c t i o n s ；s e et h e c o u n t e r e x a m p l eo fp o w e l l 12 i ft h ep a r a m e t e r 反i sd e f i n e db y 仇= m a x ( 雕r p ，o ) ， t h er e s u l t i n gc o n j u g a t eg r a d i e n tm e t h o di sc a l l e dp r p + m e t h o d a t e db yt h i sm e t h o da l w a y ss a t i s f i e st h ed e s c e n tc o n d i t i o n g d k 0 b a s e do ns t r o n gw o l f e - p o w e l ll i n es e a r c hc o n d i t i o n s f ( x k + a k d k ) 一，( z 凫) 6 q 知纸t d 凫 a n d 献石一。订d k - 1 - a k a 忌)i 咿簖以；，i y 山f ( 7 1 9 惫“知i ( 1 2 4 ) t h ed i r e c t i o nd kg e n e r - ( 1 2 5 ) ( 1 2 6 ) k 1 2 - ，j w i t h0 6 盯 0 a n dp ( 0 ，1 ) ，f i n d q 户m a x 镏学；歹= o 1 ) ， s u c ht h a t ( x 七+ 1 ) ( x k ) 一6 0 ：l i d 。1 1 2 一c 2i i g ( z 知+ a 豇d 七) 1 1 2 g ( x k + a k d k ) t d k + l 墨一c ll l g ( x 忌+ q 南d 南) 1 1 2 ， w h e r eoc1 0s a t i s f y i n gt h ew e a kw o l f e - p o w e l ll i n es e a r c hc o n d i t i o n s s t e p2 ：l e tz k + 1 = 2 ；k + o l k d ka n dg k + 1 = 夕( z 七+ 1 ) i f9 七+ 1 = 0 ，t h e ns t o p s t e p3 ：c o m p u t e 仇b yt h ef o r m u l a ( 2 1 1 ) a n dg e n e r a t ed 南+ 1b y ( 1 2 2 ) s