（应用数学专业论文）约束minimax问题的广义单调线搜索sqp算法.pdf

约束m i n i m a x 问题的广义单调线搜索s q p 算法 摘要 众所周知，序歹二次规划( s q p ) 方法是解决非线性约束优化问题最常用 的方法之一，一般来说这种算法具有比较好的收敛性质，数值实验也证明该 算法是非常有效的然而，大多数s q p 方法仍面临着一个重要问题，即这类 算法要求在每次迭代中= 次子规划都有解由于子问题的约束条件是原问题 约束条件的线性近似，因而产生的约束区域可能是空集为克服这些不足， 出现了一些新的技术，譬如像转轴运算、引进新的参数同时为达到超线性 收敛性，避免m a r a t 0 8 效应，一般需要解一个或多个子规划来产生二阶修正 方向，这种方法相对来说计算量是比较大的 本文考虑一般约束的非线性m i n i m 馘问题借助于转轴运算在每次迭代 中，我们构造一个q p 子问题来产生改进方向，同时类似于q p 子问题的构 造原理我们只需求解个线性方程组( s l e ) 来产生修正方向结合一个特殊 的效益函数采用广义单调线搜索产生步长这样便提出了一个新的解决此类 问题的算法在适当条件下，该算法确保了全局和超线性收敛性值得指出 的是，尽管确定近似积极约束集时增加了计算量，但却大大减少了相应子问 题约束条件的个数最后，进行了大量的数值试验，结果显示算法是令人满 意的 关键词：约束m i n i 嗽问题广义单调线搜索s q p 算法全局收敛性超 线性收敛性 g e n e r a l i z e dm o n o t o n el i n es e a r c h s q pa l g o r i t h mf o rc o n s t r a i n e d m i n i m a xp r o b l e m s a b s t r a c t i ti 8w e nk n o w nt h a tt h ea 1 9 0 r i t h 脚o f 卵q u e n t i a lq u a d r a t i cp r o g r a m m i n g ( s q p ) a r eo n e o ft h e 螂tc l 鹅8 i c a la l g o r i t h 瑚f o r8 0 1 v j n gn o n l i n e a rc o n 8 t r a i n t e do p t i m i z a t i o np r o b l e 脚，a n d t h e yg e n e r a i l yh a 代g o o dc o n v e r g e n c ep r o p e r t i 姻，删m e r i c a le x p e r i m e n t sa l s h o wt h a ts q p a l g o r i t h 脚a r ev e r ye 骶c t i v e h o 啪v e r ，m 蹦to ft h es q pa l g d r i t h m sa r ef a c e dw i t ha ni m p o r t a n t p r o b i 咖，t h a ti s ，a te a c hi t e 确越o nt h e 舱a l g o r i t h 砖r e q u i r et h a tt h eq u a d r a t i cp r o g r a m m i n g ( q p ) s u b p r o b i e 嘲m l 埽tb e8 0 l v a b l e d i 坶t ot h ec d n s t r a j n t so fq pr e p r e 孵n ta 五碍t o r d e tl i n e a r i z a t i o n o fo r i g i n a lp r o b l e m sc o n 8 t r a i n t s ，8 0 时f e 柏| b k8 酏o fq pm 硒rb ee m p t y i no r d e rt oo v e r c o m e t h e8 h o r t c o m i n g ，t h e r ea p p e a r8 0 m en e wt e c h i q 懈，州c h 柚p i v o t i n g 印e r a t i o n ，i r o d u c i n g n e wv a r i a b l 髑q bo b t a i ns u p e r l i r l e a ro c n v e r g e n c ea n d 删dm a r a t o s 疵t ，0 n e8 h o u l db 0 1 v eo n e o rn i o r e8 u b p r o g r a m m i n 铲t og e tas e c o n d o r d e rc o r r e c t j o nd i r e c t i o n ，t h i 8k a d st ol 盯g e8 c a i 船 o fc o m p u t a 土i o 珊 i nt h i 8p a p e r ，t h e n l i n e a rm i n i 瑚xp r o b l e 坶w i t hg e n 盱缸c 0 璐t r a i n t 8a r ed i 8 c 1 1 8 s e d b y m e a 璐0 fp i v o t i n go p e r a t i o nw ec 唧t r u c to n eq pb u b p r o b l e mt og e ta ni m p r o v e dd i r e c t i o na t e a c hi t e r a t i o n s i m n a r l y 岫i n gt h e 咖t r u c t i o n a lp r i n c i p l eo fq p8 u b p r o b k mw eo n l yn e e d o ms y b t e m so fl i n e a re q 眦i o 娜( s l e ) t oo b t a i nao o r r e c t i o nd i r e c t i o n i nc o n n e c t i o nw i t ha 印e c i a lm e r i tf u n c t i o nt h eg e r a l i z e dm o n o t o n eu 啪8 e a r c hi 8l l s e dt oy i e l dt h e8 t 印s i z e s oa n e w 讪 0 r i t l l l nf b rb o l v i n gt h ed i s c l l s dp r o b l e l 瑚培p r 郫e n t e d u n d e rm i i dc o n d i t i o 璐，w ec a n o b t a i nt h eg l o b a l 姐d8 u p e r l i n e a r 咖r g e n c e 鼬l a r b b l y w h i ka d d i n g8 0 n l e m p u t a t i o t l 8 a b o u t 印p r o x i m a t e l ya c t i v ec 0 璐t r a i t8 u b t ，b u tt h ec o 瑚t r a i n t 8n u m b e ro fs u b p r o b k 脚i s 删c hl 嘲t h a nb e o r e f i n 缸l y 8 0 m e 肌m e r i c a le ) 【p e r i m e n 七s 缸eo p e r a t e dt ot e s to l l r 驰，o r i t h m ， a n dt h e 嘲1 1 1 t sd e m o n s t r a t et h a ti ti 8s a t i s f 知t o r y k e yw o r d s ：c o n s t r a i n e dm i n i 鲫【p r o b k m 8 ；g e n e r a l i z e dm o n o t o n el i n es e a r c h ；s q pa 1 9 0 - r i t h m ；9 1 0 b a lc o n v e r g e n c e ；8 u p e r l j n e a rc o n v e r g e n c e 皇叁兰塑圭兰竺篁圭 塑查兰! 呈! 銎坚望塑竺妄墨兰塑垒些童! 星呈墨童 1 1 i n t r o d u c t i o n m i n i m a xp r o b l e mi s6 r s t l yu 8 e di np r a c t i c a lp r o b l e m ，髑p e c i a l l ye n g i n e e r i n gd e s i g np r o b 1 e mw h i c hc a nb ec o n v e n i e n t l yc h a n g e di n t ot h ef o l l o w i n gf o r m m i nf 扛) ( p ) s t 岛0 ) so ，j z ( 1 1 ) ( z ) = o ，j e ， w h e r ef ( z ) = m a ) 【 0 ) ，t ) ，j ，正ea r eg i 、r e ni n d e xs e t ss u c ht h a tt h ei n t e r s e c t i o no f e a c l it w o8 e t 8i se m p t y f b rc o n v e n i e n c eo fp r e 8 e n t a t i o n ，w eu 8 et h ef o l l o w i n gn o t a t i o n s t h r o u g h o u tt h i sp a p e r 皿( z ) = = m a x 仍( z ) ，歹，；o = m a ) 【 易( z ) ，j 厶( z ) ；o ， ( 石) = d l ，：毋p ) = 雪扛) ) ，乃( z ) = i ，：工扛) = f 扛) ) ，如= m i n ：i 乃( z ) ) ( 1 2 ) i no r d e rt os o l v et h i 8p r o b l e me m c i e n t l y ，w ea l lh o p et og e t 胁tc o n v e r g e n ta i g o r i t h m ， w h i c hc a ns a et i m e ，r e d u c ec o m p u t a t i o n sa n dt h en u 瑚b e ro fi t e r a t i o n s i ti sw e i lk n o w n t h a tt h e 鼬q u e n t i a lq u a d r a t i cp r o g r 啪m i n g ( s q p ) i 8t h i sk i n do fm e t h o dw h i c ho f t e nh a s 8 u p e r l i n e a rc on _ v e r g e n c e ( 【l 卜【4 】) f o r8 0 l v i n gs m o o t hc o n 8 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 df o rt h i 8r e a s o ni t i 8w i d e l yu s e d s i n c et h el a t e1 9 8 0 s b a s e do nt h ei d e a so fs q p ，t h e r e d e v e l o p8 0 m eo t h e rs u p e r l i n e a rc o i l v e r g e c ea l g o r i t h i 璐i n 【5 】p a n i e r t i t sa i l dh e r 8 k o v i t 8 u s e dt w os y s t e m so fl i n e a re q u a t i o n s ( s u ) 卸do n el i n e a rl e 勰ts q u 盯e sp r o b l e mt og e t t h es e a r c hd i r e c t i o na n dc o r r e c t i o nd i r e c t i o nf o ri n e q u a l i t yc o n s t r a i n e do p t i m i z a t i o n g a o ， h ea n dw u ( 【6 】) o rg a 0 ，g u o ，h ea n dw u ( 【7 】) o n l yu s e df o u rs l ew h i c hh a dt h es a m e c o e 佑c i e n tm a t r i ) 【t op r 郎e n ta 田a l g o r i t h mf hc o n s t r 撕n e do p t i m i z a t i o np r o b l e m ，f u r t h e r j i 她( 【8 】，【9 】) o b t a i n e dt h es e a r c hd i r e c t i o nt h r o u 曲s o l v i n go n e ( q p ) a n du s e dt h ee x p l i c i t f j 咖l l 】at oc o r r e c ti t s i n c es q pa l g o r i t h m sh a v ef ，斌c o n v e r g e n c e ，8 0 m ea u t h o r sh a v ed i r e c t l ya p p l i e ds q p t e c h n i q u 鹤t om i n i m a xp r o b i e m sa n dg o ts o m e8 a t i s f 孔t o r yr e s u i t s z h o ua n dt i t s ( 【l o j ) u s e dt h en o n m o n o t o n el i n es e a r c ht e c h n i q u et og e ta8 u p e r i i n e a r l yc o n v e r g e n ta l g o r i c h m f o ru n c o n 8 t r a i n e dm i n i m a xp r o b l e m i n2 0 0 2 ，y ua n dg a o ( 【1 1 1 ) g e n e r 甜i z e dt h er e s u l ti n 【1 0 】i nv i r t l l eo fas p e c l a lp e n a l t yf u n c t i o na n da l s og o ts u p e r l i n e a rc o i l v e r g e n c e s u p p o s e i s 地ec u i r e n i 把r a i o np o j m ，a n di no r d e rt oc o m p u c ez 蠹+ 1as e a r 血 d i r e c t i o nd 七s h o u i db eo b t a i n e d 矗r s t s ot h em a i np r o c e d u r eo ns q pa l g o r i t h mf o r g e n e r a im i n i m u mp r o b l e mm i n ( ，p ) ：岛忙) o ，f 矗；( z ) = o ，歹而) i st os o l v e 塑叁耋堡圭矍竺丝叁塑查坚! ! ! 里坚堕童竺妄苎兰塑塞堡童! 皇呈墨童 2 t h ef o l l o w i n gq u a d r a t i cp r o g r a m m i n g 瓣m ) + v m ) t d + ；d r 鼠d 8 t 职0 ) + v 吼( z ) r d o ，i 如， ( 1 3 ) 吻( 工) + v 局( z ) t d = 0 ，j 而 t h e nb e i n gs u b j e c t e dt ot h eb 朗e 矗ti nt h em e t h o do fs q p ，y ua n dg a 0 ( 1 1 1 】) c o n s t r u c t aq u a d r a t i cp r o g r a m m i n g 蠲f 0 1 1 0 w 8f o rg e n e r a lm i n i m a xp m b l e m ： 勰 学帅) + v 删) r d ) + j 矿凰d b t 岛( 2 七) + v 岛( z 知) t d so ，歹z 岛( z ) + v 岛p ) t d = o 歹e ， w h e r e 日k = 日( z 七) i sas 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 b e c a u s et h eo b j e c “v ef u n c - t i o nc o n t a i n st h em a xo p e r a t o r ，i ti sc o n t i n u o u sb u tn o n - d i 丑b r e n t i a b l ee v e ni fc o n s t r a i n e d f u n c t i o 璐 0 ) a j ) a r ea l ld i 艉r e n t i a b 王e s ot h ec 1 嬲8 i c a lm e t h o d 8f o rs o l v i n g8 m o o t h o p t i m i z a t i o nm i n i m u mp r o b l e r 璐m a yf a i lt or e a c ha no p t i m u mi ft h e ya r ea p p l i e dd i - r e c t l yt ot h em i n i m a xp r o b l e m 8 t h e ，t h r o u g hi n t r o d u c i n ga na u x i l i a 哆v a r i a b l e 名t h e s u b p r o b l e ma b o v ei 8e q u i v a l e n tt ot h ef 0 1 l o w i n gq u a d r a t i cs u b p r o b l e m “黪+ ，z + 5 矿删 ， 8 t 0 ) + v ( z ) r d t j ， ( 1 4 ) 毋( ) + v 毋( ) t d o ，j 正 、。 ，b ( 。) + v 岛( z ) r d = o ，j e f b rt h ei n f e 鹤i b l em e t h o d ，i e ，扩i si n f e 嬲i b l e ，t h eq u a d r a t i cs u b p r o b l e m ( 1 4 ) a b o v e d o e sn o tn e c e s s a r i l yh a 、，ef e a s i b l es o l u t 沁na n do p t i m a ls o l u t i o n a l t h o u g hy ha n dg a 0 ( 【1 1 】) u s e dt h em e t h o dp o w e np r e g e n t e di n 【1 2 】t om o d i 盼t h eq u a m a t i cp r o 酽a m m i n g ( 1 4 ) b ot h a ti th 勰a ni n i t 谢f e 蹈i b l ep o i n t ，b u tl i ua i l dy h 柚( 【1 3 1 ) g a y eac o n t r a d i c t i o n t os h o wt h a 上t h i 8m e t h o di 8n o tc o r r e c tu n d e rs d m ec o n d i t i o n s i no r d e rt os o l v et h i s p r o b 】e m ，s o m ea d d i t i o n a lc o m p u t a t i o l l s ，8 u c h 船8 0 i v i n go t h e rs u b p r o b l e mo rc o n s t r u c t i n g a n 娃p l i c i td i r e c t i o nd i r e c t l y ，a r en e e d e d o nac e r t a j nd e g r e et h i sa d d st h ec o m p u t a t i o n s o fa l | p r i t h mi t s e l i nf 14 】，g a 0 ，w ha n dl a ip r 鹧e n t e da na p p r o x i m a t es a c t i v ec o i l s t r a i n t s e t t oo v e r c o m e 曲ei n f e a s i b i l i t yo fs u b p m b l e m ( 1 3 ) s o ，i nv i r t u eo fa 百v e ne a c t i v e c o n s t r a i n ts e t ，w em o d i 匆( 1 4 ) s ot h a ti th a saf e a s i b l ep o i n t ，t h e r e f o r et h ef o n a w i n gt w o a 8 s u m p t i o n ss h o u i db er e q u i r e dj n t h i sp a p e r ( h 1 ) 凡m c t i o 竹s 五( z ) “，) ，巧p ) d | ，) 口咒d 玛( 力0 e ) 口化耐f 以f e 口s 乒邶 o 弼e rc d n f 锄钍d t s 冶盛能他礼z i n 6 f e ( h 2 ) 乃r c 舻 n t 口毋，冼e e c t d 倦 v 工( z ) 一v 允( z ) ，i 如( 。) 位) ；v 岛( z ) ， 歹厶p ) ；v 如( z ) ，j e ) 口他“n r 幻讯d 印e ”d e r i t 苎皇叁兰塑圭兰竺望叁塑墨坚! 呈! 里坚望塞丝兰兰兰塑堡垒壅! 皇呈墨童 3 r e m a r k1 1i ti 8n o td 衄c u l tt os h o wt h a t ( h 2 ) a n da n yo n eo ft h et w of o l l o w i n g c o n d i t i o n si sr e a l l ye q u i v a l e n t ： ( h 二1 ) f 0 r c t 乃0 ) ，口耐d 伸 v 工p ) 一v p ) ， 乃( z ) ；v 乃扛) ，j ( z ) ；v 以 ) ，j e ) o r e 跏；嘶讥却e 亿d e 体， 。 c h 2 - 2 ，耽c t 。邝 ( v # ) ，t 乃c ；( v 扛) ，c z ，；( v 扛) ，e ) t 站 j + 1n r 8 矗竹e o 州掣i n d e p e 犯d e n 厶 u n d e rc o n d i t i o n ( h 2 ) ，w ep r o c e s st h ef b l l o w i n gp i v o t i n go p e r a c i o nt og e n e r a t ea n a c t i v ec o n 8 t r a i n t8 u b s e t 嬲s o c i a t e dw i t ht h ec u r r e n ti t e r a t i o nd o i n tz 七 p i 、，o t i n go p e r a t i o np o p s t e p ( i )s e l e c ta ni n i t i a lp a r a m e t e r = e 七一i o s t e p ( i i ) g e n e r a t et h e 争a c t i v ec o n s t r a i n ts u b s e t 乃加山缸a n dm a t r i xr j i 。w 以# = 0 ，：一，l ( z 8 ) 一f ( z ) o ，以，。= j ，：一# 岛( z ) 皿( z ) o ) ， 以# = j j k # uj g k # u e ，k = 廿， ， ( 1 5 ) 冗以。垒( v ( z ) 一v 五。( z ) ，i 以k ，( 缸) ；v 仍( z ) ，j 石女，。；v ( z ) ，j e ) ( 1 6 ) s t 印( i i i ) i f d e t ( 碾。她。) 芝，s e t 缸= ，以k = 乃虹，以= 山虹，以= 以u 山k u e ， s t o p ；o t h e r w i s es e tg ：= a n dr e p e a ts t e p ( i i ) b a 8 i n go nt h ep 0p w ec a nt r a n s l a t e 七h es u b p r o b l e m ( 1 4 ) i n t o m i nz + ；矿日k d ( q p ) s t ，l ( z ) + v ( $ ) t dsz ， 乃k ， ( 1 7 】 毋( 扩) + v 毋( 矿) t d o ，j 山， 、。 ( 矿) + v ( z 。) t d = o ，j e ， w h i c ha l w a y sh a sa no p t i m a ls o l u t i o n ( s e el e m m a2 2b e l o w ) ，a n dy i e l da ni m p r o v e d d i r e c t i o n 扩b ys o l v i n g ( 1 7 ) a l t h o u 曲s o m ea d d i t i o n a lc o m p u t a t i o n sf o rt h ep o pa r e n e e d e dt oc o n s t r u c t ( 1 7 ) ，i tr e d u c e st h en u m b e ro fe l e m e n t si ni n d e xs e ta n dn e c e s s a r y c o m p u t a t i o n sa te a c hi t e r a t 沁n ，a b o v ea l l ，i tp u tu pw i t h 乇h e8 h o r t c o m i n go f 【1o 】一【1 1 】 w bk n o wt h a ti ti s 狮o t h e rk e yw o r ko f t h es q pk i n dm e t h o d st oa v o i dm a r a t o se f - 6 粥t ( f 1 5 】) u n d e rc e r t a i nc o n d i t i o n s r h e r ea r es e v e r a lt y p e so ft e c h n i q u e st op r e v e n tt h i s e 髓c t ，s u c h 勰8 0 l v i n g 加e0 rm o r eq p s ( 【1 6 j ，f 17 】) o rp r e s e n t i n ga i le x p l i c i td i r e c t i o n ( 【8 】， f 9 】) i n 1 0 】z h 伽a n dt i t su s e da s e c o n do r d e rc o r r e c t i o nd i r e c t i o nb ys o l v i n ga n o t h e rq p 兰塑查兰塑圭兰竺丝叁塑查坚! 呈! 墨坚塑塑丝苎苎兰望堡堡窒! 呈呈叁童 4 s u b p r o b l e mt oa v o i dm a r a t 0 8e f f e c t ，a n dy ua n dg a 0 ( 【1 1 i ) u s e dt h es a m et e c h n i q u et o g e tt h ec o r r e c t i o nd i r e c t i o n b u tt h e8 u b p r o b 】e m s ( 【1 0 卜【1 1 】) u n n e c e s s a r i l yh a v ef e a s i b l e p o i n t s ht h i sp a p e r ，w eg e tac o r r e c t i o nd i r e c t i o n 矛g u c ht h a t 毋= 0 ( 1 i 驴1 1 2 ) b yc o n s t r u c t i l 培o n es y s t e mo fl i n e a re q u a t i o n sw h i c ha l w a y sh a sau n i q u es o i u t i o n ( s e ef o r m u i a ( 2 5 ) a n dl e m m a 2 5b e l o w ) b e c a u 8 eo ft h ep i v o t i n go p e r a t i o n m e a n w h i l e t h e8 t e p i e n 薛h8 t r a t e g yi 6b a s e do nam e r i tf u n c t i o n 伽( 墨r ) = f ( 。) + r 屯 ) + r i 了o ) f ， ( 1 8 ) j e w h i c hi 8d i f f e r e n ti nt h ec o n s t r u c t i o nf r o mf 1 1 1 t h eg e n e r a l i z e dm o n o t o n el i n e 肫a r c hp f o p o s e di nt h i sw d r kd o e sn o tr e q u i r e8d e c r e a s e o f t h em e r i tf u n c t i o a te a c hi t e r a t i o nb u ta te a c hr + 1s t e p s ，w h e r eri saf r e e l y n o n n e g a t i v ei n t e g e r ，e s p e c i a i i y i fr =oi ti st h eu s u a ln n es e a r c hw ea r ef a m i j i a rt o f o rd i 疵r e n tv a i u eo fr w ec a nm a a g et os p e e du p 地ec o n v e r g e n tr a t eo ft h ep r o p o s e d a l g o r i t h m i o l l rp a p e rw es e tp e n a l t yp a r a i n e t e rr8 u m c i e n t l yl a r 韶8 0 鹧t oa s s u r et h ed e 8 c e n t o f 埘( z ；r ) b u ti np r a c t i c a la l g o r i t h mi fr 塔t o ol a r g e ，i tm u s ti n n u e n c et h ee x p e r i m e n t a i r e s u i t sa n de v e nr i 8 et oi j i - c o n d i t i o n ，s ow ep r e s e n tat e c h n i q u ei no u r “9 0 r i t h mw h i c hc a n m o d i 纾ra u t o m a t i c a l l ya te a c hi t e r a t i o nb yj n e a n so ft h em u l t i p l i e ro f ( q p ) s u b p r o b l e m a n dr e m a r l c a b l yt h i sp r o c e 岛c a nb et e 珊i n a t e da r e ra6 n i t en u m b e ro fa d j u s t m e n t s ，i e ， ri sac o n s t a n ta tl a s t ( s e el e m m a3 3 ) o n l yi ft h en e wa l g o r i t h mp r o d u c e sab o u n d e d 舱q u e n c eo fi t e r a t i o np o i n t s n o ww es u m m a r i z em a i nf e a t u r e so fo u r 柚g o r i t h ma sf o l l o w s ： t h ei n “i a jp o i n “sa r b i t r a r y ； am a i n8 e a r c hd i r e c t i o nf o rp r o b l e m ( 1 1 ) i sau n i q u e o p t i m a ls o l u t i o no f ( q p ) 8 u b p r o b - l e m ： a 盹c o n do r d e rc o r r e c t i o nd i r e c t i o nc a nb eo b t a i n e db ys o l v i n go n e8 y s t e mo fl i n e a r e c l u a t i o 姗； ag e n e r a l i z e dm o n o t o n el i n es e a r c ht e c h n i q u ei si n t r o d u c e d o u ra l g o r i t h mp o 孵e s s e sg l o b a la i l ds u p e r l i n e a rc o n v e r g e n c e i nt h en e x ts e c t i o nt h ea l g o r i t h ma n di t 8p r o p e r t i e sa r ed i s c u 豁e d ，a n dw ea i l a i y z e t h eg l o b a lc o n v e r g e n c e 柚dt h es u p e r l i n e a rc o n v e r g e n c eo ft h ea l g o m h mr e s p e c t i v e l yi n s e c t i o i l s3a n d4 f i n a l l ys o m ep r e l i m i n a r yn u m e r i c a lt e s t sa r er e p o r t e di ns e c t i o n5 皇叁耋塑圭竺竺丝塞竺查些! 呈! 竺竺望翼竺苎苎兰望垒堡窒! 竺呈叁童 5 2 a l g o r i t h m i no r d e rt os h o w8 0 m eb e n e f i c i a lp r o p e r t i e so fp o pm e n t i o n e da b o v e ，w h i c hi sh e l p f u l f o rd i s c u s 8 i n gt h ec o n v e 唱e n c eo fo u ra 1 9 0 r i t h m ，w ep r e s e n tt h ef o l l o w i n gl e m m a ，a i l di t s p r o o fi ss i m i l a rt ol e m m a 2 1i n 【8 】o rl e m m a1 1 卸dl e m m a2 8i n 【1 8 1 f i r s t ，f o r c o n v e n i e n c eo f w 订t i n g ，f o r as u b s e ts | r u ，u ea n dz f p ，w ed e n o t e m a t r r s ( z ) = ( v ，l ( 舅) v 。( z ) ，i s n ， 缸) ；v 毋( 。) ，歹s n j ；v ，b ( z ) ，歹s n _ e ) l e m m a2 1s 印p o s e 晓甜阳 一f h 纠 o f d 孤e 竹，o r 撕g 扩r r i ， 饥ep 伽d 胁w 叩e m 撕p o p 。6 e 乒n 渤甜锄n 五佗i 钯扎世m 抛ro ，c 0 汀巾壮n 如n s ，i e ， 耽e 他妇竹o 咖靠ef 拥e so ，f o d p6 e 泐卵t l 成印f 彬。埘印一i 砂j 一砂矿眈e 善e g e ，l 矿，d ，p o 讥拈妇6 0 t n d e 面h e nt ，l e r ee 研s 亡sn t l 舌 os t c 地o t 纨e 8 船i 口# e d3 e 弘e c e “) d ，p n m m e t e 邝9 e 竹e m t e d 眄p d p8 0 i 妒e 8 “手，d rn “i 一别妒琥es e 口“e n c e 矿 o ，p o 讥拈诂6 0 t n d e 正矾e ，l 钠e 代e 蕊t sd n os c 冼耐 d e t ( r n 。( $ 詹) t r 。( 七知) ) 2 o 弘r 口n 掣女以c m dn 盯七 l e m m2 2 跚p d s e 纳耐阻砂一f h 纠，l d f d ，风诂np o s 劬ed 巧n l t em 。t m 孤e n ，口r d 他鲈z 七r “， 。 俐心一口f 伽。驷 8 n 幻“eo p f 打n 8 f s d 缸“d 托( 扩，) 口n d 镪= m a x 扛) + v ( 矿) t 扩， i j ，) i 一砂( 砂，镪) 妇8 行印t i m 谢5 d z “蜘站巧r q 纠可口州d 扎匆矿缸妇n 耳k 丁p o 讥to ，矽 p r o o f ( i ) a c c o r d i n gt ot h ep o p w ec o n s t n i c t 亡h ef o l l o w i n gd i r e c j o n i ) e n o 抬 r u b = ( v 毋( z ) ，j 山k ；v ( 扩) ，j e ) ， b ( 矿) = ( 磁。e 兄。u e ) 一1 磁。e ， g ( z ) = ( 一毋扛) ，歹以；一一( 扩) ，j e ) t ， a n dd e 矗n e 矛= b 0 ) t g ) ，磊= m a x ( ) + v ( 矿) t 孑，i 乃k ) ( 2 1 ) t h e n w eh a v e 毋( 扩) + ( z 。) t 于= o ，如 ；( 矿) + v ( 矿) t 矛= o ，e s o ( 孑，争) i saf e a s i b l ep o i n to f ( q p ) a n dt h ef e a s i b l e8 e to f ( q p ) i 8n o te m p t y j 苎里叁兰塑圭兰堡垒圭塑查坠垫! 型坚塑塑丝苎苎兰堡垒些童! 坌呈叁鎏 6 o nt h eo t h e rh a | 1 d ，s i m i l a rt