（计算数学专业论文）some+nonmonotone+algorithms+for+lc1+and+nonsmooth+minmax+unconstrained+optimization.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 y - 64 2 4 0 4 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均己在论文中作了声明并表示 了谢意。 作者签名：壶量色蕉 日 期：翘。2 盐i 理 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索：有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名：叠施趁 日期： 盐口龟；z 【 a b s t r a c t 1 i nt h i sp a p e r ，w em a i n l yc o n s i d e rt h el c lu n c o n s t r a i n e d p r o g r a m m i n g 砌m i n 。他) ， w h e r e ，：r “_ r ，f l c l ，t h a tm e a n sv fi s al o c a l l yl i p s c h i t z i a nf u n c t i o n i nc h a p t e r2 w ep r e s e n tan o n m o n o t o n el i n es e a r c hm o d e la l g o r i t h mf o rt h eu n - c o n s t r a i n e dl c lo p t i m i z a t i o np r o b l e m s ，a n dp r o v et h a to u ra 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 a n di nc h a p t e r3 ，w ec o m b i n et h et r u s tr e g i o na l g o r i t h mg i v e nb ys u n w i t hn o n m o n o t o n et e c h n i q u ea n dp r e s e n tan 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 r t h ep r o b l e m sa n dg i v et h eg l o b a lc o n v e r g e n c eo ft h ea l g o r i t h m i nc h a p t e r4 ，w e g i v ean e w t r u s tr e g i o na l g o r i t h mw i t hr a d i u sb o u n d e db e l o wf o rl c 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 dp r o v et h a t i t i s g l o b a l l yc o n v e r g e n t i nc h a p t e r5 ，w ec o n s i d e r n o n s m o o t hd i s c r e t em i n i m a xp r o b l e m sm i nm a x f l ( x ) l i = 1 ，- 一，m ) ，w h e r ee a c h i sc o n v e x ，b u tn o tn e c e s s a r i l yd i f i e r e n t i a b l e t 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 f o rn o n s m o o t ho p t i m i z a t i o ng i v e nb yp a n gi se x t e n d e dt ot h i sc a s e a n dw ep r o v e t h a tt h ea 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 k e yw o r d s 1 i n es e a r c h ，t r u s tr e g i o n ，n o n m o n o t o n em e t h o d ，s t a t i o n a r yp o i n t ，u n c o n s t r a l n e do p t i m i z a t i o n 摘要 本文主要研究l e l 无约束最优化问题m i n f ( x ) ，其中，l c l ，即v ， 是局部l i p s c h i t z i a n 函数该问题在实际生活中有很强的应用背景，因此已 有很多文章已经对这类问题进行了探讨，其中s u n 等提出用二阶上d i n i 导数 代替二阶方向导数来求解子问题，分别给出了l c l 无约束最优化问题的一个 线性搜索算法和一个信赖域算法另外我们还研究了非光滑极小极大问题 本文主要分为以下四个部分： 第一部分介绍了本文的研究背景，以及文章所用的一些定义及符号。第 二部分主要研究了三e 1 无约束最优化问题，我们将非单调技术应用于线性搜 索算法，给出了l e l 无约束最优化问题的一个非单调线性搜索算法，并且证 明了该算法是整体收敛的在第三部分我们将非单调技术与信赖域算法相结 合，来求解三e 1 无约束最优化问题，给出了l e l 无约束最优化问题的一个非 单调信赖域算法，并且证明了该算法是整体收敛的在第四部分，对于l c l 无约束最优化问题，我们提出了一种半径有下界的信赖域算法，并且证明了该 算法具有整体收敛性最后，我们研究了非光滑极小极大问题，给出了一种非 单调线性搜索算法，并且证明了算法的收敛性 关键词：线性搜索，信赖域，非单调，稳定点，最优化问题 c h a p t e r1 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 t h el c 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 se x i s te x t e n s i v e l yi nv a r i o u so p t i m i z a t i o np r o b l e m s f o re x a m p l e ，t h ep r o b l e m sf r o mn o n l i n e a rc o m p l e m e n t a r i t y , v a r i a t i o n a li n e q u a l i t ya n dc 2n o n l i n e a rp r o g r a m m i n gc a nb ef o r m e da 8l c lo p t i m i z e - t i o np r o b l e m s i na d d i t i o n ，l c lo p t i m i z a t i o np r o b l e m sa l s oa r i s ef r o mt h ee x t e n d e d l i n e a r q u a d r a t i cp r o g r a m m i n gp r o b l e m s ，n o n l i n e a rm i n i m a xp r o b l e m s ，s t o c h a s t i co p - t i m i z a t i o np r o b l e m sa n ds o m es e m i - i n f i n i t ep r o g r a m s ， i nt h i sc l a s so fp r o b l e m s ，t h eo b j e c t i v ef u n c t i o ni sl c lf u n c t i o n ，b u tn o tac 。f u n c t i o n ，i e ，i ti sc o n t i n u o u s l yd i f f e r e n t i a b l ea n d i t sd e r i v a t i v ei so n l yl o c a l l yl i p s c h i t z i a n b u tn o tn e c e s s a r yf - d i f f e r e n t i a b l e t h e l i p s c h i t zc o n d i t i o np l a y sa v i t a lr o l ei nd e v e l o p i n gg e n e r a l i z e dn e w t o nm e t h o d sf o rs o l v i n gn o n s m o o t he q u a t i o n t h er e s e a r c ho ft h el i p s c h i t zc o n d i t i o ns t i m u - l a r e su st oc o n s i d e rl c lo p t i m i z a t i o np r o b l e m s i n 1 】 s u np r e s e n t e dt w os u p e r l i n - e a r l yc o n v e r g e n tm e t h o d sf o rl c lo p t i m i z a t i o np r o b l e m s t h e yc o n s i d e ru s i n gt h e s e c o n do r d e rd i n iu p p e rd i r e c t i o n a ld e r i v a t i v ea n dt h et r u s tr e g i o nt e c h n i q u et od e a l w i t hl c lo p t i m i z a t i o np r o b l e m s o nt h eo t h e rh a n d ，al a r g ep o r t i o no fo p t i m i z a t i o nm e t h o d s r e q u i r em o n o t o n i c i t y o ft h e o b j e c t i v ev a l u e t og u a r a n t e et h e k g l o b a lc o n v e r g e n c e r e c e n tr e s e a r c hi n d i c a t e s 5 n a n j i n gn o r m a lu n i v e r s i t y 6 t h a tt h em o n o t o n el i n es e a r c ht e c h n i q u em a yh a v es o l n ed r a w b a c k si np a r t i c u l a r e n f o r c i n gm o n o t o n i c i t ym a yc o n s i d e r a b l ys l o wd o w n t h er a t eo fc o n v e r g e n c ew h e nt h e i t e r a t i o ni st r a p p e dn e a ran a r r o wc 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 s o rz i g z a g g i n g t h e r e f o r e ，i tm i g h tb ea d v a n t a g e o u st oa l l o wt h ei t e r a t i v es e q u e n c et o o c c a s i o n a l l yg e n e r a t ep o i n t sw i t hn o n m o n o t o n eo b j e c t i v ev a l u e s s e v e r a ln u m e r i c a l t e s t ss h o wt h a tt h 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 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 na n dc o n s t r a i n e do p t i m i z a t i o ni se f f i c i e n ta n dc o m p e t i t i v e s e e 3 】【4 1 1 5 t 6 1 a t t h es a j n et i m e ，t 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 fl 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 i nt h e s ep a p e r s ，t h e yp r o p o s e dag r e a tn u m b e ro fa l g o r i t h m s f o rm i n i m i z i n gl o c a l l yl i p s c h i z i a nf u n c t i o n s ，f o re x a m p l e ， 7 1 i s ，阢 1 0 i nt h i sp a p e r ，w eg i v et w on o n m o n o t o n ea l g o r i t h m sa n dan e wt r u s tr e g i o nm e t h o d f o rt h el c lu n c o n s t r a i n e dp r o b l e m s w ea l s oc o n s i d e ru s i n gt h es e c o n do r d e rd i n i u p p e rd i r e c t i o n a ld e r i v a t i v e t or e p l a c et h es e c o n do r d e rd i r e c t i o n a ld e r i v a t i v e i n c h a p t e r2 ，w ep r e s e n tan 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 ，a n de s t a b l i s ht h eg l o b a l c o n v e r g e n c e ，i e ，u n d e rs o m ec o n d i t i o nw eh a v et h a te 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 ef 。k ) g e n e r a t e df r o mt h em o d e la l g o r i t h mi sas t a t i o n a r yp o i n to ft h e p r o b l e m i nc h a p t e r3 ，w ec o m b i n et h et r u s tr e g i o na l g o r i t h mg i v e nb ys u nw i t h n o n m o n o t o n et e c h n i q u ea n dp r e s e n tan 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 mb a s e d o ns o m ea s s u m p t i o n sw ec o n c l u d et h es e q u e n c e 。k ) g e n e r a t e db yt h ea 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 i nc h a p t e r4 ，w eg i v ean e wt r u s tr e g i o na l g o r i t h mw i t hr a d i u s b o u n d e db e l o wf o rt h ep r o b l e ma n dp r o v et h a tt h et r u s tr e g i o na 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 m i n i m i z a t i o no fac o m p o s i t ef u n c t i o n ( ，( z ) ) w a sc o n s i d e r e db yf l e t c h e r 【1 1 ，p a n g e t cm s a m p a i o ，y u a na n ds u n 1 2 1 ，s u na n dy u a n 【1 3 ，y u a n 1 0 】，q i e t c 7 a n dan o n m o n o t o n e l i n es e a r c ht e c h n i q u eh a sb e e np r o p o s e di ng r i p p o ，l a m - p a r i e l l o ，a n dl u c i d i 【2 i nc h a p t e r5 ，w ec o n s i d e rt h ed i s c r e t em i n i m a xp r o b l e m m i n m a x i ( x ) l i = 1 ，一t m ) ，w h i c hi s a ni m p o r t a n ts p e c i a lc a s eo ft h ec o m p o s i t e c o n v e xm i n i m i z a t i o n ，w h e r ee a c h i sc o n v e x ，b u tn o tn e c e s s a r i l yd i f f e r e n t i a b l e w e c o m b i n el i n es e a r c h m e t h o dw i t hn o n m o n o t o n e t e c h n i q u e a n dp r e s e n tan o n m o n o t o n e l i n es e a r c ha l g o r i t h m w es h o wt h a tt h ea 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 c h a p t e r1 i n t r o d u c t i o n7 1 2p r e l i m i n a r i e s w ef i r s tg i v es o m ed e f i n i t i o n st h a tw i l lb eu s e df o rt h er e m a i n d e ro ft h ep a p e ri n t h i sp a p e r ，w ec o n s i d e rt h el c lu n c o n s t r a i n e dp r o g r a m m i n g ： 砌m i n ，m ) ，l c l ( 1 2 - 1 ) i n 1 w eh a v et h ef o l l o w i n gd e f i n i t i o n s ： 1 t h eg e n e r a l i z e dd e r e c t i o n a ld e r i v a t i v eo f ，a tzi nd i r e c t i o nd ： ，。( 雹d ) ：胁s u p 型兰粤型( 1 删 一t i o 2 t h es e c o n do r d e rd i n iu p p e rd i r e c t i o n a ld e r i v a t i v eo ft h ef u n c t i o nfa tx k r “ i n t h ed i r e c t i o nd 册： 为( d ) ：l i m s u p 盟堕坐车堂 ( 123 ) f r o m 届( d ) p o s s e s s e s t h ef o l l o w i n gb a s i cp r o p e r t i e s ： ( 1 ) ， 尼( ；a d ) = a 2 艺( z t ；d ) ， ( 1 2 4 ) a n d 尼( ；d 。+ d 2 ) 2 【艺( z k ；d 1 ) + 艿( d 2 ) 】 ( 1 25 ) ( 2 ) ，：( z k ；d ) i su p p e r s e m i c o n t i n u o u sw i t hr e s p e c tt o ( x k ；d ) ，i e ，i fz ； z ka n d 也一d ，t h e n l i m8 u p 艿( z ；d 。) 厶( z 女；d ) ( 1 2 6 ) m f o rt h es a k eo fc o n v e n i e n c e ，w ea l s og i v et h ef o l l o w i n gd e f i n i t i o n sa n dl e m m a s d e f i n i t i o n1 2 1 af u n c t i o nv ，：舻_ 彤i ss a i dt ob es e m i - s m o o t ha tz 矿 飞ii sl o c a l l yl i p s c h i t z i a na tza n dt h el i m i t 一l i d m l 。 y ) ，y a 2 ，( z + a ) e x i s t s f o ra n y d r “ n a n j i n gn o r m a lu n i v e r s i t y 8 d e f i n i t i o n1 2 2 a 血n c t i o nv f ：r ”_ 册i ss a i dt ob ew e a ks e m i s m o o t ha t z 寸v f i sl o c a l l yl i p s c h i t z i a na t a n dt h el i m i t l i m s u p v h ) ，v 泸，( z4 - a ) d m o e x i s t s f o ra n yd r “ f r o mt h ed e f t n i t i o n sa b o v e ，t h e r ei sa no b v i o u sr e s u l ta sf o l l o w s p r o p o s i t i o n1 2 3 a 血n c g o nfz s w e a ks e m i - s m o o t h 矿fi ss e m i s m o o t h b u t ， i ng e n e r a lt h eo p p o s i t ei sn o tt r u e l e m m a1 2 4 1 | 飞ltr 。_ r 、i ss e m i s m o o t ha t 。t h e n 飞si sd i r e c t i o n a l l y d i f f e r e n t i a b l ea tz ，a n df o ra n yv 0 z f ( 2 + ) ，h 叫0 ，w eh a v e v h 一( v f ) 7 ( z ；h ) = o ( j ih 协 s i m i l a r l y , w eh a v et h a t h t v h 一( v f ) ”( 。；h ) = o ( i h 1 2 ) f u r t h e r m o r e ，f ，v f ：r “_ r “i sw e a ks e m i s m o o t ha tz ，w eh a v e v h 一( v ，) 名( 。；h ) = o ( i ih n l e m m a1 2 5 盯v f ：j r “_ r “i sal c lf u n c t i o n ，t h e nt h e r ee x i s ta 【0 ，1 】 a n d v a 2 ( x + a ( 一z ) ) s u c ht h a t ，( ) 一，( z ) 一v f ( z ) 7 ( y - - 2 ) = ；( y - - 2 ) 7 v ( y - - x ) p r o p o s i t i o n1 2 6 l e t f ：dc r 4 _ 只b eal c lf u n c t i o no nd ，w h e r edcr “ i sa no p e ns u b s e t 1 f 2i sas o l u t i o no f l c lo p t i m i z a t i o np r o b l e mf i21 ) ，t h e n ，7 ( z ；d ) = 0 ， a n d 艿( z ；d ) o ，v d r 8 ， c h a p t e r1 i n t r o d u c t i o n9 p r o p o s i t i o n1 2 7 l e t ，：dc | r “_ r b eal c lf u n c t i o no n d ，w h e r edcr 4 i sa no p e ns u b s e t i fzs a t i s f i e s ，7 ( z ：d ) = 0 尼( z ；d ) o ，v d 0 ，d r “ t h e nzi s 口s t r i c tl o c a lm i n i m i z e ro ff l2 i ) c h a p t e r 2 an o n m o n o t o n el i n es e a r c h a l g o r i t h m f o rl c lu n c o n s t r a i n e d o p 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 el c lu n c o n s t r a i n e dp r o g r a m m i n g ： ( p 1 。r a 口i n 他) ( 2 1 1 ) w h e r e ，：r “_ r ，l c l ，t h a tm e f l $ 1 sv ，i s al o c a l l yl i p s c h i t z i a nf u n c t i o n w e n y us u ne t4 1 1 】e x t e n d e dt h ec l a s s i c a ll i n es e a r c ha l g o r i t h mt ot h el c l c a s e w h e r et h eg r a d i e n t 飞lo fo b j e c t i v ef u n c t i o n ! i sl 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 t t h e i 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 i nt h i ss e c t i o n ，c o m b i n i n gt h el i n es e e x c hm g o r i t h mg i v e nb yw e n y u s u ne ta i i ! w i t hn o n m o n o t o n et e c h n i q u e ，w ep r e s e n tan o n m o n o t o n e l i n es e a r c ha l g o r i t h mf o rt h e u n c o n s t r a i n e dl c lo p t i m i z a t i o np r o b l e m s ，a n dp r o v et h a to l i ra 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 c h a p t e r2 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 rl c lp r o b l e m l l 2 2 a l g o r i t h m a n db a s i ca s s u m p t i o n s i nt h ef o l l o w i n g ，w ef i r s tg i v et 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 mf o rt h eu n c o n s t r a i n e dl c lp r o b l e m l e tf ：r “一r ，l c l ，v fi 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 ，为( z ；d ) i st h e s e c o n do r d e rd i n iu p p e rd i r e c t i o n a ld e r i v a t i v eo ft h ef u n c t i o nf i nt h ef o l l o w i n g ，w eg i v ea d e s c r i p t i o no fo u rl i n es e a r c ha tt h ek t hi t e r a t i o n 、g i v e n ；t ka n d k ，w en e e dt os o l v et h es u b p r o b l e m ： ( s 尸) m i n 。西k ( d ) ：= ，( z ) + v ，( z k ) r d + i 厶( z ；d ) ， ( 2 2 - 1 ) t h em o d e la l g o r i t h m s t e p1 l e t 盯( 0 ，1 ) ，7 - ( 0 1 ) ，0 a l a 2 ，a n dl e tm b ea p o s i t i v ei n t e g e ra n d x 0 口l e tk = 0 s t e p2 g i v e n2 ：k c a l c u l a t e 以a sag l o b a l b ro p t i m a ls o l u t i o no ff 221 ) i i f lv f ( x k ) l o ，t h e ns t o p s t e p3 a s s u m et h a t ，a tt h ek t hi t e r a t i o n ，ap r i o rt r i a ls t e p l e n g t hf k ( a l ，a 2 ) i sg i v e n t h en o n m o n o t o n el i n es e a r c hi st oc h o o s et h ef i r s tn o n n e g a t i v ei n t e g e rh k s u c ht h a tt h es t e p l e n g t h p k = 风r ( 2 2 ，2 ) s a t i s f i e s m + m d k ) _ 0a n dv d r “， ，( z ) s 西k ( d ) = ，( z k ) + v 厂( 。 ) 丁d + ；，二( z k ：a d ) ie ， o a v f ( 蹦7 d 十；坛( 弼搁 d i v i d i n gb o t hs i d e so ft h ea b o v ei n e q u a l i t yb ya ，u s i n g 尼( z ；a d ) = a 2 为( z k ；d ) a n d l e tai0 w eh a v e 0 v f ( x ) 7 d ，v d r ， w h i c hm e a n s 。ki sas t a t i o n a r yp o i n to ff ( 3 ) j ( 1 ) ：l e tz b e as t a t i o n a r yp o i n to ff ，i e ， v f ( x 女) 7 d o