互補問題的乘子法研究.pdf

1、碩士學位論文 萋是拿垂i冬舌內(nèi)蒙古大學 薹十童之圣}萋內(nèi)蒙古大學碩士學位論文S T U D Y o N T H E M U I J T I P L I E R M E T H O D S F o RC o M P L E M E N T A R I T Y P R o B L E M ST h e c o m p l e m e n t a r i t yp r o b l e m ( C P ) i s ac l a s so fi

2、m p o r t a n to p t i m i z a t i o np r o b l e m s ，w h i c h h a v ei m p o r t a n ta p p l i c a t i o n s i ne n g i n e e r i n g ，e c o n o m i c sa n d t r a f f i ce q u i l i b r i u m ．At h e o r e t i c a l

3、 f r a m e w o r k o fac l a s s o f L a g r a n g i a n m u l t i p l i e rm e t h o d s f o rC P w 硇e s t a b l i s h e di n ( [ s 2 l 一【5 5 】) ．皿l i 8 m e t h o d i s ac l a s s o fm e t h o d sw h i c h i n t r o d u

4、 c en o n s m o o t h e q u a t i o n sc o n t s ．i n i n gL a g r a n g i a nf u n c t i o ne q u i v a l e n tt oC P a n dc o n s t r u c ts m o o t hm e r i t f u n c t i o nc o n t a i n i n gm u l t i p l i e rp a r

5、 a m e t e r s ．S ow ec a n r e f o r m u l a t eC P 船m i n i m i z i n gp r o b l e m o rn o n l i n e a re q u a t i o n s ． M u l t i p l i e rm e t h o d sf o rC P e r e s t u d i e d i nt h i s t h e s i s ．T w on 洲

6、m u l t i p l i e rm e r i tf u n c t i o n sa r ed i s c u s s e d ．1 ．An e wN C P f u n c t i o no fC P i s p r o p o s e d ．E q u i v a l e n ts e m i s m o o t he q u a t i o n sr e f o r -m u l a t i o n o f C P i 8

7、o b t a i n e db y t h i ss t r o n gs e m i s m o o t hN C P f u n c t i o n ．W i t h t h e c o m b i n a -t i o no fm u l t i p l i e rm e t h o d sa n d s e m i s m o o t hN e w t o nm e t h o d s ，8 n e wg e n e r a

8、l i z e dN e w t o nm e t h o db a s e d o n t h e n e wm u l t i p l i e rm e r i t f u n c t i o n i sg l v e m 撇m e t h o d t r e a t st h e m e r i tf u n c t i o n 嬲s q u a r e8 皿o f t h ed e t e r m i n a t es e m

9、i s m o o t h e q u a t i o n s ．G e n e r a l i z e dN e w t o nd i r e c t i o n8 8a d e s c e n td i r e c t i o n Ⅱ珀婦t h et h o u g h to fa l g o r i t h md e a ra n d s i m p l i f i e st h es t r u c t u r ea n d t

10、 h e o r e t i c a l a n a l y s i so fa l g o r i t h m ．G l o b a l c o n v e r g e n c e ，l o c a l s u p e r l i n e a rc o n -v e r g e n c e ，q u a d r a t i cc o n v e r g e n c ea n df i n i t et e r m i n a t i

11、o nf o rn o n d e g e n e r a t i v el i n e a r c o i n -p l e m e n t a r i t yp r o b l e m sa r ep r o v e du n d e r t h e a s s u m p t i o nt h a tF i s a u n i f o i _ mp - f u n c t i o n ．N u m e r i c a lr e s

12、 u l t si n d i c a t et h i sa l g o r i t h m i s p r a c t i c a l l ye f f i c i e n t ．2 ．An e w s m o o t hm u l t i p l i e rm e r i tf u n c t i o ni sp r o p o s e d ．B a s e d o nt h i s n e wm e r i tf u n c t

13、 i o n ．d e s c e n td i r e c t i o na n d m u l t i p l i e ra d j u s t i n gm e t h o da r ec o n s t r u c t e d ．T h ee t r u c -t u r e o ft h i sm e r i tf u n c t i o ni 呂s i m p l e ．G l o b a lc o n v e r g e

14、n c e ．1 0 c a l s u p e r l i n e a rc o n v e r g e n c ea n dq u a d r a t i cc o n v e r g e n c ea r eo b t a i n e du n d e r t h ea s s u m p t i o nt h a tF i s au l l i f o r I l l p -f u n c t i o n ．F o rl i n

15、 e a rc o m p l e m e n t a r i t yp r o b l e m s ( L C P ( q ，∽) ，f i n i t et e r m i n a t i o n o ft h ea l -g o r i t h mi sp r o v e du n d e rt h ea s s u m p t i o nt h a tM i s ap - m a t r i x ．E j ( t H 舊晚n u

16、 m e r i c a le x p e r i m e n t si n d i c a t et h i sM g o r i t h mi s e f f i c i e n t ．K E Y W o R D S C o m p l e m e n t a r i t y p r o b l e m s ，m u l t i p l i e rm e t h o d s ，g e n e r a l i z e dN e w -

17、t o nm e t h o d s , g l o b a lc o n v e r g e n c e ，l o c a ls u p e r l i n e a rc o n v e r g e n c e ，f m i t et e r m i n a t i o nS U B J E C T c L A s s Ⅱ’I c A T I o N ( C L ．) 0 2 2 1 ；( 1 9 9 1 M R ) 9 0 C 3