（应用数学专业论文）修改的bfgs方法及sqp方法的研究.pdf

修改的b f g s 方法及s q p 方法的研究 摘要 b f g s 方法是求解无约束优化问题的著名的拟牛顿方法它只需利用目 标函数值和一阶导数的信息，而不需要计算h e s s i a n 矩阵，且具有收敛速度快 和数值结果好等优点近年来，许多学者给出了不同的修改的b f g s 方法， 如f u k u s h i m a , 祁力群，李董辉，韦增欣等 著名的序列二次规划方法，简称s q p 方法，是求解非线性约束优化问题 的一类非常重要的方法该方法最早由w i l s o n ( 1 9 6 3 ) 提出，但直到2 0 世纪7 0 年代中期才引起人们的重视并得到发展其中，韩世平和p o w e l l 的工作非常重 要，因此，又称s q p 方法为w i l s o n - h a n - p o w e l l 方法它在每次迭代中用一修 正的矩阵b k 代替w ( x k ，k ) 近年来，该方法有较好的发展趋势，p o w e l l 【2 5 】 提出b f g s n e w t o n - s q p 方法用来求解非线性约束优化问题。孙文瑜【2 7 1 给出 了求解半光滑约束优化问题的q u a s i - n e w t o n - s q p 型方法及其全局收敛和超 线性收敛的充分必要条件，但是并没有证明修改的b f g s q u a s i - n e w t o n - s q p 型方法是否满足条件 本文是在韦增欣等【1 】研究的基础上，给出一个新的m b f g s 算法，并证明 该算法在无线搜索条件下的全局收敛性和超线性收敛性另外，受到孙文瑜的 启发，本文构造出求解约束优化问题的一种新方法( m b f g s q u a s i - n e w t o n s q p 方法) 。并在适当的条件下证明此算法的超线性收敛性 关键词：b f g s 方法s q p 方法m b f g s s q p 方法全局收敛超 线性收敛 r e s e a r c ho nam o d i f i e db f g s m e t h o da n d s q pm e t h o d a b s t r a c t t h eb f g sm e t h o di saw e l l - k n o w nq u a s i - n e w t o nm e t h o df o rs o l v i n gu n c o n s t a i n e d o p t i m i z a t i o n t h em e t h o do n l yu s et h ev a l u eo fo b j e c t i v ef u n c t i o na n d i t sf i r s t o r d e r d e r i v a t i v ew i t h o u tc o m p u t i n gh e s s i a nm a t r i x ，m o r e o v e r ，t h em e t h o dp o s s e s s e st h ea d - v a n t a g eo ff a s tc o n v e n g e n c er a t ea n dg o o dn u m e r i c a lr e s u l t s ，a n db oo n r e c e n t l y , m a n y a u t h o r sp r o p o s e dd i f f e r e n tm o d i f i e db f g sm e t h o d s ，s u c h 醒，f u k u s h i m a ，l q i ，d l i ，z w 西e t c t h es e q u e n c eq u a d r a t i cp r o g r a m m i n gm e t h o d ，i e ，s q pm e t h o d ，i saw e l l - k n o w n m e t h o df o rs o l v i n gc o n s t r a i n e do p t i m i z a t i o mt h i sm e t h o dw a sp r o p o s e db yw i l s o n ( 1 9 6 3 ) 。 b u tt i l l1 9 7 0 si tw a sd e v e l o p e d h a na n dp o w e l ld i do n eo ft h em o s ti m p o r t a n tw o r k s f o rt h i sm e t h o d - t h e r e f o r e ，s q pm e t h o dw a sc a l l e dw i l s u n - h a n - p o w e um e t h o d a ti t s i t e r a t i o n ，w et t f l e 风t or e p l a c ew ( x k ，a ) r e c e n t l y , t h i sm e t h o d h a sb e e ni nv o g u e p o w - e l l 2 5 1p r o p o s e db f g s - n e w t o n - s q pm e t h o df o rn o n l i n e a r l yc o n s t r a i n e do p t i m i z a t i o n s w s u n 2 7 1g a v eq u a s i - n e w t o n - s q pm e t h o df o rg e n e r a ll c lc o n s t r a i n e do p t i m i z a t i o n p r o b l e m s a n dh eg a v et h el o c a l l ya n ds u p e r f i n e a r l yc o n v e r g e n ts u f f i c i e n tc o n d i t i o n s b u th ed i 血tp r o v ew h e t h e rt h em o d i f i e db f g s - q u a s i - n e w t o n - s q pm e t h o ds a t i s f i e st h e s n l f i c i e n tc o n d i t i o n so rn o t i nt h i st h e s i s ，w ep r o p o s ean e wm b f g sa l g o r i t h mf o rn o n l i n e a r l yu n c o n s t r a i n e d o p t i m i z a t i o n sw h i c hb a s e do nt h es t u d yo fz w e i ，e t a l 【1 】w ee s t a b l i s hi t 8g l o b a l a n ds u p e r l i n e a rc o n v e r g e n c ew i t h o u tl i n es e a r c h e s e n l i g h t e nb yw s u n 【2 7 】，w eg i v ea n e w m e t h o d ( i e ，m b f g s + 一q u a s i - n e w t o n - s q pm e t h o d ) a n de s t a b l i s hi t 8s u p e r l i n e a r c o n v e r g e n c eu n d e rs u i t a b l ec o n d i t i o n s k e yw o r d s b f g sm e t h o d ；s q pm e t h o d ；m b f g s * - s q pm e t h o d ；g l o b a lc o n - v e r g e n c e ；s u p e r l i n e a rc o n v e r g e n c e 苎叁兰翌主兰竺丝查垡里丝2 一! ：竺! 兰坠堑兰望二垒查圣堑竺二兰童墼竺! ! ! ：1 c h a p t e r1q u a s i - n e w t o nm e t h o d s 1 1i n t r o d u c t i o n d a v i d o n ，t h ea m e r i c a np h y s i c i s t ，p r o p o s e dt h ef i r s tq u a s i - n e w t o nm e t h o di n1 9 5 0 s b e - f o r el o n g ，t h em e t h o dw a sp r o v e dt ob ef a s t e ra n dm o r es t e a d yt h a nt h ee x i s t i n gm e t h o d p r o p o s e db yf l e t c h e ra n dp o w e l l 2 0y e a r sl a t e r ，t h eq u a s i - n e w t o nm e t h o d sb e c a m et h e f o c u si nt h es t u d yo ft h en o n l i n e a rp r o g r a m m i n g t h eq u a s i - n e w t o nm e t h o d sa st h es t e e p - e s td e s c e n tm e t h o do n l yr e q u r et h eo b j e c t i v ef u n e t i o na n di t sg r a d i e n ta te a c hi t e r a t i o n ， b u ti t sc o n v e r g e n c er a t ei sf a s t e rt h a nt h es t e e p e s td e s c e n tm e t h o d w i t h o u tc o m p u t - i n gt h eh e s s i a nm e t r i x ，8 0t h eq u a s i - n e w t o nm e t h o d sa r em o r ee f f e c t i v et h a nn e w t o n m e t h o d s 1 2 q u a s i - n e w t o nc o n d i t i o n s t h eq u a s i - n e w t o nm e t h o d so n l yu s et h eo b j e c t i o nfa n di t sf i r s t - o r d e rd e r i v a t i v et of o r m t h ec u r v a t u r ea p p r o x i m a t i o no ft h eo b j e c t i v ew i t h o u tf o r m i n gh e s s i a nm a t r i x ，m o r e o v e r ， t h em e t h o d sp o s s e s st h ea d v a n t a g eo ff a s tc o n v e r g e n c er a t ea n dg o o dn u m e r i c a lr e s u l t s i nt h ef o l l o w i n gt h e s i s ，w ew i l la n a l y s eh o wt of o r mt h ea p p r o x i m a t em a t r i xa n dh o wt o u s et h ef o r m e da p p r o x i m a t em a t r i xt or e p l a c e dt h ei n v e r s eo ft h eh e s s i a nm a t r i xi nt h e q u a s i - n e w t o nm e t h o d 8 l e tf ：j p _ rb et w i c ec o n t i n u o u s l yd i f f e r e n t i a b l eo nt h eo p e ns e tdcj p ，g ( z ) a n dg ( z ) b et h ef i r s t - o r d e ra n dt h es e c o n d - o r d e rd e r i w t i v eo f ，a tz ，r e s p e c t i v e l y t h e n e w t o ni t e r a t i v ef o r m u l ai s o 七+ 1 = z _ + o i d k ， w h e r ed ki st h en e w t o nd i r e c t i o na to a n d d k = 一g ( z 女) 一1 9 ( $ i ) ，( 1 1 ) o ii st h eo p t i m a ls t e p s i z ew h i c hi ss e l e c t e da l o n gt h en e w t o n 8d i r e c t i o nf r o mz k i n o r d e rt of o r mt h ea p p r o x i m a t em a t r i x 凰o fg ( z 詹) ，w ef i r s t l ya n a l y s et h er e l a t i o n s h i p b e t w e e ng ( ) 一a n dt h ef i r s t - o r d e rd e r i v a t i v eo ft h eo b j e c t i o n l e tw eg e t 。t + 1a tt h e 舰hi t e r a t i o n b yu s i n gt h et a y l o rs e r i e se x p a n s i o no ft h e o b j e c t i v ef ( x ) a tx k + 1a n du s i n gi t st w i c e - o r d e ra p p r o x i m a t i o n ，w eh a v e ，( 卫) ，( 句1 ) + g ( 善膏+ 1 ) t 0 一$ 膏+ 1 ) + ； - - x k + 1 ) t a ( x , + 1 ) c z x k + 1 ) ， ( 1 2 ) b yd e r i v i n gt h et w os i d e so ft h ea b o v ef o r m u l a , w eg e t g ( x ) 2g ( z k + 1 ) + g ( 霉k + 1 ) ( z x k w l ) ( 1 3 ) l e tz = x k ，8 知= z + 1 一z i ，y k = g k + l g k ，骶h a v e g 暑1 抓“， ( 1 4 ) t h ea b o v er e l a t i o n ( 1 4 ) i se x a c t l yt r u ef o rt h et w i c ef u n c t i o n n o w ，w er e q u i r et h ei n v e r s e a p p r o x i m a t i o n 王如+ 1o ft h ef o r m e dh e s s i a n s a t i s f i e st h i sr e l a t i o n ，i e ， 王k + l 玑= 乳， ( 1 5 ) w eo f t e nc a l lt h ea b o v er e l a t i o n ( 1 5 ) 衄t h eq u a s i - n e w t o nc o n d i t i o n so rt h eq u a s i - n e w t o n e q u a t i o n w ec a ng e tt h eq u a s i - n e w t o nc o n d i t i o n sb yt h ef o l l o w i n gm e t h o d s i n c et h eg r a d i e n tgi sc o n t i n u o u sa t 。“l ，s ot h e r ee x i s t s6 0 ，s u c ht h a t i f i l $ 一巩+ 1 1 i 0 l e t = 瓤，b k + 1b et h ea p p r o x i m a t i o no fg 奄+ l ，w er e q u i r e 风+ l 靠= 批，( 1 7 ) i sr e a s o n a b l e ，w h e r e 靠= $ l 一，玑= g k + l 一鲰( 1 7 ) i st h es a l i n ea s ( 1 5 ) ( 1 5 ) i s t h eq u a s i - n e w t o nc o n d i t i o n sa b o u tt h ei n v e r s ea p p r o x i m a t i o no fh e s s i a n ，w h i l e ( 1 7 ) i s t h eq u a s i - n e w t o nc o n d i t i o n sa b o u tt h ea p p r o x i m a t i o no fh e s s i a n ，w h e r eb 矗12 凰+ 1 g e n e r a lq u a s i - n e w t o nm e t h o d ( g q n m ) s t e p0 c h o o s ea ni n i t i a lp o i n tx l 舻a n das y m m e t r i cp o s i t i v ed e f i n i t em a t r i xb 1 l e t 0 b e g i v e na n d8 e tk = 1 s t e p1 i ft h eg r a d i e n tg ( 。t ) s a t i s f i e sf i g ( z k ) l l et h e ns t o p s t e p2 c o m p u t et h es e a r c hd i r e c t i o n 血b ys o l v i n gt h ef o l l o w i n gl i n e a re q u a t i o n 凤以+ 鲰= 0 ( 1 8 ) s t e p s s e a r c ha l o n gt h ed i r e c t i o n 以t of i n das t e ps i z e 口 a n ds e t z 1 = 孤+ 鲰也( 1 9 ) 广西大学硕士学位论文( 2 0 0 6 年)修改的b f g s 方法及s q p 方法的研究 3 s t e p 4 s e l e c taf l e ws y m m e t r i cp o s i t i v ed e f i n i t em a t r i xb k + 1w h i c hs a t i s f i e st h ef o l l o w i n g o r i g i n a lq u a s i - n e w t o ne q u a t i o n ( 1 7 ) s t e p 5 s e t 后= 后+ 1a n dg ot os t e p1 1 3b f g sm e t h o d b f g sm e t h o dw h i c hw 鹬p r o p o s e db yb r o y d e n ，f l e t c h e r ，g o l d f a r ba n ds h a n n ow a so n eo f t h em o s te f f e c t i v eq u a s i - n e w t o nm e t h o d sf o ru n c o n s t r i a i n e do p t i m i z a t i o n i t sc o n v e r g e n c e p r o p e r t yw a sa n a l y s e di n 【1 6 ，1 7 ，1 8 ，1 9 w ec a l ls e et h ed e d u c t i v ep r o c e s so ft h eb f g s m e t h o da sf o l l o w s l e tt h es y m m e t r i c - r a n k - 2 ( s r 2 ) b e 取+ 1 = b h + a u u t + b y 矿， s u p p o s et h eq u a s i - n e w t o nc o n d i t i o n s 【1 7 ) i sc o r r e c t ，t h e n 玩+ 1 s b ；玩巩+ a u u t 8 + b v v = y k ， w h e r et a n dt ，i sn o to n l yd e t e r m i n e d b u tt h eo b v i o n sc h o o s i n go ft a n d 口i s t = 玑，t = j 孔轧， s oa u t 船2 1 ，b y r 乳2 1 ，d e t e r m i n i n g 口；帮= 蠢，6 = 一再= 一可r 百1 面，t h e n “ = 鼠+ 缫s l , 一警l ，k s k ( 1 1 0 ) 弧 5 t b yu s i n gt h es h e r m a n - m o r r i s o nf o r m u l a 3 4 】o ft h ei n v e r s es y m m e t r i c - r a n k - i ( s r i ) f o r t h es e c o n dt i m e w eg e tb f g sr e c t i f i c a t i o no n 风： w h u + - e s = 凰”+ 訾) 蓑一丝型s t y k 监 = 巩+ 坠型鼍掣一铲乳8 i 鲰t s 讥) 。 。 = ( z - 薏t ) 风( ，一咝8 t y 。、+ 磊s k s r ( 1 1 1 ) t h ea b o v ei m p o r t a n tf o r m u l aw i l t sg i v e nb yb r o y d e n ，f l e t c h e r ，g o l d f a ra n ds h a n n oi n 1 9 7 0 t h eb f g sm e t h o dc 觚f o r m a l l yb ew r i t t e na s ： b f g 8m e t h o d s t e po c h o o s e i n i t i a lp o i n t 甸舻a n d8s y m m e t r i cp 0 6 i t i v ed e f i n i t em a t r i x 蜀l e t 0 b eg i v e na n ds e t 南= 1 s t e p1 i ft h eg r a d i e n tg ( x k ) s a t i s f i e sf l g ( x k ) l i et h e ns t o p s t e p2 c o m p u t et h es e a r c hd i r e c t i o nd kb ys o l v i n gt h ef o u o w i n gf i n e a re q u a t i o n 风以+ g k = 0 ( 1 1 2 ) s t e p 3 s e a r c ha l o n gt h ed i r e c t i o nd kt of i n das t e ps i z e 讯a n ds e t z t + l = $ k + o k d k ( 1 1 3 ) s t e p 4 u p d a t eb k + lb yf o r m u l a ( 1 8 ) s t e p 5 s e tk = k + 1 a n dg o t os t e p l b f g sr e c t i f i c a t i o ni st h eb e s tq u a s i - n e w t o nf o r m u l a i th a sm a n yb e t t e rp r o p e r t i e s ： 1 w h e nt h eo b j e c t i v ef u n c t i o ni st w i c e ( c h o o s i n gt h em i n i m i z a t i o ns t e p s i z er u l e ) ( 1 ) t h et w i c ee n d i n gp r o p e r t y ( w h e nt h eo b j e c t i v ei st h et w i c eh m c t i o n ，t h ea l g o r i t h mi s e n dw i t hf i n i t es t e p s ) ，i e ，三k = g - 1 ； ( 2 ) t h eh e r e d i t yp r o p e r t y , i e ，凰聊= 即，j o ； ( 2 ) t h em e t h o dh a st h es u p e r l i n e a r l yc o n v e r g e n ts p e e d ； ( 3 ) c h o o s i n gt h em i n i m i z a t i o ns t e p s i z er u l e ，w h e nt h eo b j e c t i v ef u n c t i o ni sc o n v e x ，t h e m e t h o dh a st h eg l o b a lc o n v e r g e n c e t h ep r o o fo ft h ea b o v ep r o p e r t i e sc 眦b es e ei n 3 4 1 ( s e c t i o no n e ，c h a p t e r 五v e ) 1 4m o d i f i e db f g sm e t h o d s r e c e n t l y , t h e r ea r em a n ym o d i f i e db f g sm e t h o di n 【1 l 1 2 1 “2 0 】一 2 2 】t os o l v et h eo p t i - m i z a t i o na n dm a n yr e s u l t sw e r eg o t a ni m p o r t a n tf a c t o ri nt h eu s eo ft h em e t h o d si s t h eu p c h t t e df o r m u l at h a tc a nd e r i v eam a t r i xz k + lf r o mt h ec u r r e n tm a t r i xb kb yu s i n g t h ei n f o r m a t i o na v a i l a b l ea tt h ek t hi t e r a t i o n h e r e ，w ef i r s t l ys t a t es e v e r a lw e l lk n o w n u p d a t e so f 玩w h i c hs a t i s f yt h eo r d i n a r yq u a s i - n e w t o ne q u a t i o n ： t h ew e l l - k n o w nb r o y d e n - f l e t c h e r - g o l d f a r b - s h a n n o ( b f g s ) f o r m u l ad e f i n e db y = 风+ 舞一警 ( 1 4 ) 苎查兰塑主兰堡丝圭丝塑! 2竺垄竺! 塑璺查墨墨兰! 鲨查墨塑竺垄 5 a ni m p l e m e n t a t i o no fg q n m u s i n gt h eb f g su p d a t ew i l lb ec a l l e da 7 b f g sm e t h o d ” t h ed a v i d o n - f l e t c h e r - p o w e l l ( d f p ) f o r m u l ai sd e f i n e db y = 鼠( 1 + 兰辔) 舞一y k s r b 矿+ b k s k y t ( 1 1 5 ) t h ea p p r o x i m a t eh e s s i a no ft h es o - c a l l e db r o y d e nc l a s si sd e f i n e db yt h ef o r m u l a b k + l = 仇+ 糍一警圳驰砌碱 ( 1 1 6 ) w h e r e 峨2 最一蕊b k s k ( 1 1 7 ) 3 i 讹8 i 廿s t a n d 机i sas c a l a rp a r a m e t e r n o t et h a tt h eb f g sa n dd f pf o r m u l ac o r r e s p o n dt ot h e c h o i c e so f 西k = 0a n d 西= 1 i nt h ef o l l o w i n gs e c t i o n ，w ew i l ls t a t et h em o d i f i e db f g sm e t h o d s r e c e n t l y , t h ea u t h o r s 2 2 1 一【2 3 】p r o p o s e dt h r e en e wt y p e so fl i n es e a r c h e sb yu s i n g t h ef u n c t i o n ( z ) = ，( z ) + 去( 一x k ) r a k ( x z ) ，( 1 1 8 ) w h 啦ea ki sas i m p l es y m m e t r i cp o s i t i v ed e f i n i t em a t r i x i fw eu s et h ef u n c t i o n kt o t h eq u a s i - n e w t o nm e t h o di nt h e 耽 i t e r a t i o n w ec a nh a v et h ef o l l o w i n gq u a s i - n e w t o n e q u a t i o n 取+ l s k = 虻，( 1 1 9 ) w h e r e 虻= 班+ a 女如i ti se a s yf o ru st of i n dt h a tw h e n 南t e n d st oi n f i n i t ya n d8 4 - + 0 ， t h e nt h en e wq u a s i - n e w t o ne q u a t i o ni sc l o s et ot h eo r d i n a r yq u a s i - n e w t o ne q u a t i o n i t i sc l e a rt h a tt h i sn e wq u a s i - n e w t o ne q u a t i o ny i e l d st h ef o l l o w i n gt h r e en e wf o r m u l a s f o r m u l a1 u s i n gt h en e wq u a s i - n e w t o ne q u a t i o nf o rb f g su p d a t ew ec a no b t a i na b f g s t y p ef o r m u l aa sf o l l o w s ： b k + l 风+ 筹一鬻 。， f o r m u l a2 u s i n gt h en e wq u a s i - n e w t o ne q u a t i o nf o rd f pu p d a t ew ec a no b t a i na d f p t y p ef o r m u l aa sf o l l o w s ： b k + i = 玩- ( 1 + 案) 筹一螋铲( 1 。) f o r m u l a3 u s i n gt h en e wq u a s i n e w t o ne q u a t i o nf o rb r o y d e nc l a s su p d a t ew ec 锄 o b t a i nab r o y d e u t y p ec l a s sa 8f o l l o w s ： = 风+ 筹一警倾( f i b , 瞄磁， ( 1 2 2 ) ! 皇查兰丝圭兰竺竺圭丝! ! 耋!竺竺竺呈竺量奎童垒皇些童兰竺竺塞 6 w h e r e u - = 最一丽b k s k ( 1 z 。) a n d 西 i sas c a l a rp a r a m e t e r n o t et h a tt h ef o r m u l a1a n dt h ef o r m u l a2c o r r e s p o n dt o t h ec h o i c e so f 也= 0a n d k = 1 h e n c e ，t h em a j o rw o r ki st od e c i d eh o wt oc h o o s ea r e a s o n a b l ea st og i v eag o o df o r m u l a a n dt h r e ec h o i c e so fa kw e r er i v e ni nf 2 4 c h o i c e1 a = a k ( 1 ) = m k i i nt h i sc a s e ， 风+ l s k = 虻= 弧+ y r t k s k ， ( 1 2 4 ) w h e r e 佻= o ( 1 l y k l l ) o r i sa p o s i t i v ec o n s t a n t i nf a c t ，l ia n df u k u s h i m a 【1 2 】h a v eg i v e na m o d i f i e db f g sm e t h o dw h i c he n s u r e j 6t h eg l o b a lc o n v e r g e n c ef o rg e n e r a lo b j e c tf u n c t i o n ，b yu 曲1 9t h i sc h o i c e u n f o r t u n a t e l y , n u m e r i c a lr e s u l t ss h o w s t h a tt h i sm o d i f i c a t i o nd o e s n o to u t p e r f o r mt h eb f g sm e t h o de v e nw ec h o o s em kt ob eav e r ys m a l ln u m b e r ，f o r e x a m p l e ，m k 1 0 一s i n c et h em o d i f i c a t i o no n l yu s i n gt h ef i r s to r d e ri n f o r m a t i o na tt h e k t hi t e r a t i o ni sn o ts u c c e s s f u l ，w em a k eo u ra t t e n t i o no nd e f i n i n ga ka 8as i m p l es t r u c t u r e w h i c hc a r r i e ss o m es e c o n do r d e ri n f o r m a t i o no ft h eo b j e c t i v ef u n c t i o n c h 。i c e2 a k = a ( 2 ) = p 堡鑫铲，( p i o ) i nt h i sc a b e ， b , + l s k = y ；= 孤讹掣踮 c h o i c e3 i nt h i sp a r t ，w ew i l ls t a t et h et h i r dc h o i c e i fw eu s et h et a y l o rf o r m u l at o t h eo b j e c t i v ef u n c t i o n ，( z ) ，w eh a v e ，( 茁) ；，( z k + 1 ) + v f ( x 七+ 1 ) t ( 。一1 + 1 ) + ；( z z 1 ) t v 2 ，( z k + 1 ) ( 卫一z 缸+ 1 ) h e n c e f ( z k ) f ( x k + 1 ) 一v f ( x k + 1 ) t 钆+ 去v 2 f ( x k + 1 ) 乳 t h e r e f o r e f l y 2 f ( x i + 1 ) 船2 f ( z k ) 一( z i + 1 ) 】+ 2 v ，( 瓢+ 1 ) r s = 2 f ( x ) - f ( x k + 1 ) 】+ 0 ( z k + 1 ) + 9 k ) r s k + s t y k b yu s i n g ( 1 2 2 ) w ec a l lh a v e s ：8 k s = s ：靠= y k + s ：a k s k ， w h i c hc o m b i n i n gw i t ht h ea b o v ee q u a l i t yy i e l d s 删= 坐虹紫逊j 砌玩伊。：靠：搬+ 兰竖l 止丛业l l s 。l l 地2 地( 1 2 5 ) 玩+ 。钆：靠：搬+ 巡盟鱼业丝盟塑迅乳 ( 1 2 5 ) 苎皇查兰竺圭兰竺兰圭f ! ! ! ! 丝 竺竺竺! ! ! 竺奎竺圣i 墼呈奎兰丝竺塞 7 t h r e en e wa l g o r i t h m sa r eo b t a i n e da sf o l l o w s ： a l g o r i t h m1 4 1 s t e p0 c h o o s ea l li n i t i a lp o i n tz l 舻a n d 缸i n i t i a lp o s i t i v ed e f i n i t em a t r i xb 1 s e t k ：= = 1 s t e p1 i f g k = 0 ，s t o p s t e p2 s o l v e ( 1 1 0 ) t oo b t a i nt h es e a r c hd i r e c t i o n 以 s t e p3 f i n dq kb yw w ps t e p s i z er u l e ，( 瓤+ 1 ) ，) + 6 a , g , r d , ( 1 2 6 ) a n d 最l d h a g d k ， w h e r e6 ( 0 ，) a n d 盯( 最1 ) s t o p4 s e t 霉k + 1 = z + a k d k c a l c u l a t ea 詹( 2 ) a n du p d a t eb k + 1b yf o r m u l a1 。 s t e p5 s e tk ：= k + 1 a n dg o t os t e p l a l g o r i t