（管理科学与工程专业论文）二层优化和nash均衡问题的同伦算法研究.pdf

堕主堕堑塞塑堂! 兰塑萋一一! 二层优化和n a s h 均衡问题的同伦算法 研究 徐庆 ( 复旦大学管理科学与工程博士后流动站) 中文摘要 二层规划问题最早来源于s t a c k e l b e r g 博弈问题。今天二层规划问题在运输、 管理、优化设计、化工、电力、网络设计等领域都有非常广泛的应用，有关二层 规划问题的算法研究也成为人们关注的焦点，目前已给出了几种求解二二层规划问 题的算法。第一类求解二层规划的算法是分枝界定法；第二类是下降法；第三类 是罚函数法。 n a s h 均衡理论可用柬分析很多重要的经济学和社会科学问题，近年来，这 个理论被用来分析很多管理科学问题，特别是供应链管理问题，成为管理科学和 经济学的重要基础理论之一。 n a s h 均衡理论解的存在性、理论和算法的研究，己引起国内外众多学者的 极大兴趣，并得到了很多结果。研究结果大部分是关于存在性和应用。对于n a s h 问题的解的描述，对偶理论以及有效的算法相对比较少。为求解n a s h 均衡问题， 一般的做法是将其转化为：( a ) 非线性方程组；( b ) 变分不等式问题( 筒记为 v i ) ；( c ) 广义均衡问题( g e n e r a l i z e de q u i l i b r i u mp r o b l e m 简记为g e p ) 及 其对应的变分不等式问题；( d ) 优化问题来求解。 因此研究n a s h 均衡问题和这四个问题之间的关系，以及这些问题间的关系 是一个很重要的研究内容。单调性对变分不等式和广义均衡问题的算法研究是很 重要的。 广义n a s h 均衡问题( 简记为g n e p ) 是n a s h 均衡问题的拓广，它的每个博 弈者的策略集依赖于其他博弈的策略集。解一个凸规划的n a s b 均衡问题能化为 一个变分不等式求解已是一个已知的事实，并且有许多方法可以应用。相应地， 广义n a s l a 均衡问题可以转化为拟变分不等式来研究。但是拟变分不等式一般是 很难的问题，目前仅有少数的算法可用来求解。一种是应用半光滑牛顿法计算拟 变分不等式，这种方法的主要不足是需要对拟变分不等式加很强的条件，同时还 要计算非光滑函数的b 次微分。另一种方法是罚方法，这种方法需要解一系列 的子n a s h 均衡问题，但这些子n a s h 问题是否满足变分不等式算法的收敛性假 设，一般是不清楚的。第三种方法是j s ，p a n g 用j o s e p h y n e w t o n 法给出了拟变 分不等式的局部收敛性方法。 本文的贡献是在适当的条件下，给出了求解二层规划问题和广义n a s h 均衡 问题的全局收敛算法同伦算法。 博士后研究报告中文摘要 本报告由六章组成。 第一章给出了求解二层规划的同伦方法。在适当的条件下，用同伦方法同伦 路径收敛到b l l p 的k k t 点。计算结果表明这种方法是可行、有效的。 第二章研究在何种条件下，n a s h 均衡能用变分不等式表示，何种条件下能 用广义均衡问题来表示，但不能用变分不等式表示，并研究三个问题解之间的关 系。同时研究了相应映射和双函数的单调性。 第三章、第四章，借助k k t 系统，给出了广义n a s h 均衡问题和带不等式 约束的广义n a s h 均衡问题的全局收敛算法。 第五章、第六章讨论了非线性互补问题和无界区域上的非凸优化问题的全局 收敛算法。 本研究成果，是本人在博士后工作期间所做的研究成果的部分汇总。本研究 的一些结果，在一定意义上具有原创性，为后续研究准备了基础。 关键词：广义n a s h 均衡，同伦方法，全局收敛，非线性互补，预估校正法，内 点同伦方法，两层规划，非凸规划，法锥条件。 坠尘坐! ! 坚塑! ! 型! ! 塑! ! ! ：! ! 塑生坐坚旦坐l 璺堕塑堕一坐 r e s e a r c ho l lh o m o t o p ym e t h o d o fb i l e v e lp r o g r a m m i n g a b s t r a c t a n dn a s ho fe q u i l i b r i u mp r o b l e m x u q i n g ( f u d a nu n i v e r s i t y ) d i r e c t e db y ：p r o f e s s o rz h ud a o l i t h eo r i g i no fb i l e v e lp r o g r a m sp r o b l e m ( b l p p ) c o u l db et r a c e dt oe c o n o m i c n o t i o no fa s t a c k e l b e r gg a m e t o d a y b i l e v e l p r o g r a m s h a v eaw i d e r a n g e o f a p p l i c a t i o n s i n e n g i n e e r i n g a n de c o n o m i c s f o r e x a m p l e ，e c o n o m i cp l a n n i n g ， a g r i c u l t u r a lc r e d i td i s t r i b u t i o n ，e l e c t r i cu t i l i t yp r i c i n ga n dp l a n n i n g ，n e t w o r kd e s i g n p r o b l e m ，o r i g i n d e s t i n a t i o n d e m a n da d j u s t m e n t p r o b l e m ，d i s c r e t e t r a n s i t p l a n n i n g p r o b l e m ，af a c i l i t yl o c a t i o na n dp r o d u c t i o np r o b l e me t c m o r ea n d m o r ea t t e n t i o nh a s b e e n p a i d t o a l g o r i t h m s o fb l p rs e v e r a l a l g o r i t h m s h a v e b e e n p r o p o s e d f o r n o n l i n e a rb i l e v e l p r o g r a m m i n g f i r s tc a t e g o r i e s o ft h e a l g o r i t h m s f o rb i l e v e l p r o g r a m m i n gi st h eb r a n c h a n d b o u n da p p r o a c h ；t h es e c o n do n e i sd e s c e n tm e t h o d s f i n a l l y , t h ep e n a l t ym e t h o d s c o n s t i t u t eat h i r dc a t e g o r yo f a l g o r i t h m s ， n u m e r o u se c o n o m i ca n ds o c i a lp r o b l e m sc o u l db ea n a l y z e db yn a s h e q u i l i b r i u m t h e o r y , i nr e c e n ty e a r s ，g a m et h e o r yw a sa p p l i e dt oa n a l y z ev a r i o u sp r o b l e m so f m a n a g e m e n ts c i e n c e ，f o ri n s t a n c e ，t h es u p p l yc h a i nm a n a g e m e n t ，i th a sb e c a m ea n i m p o r t a n t b a s i cm o d e l m o r ea n dm o r ea t t e n t i o nh a sb e e n p a i d t oe x i s t e n c e t h e o r y o fs o l u t i o n ， c o m p u t a t i o n a la l g o r i t h m sf o rn a s he q u i l i b r i u m ah o s to fr e s u l t sa b o u te x i s t e n c ea n d a p p l i c a t i o n h a v eb e e n o b t a i n e d o n l y ah a n d f u lo fr e s u l ti s i n v o l v e di n c h a r a c t e r i z a t i o n so fs o l u t i o ns e to fn a s h e q u i l i b r i u mp r o b l e m d u a lt h e o r ya n d e f f e c t i v ea l g o r i t h m w eo f t e nt r a n s f o r mn a s he q u i l i b r i u mp r o b l e mi n t on o n l i n e a r e q u a t i o np r o b l e m ，v a r i a t i o n a li n e q u a l i t i e s ( v i ) ，g e n e r a l i z e de q u i l i b r i u mp r o b l e m ( g e p ) o ro p t i m i z a t i o np r o b l e mt os o l v ei t m o n o t o n i c i t i e sp l a yk e yr o l ei na l g o r i t h m s f o rs o l v i n gv a r i a t i o n a li n e q u a l i t i e sa n d g e n e r a l i z ee q u i l i b r i u mp r o b l e m t h e r e f o r e ，i ti sv e r yi m p o r t a n tt os t u d yt h er e l a t i o n s h i p sb e t w e e nn e ，v ia n d g e e a n da l s on e e dt oi n v e s t i g a t er e l a t i o na m o n g m o n o t o n i c i t yo ft h e i rc o r r e s p o n d i n g m a p p i n g s a n db i f u n c t i o n s t h e g e n e r a l i z e dn a s he q u i l i b r i u mp r o b l e m ( g n e p ) i sa ne x t e n s i o no ft h e s t a n d a r dn a s he q u i l i b r i u mp r o b l e m ，i nw h i c he a c hp l a y e r s s t r a t e g ys e ti sd e p e n d e n t o nt h er i v a lp l a y e r ss t r a t e g i e s i ti sb yn o w aw e l l k n o w nf a c tt h a tt h es 乜m d a r dn a s h e q u i l i b r i u mp r o b l e mw h e r ee a c hp l a y e rs o l v e sac o n v e xp r o g r a mc a nb ef o r m u l a t e d 堡型! 坐! 塑堕墅! 型! ! 塑生! 塑塑里堂翌! 虹些塑! l a n ds o l v e da saf i n i t e d i m e n s i o n a lv a r i a t i o n a li n e q u a l i t y i tc o n t r a s t ，t h eg e n e r a l i z e d n a s he q u i l i b r i u mp r o b l e m h a sc o m m o n l yb e e n s t u d i e da sa q u a s i v a r i a t i o n a l i n e q u a l i t i e s ( q v i ) b u tq u a s i v a r i a t i o n a li n e q u a l i t i e s i sav e r yd i f f i c u l tp r o b l e mt o s o l v e a n do n l yah a n d f u lo fr i g o r o u sa l g o r i t h m sa r ea v a i l a b l ef o ri t ss o l u t i o n f i r s to f t h ea l g o r i t h m sf o rq v ii sas e m i s m o o t hn e w t o nm e t h o d ，am a i nd e f i c i e n c yo ft h i s p r o p o s a l i st h a ti t r e q u i r e sf a i r l ys t r o n ga s s u m p t i o n s o nt h eq v i ，a n dc a l c u l a t e s ”b s u b d i f f e r e n t i a l s ”o ft h en o n s m o o t hf u n c t i o n t h es e c o n do n ei s ap e n a l i z a t i o n m e t h o d t h i sm e t h o ds o l v e sas e q u e n c eo fp e n a l i z e dn e p s ，b u ti t i sn o tc l e a rw h e t h e r t h e p r o p e r t i e so f n a s hs u b p r o b l e m c a ns a t i s f ya s s u m p t i o nr e q u i r e df o rc o n v e r g e n c eo f t h ev 1a l g o r i t h m s f i n a l l y ，t h i r dm e t h o di st h a tj , s p a n gp r e s e n tal o c a l l yc o n v e r g e n c e m e t h o ds o l v e dq v ib yt h ej o s e p h y - n e w t o nm e t h o d t h ec o n t r i b u t i o no ft h i st h e s i si st h a tw e p r o p o s eag l o b a l l yc o n v e r g e n c e m e t h o d s o l v e db i l e v e lp r o g r a m sa n dt h eg e n e r a l i z e dn a s he q u i l i b r i u mp r o b l e m ( g n e p ) b y t h eh o m o t o p ym e t h o d ，u n d e rr e a s o n a b l ec o n d i t i o n t h i st h e s i sc o n s i s t so fs i x c h a p t e r s c h a p t e r1p r o p o s eah o m o t o p y m e t h o df o rs o l v i n gb i l e v e lp r o g r a m s u n d e ro n e s a t i s f i a b l es u f f i c i e n tc o n d i t i o n ，t h ep o i n to fh o m o t o p yp a t hg l o b a l l yc o n v e r g e st oa k k tp o i n to fb l p p s o m en u m e r i c a lr e s u l t sa r ep r e s e n t e dt os h o wt h ee f f e c t i v e n e s s o f m i sm e t h o d c h a p t e r 2i n t r o d u c es o m e r e l a t i o n s h i p s b e t w e e nn a s h e q u i l i b r i a ( n e ) ， v a r i a t i o n a li n e q u a l i t i e s ( v o ，m a d g e n e r a l i z e de q u i l i b r i u mp r o b l e m ( g e p ) w ea l s o i n v e s t i g a t et h er e l a t i o n sa m o n gm o n o t o n i c i t yo ft h e i rc o r r e s p o n d i n gm a p p i n g sa n d b i f u n c t i o n s i nc h a p t e r3a n d4 ，v i ag n e p 。s e q u i v a l e n tk a r u s h k u h n t u c k e r ( k - k t ) s y s t e m ， w ep r o p o s eag l o b a l l yc o n v e r g e n c em e t h o df o rs o l v i n gg n e pa n dw i t hi n e q u a l i t y c o n s t r a i ng e n e r a l i z e dn a s h e q u i l i b r i u mp r o b l e m i nc h a p t e r5a n d6 ，w ep r o p o s eh o m o t o p ym e t h o df o rs o l v i n gg e n e r a ln o n l i n e a r c o m p l e m e n t a r i t yp r o b l e m c p ) a n dt h en o n c o n v e xu n c o n s t r a i n e d o p t i m i z a t i o n p r o b l e m k e y w o r d s ：g e n e r a l i z e d n a s h g a m e ，h o m o t o p ym e t h o d ，g l o b a l c o n v e r g e n c e ， n o n l i n e a rc o m p l e m e n t a r i t y , p r e d i c t o r - c o r r e c t o r , i n t e r i o rh o m o t o p y ，b i l e v e lp r o g r a m s ， n o n c o n v e xp r o g r a m s ，n o r m a lc o n ec o n d i t i o n c h a p t e r1 a h o m o t o p y m e t h o df o rs o l v i n g b i l e v e lp r o g r a m m i n gp r o b l e m a b s t r a c t a h o m o t o p y m e t h o df o rs o l v i n gb i l e v e lp r o g r a m m i n gp r o b l e m ( b l p p ) i sp r o p o s e d t h ea l g o r i t h mi sb a s e do nc o n s t r u c t i n gt h eh o m o t o p ye q u a t i o nf o r b l p p o n es a t i s f i a b l es u f f i c i e n tc o n d i t i o ni sg i v e nt oe n s u r et h a tt h ep o i n to f h o m o t o p yp a t hg l o b a l l yc o n v e r g e st oak k - tp o i n to fb l p p n u m e r i c a l r e s u l t s a r ep r e s e n t e dt os h o wt h ee f f e c t i v e n e s so ft h i sm e t h o d m s c ：5 8 c 3 0 ；6 5 h 2 0 ；9 0 c 3 0 k e y w o r d s ：b i l e v e lp r o g r a m s ，n o n c o n v e xp r o g r a m s ，h o m o t o p ym e t h o d ，n o r m a l c o n ec o n d i t i o n 1 1i n t r o d u c t i o n t h eb i l e v e lp r o g r a m m i n gp r o b l e m ，b l l p ，i sa no p t i m i z a t i o np r o b l e mt h a ti sc o n s t r a i n e db y a n o t h e ro p t i m i z a t i o np r o b l e m w ec o n s i d e rt h ef o l l o w i n gb i l e v e lp r o g r a m m i n gp r o b l e m ( b l p p ) 嘧，( z ，) s t g ( x ，y ) 0 ， m ，i “f ( x ，g ) s t a ( x ，y ) s0 ( 1 1 ) w h e r e ( z ，y ) 舻+ ma n d 六f ：形+ ”- r ，g = ( g l ，g m l ) r ：舻十m - r “，g = ( g l ，一，g m 2 ) t ：r “+ “- + r ”2 b l p p ，e v e ni nt h el i n e a rc a s e ，i san o n c o n v e xo p t i m i z a t i o n p r o b l e m g e n e r a l l y , p r o b l e m ( 1 1 ) i sa n o n c o n v e xa n dn o n s m o o t hp r o g r a m 1 2ah o r a o t o p ym e t h o di o rs o l v i n gb i l e v e lp r o g r a m m i n gp r o b l e mc h a p 1 t h eo r i g i no fb l p pc o u l db et r a c e dt oe c o n o m i cn o t i o no fas t a c k e l b e r gg a m e 【2 6 t o d a yb i l e v e lp r o g r a m sh a v eaw i d er a n g e o fa p p l i c a t i o n si ne n 百n e e r i n ga n de c o n o m i c s f o re x a m p l e ，e c o n o m i cp l a n n i n g 【i o ，a g r i c u l t u r a lc r e d i td i s t r i b u t i o n1 2 1 ，e l e c t r i cu t i l i t y p r i c i n g a n d p l a n n i n g ， 1 4 ，1 7 1 ，n e t w o r kd e s i g np r o b l e m ，o r i g i n - d e s t i n a t i o n d e m a n d a d j u s t m e n t p r o b l e m ，d i s c r e t et r a n s i tp l a n n i n gp r o b l e m ，af a c i l i t yl o c a t i o na n dp r o d u c t i o np r o b l e mf 1 8 ， 1 3 1e t c s e v e r a la l g o r i t h m sh a v eb e e np r o p o s e df o rn o n l i n e a rb i l e v e lp r o g r a m m i n g f i r s t c a t e g o r i e so ft h ea l g o r i t h m sf o rb l p pi s t h eb r a n c h - a n d b o u n da p p r o a c h ，e d m u n d sa n d b a r df 1 1 1 ，a i k h a y y a l ，h o r s ta n dp a r d a l o s1 4 l ；t h es e c o n do n ei sd e s c e n tm e t h o d s ，k o l s t a d a n dl a s d o nf i 6 1 ，s a v a r da n dg a u v i n 2 2 1 f i n a l l y , t h ep e n a l t ym e t h o d sc o n s t i t u t eat h i r d c a t e g o r yo fa l g o r i t h m s ，a i y o s h ia n ds h i m i z n 【1 ，3 ，2 4 】，i s h i z u k aa n da i y o s h if 1 5 ，m a r c o t t e a n dz h uf 1 9 1 ，c a l a m a ia n dc o n nf 8 1 ，c a s ee ta l 9 1 h lt h i sp a p e r w ep r o p o s eah o m o t o p ym e t h o df o r s o l v i n gb i l e v e lp r o g r a m s f i r s tw e c o n s t r u c tt h eh o m o t o p y e q u a t i o nf o rb l p p ，t h e nw ep r o v et h a t ，u n d e ro n es a t i s f i a b l es n m c i e n tc o n d i t i o n ，t h ep o i n to fh o m o t o p y p a t hg l o b a l l yc o n v e r g e st oak k tp o i n to fb l p p t h e p r e d i c t o r c o r r e c t o ra l g o r i t h mi sp r o p o s e dt ot r a c en u m e r i c a l l yt h eh o m o t o p ye q u a t i o n s f i n a l l y ，s o m en u m e r i c a lr e s u l t sa r ep r e s e n t e dt os h o wt h ee f f e c t i v e n e s so ft h i sm e t h o d 1 2t h e h o m o t o p ye q u a t i o nf o rf o l l o w e r so p t i m i z a t i o np r o b l e m i nw h a tf o l l o w sw ec o n s i d e r b l p p ( 1 1 ) w h e r e ，f ig a n dga r es u f f i c i e n ts m o o t ha n dc o n v e x f i r s t ，w ec o n s i d e rt h ef o l l o w e r so p t i m i z a t i o np r o b l e m ， m 9 i n f ( x ，) s t a ( x ，y ) 0 ( 2 1 ) a s s u m et h a tf o rg i v e np o i n tz r ”，t h es e t r ”：a ( z ，y ) o ) i sn o n e m p t y t h e n o p t i m i z a t i o np r o b l e m ( 2 1 ) i se q u i v a l e n tt ot h ef o l l o w i n gk k - ts y s t e m v f ( z ，y ) + v a ( x ，u ) u = 0 ， u g ( x ，y ) = 0 ，乱0 ，a ( x ，y ) 0 w h e r e 钍r 罕2a n du = d i a g ( u ) t h e r e f o r e ，b i l e v e lp r o b l e mb l p p ( 1 1 ) c a nb ee x p r e s s e da s m l n z ，g s t 。 ( x ，y ) g ( x ，p ) 0 ， v f ( z ，y ) + v 目a ( x ，y ) = 0 ， u g ( x ，y ) = 0 ，u 0 ，a ( z ，) 0 ( 2 2 ) w o r kr e p o r ti o rp o s t d o c t o r a l ，f u d a nu n i v e r s i t y 3 一一 t h eh o m o t o p ye q u a t i o nf o rt h ef o l l o w e r so p t i m i z a t i o nc a l lb er e p r e s e n t e da s 嘶叫) 垒( 码f 弯黼凳涔如) _ 0 7 ( 2 3 ) w h e r ew = ( z ，y ，“) 丁，e = ( 1 ，1 ) t r m 2 ，a n dt ( o ，1 】 s e t ，( t 盯) = f ( x ，可) ，蚕( 叫) = 9 ( 茁，笋) ，s o m ef e a s i b l es e t sa n di n d e xs e t a r ed e n o t e da s f o l l o w s ： c o n d i t i o na n 1 ( t ) 垒w r “+ m 豫：( 锄) 0 a ( t ) 垒n l ( t ) r 辑r “+ ”2 ， m l 0 1 2 l ( ) 垒 叫q 1 ( ) ：i i 磊( 叫) = o ) ， t = 1 i ( w ) 垒 i 1 ，m l ：o i ( w ) = o ) ， a ( x ，y ) = t l ，m 2 ：g d x ，y ) = o ( a 1 ) v t 【0 ，1 ，q 1 ( t ) i sn o n e m p t y a n db o u n d e d ( a - 2 ) v g i ( x ，笋) ，i i g ( x ，可) ) i sam a t r i xo f f u l lc o l u m nr a n k ； ( a 一3 ) f o rt ( 0 ，1 】，w q 1 ( ) ， v 执( 删) ，。j ( 州) ，v 。h ( w ，t ) ) i sf u l lc o l u m n r a n k ( a 一4 ) v w q l ( 1 ) ， 叫+ v w m w ) + v 。 ( 叫，1 ) a n n l ( 1 ) = 叫) 。 i e t ( w ) ( a 一5 ) f o ra n y ( z ，y ) ( 。，y ) ：g ( x ，y ) 0 ，g ( z ，y ) o ) ， v ，g f ( z ，y ) v g l ( z ，) t ) i sp o s i t i v ed e f t n i t e v 品f ( x ，) + 当r n 2lv 92yg i ，y ) +v 品，) + 上ov g g i ，) + r e m a r k2 1 c o n d i t i o n ( a - 5 ) c a ng u a r a n t e et h eu n i q u e n e s so fs o l u t i o n f o rt h ef o l l o w e r p r o b l e mo fb l p p g e o m e t r i c a li n t e r p r e t a t i o no fc o n d i t i o n ( a - 4 ) i st h a tq 1 ( 1 ) s a t i s f i e st h e n o r m a lc o n ec o n d i t i o n l e m m a1 2 1 t m c c o r m i c k 2 鳓s u p p o s et h a tc o n d i t i o n ( a 一1 ) 。( a - 2 ) a n dl a 一5 ) h o l d , a n d t h es e tn = ( 。，y ) r “+ “：g ( x ，口) 0 ，a ( x ，y ) o ) i sn o n e m p t y t h e ni o ra n yg i v e n p o i n tz 囝t h e s o l u t i o nc u r v e 掣( ) ， ( ) ，t ( 0 ：1 j ，f o r f o l l o w e r sh o m o t o p ye q u a t i o n 偿圳 i sc o n t i n u o u s ，b o u n d e da n du n i q u e ，a n da 8t _ 0 ，y ( t ) t e n dt ot h es o l u t i o no ft h ef o l l o w e r p r o b l e m 4ah o m o t o p ym e t h o dl o rs o l v i n gb i l e v e lp r o g r a m m i n gp r o b l e m c h a p j 1 3t h eh o m o t o p ye q u a t i o nf o rb l p pa n dc o n v e r g e n c e o ft h eh o m o t o p y p a t h w a y c o n s i d e rt h ef o l l o w i n gp a r a m e t e r i z e dp r o g r a m m i n gp r o b l e m m l n o ，0 s t ，( ，磐) g ( x ，y ) 0 ，t ) = 0 ( 31 ) w h e i sd e s c e n d i n gt o 0 b yl e m m a1 2 1 ，p a r a m e t e r i z e dp r o g r a m m i n gp r o b l e m ( 3 1 ) b e c o m e s ( 2 2 ) p r o b l e m ( 31 ) c a , nb es t a t ea 8 m 。i n ，( 山) s t ，o ( w ) 0 ，f 3 2 ) h ( w ，幻= 0 i t sk k ts y s t e mi s v ，( 伽) + v 雪( 叫) ”+ v h ( w ，t ) a = 0 ， ( 伽，t ) = 0 ， ( 3 3 ) 矿互( 凹) = 0 ，v 0 ，蚕( 叫) s0 ， w h e r ea r ”十”2 ，口兄? 1a r em u l t i p l i e r s ，a n dv = d i a g ( v ) w h e n ti sd e s c e n d i n gt o0 ， b yl e m m a1 2 1 ，( 3 3 ) i st r a n s f o r m e da s 眦垒f v ，( 呐们鹫门灶、j = 0 删引哪3 4 ) y 参( 叫) t h em a p p i n gh ： r “十2 m + m 1 + 2 m 2 r “+ 2 m + m l + 2 m 2i ss u f f i c i e n ts m o o t hw i t hr e s d e c tt o 【w ，u ，a ) ( 3 4 ) i st h ek - k - ts y s t e m f o rp r o b l e m ( 2 2 ) 州o w ，w et u nt oc o n s t r n c tah o m o t o p ye q u a t i o nf o rs o l v i n gt h eb i l e v e l p r o g r a m m i n g p r o b l e m w ed e f i n eah o m o t o p ye q u a t i o nf o rb l p p ： 驯固垒f ( 1 _ 砷一“叫引 批y 砷“一扩1 = o ，( 3 5 ) v o ( w ) 一t v ”o ( w o ) ”! 黑。口= ( 叫， ，a ) r ，o g = ( 叫o ， o ) r ，( 0 ，1 】，w = ( 为y ，乱) r n + m r ? ：，。兄? ，a r ”+ ，a n du = d i a g ( u ) ，v = d i a g ( v ) 一 1 1 l 。? m a 1 3 1 f o r n y g i v ，e no g 、，= o ， o ) q l ( 1 ) 置鼻，t h e nt h ee q u a t i o nh (o，oo，1)：0ha snu n i q u es o l u t i o n0 = f o o ，0 ) t 。 7 w o r kr e p o r t o r p o s t d o c t o r a l ，f u d a nu n i v e r s i t y 5 p r o o fw h e nt = 1 ，( 3 5 ) b e c o m e s v h ( w ，1 ) a + w 一叫o = 0 ， 危( 叫，1 ) = 0 ， y 耍( ) = v o 互( 加o ) b y m ) m a x o ，m p ) 玎0 pi s nr e g u l a rv a l u eo f 西，