（应用数学专业论文）半无限规划离散化问题超线性收敛的模松弛可行方向法.pdf

半无限规划离散化问题超线性收敛的 模松弛可行方向法 摘要 近年来，半无限规划因其广泛的应用前景逐渐成为研究热点。尤其是九 十年代以来，无论在算法理论还是执行算法方面，都取得了很大进展。许多作 主者基于不同的技术给出了许多有效算法。离散化方法就是其中之一，这类 算法主要通过较细地离散连续变量的区间来逼近约束函数，从而将半无限规 划问题离散后转化为约束较多的约束优化问题。对于离散后的约束优化问题， 一些作者在保持全局收敛和局部收敛的情况下，每次迭代时灵活运用一个适 当小的约束子集，多数情况下可以大大减少计算量。另一方面，由于可行方向 法是处理不等式约束优化的重要方法之一，所以一直是人们研究的热点。近 来，模松弛可行方向法被提出并得到了广泛的研究，而且已经证明这类算法 具有较好的收敛速度。 本文结合半无限规划离散化方法中每次迭代选择适当约束子集的技术和 模松弛可行方向法的思想，提出了一个求解半无限规划不等式约束离散化问 题超线性收敛的模松弛可行方向法。在每次迭代中，迭代点均可行，且通过选 择适当的约束子集减少计算量，仅解一个总有解的二次子规划即可获得主方 向。同时，高阶修正方向通过解一个仅含等式约束二次子规划来获得。此外， 在适当的条件下，我们证明了算法的全局收敛性和超线性收敛性。最后，数值 试验说明本文提出的算法是有效的。 关键词：半无限规划模松弛可行方向法全局收敛性超线性收敛性 as u p e r l i n e a r l yc o n v e r g e n tn o r m r e l a x e d m e t h o do ff e a s i b l ed i r e c t i o n sf o r f i n e l yd i s c r e t i z e dp r o b l e m sf r o m s e m i i n f i n i t ep r o g r a m m i n g a b s t r a c t i nr e c e n ty e a r s ，s i n c es e m i i n 矗n i t ep r o g r a m m i n g ( s i p ) p r o b l e m sh a v ew i d ea p p l i c a t i o n b a c k g r o u n d ，m a n ye f b r t sh a v eb e e nm a d ei nt h er e s e a r c h e so fs i p e s p e c i a l l ys i n c e1 9 9 0 s ， t h er e s e a r c ho fs i ph a sm a d ea g r e a td e v e l o p m e n tb o t hi na l g o r i t h mc h e o r ya n dp e r f o r m i n g a l g o r i t h m m a n ya u t h o r sp r o p o s e dv a r i o u se 髓c t i v ea p p r o a c h e st os o l v et h i st y p eo f p r o b l e m s i np a r t i c u l a r ，t h em e t h o do fd i s c r e t i z a t i o ni sa m o n gt h e s ea l g o r i t h m s ，w h i c h c a na p p r o x i m a t ec o n s t r a i n tf h n c “o nb ym e a n so fp r o g r e s s i v e l y6 n e rd i s c r e t i z a t i o no fa n i n t e r v a lo fc o n t i n u o u sv a r i a b l e a c c o r d i n g l y ，s o l v i n gs i pp r o b l e mc a nb es u b s t i t u t e db y s 0 1 v i n gt h ed i s c r e t i z e ds e m i i n 6 n i t e ( d s i ) p r o b i e m ，w h i c hh a saa m o u n to fc o n s t r a i n t s a st od s ip r o b l e m ，s o m ea u t h o r ss u i t a b l yc h o o s ec o n s t r a i n ti n d i c e sa te a c hi t e r a t i o nw h i l e p r e s e r v i n gt h eg l o b a la n dl o c a lc o n v e r g e n c e ，w h i c hm a yl e a dt os u b s t a n t i a lc o m p u t a t i o n a l s a v i n g 0 n 七h eo 乞h e rh a n d ，t h em e t h o do ff e a s i b l ed i r e c t i o n s ( m f d ) i sa ni m p o r t a n t m e t h o df o rs o l v i n gi 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 ns i n c en o r m - r e l a x e dm e 协o do f f e a s i b i ed i r e c t i o ni sp r e s e n t e d ，i th a sb e e nf u r t h e rs t u d i e da n da p p l i e dw i d e l y m o r e o v e r ，i t i ss h o w nt h a tt h en o r m r e l a x e dm e t h o do ff e a s i b l ed i r e c t i o nh a sg o o dc o n v e r g e n c es p e e d i nt h i sp a p e r ，c o m b i n i n gt h et e c h n i q u eo fu p d a t i n gd i s c r e t i z a t i o ni n d e xs e ta te a c hi t e r a t i o na n dt h ei d e ao ft h en o r m r e l a x e dm f d ，w ep r e s e n taa l g or i t h mf o rs 0 1 v i n gi n e q u a l i t y c o n s t r a i n t e dd s ip r o b l e m sf r o ms i p a te a c hi t e r a t i o n ，t h ei t e r a t i o np o i n ti sf e a s i b l ea n d t h em a i n $ e a r c hd i r e c t i o ni sc o m p u t e db ys o l v i n go n l yo n ed i r e c t i o n 矗n d i n gs u b p r o b l e m ， i e jaq u a d r a t i cp r o g r a m m i n g ，a n ds o m ea p p r o p r i a t ec o n s t r a i n t sa r ec h o s e nt or e d u c et h e c o m p u t a t i o n a lc o s t ah i g h o 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 ga n o t h e r q u a d r a t i cs u b p r o b l e mw i t ho n l ve q u a l i c yc o n s t r a i n t s u n d e rs u i t a b l ec o n d i t i o n s ，t h ep r o p o s e da l g o r i t h mi sp r o v e dt op o s s e s st h eg l o b a lc o n v e r g e n c ea n ds u p e r l i n e a rc o n v e r g e n c e f i n a l l y ，s o m ee l e m e n t a r yn u m e r i c a le x p e r i m e n t sa r er e p o r t e d k e yw o r d s ：s e m i i n i n i t ep r o g r a m m i n g ；n o r m r e l a x e dm e t h o do ff e a s i b l ed i r e c t i o n ；g l o b a lc o n v e r g e n c e ；s u p e r l i n e a rc o n v e r g e n c e 皇查兰垫圭兰竺篁圭 圭垄竺堡型垒堡丝望矍堡垒竺些竺竺堡垒丝! 堑奎鱼壅 l 1 i n t r o d u c t i o n i nt h i sp a p e r ，w ec o n s i d e rt h es e m i i n 6 n i t ep r o g r a m m i n g ( s i p ) p r o b l e ma sf o l l o w s 肿 霉端妪。， ， s tq f n l l i o ) oi s 印p r o p r i a t e l ys m a u t h o u 曲s u c l la na p p r o a c hc a n 卸s u r ec o n v e r g e n c e ，j tm a yp r o d u c e s u b p r o b l e m sw i t ha nu n d u l yl a r g en u m b e ro fc o n s t r a i n t sw h e nt h ed i s c r e t i z a t i o ni sv e r y 6 n e f b r t u n a t e i y ，i ti ss h o w ni n 1 6 j h a t ，t h en u m b e ro f c o n s t r a i n t su s e di nt h es u b p r o b i e m s c a nb ef h r t h e rr e d u c e dw i t h o u tj e o p a r d i z i n gg l o b a lc o n v e r g e n c e i nf a c t ，s u c has c h e m e 【1 6 i si n s p i r e db yt h eb u n d l e t y p em e t h o d so fn o n d i n b r e n t i a b l eo p t i m i z a t i o n ( s e e ，eg f 1 9 ，2 叫) s p e c i 五c a y ，a ti t e r a t i o n 七，t h es e a r c hd i r e c t j o n 扩i sc o m p u t e du s i n gas u j t a b l e s u b s e tq o fq a f t e ran e wi t e r a t ez o + 1h a sb e e no b t a i n e d ，an e ws e tq k + 1w h i c hi st h e d i s c r e t i z a t i o ni n d e xs e to ft h ec o n s t r a i n t s ，i st ob eu s e di nt h ec o m p u t a t i o no ft h es e a r c h d i r e c t i o nd + a ti t e r a t i o n 七十1 s u c hq + 1i sc o n s t r u c t e db yi n c l u d i n g ( i ) a 1 1u n s u c ht h a t ( z 2 + 1 ，u ) = 0 ( ie ，t h e “a c t i v e ”c o n s t r a i n t s ) ；( i i ) a l lu q w h i c ha f f e c t e dt h e c o m p u t a t i o no ft h es e a r c hd i r e c t i o nd 2 ；a n d ( i i i ) a l lu q ，i fi te x i s t s ，w h i c hc a u s e da s t e pr e d u c t i o ni nt h ec u r v es e a r c ha ti t e r a t i o n 后 i np r a c t i c e ，( i ) i su s e dt oe n s u r et h a td i saf 色a s i b l ed i r e c t i o n ，a n d ( i i ) 一( i i i ) a i dt oa v o i dz i 哥z a g g i n go ro t h e rj a m m i n gp h e n o m e n a ( s e e 1 6 】) u n f o r t u n a t e l y ，f o ra 丘x e dl e v e lo fd i s c r e t i z a t i o n ，t h ea l g o r i t h m si n 【1 2 ，1 6 e x h i b i t a tb e s tal i n e a rr a t eo fc o n v e r g e n c e s o m ea u t h o r sa t t e m p tt oa p p l yt h es e q u e n “a l q u a d r a t i cp r o g r a m m i n g ( s q p ) s c h e m e s ，w h i c he x h i b i tf a s tc o n v e r g e n c e ，t os o l v et h e d i s c r e t i z e dp r o b l e mf r o ms i p ，a n dm a k es o m ea c h i e v e m e n t s i nf 1 4 i ；t h ef e a s i b l es e 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 ( f s q p ) 一t y p ea l g o r i t h mi se x t e n d e dt os o l v et h ed i s c r e t i z e d p r o b l e mf r o ms i p ，w h i c hp o s s e s s e ss u p e r l i n e a rc o n v e r g e n c e h o w e v e r ，i tn e e dt os 0 1 v e t h r e eq u a d r a t i cp r o g r a m m i n g ( q p ) p r o b l e m sa te a c hi t e r a t i o nt h ef o r m e rt w oq p sa i d t oy i e i dt h em a i ns e a r c hd i r e c t i o n ，w h i c hi sa c c o m p i i s h e db yt h ec o n v e xc o m b i n a t i o no f t h es o l u t i o n sd 0a n dd oo ft h et w oq p s t h ec o 伍c i e n tpo ft h ec o n v e xc o m b i n a t i o nn e e d t ob ea d j u s t e da te a c hi t e r a t i o n t h el a t t e rq pi su s e dt og e n e r a t eah i g h + o r d e rc o r r e c t i o nd i r e c t i o nt oe n s u r ef 拈tc o n v e r g e n c e t h u s ，e v e nj ft h ee x t e n d e df s q pa l g o r i t h mh a s s o m eg o o dp r o p e r t i e s ，i tn e e dt oc o s te x p e n s i v ec o m p u t a t i o n i np r a c t i c e ，t h ec o n v e r g e n c e p r o p e r t yo ft h ee x t e n d e df s q p t y p ea l g o r i t h mi sr e l a t e dt oc o n s t r u c t i n go n ed i r e c t i o n f i n d i n gs u b p r o b l e m ( d f s ) a n dc h o o s i n gi t sc o n s t r a i n t ss u i t a b l y 皇查兰塑圭兰堡垒塞童垄堡垫型查堡些望堡堡垒些些竺竺堡垒丝三堑童鱼童 3 0 nt h eo t h e rh a n d ，i nr e c e n t ”a r s ，m a n ye 舫r t sh a v eb e e nm a d eo nt h er e s e a r c h e s o fm f d ，w h i c hi sa ni m p o r t a n tm e t h o df o rs o l v i n gt h ef o l l o w i n gi n e q u a l i t yc o n s t r a i n e d o p t i m i z a t i o n 。 m i n ，( z ) s t 卯( z ) so ，j ，= l ，2 ，m ) ， w h e r ez 兄“a n dt h ef u n c t i o n s ， 毋0 ，) ：尼1 - ra r ea l lc o n t i n u o u s l yd i f f e r e n t i a b l e t h et h e o r e t i c a lb a s i sf o rm f dw a so r i g i n a l l yd e v e l o p e db yz o u t e n d q k 2 1 】l a t e r ， r b p k i s 一、，e i n o t t s 【2 2 】a n dp i r o n n e a u p o l a k 【2 3 1i m p r o v e dt h ee a r l ym f da n dt h em a i n i m p r o v e m e n ti nt h ed f si n1 9 9 4 ，c a w o o da n dk o s t r e v ag e n e r a l i z e d 2 3 】a n dp r e s e n t e d an o r m r e l a x e dm f da l g o r i t h m 2 4 f 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 np r o b l e mp s u b s e q u e n t ly jc h e na n dk o s t r e v a 【2 5 】g e n e r a l i z e dt h en o r m r e l a x e dm f d 【2 4 】b yi n t r o - d u c i n gm o r ep a r a m e t e r sw h i c h c a nb ea d j u s t e dt os p e e du pt h ec o n v e r g e n c e ，i nw h i c ht h e d f sh a s t h e f o r mo f m i nz + 矿风d d f s s t v ，( z ) 1d 7 0 z ， 卯( z 2 ) + v ( z 2 ) 1d s z ， j j ， w h e r e ，7 ，( j ，) a r ea l lp o s i t i v ec o n s t a n t s ，a n d 凰i sap o s i t i v ed e i n i t em a t r i ) 【t h e a l g o r i t h mi ss h o w nt ob es u p e r l i n e a r l yc o n v e r g e n t t h eg e n e r a l i z e di v i f dw a sf u r t h e r s t u d i e db yk o s t r e v aa n dc h e n 【2 6 】，l a w r e n c ea n dt i t s 【2 7 ，z h ua n dz h a n g 【2 8 l ，j i a n ， z h e n g ，h ua n dt a n g 【2 9 _ i nf a c t ，【2 7 】p r e s e n t e dt h ef 0 1 l o w i n gq p ( i e ，d f s ) t oo b t a i nt h em a i nd i r e c t i o n a te a c hi t e r a t i o n g i v e nai t e r a t ep o i n tz 2i nx = z i 卯( z ) 茎o ，j = 1 ，2 ，m ，a s y m m e t r i cp o s i t i v ed e 矗n h em a t r i xh ka n d an o n n e g a t i v es c a l a rm ，t h eq ph a st h ef o r m o f m i n 矿凰d + 。 q ps t v ，( 妒) 1d sz ， 野( z ) + v 9 j ( 一) 丁d 曼啦z ，j = 1 ，2 ，一，m ， w h e r ezi sa na d d i t i o n a ls c a l a rv a r i a b l e ，a n dt h ep a r a m e t e r 叶ka s s o c i a t e dw i t hz 2 i su s e d t oe n s u r eg l o b a la n ds u p e r l i n e a rc o n v e r g e n c ei nf a c t ，t h eg e n e r a l l z e dn o r m r e l a x e dm f d 【2 5 】a n d 2 7 c a ns p e e du pt h ec o n v e r g e n c eb e t t e rt h a n 2 4 i nt h i sp a p e r ，c o m b i n i n gt h ei d e ao ft h en o r m r e l a x e dm f d 【2 5 ，2 7 1w i t hc h et e c h n i q u e o fu p d a t i n gd i s c r e t i z a t i o ni n d e xs e t 1 4 ，1 6 ，w ep r e s e n tan e wa l g o r i t h mf o rs 0 1 v i n gd s i ( 12 ) f o ms i p t h em a i nd i r e c t i o no ft h ep r o p o s e da l g o r i t h mi so b t a i n e db ys o l v i n go n l y o n ed f sa n dah i g h o r d e rc o r r e c t i o nd i r e c t i o ni so b t a i n e db ys o l v i n ga n o t h e rq u a d r a t i c s s u b p r o b l e mw i t ho n l ye q u a l i t yc o n s t r a i n t s t h em a i nf e a t u r e so ft h en e wa l g o “t h mi n c l u d e ( i ) af e a s i b l ed i r e c t i o no fd e s c e n t f o rp r o b l e m ( 1 2 ) i so b t a i n e db ys o l v i n go n l yo n ed f s ；( i i ) t h et e c h n i q u eo fu p d a t i n g 皇叁兰塑圭兰竺篁塞兰垄堡垫型堂墼些望望丝垒些些竺竺堡垒丝! 堡童鱼童 a d i s c r e t i z a t i o ni n d e xs e tc a nr e d u c et h ec o m p u t a t i o n a lc o s t ；( i i i ) ah i g h o r d e rc o r r e c t i o n d i r e c t i o nc a nb eo b t a i n e db ys o l v i n gaq u a d r a t i cs u b p r o b l e mw i t ho n l y e q u a l i t yc o n - s t r a i n t s ；( i v ) u n d e rw e a k e rc o n d i t i o n ss u c ha sm f c q ，t h ep r o p o s e da l g o r i t h mp o s s e s s e s t h ew e a k e r9 1 0 b a lc o n v e r g e n c e ；( v ) t h es u p e r l i n e a rc o n v e r g e n c eo ft h ep r o p o s e da l g o r i t h m i so b t a i n e du n d e rl i c qa n do t h e rs u i t a b l ea s s u m p t i o n s t h ep a p e ri so r g a n i z e da sf o l l o w s i nt h en e x ts e c “o n ，w ep r e s e n tt h ed e t a i l so f o u ra l g o r i t h ma n dd i s c u s si t sp r o p e r t i e s n e x t ，t h ew e a k e rg l o b a lc o n v e r g e n c ei sp r o v e d i ns e c t i o n3 i ns e c t i o n4 ，w ea n a l y z et h es t r o n ga n ds u p e r l i n e a rc o n v e r g e n c eo fo u r a l g o r i t h m s o m ee l e m e n t a r yn u m er i c a le x p e r i m e n t sa r er e p o r t e di ns e c t i o n5f i n a l l y 】 s o m ec o n c l u d i n gr e m a r k sa r eg i v e ni ns e c t i o n6 2 d e s c r i p t i o no fa l g o r i t h m f b rt h es a k eo fa n a l y s i s ，d e 6 n et h ef 色a s i b l es e to fd s i ( 12 ) a s x = z r “i ( z ，u ) o ，b b q ) l e tp o i n tz x ，q q ，w ei n t r o d u c et h ef o l l o w i n gd f s d f s ( ，风，吼，仉) ( 2 1 ) 西( z ，o ) + v 。咖 ，u ) r d ，叩z ，v c j q t ， w h e r e 加，) a r ea up o s i 乞i v ec o n s t a n t s ，a n d 玑i sap o s i t i v ep a r a m e t e r a s s o c i a t e d w i t hz i np a r t i c u l a r ，叩kp l a y sa ni m p o r t a n tr o l ei na s s ur i n gt h eg l o b a lc o n v e r g e n c ea n d t h ec o n v e r g e n c er a t eo ft h ep r o p o s e da l g or i t h m f b rn o t a t i o n “c o n v e n i e n c e 、w ed e n o t et h es o l u t i o no fd f s ( z i ，日k ，q ，卵k ) a sf b l l o w s ( d ，。k ) 竺( d ( z 2 ，丑i ，q 女：仉) ，z ( z 2 ，日i ，q k ，q ) ) i na d d i t i o n ，t h ef o i l o w i n gb a s i ca s s u m p t i o n sa r en e c e s s a r yi nt h i sp a p e r - a s s u m p t i o na 1 吼e 凡n c “o n s ，：r “- ro 礼d 毋( ，u ) ：r “_ r ，u q o r e c o n 打l “o “s 西d i 扩色r e n 艇凸6 f e l e tt h es e to fa c t i v ec o n s t r a i n t sf b rap o i n tz xb ed e n o t e db y q 。d ( z ) 垒 u q it j j ( z ，u ) = o ) ( 22 ) a s s u m p t i o na 2 s u p p d s e 矾o 执em o 伽血s o 州。n f r o m o 口i 如g d n s m 饥q u o f 访c o “。n ( m f c q ) d f d so to n yz x ，i e ， e r e8 z i s s 口u e c t d rd r “s 让c 8 v z 毋( z ，c u ) t d 0 ，v u q 。( z ) z d 加 巩 一 矿勺 1 2 勺 z 弘八 v嘶呲 广西大学硕士学位论文半无限规划离散化问题超线性收敛的模松弛可行方向法 5 t bd e s c r i b et h em a i nc h a r a c t e ro ft h ed f s ( 2 1 ) ，w eg i v et w o1 e m m a sa sf o l l o w s l e m m a2 1 三e xo n dq k q s 却p o s e 砘口地em n 打妇日女i ss 掣m m e 而cp o s i t 妇e d 币n i e n d