（计算数学专业论文）解无约束优化及非线性最小二乘问题的自适应信赖域算法.pdf

g - j 摘要 对于一般的无约束最优化问题及其特殊情况非线性最小二乘问题而 言，信赖域方法是一种有效的方法而信赖域半径的选取对于信赖域方 法的效率有着很大的影响黑龙在文f 1 2 】中给出了一种自适应信赖域算 法，该算法利用r 函数以变化的速率来调整信赖域半径的大小章祥荪 等在文2 6 1 中也给出了一种自适应信赖域算法，它利用当前迭代点的梯 度和海赛阵信息来选取当前迭代步的信赖域半径数值试验表明，这两 种方法都比传统的信赖域方法有效本文的第一部分将文【1 2 】中的自适 应信赖域算法和当前流行的非单调技术结合，并利用文【1 6 】中信赖域和 线搜索相结合的思想，给出了求解一般的无约束最优化问题的带线搜索 的非单调自适应信赖域算法文中证明了新方法的全局收敛性数值试 验表明比起文【1 2 】中的信赖域算法，新算法更有效地节省了计算量本 文的第二部分将文【2 6 】中的自适应信赖域算法应用到文f l o 】中，给出了 求解非线性最小二乘问题的自适应锥模型信赖域算法该算法中我们允 许使用非精确的方法近似求解信赖域子问题文中给出了新算法的全局 收敛性和超线性收敛性。数值试验表明了该算法的有效性 关键词；无约束优化；非线性最小二乘问题；线搜索方法；信赖域方 法；锥模型；总体收敛性；超线性收敛性；非单调 p a b 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 f f i c i e n tm e t h o d st os o l v et h eg e n e r a lu n c o n s t r a i n e d o p t i m i z a t i o na n di t s 叩e c i a ls i t u a t i o n ，t h en o n l i n e a rl e a s ts q u a r e sp r o b l e m s t h ec h o i c eo f t h et r u s tr e g i o ur a d i u sh a sa l li m p o r t a n te f f e c to nt h ee f l i c i e n c yo f t h et r u s tr e g i o nm e t h o d h e i1 1 2 】p r o p o s e das e l f - a d a p t i v et r u s tr e g i o n “g 喇t h m ，i nw h i c ht h et r u s tr e g i o nr a d i u s i su p d a t e da tav a r i a b l er a t eb yr - f u n c t i o n z h a n ge t a 1 【2 6 】a l s op r o p o s e da na 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 n 幽o nt h eg r a d i e n ta n dh e s s i a n o 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 ss h o wt h a tb o t ht h em e t h o d sa r em o r e e 最c i o n tt h a nt h et a d i t i o n a lt 嗽r e g i o nm e t h o d t h ef i r s tp a r to ft h i st h e s i sp r o p o s e sa n e w n o n m o n o t o n i c s e l f - a d a p t i v e t r u s tr e g i o n a l g o r i t h m w i t h l i n e s e a h t o s o l v e t h e g e n e r a l u 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 nw h i c hw ec o m b i n et h es e l f - a d a p t i v et r u s tr e g i o n m e t h o di n 【1 2 】w i t ht h ep o p u l n o n m o n o t o n et e c h n i q u ea n du s ec o m b ；, a gt r u s tr e g i o n w i t hl l n es e a r c ht e c h n i q u e si n 【1 6 1 w ee s t a b l i s ht h eg l o b a lc o n v e r g e n c er e s u l to ft h e n e wm e t h o d n u m e r i c a lr e s u l t ss h o wt h a tt h en e wn o n m o n o t o n i cm e t h o dc a nb g m o r e c o m p u t a t i o nt h a nt h em e t h o di n 【1 2 】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 e t r u s tr e g i o nm e t h o di n1 2 6 】t of l o jt 0p r o p o s ea na d a p t i v ec o n i ct r u s tr e g i o nm e t h o df o r n o n l i n e a rl e a s ts q u a r e sp r o b l e m s i nw h i c hw ec a nt | i n e x a c tm e t h o d st os o l v et h et r u s t r e g i o ns u b p r o b l e ma p p r o x i n m t e l y 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 e n e wa l g o r i t h ma r ee 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 em e t h o dj 8e $ c i s n t k e yw o r d s u n c o n s t r a i n e do p t i m i z a t i o n ，n o n l i n e a rl e a s ts q u a r e sp r o b l e m ，l i n es c o f f c h m e t h o d ，t r u s tr e g i o nm e t h e d ，c o n i cm o d e l ，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 xc o n v e r g e n c e ， n o n m o n o t o n et e c h n i q u e 学位论文独创性声明 + y9 8 1 0 1 0 本人郑重声明； l 、坚持以求实、创新”的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发 表或撰写过的研究成果 5 、其他同志对本研究所做晦贡献均已在论文中作了声明并表示了谢 意 作者签名，圭丕拯 日 期；壁垒：生! 墨 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有 权保留学位论文并向国家主管部门或其撸定机构送交论文的电子版和纸质 版；有权将学位论文用于非赢利目的的少量复制并允许论文进人学校图书 馆被查阅；有权将学位论文的内容编人有关数据库进行检索；有权将学位 论文的标题和摘要汇编出版保密的学位论文在解密后适用本规定 作者签名：扬圭丕 日 期t翘q 厶结基 本文创新点 本文考虑的是求解一般的无约束最优化问题及其特殊情况非线性最小 二乘问题的非传统信赖域方法，主要由两个部分组成 本文的第一部分考虑的对象是一般的无约束最优化问题，文章从有效 地节省计算量的角度考虑，将文【1 2 】中的自适应信赖域算法和当前流行 的非单调技术结合，并利用文1 1 6 】中信赖域和线搜索相结合的思想。给 出了带线搜索的非单调自适应信赖域算法文中证明了新方法的全局收 敛性，并进行了数值试验 ， 本文的第二部分针对非线性最小二乘问题，利用文【1 0 】中求解非线性 最s j 、- - 乘问题的锥模型算法思想，给出了海赛阵中二阶信息项的割线近 似的不同校正公式，并利用文1 2 6 】中的自适应信赖域技术最终给出了求 解非线性最小二乘问题的自适应锥模型信赖域算法算法中我们允许使 用非精确的方法近似求解信赖域子问题文中给出了新算法的全局收敛 性和超线性收敛性分析以及数值试验的结果 i i c h a p t e r1 i n t r o d u c t i o n w ec o n s i d e ra l g o r i t h m sf o rs o l v i n gt h eg 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 np r o b l e m 蠹鎏m ) ( l 1 1 ) a n di t ss p e c i a ls i t u a t i o n ，t h en o n l i n e a rl e a s ts q u a r e sp m b l e m bt h a ti s ，t h eo b j e c t i v ef u n c t i o n ，0 ) h a st h ef o l l o w i n gs p e c i a lf o r m 州：；妻晌 j = l ( 1 1 2 ) w ea s s u m et h a tt h eo b j e c t i v e m c t i o n ，( z ) i sar e a l - v a l u e dt w i c ec e n t i n u o a s yd i f f e r e n o t i a b l ef u n c t i o na n db o u n d e db e l o w t h el i n es e a r c hs t r a t e g ya n dt h et r u s tr e g i o nm e t h o da r et w ob a s i ci t e r a t i v em e t h o d 8 f o rs o l v i n g ( 1 - 1 1 ) t o s i l mg l o b a lc o n v e r g e n c e ； t h eb a s i c 暑t n l c t u 糟o fl i n es e a r c ha l g o r i t h mi s 曲f o l l o w e a tt h ec u r r e n ti t e r a t e 霉， w ec h o o s ead e s c e n td i r e c t i o n 以s a r i s 聊n gv ，0 ) t 如 0i sat r u s tr e g i o nr a d i 瑚 i nt h i sc h a p t e r ，t h en o t a t i o n1 1 d e n o t e st h ee u c l i d e a n r mo l lr “a f t e ro b t a i n m ga t r i a ls t e pd k ，w h i c hi s e x a c to ra p p r o x i m a t es o l u t i o no fs u b p r o b l e m ( 2 1 2 ) 一( 2 1 3 ) ，t h e t r u s tr e ! g i o i lm e t h o dc o m p u t e st h er a t i o 飞= 箍= 铡掰 4 ( 2 1 4 ) c h a p t e r2 n o n m o n o t o n i cs e l f - a d a p t i v et r u s tr e g i o nm e t h o dw i t hl i n es e a r c h5 t oc h e c kw h e t h e rt h et r i a ls t e pd ki sa c c e p t a b l e t h e nt h et r u s tr e g i o nr a d i u sa ki sa l s o u p d a t e da c c o r d i n gt ot h ev a l u eo fr ks i n c e kr e f l e c t st h ee x t e n tt ow h i c ht h eq u a d r a t i c m o d e lc k ( d ) a p p r o x i m a t e st h eo b j e c t i v ef u n c t i o nl ( x k + d ) f o rt h et 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 ，t h et r u s tr e g i o nr a d i u sa ki 8u p d a t e da tac o n s t a n tr a t e h o w e v e r h e i 【1 2 p r o p o s e das e l f - 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 nw h i c ha k i su p d a t e da tav a r i a b l e r a t eb yr - f u n c t i o no fr k 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 ea l g o r i t h m i t 珥a l s on o t i c e dt h a tn o c e d a la n dy u a n 【1 6 s u g g e s t e dac o m b i n a t i o no ft h et r u s t r e g i o na n dl i n es e a r c ht e c h n i q u e s i nt h et r a d i t i o n a lt n m tr e g i o nm e t h o d ，i ft h et r i ms t e p 呶p r o d u c e db ys u b p r o b l e m ( 2 1 2 ) 一( 2 1 3 ) i 8n o ta c c e p t a b l e ，x k + 1w i l lb es e t 舾女a n d t h es u b p r o b l e mw i t har e d u c e dt r u s tr e g i o nr a d i u sw i l lb es o l v e d r e s o l v i n gt h et r u s t r e g i o ns u b p r o b l e mc a nb ec o s t l y i nc o n t r a s t ，l i n es e a r c hm e t h o d sr e q u i r er e l a t i v e l y f e w c o m p u t a t i o n st od e t e r m i n ean e wt r i a lp o i n t t h 口e f o mt m d e rc e r t a i nc o n d i t i o n sa b o u t d k ，w ec m as w i t c ht ot h el i n es e a r c ht e c h n i q u ea tt h eu n a c c e p t a b l et r i a ls t e p t h i sm a y l e a dt oac o n s i d e r a b l ec o m p u t a t i o n a ls a v i n g b e c a u s et h em o n o t o n i cd e c r e a s i n gr e q u i r e m e n tf o rt h es e q u e n c e ，扛i ) m a yc a l l s ea s e r i e so fv e r ys m a l ls t e pi ft h ec o n c u r so fo b j e c t i v ef u n c t i o ni8 x eaf a m i l yo f e u r v w i t h l a r g ec t l r v a t l l r e ，n o n m o n o t o n i ct e c h n i q u e 塔u s e f u l i nt h i sc h a p t e r ，w ew i l lm o d i f ya n di m p r o v et h es e l f - 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 p r o p o s e di n 【1 2 b ya d o p t i n gt h ea b o v ei d e a s ：b a c k t r a c k i n gl i n es e a r c ha n dn o n m o n o t o n i c t e c h n i q u e b o t ht 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 le x p e r i m e n ts h o wt h a tt h en e wm e t h o d i 8p o t e n t i a l l yc o m p e t i t i v e t h i sc h a p t e ri so r g a n i z o d f o l l o w s n e x ts e c t i o nw ed i s c u s so u rn e wa l g o r i t h m i n s e c t i o n3 ，t h eg l o b a lc o n v e r g e n c ep r o p e r t yo ft h ea l g o r i t h mi 8p r o v e d i ns e c t i o n4 ，t h e r e s u l t so fn 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 t h ef i n a lr e m a r k sa r eg i v e ni ns e c t i o n5 2 2o u ra l g o r i t h m f i to fa 1 1 w ei n t r o d u c et h ed e f i n i t i o no fr - f u n c t i o n d e f i n i t i o n2 2 1a n y 口扎e d i m e n s i o n a lf u n c t w nr 目( t ) d 明n e a 伽r = ( 一0 0 ，+ o o ) 埘j l t h ep a r a m e t e rt 1 ( o 1 ) i sn nr - f u n c t i o n 矿a n do n l y 矿i ts a t i s f i e s ： ，砂( t ) 扫n 鲫d r e u s i n g 伽( 一0 0 ，+ ) ； 俐1 1 理岛( t ) = 岛，w h e r e 历( 0 ，1 ) 妇as m a l lc o n s t a n t ； ，黝( t ) s1 7 l ，厂d ra l l t 町w h e r e 7 l ( 0 ，1 一卢1 ) 舀ac o n s t a n t ； 例( 们= 1 + ，w h e r e 仇( 0 ，+ ) 妇a c o n s t a n t ； 俐1 啦岛( t ) = 岛，w h e r e 历( 1 + 能，+ ) 妇ac o n s t a n t p r o mt h ed e f i n i t i o nw ec a l le a s i l yg e tt h ef o l l o w i n gi m p o r t a n tp r o p e r t i e so fr - f u n c t i o n s ： n a n j i n gn o r m a lu n i v e r s i t y 6 t h e o r e m2 2 2a nr - f u n c t z o n 岛( ) n 旆e wq ( 0 ，1 ) ，s a t z s f i e s 0 p ls ( t ) l 一7 l 1 ，v t ( 一，叩) ， ( 2 2 1 ) 1 1 + 加嘞( t ) 岛 0 ，0 ，0 风 1 ，0 1 + 7 2 ，0 c l c l ，s e t + l = $ - + 以，g o t os t e p5 o l l u i s ec h o o s ek = 1 ， 0 3 ， 2 ， u n t i lt h ef o l l o w i n g 衲q 矗纫i ss a t i s f i e d ，( 瓢+ a k d k ) s ，l ( k ) + o a k 鳍d k ( 2 2 8 ) s e t x k + l = 巩+ k 如，g o t os t 印5 c h a p t e r2 n o n m o n o t o n i cs e l f - a d a p t i v et r u s tr e g i o nm e t h o dw i t hl i n es e a r c h7 s t e p5 ，k + 1 = 见。( m ) k s e t m ( k + 1 ) = m i n m ( k ) + 1 ，m ) ，k = k 4 l ，9 0t os t e p j r e m a r k2 2 4a tt h ek t hs t e p , w h e np ksc l 。w e a l w a y sr i n das u f f i c i e n ts m a l l a k 0s u c ht h a t ( 2 2 8 ) h o l d s w e v e r i f yt h i sc l a i mb yu s i n gt a y l o r st h e o r e m f ( w k + a k d k ) 一h ( x ) 一o a 女目善d sl ( x k + a k d k ) 一l ( x k ) 一口a k 露畋 = ( 1 一口) a 露如+ d ( a )( 2 2 9 ) s i n ed 暑鲰一r 0 肌0 m i n k ，i i g k l l l l 8 k 1 1 ) c l ，= ( o ，1 ，2 ， v n a n j i n gn o r m a lu n i v e r s i t y 8 l e m m a2 3 2t h es e q u e n c e x k g e n e r a t e db ya l g o m t h m22 3r e m a m ss nn o ，a n d 撕( i ) 妇n o n m c r e a s i n 9 p r o o f w h e nk i ，t h a ti 8 ，p k = ( ，i ( ”一f k + 1 ) p r e d k q ，s i n c ec l 0a n dp r e d k 0 ， w e h a v et h a t 忙) f k + 1 w h e nk j ，t h a ti s ，a + l ( 七) + 口a 七靠d k ，s i n 鲤d k + 1 s o ，f o ra i l 毛w eh a v ef l ( k l 1 4 + i i ti sc l e a rt h a t 知e a s s u m et h a t 钆n o ，f o r 七0 s i n c et ( k ) k ，f t c k ) o ， t h e ni tf o l l o w st h a t + l 0 ， ( 2 3 3 ) w h e r e6 0i snc o n s t a n t , t h e nt h e r ee x i s t s 口c o n s t a n t ，y 0s u c ht h a t 趣2 磊，七= o ，1 ， ( 2 3 4 ) 2 曲8 地慨妇蛳e d 妇螈= 趱i i b , i i + l - p r o o f b e c a u s ev f ( z ) i su n i f o r m l yc o n t i n u o u s ，t h e r ee x i t sap o s i t i v en u m b e r 口s u c h t h a t 【v ，扛+ 田一v f ( z ) l ；r ( 1 - e 2 ) 6 1 1 d k l l ，z 兄” ( 2 3 5 ) i ss a t i s f i e df o ra l ll i d l l 口w es h o wb yi n d u c t i o nt h a t ( 2 3 4 ) h o l d sw i t h 1 = m m a o m o ，风口 南，1 5 , r ( 1 一c 2 ) 角6 ) ( 2 3 6 ) w h e nk = 0 ，i ti so b v i o u st h a ta 0 ，胁，s o ( 2 3 4 ) h o l d sf o r 七= 0 a s s u m et h a t ( 2 3 4 ) i st r u ef o r ，w ew i l lp r o v et h a t ( 2 3 4 ) h o l d sf o r 詹+ 1 s i n c em ki sn o n d e c r c e s i n g ，t op r o v e ( 2 3 4 ) f o r 蠹+ 1 ，i t8 1 l m c e f lt oe s t a b l i s ht h er e l a t i o n “t2 壶( 2 和 s i n c ea k + t = 冠c 2 ( p k ) a k ，i tf o l l o w sf o r mt h e o r e m2 2 2t h a tw h e nm c 2 ，l a k i nt h i se a s e ，r e l a t i o n ( 2 3 7 ) i st r i v i m t h e r e f o r e ，i nt h er e m a i n d e ro fp r o o f , p k 2 ( i c 2 ) r 8 m i n a k ，6 i i b , i i 一( 1 一e ) r 6 1 1 d , k l l ( 1 一c 2 ) r 6 2 m i n a k ，6 i i 口 0 一k ) = ( 1 一c 2 ) r 6 m i n a k ，2 a l l b k l i 一 ( 2 3 1 2 ) u s i n gt h ea b o v ec o n d i t i o n ，w ec 吼g i v ebc o n s t a n tl o w e rb o u n do i lt h ep r o d u c t 知8 园训 i nf a c t ，i f 七王k l is 最i tf o l l o w sf r o m ( 2 3 1 2 ) t h a t t h u s ，t h ef o l l o w i n gr e l a t i o n i f k 0 ( 1 一o a ) r & 0 母川 r a i n ( 1 一。2 ) 确6 1 风 a l w a y sh o l d s s o ，七十t 俄七 7 口k t h e r e f o r e ，b yi n d u c t i o n ，( 2 3 4 ) h o l d sf o ra l lk ( 2 3 1 3 ) ( 2 3 1 4 ) 1 慨t h u s ，( 2 3 4 ) h o l d sf o rk + 1 口 l e m m a 兰3 4 可仇d 凸百o b i8 佗u n i 一o r m t u6 d “n d 甜n 几d ( 2 3 3 ) h o t & , t h e nt h e r e e i t so c o n s t a n ta 0s u c h t h a t 讹正a a ， n a n j i n gn o r m a lu n i v e r s i t y 1 0 p r o o f w h e nji saf i n i t es e q u e n c e ，i ti so b v i o u st h a tt h ec o n c l u s i o ni st r u e w h e nj i sa ni n f i n i t es e q u e n c e ，w ep r o v ei tb yc o n t r a d i c t i o n a s s u m et h a tt h el e m m a i sn o tt r u e ， t h a ti s ，t h e r ee x i s t sai n f i n i t es u b s e q u e n c ets u c ht h a t o 。l i r a k t a 2 0 i tf o l l o w sf r o ma l g o r i t h m2 2 3t h a t 、f ( x k + 等靠) 一，( z ) 之，+ 警如) 一，( ) 。a 。k 一，t ，d k s i n c e ，+ - 警d k ) 一m 扣等飒+ 。( - 警l l d k l l ) ， ( 1 - - a ) 等以州勃酬) 2 o d e r i v i n g ( 2 3 x 8 ) b y 警l l d k i ia n dn o t i n gt h a t1 一口 0a n dg 手矗50 ，w e 。b r a i n h l i 5 丽9 z d k k e t = o 一i i 如“ i tf o l l o w sf r o m ( 2 2 4 ) ，( 2 3 1 ) a n d ( 2 3 3 ) t h a t 9 蚕d - r l l g a l lm i n a k ，i l g d l l b d s r s m i n a ，6 k t h 邶 。躲k e t 尚_ o 七一， “d 七i l t h e o r e m2 3 5a s s u m et h a ta s s u m p t i o n2 3 1h o l d s a l g o r i t h m2 2 s t h e n l i * m 。i 。n fi l s k l l = o ( 2 3 1 5 ) ( 2 3 1 6 ) ( 2 3 1 7 ) ( 2 3 1 8 ) ( 2 3 1 9 ) ( 2 3 2 0 ) ( 2 3 2 1 ) l e t # k ks e q u e n c eg e n e 毗db y ( 2 3 2 2 ) p r o o f iw ep r o v ei tb yc o n t r a d i c t i o n a f l s u n l et h a t ( 2 3 2 2 ) 扭n o tt r u e ，t h a t 域t h e r e e x i s t sac o n s t a n t5 0s u c ht h a tj i g , , , l l 6 , v k w h e nq k ) 一1 j ，i tf o l l o w sf r o m ( 2 2 4 ) a n dl e m m a 2 3 4t h a t ，锄( t ) ) = ( x f t a ) 一1 + a t ( k 一l 画( 耐一1 ) 。到：深) 一1 ) ，( 却耻) 一1 1 ) + 。( ) 一l 靠) 一l 西( 砷一l l l ( 1 ( k ) - * ) - m a l ( k ) - i ) - l a t ( 1 , ) - t , 啬揣 l t ( t ( k ) 一1 ) 一r a a t ( k ) 一1 5m i n a t ( k ) 一1 ，8 1 k f t q ( k ) 一1 ) 一r a a 6 m i n a l ( a ) 一l ，s k ( 2 3 2 3 ) c h a p t e r2 n o n m o n o t o n i cs e l f - a d a p t i v et r u s tr e g i o nm e t h o dw i t hl i n es e a r c h 1 1 w h e nl ( k ) 一i i ，i tf o l l o w sf r o m ( 2 2 3 ) t h a t l ( x l ( k ) ) = c 恐。, n a n j i n gn o r m a lu n i v e r s i t y w ed e n o t et h en u m b e ro fg r a d i e n te v a l u a t i o n sb yn g t h en u m b e ro ff u n c t i o ne v a l u - a t i o n sb yn fa n dt h es i z eo fp r o b l e m sb yn 二i st h ec o m m o nl o g a r i t h mo fp a r a m e t e r f a c t o rt ot h es t a n d a r di n i t i a lp o i n ta c c o r d i n gt ot h er u l eg i v e ni nf 1 4 ，t h a ti s ，i fx 0i st