（计算数学专业论文）解无约束优化问题的自适应信赖域法.pdf

摘要 对于一般的无约束优化问题，信赖域方法是一种比较有效的方法。而 其中信赖域半径的选取对算法的好坏有着很大的影响。最近章祥荪等在 文f 1 中给出了一种自适应信赖域算法，利用当前迭代点的梯度和海赛 阵信息来选取当前迭代步的信赖域半径，数值试验表明，该方法比一般 的信赖域方法有效。本文的第一部分结合当前比较流行的非单调技术， 给出了一种新的非单调自适应信赖域方法，同时给出了文 1 中信赖域 子问题的近似解法，从而推广了文 1 中的算法，我们给出了新算法的全 局收敛性和超线性收敛性，数值试验表明非单调算法较单调的要有效。 第二部分将文1 1 中的自适应技术应用到锥模型的信赖域方法中去，给 出了一个新的锥模型信赖域子问题，同时也证明了新方法的全局收敛性 和超线性收敛性，数值试验表明了新算法的有效性。 关键词；信赖域方法；锥模型；无约束优化；总体收敛性；超线性收 敛；非单调 ab s t r a c t t r u s tr e g i o nm e t h o di sak i n do fe m c i e n ta n dr o b u s tm e t h o dt os o l v e g e n e r a lu n c o n s t r a i n e do p t i m i z a t i o n a n dt h ec h o i c eo ft h et r u s tr e - g i o nr a d i u si sv e r yi m p o r t a n t t ot h ee f f i c i e n c yo ft h em e t h o d r e c e n t l y z h a n ge t a l _ 1 p r o p o s e dan e w t r u s tr e g i o nm e t h o dc a l l e da d a p t i v e t r u s tr e g i o nm e t h o d ，i nw h i c ht h et r u s tr e g i o nr a d i u sd e p e n d so nt h e g r a d i e n ta n dh e s s i a no ft h ec u r r e n ti t e r a t ep o i n t n u m e r i c a lr e s u l t s s h o wt h ee f f i c i e n c yo ft h em e t h o d t h ef i r s tp a r to ft h i st h e s i sc o r n b i n e st h en o n m o n o t o n e t e c h n i q u e t ot h ea d a p t i v et r u s tr e g i o nm e t h o d 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 er e s u l t so ft h ea l g o r i t h ma r e e s t a b l i s h e d n u m e r i c a lr e s u l t ss h o wt h a tt h en o n m o n o t o n em e t h o di s m o r ee f f i c i e n t t h es e c o n dp a r to ft h i st h e s i sp u t st h ea d a p t i v et e c h n i q u et ot h ec o n i ct r u s tr e g i o nm e t h o d ，a n dw ea l s og i v et h eg l o b a l a n ds u p e r l i n e a rc o n v e r g e n c er e s u l t so ft h en e wm e t h o d n u m e r i c a l r e s u l t ss h o wt h a tt h en e wm e t h o di se f f i c i e n t k e y w o r d s t r u s tr e g i o nm e t h o d ，c o n i cm o d e l ，u n c o n s t r a i n e do p t i m i z a 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 ，n o n m o n o t o n e m e t h o d s 果。 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名：丛碰垒 日期：迎垒蝗 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行检 索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密 后适用本规定。 作者签名：丛堑坌 日期： 2 艘幺魅2 c h a p t e r 1 i n t r o d u c t i o n w 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 gal o c a ls o l u t i o no ft h ep r o b l e m 。m r i n 。m ) ( 1 - l 1 ) w h e r e ，( z ) ，t h eo b j e c t i v ef u n c t i o n ，i sa r e a l v a l u e dt w i c ec 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 ，w h i c hw ea s s u m ei sb o u n d e db e l o w w ef i r s ti n t r o d u c es o m es t a n d a r dn o t a t i o n s 1t h e n o t a t i o n f fd e n o t e st h ee u c l i d e a nn o r l no nr “ 2 s u p p o s e z 女) i sas e q u e n c eo fp o i n t sg e n e r a t e db ya na l g o r i t h m ，w ed e n o t e = f ( z k ) ，g k = g ( z ) a n dh k = h ( x k ) ，w h e r eg ( z ) r “a n dh ( x ) r ”。“a r et h eg r a d i e n t a n dh e s s i a no f1 ( 5 ) e v a l u a t e da tz 3 b ki sas y m m e t r i cm a t r i x ，i sas a f e l yp o s i t i v ed e f i n i t em a t r i xb a s e do ns c h n a b e l a n de s k o w 【2 】m o d i f i e dc h o l e s k yf a e t o r i z a t i o n ，b k = 风+ 段，w h e r e 皿= 0i fb ki s s a f e l yp o s i t i v ed e f i n i t e ，a n de ki sad i a g o n a lm a t r i xc h o s e nt om a k eb kp o s i t i v ed e f i n i t e o t h e r w i s e t h e r ea r et w ob a s i ca p p r o a c h e st os o l v ep r o b l e m ( 1 1 1 ) ，n a m e l y ：t h el i n e a rs e a r c h s t r a t e g ya n dt h et r u s tr e g i o nm e t h o d i nt h i st h e s i s ，t h el a t t e ra p p r o a c hi sd i s c u s s e d t r u s tr e g i o nm e t h o d sa r er o b u s ti t e r a t i v em e t h o d si nw h i c ht h eo b j e c t i v ef u n c t i o n f ( z ) i sa p p r o x i m a t e di nas u i t a b l en e i g h b o r h o o do ft h ec u r r e n ti t e r a t e ( t h et r u s tr e g i o n ) b yam o d e lw h i c hi se a s i e rt oh a n d l et h a n ，( o ) ab a s i ct r u s t r e g i o na l g o r i t h mw o r k sa sf o l l o w s a te a c hi t e r a t eo 女，at r i a l s t e pi s u s u a l l yc o m p u t e db ys 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 ： m i n c k ( d ) = 甄t “1 i i “t 口女d s t 1 i d l i 女( 1 1 2 ) w h e r eg k = v ( 。k ) i st h eg r a d i e n ta tt h ec u r r e n ti t e r a t ex k ，玩i sa nn n s y m m e t r i c m a t r i xw h i c hi se i t h e rt h eh e s s i a no ff ( z ) o ra l la p p r o x i m a t i o nt oi t ，a n d ki sat r u s t n a n j i n gn o , r e a lu n i v e r s i t y 2 r e g i o nr a d i u s c o m p a r e dw i t ht h el i n es e a r c hm e t h o d s ，i t d o e sn o tr e q u i r e 圾t ob e p o s i t i v ed e f i n i t e d u et oi t s s t r o n gc o n v e r g e n c ep r o p e r t i e sa n dr o b u s t n e s s ，t r u s tr e g i o n m e t h o d sh a v eb e e ns t u d i e db ym a n ya u t h o r s ，s e e 3 【4 【5 【6 7 】【8 9 1 0 f o rt h et r u s tr e g i o nm e t h o d s ，t h ec h o i c eo ft h et r u s tr e g i o nr a d i u si nt h es u b p r o b l e m ( 1 1 2 ) i sv e r yi m p o r t a n tt ot h ee f f i c i e n c yo ft h em e t h o d s h o w e v e r ，i nt r a d i t i o n a lt r u s t r e g i o nm e t h o d s ，t h et r u s tr e g i o nr a d i u sa ki si n d e p e n d e n to f 瓤a n db k t h i ss i t u a t i o n w o u l dd e c r e a s et h ee f f i c i e n c yo ft h e s em e t h o d s i n 1 z h a n ge t a 1 p r o p o s e dan e wt r u s tr e g i o ns u b p r o b l e m ，i nw h i c ht h et r u s t r e g i o nr a d i u su s e st h ei n f o r m a t i o no fg ka n d 岛，s e e ( 2 1 2 ) w i t ht h i sn e ws u b p r o b l e m ， t h e yc o n s t r u c ta na d a p t i v et r u s tr e g i o nm e t h o d n u m e r i c a le x p e r i m e n t ss h o wt h a tt h e a l g o r i t h mi sv e r ye f f i c i e n t a l lt h e s em e t h o d sc o n s t r u c ta ni t e r a t i v es e r i e sz ks u c ht h a tt h es e r i e s a ) = ，( k ) i s m o n o t o n i c a l l yd e c r e a s i n g h o w e v e r ，t h i su s u a l l ys l o w st h ec o n v e r g e n c er a t eo ft h e m i n i m i z a t i o np r o c e s s ，e s p e c i a l l yi nt h ep r e s e n c eo fs t e e p - s i d e dv a l l e y sf 1 1 j 【1 2 ， r e c e n t l y , t h en o n m o n o t o n i cl i n es e a r c ht e c h n i q u ef o ru n c o n s t r a i n e do p t i m i z a t i o ni s p r o p o s e db yg r i p p oe t a 1 1 2 】【1 3 1 【1 4 1 【1 5 1 d u et ot h eh i g he f f i c i e n c yo fn o n m o n o t o n i c m e t h o d s lm a n ya u t h o r sg e n e r a l i z e dt h en o n m o n o t o n i ct e c h n i q u et ot r u s tr e g i o nm e t h o d s a n dp r o p o s e dn o n m o n o t o n et r u s tr e g i o nm e t h o d s ，s e e 1 1 1 【1 6 1 7 】t h e o r e t i ca n a l y s i s a n dn u m e r i c a lr e s u l t ss h o wt h a tt h ea l g o t i t h m sw i t hn o n m o n o t o n ep r o p e r t i e sa r em o r e e f f i c i e n tt h a nt h ea l g o r i t h m sw i t hm o n o t o n e p r o p e r t i e s c o n i cm o d e lm e t h o d sf o ru n c o n s t r a i n e do p t i m i z a t i o nh a v eb e e nf i r s ts t u d i e d b yd a v i d o n 2 0 】i n1 9 8 0 ，s o r e n s e n 2 1jp u b l i s h e dd e t a i l e dr e s u l t so n ac l a s so fc o n i cm o d e lm e t h o d a n dp r o v e dt h a tap a r t i c u l a rm e m b e ro ft h i sc l a s sh a st h eq - s u p e r l i n e a rc o n v e r g e n c e i n t h e s em e t h o d s ，t h e yu s e dal i n es e a r c ht os t e pf o r w a r d i n 【8 】 2 2 2 3 【2 4 2 5 2 6 】，c o n i c m o d e lb a s e do i lt r u s tr e g i o nm e t h o d sa r es t u d i e d ，n u m e r i c a lr e s u l t ss h o wt h ee f f i c i e n c yo f t h ec o n i ct r u s tr e g i o nm e t h o d 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 ec o m b i n et h ea d a p t i v et r u s tr e g i o n m e t h o dw i t hn o n m o n o t o n i ct e c h n i q u et op r o p o s ean o n m o n o t o n ea d a p t i v et r u s tr e g i o n m e t h o da n d s t u d yi t sc o n v e r g e n c ep r o p e r t i e s n u m e r i c a lr e s u l t ss h o wt h ee f f i c i e n c yo ft h e n e wm e t h o d i nc h a p t e r3 ，w ec o m b i n et h ec o n i cm o d e lw i t ht h ea d a p t i v et r u s t r e g i o n m e t h o dt of o r man e wm e t h o dc a l l e dt h ec o n i ca d a p t i v et r u s tr e g i o nm e t h o d w ee s t a b l i s h t h ec o n v e r g e n c er e s u l t so ft h en e w m e t h o d ，a n dt h ee f f i c i e n c yo ft h em e t h o di st e s t e db y t h en u m e r i c a lr e s u l t s c h a p t e r 2 n o n m o n o t o n e a d a p t i v e t r u s t - r e g i o nm e t h o d f o r u n c o n s t r a i n e d pr o b l e m s 2 1i n t r o d u c t i o n o p t i m i z a t i o n w ec o n s i d e rt h ef o l l o w i n gu 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 砌r a i n ：。m ) ( 2 1 - 1 ) w h e r e ，( 叫i st w i c 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 t r u s tr e g i o nm e t h o d sh a v ev e r yn i c eg l o b a l a n dl o c a lc o n v e r g e n c ep r o p e r t i e s ，a n di th a sb e e ns h o w nt h a tt h e ya r ev e r ye f f e c t i v ea n d r o b u s tf o rs o l v i n gp r o b l e m ( 2 1 1 ) r e c e n t l y , t h en o n m o n o t o n i cl i n es e a r c ht e c h n i q u ef o ru n c o n s t r a i n e do p t i m i z a t i o ni s p r o p o s e db yg r i p p oe t a 1 1 2 】【1 3 】【1 4 【1 5 d u et ot h eh i g he f f i c i e n c yo fn o n m o n o - t o n i cm e t h o d ，t h i st e c h n i q u ei sc o m b i n e dw i t ht h et r u s t r e g i o na l g o r i t h mt od e a lw i t h u n c o n s t r a i n e do p t i m i z a t i o n 【1 1 】【1 6 【1 7 m o r er e c e n t l y ，z h a n ge t a l - 【l 】p r o p o s e da na d a p t i v et r u s tr e g i o nm e t h o d ，t h e yc o n s t r u c tan e wt r u s tr e g i o ns u b p r o b l e m ，i nw h i c ht h et r u s tr e g i o nr a d i u su s e st h ei n f o r m a t i o n o fg ka n db k ，i e ，t h e ys o l v et h ef o l l o w i n gs u b p r o b l e m ： m i n 机( 曲= g d + i i t b d s t i i d l lsa k( 2 1 ，2 ) w h e r ea k = c p l l q 女f i m - k ，0 c 1 ，五靠= | f 反“玑a n dpi s an o n n e g a t i v ei n t e g e r 反 i sas a f e l yp o s i t i v ed e f i n i t em a t r i xb a s e do ns c h n a b e la n de s k o wf 2 1r o o d m e dc h o l e s k v 3 n a n j i n gn o r m a lu n i v e r s i t y 4 f a c t o r i z a t i o n ，b k = b k + e k ，w h e r ee k = 0 i fb ki ss a f e l yp o s i t i v ed e f i n i t e ，a n d 邑i s ad i a g o n a lm a t r i xc h o s e nt om a k eb kp o s i t i v ed e f i n i t eo t h e r w i s e t h i sm e t h o dd e f i n e s ka u t o m a t i c a l l yb a s e do n9 ka n d 仇，w h i l ea ki nt r a d i t i o n a lt r u s tr e g i o nm e t h o d si s i n d e p e n d e n to f 9 ka n db k i nt h i sc h a p t e r ，w ew i l ld i s c u s san o n m o n o t o n i cv e r s i o no ft h ea d a p t i v et r u s tr e g i o n m e t h o d p r o p o s e d i n ”f u r t h e r m o r e ，i n s t e a do f s o l v i n g t h es u b p r o b l e m ( 2 1 2 ) e x a c t l y ，w e s o l v et h es u b p r o b l e m ( 2 1 ，2 ) i n e x a c t l yb yu s i n gt h et r u n c a t e dc o n j u g a t eg r a d i e n tm e t h o d 3 【4 t h en u m e r i c a lr e s u l t ss h o wt h a to u ra l g o r i t h mi s e f f e c t i v e t h i sc h a p t e ri so r g a n i z e da sf o l l o w s n e x ts e c t i o nw ed e s c r i b eo n rn o n m o n o t o n e a d a p t i v et r u s tr e g i o na l g o r i t h m i ns e c t i o n3w ep r e s e n ta l la l g o r i t h mt og e ta ni n e x a c ts o l u t i o n t ot h es u b p r o b l e m ( 2 1 2 ) ，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 er e s u l t so ft h ep r o p o s e d a l g o r i t h ma r ed i s c u s s e di ns e c t i o n4 ，t h en u m e r i e a lr e s u l t sa r er e p o r t e di ns e c t i o n5 2 2o u r a l g o r i t h m a sm e n t i o n e di ns e c t i o n1 ，w eo b t a i nt h et r i a ls t e p 巩b ys 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 m i n 机( d ) = 9 吾d 十l d t b k d s , t 1 i d l isa k( 2 2 1 ) w h ”e k ：酽1 1 乳l l 丽女，o c 1 ，丽 = 1 1 百k - 1 ，a n dp i san o i l n e g a t i v ei n t e g e r r e m a r k2 2 1i nt es u b p r o b l e m ，t ec o m p u t a t i o n 吖i i 露1 1 | i st h es a m ea sp , t h e r e f o r e m ec o m p u t a t i o n a lc o m p l e x i t y | o rs u b p r o b i e m ( 2 2 。i ) i so ( n 3 、 r e m a r k2 2 2w ew i l ln o ts o l v et h e d e s i g na ni n e x a c ta l g o r i t h mt os o l v ei t j s u b p r o b l e m ( 2 2 1 ) e x a c t l y a si n 1 1 1 i i n s t e a dw e w h i c hw i l lb ed i s c u s s e di ns e c t i o n ； r e l a x i n gt h ea c c e p t i n gc o n d i t i o no nd k ，w eu s et h en o n m o n o t o n i ct r u s t r e g i o nt e c h n i q u e l e t ，l ( 女) 2 ，( 。l 咔) ) 。s m j a ，。x ( 砷，( 。一j ) ( 2 2 2 ) w h e r em ( 0 ) = 0a n d0 m ( k ) sm i n m ( k 一1 ) + 1 ，m ) ，k 1 ，a n dm an o n n e g a t i v e i n t e g e r t h e nt h ea c t u a lr e d u c t i o no f ，( z ) i sd e f i n e db y a r e d k = ，l ( i ) 一，( z 女+ d k ) a n dt h ep r e d i c t i v er e d u c t i o no ff ( x ) i s p r e d k = f l ( k ) f ( x k ) 一t k ( d k ) ( 2 2 3 ) ( 2 2 4 ) c h a p t e r 2n o n m o n o t o n ea d a p t i v et r u s t r e g i o nm e t h o d5 t h et r i a ls t e pd ks a t i s f i e s 一t ( d k ) 卢1 1 9 ki i n n i n ，1 i l l 。g k 女l j j l ) ( 2 2 5 ) w h e r e 卢( o ，1 】( s e e ( 8 ”t h i sr u l e i su s e di nd e t e r m i n i n gt h ea p p r o x i m a t es o l u t i o no f t h es u b p r o b l e r a ( 2 2 1 ) n o ww eg i v ead e s c r i p t i o no fo u rn o n m o n o t o n ea l g o r i t h m a l g o r i t h m2 2 3 s t e p0 ，g i v e nx o r “，0 c 0 ，0 0 ， 0 s e tp o 。0 ，r o = 一g k ，s o = r o ，i = 0 s t e p2 c o m p u t e m = s t b k s i ( 2 3 1 ) 盯 i i 0t h e ng ot os t e p3 o t h e r w i s ec o m p u t er 0 s u c ht h a t 十r 8 ；| | = a k ( 2 3 2 ) s e t p = p i + r 吼a n ds t o p s t e p3 c o m p u t e 啦= r t r 。m ，( 2 3 3 ) 仇+ l = 挑+ a l 乱( 2 3 4 ) 可| j p + 1i i 0 ，s u c ht h a t s e t p 2p i + r s ta n dr e t u r n l 鼽+ t s i | | = 女 s t e p4 c o m p u t e r i + l r i o 。i b k s i i f l i r i + l l i l l l g k l i 靠 s e tp 2 p i + l a n dr e t u r n o t h e r w i s ec o m p u t e 觑= 晤1 啊1 r t r , 乱+ 1 = r i + 1 + 鼠魂 s e t i = i + la n d g ot o 印2 ( 2 3 5 ) ( 2 36 ) ( 2 3 7 ) ( 2 3 8 ) ( 2 3 9 ) l e m m a2 3 2 l e t 丹( j = 0 ，- 一，i ) b et h e i t e r a t e s g e n e r a t e db y t h e a l g o r i t h m t h e n 机嘞) ( j = 0 ，- ，i ) o ”s t r i c t l yd e c r e a s i n ga n d 机) 机( p 。) f u r t h e r ，l i p jl l ( j = 0 ，i ) a r es t r i c t l yi n c r e a s i n ga n d p r o o f s e et h e o r e m2 1i n 3 】口 扣| | l | p ( 2 3 1 0 ) ( 2 3 1 1 ) c h a p t e r2 n o n m o n o t o n ea d a p t i v et r i l s t r e g i o nm e t h o d 7 t h e o r e m2 3 3 s u p p o s et h a t t h et r i a ls t e pd ki sd e t e r m i n e db ya l g o r i t h m2 ，3 1 t h e n d ks a t i s f i e s ( 2 2 5 ) p r o o lf r o mt h es t r u c t u r eo fa l g o r i t h m2 3 1 ，w ek n o wt h a tt h es o l u t i o nd ko ft h e a l g o r i t h mh a st h ef o l l o w i n gf o r m ： fp i + 1i f ( 2 3 7 ) h o l d s ， d k = p i + t s ii f l 0a n d ( 2 3 5 ) i su s e d 【p i + f &i f 7 s 0a n d ( 2 3 2 ) i su s e d 蛐) s 一批i im i n ，黼) ( 2 肌2 ) c a s e1 t f 3 0 0 ，t h e r ea r et w os u b c a s e s ( i ) i fl i o o s 0 | | 8 1 1 口女i im i n k ，| l i l g i k k l o l ，- i ，k = l , 2 ( 2 4 2 ) w h e r e d ki sa ni n e x a c ts o l u t i o n 。ft h es u b p r o b l e m ( 2 2 1 ) t i i ) m a t r i c e s 悃k 、a r eu n t f o r m l y b o u n d e d i e t h e r ei sap o s i t i v es c a l a rks u c ht h a t i b k is k ，k = 1 ，2( 2 4 3 ) t h e f o l l o w i n gl e m m a sa r ei m p o r t a n tt ot h ea n a l y s i so ft h ec o n v e r g e n c eo ft h em e t h o d l e m m a2 4 2 s u p p o s et h a ta s s u m p t i o n2 1 ( i i ) h o l d s ，t h e nt h e r ei s ap o s i t i v es c a l a ri s u c ht h a t 出| | 刮9 七虮k = 1 ，2 ，( 24 ，4 ) p r o o f s i l l c e 1 1 4 1 1 ：扩| | 啦i i i l & - 1 | | l i e k - 1