（运筹学与控制论专业论文）一类修改的共轭梯度法的全局收敛性.pdf

一类修改的共轭梯度法的全局收敛性 摘要 共轭梯度法是求解大规模优化问题最常用的方法之一。近年来， h a g e r 和z h a n g 及d a i 和l i a o 提出了一些有效的共轭梯度法。在此基础 上，本文提出一类修改的共轭梯度法。在适当的条件下，这些方法均满 足充分下降条件。本学位论文的具体内容如下： 第一章回顾了共轭梯度法的发展过程，并重点介绍了相关的共轭梯 度法。 第二章，根据h a g e r 和z h a n g 提出的参数公式，给出了一个新的 共轭梯度法，并在强w o l f e p o w e l l 条件下证明了其对强凸函数的全局收 敛性。之后，本章给出了两个相关的杂交共轭梯度法，并在强w o l f e p o w e l l 条件下证明了它们对一般非线性函数的全局收敛性。 第三章，根据d a i 和l i a o 提出的参数公式1 及h a g e r 和z h a n g 提 出的参数公式，给出了另一个新的共轭梯度法，并在弱w r 0 1 f e p o w e l l 条件下证明了它对强凸函数的全局收敛性。之后，本章给出了一个相关 的杂交共轭梯度法，并在弱w o l f e p o w e l l 条件下，证明了它对一般非线 性函数的全局收敛性。 第四章，给出了相关算法的数值结果，从数值结果角度分析了新方 法的有效性。 敛性 关键词：无约束优化共轭梯度法充分下降条件线搜索全局收 g l o b a lc o n v e r g e n c eo fat y p eo fm o d i f i e d c o n j u g a t eg r a d i e n tm 匠t h o d a b s t r a c t c o n ju g a t eg r a d i e n tm e t h o di so n eo ft h em o s tu s e f u lm e t h o d sf o rl a - g e r - 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 n r e c e n t l y h a g e r - z h a n ga n dd a i l i a o p r o p o s e ds o m ee f f e c t i v ec o n ju g a t eg r a d i e n tm e t h o d s t og e tm o r ee f f i c i e n t m e t h o d si nt h en u m e r i c a l p e r f o r m a n c e ，at y p eo fm o d i f i e dc o n j u g a t eg r a d i e n t m e t h o di sp r o p o s e d u n d e rm i l dc o n d i t i o n s ，o u rm e t h o d sa l ls a t i s f ys u f f i c i e n t d e s c e n tp r o p e r t y t h et h e s i si so r g a n i z e da sf o l l o w s ： 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 ft h ec o n j u g a t eg r a d i e n tm e t h o d s a n di n t r o d u c e ss o m er e l a t e dc o n j u g a t eg r a d i e n tm e t h o d s i nc h a p t e r2 ，b a s e do nt h eu p d a t ep a r a m e t e rp ：o fh a g e r - z h a n g ，an e w c o n j u g a t eg r a d i e n tm e t h o di sp r o p o s e d u n d e rs t r o n gw o l f e p o w e l lc o n d i t i o n s ，i t sg l o b a lc o n v e r g e n c ef o rs t r o n g l yc o n v e xf u n c t i o n si sp r o v e d t h e n ， t w or e l a t e dh y b r i dc o n j u g a t eg r a d i e n tm e t h o d sa r ea l s op r o p o s e d t h e i rg l o b a l c o n v e r g e n c e f o r g e n e r a l n o n l i n e a rf u n c t i o n si s p r o v e d w i t h s t r o n g w 6 1f e p o w e l lc o n d i t i o n s i nc h a p t e r3 ，b a s e do nt h eu p d a t ep a r a m e t e rp ：o fh a g e r - z h a n ga n dt h e u p d m ep a r a m e t e r8 po fd a i - l i a o ，a n o t h e rn e wc o n j u g a t eg r a d i e n tm e t h o di s p r o p o s e d u n d e rw e a kw o l f e - p o w e l lc o n d i t i o n s ，i t sg l o b a lc o n v e r g e n c ef o r s t r o n g l yc o n v e xf u n c t i o n si sp r o v e d t h e n ，o n er e l a t e dh y b r i dc o n j u g a t eg r a - d i e n tm e t h o di sa l s op r o p o s e d i t sg l o b a lc o n v e r g e n c ef o rg e n e r a ln o n l i n e a r f u n c t i o n si sp r o v e dw i t hw e a kw o l f e p o w e l lc o n d i t i o n s i nc h a p t e r4 ，n u m e r i c a lr e s u l t sa r er e p o r t e d f r o mn u m e r i c a lp o i n t ，t h e n e wm e t h o d sa r ee 筒c i e n t k e yw o r d s ：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 eg r a d i e n tm e t h o d ； s u f f i c i e n td e s c e n tc o n d i t i o n ；l i n es e a r c h ；g l o b a lc o n v e r g e n c e 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和 相关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的 研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过 重要帮助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：日 邑第 学位论文使用授权说明 如g 年占月占e l 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文： 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 函口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：榔导师签名：韦移罾饮弘- 3 年二月日 ， 广西大掌硕士掌位论文( 2 0 0 8 ) 一类修改的共轭梯度法的全局收敛性 c h a p t e r1 i n t r o d u c t i o n t h ep r o b l e mo fi n t e r e s tc a l lb es t a t e da st h a to ff i n d i n gas o l u t i o nx t ot h ep r o b l e m m i n f ( x ) ， w h e r ef ：r “一ri 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 t h e s ep r o b l e m so f t e na r i s en o to n l yf r o ma p p l i c a t i o nf i e l d ss u c ha se c o n o m i c ，s o c i a l ， s c i e n c e ，e n g i n e e r i n g ，m a n a g e m e n tf i e l d s ，e t e ，b u ta l s of r o mt h e o r e t i c a lf i e l d sb e c a u s em o s t o fo p t i m i z a t i o np r o b l e mc a l lb er e d u c e dt oa l lu 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 】 t h ec o n j u g a t eg r a d i e n tm e t h o di sap o w e r f u la p p r o a c hf o rs o l v i n gl a r g es c a l em i n i m i z a t i o np r o b l e m sd u et oi t ss m a l l e rs t o r a g er e q u i r e m e n t sa n ds i m p l ec o m p u t a t i o n t h i s m e t h o dw a sm o t i v a t e db yh e s t e n c ea n ds t i e f e l 【2 f o rs o l v i n gs y m m e t r i cp o s i t i v ed e f i n i t e l i n e a re q u a t i o n sa n dd e v e l o p e db yf l e t c h e ra n dr e e v e s 【3 f o rs o l v i n gu n c o n s t r a i n e dm i n i - m i z a t i o np r o b l e m s t h ei t e r a t i v ef o r m u l ao ft h ec o n j u g a t eg r a d i e n tm e t h o di sg i v e nb y x k + l2 x k + 反a n d & = x k + l x k ， w h e r e 口i i sas t e p l e n g t hw h i c hi sc o m p u t e db yc a r r y i n go u ts o m el i n es e a r c h ，a n d t h es e a r c hd i r e c t i o nd e f i n e db y 以= 二耋，+ 屏矾书 嚣篓三三 ( 1 1 ) 以i s ( 1 2 ) w h e r e p ki sap a r a m e t e rt h a td e t e r m i n e st h ed i f f e r e n tc o n j u g a t eg r a d i e n tm e t h o d s ，a n d g = v f ( ) i ti sk n o w n t h a t ，s t a r t i n g 、v i t i lt h es e m i n a lp a p e ro ff l e t c h e ra n dr e e v e s 3 】，t h ed o m a i no fa p p l i c a t i o no fc o n ju g a t eg r a d i e n tm e t h o d si se x t e n d e dt on o n l i n e a rp r o b l e m s i n t h e i rp a p e r , t h eu p d a t ep a r a m e t e r 3 k i sg i v e nb y 慨+ ( 1 3 ) w h e r e1 1 i ld e n o t e se u c l i d e a nn o r m f o rn o n q u a d r a t i co b j e c t i v ef u n c t i o n s ，t h ef rm e t h o d h a sg l o b a lc o n v e r g e n c ew h e ne x a c tl i n es e a r c ho ri n e x a c tl i n es e a r c hi su s e d 4 6 】h o w - e v e r , p o w e l l 7 】7 o b s e r v e dt h a ti ns o m ec a s e sj a m m i n go c c u r r e d ，t h a ti s ，t h es e a r c hd i r e c t i o n sd kb e c o m en e a r l yo r t h o g o n a lt ot h eg r a d i e n t g i n19 6 9p o l a ka n dr i b i 6 r e 【8 】a n d p o l y a k 【9 】9g a v eam o d i f i c a t i o no ft h ef l e t c h e r - r e e v e su p d a t ew h i c ha d d r e s s e dt h ej a m m i n gp h e n o m e n o nw h i c hw a sp o i n t e do u tb yp o w e l l 【7 】7 i n19 7 7 1 1 1 e i rc h o i c ef o rt h eu p d a t ep a r _ m e t e rw a s 最y k i g 2 ( 1 4 ) w h e r ey k = g 女“一g 女w h e nj a m m i n go c c u r s ，t h es e a r c hd i r e c t i o ni sn ol o n g e ro r t h o g o n a l t ot h eg r a d i e n t ，b u tb e c a m en e a r l yt h en e g a t i v eg r a d i e n t t h i sb u i l t i nr e s t a r tf e a t u r eo ft h e 心i一2 广西大掌硕士掌位论文( 2 0 0 8 ) 一类修改的共轭梯度法的全局收敛性 p r pm e t h o do f t e ng a v em o r er a p i dc o n v e r g e n c ec o m p a r e dt ot h ef rm e t h o d t h ep a p e ro fh e s t e n e sa n ds t i e f e l 【2 】2 p r e s e n t sac h o i c ef o r 尾c l o s e l yr e l a t e dt ot h e p l 冲s c h e m e ： 蹬= 糍 i np a p e r 【10 ，l i ua n ds t o r e yg a v ea n o t h e rc h o i c ef o r a n dh ss c h e m e ： 烨 ( 1 5 ) c l o s e l yr e l a t e dt ot h ep r p ( 1 6 ) i f 嘶i so b t a i n e db ya ne x a c tl i n es e a r c h ，t h e nu s i n g ( 1 2 ) a n do r t h o g o n a l i t yc o n d i t i o n g ：“d k = 0 。w e w i l lg e t8 ：s = 8 = p ：褂 t h e r ea r eo t h e rw e l l - k n o w n u p d a t ep a r a m e t e r s ，s u c ha st h ec dm e t h o do ff l e t c h e r 【11 】 a n dd ym e t h o do fd a i y u a n 【1 2 t h e yh a v et h eu p d a t ep a r a m e t e r so ft h ef o l l o w i n gf o r m , r e s p e c t i v e l y 矿= 鞋， p o , = i l g 毛, 瓦+ , 1 2 。 ( 1 7 ) ( 1 8 ) r e c e n t l y , s o m ee f f i c i e n tn o n l i n e a rc o n j u g a t eg r a d i e n ta l g o r i t h m si n c l u d et h ec o n j u g a t e d e s c e n ta l g o r i t h mo fd a i l i a o 【13 】a n dt h es c h e m eo fh a g e r - z h a n g 【14 - 1 6 ，a n ds oo n t h es c h e m eo fd a i l i a oa n dh a g e r - z h a n gc o r r e s p o n d st ot h ef o l l o w i n gc h o i c e sf o rt h eu p d a t ep a r a m e t e r ： 舻= 去( 儿一科， 聃卿矾翳厂砺g k + 1 ( 1 9 ) ( 1 1 0 ) w i t he x a c tl i n es e a r c h ，t h em e t h o dr e d u c e st oan o n l i n e a rv e r s i o no ft h eh e s t e n e s s t i e f e l c o n j u g a t eg r a d i e n ts c h e m e a l t h o u g ht h ea b o v em e n t i o n e dc o n j u g a t eg r a d i e n ta l g o r i t h m sa r ee q u i v a l e n tt oe a c h o t h e rf o rm i n i m i z i m zs l r o m zc o n v e xo u a d r a f i cf u n c t i o n su n d e re x a c tl i n es e a r c h t h e vh a v e d i f f e r e n tp e r f o r m a n c ew h e nm i n i m i z en o n - q u a d r a t i cf u n c t i o n so ru n d e r t a k ei n e x a c tl i n e s e a r c h e s f o rn o n - q u a d r a t i co b j e c t i v ef u n c t i o n s ，t h ef rm e t h o dh a sg l o b a lc o n v e r g e n c e 【4 6 】t h ep r pm e t h o dh a sn og l o b a lc o n v e r g e n c eu n d e rs o m et r a d i t i o n a ll i n es e a r c h e s s o m ec o n v e r g e n tv e r s i o n sw e r ep r o p o s e db yu s i n gs o m en e w c o m p l i c a t e d1 i n es e a r c h e so r t h r o u g hr e s t r i c t i n gt h ep a r a m e t e r 展t on o n - n e g a t i v en 眦b e r 17 - 2 2 t h ec dm e t h o d w a sp r o v e dt oh a v eg l o b a lc o n v e r g e n c ep r o p e r t yu n d e rs t r o n gw b l f e p o w e l ll i n es e a r c h 2 广西大学硕士学位论文( 2 0 0 8 )一类修改的共轭梯度法的全局收敛性 谢t has t r o n gr e s t r i c t i o no nt h ep a r a m e t e r s 【2 3 1 d ym e t h o dh a sg l o b a lc o n v e r g e n c ej u s t u n d e rw e a kw b l f e p o w e l ll i n es e a r c h 【1 2 o t h e rr e l a t e da n a l y s i sc a nb es e e ni np a p e r s 【1 0 ， 1 5 ，2 4 3 1 ，e t c 】 g e n e r a l l ys p e a k i n g 【15 ，t h ef r ，d ya n dc dm e t h o d sa l lh a v et h ec o m m o nn u m e r a - t o r i i g t ；l8 2 t h e yh a v es t r o n gc o n v e r g e n c et h e o r y t h o u g h , t h e s em e t h o d sa r e a l ls u s c e p t i b l et oj a m m i n g t h a ti s ，t h e yb e g i nt ot a k es m a l ls t e p sw i t h o u tm a k i n gs i g n i f i c a n tp r o g r e s s t om i n i m u m t h ep r p , h sa n dl sm e t h o d s ，w h i c hs h a r et h ec o m m o nn u m e r a t o rg ；+ ly ， p o s s e s sab u i l t - i nr e s t a r tf e a t u r et h a ta d d r e s s e st h ej a m m i n gp r o b l e m ：w h e nt h es t e pi s s m a l l ，t h ef a c t o ry ki np kt e n d st oz e r o h e n c e ，| b kb e c o m e ss m a l la n dt h en e w s e a r c h d i r e c t i o nd k + lb e c o m e sn e a r l yt h en e g a t i v eg r a d i e n t i ng e n e r a l ，t h en u m e r i c a lp e r f o r m a n c eo ft h e s em e t h o d sa r eb e t t e rt h a nt h ep e r f o r m a n c eo fm e t h o d sw i t hn u m e r a t o ri i g 川 i n 反 a sw eh a v es e e n 【1 5 ，t h ef i r s ts e to fm e t h o d sf 1 ld yc dh a ss t r o n gc o n v e r g e n c e p r o p e r t i e s ，b u tt h e ym a yn o tp e r f o r mw e l li np r a c t i c ed u et oj a m m i n g o nt h eo t h e rh a n d ， t h es e c o n ds e to fm e t h o d sp i 啦h s ，l sm a yn o tc o n v e r g ei ng e n e r a l ，b u tt h e yo f t e np e r - f o r mb e t t e rt h a nt h ef i r s ts e to fm e t h o d si np r a c t i c e s o ，c o m b i n a t i o n so ft h e mh a v eb e e n p r o p o s e dt oe x p l o i ta t t r a c t i v ef e a t u r e so fb o t h v a r i o u sv e r s i o n so fh y b r i dm e t h o da p p e a r i n19 8 4 ，p o w e l l 【4 】4s h o w e dt h a tt h ep r pm e t h o d ，埘t h1 2 o b t a i n e db ya ne x a c tl i n e s e a r c h ，c a nc y c l ei n f i n i t e l y , w i t h o u ta p p r o a c h i n gas t a t i o n a r yp o i n t t oc o p e 晰mp o s s i b l e c o n v e r g e n c ef a i l u r ei nt h ep r ps c h e m e ，p o w e l l 【31 】s u g g e s t e dt h a t 尻b er e p l a c e db y p = m a x 8 r 惑 i no t h e rw o r d s ，w h e nt h e p kg i v e nb yp r p i sn e g a t i v e ，i ti sr e p l a c e db yz e r o i n1 9 9 2 ， g i l b e r ta n dn o c e d a l 18 】p r o v e dg l o b a lc o n v e r g e n c eo ft h i sp r p + s c h e m e o t h e rw a y st o r e s t r i c t 孱i n t h ep i 冲s c h e m ea r ed e v e l o p e di np a p e r s 【3 2 ，3 3 ，e t c 】 m o s tr e c e n t l y , d a i l i a o 13 】a n dh a g e r - z h a n g 【14 - 16 p r o p o s e ds o m en e wc h o i c ef o r t h eh y b r i df o r m ，w h i c hi m p l e m e n t e de f f i c i e n t l yi np r a c t i c e ， w h e r e 玑= 一1 一 爱，o ) r 爱川划， 以 1 m i n r l ，蚓1 ) 彤= m a x ，仇 ， ，7 i sa c o n s t a n t ( 1 1 1 ) ( 1 1 2 ) o n c et h ed e s c e n td i r e c t i o n 巩i sd e t e r m i n e da tt h ekt hi t e r a t i o nw es h o u l ds e e ka s t e ps i z ea l o n gt h ed e s c e n td i r e c t i o na n dc o m p l e t eo n ei t e r a t i o n ，t 1 1 a ti sl i n es e a r c h f o rt h e l i n es e a r c h i tr e q u i r e ss u f f i c i e n ta c c u r a c yt oe n s u r et h a tt h es e a r c hd i r e c t i o n ss a t i s f yd e - s c e n tp r o p e r t i e s 【3 4 t h e r ea r em a n yl i n es e a r c h e st of i n da l la v a i l a b l es t e ps i z e t h ei d e a l l i n es e a r c hr u l ei st h ee x a c to n et h a ts a t i s f i e s f ( x k + 喀) = 咖厂( + 反) ( 1 1 3 ) i nf a c t t h ee x a c ts t e ps i z ei sd i 伍c u l ta n de v e ni m p o s s i b l et os e e ki np r a c t i c a lc o m p u t a t i o n 广西大学硕士掌位论文( 2 0 0 8 ) 一类修改的共轭梯度法的全月收敛性 t h u sm a n yr e s e a r c h e r sc o n s t r u c t e ds o m ei n e x a c tl i n es e a r c hr u l e s ，s u c ha sa r m i j oc o n d i - t i o n s 3 5 ，g o l d s t e i nc o n d i t i o n s 【3 6 ，w e a kw o l f e - p o w e uc o n d i t i o n s 【3 7 ，3 8 ，s t r o n g w o l f e p o w e l lc o n d i t i o n s 【3 7 ，3 8 a n dg e n e r a l i z e dw o l f e - p o w e l lc o n d i t i o n s 【6 】，a n ds oo n t h ew e a kw o l f e p o w e l lc o n d i t i o n s 37 ，38 】a r e ： f ( x k + 喀) 一( ) 8 a , 反以， ( 1 1 4 ) 毹+ 1 吃盯磊矾，( 1 1 5 ) w h e r e0 万 1 7 1 i nt h es t r o n gw o l f e - p o w e l lc o n d i t i o n s ，( 1 15 ) i sr e p l a c e db y f 反+ l 以l 一仃或反 ( 1 1 6 ) m o s tr e c e n t l y , z h a n ga n dh a g e r 14 - 16 】i n t r o d u c e da na p p r o x i m a t ew r o l f ec o n d i t i o n s ： 盯反矾g 斛rl 吨( 2 6 1 ) g ：矾，( 1 1 7 ) w h e r e0 艿 1 2a n d 万 0s u c ht h a t l i g o o l t - m ，垤q s i n c e f ( x i ) i sad e c r e a s i n gs e q u e n c e ，i ti sc l e a r t h a tt h es e q u e n c e ( 以) g e n e r a t e db y a l g o r i t h m2 。1o ra l g o r i t h m2 2 i sc o n t a i n e d 遮q ，a n dt h e r ee x i s t sac o n s t a n tf s u c h t 1 1 a t 1 i m f ( x k ) = 厂 i nt h ef o l l o w i n gs u b s e c t i o n s ，w ew i l ld i s c u s st h eg l o b a lc o n v e r g e n c eo fa l g o r i t h m2 1 a n da l g o r i t h m2 2 2 2c o n v e r g e n c ep r o p e r t i e sf o rs t r o n g l yc o n v e xf u n c t i o n s af u n c t i o nfi ss a i dt ob es t r o n g l yc o n v e xo ns o m es e tsi ft h e r ee x i s t sap o s i t i v e c o n s t a n t s u c ht h a t ( v 厂( x ) 一v 厂( y ) ) r ( x - y ) l l x - y l l 2 ，v x ，y 奄s w en o ww i l ld i s c u s st h eg l o b a lc o n v e r g e n c eo ft h es c h e m e ( 1 2 ) a n d ( 2 i ) f o rs t r o n g l y c o n v e xf u n c t i o n sw i t ht h es t r o n gw o l f e p o w e l lc o n d i t i o n s f i r s t ，w ew i l le s t a b l i s ht h e s e a r c hd i r e c t i o n sg e n e r a t e db