（应用数学专业论文）新锥模型信赖域算法研究(1).pdf

中文摘要 用二次模型逼近原优化问题的信赖域算法因其较强的适应性和收敛性成为优 化算法中一类重要的数值计算方法。然而，对于非二次形态强、曲率变化比较剧烈 的函数，二次模型信赖域算法显得力不从心。近年来，锥模型信赖域算法的研究引 起了普遍关注，尤其是2 0 0 5 年新锥模型信赖域算法的提出，不仅弥补了二次模型 信赖域算法的缺陷，而且突破了传统锥模型信赖域算法只在平面一侧求解函数最优 值的局限。因此本文主要研究新锥模型信赖域算法的子问题求解和算法框架本身的 构造与改进，利用锥函数的参数特性，结合非单调策略，提出新的自适应调节信赖 域半径，给出了可以求解大规模问题的新算法，而且每一种新算法的提出，都是对 前一种算法的改进与完善。最后，给出一种的新水平向量，数值试验验证了该水平 向量的有效性。 本文共分六章，第一章主要介绍了信赖域算法的基本思想，二次模型和锥模型 的研究现状。第二章介绍了锥模型信赖域算法的理论基础，及新锥模型信赖域算法 的子问题求解，并给出了部分锥函数性质定理的有关证明和几种经典的优化测试问 题。第三章结合新锥模型子问题的折线法求解算法，提出了一种非单调的新锥模型 信赖域算法，该算法是二次模型信赖域算法和传统锥模型信赖域算法的推广。将新 算法与二次模型信赖域算法、传统锥模型信赖域算法比较得到了较好的数值结果， 并证明了新算法的全局收敛性和超线性收敛性。第四章给出了一种新的调节信赖域 半径方法，提出了自适应的新锥模型信赖域算法，该算法弥补了非单调锥模型信赖 域算法中的不足。证明了算法的全局收敛性。第五章提出了一种新锥模型信赖域算 法的混合算法，用新算法对大规模的测试函数进行检验，得到了理想的数值结果， 从而有望解决大规模优化问题，并证明了新算法的全局收敛性，最后，给出了数值 实验的结果分析。由于锥模型逼近也是算法改进的一个方向，考虑到水平向量参数 选择的重要性，本文在第六章利用二次模型与锥模型拟牛顿条件的近似等价性，提 出了一种新的水平向量，将该水平向量应用于新锥模型信赖域算法得到了较好的数 值实验结果。 关键词：新锥模型；信赖域算法；非单调技术；自适应技术；水平向量 a b s t r a c t t r u s tr e g i o na l g o r i t h mb a s e do nq u a d r a t i cm o d e lh a sb e c o m ea n i m p o r t a n tc l a s s o fn u m e r i c a lc a l c u l a t i o nm e t h o d sb e c a u s eo fi t s s t r o n g a d a p t a b i l i t ya n dc o n v e r g e n c eo fo p t i m i z a t i o na l g o r i t h m s b u tf o rs t r o n g n o n - q u a d r a t i cf o r ma n dt h es h a r pc h a n g ei nc u r v a t u r ef u n c t i o n ，t h eq u a d r a t i c m o d e ls e e m st ou n a b l et os o l v ei t i nr e c e n ty e a r s ，t h ec o n i cm o d e lf o rt h e s t u d yo ft r u s tr e g i o na l g o r i t h mh a sa r o u s e dw i d e s p r e a dc o n c e r n e s p e c i a l l y , t h et r u s tr e g i o na l g o r i t h mb a s e do nn e wc o n i cm o d e lw a sp r o p o s e di n 2 0 0 5 ，i ti sn o to n l ym a d eu pf o rt h ed e f e c t so ft h eq u a d r a t i cm o d e lt u r s t r e g i o na l g o r i t h m ，b u ta l s ob r o k e nt h r o u g ht h el i m i t a t i o n so ft r a d i t i o n a lc o n i c m o d e lt r u s tr e g i o na l g o r i t h mo ns o l v i n go p t i m a lv a l u ei no n es i d eo ft h e p l a n e t h e r e f o r e ，t h i sa r t i c l em a i n l ys t u d i e si ns o l v i n gs u b p r o b l e m ，t h e s t r u c t u r eo ft h ea l g o r i t h mf r a m ea n dt h ei m p r o v e m e n t m a d eu s eo ft h e p a r a m e t e r s c h a r a c t e r i s t i c sa n dc o m b i n i n gw i t hn o n - m o n o t o n es t r a t e g y , w e p u tf o r w a r dan e wp r o b l e mt os o l v el a r g e s c a l ea l g o r i t h m a n de a c hn e w m e t h o di st h ed e v e l o p m e n to ft h eo l dm e t h o d f i n a l l y , an e wl e v e lv e c t o ri s p r o p o s e da n dv e r ye f f e c t i v e t h i sa r t i c l ei sd i v i d e di n t os i x c h a p t e r s i nt h ef i r s tc h a p t e r , w e i n t r o d u c et h eb a s i ci d e ao ft h et r u s tr e g i o na l g o r i t h m ，t h ep r e s e n ts i t u a t i o no f t r u s tr e g i o no nq u a d r a t i cm o d e la n dt h ec o n i cm o d e l c h a p t e ri ii n t r o d u c e s t h et h e o r e t i c a lb a s i so fc o n i cm o d e lt r u s tr e g i o na l g o r i t h ma n dt h en e wc o n i c m o d e lt r u s tr e g i o na l g o r i t h mf o rs o l v i n gt h es u b p r o b l e m a n dw ep r o v e s o m eo fc o n i cf u n c t i o nt h e o r e ma n dl i s ts e v e r a l t e s t i n g c l a s s i c a l o p t i m i z a t i o np r o b l e m i nc h a p t e ri i i ，b ym e a n so ft h ed o g l e ga l g o r i t h mf o r s o l v i n gt h es u b - p r o b l e m ，an o n m o n o t o n i cc o n i cm o d e lo ft h en e wc o n i c t r u s tr e g i o na l g o r i t h mi sa d v a n c e d ，w h i c hi st h ed e v e l o p m e n to ft h es e c o n d m o d e lt r u s tr e g i o na l g o r i t h ma n dt r a d i t i o n a lc o n i cm o d e lo ft r u s tr e g i o n a l g o r i t h m c o m p a r e dw i t ht h e m ，t h en e wc o n i cm o d e lh a sb e e nr e l a t i v e l y g o o dn u m e r i c a l r e s u l t s a n dt h e g l o b a lc o n v e r g e n c ea n ds u p e r l i n e a r c o n v e r g e n c ea r ep r o v e d i nc h a p t e ri v , w eg i v ean e wa d a p t i v ea d ju s t m e n t i i i o ft r u s t r e g i o nr a d i u s ，a n d an e wa d a p t i v et r u s tr e g i o nm e t h o dw a s p r o p o s e d ，w h i c hm a k eu pt h ed e f i c i e n c i e so ft h en o n m o n o t o n ec o n i cm o d e l t r u s tr e g i o na l g o r i t h m a n dt h eg l o b a lc o n v e r g e n c ea l g o r i t h mi sp r o v e d c h a p t e rvp r o p o s e sah y b r i da l g o r i t h mo f t h en e wc o n i c m o d e lt r u s tr e g i o n a l g o r i t h m w i t h t h en e wm e t h o d ，w ec a nt e s ts o m el a r g e s c a l e f u n c t i o n s b e c a u s eo fi t si d e a lm u m e r i c a lr e s u l t s ，i ti se x p e c t e dt os o l v e l a r g e s c a l eo p t i m i z a t i o np r o b l e m s t h eg l o b a lc o n v e r g e n c e o ft h en e w a l g o r i t h mi sp r o v e d ，a n df i n a l l yw ea n a l y z et h en u m e r i c a lr e s u l t so ft h e a l g o r i t h m b e c a u s et h ea p p r o x i m a t i o no ft h ec o n i cm o d e li sa l s oad i r e c t i o n f o ri m p r o v i n ga n dt a k i n gi n t oa c c o u n tt h ei m p o r t a n c eo ft h el e v e lv e c t o ro f p a r a m e t e r ss e l e c t i o n ，f i n a l l y , b ym e a n so fa p p r o x i m a t i o ne q u i v a l e n c eo ft h e c o n d i t i o n so fq u a s i - n e w t o nb e t w e e nt h eq u a d r a t i cm o d e la n dt h ec o n i c m o d e l ，an e wl e v e lv e c t o ri sp r o v e di nc h a p t e rv i k e yw o r d s ：n e wc o n i cm o d e l ；t r u s tr e g i o na l g o r i t h m ；n o n m o n o t o n et e c h n q u e s ；a d a p t i v et e c h n i q u e s ；l e v e lv e c t o r i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：孟亟 日期：手盟一 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：盈j 坠一日期：碰弓乙丘l 一 导师签名： 五辱刍 日期：堡2 ：墨：! 兰 绪论 绪论 信赖域算法是非线性优化的一类重要的数值计算方法。该算法有很好的稳定性 和很强的收敛性。近二三十年来，信赖域算法受到优化界的很大重视。 信赖域算法一般采用二次模型来逼近原问题。对于信赖域子问题( t s p ) ，已经 有很多学者对其进行了深入的研究，参见文献 1 】 2 】 3 】 4 】 5 】。而基于_ 7 - - 次模型的信 赖域算法的理论和算法也基本成熟。求解光滑无约束优化问题的信赖域算法可参见 文献【6 7 】 8 】 9 】等；而求解约束优化问题的此类算法可参见文献 1 0 】 1 1 】 1 2 】【1 3 】等； 它们的收敛性结果可参见文献 1 4 】；非光滑优化问题的信赖域算法可参见文献 【1 5 1 6 1 7 1 8 等。 然而，对于一些非二次性态强、曲率变化比较剧烈的函数，用二次模型逼近的 信赖域子问题来逼近原优化问题，效果较差。鉴于此，d a v i d o n l l 9 】于1 9 8 0 年首次提出 了求解无约束优化问题的锥模型方法。锥模型作为二次模型的推广，具有如下优点： ( 1 ) 、对于一些非二次形态强、曲率变化比较剧烈的函数，由于锥模型具有更多的自 由度，锥模型的逼近效果比二次模型的逼近效果要好。( 2 ) 、二次模型没能充分利用 以前迭代点的有用信息，而锥模型可以充分利用以前迭代点的插值信息，从而有利 于提高算法的效率。( 3 ) 、s d i 【2 0 】，w s u n t 2 3 1 和n i 【4 0 1 等人对锥模型信赖域算法在理论 上和数值实验上都给出了较充分的证明。大量实验表明，锥模型方法可以避免二次 模型方法中的不足，从而进一步改进和完善算法。( 4 ) 、锥模型和二次模型一样，既 有牛顿算法的局部收敛性，又有理想的全局收敛性，文献 2 0 2 1 2 2 和文献 3 0 4 0 4 4 等研究了锥模型共线调比拟牛顿算法、锥模型拟牛顿法和直接搜索法。 文献 2 3 1 提出了求解光滑约束优化问题的锥模型信赖域算法，同时还给出了锥模型信 赖域子问题的最优性条件。文献【2 4 】 2 5 】【2 6 】对锥模型信赖域子问题的算法及收敛性 进行了研究， 2 7 2 8 对约束优化问题的锥模型信赖域算法进行研究。然而上述锥模 型信赖域算法都是在超平面即：1 一b r s 0 的一侧求解优化问题的最优解。2 0 0 5 年， 为了克服锥函数的可能无界性和扩大求解范围，倪勤在文献 2 9 1 中提出了新锥模型信 赖域子问题，并给出了相应的最优性条件，这为进一步研究锥模型算法提供了一个 新的途径。关于新锥模型信赖域子问题的研究参考文献 3 0 3 5 。近几年来，由于其 良好性质，锥模型及新锥模型信赖域算法的研究吸引了越来越多的重视和研究，从 新锥模型信赖域算法研究 而新锥模型信赖域算法也因此蓬勃发展，己经发展成为具有了一定的理论基础并且 实际计算中具有某方面优势的算法。 锥模型信赖域算法的关键步骤是构造锥模型信赖域子问题及求解。当倪勤提出 了新的锥模型信赖域子问题后，许多学者对新锥模型信赖域子问题的改进，除了把 有些锥模型信赖域子问题转化成二次模型子问题、凸规划或对偶问题来求解外，陆 晓平提出的锥模型折线法继承了二次模型折线法的优点，且在一定程度上改进了新 锥模型信赖域算法。从而，本文在解决新锥模型信赖域子问题上都采用新锥模型信 赖域子问题的折线法。 综上所述，二次函数模型的优化算法已有多年的深入研究，理论和算法都已经 比较成熟，而锥模型算法还有很多的研究工作要做。因此，本文主要研究新锥模型 信赖域算法框架的改进，在算法迭代过程中，目标函数信息，梯度信息及二次信息 影响着算法的收敛程度。考虑到在二次模型传统信赖域算法中，带有目标函数信息 调整策略的非单调技术和带有梯度信息( 或二次信息) 的信赖域半径调整策略的自 适应技术在算法改进上的突破，我们也将其应用到新锥模型信赖域算法中，针对锥 模型自身的特点给出带有水平向量信息的调整策略。并给出新算法的收敛性分析， 最后用数值实验验证了新算法的有效性。所以，我们首先介绍基本的锥模型信赖域 算法。 2 第一章锥模弛信赖域算法简介 第一章锥模型信赖域算法简介 新锥模型信赖域算法的提出是建立在补充与完善锥模型信赖域算法和二次模型 信赖域算法的基础之上，为了更好的了解新锥模型信赖域算法的发展与前提，本章 首先给出不同逼近模型下的信赖域算法简介。 1 1 二次模型与信赖域算法 信赖域算法的研究起始于p o w e l l 等人的研究在一定意义下著名的求解非线性最 小二乘的l e v e n b e r g - m a r q u a d t 算法( 见文献【3 7 】- 3 8 ) 是一个特殊的信赖域算法。所以人 们提及信赖域算法的历史总是追溯至l j l e v e n b e r g - m a r q u a d t 算法。 为叙述方便，文中统一定义： 五= f ( x k ) ，g 。= 町( k ) ，色= v 2 f ( x 。) 或为v 2 f ( x k ) 的近似对称矩阵。 针对无约束优化问题 m i n s ( )( 1 1 ) p o w e l1 在文献【7 中给出无约束优化问题的一般信赖域算法： 算法1 1 步骤1 给出x o r ”，b o r n 。na o o ，s 0 ，0 7 7 l 7 7 2 1 ，0 y 1 1 y 2 ，k = 0 ； 步骤2 如果恬。忙s ，则停；否则，求解信赖域子问题得到j 。； 步骤3 计算p r e d k ，a r e d k ，r k ： m 反训0 ) - 沙p 巩= 六一f ( x k 州，= 等 诋。= k 簇 雠蕊茹； 步骤4 修正b ；尼= k + 1 ，转步2 ； 注算法1 1 中的信赖域子问题为 罂妒丸( s ) = f ( x k ) + 爵s + 了15 t 瞑s ( 1 2 ) 盯s a t 其中，屯( s ) 是在稚处逼近原问题的二次函数。 从算法1 1 中可以看出，信赖域算法的构造和逼近是密切相关的。即给出一个当 新锥模型信赖域算法研究 前迭代点x 。，构造一近似于原问题的逼近模型。由于该模型主要是基于原问题在x 。的 信息，故此模型仅在x 。附近可以很好的逼近原问题。所以人们仅在x 。附近的某一邻 域内相信该模型。信赖域算法的子问题都是在当前迭代点x 。附近的某一邻域内求逼 近模型的最优点，该邻域被称为信赖域。它通常是以x 。为中心的广义球，球的半径 被称为信赖域半径。信赖域的大小通过迭代逐步调节。一般说来，如果在当前迭代 模型较好地逼近原问题，则扩大信赖域半径，否则缩小信赖域半径。 信赖域算法的关键组成部分是如何求得信赖域试探步以及怎样决定试探步是否 可以被接受。试探步是信赖域子问题的解，所以如何求得信赖域试探步实质上归结 于子问题的构造。传统的信赖域子问题是用二次模型来逼近原函数。文献 1 并1 1 2 0 】 独立证明了二次模型信赖域子问题的最优性条件，并给出了求解信赖域试探步的算 法决定试探步是否可被接受通常是利用某一价值函数，看试探步是否能使价值函数 下降。对于无约束优化问题，价值函数显然是目标函数。对于约束优化问题，价值 函数常常是一罚函数。 1 2 锥函数 1 9 8 0 年，d a v i d o n 首次提出了锥函数。下面给出锥函数的一个定义： 定义1 1 如下形式的函数厂：x r 称为锥函数： 所( m + 篇+ 丢尚，( 蜘 1 或b s s 0 ) ， 则问题( 1 9 ) 的可行集为s q ，其中q = b n s 倪勤在文献 4 0 】中给出女口t e j i n _ 引理2 1 假设0 ( o ，1 ) ，b r ”，a 0 ，令s i = s r ”i 配s 1 - e o ， = j r ”i 配s l + e o ，则 f b i f1 - s 。a 。i i b k0 q = b n s 矿1 1 - a 。i t b k t | l 。 即s s ，又因为bcs ，所以q = bf ls = b 。 ( 2 ) i 发 1 - a 。0 b k 氏，如果s b ，即a 女，则b k t s _ i b ka 。 1 + ，则s 诺s ：， 因此bns ，= 妒，则q = bns = bns ， 7 新锥模型信赖域算法研究 ( 3 ) 如果t1 1 仇1 1 l + s 。，贝u6 。，令 8 2 - - m i n 1 ，t 面湍，贝os b 且 烨”引警渊外即眺脚。钒= 南吣灿：召且 醛是= 1 1 钆1 1 女1 + s 。即s 2 s 2 因此bns ，b ns 2 贝, t jn ：( b n s 。) u ( b n s 2 ) 因此，根据限| | 和。的不同，新锥模型信赖域子问题可以分成如下三种情况： 当1 一。怜i i 时，问题( 1 8 ) - ( 1 9 ) 变为 = 群。 当1 1 一。f i b k l l l 。时，问题( 1 8 ) 一( 1 9 ) 变为 i l l l l l l r e ( s ) 1j ，i i s l l 。，酲j 1 一s 。 当。慨l l 1 + s 。时，问题( 1 8 ) 一( 1 9 ) 变为 ，n 、 m i n 垅( s ) 只仁 0 ，则s 与d 位于超平面1 - b7 1 s = 0 的同侧，若1 一b7 1 b 一1 9 。时，一6 7 s = t 一6 7 ( i _ = 三丢拿最 = t 二= _ 石害巧 。 1 - b r b - l g 赢删函数 所在志一诗上严格单调递增。同时函姒唧，在 佗诸籼志上严觯调黼 ( 3 ) 若g r b g b r g g7 g 0 ，则函数聊( 一r g ) 在f 0 上单调递减。 证明由( 1 8 ) 得 聃卅嘲2 丽- r gr g 畦端 亿6 ， 芴( r ) = - g r g ( 1 而+ r b 刁r g ) 万+ r g r g b r g + 4 r g r b g ( 1 + r b t 丽g ) 2 石- 4 露r 2 9 厂r b g b r g 一( 1 + b r g ) 9 新锥模型信赖域算法研究 ：二墨：星+ 三星! 丝：星+ ! 星：垒垒一r 2 9 r b g b r g 1 + r b7 9 ( 1 + r b 7 9 ) 2 ( 1 + r b 。g ) 2( 1 + r b 。g ) 3 r ( g7 8 9 g r g b7 g ) 一g7 g = 一 ( 1 + r b7 g ) 3 =等紫”丽gr91+rb( i g 丫 、 g ib g g ig b ig ( 1 ) 当g r 磁一b r g g r g 0n b 7 g 0 时，由( 2 7 ) 得l + 而r g 1 s o 0 ， 若。f 0 g ib g b lg g lg 一 若仁而身靠，确一o ( 2 7 ) ( 2 ) 当g r 风一b r g g7 g 0 且67 1 9 赢，当志一诗时k 。可知 1 + 扩g 1 + 诸6 g 诋地则自( 2 7 ) 粝 o 由于 所以 1 + o i b r g i 巍2五i+eo一卒1sg b t g ggb t g 五 。 一= = i i g t t g tb gk t ， 诸 志 亿8 ， 靴诸棚2 固孙 志鼬魄枷可知 1 + 比1 + 雨l + e o 6 7 1 9 一。 。，脚7 ) 得确 。 若晒 面岛而，i 扫b r g 。，贝。由( 2 7 ) 得鬲( r ) 0 ， g 。g 若f 0 ，1 + r b7 g 0 ，则由( 2 7 ) 可知 证毕 令 确= 觜卜盎， = 万拓g r _ g t 咖r g ) _ g r g ) “6 i 旧一f 5 ，科c ( b g ) 0 。 r ( ) ( 2 ) 当l - abl 0 b r g 0 ( 3 ) 当a l b l + e 。时，f 的定义同( 2 ) 中的定义。 定理2 5 设若b 为正定对称矩阵，g 0 ，c ( 忪) 0 ，1 - b 7 1 艇0 ， ( 1 ) 若1 67 b 一1 9 0 ，则锥函数( 1 8 ) 在线段s ( ，) = s 印+ ，g 一s 印l0 f 1 在是，的 1 l 新锥模型信赖域算法研究 单侧递减函数。 ( 2 ) 若1 - b7 b 。1 9 0 ，假设直线j = s 印+ r b 一) 与超平面1 67 s = 0 的交点为 s r 0 ，f o 为对应f 值，则锥函数( 1 8 ) 在射线s o ) = j 印+ f b 一s 印lf 0 ，c ( b g ) 0 ，0 f 1 , g l ( 2 1 0 ) 、( 2 11 ) 矢h 卢。 0 ， 卢 0 ，又由柯西不等式知g r b g g7 b g g t g g7 1 9 0 ，所以由( 2 2 2 ) 可知办o ) 0 即这时，厅( ，) 为0 ，1 上单调递减函数。 ( 2 ) 1 一b7 b g 0 ，p 0 ，因此得0 ，即垆+ ( 1 - o f f 印 o 同理，当f 0 因 此若1 一b7 b g 0 ，当0 0 ， 卢 0 ， 印+ ( 1 一f 归印 o 代入( 2 2 2 ) 得力。o ) 0 ，故可得这时，办o ) 为0 0 ， 所以，办o ) 为f 0 ，b r ”i i ；葑足_ a l l b l 1 一s 。则s + 是子问题( 尸1 ) 的解当 且仅当存在r 0 ，有 陋一g b7 + ， + = 一g + r 2 6 ( 2 2 5 ) r 一) ：l ( 2 2 6 ) 且b + r ( ，一2 6 67 ) 是半正定矩阵，若b + 才( ，一a 2 b b7 ) 正定，则s 。是( 尸1 ) 的唯一解。 定理2 7 【4 0 】设一。 a i b - 1 s o ，如果s 是子问题( 尸2 ) 的解，则存在正，t 0 使得 ( b g b r + 一巾+ = 一g 一舶 ( 2 2 7 ) 正0 l s + 0 一) = o ，l l ；( b t s * - - 1 + s 。) = o ( 2 2 8 ) 且对任意d b r d ：o 有d 7 h q 。d o 其中雪= b + i ，+ 石6 67 ，石= t 。一_ 2 ， 1 4 第二章新锥模璎信赖域子问题分解及性质 彰b = b ，q 的定义参见文献 4 0 】。 定理2 8 i 4 0 1 设b 为对称矩阵，一s 。 l l b - 1 s 。，若存在正，t 芝0 ， ( b - g b r + 小= - g 一舢 i - ) = u ，t 一l + g o ) 一- - ，6 1 咱，且i i s l l 1 + s 。 其中台：b + 九：，+ 动67 1 0 ，石= t s 。一2 ，则j + 是子问题p 3 ) 的解。 由定理2 1 0 2 1 4 可得。 定理2 1 1 3 4 1 设b o 且1 一b r b 一1 9 0 ，若s j q ，则s 为问题( 1 8 ) 一( 1 9 ) 的唯一解； 否则( 1 8 ) ( 1 9 ) 的解必在可行域q 的边界上达到。 证明对于子问题p 1 ) 由定理2 1 0 可知，如果s 是( p 1 ) 的解，因b 0 由( 2 2 5 ) 可得 当才= 0 时，s = s n 且s 即为( p 1 ) 的唯一解；当才 0 时由( 2 2 6 ) n - - 丁彳 i s * i l = ，知s 在信赖域的边界上。 对于子问题p 2 ) 由定理2 7 可知，如果s + 是p 2 ) 的解，因b 0 由( 2 2 7 ) 可得当 正= a ：= 0 时，s + = s b s 即为( p 2 ) 的唯一解；当硝 0 ，t = 0 时，由( 2 2 8 ) 可得 妒i i = ，则s 在信赖域的边界上；当石= 0 ，t 0 时，由( 2 2 8 ) 可得，j + 在可行 1 5 新锥模型信赖域算法研究 域q 的1 一b r s = s o 边界上；当 0 ，t 0 时得s ) - b 忙l l = 域1 67 j = s 。的交点， 此时s 在可行域q 边界上。证毕 对于子问题( p 3 ) 由定理2 1 0 类似上述证明，若s q ，则s _ 即为子问题( e e ) 的唯一解；否则( p 3 ) 的解必在可行域q 的边界上达到。证毕 文献 3 1 中给出如下定理，详细证明略。 定理2 1 2 设b 0 ，j 为( 1 8 ) ( 1 9 ) 的解。若存在l a g r a n g e 乘子硝使得 1 一b7 ( b + 2 ：i ) - 1 9 0 ，则有 j + = 一( b + 一，) 。1i三二兰圭i三三拿铲g+(s。一2)6。235、 2 4 求解子问题的折线法 2 2 节中的性质定理及2 3 节中子问题的最优性条件为折线法的求解提供了依 据，则求解子问题( 1 8 ) ( 1 9 ) 根据l b l ，g 。和的关系，总能转化为子问题( 尸1 ) ( 尸2 ) ( p 3 ) 之一，为了叙述简洁我们去掉迭代下标，首先给出如下算法【3 4 】： 子算法1 ( 解子问题( p 1 ) ) 步骤1 计算s _ = 一b - 1 9 ( 1 一b r b 。1 9 ) ； 步骤2 如果忙l l a ，则s = s ，停止； 步骤3 计算s d = 一r g ，f 由定理2 4 的( 1 ) 式决定； 步骤4 如果f = r ( ) ，则s + = s d ，i 步骤5 计算柯西点，s = s g ) = ，+ + ( 1 一f ) s 印，其中f 满足忙g + 】i = ，当 1 67 b 一1 9 0 时，取，+ = t l ；当1 67 b 一1 9 0 时，r = ，2 其中 t l ：- c + 、c 2 - a d ，t 2 ：二掣，口：o s 一s 印1 2c = g 一j 印) r s 印 a口 ” ” d = s o p 卜2 ， 0 ，则s = ，其中f + 满足1 + f b7 g = s 。停止； 步骤6 如果忙叩 ，令s = s ( f ) = f + s + ( 1 一f ) s 印，其中满足 l l s ( r 1 1 = ，r 。= - c + 后_ c i 2 一- a d ，r ：= - c - 厅_ c 7 2 - a d ，口= i i s , , - s 印1 1 2c _ - g 一j 印y j 妒 d = m 1 2 _ 2 ，o t ， u 2 o 时，若s 。) q ，岛= s ( f 。) ，否则计算s 。= f s + ( 1 - t 轧必印， 其中0 ，。 1 使得1 - b7 屯= 占。成立，若j q ，则j = j 。，停止，否则j = 劫， 停止； 步骤8 当1 6 7 1 b - 1 9 o 时，取f + = f 2 ，s = s ( f 2 ) ，d = 忙印j 1 2 一2 ，0 r l ， 1 ，r 2 o 子算法3 ( 解子问题( p 3 ) ) 步1 7 同子算法2 的步1 7 ； 步骤8 当1 一b r b g 0 时，计算f 一，使得1 一b tg s ，+ ( 1 一必印) = 一s 。成立，如果 0 t l 0 ，而此时锥模 型子问题的求解也近似二次模型子问题求解，这样做又容易使锥模型信赖域失去其 自身的特点。而且信赖域位于超平面1 一b r s = 0 的一侧，这样使得所求的解只在超 平面的一侧，当牛顿点s 、，和原点d 在超平面l b r s = 0 的同侧，且原点d 离牛顿点 s ，比较远时，因信赖域半径的大小受限制，所得解有可能不接近牛顿点。而当牛 顿点j 和点d 在超平面1 一b r s = 0 的异侧时，因信赖域被限制在超平面l b r s = 0 的原点d 的那侧，所求解不可能和牛顿点很接近，这样就可能会降低算法的效果。 而新锥模型信赖域子问题求解包括了b 和的各种情况，当牛顿点s 和原点d 在 1 一b r s = 0 的同侧，即使初始点0 离牛顿点j 比较远，也可取较大的信赖域半径， 使得所求解接近牛顿点当牛顿点s 和点d 在1 一b r s = 0 异侧时，所求的解仍可以与 牛顿点在1 一b r s = 0 同侧，也可间接达到牛顿点因此本文采用新锥模型子问题求解 有望获得更好的效果，下面我们先给出基本的新锥模型信赖域算法： 新锥模型信赖域算法2 3 步骤1 给出r ”，b o r n , b o r “”，( 一般选择b o = 0 ，b o = 1 ) ，a o 0 和精度 要求s 0 ，0 7 1 7 7 2 1 ，0 y l 1 y 2 ，k = 0 ； 步骤2 如果fg 。l | s ，则停；否则转步3 ； 步骤3 用折线法求解新锥模型信赖域子问题： 当1 一s o 时，调用子算法1 ；当1 1 一0 s 。时，调用子算法2 ；当i + e 。 时，调用子算法3 。转步骤3 ； 步骤4 计算丘，进行试探步可接受性检验； 步骤5 修正b m ，反+ l ， 置k = k + l ，转步2 。 注上述算法中反+ 。满足以下式子：( 详细推导公式参考文献 4 1 】) 仇+ l & 2 y k r 2 3 6 ) 1 r 第二章新锥模型信赖域子问题分解及性质 卸。+ 石y k y r 一鬻帆= 等繇 ( 2 3 7 ) p 。+ 。：一 + 。) 2 一g ；5 。k 五，s 。) ，儿：卢。+ 。g 。卅一卢乏。g 。，6 i “：鱼垒争二! g 。( 2 3 8 ) g ；s k 引理2 1 3 3 4 1 令s t 是算法2 3 产生的解，则有 删 目酬池 南，粉，莆) 亿3 9 、 25 几釉绎血测试甬数 无约束优化问题中，针对不同的具体问题，算法的设计也不同，鉴于二次模型 信赖域算法与锥模型二次信赖域算法的区别，我们给出几种经典的测试函数，主要 检验新算法的可行性及收敛效果的好坏。由于二次模型信赖域算法对某些非二次形 态强，且曲率变化剧烈的函数( 最常见是r o s e n b r o c k 函数也称为“香蕉函数”) 收敛效 果较差，我们希望给出的新算法能达到收敛效果较好的目的。以下给出具体的优化 测试问题以及用m a t l a b 软件画出三维空间中的八个函数图像。 ( 1 ) c o n i cf u n c t i o n - 厂g ) = ( x ? + x ；) ( 1 一x ，) 2 ( 2 ) c u b ef u n c t i o n ： 厂g ) = 1 0 0 ( x ：一x ? ) 2 + ( 1 一x l 2 ( 3 ) b e a l ef u n c t i o n ： y 1 = 1 5 ；y 2 = 2 2 5 ；y 3 = 2 6 2 5 厂g ) = ( j ，l - - x l ( 1 - - x 2 ) )