（计算数学专业论文）two+nonmonotone+algorithms+for+composite+nonsmooth+programming+problems.pdf

摘要 本文研究复合非光滑极小化问蹈r a i n ( ，扛) ) ，其中目标函数中，：冠”寸 兄”是局部l i p s c h i t z 函数，h ：r ”_ 只是连续可微的凸函数该问题在实 际生活中有很强的应用背景，大量的工程和统计问题都可以归结为复合极小 化问题因此已有很多文章对这类问题进行了探讨，其中s a m p a i o ，y u a na n d s u n 对此问题给出了信赖域处理的方法，并对算法做了收敛性分析 在本文中，我们结合非单调技术研究了复合非光滑极小化问题，分别给 出了解该问题的非单调线搜索方法和非单调的信赖域方法在论文的第一部 分，我们对问题的背景以及已有的研究成果作了一个简要的介绍，同时也交代 了本论文的出发点和动机在第二部分，我们将非单调技术与线搜索方法相结 合，给出了解复合非光滑极小化问题的一种非单调线搜索算法并证明了该算 法具有全局收敛性该算法推广了p a n g 解复合问题的算法在第三部分，我 们进一步将非单调技术与信赖域方法结合，给出了解复合非光滑极小化问题 的一种非单调信赖域算法，同样对算法的收敛性进行了讨论 关键词：非光滑优化，非单调线搜索，信赖域算法，临界点 2 a b s t r a c t ac l a s so fn o n s m o o t hc o m p o s i t em i n i m i z a t i o np r o b l e m s ( p ) m i n ( ，( z ) ) a r e c o n s i d e r e di nt h i st h e s i s w h e r ee a c hf ：r “- - + r “i sal o c a l l yl i p s c h i t z i a n f u n c t i o n ，a n dh ：r “- - + ri sac o n t i n u o u s l yd i f f e r e n t i a b l ec o n v e xf u n c t i o n i np r a c t i c e ，m a n yp r o b l e m sf r o me n g i n e e r i n ga n ds t a t i s t i c sp r o b l e m sf a l li n t o t h ec l a s so f p r o b l e m s ( p ) f o ri n s t a n c e ，t h ep r o b l e m o fs o l v i n gt h es y s t e mo fn o n s m o o t h e q u a t i o n sa n dt h el e a s ts q u a r e sp r o b l e mw i t hn o n s m o o t hd a t a a r es p e c i a l c a s e so f ( p ) b e c a u s eo fi t sp r a c t i c a li m p o r t a n c e ，t h i sc l a s so fp r o b l e m s ( p ) h a s r e c e i v e dal o to fa t t e n t i o nf r o mt h er e s e a r c hc o m m u n i t y i np a r t i c u l a r ，s a m p a i o ， y u a na n ds u nh a sp r o p o s e dat r u s tr e g i o nm e t h o df o r ( p ) a n da l s op r o v i d e dt h e c o i i x e r g e n c ea n a l y s i st os u p p o r tt h e i ra l g o r i t h m i cp r o p o s a l s m o t i v a t e dp a r t l yb y t h e i rw o r k ，w ep r e s e n tt w on o n m o n o t o l l ea l g o r i t h m sf o rt h i sc l a s so fn o n s m o o t h c o m p o s i t em i n i m i z a t i o np r o b l e m sw h i c hb a s e do nl i n es e a r c hm e t h o da n dt r u s t r e g i o nm e t h o dr e s p e c t i v e l yi nt h i st h e s i s a f t e rab r i e fi n t r o d u c t i o no ft h ep r o b l e m s ( p ) i nt h ef i r s tc h a p t e r ，an o n m o n o t o n el i n es e a r c ha l g o r i t h mf o rt h i sc l a s s o fp r o b l e m si sp r o p o s e di nt h es e c o n dc h a p t e r ，a n dt h eg l o b a lc o n v e r g e n c eo ft h e a l g o r i t h mi sa l s os t u d i e di n t h i sc h a p t e ri nt h et h i r da n dt h ef i n a lc h a p t e r ，w e p r o v i d ean o n m o n o t o n et r u s tr e g i o nm e t h o da sw e l la st h eg l o b a lc o n v e r g e n c e a n a l y s i so ft h en e wa l g o r i t h m k e yw o r d s n o n s m o o t ho p t i m i z a t i o n ，n o u m o n o t o n el i n es e a r c h ，t r u s tr e g i o n a l g o r i t h m ，c r i t i c a lp o i n t 果。 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名：冱聋毫士 日 期：至2 生垒：z 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行检 索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密 后适用本规定。 作者签名：主聋主丞 日 期：逝! 幺色曼 c h a p t e r 1 i n t r o d u c t i o n 1 1i n t r o d u c t i o n i nt h i st h e s i sw ec o n s i d e rac l a s so fn o n s m o o t hc o m p o s i t em i n i m i z a t i o n p r o b l e m s ( p )r a i n ( ，( z ) ) ， w h e r ef ：r “_ r ”i sal o c a l l y l i p s c h i t z i a nf u n c t i o n a n dh ：r “- ri sa c o n t i n u o u s l yd i f f e r e n t i a b l ec o n v e xf u n c t i o n s t a r t i n gw i t ht h ew o r ko fc l a r k e 1 t h e r eh a sb e e nag r o w i n ga m o u n to f r e s e a r c ho fi nt h ea r e ao fn o n s m o o t h o p t i m i z a t i o n t h e s er e s e a r c ha c h i e v e m e n t s i n c l u d et h ew o r k so ff l e t c h e r 2 j p a n g ，h a na n dr a n g a r a j 3 q ia n ds u n 4 1 a n dy u a n 卧f l e t c h e r 2 】c o n s i d e r e dt r u s tr e g i o nm e t h o d sf o rt h e c o m p o s i t e n o n d i f i 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 m r a i n y ( x ) = g ( x ) + ( ，( z ) ) w h e r e 口：彤_ ra n d ，：r ”_ r ”a r ec o n t i n u o u s l y 出f f e r e n t i a b l ef u n c t i o n a n dh ：r “_ ri sac o n v e xb u tn o n s m o o t hf u n c t i o nb o u n d e db e l o w h o w e v e r m a n yp r a c t i c a lp r o b l e m sf r o me n g i n e e r i n ga n ds t a t i s t i c sp r o b l e m sc o m ed o w n t ot h ec l a s so fp r o b l e m s ( p ) f o ri n s t a n c e ，t h ep r o b l e mo fs o l v i n gt h es y s t e mo f n o n s m o o t he q u a t i o n sa n dt h ei e a s t s q u a r e sp r o b l e mw i t hn o n s m o o t hd a t aa r e s p e c i a lc a s e so f ( p ) b e c a u s eo fi t sp r a c t i c a l 油p o r t a n c e ，t h i sc l a s so fp r o b l e m s 1 n a n j m gn o r m a lu n i v e r s i t y 2 ( p ) h a sl e c e i v e d al o to fa t t e n t i o nf r o mt h er e s e a r c hc o u l n l u n i t y i np a r t i c u l a r ， s a m p a i o 6 1 a na n ds u n 【7 h a sp r o p o s e dat r u s tr e g i o nm e t h o df o r ( p ) a n d a l s o p r o i d e d t h ec o n v e r g e n c ea n a l y s i st os u p p o r tt h e i r a l g o r i t h m i cp r o p o s a l s t h i sw o r ka l s oe x t e n d e dt h et h e o r yo ft r u s t r e g i o na l g o r i t h mf o r n o n s m o o t h o p t i m i z a t i o ng i v e nb yf l e t c h e r ，p o w e l l ，a n dy u a n m o t i v a t e dp a r t l yb yt h e i r w o r kw ew o u l dp r o p o s et w on o n m o n o t o n ea l g o r i t h m sf o rt h i sc l a s so fp r o b l e m s ( p ) i nt h i sd i s s e r t a t i o n a sw en o t e d al a r g ep a r to fe x i s t i n ga l g o r i t h m sf o rt h en o n s m o o t h o p t i m i z a t i o np r o b l e m sa r em o n o t o n ea l g o r i t h m s h o w e v e r ，t h ei m p o s i n gm o n o t o n i c i t yo f t h es e q u e n c eo fo b j e c t i v ef u n c t i o nv a l u e si sn o tw i t h o u td r a w b a c k s at y p i c a l c a s ei sw h e nt h ei t e r a t i o ni st r a p p e dn e a ra d e e pn a r r o wc u r v e dv a l l e y , w h i c hc a n r e s u l ti n 、。e r ys h o r ts t e p so rz i g z a g g i n gt h a ti st os a yt h em o n o t o n i c i t yc a nc a u s e s e r i o u sl o s so f e f f i c i e n c y d i f f e r i n gf r o mt h em o n o t o n em e t h o d s ，t h en o n m o n o t o n e m e t h o d sr e l a xt h en l o n o t o n el i m i t a t i o na n da l l o wt h ei t e r a t i v es e q u e n c et oo c e a s i o n a l l yg e n e r a t ep o i n t sw i t hu o n m o n o t o n eo b j e c t i v ev a l u e s t h ee f f i c i e n c ya n d a d v a n t a g e o u so ft h en o n r n o n o t o n et e c h n i q u eh a sb e e np r o v e db ys o m en u m e r i c a l r e s u l t s t h e r e f o r e ，i nt h i sp a p e rw ep r e s e n tt w on o n m o n o t o n ea l g o r i t h m sw h i c h a r eb a s e do nl i n es e a r c hm e t h o da n dt r u s tr e g i o nm e t h o dr e s p e c t i v e l y t h et e c h n i q u eo fn o n m o n o t o n el i n es e a r c ht e c h n i q u ew a nf i r s t p r o p o s e db y g r i p p oe ta l 【8 f o rn e w t o n sm e t h o d s n u m e r i c a lr e s u l t sr e p o r t e di nt h a tw o r k i n d i c a t et h a tt i l en o n m o n o t o n el i n es e a r c ht e c h n i q u em a ya l l o wac o n s i d e r a b l e s a v i n gb o t hi nt h en u m b e r o fl i n es e a r c ha n di nt h en u m b e r o ff u n c t i o ne v a l u a t i o n t h e r e f o r e ，i nt h ec h a p t e r2o ft h et h e s i s ，au o n m o u o t o n el i n es e a r c ha l g o r i t h m i sp r e s e n t e df o rt h en o n s m o o t hc o m p o s i t eo p t i m i z a t i o np r o b l e m ( p ) t h eg l o b a l c o n v e r g e n c eo f , t h ea l g o r i t h mi sa l s op r o v e di nt h i sc h a p t e r t h e p r o b l e m o ft r u s tr e g i o nf o rn o n s m o o t h o p t i m i z a t i o na n dn o n s m o o t he q u a - t i o n sh a sb e e nc o n s i d e r e db yf l e t c h e r s a m p a i o ，y u a na n ds u n 【7 i q ia n d s u n 4 1a n ds u na n dy u a n 【6 q ia n ds u n 4 】e x t e n d e dt h ec l a s s i c a lt r u s tr e g i o n c h a p t e r1i n t r o d u c t i o n3 a l g o r i t h mt o t h en o n s m o o t hc a s ew h e r et h eo b j e c t i 、，ef o n c t i o ni s l o c a l l yl i p s c h i t z i a n a n dp r o v e dt h a tt h e i ra l g o r i t h mi s g l o b a l l yc o n v e r g e n t o nt h eo t h e r h a n d ，t h en o n m o n o t o n et e c h n i q u ew a sg e n e r a l i z e dt ot r u s tr e g i o nm e t h o d st h e o r e t i ca n a l y s i sa n dn u m e r i c a lr e s u l t ss h o w0 h a tt h e a l g o r i t h m sw i t hn o n n - o n o t o t l e p 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 eo n e sw i t hm o n o t o n e p r o p e r t i e s ，s o ，c o m b i n i n gt h et r u s tr e g i o na l g o r i t h mo fq ia n ds u n 4 w i t ht h en o n m o n o t o n et e c h n i q u e ， w ep r o p o s ean o n m o n o t o n et r u s tr e g i o na l g o r i t h mf o rt h en o n s m o o t h o p t i m i z a t i o np r o b l e m s ( p ) a sw e l la 5t h eg l o b a lc o n v e r g e n c ea n a l y s i so fo u ra l g o r i t h mi n t h ec h a p t e r3 1 2p r e l i m i n a r i e s t h r o u g h o u tt h i sp a p e r ，w ed e n o t er “t h ef i n i t e d i m e n s i o n a ls p a c e ，a n da s s n m ea l l f u n c t i o n sl o c a l l yl i p s c h i t z i a nc o n t i n u o u s ，t h ef o l l o w i n gc o n c e p t sa n d p r o p e r t i e s c a nb ef o u n di n f l 】 d e f i n i t i o n1 2 1 口，l e tf ：r “_ r ，a n dz r “b es u c ht h a tf ( x ) i s f i n i t e ， t h el o w e ra n d u p p e r d i n id i r e c t i o n a ld e r i v a t i v e so l l a txi nt h ed i r e c t i o nu 蛩 a r eg i v e nr e s p e c t i v e l ya 8 方叫= 1 i m 搿【，( z + 刎一，( 圳 付( z ，口) = l i ms u p f ( x + t v ) 一，( z ) t d e f i n i t i o n1 2 2 f i jt h ec l a r k ed i r e c t w n a ld e r i v a t i v ey o 讧。u 1 0 ffa tzi n t h ed i r e c t i o nu r “i sd 西n e db y f o ( z ，= l i m ，s u p f ( x + t v ) 一，( z ，) z o t o t h ec l a r k es u b d i f f e r e n t i a la | 蛐o f | a txi 8d e f i n e db y a ，( z ) = r “if r f o ( 。，”) ，v v r ”) d e f i n i t i o n1 2 3 e 1 1t h ef u n e t i o njir n _ r i ss a i dt ob el o w e rs e r n i c o n t i n u o u sa t2 7 0 ，矿 f ( x o ) 墨l i mi n f ，( 。) n a n j m gn o r m a lu n i v e r s i t y 4 t h e f u n c t i o nf ：r 1 呻ri ss a i dt ob eu p p e rs e m i c o n t i n u o t t sa tz o ，扩 f ( x o ) l i ms u p ，( z ) z z l e m m a 1 2 4 ( 1 】l e tf ：r ”_ r b el o c a l l yl i p s c h i t z i a nf u n c t i o n z 船 t h e n ( 1 ) 2 ) ( 3 ) ，ox ，d ) = m a x f 7 d1f o f ( x ) ，vd 舻， p ，f 。) i s 。c o m p a c ts e ta n d 9 ，f z ) 西 ，o ( 。，一) i s ap o s i t i v e l yh o m o g e n e o u sa n ds u b l i n e a r d e f i n i t i o n 1 2 5 t i l l e tf = 媳l ， t 并：礤_ 酽b ec o n t i n u o u s d i f f e r e n t i a la tz r “，t h e n ej a c o b im a t r i xj ( x 1 r m 。“i sd e f i n e da s m ，：f ，罄o _ l 蕤o l , _ 嫠1 i 啦啦垃j d e f i n i t i o n1 2 6 1 i ll e tf = 毡l 。， 搿i 酚_ r m ? a n d e a c h | t ? i = 1 ，2 ，7 nb el o c a l l yl i p s c h i t z i a nc o n t i n u o u s t h e nt h eg e n e r a l i z e dj a c o b im a t r i x j ( z ) r ”。“i sd d i n e da s o f ( x ) r = z r ”。“f ，( z ) = l i ml ，( z k ) ) ， z c h a p t e r 2 ano n m o n o t o n el i n es e a r c h l 1 _ - 一， 1 m e t h o df o rn o n s m o o t h 一 0 0 t i m i z a t i o n 2 1i n t r o d u c t i o n c o n s i d e rt h ec o m p o s i t ep r o g r a m m i n g ( p ) r a i nf ( z ) = h ( ，( 。) ) 、 z r “ 、 一 ( 2 11 ) w h e r ef ：r “- - + r “i sal o c a l l yl i p s c h i t z i a nf u n c t i o n a n dh ：r “- - - ) ri sa c o n t i n u o u s l yd i f f e r e n t i a b l ec o n v e xf u n c t i o nb o u n d e db e l o w p r o b l e m ( 2 1 ，1 ) h a sb e e ns t u d i e di nm a n yl i t e r a t u r e s ( s e e 4 - 6 ) ，s o m el i n e s e a r c hm e t h o d sa n dt r u s tr e g i o nm e t h o d sw e r ep r e s e n t e d i np a r t i c u l a r ，s a m p a i o ， y u a na n ds u n 7 】h a sp r o p o s e dat r u s tr e g i o nm e t h o df o r ( p ) a n da l s op r o v i d e d t h ec o n v e r g e n c ea n a l y s i st os u p p o r tt h e i ra l g o r i t h m i cp r o p o s a l s a l a r g ep o r t i o no ft h e s em e t h o d sr e q u i r em o n o t o n i c i t yo ft h eo b j e c t i v ev a l u e s ，b u tr e c e n tr e s e a r c h e si n d i c a t et h a tt h em o n o t o n e l i n es e a r c hm a yh a v es o m e d r a w b a c k s at y p i c a lc a s ei sw h e nt h ei t e r a t i o ni s t r a p p e dn e a rad e e pn a r r o w c u r v e dv a l l e y , w h i c hc a nr e s u l ti nv e r ys h o r ts t e p so rz i g z a g g i n g t h a ti st os a y t h em o n o t o n i cl i m i t a t i o nc a nc a u s es e r i o u sl o s so fe f f i c i e n c y h o w e v e r t h en o n m o n o t o n em e t h o d sa l l o wt h ei t e r a t i v es e q u e n c et oo c c a s i o n a l l yg e n e r a t ep o i n t s 5 n a n j i n gn o r m a lu n i v e r s i t y w i t hn o n n l o i l o t o n eo b j e c t i 、r ev a l u e s t h e r e f o r e ，i nt h i sp a p e r ，w ew i l lp u tf o r w a r dan o n n l o n o t o n el i n es e a r c hm e t h o da n ds h o wt h a tt h ea l g o r i t h mi sg l o b a l l y c o n v e r g e n t 2 2t h en o n m o n o t o n el i , n es e a r c ha l g o r i t h m t h r o u g h o u tt h i sp a p e r ，w e d e n o t et i l ec l a r k ed i r e c t i o n a ld e r i v a t i v ea n dt h ec l a r k e s u b d i f f e r e n t i a lo ffa tzb y ，。( z ，d ) a n do f ( z ) c o n s i d e rt h ep r o b l e m ( 2 1 1 ) l e tz tb eag i v e ni t e r a t e 、v ec o n s i d e rt h e f o l l o w i n gs u b p r o b l e mt oo b t a i na s e a r c hd i r e c t i o nd k ： ( s p ) 。m r i n 。垂七( d ) = 赶( ，( z k ) + z 2 d ) + ；6 扩口k d ， ( 22 1 ) w h e r ez k o i ( x ) i st h eg e n e r a l i z e dj a e o b i a no f ，a tz t ，b k r “。”i sag i v e n s y m m e t r i cm a t r i x ， p r o p o s i t i o n2 2 1 l e tf =hof ，w h e r e ：静- - + 秽i sal o c a l l y 徊s c h i t z i a n n c t i o n ，a n dh ：r “- - + 冗i sac o n t i n u o u s l yd i f f e r e n t i a b l ec o n v e z 如n c t i o n t h e nfi sal o c a l l yl i p s c h i t z i a n 九n c t i o na tza n do n eh a so f ( x ) = z 了v ( ，( 3 ) ) f z a ，( z ) ) d e f i n i t i o n2 2 。2 。嘲l e tf= 三咖s c h i t z i a na n c t i o n ，a n dh ：r ”_ f u n c t i o ni h0 ，w h e r e ，：冗”_ r ”如al o c a l l y 只i sac o n t i n u o u s l yd i f f e r e n t i a b l ec o n ? j e 2 z f 。( z ，d ) = ( 。，) 。( 。，矗) 。z m a a ，x ( ：) ( d ，z 丁v ( ，( z ) ) ) o ，v d r “ t h e n i sc a l l e dac r i t i c a lp o i n to | f = h o | i nt h ef o l l o w i n g ，w eg i v ead e s c r i p t i o no fo u rl i n es e a r c ha l g o r i t h m a l g o r i t h m2 2 3 s t e pj l e t 盯( 0 ，1 ) ，丁( 0 ，1 ) ，0 一a t l d t b 女d k d i v i d i n gb o t hs i d e sb yq ，p a s s i n gt ot h el i m i tz 。，w eo b t a i nt h a t ( h o ( d ) 2 d 吾b k d k 一；剐k t h u s ，( 2 3 5 ) i m p l i e s h ( f ( x k ) + 霹d ) ) h ( f ( x k ) ) 一：d 罩b k d 女， w h i c hc o n t r a d i c t sf 2 3 ，3 1 c h a p i c r2an o l l l u o l l o t o l l el i n es e a r c hm e t h o df o r ( p ) 9 l e m m a2 3 2 l e tf=h 0f ，w h e r ef ：r ”+ r “i sal o c a l l y 三i p s c h i t z i a n 知n c t i o n ，a n dh ：r ”_ 矗i sac o n t i n u o u s l yd i f f e r e n t i a b l ec o n v e x 丘n c t i o n a s s u m et h a ts o re v e r yk t h ed i r e c t i o nd kg e n e r a t e db yt h em o d e l a l g o r i t h ms a t i s 铽e s ( 2 ，3 i ) t h e n ，t h e1 0 l l o w m gs t a t e m e n t sa r ee q u i v a l e n t ： 8 ) d = 0 i st h eo n l yg l o b a l l yo p t i m a ls o l u t i o no f t h e p r o b l e mf 2 ，2 i ： ) d = 0 i sag l o b a l l yo p t i m a ls o l u t i o n0 t h ep r o b l e m 2 2 。1 ) ： ( c 1 t h e o p t i m u mo b j e c t i v ev a l u eo ft h ep r o b l e m1 227 i 1i sh ( f ( x k ： ( d ) 3 ：k i snc r i t i c a lp o i n t0 l f = h 0 f p r y 西( a ) = ( b ) 号( c ) 。t h e s ei m p l i c a t i o n sa r eo b v i o u s ( c ) 辛( d ) s i n c e t h eo p t i m u m o b j e c t i v ev a l u eo f t h ep r o b l e m ( 2 2 1 ) i sh ( ( x 女) ) w eh a v e ，f o ra n yd r “a n da n yp o s i t i v es c a l a ra 0 附( ) ( + a 刃d ) + 等矿鼠d o 茎 ( ，扛。) + a 霹d ) 一 ( ，( z 女) ) + 箕d 丁b d d i v i d i n gb o t hs i d e sb yaa n dl e ta 0 w ed e d u c et h ed e s i r e dc o n c l u s i o n 。( ，( z k ) ，z 看d ) = f 。( z t ，d ) = ( ho ，) 。( z k ，d ) 0 ( d ) j ( a ) s u p p o s et h a tp r o b l e m ( 2 ，2 1 ) h a san o n z e r oo p t i m a ls o l u t i o nd k t h e n ， h ( f ( x t ) + 刁以) + ；玩d h ( f ( x i ) ) ， i e h ( f ( x 女) + z d 女) 一h ( f ( x e ) ) l d 吾b k d k f r o mt h ep r o o fo fl e m m a3 1 ，w eh