（计算数学专业论文）滤子方法求解非线性优化问题.pdf

中文摘要 摘要 非线性( 无) 约束的最优化理论与方法的研究，由整体收敛性和局部收敛速率两部分构 成，其中线搜索技术与信赖域策略是保证算法的整体收敛性的两个重要手段。同时，伴 随着计算机的发展和软件的完善，最优化问题的数值求解正变得越来越实际可行。 本文丰要针对非线性等式约束、非负约束、一般约束优化问题与非线性等式和不等 式系统，借助f l e t c h e r 和l e y f f e r 提出的滤子思想，将约束优化问题和非线性系统转化为 多目标优化问题，提出了各类有效的线搜索滤子方法，求解非线性约束优化问题以及非 线性等式和不等式系统。 f l e t c h e r 和l e y f f e r 针对非线性优化问题提出了滤子方法，从而代替传统的罚函数方法 来保证优化算法的整体收敛性。其主要的思想是，当目标函数或约束违反度被改进时， 就接受试探点。但是，先前的工作只考虑滤子信赖域方法和算法的整体收敛性。因此， 本文将滤子线搜索方法结合两类正割算法求解非线性等式约束优化问题。与一般的滤子 方法不同的是，本文用拉格朗日函数代替目标函数作为滤子的组成部分。在保持整体收 敛性的情况下，算法具有局部二步q 超线性收敛速率，而且不需要引入二阶校正步。 近期的研究表明，单调的线搜索方法存在些缺点。尤其是当迭代点到达函数的狭 窄谷底时，单调下降的要求可能导致降低收敛速率。g r i p p o 等人推广了a r m i j o 条件，提 出了非单调线搜索方法。该方法允许函数值上升，同时保证算法的整体收敛性。数值实 验结果证明非单调线搜索方法是有效的、可靠的。本文将滤子正割方法与非单调技术结 合求解非线性等式约束优化问题。主要贡献在于将非单调技术应用于滤子和下降条件， 使得新方法相对于单调方法更容易接受试探步长，减少了计算量。 既约h e s s i a n 次规划算法被证实是求解大规模优化问题的有效方法，尤其是对自由 度相对不人的问题。通过空间分解技术，在相对较小的空间里面求解q p 子问题，可以大 大降低存贮空间和计算量。考虑既约h e s s i a n 二次规划算法和由y u 等人提出的非单调技 术，本文构造了非单调滤子既约h e s s i a n 算法求解非线性等式约束优化问题。在合理假设 下，证明了算法具有整体收敛性和二步q 超线性收敛速率。数值结果表明非单调方法比 单调的情形更有效，同时不会受到m a r a t o s 效应的影响，即最后几次迭代的步长都是1 。 内点障碍方法在大规模优化计算当中得到日益重视。与积极集策略不同，这些方法 提供了解决不等式约束优化问题的另一种有效手段。本文提出了滤子内点方法求解非线 性等式和非负约束优化问题。数值结果表明该算法是可行的。 国际上很多学者提出了多维滤子的定义，g o u l d ，l e y f f e r 和t o i n t 用多维滤子的思想 求解非线性方程组和非线性最d - - 乘问题。g o u l d s a i n v i t u 和t o i n t 则解决了无约束优化 问题的求解。w i c h t e r 和b i e g l e r 提出了滤子线搜索方法求解等式约束优化问题。由于很 第1 页 上海师范大学博士学位论文 多问题同时含有等式和不等式约束，本文基于多维滤子和非单调技术将w a c h t e r b i e g l e r 的方法推广到求解一般约束优化问题。当优化问题只有等式约束和m = 1 时。该方法就 是w i i c h t e r - b i e g l e r 的方法。数值结果与s n o p t 比较，表明新方法是有效的。 非线性等式和不等式系统在应用数学领域有大量的应用，在数学建模、优化、互补 问题以及变分不等式的数值算法中起着核心地位。作为滤子方法的应用，本文提出了非 单调滤子方法求解非线性等式和不等式系统。在合理假设下，该方法具有整体收敛性和 局部q 超线性收敛速率。数值结果与两类信赖域方法比较，表明新方法是有效的，同 时，完全步z 知+ 1 = z 知+ d k 或z 七+ 1 = z 七十d 七+ d 妒在最后几次迭代中被接受，使得序列 f z q 超线性收敛于z 。 最后本文对所做的研究工作进行总结，特别是创新点小结，并提出了进一步的研究 方向。 关键词：优化问题：滤子；线搜索方法；非单调技术：内点法：整体收敛性：局部收敛 速率；m a r a t o s 效应。 第1 i 页 a b s t r a c t t h es t u d yo ft h e o r ya n dm e t h o d so fn o n l i n e a r ( u n ) c o n s t r a i n e do p t i m i z a t i o ni sc o m p o s e do f t w op a r t s ，i e ，g l o b a lc o n v e r g e n c ea n dl o c a lc o n v e r g e n tr a t e b o t hl i n es e a r c ht e c h n i q u ea n d t r u s tr e g i o ns t r a t e g ya r ew e l l a c c e p t e dm e t h o d si nt h eo p t i m i z a t i o ni no r d e rt oa s s u r eg l o b a lc o n v e r g e n c e a tt h es a m et i m e ，a c c o m p a n yw i t ht h ed e v e l o p m e n to fc o m p u t e ra n dt h ep e r f e c to f s o f t w a r e ，n u m e r i c a le x p e r i m e n t so fo p t i m i z a t i o np r o b l e m sa r eb e c o m i n gm o r ea n dm o r ef e a s i b l e a n de f f e c t i v e t h i st h e s i si sd e v o t e dt os t u d y i n gs y s t e m a t i c a l l yt h ea l g o r i t h m so fn o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o n ，i n c l u d i n gw i t he q u a l i t yc o n s t r m n t s ，n o n n e g a t i v ec o n s t r a i n t s ，g e n e r a lc o n s t r a i n t s t h ea l g o r i t h mo fn o n l i n e a rs y s t e m so fe q u a l i t i e sa n di n e q u a l i t i e si sa l s oc o n s i d e r e d b ye m p l o y i n g t h ef i l t e ri d e ai n t r o d u c e db yf l e t c h e ra n d l e y f f e r , w ep r o p o s es e v e r a le f f i c i e n tl i n es e a r c hf i l t e r m e t h o df o rs o l v i n gn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o na n dn o n l i n e a rs y s t e m so fe q u a l i t i e sa n d i n e q u a l i t i e s f l e t c h e ra n dl e y f f e rp r e s e n t e df i l t e rm e t h o d sf o rn o n l i n e a rp r o g r a m m i n g ( n l p ) ，o f f e r i n g 柚 a l t e r n a t i v et om e r i tf u n c t i o n s ，a sat o o lt og u a r a n t e eg l o b a lc o n v e r g e n c eo fa l g o r i t h m sf o rn o n l i n e a r p r o g r a m m i n g t h eu n d e r l y i n gc o n c e p t i st h a tt r i a lp o i n t sa r ea c c e p t e di ft h e yi m p r o v et h eo b j e c t i v e f u n c t i o no ri m p r o v et h ec o n s t r a i n tv i o l a t i o n p r e v i o u st h e o r e t i c a lw o r ko nf i l t e rm e t h o d sh a s c o n s i d e r e dt r u s tr e g i o na l g o r i t h m sa n do n l yt h eq u e s t i o no fg l o b a lc o n v e r g e n c e s ow ee x t e n dt h e l i n es e a r c hf i l t e rm e t h o dt ot w os e c a n ta l g o r i t h m sf o rn o n l i n e a re q u a l i t yc o n s t r a i n e do p t i m i z a t i o n b ye m p l o y i n gt h el a g r a n g i a nf u n c t i o nc ( z ，a ) ( i n s t e a do f t h eo b j e c t i v ef u n c t i o n ，( z ) ) i nt h ef i l t e r b e s i d e sg l o b a lc o n v e r g e n c e ，w ep r o v e0 1 1 1 a p p r o a c hc o n v e r g e sl o c a l l yt w o - s t e pq s u p e r l i n e a r , e v e nw i t h o u ta na d d i t i o n a ls e c o n do r d e rc o r r e c t i o nt h a ti sn e e d e db ym a n ya l g o r i t h m st oa v o i dt h e m a r a t o se f f e c t r e c e n tr e s e a r c hi n d i c a t e st 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 m ed r a w b a c k s i 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 yr e d u c et 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 g r i p p oe ta 1 g e n e r a l i z e dt h ea r m i j or u l ea n d p r o p o s e dan 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 rn e w t o n sm e t h o dw h i c hp e r m i t si n c r e a s ei n f u n c t i o nv a l u e ，w h i l er e t a i n i n gg l o b a lc o n v e r g e n c eo ft h em i n i m i z a t i o na l g o r i t h m s e v e r a ln u m e r i c a lt 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 ei se f f i c i e n ta n dc o m p e t i t i v e w e p r o p o s ea f i l t e rs e c a n tm e t h o dw i t hn o n m o n o t o n el i n es e a r c hf o rn o n l i n e a re q u a l i t yc o n s t r a i n e d o p t i m i z a t i o n t h em a i nc o n t r i b u t i o no fo u rp a p e ri st oe m p l o yt h en o n m o n o t o n e i d e at ot h es u f - f i c i e n tr e d u c t i o nc o n d i t i o n sa n df i l t e r t h i sn e wm e t h o dh a sm o r ef l e x i b i l i t yf o rt h ea c c e p t a n c eo f 第1 i i 页 上海师范大学博士学位论文 t h et r i a ls t e pa n d 嘲u i r e sl e s sc o m p u t a t i o n a lc o s t sc o m p a r e dw i t ht h em o n o t o n eo n e ar e d u c e dh e s s i a ns u c c e s s i v eq u a d r a t i cp r o g r a m m i n g a l g o r i t h mh a sb e e ns h o w nt ob es u c - c e s s f u li ns o l v i n gl a r g e - s c a l en o n l i n e a r o p t i m i z a t i o n ，e s p e c i a l l yf o rp r o b l e m sw i t hf e wd e g r e e so f f r e e d o m b a s e do nr e d u c e dh e s s i a na l g o r i t h ma n dn o n m o n o t o n et e c h n i q u e p r e s e n t e db yy ua n d p u ，w ep r o p o s ean o n m o n o t o n ef i l t e rr e d u c e dh e s s i a nm e t h o df o rn o n l i n e a re q u a l i t yc o n s t r a i n e d o p t i m i z a t i o n s i m i l a rt oc h a p t e r2 ，t h el a g r a n g i a nf u n c t i o nc ( z ，入) i se m p l o y e di nt h ef i l t e r t h e g l o b a la n dl o c a lc o n v e r g e n c ei sg i v e nu n d e rr e a s o n a b l ea s s u m p t i o n t h en u m e r i c a lr e s u l t ss h o w t h a tt h en o n m o n o t o n e a l g o r i t h mi sm o r ee f f e c t i v et h a nm o n o t o n eo n ea n dd o e sn o ts u f f e rf r o mt h e m a r a t o se f f e c tf o ra l lp r o b l e m st e s t e dh e r e ，i e ，u n i ts t e p sa r ea c c e p t e di nl a s ts e v e r a li t e r a t i o n s g r o w i n gi n t e r e s t i ne f f i c i e n to p t i m i z a t i o nm e t h o d sh a sl e dt ot h ed e v e l o p m e n to fi n t e r i o r - p o i n to rb a r r i e rm e t h o d sf o rl a r g e s c a l en o n l i n e a rp r o g r a m m i n g i np a r t i c u l a r , t h e s em e t h o d s p r o v i d ea na t t r a c t i v ea l t e r n a t i v et oa c t i v es e ts t r a t e g i e si nh a n d l i n gp r o b l e m sw i t hl a r g en u m b e r s o fi n e q u a l i t yc o n s t r a i n t s w ep r o p o s eaf i l t e r i n t e r i o r - p o i n tm e t h o df o rn o n l i n e a re q u a l i t ya n d n o n n e g a t i v ec o n s t r a i n e do p t i m i z a t i o n s o m en u m e r i c a le x p e r i m e n t st os h o wt h ee f f e c t i v e n e s so f t h ep r o p o s e da l g o r i t h m f i l t e rm e t h o d sh a v eb e e ne x t e n d e db yg o u l d ，l e y f f e ra n dt o i n tt ot h en o n l i e a re q u a t i o n s a n dn o n l i n e a rl e a s ts q u a r e sa n db yg o u l d ，s a i n v i t ua n dt o i n tt ot h eu n c o n s t r a i n e do p t i m i z a t i o n p r o b l e mw i t hm u l t i d i m e n s i o n a lf i l t e rt e c h n i q u e w h c h t e ra n db i e g l e rp r e s e n t e dl i n es e a r c hf i l t e r m e t h o d sf o rn o n l i n e a re q u a l i t yc o n s t r a i n e dp r o g r a m m i n g s i n c em a n yp r o b l e m sc o n t a i nb o t h e q u a l i t ya n di n e q u a l i t yc o n s t r a i n t s ，w eg e n e r a l i z ew i c h t e r - b i e g l e rm e t h o d sf o rs o l v i n gg e n e r a l n o n l i n e a rp r o g r a m m i n gb a s e do nt h em u l t i d i m e n s i o n a lf i l t e rt e c h n i q u e u n d e rm i l dc o n d i t i o n s ， t h eg l o b a lc o n v e r g e n c ea n dl o c a ls u p e r l i n e a rc o n v e r g e n c eo ft h em e t h o da r eo b t a i n e d i fn o n l i n e a r p r o g r a m m i n go n l yh a se q u a l i t yc o n s t r a i n t sa n dm = 1 ，t h em e t h o da c t u a li st h ew i c h t e r - b i e g l e r l i n es e a r c hf i l t e rm e t h o d s t h en u m e r i c a lr e s u l t ss h o wt h a tt h en e wm e t h o di se f f e c t i v ec o m p a r e d w i t l ls n o p l s y s t e m s o fn o n l i n e a re q u a l i t i e sa n di n e q u a l i t i e sa p p e a ri naw i d ev a r i e t yo fp r o b l e m si na p p l i e dm a t h e m a t i c s t h e s es y s t e m sp l a yac e n t r a lr o l ei nt h em o d e lf o r m u l a t i o nd e s i g na n da n a l y s i s o fn u m e r i c a lt e c h n i q u e se m p l o y e di ns o l v i n gp r o b l e m sa r i s i n gi no p t i m i z a t i o n ，c o m p l e m e n t a r i t y , a n dv a r i a t i o n a li n e q u a l i t i e s a sa p p l i c a t i o n ，w ep r o p o s ean o n m o n o t o n ef i l t e rm e t h o df o rn o n l i n e a rs y s t e m so fe q u a l i t i e sa n di n e q u a l i t i e sw h i c hg u a r a n t e eg l o b a lc o n v e r g e n c ea n dp o s s e s sl o c a l s u p e r l i n e a rc o n v e r g e n tr a t eu n d e rs u i t a b l ec o n d i t i o n s f r o mt h en u m e r i c a lr e s u l t s ，w ec a ns e et h a t o u r a l g o r i t h mp e l l f o 册sw e l lc o m p a r e dw i t ht w ot r u s t - r e g i o nm e t h o d sa n df u l ls t e pz 膏+ 1 = z 七+ d 七 o rx k + l2x k + d k + d 扩i s a c c e p t e di nl a s ts e v e r a li t e r a t i o n ss ot h es e q u e n c e z 七) c o n v e r g e st o z 。q s u p e r l i n e a r l y 第页 f i n a l l y ，w ec o n c l u d et h em a i nn e wr e s e a r c hr e s u l t so ft h i st h e s i sa n dp r o p o s es o m ef u r t h e r r e s e a r c hd i r e c t i o na b o u to u rw o r k k e y w o r d s ： o p t i m i z a t i o n ；f i l t e r ；l i n es e a r c hm e t h o d ；n o n m o n o t o n et e c h n i q u e ；i n t e r i o rp o i n t m e t h o d ；g l o b a lc o n v e r g e n c e ；l _ x ) c a lc o n v e r g e n tr a t e ；m a r a t o se f f e c t 上海师范大学博士学位论文 主要符号对照表 n 维实向量空间 nxm 维实矩阵 1 1 2e u c l i d 范数 n 维决策变量 向量z 的第j 个分景 优化问题或非线性系统的解 函数，的梯度向量 映射f 的雅可比矩阵 函数厂的h e s s i a n 矩阵 等式约束集 不等式约束集 可行集 表示取下确界 表示属于 表示任意 矩阵g 的逆运算 矩阵a 的伪逆 矩阵a 的值域 矩阵a 的零空间 滤子 滤子增广的迭代指标集 第v i i i 页 舭秽z巧以w w啊z s肼v伊刚小厂z 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或机构已经发 表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中做了明确的声明并表示了谢意。 作者签名：矽l - 蟹i t 期：作者签名： 迕 期： 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵守此规定) 作者签名：盈垒整 导师签名： 日期：珥竺：? 第一章最优化理论与方法的基础 第一章最优化理论与方法的基础 1 1 最优化问题简介 最优化问题的一般形式数学模型为 m i n ，( z ) ， s t q ( z ) = 0 ，i = 1 ，2 ，m ，( 1 1 1 ) q ( z ) s0 ，i = 仇+ 1 ，p ， 其中z r n 为决策变量，( z ) ：r n _ r 1 为目标函数，q ( z ) ：r n _ r 1i = 1 ，p 为 约束函数。称集合 s = 【z r niq ( z ) = 0 ，i = 1 ，2 ，m ；龟( z ) 0 ，i = m + 1 ，p ) ( 1 1 2 ) 为问题( 1 1 1 ) 的可行集。如果s = r n ，则称问题( 1 1 1 ) 为无约束优化问题。对于最优化问 题，主要任务就是求最优解或者稳定点。 下面引入最优化理论与方法的基本概念。 定义1 1 1 设z 。s ，若对vz 5 有 f ( x 。) ，( z ) ，( 1 1 3 j 则称z + 是问题( 1 1 1 ) 的整体极小值点。进一步，若对vz 5 且z z 。，有 f ( x 。) o ) ，对vz sn m ( z 。) ，有 f ( x 。) ，( z ) ， ( 1 1 5 ) 则称z + 是问题( 1 1 1 ) 的局部极小值