幾類特殊非凸規(guī)劃問題的分支定界算法.pdf

1、河南師范大學(xué)碩士學(xué)位論文幾類特殊非凸規(guī)劃問題的分支定界算法姓名：靳利申請學(xué)位級別：碩士專業(yè)：計(jì)算數(shù)學(xué)指導(dǎo)教師：申培萍20090401A B S T R A C TG l o b a l o p t i m i z a t i o n m e t h o d s r e s e a r c ht h e c h a r a c t e ra n d t h ec o m p u t a t i o n a lm e t h o d o f

2、t h e g l o b a l o p t i m a l p o i n t o ft h e n o n l i n e a r f u n c t i o no ns o m e r e g i o n ．T h e g l o b a l o p t i m i z a t i o np r o b l e m sh a v eb e e nv e r y e x t e n s i v ei ne c o n o m i

3、cp l a n ，e n g i n e e r i n gd e s i g n ，p r o d u c t i o nm a n -a g e m e n t ，t r a n s p o r t a t i o n ，n a t i o n a ld e f e n s e ，a n dS Oo n ．T h e b r a n c ha n d b o u n d a l g o r i t h mi so n e o ft

4、 h e f r e q u e n t l y - u s e da n d e f f i c i e n tg l o b a lo p t i m i z a t i o nm e t h o d s ，a n d i th a s b e e na h o tt o p i co fr e s e a r c hi n t h eg l o b a lo p t i m i z a t i o nf i e l d s i n

5、r e c e n ty e a r s ．T h eb r a n c ha n db o u n da l g o r i t h m sa r ep r o p o s e d b a s e do ns o m e k n o w n t h e o r i e sf o rg l o b a l l ys o l v i n gs e v e r a lc l a s s e so fn o n c o n v e xp r

6、o g r a m m i n g p r o b l e m s ．r e s p e c t i v e l y ．M a i nc o n t e n t sa r e a u sf o l l o w s ：F i r s t l y , ac o n i c a lb r a n c h - - a n d - - b o u n da l g o r i t h m i s p r o p o s e df o rt h e

7、s u mo fc o n c a v e -c o n v e xr a t i o sp r o b l e m o v e rac o n v e xs e t ．F i r s t ，t h ep r i m a lp r o b l e mi se q u i v a l e n t l y r e f o r -m u l a t e di n t o a n o n c o n v e xo p t i m i z a t

8、 i o np r o b l e mb yi n t r o d u c i n gn e w v a r i a b l e s ．N e x t ，ab r a n c ha n db o u n d a l g o r i t h mi sc o n s t r u c t e df o rs o l v i n gt h e e q u i v a l e n tp r o b l e m ．B yu s i n gc o n

9、 c a v e e n v e l o p e ，as e q u e n c eo fr e l a x a t i o nc o n v e xp r o g r a m m i n g p r o b l e m sa r e c o n s t r u c t e df o rs u p p l y i n gt h eu p p e rb o u n d si n t h ep r e s e n t e da l g o

10、r i t h m ．T h e n ，t h ek e yp r o b l e m s o fe s t i m a t i n gu p p e r b o u n d s a r ee q u i v a l e n tt ot h e s e q u e n c eo fr e l a x a t i o nc o n v e xp r o g r a m m i n gp r o b l e m sw h i c hd on

11、 o t c h a n g ei n s c a l ea n d c a nb es o l v e de f f i c i e n t l y ．S o ，t h e p r e s e n t e da l g o r i t h mm a yb ec o d e da n da p p l i e dt op r a c t i c a lp r o b l e m sm o r ee a s i l y ．I na d d

12、 i t i o n ，t h ec o n i c a lp a r t i t i o ni su t i l i z e df o rt h e p a r t i t i o n o ft h ep r e s e n t e d b r a n c ha n d b o u n d a l g o r i t h m ，a n d a p r o c e d u r e f o rt i g h t e n i n gt h

13、e u p p e rb o u n d i sd e v e l o p e d ．O u ra l g o r i t h mh a sl e s sv a r i —a b l e sa n dc o n s t r a i n t si n t h ec o m p u t a t i o np r o c e d u r ef o r o b t a i n i n gu p p e rb o u n d s ．S ow ec

14、 a n i m p r o v el a r g e l yt h ec o n v e r g e n c eo ft h e a l g o r i t h m ．N u m e r i c a le x p e r i m e n t ss h o wt h a tt h e c o m p u t a t i o n a le f f i c e n c yc a n b ei m p r o v e do b v i o u

15、 s l y b yu s i n g t h i st e c h n i q u e ，t h a t i s ，t h en u m b e r o fi t e r a t i o n ，a n dt h ee x e c u t i o nt i m eo ft h e a l g o r i t h mc a n b er e d u c e d s i g n i f i c a n t l y ．S e c o n d

16、l y , a c o n v e x i f i c a t i o nm e t h o d b a s e do na b r a n c ha n db o u n d s c h e m e i sp r e s e n t e df o rt h eg e n e r a l i z e dg e o m e t r i cp r o g r a m m i n gw i t hf r e e v a r i a b l e