（应用数学专业论文）不等式约束非线性minimax问题的可行广义单调线搜索sqp算法.pdf

不等式约束非线性m i n i m a x 问题的 可行广义单调线搜索s q p 算法 摘要 由于序列二次规划( s q p ) 算法具有快速收敛速度，所以它是求解光滑约束优 化问题的有效方法之一因此许多作者运用经典的s q p 方法来解决m i n i m a x 问 题，并且得到了一些有效的算法但许多解带约束m i n i m a x 问题的算法都应用罚 函数，是不可行类算法，这对于严格要求可行的问题是一个缺点，尤其在工程设 计方面而且所有的算法要么是纯粹单调的，要么是纯粹非单调的，算法没有 把单调和非单调的情形自动统一起来 本文讨论带不等式约束的非线性m i n i m a x 问题。结合模松弛可行方向法和非 单调线搜索技术，给出了一个新的可行广义单调线搜索序列二次规划算法在 每次迭代中，通过求解一个二次子规划得到一个可行下降方向为了克服m a r a t o s 效应，通过求解另一个二次子规划得到一个高阶修正方向作为结果，算法具有 全局和超线性收敛性特别地，用一个弱m f c q 代替线性无关约束规格( l i c q ) 得到算法的全局收敛性最后，用例子验证了算法的数值有效性 关键词：不等式约束m i n l m a x 问题广义单调线搜索可行s q p 算法 全 局收敛性超线性收敛性 中图分类号：0 2 4 1 f e a s i b l eg e n e r a l i z e dm o n o t o n el i n es e a r c hs q p a l g o r i t h mf o rn o n l i n e a rm i n i m a xp r o b l e m s w i t hi n e q u a l i t yc o n s t r a i t s a b s t r a c t s 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 ( s q p ) m e t h o di sa ne 尚c i e n tm e t h o df o rs o l v i n 屠s m o o t h c 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 sb e c a u s eo fi t sf a s tc o n v e r g e n c er a t e t h u sm a n ya u t h o r sh a v e a p p l i e dt h ec l a s s i c a ls q pm e t h o dt os o l v et h em i n i m a xp r o b l e m sa n dg o ts o m ee m c i e n ta l g o r i t h m s b u tm a l l ya l g o r i t h m sf o rm i n i m a xp r o b l e m sw i t hc o n s t r a i n t su s ep e n a l t yf u n c t i o n ，t h u st h e ya r en o t t h ef e a s i b l em e t h o d s ，w h i c hi sad r a w b a c l ( i ns o m es t r i c t l yf b a s i b l ec a s e s ，e s p e c i a l l yi nt h ee n g i n e 盯 i n gd e s i g n s a l s 0 1a ut h ea l g o r i t h m sf o rm i n i m a xp r o b l e m sa r ee i t h e rm o n o t o n eo rn o n m o n o t o n e ， a n dt h e ya r en o tu n 饵e da u t o m a t i c a l l m i nt h i 8p a p e r ，t h en o n h n e 缸m i n i m a x 矿o b l e m sw i 恤i n e q u a l i t yc o n s t r a i n t sa r ed i s c u s s e d w i t h t h eh e l po fn o r m - r e l a x e dm e t h o do ff e a 5 i b l ed i r e c t i o na n dt h en o n m o n o t o n el i n es e a r c ht e c h n i o u e w ep r e s e n tan e wf e a s i b l es q pa l g o r i t h mw i t hag e n e r a l i z e dm o n o t o n el i n e s e a r c h a te a c hi t e r a t i o n ，af e a s i b l ed i r e c t i o no fd e s c e n ti so b t a i n e db ys o l v i “gaq u a d r a t i cp r o g r a i n m i n g ( q p ) t 0 a v o i dt h em a r a t o se 乳c t ，ah i g ho r d e rc o r r e c t i o nd i r e c t i o ni sa c h i e v e db ys o l v i n ga n o t h e rq pa sa r e s u l t ，t h ep r o p o s e da l g o r i t h mh a s9 1 0 b a la n ds u p e r l i n e a rc o n v e r g e n c e e s p e c i a l l y ，t h eg i o b a lc o n v e r g e n c ei so b t a i n e du n d e raw e a km a n g a s a r i a n n o m o v i t zc o n s t r a i n tq u a l i 矗c a t i o n ( m f c q ) i n s t e a d o ft h el i n e a r l yi n d e p e n d e n tc o n s t r a i n tq u a l i 右c a t i o n ( l i c q ) a t1 a s t ，i t sn u m e r i c a le 髓c t i v e n e s si s d e m o n s t r a t e dw i t ht e s te x a m d l e s k e yw o r d s ：i n e q u a l i t yc o n s r a i n t s ；m i n i m a xp r o b l e m s ；g e n e r a l i z e dm o n o t o n el i n es e a r c h f e a s i b l es q pa l g o r i t h m ；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 苎皇查兰丝圭兰竺篁圭至重垒丝查! ! 垒些竺垫! 竺坚望翼竺至堑苎墨兰塑垒些奎皇竺苎童 1 i n t r o d u c t i o n i ti sv e r yc o n v e n i e n tt oe x p r e s ss o m e e n g i n e e “n gd e s i g np r o b l e m si nam i n i m a xf o r ma s f o l l o w s ( p ) m i n ，( z ) s t 毋( z ) o ，j j ( 11 ) w h e r ef ( z ) = m a x ( z ) ：i j ) w i t h = 1 ，2 ，m ) ，j = ( 1 ，2 ，m ) d e n o t et h e f e a s i b l es e to f ( p ) a sx = z ：野 ) o ，j j ) s i n c et h eo b j e c t i v ef u n c t i o nf ( z ) i sc o n t i n u o u sb u tn o n d i f r e r e n t i a b l ee v e ni ft h ef u n c t i o n s ( i ，) a r ea l ld i 舵r e n t i a b l e ，t h ec j a s s i c a lm e t h o d s f o rs m o o t ho p t i m i z a t i o np r o b l e m sc a n n o tb eu s e dd i r e c t l yt os o l 、r et h i sk i n do fc o n s t r a i n e dm i n i m a xp r o b l e m s i ti sw e l lk n o w nt h a tt h es q pm e t h o di so n eo ft h ee 伍c i e n tm e t h o d sf o rs o l v i n gs m o o t h c o n s t r a i n e do p t i 瑚j z a t i o np r o b l e m s ，b e c a u s ei th a sf a s tc o n 、r e r g e n c er a t e t h u s ，t h es q p m e t h o dp l a y sa ni m p o r t a n tr o l ei nh i 曲l yt i m e c o n s u m i n gs i m u l a t i o n ss o ，m a n ya u t h o r s h a v ea p p l j e dt h ej d e ao fs q pm e t h o dt op r e s e n te 矗色c t i v ea l g o r i t h m sf o rs o 】v i n gt h em i n i m a x p r o b l e m s ，s u c ha sr ，e f s 1 6 i nr e f 【3 】，t h em i n i m a xp r o b l e m sw i t h o u tc o n 5 t r a i n t sa r e d i s c u s s e dw i t h “n o n m o n o t o n e ”l i n es e a r c h r e f s 【4 a n d 5 u s ea p p r o p “a t ep e n a l t yf u n c t i o n a n da u g m e n t e dl a g r a n g i a nf o r m u l a t i o nt os o l v ed i r e c t l ym i n i m a xp r o b l e m sw i t he q u a l i 乞y a n di n e q u a l i t yc o n s t r a i n t s ，r e s p e c t i v e l 弘i nr e f s 4 ，5 ，t h ep e n a l t yp a r a m e t e rs e l e c t j o nr u l e i sv e r yi m p o r t a n t i n 4 】，t h ep e n a l t yp a r a m e t e ri sa d a p t i v e l ya d j u s t e d h o w e v e r ，i nt h e i n e q u a i i t y - c o n s t ra i n e dc a s e 【5 】，af u r t h e ra d j u s t m e n tf a c t o ri si n t r o d u c e df o re a c hc o n s t r a i n t r e f 【6 】i n c l u d e sg e n e r a lc o n s t r a i n t sa n di s ae x t e n s i o no f 【3 w i t ht h ef o u o w i n gf o r m m i nf 扛) ( p ) s t g ( z ) o ，j j ， 。( z ) = o ，i e w h e r ee = 1 ，m e ) s j m j l a rt ot h eg e n e r a lc o n s t r a i n e do p t i m i z a “o np r o b 】e m ，t h ed i r e c t i o n6 n d i n gs u b p r o b l e m ( d f s ) i n 【6 】a ti t e r a t i o np o i n t 妒h a st h ef o l l o w i n gf o r m m i n ；矿月j d + m a x v ( ) r d + 扛。) ：i ， s ，t 鲫( z ) + v 9 j ( 。2 ) 了1 d o ， j 工( 1 2 ) i ( z ) + v h i ( z ) 1d = o ， i e t h ef e a s i b l es e to fs u b p r o b l e ma b o v em a yb ee m p t y ，t h u s1 6 g a eam o d i f i e ds u b p r o b l e m ， b u tt h ea n a l y s i si n 【6 】i ss t i l lc o r r e s p o n d i n gt o ( 1 2 ) w h a t sm o r e l l i ua n dy u a n 【7 1g a v e ac o u n t e r e x a m p l et os h o wt h a tt h em o d 汾e ds u b p r o b l e mm a yb ei n c o m p a “b l e s u p e r l i n e a r c o n v e r g e n c ei so b t a i n e di n 3 6 w i t hd i 行e r e n tt e c h n i q u e st oo v e r c o m et h em a r a t o se f f e c t f 8 】b u t ( 4 6 】a 儿u s ep e n a l t yf u n c t i o n sa n dt h ea l g o r i t h m sa r en o tt h em e t h o do ff e a s i b l e 妄皇叁兰塑圭兰竺篁叁至至耋塑查! ! 垒些竺堡! 竺竺望矍竺! 堡耋苎兰塑垒堡童耋里呈墨兰 2 d i r e c t i o n ( m f d ) s i n c et h ei t e r a t i o n sm a yn o tb ef e a s i b l et h o u g ht h e ym o v et o w a r d sf e a s i b l e s e t ，w h i c hi sad r a w b a c ki ns o m es t r i c t l yf e a s i b l ec a s e s ，e s p e c i a u yi nt h ee n g i n e e r i n gd e s i g n s s i n c et h ei d e ao ft h i sp a p e rh a ss o m e t h i n gt od ow i t ht h em f d ，e s p e c i a l l yt h ei d e ao f t h en o r m r e l a x e dm f d ，w e 矗r s tr e m i n dt h ei d e aa n di t sp r o g r e s so ft h em f d m f di sa l s oa ni m p o r t a n tc l a s so fm e t h o df o rs o l v i n gp r o b l e m ( p ) w i t hs i n g l el e v e l o b j e c t i v ei e ，m = 1 ( s u p p o s et h a tm = 1 i nt h i sp a r a g r a p h ) m f dh a sb e e ns t u d i e dw i d e l y b yan u m b e ro fa u t h o r s ，b u ta l m o s te a c hi m p r o v e m e n ti nm f d o c c u r r e di nt h em o d i f y i n go f d f sm f dw a so r i g i n a l l yp r o p o s e db yz o u t e n d i j k 【9 ，ag o o dp r o p e r t yo ft h ez o u t e n d 巧k s 4 f ) i st h a taf b a s i b l ed j r e c t j o no fd e s c e n tc a nb eo b t a i n e db ys o 】、r i n go n e1 i n e a rp r o g r a m h o w e 、r e r ，、，o l f 色 1 0 1p r o v e dt h a tz o u t e n d i j k sm f d d o e sn o tp o s s e s sg l o b a lc o n v e r g e n c ew i t h ac o u n t e r e x a m p l e l a t e r ，t o p k i s - ，e i n o t t 【1 1 】m o d i 矗e dz o u t e n d u k sm f db ym o d i f y i n gt h e d f st h em o d i 6 e dd f sa s s u r e st h a tt h es e q u e n c eo fp o i n t sg e n e r a t e db yt h ea l g o r i t h m c o n v e r g e st oaf r i t zj o h np o i n ta n dh a st h ef o l l o w i n gf o r m ： i i 儿i lz ( z ，d 1 m s t v ，1 ( 扩) 。d 曼z ， 幻( z ) + v 卯( z 2 ) 1d 曼z ， j j d s ， w h e r esi sas p e c i a ls e tb o u n d i n gt h ed i r e c t i o nda n dzi sa na u x i l i a r yv a r i a b l e h o w e v e r ，t h e r o p k i s v 色i n o t t sm f dd o e sn o tc o n v e r g ei i n e a r i ye v e nu n d e rc e r t a i nc o n v e x i t ya s s u m f t i o n s 【1 2 卜 b a s e do nt o p k i s v e i n o t t sm f d ，p i r o n n e a u p o l a k sm f d 1 3 】f u r t h e ri m p r o v e dt h e m f d 1 1 】s u c h 曲a tt h ed f s h a st h ef o l l o w i n gf o r m 嘶z + 洲 2 s t v ( 扩) 1dsz ， 缈( 扩) + v 毋扛) 1d 曼z ， j ， b u t ，t h ep i r o n n e a u p o l a k sm f do n l yh a sl i n e a rc o n v e r g e n c e m o t i v a t e db yt h ep i r o n n e a u p 0 1 a k sm f d ，c a w o o da n dk o s t r e v a 1 4 p r o p o s e dan o r m r e l a x e dm f d a n dt h e i rd f si s a s f 0 1 1 0 w s m i nz + ；护。b k d s t v ( 扩) 1d 兰z ， 卯( z 。) + v 鲫( 扩) 1d 。，j z w h e r e i sap o s i t i v ec o n s t a n t u n d e rc e r t a i na s s u m p t i o n s ，t h ec a w o o da n dk o s t r e v a s m e t h o dh a sg l o b a lc o n v e r g e n c e ! 吣s p e e du pt h ec o n v e r g e n c er a t e ，c h e na n dk o s t r e v a 【1 5 皇叁兰丝圭兰竺篁圭至兰查竺查! ! 垒兰竺垫垫! 竺望塑竺兰堑苎兰兰塑丝些童! 里呈墨童 3 p r o p o s e da n o t h e rm f d i n1 9 9 9b yr e f o r m i n gt h ed f sa b o v ea sf o l l o w s ： m i nz + ；矿风d ( 。，d ) 一 s t v ( 扩) 1d 加z ， 乳( 矿) + v 缈( 矿) 1d z ，j z w h e r e1 b ，7 ， ( j t ，) a r ea l lp o s i t i v ec o n s t a n t s b a s i n go nt h ed f sa b o 、e ，j i a n ，z h e n g ，h u a n d 】h n g 【1 6 】p r o p o s e dan o r m r e l a x e ds t r o n g l ys u b f 色a s i b l ed i r e c t i o nm e t h o df o rs o l v i n g ( p ) w i t ha na r b i t r a r yi n i t i a li t e r a t i o np o i n t i n 【1 6 ，t h ed f sh a st h ef o l lo - i n gf o r m m i nz + ；矿b k d ( ：，d ) s t v ，1 ( z 2 ) 1d 茎加。+ n ( z 2 ) ， 卯( z 2 ) + v 幻( 扩) 。d5 玑z ， j j 扛) ， 卯( z ) + v 野( 一) 1d 冬讯z + 妒( 扩) ， j j + ( z 。) ， w h e r e ( z 2 ) i sap e n a l t yf u n c t i o n ，r ki sap o s i t i v ep a r a m e t e ra s s o c i a t e dw i t hz 2 ，j 一( z ) = j j ：卯( z ) 曼o ) ，j + ( z ) = j j ：缈( z ) o ) ， 妒( z ) = m a o ；9 ，( z ) ，j t ，) b u t t h es u p e r l i n e a rc o n v e r g e n c ei sn o td i s c u s s e di n 【1 6 】 i n1 9 8 6 ，gr i p p o ，l a m p a r i e l l oa n dl u c i d i 【1 7 】p r o p o s e da “n o n m o n o t o n e ”1 i n es e a r c h a c c o r d i n gt ow h i c ht h eo b j e c t i v ef u n c t i o n i sn o tf o r c e dt od e c r e a s ea te v e r yi t e r a t i o nb u t m e r e l ye v e r yli t e r a t i o n s ，w h e r eli s af r e e l ys e l e c t e dp o s i t i v ei n t e g e r t h e ys h o w e dt h a t ， w i t hs u c hal i n es e a r c h ，g l o b a lc o n v e r g e n c ei ss t i l lg u a r a n t e e d ，a n dt h e ya l s op o i n t e do u t t h a t ，a st h ef u nn e w t o ns l e pc a nt h e nb et a k e ne a r l i e r ，c o n v e r g e n c em a yo f t e nb es p e e d e d u p i nt h i sp a p e r ，m o t i v a t e db yt h et e c h n i q u e so ft h en o r m r e l a x e dm f di n 【1 5 ，1 6 】a n d t h e “n o n m o n o t o n e i i n es e a r c hi nf 3 ，6 ，1 7 ，w ep r e s e n tan e ws q pa l g o r i t h mf 。rm i n i m a x p r o b l e mw i t hi n e q u a l i t yc o n s t r a i n t s t bg e taf e a s i b l ed i r e c t i o no fd e s c e n ta n dr e d u c et h e c o m p u t a t i o n a lc o s t ，b a s i n go na n 一a c t i v eo b j e c t i v es u b s e ta n da 疗一a c t i v e c o n s t r a i n ts u b s e t ， w ec o n s t r u c tan e wq ps u b p r o b l e m ，w h i c ha l w a y sh a saf e a s i b l es o l u t i o na n dp o s s e s s e ss m a l l s i z e b ys o l v i n gt h eq ps u b p r o b l e m ，w eg e taf e a s i b l e d i r e c t i o no fd e s c e n t t ba v o i dt h e m a r a t o se f f 色c t ，w ec o n s t r u c ta n o t h e rq ps u b p r o b l e mc o r r e s p o n d i n g t ot h e6 r s to n et og e ta h e i g h t o r d e rc o r r e c t i o nd i r e c t i o n t h e n ，w ep r e s e n to u r “g e n e r a l i z e dm o n o t o n e ”l i n es e a r c h a l g o r i t h m ，i e ，t h em e r i tf u n c t i o ni sf o r c e dt od e c r e a s ea te v e r yr + 1 i t e r a t i o n s ，w h e r er i san o n n e g a t i v ei n t e g e r i fr = o ，t h e no u ra l g o r i t h mi sau s u a lm o n o t o n ea l g o r i t h m ，e l s e ， w en a m ei trm o n o t o n ea l g o r i t h m a te v e r yi t e r a t i o n ，w en e e do n l yt os o l v et w oq p sw i t h s m a us i z ea tm o s t u n d e rm i l dc o n d i t i o n s ，t h 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 ec a nb e o b t a i n e d e s p e c i a l l y ，t h e9 1 0 b a lc o n v e r g e n c ec a nb eo b t a i n e do n l yu n d e ra w e a km f c q t h er e s to ft h i sp a p e ri so r g a n i z e da sf 0 1 l o w s t h en e x ts e c t i o ng i v e so u ra l g o r i t h ma n d s o m ep r o p e r t i e so fi t i ns e c t i o n3a n ds e c t i o n4 ，w ed i s c u s st h e9 1 0 b a la n ds u p e r l i n e a r 妄里查兰丝圭耋竺篁塞至耋垒竺奎! ! 些些竺垫墅竺望望竺至堑苎苎兰塑垒苎窒篁鱼呈兰兰 。 c o n v e r g e n c e ，r e s p e c t i v e l y s o m ep r e l i m i n a r yn u m e r i c a lr e s u l t sa r er e p o r t e di ns e c t i o n5 f i n a l l y w eg i v es o m er e m a r k sa b o u to u ra l g o r i t h m 2 t h ea l g o r i t h m f i r s t ，f o raf 色a s i b l ep o i n tz x ，w ed e n o t es e t s ，( z ) a n dj ( z ) b y j ( z ) = i ，：，i ( z ) = f ( z ) ，j ( z ) = j j ：幻( z ) = o r oy i e l daf 色a s i b l ed i r e c t i o no fd e s c e n ta tp o i n tz 2 x ，w ec o n s t r u c taq u a d r a t i cp r o g r a m a s f 0 1 】o w s 黜z + i 矿风d q p ( z ，以) s t ( z ) + v ( z ) t d f ( z ) z ， 磋， ( 2 1 ) 卯0 ) + v 卯扛) 了d c k z ，j 瑰， w h e r ec k ，e 女，民 o ，= i ，：f ( z 2 ) 一 ( z ) e ) ，磕= j l ，：一口k 毋( z 2 ) ) ，a n d t h es 、m m e t r i cp o s i t i v ed e 矗n i t em a t r i xh ki sa na p p r o x i m a t i o nt ot h el a 口a n g i a nh e s s i a n m a t r i xo f ( p ) l e m m a2 1s 叩p o s e 执o f 冼em o n z 仇i ss 掣m m e 拥cp d 毗向ed 币砸e n e n q p ( z ，日k ) 九o sn 钍n i g u ed p 竹i 。fs 0 2 “f i d n j i j ( ，扩) i so no p i m n fs o f u “o nd ，q p ( 一，日i ) t 厂n 竹do 礼冶矿 f i so k k t p o 讯0 ，q p ( ，风) t h ep r o o fo ft h i sl e m m ai ss i m i l a rt ot h eo n eo fl e m m a2 1i n 【1 6 】，t h u si ti so m i t t e dh e r e s u p p o s et h a t ( z k ，d ) i st h es o l u t i o no f ( 2 1 ) t h e nt h e r ee x i s tm u l t i p l i e rv e c t o r sa ；k a n d 肛s u c h t h a t 。钆 小引v + ，轰瞄( v 剖一o ，亿。， io a ? 上( ( z ) + v ( z 。) r d 一f ( z ) 一钆) so ，i 吃， 、 。 【os 瞄上( 卯扛2 ) + v 缈( 一) 丁扩一c ) o ，j 磕， w h e r e 叫上可i n d i c a c e so r t h o g o n a l i t yo fa n yv e c t o r s 训a n d 暑， ap o i n tz xi ss a i dt ob eas t a “o n a r yp o i n to fp r o b l e m ( p ) i ft h e r ee x i s tm u l t i p l i e r v e c t o r s7 r 2 = ( 7 r ? ，i ) a n d 2 = ( 咭，j | ，) s u c ht h a t f 7 r v ( ) + u ；v 夕j ( 扩) = o ；7 r = 1 ， i ，j e j 。 i ， 【os7 r _ l ( ，i ( z ) 一f ( z ) ) o ，i ，；osu ；上g j ( z 2 ) o ，j j ( 2 3 ) f i r s t ，t h et w of 0 1 1 0 w l n gh y p o 恤e s e sa r en e c e s s a y1 nt h l sp a p e 。 h 1f h n c “o n s 0 ，) n d 毋0 j ) 。r e 。“丘邶o r d 8 rc d n t n u d u s 妇d i 如r e n “0 6 f 8 h 2 卯；e 叫e 砒m f c qh d f d so e n c z x ，i e ，忱e r e e 。诂 snu e c d rds u 。 o n 叫 v 卯( z ) t d o ，d ro j ( z ) r e m a r k2 1c o r r e s p o n d i n gt ot h ea s s u m p t i o nh 2 + i n s e c t i o n4 ，t h em f c qh o l d i n g a te a c hz xi m p l i e st h a tt h e r ee x i s t s av e c t o rda n df o rs o m e 砝扛) 8 u c h