求解非凸半定規劃問題的一種非線性Lagrange方法.pdf

1、大連理工大學碩士學位論文求解非凸半定規劃問題的一種非線性Lagrange方法姓名：張杰申請學位級別：碩士專業：運籌學與控制論指導教師：張立衛20070601求解非凸半定規劃問題的一種非線性L a g r a n g e 方法A N o n l i n e a rL a g r a n g eM e t h o d f o rS o l v i n g N o n c o n v e xS e m i d e f i n i t eP r

2、 o g r a m m i n g P r o b l e m sA b s t r a c tC l a s s i c a l L a g r a n g i a n si nw h i c ht h e m u l t i p l i e r v e c t o r sa n dt h ec o n s t r a i n tm a p p i n g sa r ei n v l o v e di nl i n e a rw a

3、 y s ，p l a ya ni m p o r t a n tr o l e i ns t u d i e so nt h ed u a l i t y t h e o r i e so f c o D , -v e x p r o g r a m m i n g s ，e s p e c i a l l yt h a to fl i n e a rp r o g r a m m i n g sa n dq u a d r a t

4、i cp r o g r a m m i n g sw h i c h s h o u l db e e x p r e s st h r o u g h C l a s s i c a lL a g r a n g i a n s ．B u t i nn o n c o n v e x p r o g r a m m i n g s ，t h ep r i m a l p r o b l e m sa n d t h ed u a l

5、 i t y p r o b l e m sw h i c ha r e b a s e do nC l a s s i c a lL a g r a n g i a n sh a v ed u a l i t yg a p s ．S om a n y s h o l a r sa r eb e c o m em o r ea n dm o r ei n t e r e s t e d i ns t l l d y i n go nt

6、h e v a r i e so fC l a s s i c a lL a r a n g i a n s ．N o n l i n e a rL a g r a n g i a n sa r ev a r i a n t so ft h e c l a s s i c a lL a g r a n g i a n ．i n w h i c ht h e m u l t i p l i e rv e c t o r s o rc o

7、n s t r a i n tf u n c t i o n sa r e i n v o l v e di nn o n l i n -e a rw a y s ．N o n l i n e a rL a g r a n g em e t h o d sa r e d u a lm e t h o d s b a s e d o nn o n l i n e a r L a g r a n g i a n sf o rs o l v

8、i n go p t i m i z a t i o np r o b l e m s ．A sd u a lm e t h o d s u s u a l l yr e q u i r en or e s t r i c t i o n so nt h ef e a s i b i l i t yo fp r i m a lv a r i a b l e s ，n o n l i n e a rL a g r a n g em e t

9、 h o d sa r e p l a 舜n gi m p o r t a n t r o l e si n s o l v i n gc o n s 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 ．T h i sd e s s e r a t i o na t t e m p t st oe x t e n dt h i sm e t h o d t os o l v i n

10、gN C S D P f o rt h ep r o f i c i e n c yo fn o n l i n e a rl a g r a n g e i a na l o g r i t h ms o l v -i n gn o n l i n e a rp r o g r a m m i n ga n de x t e n s i v eu t i l i z a t i o n o fN C S D P i np r a c

11、t i c a lp r o b l e m s ．w ec o n s t r u c ta d u a la l o g r i t h mb a s i n go na n o n l i n e a rl a g r a n g i a nf o rs o l v i n g N C S D P a n dt h e np r o v e i t sl o c a lc o n v e r g e n c e ．黜i st os

12、 a y ．t h e s e q u e n c ep r o d u c t e db y t h e a l o g r i t h mc o n v e r g et oK K T p o i n t so fp r i m a lp r o b l e m ．A n d a tl a s tw e e s t a b l i s ht h ee r r o re s t i m a t ef o r m u l a ．t h

13、e m a i nr e s u l t s ，o b t a i n e di nt h i s d i s s e r a t i o n ，m a yb es u m m e r i z e da sf o l l o w s ：1 ‘C h a p t e r 2i sd e v o t e dt os u m m a r i z i n gt h eo p t i m a lc o n d i t i o n so fN C

14、S D P w h i c ha r ei n d i s p e n s a b l et ot h e n e x tc h a p t e r ．T h i sc h a p t e r a tf i r s ti n t r o d u c e st h eo p t i m a lc o n d i t i o n so fa b s t r a c tc o n s t r a i n to p t i m i z a t

15、i o n ．A n dt h e nu t i l i z e st h o s ec o n d i t i o n st ot h e N C S D P ．2 ．C h a p t e r 3i sd e v o t e d t ob r i n g i n g f o r w a r d a n o n l i n e a r L a g r a n g e a l g o r i t h m f o rN C S D Pp

16、r o g r a m m i n g a n d p r o v i n g i t sc o n v e r g e n c e ．N a m e l y , u n d e rs o m e m i l da s s u m p t i o n s ，i t i sp r o v e dt h a tt h e r ee x i s t sa t h r e s h o l do ft h ep e n a l t yp a r

17、a m e t e r s u c ht h a tt h e s es e q u e n c e sg e n e r -a t e db yt h en o n l i n e a ra l g o r i t h ml o c a l l yc o n v e r g et ot h eK K T p o i n t o fN C S D P w h e n t h ep e n a l t yp a r a m e t e r

18、 i sl e s s t h a nt h et h r e s h o l d ．M o r e o v e r ，w e e s t a b l i s ht h ee r r o rb o u n d o ft h e s o l u t i o n sw i t h t h ep e n a l t yp a r a m e t e r ．K e yW o r d s ： N o n c o n v e xS D P ；T h