（计算数学专业论文）非线性l1问题的调节熵函数法.pdf

摘要 非线性1 。问题是一个常见的无约束不可微优化问题，它经常 出现在网络和系统设计等实际问题中。本文提出了求解该问题 的调节熵函数法并给出了其性质及算法，该算法克服了之前一 些算法，特别是极大熵函数法的h e s s e 阵渐趋病态的缺点。 本文分为四个部分：第一部分介绍极大熵方法，并给出了一个 方法如何避免熵函数的溢出；第二部分提出了求解非线性f 。问题 的调节熵函数法，给出了其性质；第三部分给出了算法，证明了该 算法的收敛性；第四部分为数值实验，结果表明该算法效果良好 关键字：非线性f 。问题，最优解，调节熵函数法，可调参数，极 大熵函数法 a b s tr a c t t h en o n l i n e s xc 1 p r o b l e mi sa ni m p o r t a n tn o n - d i f f e r e n t i a b l eu n - 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 i ti so fg r e a tp r a c t i c a li m p o r t a n c e t on e t w o r ka n ds y s t e md e s i g n e r sw i s h i n gt oa p p r o x i m a t eas p e c i f i e d r e s p o n s eb yan e t w o r ko rs y s t e mr e s p o n s e i np r e s e n tp a p e r t h ea d j u s t a b l ee n t r o p yf u n c t i o nm e t h o di su s e dt os o l v et h i sp r o b l e m t h i s m e t h o da t t e m p t st oo v e r c o m es o m ed r a w b a c k so ff o r m e rm e t h o d s e s p e c i a l l yt h em a x i m u me n t r o p yf u n c t i o nm e t h o d i nc h a p t e r2 ，w ep r e s e n ta g la d j u s t a b l ee n t r o p yf u n c t i o na n dg i v e s o m e p r o p e r t i e s i nc h a p t e r3 ，t h ea l g o r i t h m i sg i v e na n dt h ec o n v e r g e n c ei sp r o v e d n u m e r i c a lt e s t ss h o wt h a tt h i sa l g o r i t h mi se f f i c i e n t a n dp r a c t i c a l s o l u t ! o n a j u s e a b l e m a x l m u m e n t r o p y 墨黜搬 艨蝴咄 淌 麟怒眦w 砂m y 吐劬胁 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的+ 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经 发表或撰写过的研究成果。 j 、其他同志对本研究所敞的贡献均已在论文中作了声明并表示了谢 意。 作者签名：墨整 日 期：兰里：! ：2 学位论文使用授权声明 本人完全了解南京师范大学有关噪留、使用学| 立论文的规定，学饺有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸 质叛；有权将学位论文用于非赢利目的的少量复利并允许论文进入学校 图书馆谈查阅；有权将学位论文的内容编入有关数据库进行俭索；有仅将 学1 立论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名：兰篁 日期：竺! ! 12 p r e f a c e t h en o n l i n e a r1 1p r o b l e mm a yb es t a t e da sf o l l o w s m i n f ( z ) = fi f , ( z ) l ，i = l “2 一，m z一 i = 1 w h e r exi sa nn d i m e n s i o n a lc o l u m nv e c t o ra n d 扛) ，i = 1 2 ( 1 ) m a r ea l l c o n t i n u o u s l yd l i f e r e n t i a b l ef u n c t i o n 8 m o r e o v e r t h e r ea r ea tl e a s to n en o n l i n e a r f u n c t i o n si n 五( z 儿i = 1 ，2 ，t 。m ) t h em a x i m u me n t r o p yh m e t i o nm e t h o d ( a l s o c a l l e da 8c o h e r e n tf u n e t i o nm e t h o d ) d e v e l o p e dt h e s ey e o r si sar a t h e re f f e c t i v e m e t h o da n dt h e r eh a sb e e nag r o w i n ga m o u n to fr e s e a r c hi nt h ea r e ao ft h i s m e t h o da n di t 8a l g o r i t h me s p e c i a l l yi ns o l v i n gt h em a x i m u mp r o b l e m s e e 【5 6 】 吲f 8 j 剧y a oa n dc u if 1 1p r o p o s e dam a x i m u me n t r o p yf u n c t i o nm e t h o dt os o l v e p r o b l e m ( 1 ) u s i n gt h ef u n c t i o n f p ( z ) = 胁( 砂引+ e 嘶2 ) p o ( 2 ) t = 1 o w i n g t o f ( 。) o ( z ) f ( 。) + 罢f n 2 ， ( 3 ) 乓( 。】u n i f o r m l yc o n v e r g e st of ( x ) a sp 一+ t h e r e f o r e ，w h e npi sl a r g e e n o u g h ，t h eo p t i m u ms o l u t i o no fr a i n 0 ( z ) c a l la p p r o a m a t et ot h a to fp r o b l e m ( 1 ) w e l l h o w e v e r ，b ya n a l y z i n gt h et h eh e s s i a nm a t r i xo f 昂( z ) ，i ti sf o u n dt h a tf o r h i g hv a l u e so ft h ea p p r o x i m a t i o nc o n t r o l l i n gp a r a m e t e rp ，t h ed i f f e r e n t i a b l eo p t i m i z a t i o np r o b l e mi n v o l v e di nt h ee n t r o p yf u n c t i o nm e t h o db e c o m e si l l c o n d i t i o n e d a n dh e n c ed 通c u l tt os o l v e i n t h i sp a p e r ，am o d i f i e dm a x i m u me n t r o p ym e t h o di sp r o p o s e dt os o l v e n o n l i n e a rf 1p r o b l e m t h i sm e t h o di sa ni m p r o v e m e n to fm a x i m u me n t r o p ym e t h o d b ya d d i n gt h ea d j u s t a b l ep a r a m e t e r st , i ，i = l ，2 ，+ 一，m ，a n da t t e m p t st oo v e r c o m e d r a w b a c k so ff o r m e rm e t h o d 1 t h en e wa d j u s t a b l ee n t r o p yf u n c t i o ni s ： f p ( x , ? 3 1 = ；毒z n ( 半+ 半e 吼) w h e r e 一1 让1 、i = 1 ，2 ，r m t h i st h e s i si so r g a n i z e da sf o f i o w s i nc h a p t e r l ，w es t u d yt h em a x i m u m e n t r o p yf u n c t i o nm e t h o da n dh o wt oa v o i dt h eo v e r f l o w i nc h a p t e r 2 ，w ed i s c u s s t h ea d j u s t a h l ee n t r o p yf u n c t i o nm e t h o da n ds o m ep r o p e r t i e so fn e wa p p r o x i m a - t i o nf u n c t i o na r ep r e s e n t e d i nc h a p t e r 3 ，t h ec o r r e s p o n d i n ga l g o r i t h ma n di t s c o n v e r g e n c ea r es t u d i e d i nc h a p t e r 4 n u m e r i c a lr e s u l t ss h o wt h ef e a s i b i l i t ya n dt h e e f f i e i e n c yo ft h i sa l g o r i t h m 2 c h a p t e r1 r 1 1 1 1 n em a x l m u me n t r o d vm e t h o d f o rn o n l i n e a r 1 1 p r o b l e m n o n l l n e a r l1 1 1 i n t r o d u c e f 治c o n s i d e rt h en o n l i n e a r1 1p r o b l e m ： 瓣f ( z ) = 忡) 忙i l ，2 - ，m t = 1 ( 1 1 ) t h ef u n c t i o nf ( x ) i sn o n - d i f f e r e n t i a b l ea tp o i n t sw h e r ea tl e a s to n eo ft h e i s e q u a l t oz e r o ，e v e ni ft h ef u n c t i o n s ， a r ed i f f e r e n t i a b l e t h e r e f o r e t h eu s u a l n e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rd i f f e r e n t i a b l eu n c o n s t r a i n e df u n c t i o n sc a n n o t b ea p p l i e di no u rc a s e s i n c e f ( z ) = i z ( z ) l = m a x f d z ) 一 ( z ) ) 1 l2 ) i = 1l = 【 t h e nt h em a x i m u me n t r o p yf i m c t i o no fp r o b l e m ( 1 1 ) i s 聃) = ；塾( 删+ e - 州功 ( 1 3 ) w h e r et h ep a r a m e t e rpi sap o s i t i v ei n t e g e r o b v i o u s l y , b ( z ) i sd i f f e r e n t i a b l ea n d h a st h es a m eo r d e rs m o o t h n e s sa s 扛) ，i = 1 ，2 ，一一，m 3 1 2 p r o p e r t i e s l e r n m a1 2 1 昂( 嚣) u n i f o r m l yc o n v e r g e st of ( x ) o ni t sd e f i n i t i o nd o m a i na sp 。 + o 。a n dt h ef o l l o w i n gi n e q u a l i t yi ss a t i s f i e d ： f ( z ) 昂扛) f ) + 詈f n 2 ， ( 1 4 ) l e m m a1 2 2b ( 。) i ss t r i c t l yd e c r e a s i n ga b o u tp ，i e ，w eh a v et h ei n e q u a l i t y 昂。( z ) p 2 0 w ec a l l - s e ef r o mt h eu p p e rt w ol e m m a st h a tb ( 。) h a sg o o dp r o p e r t y a n du n i f o r m l ya p p r o x i m a t e st of ( x ) a sp + 。s ot h e o r e t i c a l l y , t h eo p t i m u m s o l u t i 。no fr n j ng ( x ) t a x ia p p r c o d m a t et 。t h a t 饥m 。i “f ( 。) 8 “m 。1 。m 1 y ”h e np i s l a r g ee n o u g h 1 3 a l g o r i t h ma n di t sc o n v e r g e n c e ( m a x i m u me n t r o p yf u n c t i o nm e t h o df o rn o n l i n e a ri ip r o b l e m ) a l g o r i t h m1 1 s t e p j ：g i v e nx o r “，p l 0 ，z 0 ，s e tk = o s t e p 2 ：g i v e ns t a t i n gp o i n tz k 一1 ，g e t 船o p t i m u ms o l u t i o nz ko f 吗n 蹦加去喜w 以+ e _ 肼) ( 1 s ) s t e p j ：g i v e n5 0 ， ，1f ( x k ) 一f p k ( k 】i ，t h e ns t o p o t h e r w i s e ，s e t p k + l ：= f p k ，k ：= + 1 ，邝托f n2 0 l e m m a1 3 1f f i r s t o r d e rn e c e s s a r yc o n d i t i o n sf o ro p t i m a l i t y ) i no r d e rf o rf ( x 1t oh a v eam i n i m u ma tt h ep o i n tr ，矾m u s th a v e s i g n ( 五( 矿) ) v ( 矿) + i v ， ( 矿) = 0 ( 1 6 ) l g a 扛) i e a ( x ) w h e r e 一1 地1 ，i a ( z ) ，a ( x + ) = ii ( z + ) = 0 ，i = 1 ，2 ，一，竹1 ) 4 l e m m a1 3 2i fx + i sas t a t i o n a r yp o i n to ft h eo b j e c t i v ef u n c t i o n 昂t ( z ) i _ e ，v r f p ( 矿) = 0a n d i sal i m i tp o i n to ft h es e q u e n c e z ； a sp k 。+ o 。一t h e n 矿 s a t i s f i e st h ef i r s t o r d e rn e c e s s a r yc o n d i t i o n so fm ( x ) f o ro p t i m a l i t y t h eu p p e rl e m m a st e l lu st h a ti f c a ng e tt h es t a t i o n a r yp o i n t so fb ( z ) ， t h e nt h e i r l i m i tp o i n tm u s ts a t i s f yt h en e c e s s a r yc o n d i t i o n so ff ( x ) f o ro p t i m a l - i t y t h e o l l o w i n gt h e o r e mw i l ls h o wt h a ti fw ec 8 ng e t t h eo p t i m u ms o l u t i o n so f p r o b l e m ( 1 ，5 ) ，t h e nt h e kl i m i tp o i n tm u s tb et h eo p t i m u m s o l u t i o no f p r o b l e m ( 1 1 ) t h e o r e m1 3 3l e tt h ef u n c t i o n s ( z ) ，i = 1 ，2 ，一，m ，b ec o n t i n u o u s l yd i f f e r e n t i a b l e a n dt h el e v e ls e t l = 工 昂( z ) sb 。( 。) ) ( 1 7 ) i sb o u n d e d t h e ne v e r y a c c u m u l a t i o np o i n to ft h es e q u e n c e k ) w h i c ha r ed e r i v e d f r o ma l g o r i t h m l 1i st h eo p t i m u ms o l u t i o no fp r o b l e m ( 11 ) 1 4t h ea v o i d a n c eo fo v e r f l o w w ef i r s ti n t r o d u c et w on o t a t i o n si nt h i ss e c t i o n ： 1 砩i st h eo p t i m u ms o l u t i o no fp r o b l e m ( 1 3 ) 2 li st h ec r i t i c a lv a l u eo fo v e r f l o w ，1 e ，t h ec o m p u t e rw i l l o v e r f l o ww h e n c o m p u t i n ge l 3 仇扣) = m a x f i ( z ) ，一 扛) ) f r o mt h eu p p e rd i s c u s s i o n ，w ec a ns e et h a tu n d e rs o m ec o n d i t i o n ，t h e e r r o rb e 七w e e n 工口a n dz w i l lb ea r b i t r a r i l ys m a l l8 , 8l o n ga spi sl a r g ee n o u g h b u t a c t u a u y 7t h em a x i m u me n t r o p yf u n c t i o nf p ( z ) m a yo v e l 咀o wi fpi sl 淞g ee n o u g h ， a n dt h eh e s s i a nm a t r i xo fb ( o ) m a ya l s ob ei l l - c o n d i t i o n i n g t h e ni nt h i ss e c t i o n w ew i l ld i s c u s sh o w t oa v o i dt h eo v e r f l o wo f 昂( z ) l e t ( z ) = 0 ：p l ，( z ) l 专 ，t h e n w e h a v e 驰) = ；势( e p f i ( z ) - i - e - v i i ( z ) ) ：- f r v z - 、, + 1 1 d 子l n f l + e 一珈t ( z ) 1 ( 1 8 ) = f ( z ) + ；管l n ( 1 + e _ 酬 ) + ；磊1 n ( 1 打酬1 ) 5 耳( z ) = f ( 。) + 1 n ( 1 + e 一卸鲥。) ( 1 9 ) 疟l w h e n 琶，w eh a v ep g i ( x ) s 鲁，i r e ，一l 一2 p g ( x ) 0 t h e r e f o r e ，i fw e t a k e 昂( z ) a s 斥( z ) t h eo v e r f l o wo f 弓( z ) c a rb ea v o i d e d m o r e o v e r ， 0 s 昂( z ) 一b ( z ) = ；el n ( 1 + e - 2 m ( 。) ，1 箸“1 一l 、 (110)1 s ；i n ( 1 + e 一) 卜 k e l p s i r n l n ( 1 + e ) s ot h ee r r o rb e t w e e n0 ( z ) a n d 昂( z ) i sv e r ys m a l l ，a n dr e a c h e st h er e q u k e dp r e c i s i o no fc o m p u t e r a l t h o u g h 皿) ，i = l ，2 ，ma r en o n d i f f e r e n t i a b l e a n d 耳( z ) i sn o n d i f f e r e n t i a b l et o o ，i ti s f e a s i b l et ot a k e 写( ) a st h ea p p r o ：d m a t , e c o m p u t a t i o no fb ( z ) 6 c h a p t e r2 a d j u s ta b l ee n t r o p yf u n c t i o n m e t h o df o rn o n l i n e a r1 1m e t h o d 2 1 i n t r o d u c t i o n q i n g z h iy a n gf 2 】p r o p o s e dt h ea d j u s t a b l ee n t r o p yf u n c t i o nm e t h o dt os o l v et h e m i n - m a “xp r o b l e m t h i sm e t h o di sa ni m p r o v e m e n to fm a x i m u m e n t r o p ym e t h o d a n da t t e m p t st oo v e r c o m es o m ed r a w b a c k so ff o r m e rm e t h o db ya d d i n gs o m er e g ， u l a t o r yf a c t o r s t h e o r e t i c a la n a l y s i sa n dn u m e r i c a lc o m p u t a t i o na l li l l u s t r a t et h a t t b 2 sm e t h o di ss u p e r i o rt ot h ef o r m e ro n e i nt h i ss e c t i o n w em a k eu s eo ft h i sm e t h o dt os o l v et h en o n l i n e a rf 】p r o b l e m ： 睁f ( 。) = ( 吼i = 1 2 - m = l f 2 1 1 w h e r exi sa nu - d i m e n s i o n a lc o l u m nv e c t o ra n d 五( 。) i = 1 2 ，m ，a 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 ef u n c t i o n s m o r e o v e r ，t h e r eo x ea tl e a s to n en o n l i n e a r u n c t i o n s i n 五如) i = l ，2 ，一，m ) 驰，归；1 善r n 轨( 半删+ t l - - u e 舶) ( 2 2 ) w h e r e - 1 q l ， = 1 ，2 ，一，” i nt h ef o l l o w i n g ，w ew i l ls t u d ys o m ep r o p e r t i e so fb ( ，u ) 7 2 2 a p p r o x i m a t i o np r o p e r t y t h e o r e m2 2 1l e t 一1 0 l e t 矽( 鲫) = 如f 字e p 舯) + 挚口_ 脚】i f p o ， h a v e 鑫爿。( z ，”) 。专垫竺唑坚匙塑炭豢筹筹型些墼= 二= 竺兰”土毛班e p 【；+ ! ；盐：= ；币万工。 ( 2 6 ) b e c a u s eo ft h ec o n v e xq u a l i t y 啪h a v e 0 ，岳巧2 ( 。，口) 0 m 0 。8 。v e r ，i f p o ，w eh a v e 杀昂( 。，”) = 曼毒巧hu ) o t h e ne 扫、。) i 。 3 。a c c 。r d i r l g 抽( 2 3 ) a n d l 地 0 ，t h e nt h ee q u a l i t i e sb ( j ，甜) = f ( ) a n d u i = q ( z ) ，i 葶a ( 5 ) a x es a t i s f i e d p r o o f is u p p o s et h a t 饥= 地( 虿) ，f 毛 4 ( ) f o ra l li a ( 5 ) t h e n h a v e 挑 - 1 + i - n - ( - 1 + 半e - p h ( 5 ) ：o ( 28 ) 乓( z ， ) = i 1 斟( _ ) 1 n 【号尸e p ( 引+ 立字e - p f , ( 斟】 = ；i ( i ) i ne p 忡i 一鄹f _ 1i ( 虿) i ( 2 9 ) = ：。i 五( z ) = f ( 5 1 s u p p o s et h a tr ( i ”) = f ( _ ) i ft h e r ee x i s t ss o m ei n t e g e rj 百4 ( ) s u c ht h a t u j 叶f i ) 一l q 1 s i n c e 疗( z ) | 厶( z ) lo r l ( z ) l 疗( i ) l ，t h e nw eh a v e 1 1 1 半删”t 半e 嘶( 刳 1 n 半e p l g ( m ) l + p ! f i ( w ) 1 p 叭i ( 2 1 0 ) i e ，( 孑u ) 0 ，0 o r 0 ，i = l ，2 ，r ，i f b x = 0c a l lr e s u l t i ns t a s r | i 。 1 2 ，t h e n v a ( o ，r ) ，3 k o o , i f k k o w eh a v ex t ( a + k b r u b ) s aj j z l l 2f o r v s r “ t h e o r e m2 3 1s u p p c l s et h a ta s s u m p t i o n ( b ) h o l d s ，t h e nw eh a v ev b ( z + ， + ) = 0 ，w h e r e ；= s i g n a ( x + ) ，t 芒a = 4 ( 矿) 1 1 p r o o f f o ri 专a w eh a v e 特描斋* 器纂= s i g n f i ( ：嵋( 1 + 钉；) e p ( 。+ ) + ( 1 一口：) e p ( z ) 47 一 f o r i a ，f r o m a ( x ) = 0 ，粥h a v e ( 1 + v ；) e p a ( r ) 一( 1 一 ：) e p a ( 。一。 可再两蕊可可f 哥弦面两2 q t h e r e f o r e f 22 1 1 f 2 2 2 1 瓦o ( z + ，a ) = v ；v i , ( z + ) = ( s 匆”五( 。) ) d rv a ( z ) 十露v 正( 。) = 0 i = i i g at ( 2 2 3 ) t h e o r e m2 3 2s u p p o s e dt h a ta s s u m p t i o n s ( a ) 一( e ) h o l d ，t h e nt h e r ee x i s t s f 0 ，i fp 盒w ec a ng e tt h ec o n c l u s i o nt h a t 铝矿) i ss t r i c t l yp o s i t i v e w h e r e + i st h es s a t i ea st h a ti nt h e o r e m 2 3l p r o o f _ f o ru ；= s i g n ( z + ) ，i g a ，、北h a v e v ：昂( 一矿) = 蓥舞器鞫耩v 2 ( r ) + p 蚕卜( 篇崩寄量警揣) 2 】v 地啊脾甲 = ( s 匆九五( 。) ) v 2 扛) + u ；甲2 五( r ) + p ( 1 一“：2 ) v a ( z + ) v f d x ) 7 = ( s i g n a ( z ) ) v 2 ( 。+ ) + u ? v 2 ( z ) + p v t ( z + ) v “f 7 ( z + ) r i g a拒 f 22 4 ) w h e r ev + = d i a g ( 1 一u ；2 ，i a ) ，v 了( ) = ( v f ( z ) ，i a ) f r o ml e m m a 2 3 4a n dt h es u p p o s i t i o n ，w ec a ns e et h a tv ；0 ( 。u ) i ss t r i c t l y p o s i t i v e t h e o r e m2 3 3i f 矿i st h eo p t i m u ms o l u t i o no fn o n l i n e a rc