（运筹学与控制论专业论文）求解无约束优化问题新方法的研究.pdf

求解无约束优化问题新方法的研究 摘要 求解无约束优化问题两类有效的方法是：共轭梯度法和拟牛顿法。共轭梯 度法以其迭代简单，存储量低著称。拟牛顿法中最有效的方法是b f g s 方法，它 只需利用目标函数值和一阶导数的信息，而不需要计算h e s s i a n 矩阵。本学位论 文研究了新的共轭梯度算法和新的b f g s t y p e 算法，分别对其相应的收敛性进 行证明，初步的数值结果表明新算法是有效的。 第一章，回顾有关共轭梯度法和拟牛顿法的基本知识及一些著名成果。 第二章，在公式卯忱和卢扩的基础上，提出新公式臃+ ，得到一个新的共 轭梯度算法。该算法在强w b l f e 条件下具有全局收敛性。数值结果表明新算法是 有效的。 第三章，利用一个修改的雕( 弘) 公式，提出另一个新的共轭梯度算法。该 算法搜索方向的充分下降性不依赖于线搜索条件，并证明了新算法在弱w - o l f e 条 件下具有全局收敛性。初步的数值结果表明该算法是有效的。 第四章，根据韦等( 2 0 0 4 ) 提出的新的拟牛顿方程b 七+ 1 s 凫= 皖= 玑+ a 南s 南，其 中a 惫是矩阵，提出新的b f g s t y p e 算法。证明了新算法的全局收敛性及超线 性收敛性。其数值结果表明该算法是有效的。 关键词：无约束优化共轭梯度法拟牛顿法b f g s t y p e 算法全局收 敛性超线性收敛 r e s e a r c ho nn e wm e t h o dsf o rsol 1 v i n g u n co n s t r a i n e d0 p t i m i z a t i o np r o b l e m a bs t r a c t t 、釉c l a s s e so fe h e c t i v em e t h o d sf o rs o l v i n gu 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 ma r e c o n j u g a t e 耵a d i e n tm e t h o d sa n dq u a s i n e w t o nm e t h o d s c o n j u g a 七eg r a d i e n tm e t h o d sa r e f a m o u sf o rt h e i ri n t e r a t i o ns i m p l i c i t ya n d1 0 wm e m o r yr e q u i r e m e n t s f b rq u a s i n e w t o n m e t h o d s ，t h em o s te f k c t i v eo n ei st h eb f g s w i t h o u tf o r m i n gt h eh e s s i a nm a t r i x ，t h e m e t h o do n l yu s et h eo b j e c t i v ef h n c t i o na n di t s 矗r 8 t o r d e rd e r i v a t i v ev a l u e n e wc o n j u g a t e g r a d i e l l ta l g o r i t h m sa n dn e wb f g s t y p ea l g o r i t h 工i 【sa r es t u d i e di nt h i st h e s i s t h e9 1 0 b 出 c o n v e r g e n c eo ft h e s en e wa l g o r i t h m s 盯ep r o v e du n d e rs o m em i l dc o n d i t i o 璐r e s p e c t i v e l y 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 e ya ，r ee m c i e i l t i nc h a p t e r1 ，t h ef o u n d a t i o n a lk n o w l e d g ea n ds o m ef a m o u sr e s e a r c h e sa b o u tc o n j u g a t e g r a d i e n tm e 七h o d sa n dq u a s i n 印汽o nm e t h o d s 缸er e c a n e d i nc h a p t e r2 ，an e wc o l l j u g a t eg r a d i e i l tm e t h o dw i t h 俄+ b a s eo np ? l 2a n d 镤+ i s p r o p o s e d t h e nt h eg l o b a lc o l l _ v e r g e n c ef o rt h i sm e t h o di sp r o v e du n d e rt h es t r o n gw b l 俗 p o w e l lc o n d i t i o n s t h en u m e r i c a lr e s u l t ss h o wt h a tt h en e wo gm e t h o di se 伍c i e n t i nc h a p t e r3 ，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 dw i 七ham o d i f l e d 硝( 肛) m e t h o d i sp r o p o s e d ，w h i c hc a ne n s u r et h es u m c i e n td e s c e n tc o n d i t i o ni n d e p e n d e n to fl i n es e a r c h a n di t s9 1 0 b a lc o n v e r g e n c ei sp r o v e dw i t ht h e ，e a kw b l f 巨p o w 它uc o n d i t i o n s p r e l i m i n a r y n u m e r i c a lr e s u l 七ss h o wt h a ti t i se m c i e n t i nc h a p t e r4 ，b a s e do nt h en e wq u a s i n e w t o ne q u a t i o nb 凫+ 1 s 忌= 坑= 纨+ 4 忌s 血， w h e r ea 凫i ss o m em a t r i xp r o p o s e db yw 西，e ta 1 ( 2 0 0 4 ) ，n e wb f g s t y p ea l g o r i t h m sa r e p r o p o s e d t h e nt h e i rg l o b a le o n v e r g e n e ea n ds u p e r l i n e a rc o n v e r g e n c ep r o p e r t i e sa r ep r o v e d n u m e r i c a le x p e r i m e n t sh a v eb e e ng i v e nt o8 h o wt h a tt h e ya r ee 伍c i e n t k e yw o r d s ：u n c o l l 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 酽a d i e n tm e t h o d ；q u a l s i n e w t o n m e 七h o d ；b f g s t y p ea l g o r i t h m ；g l o b a lc 0 1 w e r g e n c e ；s u p e r l i n e 甜c o n v e r g e n c e 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果 和相关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经 发表过的研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的 研究工作提供过重要帮助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：套彦蜿沁咿多年 z 月么日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时阅： d 即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：李彦允形导师签名镛妖加p 年6 月石日 c h a p e r1 i n t r o d u c t i o n 1 1c o n j u g a t eg r a d i e n 七m e t h o d s n o n l i n e a rc o n j u g a t eg r a d i e n t ( c g ) m e t h o d sa r e w e l ls u i t e df o rs o l v i n gl 缸g e - s c a l ep r o b l e m jd u et ot h ei t e r a t i o ns i m p l i c i t ya n dl o wm e m o r yr e q u i r e m e n t s t h en o n l i n e a rc o n j u g a t e 酎a d i e n tm e t h o di sd e s i g n e dt os o l v et h ef o l l o 丽n gu 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 m t 礼 ，( z ) lz 舻) ， ( 1 1 ) w h e r e 厂：尼1 一ri sas m o o t h ，n o n h n e a rf u n c t i o n t h e i t e r a t i v ef o r i n u l ao ft h ec o n j u g a t e g r a d i e n tm e t h o d si sg i v e nb y z 缸+ l2z 后+ a 忌d _ | c o n ds 南= q _ j c d 惫，( 1 2 ) w h e r eq 七i sas t e p l e n 勘hw h i 出i se o m p u t e db yc 缸r y i n go u ta l i n es e a r c h ，a n d 毗i st h e s e a r e hd i r e c t i o nd e f l n e db y w h e r e 风i sas c a l a r ， 以：工 【 一鲰 t ，恐= 1 ， 一夕七+ 风d 后一l 玎惫2 ， a n d9 后= v ，( z 知) w 色d i s p l a ys o m ef o r m u l a sf o r 凤a sf o l l o w 8 ： 酽= 器( 胁s q 龇刷 舻= 磐( 融胁坷俐e s 2 m 矿k 淼( p 0 2 如r 0 6 衙e _ p 咖州3 4 】) ； 蘼。一牿( c 。咖以e 珧s c e 毗 牡一器 = 嚣 ( i u s 舌o r e 可 ( d n t y u o 仡 矿一a x 糕j 0 “器 ”七一1 y _ i c l “& 一l 占拧一1 伽叫蔑j 0 ) 一t 糕 6 ) ； 【7 】) ； ， o ) ( d o i l i o o 8 】) ； ， o ) ( l i t n 礼夕一w e i 【9 】) ； ( 1 3 ) ( 1 4 ) ( 1 5 ) ( 1 6 ) ( 1 。7 ) ( 1 8 ) ( 1 9 ) ( 1 1 0 ) ( 1 1 1 ) l 吼i f 2 一 肛l 夕蚕九一11 0 臃鲰一1 i + l i 鲰一1 1 1 2 训椰鼢一1 i ，( y u z 危n 。一w e t 10 】) ( 1 1 2 ) d 亡九e r 叫i s e 成：兰一。彬。一y。一l；乱。11。， 吼一厩习广勖叫一m 乱叫j ， ( 1 1 3 ) w h e r ej l j j p ? o t 嬖、如一n o r m ，亡i ss o m ep o s i t i v ec o n s t a n t ，纨一1 = 鲰一鲰一1a n d 缆一l = 蜘+ 背s m ，w h e r e 虬。- 2 m ) 叫训删圳训加惫一：1 w e r e g a r dt h ec gm e t h o d sc o r r e s p o n d i n gt o 卯加，缳+ ，硝，a n d 俄a s 卯l 2m e t h o d ，俄+ m e t h o d ， p m e t h o da n d 镤m e t h o dr e s p e c t i v e l y ：t h ep r o p e r t i e so ft h ea b o v ec gm e t h 。d sh a eb e e n s t u d i e db ym a n yr e 8 e a r c h e r sf o rm a n y ”a r s ( e g i 1 h 3 6 ) n e x t ，w ew i l lg i v e 七w di m p o r t a n tp r o p e r t 砖w h i c l lh a so 托e nb e e nu s e di nt h e1 i t e r a t u r e t oa n a l y z et h eg l o b a lc o n v e r g e n c eo fc o n j u g a t eg r a d i e n 七m e t h o d sw i t hi n e x a c t1 i n es e a r c h e s ( s e e 3 2 ，3 3 ，3 4 ，3 6 】) v 娓s a yt h ed e s c e i l tc o n d i t i o nh o l d si fe a c h8 e a r e hd i r e c t i o nd 七s a 七i s f i e s 9 吾毗 0s u c ht h a t ，f o re a c h8 e a r c hd i r e c t i o n 以， 9 吾也一c | i 夕七| 1 2 ， v 七1 t h ef o l l o w i n g1 i n es e a r c h e sa r eo 代e nu s e dt oa n a l y 8 et h eg l o b a lc o i e r g e n c e ： t h ew e a kw o l f e p o w e l l ( w w p ) l i n es e a r c hi st of i n dq s a t i s 匆i n g 厂( z 知+ 口凫以) 一，( z 凫) 6 口惫9 吾d 膏， 夕( + a j c 毗) 丁毗仃夕吾毗， w h e r e0 6 0 a n dt h eg l o b a lc o n v e r g e n c er e s u l tf 6 rt h en e wc gm e t h o di se s t a b l i s h e dw i t ht h e w w pc o n d i t i o n s t h ep r e l i m i n a r yn u m e r i c a lr e s u l t sa r ec o n t a i n e d 1 2q u a s i _ n e w t o nm e t h o d s s e v e r a lr e c e n te o m p u t a t i o n a ls t u d i e sh a 鹏s h o w nt h a tt h eq u a s i n e w t o nm e t h o d sa r e e 矗e c t i v em e t h o d sf o rs o l v i n gt h 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 ) a sw ea uk n o w ， b a s e do nt h es e c o n do r d e rt 蚵l o rs e r i e sa p p r o 妇m a t i o n ，n e w t o nm e t h o di i o l v e sc o m p u t 跏 t i o no ft h eh e s s i a nm a t r i xo fs e c o n do r d e rd e r i v a 七i v e sa te a c hi t e r a t i o n i nd r a c t i c ei ti so 允e n p r e f e r r e dt oa p p r o x i m a t et h eh e s s i a nm a t r i x ( o rs o m e t i m e si t si i e r s e ) w i t has y m m e t r i c p o s i t i v ed e f i n i t em a t r i x 七h r o u g hs o m ee 矗e c t i v ep r c e d u r ei n s t e a do fi t se x a c tc o m p u t a t i o n t h i si d e ao fa p p r 0 ) ( i m a 七i n gt h eh e s s i a nw i t has w n m e t r i cp o s i t i v ed e f i n i t em a t r i ) ( w a u s 矗r s t i n t r o d u c e db vd a v i d o nf 37 1 t h ec l a s so fm e t h o d st h a ta p p r o x i m a t e sn e w t o nm e t h o db y u t i l i z i n gs o m es y m m e t r i cp o s i t i v ed e n i t ea p p r 0 x i m a t i o no ft h eh e s s i a no rt h ei n v e r s eh e s s i a ni n s t e a do ft h ec o r r e s p o n d i n ge x a c tv a l u ei st e r m e da sq u a s i n e w t o nm e t h o d s l e tu s 3 广西大学硕士学位论文( 2 0 0 8 ) 求解无约束优化问题新方法的研究 d e n o t ea na p p r o x i m a t i o nt ot h eh e s s i a na tt h e 尼t hi t e r a t i o nb yb 凫i th a sb e e ns h o w nt h a t t h eb f g sm e t h o di st h em o s te 髓c t i v eo ft h eq u a s i n e 毗o nm e t h o d s 行o mt h ec o m p u t a t i o n p o i n to fv i e w t h ec o n 、，e r g e n c ep r o p e r t i e so ft h eb f g sm e t h o d f o rc o i e xm i l l i m i z a t i o nh a e b e e ns t u d i e db ym a n yr e s e a r c h e r s - f o re x 锄p l e 2 0 】一【2 3 】i ti sn o wk n o w nt h a tt h eb f g s m e t h o dm a yf a i lf o rn o n c o n v e xf u n c 七i o n s 2 4 】h e n c e ，g r e a te 珏o r t sh a v eb e e nm a d et of i n da q u a s i - n e w t o nm e t h o dt h a tn o to n l yp o s s e s s e sg l o b a lc o r l v e r g e n c eb u ta l s oi ss u p e r i o rt ot h e b f g sm e t h o df r o mt h en u m e r i c a lp e r f o r m a n c ep o i n to fv i e w ( s e ea l s o ，e - g ， 2 5 】 3 1 】， 3 8 】) t h eo r i g i n a lq u a s i n e w t o ne q u a t i o ni sb 七十1 s 惫= 弧，w h e r e 弧= 鲰+ l 一鲰w r e i ，l ia n dq i 3 8 】p r o p o s e da n e wq u a s i n e w t o ne q u a t i o n 上丸+ 1 & = 城，w h e r e 碱= 鲰+ a k s ，a 七i ss o m e i t l a 。t r i x h e r e ，w ep r e s e l l ts e v e r a l r e l lk n o w nu p d a t e so fb 惫： t h e ，e l l k n ( 舢b f g sf o r i n u l a ( 3 9 】i sd e f i n e db y 艮= 风一鬻+ 舞 i h eb f 、g s 一1 上yp ef o r h m l a 【4 0 ji sd e t i n e db y z = 鼠一鬻+ 筹， w h e r e 城2 弧+ 也( 3 ) s 惫a n da ( 3 ) 2 赫j ， 毋昆：2 ( 氏一。厶+ 】) + ( g 知+ 】+ 舭) t s 靶 a n da n o t h e rb f g s t y p ef o r m u l a 3 8 】i sd e 丘n e df o rg e n e r a lf 、l c t i o n ，b y ： 一卜鬻+ 筹咄 l 鼠i 厂忌岩k ， w h e r et h ei n d e xs e tk i sd e 丘n e db y k= 0s u ( 血t h a t z l l b ，比q ( 2 2 ) a s s u m p t i o nb ：i ns o m en e i g h b o r h o o d o fq ，厂i sc o n t i n u o u s l yd i 丑电r e n t i a b l e ，a n di t s 酽a d i e n ti sl i p s c h i t zc o n t i n u o u s ，n a m e i y ，t h e r ee x i s t sac o n s t a n t 己 0s u c ht h a t g ( z ) 一9 ( 可) l i lj | z 一| | ，v z ， u n d e rt h ea b o v ea s s 眦p t i o n so n ，t h e r ee ) 【i s t sac o n s t a n t ，y 0s u c ht h a t 2 2c o m ，e r g e n c ea n a l y s i s o ( z ) i i 7 ，v z q g l 山| l ， v z a 5 ( 2 3 ) ，n 、 k 厶吐， 广西大学硕士学位论文( 2 0 0 8 ) 求解无约束优化问题新方法的研究 i nt h i 8s e c t i o n ，w ed 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 e 成+ m e t h o df o rg e n e r a lf u n c t i o l l s 2 2 1g e n e r a lc o 玎r g e n c er e s u l t z o u t e n d i j k 【4 1 】a n dw b l f e 【4 2 ，4 3 】h a - v ee s t a b l i s h e dt h ef o l l o w i n gl e m m a 2 1a n dl e m m a 2 2w h i c ha r eu s e df o ra n yc gm e t h o dw i t ht h es w pl i n es e a r c h t h ed e t a i l e dp r o o f sh a v e b e e ng i v e ni n 4 1 ，4 2 ，4 3 】 l e m m a2 1l e t 口惫b eo b t a i n e db yt h es w pl i n es e a r c h s u p p o s et h a ta s s u m p t i o i l s a ，ba n d 七h ed e s c e n tc o n d i t i o n ( 1 1 4 ) h o l d t h e nw eh a e ( 一q 七夕融) o 。 七= 1 ( 2 5 ) l e m m a2 2c o n s i d e rt h ec gm e t h o do ft h ef o r m ( 1 2 ) 一( 1 3 ) ，w h e r eq 七i so b t a i n e db y t h es w p1 i n es e a r c h s u p p o s et h a ta 8 s u m p t i o 璐a ，ba n dt h ed e s c e n tc o n d i t i o n ( 1 1 4 ) h o l d t h e nt h ef 0 1 1 0 w i n gs o - c a l l e dz o u t e n d i j kc o n d i t i o nh o l d s ： 壹饼 慨 台恻1 2 、。一 n o mt h ea b o v e1 e m m a sw ec a nh a v et h ef o l l o w i n gl e m m a ( 2 6 ) l e m m a2 3c o n s i d e rt h ec gm e t h o do ft h ef o r m ( 1 2 ) 一( 1 3 ) ，w h e r e 口七i so b t a i n e db y t h es w pl i n es e a r c h s u p p o s et h a ta s s u m p t i o n sa ，ba n dt h ed e s c e n te o n d i t i o n ( 1 1 4 ) h o l d t h e ne i t h e r l 啦i n 圳蚓i = o ，c 。 o r 喜雠 l = 2 2 2c o n 、伧r g e n c ea i l a l y s i sf o rg e n e r a lf u n c t i o n s i nt h i ss u b s e c 七i o n ，w ea n a l y s et h eg l o b a l f u n c t i o n s n a ，w ep r o v et h a ，td 七s a t i s f i e st h e 6 ( 2 7 ) ( 2 8 ) ( 1 2 ) 一( 1 3 ) ，w h e r eq _ i 。i so b t a i n e d a n dt h ed e s c e n tc o n d i t i o n ( 1 1 4 ) ( 2 9 ) c o m r e r g e n c eo ft h en e wm e t h o df o rg e n e r a l s u m c i e n td e s c e n tp r o p e r t y ( 1 1 5 ) 赢 广西大学硕士学位论文( 2 0 0 8 )求解无约束优化问题新方法的研究 l e m m a2 4s u p p o s et h a tt h ei t e r a t i o na n dt h e 出r e c t i o n 甜eg e n e r a t e db y ( 1 2 ) a n d ( 1 3 ) r e s p e c t i v e l y ，w h e r e 觑i sc a l c u l a t e db y ( 2 1 ) a n d 口南i so b t a i n e db yt h es w pl i n es e a r c h ( 1 1 6 ) a n d ( 1 1 8 ) ，t h e n ，以s a t i s f i e st h es u 伍c i e n td e s c e n tp r o p e r t y ( 1 1 5 ) f o ra l l 七 p r o o f u s i n g ( 1 2 ) ，( 1 3 ) a n d ( 2 1 ) ，、eh a e 睫d k i | 鲰1 1 2 靠0 一g k +玩一鹅夕m ) 咱k 鲰一1 1 1 2 毗一1 ) 蚓1 2 1 + 淼c 1 一蒜南一气铲， g + 淼c l 一确南卜 n o m ( 1 1 8 ) a n dc a u e h y s c h w a r zi n e q u a l i t y ) t h ea b o v ei n e q u a l i t yg i v e s 赫g + 眷恢1 1 2 。：i 一，1 1 2 r ，e p e a t i n gi t ，、v eh a et h ef o l l o w i n gr e s u l t l e t t i n gc = 1 + 2 口 赫扣广谗= 一1 1 + 2 盯