（计算数学专业论文）框式约束凸二次规划问题的内点算法.pdf

摘要 本文主要研究了框式约束的凸二次规划问题。这类问题出现在很多的 应用领域近年来提出的原始对偶内点方法是一类有效的算法但是考虑 到该问题是不等式约束凸二次规划的一种较简单的形式，即它的可行域 x = 知| f z m ，z 彤 是个十分简单的超长方体，所以我们给出了 一种赢接在x 上的内点迭代本文主要分为以下三个部分： 第一部分介绍了本文的研究背景。第二部分给出了求此类问题的一种 新的内点算法，该方法通过在内含于超长方体内的一系列超椭球体上求 最优解，来逐步逼近于原问题的最优解并给出了该算法全局收敛性的证 明在第三部分，对于框式约束问题，我们提出了一种势函数下降的内点 算法每次迭代中搜索方向由一个线性方程组解出，并利用a r m i j i o 准则 进行线搜索，同时使势函数的值减小并证明了该算法是全局收敛的 关键字：二次规划，内点法，势函数 a b s t r a c t i nt h i sp a p e r ，w em a i n l yc o n s i d e rt h ec o n v e xq u a d r a t i cp r o g r a m - r u i n gw i t hb o xc o n s t r a i n t s t h i sp r o b l e ma r i s e si ns e v e r a l9 2 - e a so fa ，o p l i c a t i o n s i nc h a p t e r2 ，c o n s i d e r i n gt h ef e a s i b l er e g i o nx = 扛l f 茎 z m ，z 月” i sas i m p l ea n ds p e c i a ls u p e rc u b o i d w ep r e s e n t ak i n do fd i r e c ti n t e r i o r - p o i n ta l g o r i t h mo nx i tr e a c h e st h eo p t i m a ls o l u t i o nb ys o l v i n ga s u b p r o b l e mw i t hs u p e re l l i p s o i dc o n s t r a i n t s e m b e d e di nt h es u p e re u b o i d w jp r o v et h a to u ra l g o r i t h mi sg l o b a l l yc o n v e r g e n t a n di nc h a p t e r3 ，w ep r e s e n tap o t e n t i a l r e d u c t i o n i n t e r i o r p o i n tm e t h o df o rs o l v i n gt h i sp r o b l e m a te a c hs t e po ft h ea l - g o r i t h r n as y s t e mo fl i n e a re q u a t i o ni ss o l v e dt og e ta s e a r c hd i r e c t i o n a n dt h ea r m i j o ：sr u l ei su s e dt od e t e r m i n eas t e ps i z e s i m u t t a n e - o u s l yt h ev a l u eo ft h ep o t e n t i a lf u n e t i o ni sr e d u c e d w ep r o v et h a tf o r a n yi n i t i a lp o i n tt h es e q u e n c ep r o d u c e db yt h ea l g o r i t h mi sb o u n d e d a n de v e r ya c c u m u l a t i o np o i n to ft h es e q u e n c ei st h eo p t i m a ls o l u t i o no ft h ep r o b l e m i no t h e rw o r d ，t h i sa l g o r i t h mh a st h eg l o b a l c o n v e r g e n c e k e yw 0 r d s ：q u a d r a t i cp r o g r a m m i n g ，i n t e r i o r - p o i n t ，p o t e n t i a lf u n c _ t l o l l 学位论文独创性声明 本人郑重声明： l 、坚持以求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本c 仑文中除引文外，所有实验、数据和有关材料均是真实的 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经 发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢 意。 作者签名 日期 学位论文使用授权声明 本几完全了解南京师范大学有关保留、使用学位论文的规定，学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸 质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆被查阅；有权将学位论文的内容编入肓关数据库进行俭索；有权将 学位沦文的铄题和摘要汇编出版。保密的学位沦文在解密后适用本规定。 怍青签名 日 期 c h a p t e r1 i n t r o d u c t i o n ，ec o n s i d e rac l a s so fa l g o r i t h m sf o rf i n d i n gas o l u t i o no ft h ep r o b l e m 1 一一 r a i n ，( z ) = ；一h a ：+ b j z s t f z m( 1 1 ) w h e r e 丑r “1 “i sas y m m e t r i cp o s i t i v ed e f i n i t ef s e m i - d e f i n i t e ) m a t r i xb ，f ，m r “，a n dl i m i ，i = 1 ，2 ：- ，n t h i sp r o b l e ma r i s e si ns e v e r a la r e a so fa p p l i c a t i o n s ，s u c ha sp r o b l e mo fd i f f e r e n - t i a le q u a t i o n s ，d i s c r e t eo p t i m a lc o n t r o lw i t hc o n t i n u et i m ea n dd e s i g ne n g i n e e r i n g ， l i n e a rl e a s ts q u a r ep r o b l e mw i t hb o xc o n s t r a i n t so ra sas e q u e n t i a ls u b p r o b l e mo f n o n l i n e a rp r o g r a m m i n gm e t h o d s t h e r e f o r e ，i th a sas p e c i a li m p o r t a n c e m a n yd i f f e r e n ta l g o r i t h m sh a v e b e e ns t u d i e df o rs o l v i n gt h i st y p eo fp r o b l e m ，s u c ha sp r o j e c t i o ng r a d i e n tm e t h o d 1 1 ，a c t i v e - s e tm e t h o d 1 2 1 ，m a t r i xs p l i t t i n g m e t h o d s c 3 】【4 】【5 】 2 4 】a n dt h ei n t e r i o rp o i n tm e t h o d 6 】 7 】| 2 l 】【2 2 ) t h e s ea l g o r i t h m s h a v ef i n i t ec o n v e r g e n c ei ft h ep r o b l e mi ss t r i c t l yc o h v e xa n dt h es o l u t i o ni sn o n d e g e n e r a t ea s i m i l a ra l g o r i t h mc o m b i n e sc o n j u g a t eg r a d i e n tw i t hg r a d i e n tp r o j e c d o nt e c h n i q u e ，a n dl l s e s an e ws t r a t e g yf o rt h ed e c i s i o no fl e a v i n gt h ec u r r e n tf a c e a n dm a i z ei tp o s s i b l et oo b t a i nf i n i t ec o n v e r g e n c ee v e nf o ras i n g u l a rh e s s i a na n d i nt h ep r e s e n c eo fd u a ld e g e n b r a c y b lap r i m a l d u a li n t e r i o rp o i n ta l g o r i t h mi s a l s ou s e dt os o l v el a r g ep r o b l e m ( 1 ，1 ) ，a n dt h en u m e r i c a le x p e r i m e n t sh a v es h o w n t h a tt h em g o r i t h mr e q u i r e so n l yaf e ws t e p sa n di sv e r ye f f i c i e n t 9 】 p o t e n t i e d r e d u c t i o na l g o r i t h m sn s et h ef o l l o w i n gs t r a t e g y ：f i r s t ，o n ed e f i n e sa p o t e n t i a lf i m c t i o nt h a tm e a s u r e st h eq u a l i t yf o rp o t e n t i a l lo fa n vt r i a ls o l u t i o no f t h eg i v e np i o b l e mc o m b i n i n gm e a s u r e so fp r o x i n f i t yt ot h es e c 】fo p t i m a ls o l u t i o n s p r o x i m i t yt ot h ef e a s i b l es e ti nt h ec a s eo i n f e a s i b l e i n t e r i o r p o i n t s ，a n dal n e t l s l l r o o fc e n t r a l i t ? w i t h i nt h ef e a s i b l er e g i o n ，p o t e n t i a lf u n c t i o n sa r eo f t e nc h o s e ns u c h t h a to n ea p l ) io a c h e sa no p t i m a ls o l u t i o no ft h eu n d e r l y i n gp r o b l e n lb 3 r e d u c i n g t h ep o t e n t i a lf u n c t i o nt h e n t h es e a r c hf o ra no p t i m a ls o l u t i o nc a nb ep e r f o r m e d j ) 、p t u g r e s s i 、er e d t t c t i o no ft h ep o t e n t i a ll t l n c t i o n 1 e a d i n gt oc 1p o t e n t i a l r e l h t c t i o n a l g o r i t h m w er e f e rt h er e a d e rt ot w oe x c e l l e n t s u r v e y sf o rf u r t h e rd e t a i l so n p o t e n t i a l - r e d u c t i o nm g o r i t h m s 【1 0 1 1 t h i st h e s i si so r g a n i z e da sf o l l o w s i nc h a p t e r2 w ep r e s e n tan e wi n t e r i o r p o i n tm e t h o dt os o l v et h i sp r o b l e m a te a c hi t e r a t e 。2 ，w em u s ts o l v i n gt h ef o l l o w i n gs u b p r o b l e m ： t 一一 m i n ( z ) = ；一日z + b 。z z s t i | d 1 ( z z j 1 2 墨l( 1 2 ) h e r e d ( ) “( z z ( ) | 1 2 茎l i sas u p e re l l i p s ee m b e d d e di nt h es u p e rc u b o i d x = xr l o m ，x r ”t h i sd i r e c ti n t e r i o r p o i n ti t e r a t i v eo nxs h o u l d b es i m p l e rt h a nt h ep r i m a l d u a li n t e r i o rp o i n tm e t h o d a tl e a s tt h ed i m e n s i o no f i t e r a t i v ev a r i a b l e si sf e w e rw ep r o v et h ec o n v e r g e n c eo ft h i s a l g o r i t h m a tl a s t s o m en m n e r i ce x p e r i m e n t si sg i v e nt os h o wt h ee f f i c i e n c yo ft h i sn e wm e t h o d i nc h a p t e r3 ，w ep r e s e n tap o t e n t i a l r e d u c t i o ni n t e r i o r p o i n tm e t h o df o rs o l v i n g t h i sp r o b l e m o u rg o a li st ot r yf i n d i n ga ne a s yw a yt os o l v et h i sp r o b l e m t h e m a i ni d e ao ft h ea l g o r i t h mi st oi n t r o d u c eap o t e n t i a lf u n c t i o nf o rt h i sp r o b l e m a te a c hs t e po ft h ea l g o r i t h m as y s t e mo fl i n e a re q u a t i o ni ss o l v e dt og e tas e a r c h d i r e c t i o na n dt h ea r m i j o sr u l ei su s e dt od e t e r m i n eas t e ps i z es i m u l t a n e o u s l yt h e v a l u eo ft h ep o t e n t i a lf u n c t i o ni sr e d u c e dw ep r o v e st h a tf o ra n yi n i t i a lp o i n tt h e s e q u e n c ep r o d u c e db yt h ea l g o r i t h mi sb o u n d e da n de v e r ya c c u m u l a t i o np o i n to f t h es e q u e n c ei st h eo p t i m a ls o l u t i o no ft h ep r o b l e m i no t h e rw o r d ，t h i sa l g o r i t h m h a st h eg l o b a lc o n v e r g e n c ea tl a s tag r o u po fe x a m p l e sa r eg i v e n t h en u m e r i c a l r e s u l t ss h o w st h ea l g o r i t h mi se f f e c d v e c h a p t e r2 a n i n t e r i o r p o i n ta l g o r i t h mf o r c o n v e xq u a d r a t i cp r o g r a m m i n g w i t hb o xc o n s t r a i n t s 2 1i n t r o d u c t i o n a ni n t e r i o r p o i n tm e t h o df o rs o l v i n gaq pp r o b l e mw i t hb o xc o n s t r a i n t si sd e s c r i b e di nt h i ss e c t i o n 1 m i n ，( z ) = ；z r 日z + 6 7 上 一 s t 2 z 曼mf 2 1 ) w h e r e 日er i sas y m m e t r i cp o s i t i v ed e f i n i t ef s e m i d e f i n i t e ) m a t r l x b ，2me 只“a n df ， m ，i = 1 2 ， ，n i t i sw e l lk n o w nt h a tt h ep r i m a l d u a li n t e r i o rp o i n tm e t h o d ( i n c l n d i n gc e n t r a l p a t t i - f o l l o w i n g ) i sak i n do fe f f e c t i v ea l g o r i t h m t h ex = x l l 茎上兰h 。，上r “i s r , h ef e a s i b l er e g i o no fp r o b l e m ( 9 1 ) i t l sav e r ys i m p l ea n ds p e c i a ls u p e rc u b o i d t h u sw ec o n s i d e rt h a ta nd i r e c ti n t e r i o r p o i n ti t e r a t i v eo nxs h o u k l b es i m p l e r t h a nt h ep r i m a l d u a li n t e r i o rp o i n tm e t h o d a tl e a s tt h ed i m e n s i o no fi t e r a t i v e v a r i a b l e si sf e w e rc o n s i d e r i n gt h i st h o u g h t sw ep r e s e n tak i n do fi n t e r i o r p o i n t a l g o r i t h mo nxt h eg o a lo ft h ep a p e ri st ot r yf i n d i n ga ne a s yw a yt os o l v et h e p r o b l e m t h i sc h a p t e ri so r g a n i z e d “f o l l o w sn e x ts e c t i o nw ew i l ld e s mi b et i l e p r o b l e n l a n dg i v es o n i cp r e l i m i n a r yr e s u l t si ns e c t i o n3w ew i l lp r e s e n to n rn e vi n t e r i o r 。p o i n t “l g o r i t h m a n dp t o r es o l n ee o n c l n s i o a s i ns e c t i o n4w ew i l lp r o v et h ec o n - e r g e n c e o ft h i sa l g o r i t h mi ns e c t i o n5 s o l n en u m e r i c a ir e s a h sa r er e p o t t h lw h i c hs h o 、x r t i l ea l g o r i t h mi se f f e c t i v ea n df e a m b l ea tl a s tw eg i v eab r i e fd e s c r i p t i o no fo l n ；d g o r i t l n na tt 1 1 es a m et i m ep o i n to n ei t sl i m i t a t i o na n dw h a ts h o u l dw ei m p r o x e l no n l - n i l ew o r kf o rt h i sm e c h o d 3 躲2p n j l n g 髯0 1 黑警。u 篙v e r s ，yd a 一11 x l j“nr 1 、j ln i1 1、 2 2p r e l i m i n a r i e s t h ep r o b l e m ( 2 1 ) i sac o n v e xp r o g r a m m i n g ，8 0w ec a nh a v et t l ef o l l o w i n gc o n c l u s i o n s t h e o r e m2 1ri st h eo p t i m a ls o l u t i o no ft h ep r o b l e mf 2 1 ) i la n do n l y 讨t h e r e e z i s t ”f pa n dz ，”w h i c hs a t i s j y h e 如l l o v o i n 9 ，。r m u l a h 矿+ b = a 。 n 0 ，i fz ；= m ： n 0 ，i fz ；= k i = 1 2 ，。，n k = 0 ，i ，l i x ； m ； ( 22 ) p r o o f l e t 矿b et h eo p t i m a ls o l u t i o no ft h ep r o b l e m ( 21 1 t h e nt h e r ea r e u ，u r ”s u c h 曲a tt h ef o l l o w i n gr e l a t i o n s h i ph o l d i = 1 2 n ( 23 ) t h ef o r m u l a ( 2 3 ) i st h ef i r s to r d e ro p t i m a l i t yc o n d i t i o n so rk k tc o n d i t i o n s o ft h ep r o b l e m ( 2 1 ) l e ta = u u t h e n h z 8 + b = a + f o ri = l 、2 ，、n i f f ：= f n i ，d u et ou ( f 。一r ；) = 0a n da i 0 ，t h e n a ：= 仇一u 。o ； i fr ：= f 。d u et oa i ( 1 r t i z i ) i f l 。i i n i ，d u e t ou ：( m 。 0a n de ：0 ，t h e n a ；= v i a i 0 。：) = 0a n d “( f 。一z ? ) = 0 t h e n m = f ，一a i = 0 t h i sp r o v e sr , l l ef o r u m l af 22 1 o nt h ec o n t r a x 3 ri ft h et b r m u l af ：2 1i sn 。l i et h e nf o ri = 12 = ，、il【 m n ：亘 一曦蠹 矿限 日 毗啦地 “ = ，刮“吖， 驴 ；? z ，。i = mz i fz ：= i i i ，2 l o ? m ： t h u st h ef o r m u l a ( 23 ) i sa l s op r o v e dt r u e b e c a u s et h ep r o b l e m ( 21 ) i sa c o n v e xp r o g r a m m i n g ，k k tp o i n tm u s tb ea no p t i m a ls o l u t i o n s oz + i st h eo p t i m a l s o l u t i o no ft h ep r o b l e m ( 2 ，1 ) d u et o1 2 z ，啦 i ，o ：= j ( f ：+ m ：) ；( f ，+ m i ) i = 1 2 ( f 。+ 吼) t h e o r e m2 2a s s u m ea i n t xa n di ti s n tt h eo p t i m a ls o l u t i o n 。，t h ep r o b l e m 21 ) ii st h eo p t i m a ls o l u t i o no ft h ef o f l o w i n gp r o b l e m ( 2 4 1 m i n ，( z ) = = 1 ，日z + b 7 z s t j j d 。( z 一酬1 2 l( 2 4 ) t h e n 驴j i so nt h eb o u n do fxo tl i d 一( z a ) l h l ，ii st h eo p t i m a ls o l u t i o no t t h ep r o b l e m 偿z j ，o t h e r u i s e ，( ) 0w h i c hs a t i s f i e st h ef o l l o w i n gf o r m u l a s ( 25 ) h 下+ b = 一2 p d 一2 i n 1 “( 【一 d 一1c 丁一a ) i i ) = 0 25 k m 葛撕j | r，、【也 | i 扎 血 “ | l d a = 一2 # d 一2 f i n 1 o b v o u s l ya ；= 0 ，i i 0 i fz 。o = m i ot h e n a 如0 ： i f 夏d = f t h e n a ，。兰0 f r o mt h e o r e m ( 21 ) ，w ek n o wzi st h eo p t i m a ls o l u t i o no ft h ep r o b l e m ( 21 ) c a s e2 i f | | d _ 1 ( z o ) 1 1 2 1 d u et ot h ef o r m u l a ( 2 5 ) ，t h e r ea r e “= 0 h j + b = 0 a c c o r d i n gt ot h e o r e m ( 2 1 ) ，虿i st h eo p t i m a ls o l u t i o no ft h ep r o b l e m ( 2 1 ) c a s e3 i f z i s n ：to nt h eb o u n do f xa n de d - 1 ( z 一划1 2 0s m a l le n o u g hs u c h t h a t 。一。( 日o + b ) ( z d 一( z a ) 1 1 2s1 ，z r “) ，( n a ( h a + 6 ) ) f ( a ) n o ws i n c ezi st h eo p t i m a ls o l u t i o no ft h ep r o b l e m ( 2 , 4 ) ，w eh a v e f ( x ) 0 、c f 攀) n 七= s t e p 2 7s o h ，et h e o u o w i n gs u b p r o b l e mt og e ta ? go p t i m a ls o l u t i o n r ( 。+ l n i nm ) = ；r t h _ + 娲 印 0 m 弘 一 一 叭 。i d 卜 | l + h 麓，。亭船褫：絮。贪慧紫5d 、- 内7 一a s t e p 3 ：s e t f 帆一z p 茁“= z _ lj ( m ：一f 。) s t e p4 ：c o m p u t e d + l ：r a i nd ? + l 。 1 0 n i f 世+ 1 0 ，p 0 ，eh a v e ( h x ( 。+ p + 6 ) t f 工【。) 一z ( “+ p ) 0 p r o o t h x ( ) + 6 = 甘。一h x i 女+ 1 ) 4 - 日。( k + 1 ) _ lb = h ( z ( ) 一z f 。+ 1 ) 一2 卢( 十) d ( ) + 2 ( t ( + 1 ) 一z ( k ) = 一( 日4 - 2 肛( + 1 d ( 。) - 2 ) ( 。( + 1 ) 一z ( 剐) a c c o r d i n gt o ( 2 6 ) ，w eh a v e ( z + 1 一。) = 2 肛。( 日+ 2 p ( 6 + 1 ) d ( ) _ 2 ) 一1 d ( 一1 ) 2 ( z ( ) 一茁( 一1 ) ( 27 ) t h u sw eh a v e ( h 5 ( + p + 6 ) r ( 。( ) 一。( 2 十p ) = ( h z 。+ 9 1 + 6 ) 丁 ( z ( q 一。( + 1 ) 十+ ( z ( 2 + m 一”一z ( + m ) + ( 。【k + p 一“r ( 女+ p ) 1 s p r e a dt h ea b o v ef o r m u l aa n da n a l y z ea n yt e r mo fi t b yu s i n g ( 2 6 ) a n d ( 27 ) r e p e a t e d l y , w ec a no b t a i n ( z 【十p ) 4 - 6 ) r ( z ( m 一1 ) 一z ( k + r n ) ) = 【2 p 肚+ d + 9 1 】一2 ( z ( + p ) 一z ( + p 一1 ) 丁( z ( + m 】一。【k 十m i ) = f 4 肛( “+ p d ( + p 一1 ) p ( 2 + p 一1 ( 日+ 2 口( k + p d ( + p 1 ) 一2 ) 一1 d ( k + p 一2 ) 一2 ( 上+ 9 一”一z + p 一2 ) 】t ( z ( “+ m ) 一。( + m 一1 ) po 。 = f 2 9 一“p + 。d 。+ 9 1 。i i ( ( h + 2 “( + 。d ( k + i - 1 ) 。) 一d ( k + t - 2 】2 ) i = m i = n + 1 ( t 廿+ m 一5 ( r e + m - 1 ) 】7 ( 小“+ 一z l 十仉一1 ) = ( c l k l - r n ) 一t l + m 一1 ) ) r 叫( f ( “+ n ”一z ( k + 俨【1 b yl e m n l a2 2 w ec a nk n o wj ，i sp o s i t i v es e m i d e f i n i t e t h l l st h e 、，n i l l eu f t i l ea b o x 7 ee x p r e s s i o ni sn o n n e g a t i v e 。 t h u s ( h 一。+ p + 们r ( r 一( 。+ 计) 三0 l e m m a2 4s u p p o s et h a tt h ea s s l t m p t i o no fl e m m a ，2 f d ! 幽7 h f ，7 阿2 ( ，一b 一 s2 4c o n v e r g e n c ea n a l y s l s 一1 0 一 n a n j n cn o r m a lu n 【、e r s i t yd a ix 1 、 p r o o f s e t h = b t b f o rv 0 ，坳 0 ，b yl