（应用数学专业论文）求解无约束优化的两种算法.pdf

求解无约束优化的两种算法 摘要 耐于无约束优化问题 襞器2 ( x ) ， 其中f ：卵一虢，目前已有许多有效的求解方法及其相关的收敛性分析拟牛 顿法和信赖域法就是众多有效方法中的两种它们在每步迭代时均利用目标 函数值和一阶导数信息来构造目标函数的h e s s i a n 矩阵近似，而不需要计算 h e s s i a n 矩阵，同时具有收敛速度快的优点本文首先证明一种修正的d f p 方法的全局收敛性，然后提出一种求解非光滑凸优化的非单调自适应信赖域 方法本文结构如下， 第一章，简单地介绍求解无约束优化的拟牛顿方法和信赖域方法，然后 给出求解非光滑凸优化的预备知识 第二章，韦增欣等在文【1 1 1 中提出了修正的拟牛顿公式，并分别在文【1 1 l 及【1 2 1 中给出了修正b f g s 方法的全局收敛性和超线性收敛性的证明，但尚 未证明修正d f p 方法的全局收敛性。本章在适当的条件下，证明上述修正 d f p 方法在弱w o l 胁p a 啊，e l l 线搜索下是全局收敛的初步的数值计算表明该 方法是值得提倡的 第三章，信赖域方法有较强的收敛性质：不仅全局收敛，而且超线性收 敛非单调技术可以提高寻找到全局最优点的可能性；另外，当计算的函数 出现峡谷形时，有助于提高收敛速度受文【2 4 】和【2 5 】的启发，本章对非光 滑凸优化问题提出了一种非单调自适应信籁域方法在适当的条件下，证明 该方法具有全局收敛性和超线性收敛性。 关键词：无约束优化凸函数修正d f p 方法线搜索信赖域 方法收敛性 皇查兰塑圭兰竺竺圭! 丝! ! 兰2 ；耋墼垄塑查垡丝竺苎竺兰兰 虹 t w oa l g o r i t h m sf o rs o i i n g u n c o n s t r a i n e do p t i m i z a t i o n a b s t r a c t t l y t h e r e 眦m a n yk i n d b0 fe 髓c t i v em e t h o d sa n dt h e i rc o r r e s p o n d i n gc o n v e r - g e n c ea n a l y s 鹤0 rt h ef o n o 丽n g1 1 n c o 璐t r 8 i n e d0 p t i n l i z 她| 0 np r o b l e l n 磐m ) ， w h e r e ，：舻一蹰q u a s i - n e 砒o nm e t h o d sa n dt r l l s tr 晒o nm e t h o d 8a r et w 0k n d 8 0 ft h e e 髓c t i 、r em e t h o d s b o t ho ft h e mu 孵t h ev a l u eo f0 b j e c t i v ef i l c t i o n8 n dt h e i n f o r m a t i o no fi t s 丘r s 七一o r d e rd e r i n i a nt oc o r 塔t r u c ta p p r d m a t eh 国s i a nm a t r i 】【i 蚰t e a d o fc a l c l l l a t i n gh e s s i a nm a t r i xo fo b j e c t i v ef u n c 七i o na te v e r yi t e r a t i o n ，t h e y 舡s oh a v et h e a d v a n t a g eo ff a s t 咖g e n c er a t e i nt h j st h e s i b ，w ef i r s 七p r a v et h eg l o b a lc o n v e r g e n c e o fam o d i 6 e dd f p m e t h o d ，t h e np r o p o an o 耻o n o t o n ea d a p t mt r u s tr e g o nm e t h o d f o rn o 璐m o o t h n v e xo p t i m i z a t i o n t h et h e s i si so r g a n i z e d 罅f o l l o w 8 ： i nc h a p t e r1 ，靴b r i e 丑yi t r o d u c eq u 粥卜n e w t o nm e t h o d sa n dt r 瑚tr e 舀o nm e t h o d sf b ru n c o n s t r a i n e do p t i m i z a t i o n ，t h e n 舀v et h ep r e i i 蝴yk n o w l e d g ef o rn o m m o o t h c o n v e x0 p t i n l i z a t i o n hc h 印t e r2 ，w j ie ta 1 p r o p 0 6 e dm o d 访e dq u a s i _ n e w t o nf d r m i l l 髓m 【1 1 】，雠d 篑t a b 鼬e dt h e 斟o b a l 删1 v e r g e b c ea n dt h es u p e r 】i n e a rc o n 憎g e n c ef o rt h en 1 0 鼬e db f g s m e t h o di n1 1 l 】a n d 【12 】，r e s p e c t i 、，e l 弘h a w e v e r ，t h e 舀o b 8 lc o r l v e r g e n c eo ft h em o d i 如d d f p 础t h o dw 硇n d t 百v e l l i nt l l i 8c h a p t e r ，u n d e r 印i t a b l ec o n d i t i o w ep r o v et t h em o d i f i e dd f pm 吼h o di 8 酉o b a l l y n v e r g e n tw i t hw e a kw b l 缸p o w e ul i n e 盯出 p r i m a r yn u m e r i c a lr e 8 i l l t s8 h a wt h a tt h i sm e t h o di sp r o m i 8 i n g i nc h a p t e r3 ，t r u s tr e 舀o nm e t h o d 8h a v e8 t r o n gc d n v e r g e n c ef e a t l l r 鹤，n o to n l y 斟o k a 1 1 y n v e r g eb u ta l s os u p e r h n e b r l yc o n v e r 铲n o n 1 0 n o t o n et e c h n i q u ec a ne r l h a n c et h e l i k e l i h o o do f6 n d 洫ga 斟o b a lo p t i n n ，f u r t h e 珊o r e ，i tc a ni m p r a v ec o n v e r g c er a t ew h e n t h ef l l n c t i o c o m p u t e dj 8f o r c e dt oc r e e p 越o n gt h eb o t t o m0 fan a r r a wc u r v e d m e 弘e n 1 i g h e n e db y 【2 4 】a 1 1 d 【2 5 】，mt h j 8d h 筇协矾p r o p o an o 砌o n o t d n ea d 印t i v et n 璩tr e g i o n m e t h o df b fn o 瑚m o o t hc o n 、，既o p t i m i z a n o n ，u n d e rs u i t a b l ec o n d i t i d 地，w e8 h o wt h a tt h e m e t h o di 8g l o b a n ya n ds u p e r l i n e a r l yc o n v e r g e n t k 更 yw o r d s u n 璐t r 曲1 e do p t i m i z a t i o n ；c o n v 戡f i m c t i o n ；m o d i f i e dd f pm e t h o d ； l i n e 缸c l l ；t r u s tr e 舀o nm e t h o d ；c d n v e r g e n c e c h a p t e rli n t r o d u c t i o n c o n s i d e rt h ef 0 1 】o w i i l gu n c d i l s t r a i n e do p t j m i g a t j o np r o b 】e m 罂臻m ) ， ( 1 1 ) w h e r e ，：舻_ 跪i 88c o n t i 珊。璐l yd i 勋e n t i 龇缸l c t i o nw h o s e 伊砌e n t8 t w mb e d e n o t e d b y 9 ( z ) t h e r ea r e m a n y l 血d 8 0 f m e t h o d 8 f o r 8 0 l v i n g p r o b l 哪( 1 _ 1 ) ，f o re x 啪p l e ， 。d 面u g a t eg 砌e n tm e t h o 出，q u a s i - n e w t o nm e t h o d s ，t r l l s tr e g j o nm e t h 0 如8 n d o n ag r e a td e a lo ft h e o r e t i c a l 吼a l y 8 嘲蛆dn 啪e r i c 缸田e r i m e n t 88 h a wt h tq u a 8 i - n e w t o nm e t h o d sa n dt n 培tr e 西o nm e t h o d 8a 舱疆b c t i v em e 垃【o i l sf o r 鲥v j n gp r o b l 锄 ( 1 1 ) b o t ho ft h e ml 瑚t h ei n f b 珊雠i o no f 丘r m o r d e rd e r i 眦i o o fo b j e “i v ef i l n c t i o nt o c o i l s t r u c ta p p r o 妇m a t eh 吲a nm 8 t r i xi 瑚t e 8 do fe a l c l l l a t i n gh e 豁i a m a t r 坟o f0 b j e c t i v e f h n c t i o nw 1 1 i c hm a y b e 麟p e n 8 i v eo rd i m 吼d tt oc a i c u l a t e q u 鹊0 n e w t o nm e t h o l s 缸ev e r y f a m o n sf o rt h e i rs 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 a n dd 铝i r a b l ec o m p n t a t i o n 8 l 鹪p e c t s ， a n dt r t l s tr e 舀o nm e t h o d s 盯ew e n 4 【n o w nf o rt h e i rs t r o n gc o n v e r g e n c e 勉t u r 皓 w 毛n o wb r i e f l yi n t r o d u c eq u 髂i n e w t o nm e t h o d sa n dt r u s 七r e 百o nm e t h o d 8 1 1q u a s i - n e 讯o nm e t h o d s q u a 8 i n 钾n o nm e t h o d 8a r ei t e r a t i v e l e t h o d 8o f 让屺f b r m 茁b + 1 = z 知+ o 也 w h e r en i sas t e p l e n 酵h 越l d 也蟾as e a r c hd i r e c 乞i o nd e t e r m i n e da sf o l l o w 8 b k 呶= 一鲰， w h e r e 鲰= 9 0 k ) a n d m a t r i 】c 圾 1 ) o f t e n n e e d t 0s a t i s f y t h e f o u o w i n gq u a s i n e 叭o n e q u a t i o n b k s k 一12 瓠一l ， w h e r e5 k l = g 一z 七一l ，弧一l = 鲰一鲰一1 d i f f e r e n tu p d a t e 凤如e l d sd i 疗b r 啦l tq u a s i n e w t o nm e t h o d d f pi n e t h o d ，w h o s eu p d a t e 瓯墙g i v e n 鹪 地+ ( 1 + 訾) 舞一迹喾咝， 耋皇查兰塑圭耋竺丝兰堡! ! 兰2 查竺垄竺查堡垒丝里竺量鎏 2 i sa 鼬n o 璐q n 硝一n e w 屯o nr n e t h o d i ti l 矗r 8 p p o 潮b yd 撕d o n ( 1 9 5 9 ) 眦di 81 a 七e r d e v e l o p e db yf l e t h e r8 n dp 0 w e n ( 1 9 6 3 ) p o w e l l p r a v e dt h a td f pm e t h o di 8g l o b a l l y c o n v e r g e n tw i t he 黜c t1 i l l es e a r c hf o ro b j e 啦i v em n c t i o n ，如) 王sc o n v e x b u tw h 既i n e ) ( a c 七 l i n e 船a r c hi 81 1 8 e d ，t h ed o b 以删g 即c eo fd f pm e t h o dr e m a j n 80 p e n ，e v e no b j e c t i v e f u n c t i o n ，( z ) i su n 讧o m d yc o n v 魄t h e y e 缸8 ，y u a n 闭，x u 蛆dl i u 【3 】，x u 【4 l ，y i na n d h 龇l i 铷g 珊d i 侬彻tt h e o r e t i c a la n a 蚴嘲f o rt h e 百o b a lc o n v e r g e n c eo fd f p m e t h o du n d e r t h ec q n d i t i o nt h a t ，( o ) i b u n 迁b m l yc d n v e xf i l l l 耽i o n ，r e 8 p e c t i 晦 a n o t h e rf a m 0 1 1 8q u 拍i n e w t o nm e t h o di 8b f g sm e t h o d ，i t 8u p d a t e 凤i 8 = 玩一鬻+ 鞣 t h e 删r g e n c ep r o p e r t i e 8o fb f g sm e t h o df o rc o n v 既n l i i l i m 也a t i o nh a eb e e n8 t u d i e d b vm 锄yr e 吕e 盯d l e r 8 【6 卜【l0 1 n 啪e r i c a lr e s u l t s8 t 娜t h a tb f g sm e c h o di 8o n eo ft h em o s t e 如c t i v eq u 喇一n 哪t o nm e t h o 幽 & c e n t l y ，w 西，l ia n dq i 【1 1 1p r o p o s e dan 哪q u a 8 i n e w t o n 螂l a t i o n f k + l 乳一醛， ( 1 2 ) w b e r e ， 菇= 鲰+ a 如， 瓠= + l 二g 七，鲰= g k + 1 一鲰，a = a k ( 3 ) = 型豇亟e 丑三星“ 祭塾越卫龇， ( 1 2 ) ，am o d i f i e db f g sf o r m u l a ( m b f g s ) 鲻= 鼠一鬻+ 错 a n dam o d i 丘e dd f pf o r m u l a ( m d f p ) ( 1 3 ) b a s e do n ( 1 4 ) 舻蝴”器) 筹一掣 ( 1 s ) a r eg e n e r a t e d w e i ，“龇l dq i 【儿l 缶s tp r o v e dm b f g sm e t h o di s 西o b m l yc o n 嘴n t i l n d e rw e a kw b 焐p o w e ub n eb e a r c h ，m l dl a t e r ，w 苟e ta 1 1 l r 甸p r o v e dt h a tm b f g sm e t h o d a l s oh a st h es u p e r u n e a rc o n v e r g e n c e 谢t hw e a kw b l 肛p o e ul i n es e 盯c h h o w e v e r ，t h e g l o b a lc o n v e r g e n c eo fm d f pm e t h o dw 嬲n o tg i v e n i nc h a p t e r2 ，w ew mp r o v et 蛾 m d f pm e t h o d i s 西o b 出l yc 0 赫r g e n t 丽t hw e a kw 0 瞻p 呻e nh n e a r c h 咖d e rs u i t a b l e c o n d i t i o 璐p r i m a r yn u m e r i c a ir e s l l l t sw ms h o wt h a tt h i sm e t h o di sp r o m i s i g 1 27 i i u s tr e g i o nm e t h o d s n u s tr e 百o nm e t h o d sa r o b l l s ti t e r a t i v em e t h o d s a te a c hi t e r a t i o n ，t h e yr e q i l i r et 0 c a l c l l l a 抛at r i a ls t 印呶b ys o l v i n gt h e 如n o 丽n g8 u b p r o b l e m j 曙靠d + ；矿鼠d = 机( d ) ( 1 6 ) 8 t 删l k ， w h e r e 肌= v ，) ，鼠舻。a8 y 玎啪e t r i cm t r 波w l l i c hi se i t h e rh e 8 s i a 丑m 8 t 淑o f ，a t 繇o r 锄a p p r o 越m a t i o nt o i t ，a n d 七 oi sat n l 础r e g 岫r a d i u s 鼍i 8u p d a t e d a c c o r d i n g t o t h e v a l u eo f r a t i o 他w h i 吐i 8 e q u a l t o t h e a c t u a lr e d u c t i o n 仃( 巩) 一( 瓤+ 也) ) d i v i d c 8t h ep r e d i c t e dr e d u c t i o n ( 机( o ) 一妒k ( 如) ) i f 他i 8l a 唱e rt h a no re ( 1 u a lt oa 丘x e d p 0 8 i t i v ec o n s t a n tw h i d li s8 m a u e rt h a n1 ，t h 欢j 8a c o e p t e d ，瓢+ l = 瓢+ 呶8 n d z h + 1 = 七o r k + l 之r k ，w h e r er 1 o t h e r w i 蹲以i 8n o ta c c e p t e d ，i + l = 正ka n d + l = f ，w h e r e ( 0 ，1 ) c o m p a r e d 丽t hh n es e 材c hm e t h o d s ，t r u s tr e 舀o nm 甙h o d 8 o b v i o u s l yp o s 8 e 鼹s o m ed e s i r a b l et h e o r e t i c a lf e a t l l r 铝t h e yh a v ev e r ys t r o n gc on _ v e r g e n c e p r o p e m e s 衄dc a nb ea p p l i e dt oi l l c o n d m o n e dp r o b l 锄s m o r e o v e r ，t r l l 8 tr e g i o nm e t h o d 8 a 1 1 0 wt h a t 凤ms u b p r o b l e m ( 1 6 ) 塔i d e 钒te i t i sl 【l l o 帆t h a tm o s to ft h ep r o p e dm e t 】1 0 d 8f o ro p t i m i z a t i o np r o b l e m 8r e q u i r e o b j e c t i v ef 衄c t i o n 、枷u 皤d e c r e 船i n gm o n o t o n i c a l l ya te a d hi t e r a t i o n ，h l t 世i i ss d h 哪ec a n c 0 1 1 s i d e r 矗b l y8 l a wt h er a t eo fc o n v e r g e i l c ei nt h e m t e m e d i a t es t a g 鹤o ft h em i m i m j z a t i o n p c e 嚣，e s p e c i a u yi nt h ep r 豁e n c eo fn a r r o wc u r v e d 、，a l l e y t oa v 钟c o m et h i 86 h o r t m - i i l g r i p p oe ta 1 【13 】p r o p 0 8 e dan o 砌o n o t o n el i n es e a “五t e d l n i q u ef o rn e w t o n 8m e t h o d s i n c et h e n ，n o n m o n o t o n et e 血l i q u eh a sb e e ns t u d i e db ym a n ya u t h o 瑙g r i p p oe ta 1 【14 】 p r o p o s e dan o n m o n o t o n et r l l n c a t e dn e w t o m e t h o d 们t hn o 眦o n o t o n el i n e8 e 町c h m a n y a u t h o r sg e n e r a h z e dn o 衄o n o t o n et e c h l l i q u et ot r l l s tr e 酉o nm e t h o d 8a n dp r o p o s e dn o n - m o o t o n et r l l s tr e g i o nm e t h o d 8 t h e o r e t i c a la n a ：l y 8 e 8a n dn 啪e r i c a lr e s u l t sb h a wt h a t a l g o r i t l m l sw i t hn o n m o n o t o n ep r o p e r t i e sa r e l o r ee f f 记i e n tt h a na l g o r i t h i n sw i t hi n o n o _ t o n ep r o p e r t i 曙s i n c et r u s tr e g i o nm e 如o d 88 r ee 伍c i e n tf o r o i i s m o o t ho p t i m j z a t i o n p r o b l e m s ，w ew i up r o p 0 8 ean o i l i n o n o t o n e8 d a p t i v et r l l 8 tr e 舀o nm e t h o df o rn o 蝴o t h 0 0 n v e xo p t i m i z a t i o ni nc h a p t e r3 u n d e r8 i l i t a b l ec o n d i t i o n ，w e 硒l l 郫t a b l i s ht h a tt h e m e t h o di sg i o b a u ya n db u p e r l i n e 日r l y g e n t 广西大学硕士学位论文偿0 d 6 年) 求解无约束优化的两种算法 4 1 3 p r e l i m i n a r yk n o w l e d g e 蚤 n o n s m o o t hc o n v e o p t i m i z a - t i o n o b j e c t j v e 劬c t j o no fp r o b l 锄( 1 1 ) 王8p 硎b l yn 叩d i 脑e n t i 曲l b t 1 1 i sc 嘴d c c l l r s ，w e a 黯u n l et h a t ，j s8n o n 8 m o o t h 8 t r o n 羽yc o n v e xf l m c t i o n ，i e ，t h e r e 鄹出t 8 & c o n s t 踟1 tb o 8 u c ht h a 七 1 ，( n 。+ ( 1 一曲一) 吖( 卫) + ( 1 一句，( ) 一妄她( 1 一o ) i 陋一一j j 2 ， f o r a u 茁，一渺a n d o ( o ，1 ) t h ec o n s 七锄t 6 i 8 c a l l e d t h e m o d m 璐o fs t r o n gc o v 嘲t y a 豁o c i 8 t i 耐耐t hp r o b l e m ( 1 1 ) i st h ep r o b l 锄 ：醢f ( 甸， ( 1 7 ) w h e r ef ：舻_ 虢培t h e8 0 c a u e dm 0 r e a u y 0 s i d ar e g u l a r i z a t i o no f ，【1 5 1 ，啊棚出i 8d e 矗n e d b y 1 ： f o ) 2 ：醣f ，( 力+ 云o z z 2 ， ( 1 8 ) w h e r e 入主sap 嘲t i v ep a r 锄e t e r 。a n d0 0d e n o t e st h ee u c h d e a nn o r m ，i nt h i st h e s i 8 ，w e f t h ev a l u eo fp a r a i n e t e ra t h en e 砒p r o p 0 8 i t j o n8 h o w s m eb 龉i cp r o p e r t i o ft h e f a d i e n to f f p r o p o s i t i o n1 1 【1 5 1 凡扎c 抚吼f 缸励讹一砌以c 彻u 吼de 可e 删砒e 他d 旬毵他n “口娩 。埘冼9 m d i 饥 1 夕( z ) 三v f ( 。) = ：( 卫一p ( 名) ) ， 砒陀p ( z ) 妇冼8 埘西弘em 锄妇；如盯兢口，砂，t e 。， p ( 小2 哪喀 他) + 刳z z i l 2 ) j l 如他。钟e n 钳e 口o e ，0 ro 盯$ ，z 7 乎p 0 9 ( 。) 一9 ( z ) 1 1 2 ( 9 0 ) 一9 ( 一) ) t ( g 一一) 肌d 九r 琥e 仰l d 他 0 9 ( 。) 一9 ( 一) 0 0 z 一。，n ， t h i sp r o p o s i t i o n 8 h o w s ，i n p a n i 叫a r ，t h a t t h e m 8 p p i n g g ：舻一舻i s 酉o b a l l y l i p s c h j t z n t i n u o u s h e n c e ，b yr a d e m a c h e r 8t h e o r e m ，口i 8d i 既r 即t i a b l e8 h n o s te w r ) 砒e r e i - h e nw e d e 6 n e 西( z ) = c d y 舻”ly 2 恕v 9 溆) ，如) ， 耋皇叁兰堡圭兰竺兰塞丝! ! 耋2垒竺垄竺查丝些丝重窒墨兰 5 w h e r e = 0 舻f9 妇反，e r 菇曲! e 耐) ，8 i l d 国( s ) i st h eg 锄e r 8 珏z e dj a c o b j a n m a t r 仅o f 9a t 。i n t h e8 e r l 8 eo f 【1 6 1 t h en e x tp r o p i t i o nf o r m a l l ys t a c e st h ee q _ l l i v m e n c eb e t w p r o b l e m 8 ( 1 1 ) a i i d ( 1 7 ) p r o p o s i t i o n1 2 【15 】砚e 如舶埘叼s t 口钯m 饥如口他e 口砸n f e n j 霉俐n i m 眈e s ，帆舻； 2 z = p ) i 只9 ( 妨= o i 五zm 伽伽l 钯酗fd n 虢“ i tg a nb es h o w ni n 【1 5 】t l l a ti f ，i 8s t r o n 羽y0 0 n v 既而t hm o d t l l 瑚6 o ，t h 锄f i sa b o8 t r o n g i yc o n v 甑w i t hm o d l l l i l 8 矗a 1 8 0 ，t h es t r o n gc o n v e x i t yo f ，i m p l i e 8t h a t t h e r e 喇s t sa t u l i q u es 0 1 u t i o n 孟0 f g ( 茁) = o s i n t h em 0 r e a u - y 0 s i l ar e g u l a r i z a t i o ni t s e i bd e 6 n e dt h r o u g ham i n i m i z a t i o np r o b _ l 锄i n v o l 、，i n g 六t h e c a 础e v 础u a t i o no ff i l n c t i o nf 8 n di t s 黟a d i e n t9a 七a na r b i t r 踟= yp o i n t z 沁p r a c t i c a l l yi m p o s s i b l ei ng e n e r a l t 0o 、，煳et h i sd i 凤姒t y n k u 8 h i h m 蛐dq i 【1 砚 麟p l o r et h ep o s s i b i i i t y0 fu t i i i z i n g 印p r o ) 【i m a t i o n 8o ft h o s ev 虹u i n s t e a d “t h e i re x a c t 、诎u 镪i nt h ef 0 1 h i n g ，w es h a l lm a k eu o f 印p r d m a t ev a l u 朗o f 胁c t i o nfa n di t 8 伊a d i e n t 夕s u p p o t h a 七f o re a c h z 舻8 n d f o r e a c he o ，w e c a n 矗n da i l 8 p p r d m a t i o n 矿( z ，f ) t ot h e u n i q u em i n i m i z e rp ( z ) i n ( 1 8 ) s u c ht h a t ，p ，f ) ) + 击l l p 口( 霉，e ) 一z 8 2 f ( $ ) + e a 且i i p l e m e n t a b l ep r o c e d l l r ef o r 丘n d i n g8 u c h 姐印p r 似i a t em i n i m i z 既m a yb ef o l l n di n 1 1 8 h 2 0 】b yu 或n g 矿p ，) ，w ed e f i n e p p r d m a t i o n 8p ( z ，f ) a n d 旷扛，f ) t of ( ? ) a n d 夕( $ ) ，r e s p e c t i v e l y b y f 。扛，) = ，( p 8 p ，( ) ) + 六j f 矿0 ，e ) 一。f f 2 a n d 1 口4 ( z ，e ) = ( $ 一p o ( $ ，) ) t h en ( tp r o p 0 8 i t i o nc o n t a i n s8 0 i n ep r o p e r t i 铝o fa p p r o 蚵m a t ef h n c t i o na n dg r 8 d i e n t 试u e 8o f 劬c t i o n f ，w h i c h w m b e l 】幽妇i n c h a p t 舀3 p r 0 0 fo f t h i 8 p r o p 埘t i o n c a n b e f o t l n d i n f l 7 1 锄d f 2 1 】， 三皇查兰竺圭兰竺竺塞! 塑! 量2查竺垄竺查堡些竺塑竺量童 6 p r o p 0 8 i t i o n1 3 工酣，岛，勺6 e 口r 6 乱m 删p d s i 踟e 竹伽t 6 e 瑚g 竹d 屯= m a x b ，勺) 砸p 卵s e 地以，妇s 加叼匆c d 舢凹埘冼m 砒妇6 吼饥纨e ，o f f o t 咖讥b 邮枷 d 地 j ，f ( 。) f 。扛，e ) s f 0 ) + e ； 2 1 l p 0 0 ，e ) 一p ) 0 、2 a e ； 只i b 8 0 ，e ) 一夕( z ) 0 、警； 4 8 扩( t 岛) 一g 。( 暑，勺) i i ；8 茁一暑，i l + 、警j 置( 旷 ，屯) 一9 口 ，勺) ) t ( 卫一! ，) 5 未了i l z 一训1 2 一、警o z 一! ，o j 抗。旷 ，岛) 一9 。( p ，勺) 0 2 ( 旷o ，乞) 一9 。函，勺) ) t o 一可) + 争o z g o + 警 苎皇叁兰竺圭茎竺竺墨 ! ! ! ! 耋2圭竺叁竺查堡垒竺里竺量童 7 c h a p t e r2c o n v e r g e n c ea n a l y s i so fa m o d i a e d d f pm e t h o d 2 1 a l g o r i t h ma n di t 8g 1 0 b a lc o r l v e r g e n c e i nt h j 8s e c t i o n ，吼d e r8 0 m em i l d 啪d i t i o n 8 ，w ee g t a b h s ht h eg l o b “c o n v e r g e n c eo fm d f p m e t h o d 毗hw e a kw o 瞻p o w e l 王l i m 鼬a r c hw h e no b j e c t i v ef l l n c t i o n ，0 ) i 8u n 如m l y c o n 嗽a 1 9 0 r i t h i ni 8 百v 吼嬲f o u o w s ： a l g o r i t h m2 1r 枷即讹巩o dj s t e p1 翻口e 绷尬f 舻讯tz l 舻帆do n 伽靠缸fs 掣仇m e 饥c 砷s 甜妇ed 咖池仇口打话 b l 乎p 肌，c d d s ec d t 肌幻占，盯册des 钍c 矗疏武6 ( o ，) ，盯( 占，1 ) o 以e = 1 0 一6 s 酣七：= j s t 印2 竹印e 鲰= v ，( 。 ) 巧8 鳜0 e ，s 印d 坑e n 廊e ，s 以 靠= 一b i l 鳜( 2 1 ) s t e p3 f i 础s t 印s 缸ea 知s c 矗眈越如b 如骱蜘一p 0 ”e f 2 溉es 化危 。 ， k + a k d k ) 一， k ) s6 d k 西? 如( 2 2 ) n n d 9 ( $ k + q k d k ) t d 盯9 看以( 2 3 ) o 陀s 口t 遣 e 击 s t 印4 & t 钆+ l = 瓢+ a 女蟊( 2 4 ) s t e p5 唧抛a ( 3 ) n 删卸d d f e j 孔的肋即扣m 讹口印 s t 印6 。i 量酣豇：= j c + l ，8 竹d9 d t d e p2 ， t i o n s t 0 鹤t a b l i 8 ht h e 西o b a lc o n v e r g e n c e a k 喇t h m 2 ：1 ，w en e e dt h ef 0 u o 响 1 9 黜p - 苎皇查兰塑圭兰竺篁圭! ! ! ! 耋2兰丝垄丝奎丝些竺塑兰量童 8 a g s u m p t i o n2 1 ( i ) ，：g p _ 狞i s t w i c ec o n t i n u o u s l yd i r e n t i a b l eo n 渺 ( i i ) ，( z ) j s t l n i f 。r m l y c o n v e xo n t h e l e v e l 融 q = 扛i ，( $ ) ，( 茁- ) ) ，