（应用数学专业论文）求解信赖域子问题的折线算法研究.pdf

中文摘要 信赖域算法是求解非线性优化问题的一类重要的数值计算方法，由于信赖域算 法具有良好的性质，即强适性和较强的收敛性，因此受到非线性优化研究界的广泛重 视特别是最近十多年，这种方法已经成为非线性最优化问题研究的一个热点而求 解信赖域子问题是实现信赖域算法的关键，信赖域子问题的求解直接影响到算法的 稳定性及收敛性在信赖域子问题的求解算法中，折线法( 包括单折线法，双折线法， 混合折线法及不定折线法等) 是一类重要并且有效的算法。本文主要研究求解信赖域 子问题的折线算法 第一章简单介绍了信赖域方法，主要介绍求解信赖域子问题的两类折线算法以 及本文要做的工作 第二章提出了一种带线搜索的自适应混合折线信赖域算法，将求解信赖域子问 题的混合折线法与自动确定信赖域半径的方法相结合，并且在试探步不可接受时， 采用线搜索来计算下一个迭代点，在适当条件下，证明了算法的全局收敛性，数值 试验验证了新方法的有效性 第三章在第二章算法的基础上引入了非单调技术，提出了一种带线搜索的自适 应非单调混合折线信赖域算法，当计算的函数出现峡谷时，有助于减轻计算负担 在适当假设条件下，证明了算法的全局收敛性，数值结果表明新方法有效 第四章提出了一种非单调自适应不定折线信赖域算法，当玩不正定时，下降方 向主要运用b u n c h p a r l e t 分解来确定，不同于一般的非单调信赖域算法，新算法 根据实际下降量与预估计下降量的比值按照变化的速率对信赖域半径进行调整在 一定条件下证明了算法的收敛性，并且给出了相应的数值试验结果 关键词：无约束优化；信赖域算法：信赖域子问题；折线算法；非单调技术；自适应 技术 a b s t r a c t t r u s tr e g i o n ( t r ) m e t h o di sa ni m p o r t a n tc l a s so fn u m e r l 。c a lm e t h o d f o r s o l v i n gn o n l i n e a ro p t i m i z a t i o np r o b l e m s t r m e t h o dh a sp r e f e c t p r o p e r t i e s ，t h a ti s ，r o b u s t n e s s a n de x c e l l e n tg l o b a lc o n v e r g e n c e s ot h i s m e t h o dh a sa t t r a c t e dm a n ys c h o l a r s a t t e n t i o n e s p e c i a l l y ，t h i sm e t h o dh a s b e e nar e s e a r c hh o ts p o tf o rn o n 1 i n e a ro p t i m i z a t i o ni nt h er e c e n td e c a d e i t i sv e r yi m p o r t a n tt os e e kas o l u t i o no ft h et rs u b p r o b l e mf o rt h er e a l i z a t i o n o ft h et ra l g o r i t h m as o l u t i o no ft h et rs u b p r o b l e ma f f e c t st h es t a b i l i t y a n dc o n v e r g e n c eo ft h et r a l g o r i t h md i r e c t l y i nm a n y k i n d so ft h es o l u t i o n o ft h et ra l g o r i t h m ，d o g l e gm e t h o d s ( i n c l u d e ds i n g l ed o g l e gp a t h ，d o u b l e d o g l e gp a t h ，h y b r i dd o g l e gm e t h o da n d i n d e f i n i t ed o g l e gp a t ha n ds oo n ) a r e i m p o r t a n ta n de f f e c t i v ea l g o r i t h m t h i sp a p e rm o s t l yr e s e a r c h e st h ed o g l e g m e t h o df o rt h es o l u t i o no ft h et rs u b p r o b l e m i nc h a p t e ro n e ，w ef i r s ti n t r o d u c et h et rm e t h o ds i m p l y ，a n dw e i n t r o d u c et h et w ok i n d so fd o g l e gp a t h sa n dt h ew o r kt h a tw eh a v ed o n e i nc h a p t e rt w o ，a na d a p t i v eh y b r i dd o g l e gt r u s tr e g i o nm e t h o dw i t hl i n e s e a r c hw a sp r e s e n t e da n da n a l y z e d w ec o m b i n e dt h eh y b r i dd o g l e gm e t h o d w i t ht h ea d a p t i v em e t h o d ，i fat r i a ls t e pw a sn o ta c c e p t e d ，w ep e r f o r m e da l i n es e a r c ht of i n das u c c e s s f u l i t e r a t i v ep o i n t u n d e rs o m em 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 er e s u l t so ft h en e wm e t h o dw e r ep r o v e d n u m e r i c a l e x p e r i m e n t ss h o w e dt h en u m e r i c a lr e s u l t sa tt h en e wm e t h o d w e r ee f f i c i e n t i nc h a p t e rt h r e e ，an o n m o n o t o n ea d a p t i v eh y b r i dd o g l e gt r u s tr e g i o n m e t h o dw i t hl i n es e a r c hw a sp r e s e n t e da n da n a l y z e d o nt h eb a s i so ft h e a l g o r i t h mw h a tw ep r e s e n t e di nt h ec h a p t e rt w o ，w ec o m b i n ei t w i t ht h e n o n m o n o t o n et e c h n o l o g y ，w h e ni nt h ep r e s e n c eo ft h en a r r o wc u r v e dv a l l e y ， t h et e c h n o l o g yc a na l l e v i a t et h eb u r d e no fc a l c u l a t i o n u n d e rs o m em i l d c 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 er e s u l t so f t h en e wm e t h o dw e r ep r o v e d n u m e r i c a le x p e r i m e n t ss h o w e dt h a tt h en e wm e t h o dw a se f f i c i e n t i nc h a p t e rf o u r ，an o n m o n o t o n ea d a p t i v ei n d e f i n i t ed o g l e gp a t ht r u s t t t i r e g i o nm e t h o dw a sp r e s e n t e da n da n a l y z e d w h e nb 女w a si n d e f i n i t e ，t h e d e s c e n d e n td i r e c t i o n g e n e r a t e dm a i n l yb ye m p l o y i n g b u n c h - p a r l e t t f a c t o r i z a t i o n d i f f e r e n tf r o mt r a d i t i o n a ln o n m o n o t o n et ra l g o r i t h m ，t h e t r u s tr e g i o nr a d i u sw a su p d a t e da tav a r i a b l er a t ea c c o r d i n gt ot h er a t i oo ft h e a c t u a lr e d u c t i o nt ot h ep r e d i c t e dr e d u c t i o no ft h eo b j e c t i v ef u n c t i o n w e s h o w e dt h a tt h ea l g o r i t h mp r e s e r v e dt h es t r o n gc o n v e r g e n c ep r o p e r t i e so f t rm e t h o d n u m e r i c a lr e s u l t sw e r ep r e s e n t e da n dd i s c u s s e d 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 ；t r u s tr e g i o na l g o r i t h m ；t r u s t r e g i o ns u b p r o b l e m ；d o g l e gp a t hm e t h o d s ；n o n m o n o t o n et e c h n i q u e ；a d a p t i v e t e c h n i q e s i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：二至奠3 垒址日期：二造与l 曼l 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文：学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 茎垒竺茎乞日期：兰聋! 堑! 廷 、 导师签名： 乏缉垒 日期：洲6 t iz - 第一章绪论 第一章绪论帚一早珀t 匕 本文主要从信赖域子问题的角度，讨论了无约束非线性优化的信赖域算法针 对信赖域子问题的类型，构造了不同类型的信赖域算法，并做了相应的收敛性与数 值试验 1 1 非线性优化的信赖域算法 信赖域方法( t r u s t r e g i o nm e t h o d s ) 是求解非线性规划的一类较新的方法，在 近二十年来的发展历程中，它受到最优化研究者的高度重视，一直以来是非线性规 划的研究热点其研究起始于2 0 世纪六十年代的p o w e l l 1 ，其基本技巧在一定意义 上等价于著名的求解非线性最小二乘问题的l e v e m b e r g r l a r q u a d t 算法2 1 信赖域算 法与传统的线搜索不同，它可以用非凸函数逼近模型，具有可靠、稳健性的特点， 可用于“病态”问题求解，具有较强的收敛性，它可以用来代替一维搜索，解决 h e s s i a n 矩阵最不正定和孔为鞍点等困难，既有牛顿法的快速局部收敛性，又具有 理想的总体收敛性 考虑无约束优化问题 m i n f ( x ) ，x r ” ( 1 1 ) 其中厂：r ”- - r 二次连续可微 信赖域方法的基本思想是：在每次迭代中给出一个信赖域，这个信赖域一般是 当前迭代点x 。的一个小邻域然后在信赖域上求解一个子问题，我们称这个解s 。为 试探步( t r i a ls t e p ) 然后再利用某一评价函数来决定是否接受该试探步以确定 下一个迭代的信赖域如果试探步被接受，则吒+ l = + s ，否则x k “= 讫新的 信赖域的大小取决于试探步的好坏粗略的说，如果试探步较好，则信赖域的大小 保持不变或者扩大：否则，将缩小信赖域 对于无约束优化问题( 1 1 ) ，利用二次逼近，可构造如下的信赖域子问题： r a i n q t k ) s ) = ( t ) + g t t s + i 1s t 色ss j 0 s 0 ( 1 2 ) 其中g 。r ”为目标函数厂g ) 在当前迭代点x 。的梯度，反r “”为目标函数厂b ) 在 当前迭代点z 。的h e s s i a n 矩阵或其近似，h 。为信赖域半径，s 为待求变量 设s 。是信赖域子问题( 1 2 ) 的解，一般情况下，我们称目标函数y ( x ) 在第k 步 求解信赖域子问题的折线算法研究 的实际下降量为 a r e d 。= ：f ( x 。) ( x 。+ 。) 称二次模型函数g ( & ) 的下降量 p r e d 。= ( 0 ) 一q g 。) 为预估计下降量，定义比值 r k = a r e d 女p r e d l 它衡量了二次模型g ( ( ) 与目标函数厂g ) 的逼近程度，： 越接近于1 ，表明逼近程 度越好 下面给出无约束优化问题的一般信赖域算法： s t e p l 给出初始值而，s ，0 乞 c 4 1 c l ，0 c o c 2 l ，令h o = | lg oj j ，k = 0 s t e p 2 如果恬。1 l s ，则停止 s t e p 3 解信赖域子问题( 1 2 ) ，求出 s t e p 4 。求出r k ，根据r k 的大小决定是否接受试探步& 以及如何调节信赖域半径 h ： f ， 12 t 坼+ s k 如果c o ； 否则 选择h k 满足： e c 3 鹏1 1 s kl l , c , 1 嚣2 ； s t e p 5 修正b ，k ：= k + 1 ；转s t e p 2 1 2 无约束信赖域算法的研究现状 信赖域子问题是信赖域方法的关键组成部分，它的有效求解直接影响算法的效 率求解信赖域子问题( 1 2 ) 的方法主要有： ( 1 ) 解信赖域子问题的折线法：对于无约束问题( 1 1 ) ，当( 1 2 ) 中的玩变化 2 第一章绪论 时，s 的解形成一条空间曲线，称为最优曲线，求解子问题( 1 2 ) 比较有效和实 用的信赖域方法是折线法，该方法构造折线近似最优曲线，然后得到子问题( 1 2 ) 的近似解这种组合曲线路径和信赖域的思想最早出现在p o w e l l 的单折线算法【3 】 中，现在各种曲线路径信赖域算法层出不穷，例如，双折线算法【4 1 ，s o r e n s e n 5 1 提 出的算法，m o r e 和s o r e n s e n 的算法【6 1 ，限制梯度路径算法【7 】，步长函数算法偈1 ， 不定折线路径算法【9 1 ，徐成贤等提出了切线单折线法【1 0 】在这些基础上，张立【1 1 1 等 在2 0 0 1 年提出了混合折线法，数据表明，混合折线法优于单折线法 ( 2 ) 解信赖域子问题的拟牛顿法：拟牛顿法具有许多优点，比如：迭代中仅需 一阶导数，不必计算h e s s i a n 阵，除d f p 算法外的b r o y d e n 族算法具有超线性收敛 性，以及它具有n 步二阶收敛速率的性质拟牛顿法的应用主要是 鼠1 的秩校正公 式以避免m a r o t o s 效应，集中于 反 的拟牛顿型秩校正，如b f g s ，s r i ，d f p 以及 邓乃扬等提出的基于新拟牛顿方程的拟牛顿算法i l2 1 李换琴等提出改进的s r i 拟牛 顿算法的2 刀步q 二次收敛性【1 3 i ；k b a l f a nh f 的s r i 校正的理论与实验分析m 1 ； 陈兰平，焦宝聪对非拟n e w t o n 的非凸族作了收敛性分析【1 5 】；n iq i n 提出的有限内 存的拟牛顿算法【1 6 】；z h a n gj i a n z h o n g 等人提出一类新的拟牛顿方程： b k + 1 & = 或= m + 仇乱( s ；& ) 及其收敛性n 7 1 ；b e n e d e t t am o t i n i 等人在其文献中给 出的不精确拟牛顿算法1 2 等 ( 3 ) 解信赖域子问题的共轭梯度法：共轭梯度法由于不需要矩阵计算和存储， 成了解大型问题的首选方法主要有s t e i h a u g 体】提出的用预处理共轭梯度法c g 解 信赖域子问题；孙文瑜和后六生【1 9 1 提出了三项预处理c g 法；赵良英和徐成贤 2 0 1 提 出用共轭梯度法解信赖域子问题的重新开始策略等 与近年来流行的其他优化算法一样，信赖域算法与其他优化算法的结合是一个 必然趋势，比较有代表意义的结合方式有：与线搜索算法结合，j o r g en o c e d a l 和袁 亚湘将线性搜索方法和信赖域算法相结合，提出回溯线搜索技术：与内点法结 合，一方面，构造罚函数以避免迭代点列溢出可行域，另一方面是c o l e m a n 和l i 提出了尺度信赖域约束0 毋j 0 魂策略：a r c o n n 等人提出了两步( t w o s t e p ) 信赖 域算法【2 2 1 传统的信赖域方法为了保证算法的整体收敛性，都要求新的迭代点能保证目标 函数值或价值函数比当前的值要严格单调减少然而，人们在实际计算中发现：对 于某些问题，这样做并不能保证算法是有效的g r i p p o 2 3 】等人首次提出了非单调线 搜索，并将此技术分别运用到n e w t o n 法和截n e w t o n 法中邓乃扬【2 4 】等人利用非单 气 求解信赖域子问题的折线算法研究 调性策略这一技巧首次提出了一类具有强收敛性的非单调信赖域算法最近两年， 莫降涛、刘春燕和颜世翠让5 1 提出了一种带有固定步长的非单调信赖域方法；可婷和 景书杰【2 6 1 提出了一类带线性搜索的非单调信赖域算法 信赖域方法中的重要问题之一是信赖域半径的选取，因为它对算法的效率有重 大的影响，在传统的信赖域方法中，信赖域的半径都是靠经验来选取的，而没有一 般的规则来指导我们为克服此缺点，许多学者将自适应技术与信赖域算法相结合 提出了自适应信赖域算法 1 3 与本文有关的求解信赖域子问题算法 对于信赖域子问题( 1 2 ) ，当信赖域半径h 露变化时，s 的解形成一条空间曲线， 人们可以在信赖域内沿着从x t 出发的曲线近似求解信赖域子问题由这种组合曲 线路径和信赖域的思想启发，将问题( 1 1 ) 转化为一个求解近似解的二次最小化 模型： m i n q 。( s ) is s ，1 1 4 - c p 一i n p 寸磋为双折线 赵英良等提出了一个切线单折线法，如果最可逆，过式作最优曲线的切线， 将切线投影到由- g 。和一所1 & 所张成的平面上，我们把投影与一g 。的交点称为x 。( k ， j 瑶一为切线单折线法 而张立等提出的混合折线法是由切线单折线法和双折线法构造的，即 j 一 - - 印( k 寸瑙成为混合折线法 4 第一章绪论 当b 不正定时，s 是由一g k ，一( 鼠+ ，) g 。和一个负曲率方向d 张成的三维空 间，其中负曲率方向d 是由b u n c h p a r l e t t 分解【2 8 1 来构造的 工： 图1 11 2 1 单折线步方法和双折线步方法 f i g u r e l 1s i n g l ed o g l e gp a t h ，d o u b l ed o g l e gp a t h 我们将在下面的两个小节中对混合折线法和不定折线法进行详细介绍 1 3 1 求解信赖域子问题的混合折线法 1 3 3 基于单折线法、双折线法及切线单折线法，张立等给出了混合折线法本文第 二章及第三章构造的信赖域算法中，求解二次模型信赖域子问题( 1 2 ) 采用下面构 造的混合折线法： 算法1 1 混合折线算法 s t e p l 给出x 。和信赖域半径h 。，计算级和最 s t e p 2 计算牛顿点和近似牛顿点： s w ( k = - b i l 致 - - j 驴( k - ( o 8 b + 0 2 i ，s 甲a b = g ) 2 g 孤g 。x g ；b ；1 9 。) s t e p 3 计算投影矩阵： a = ( g 。，一b i g 。) ，p = 彳( 彳7 彳广1 4 ， s t e p 4 令c = 一s 竺，e = p 巧1 c ，确定p 和g 女的第歹个分量， 使 g 。( 1 ) p ( ) 一g 。( ) p ( 1 ) 0 ，令 气 求解信赖域子问题的折线算法研究 口= ( c ( 1 ) p ( _ ，) 一c u ) p ( 1 ) ) ( 毋( 1 ) p ( ) 一反( ，) p ( 1 ) ) ， 则= - a g 女 s t e p 5 计算子问题( 1 2 ) 的解： ( 1 ) 若吃- 1 1 s 驯，则 2 h k - g k l l g , i i ( 2 ) 矧s 纠 o ，d ，= o ，d 。 o ( 1 7 ) 尚 p 肾，蚴i l d l l 怛l , i l d l l2 ) 8 ， 这里毒e ( 1 2 ，1 ) ，p ( o ，1 ) ，r 是路径 r 盘= 砟，础，d ) ， 这里磋k 坼十j r j - 坳( k ) ( 2 ) 如果上面条件( 1 7 ) ，( 1 8 ) 不满足，选择a 0 使得 毋+ a i 的最小特征值 ( 1 9 ) 这里 0 是一个常数如果对于一个常数m ，0 色忙m ，那么一定存在一个常数 m 2 0 使得 0 反+ a ，0 m 2 v 七( 1 1 0 ) 这时r ( ) 是路径 r 艺：= h ，x 譬，d ) 第一章绪论 1 = x k + s 竽，s 箩= 一( b + a ，) g 。 算法1 2 不定折线算法 s t e p l 给出和信赖域半径h 。，计算颤和色 s t e p 2 判断最是否正定，如果色正定转s t e p 3 ；否则转s t e p 5 s t e p 3 计算c 尸点、牛顿点和近似牛顿点： = 一c t 女g 女，) - 一所1 9 i ，i n 似p ) _ ( o 8 b + o 2 ，) s 印t * b = g ；g 。) 2 g ；玩g 。k ；b f l g 。) ，a 。 s t e p 4 计算子问题( 1 2 ) 的解： ( 1 ) 若- 1 1 j 圳，则 ( 2 ) 刮s 圳 吃雕i l ，则 其中7 7 的取值使得慨l l = h k ( 3 ) 若滞0 玩，则 其中7 7 的取值使得慨0 = 玩 & 2 h k - 恻g k s k = s 譬+ d ， s = s 鬻+ r d s t e p 7 计算s 爹= 一( 最+ a ，) g i ( 1 ) 若仇- l l s 圳，则 如果蚓l 魂，则 2 h k - g k f 吼= s 譬+ d & = 5 竽+ r i d 其中叩的取值使得恢0 = h k 不定折线法具有以下性质【9 】： 当点x 从点x 。出发，沿不定折线移动时， ( 1 ) 点x 到点x 。的距离单调增加； ( 2 ) 二次模型g ( j ) 的值单调下降 1 0 第一章绪论 1 。4 本文测试函数 本文数值试验用到的7 个标准测试函数如下： n 1 - - c o n i cf u n c t i o n 厂( x ) = ( 彳+ ) ( 1 一_ ) 2 n 2 一c u b ef u n c ti o n 厂( x ) = 1 0 0 ( x 2 一# ) 2 + ( 1 - x 1 ) 2 n 3 wr o s e n b r o c kf u n c t i o n 厂( x ) = 1 0 0 ( x 2 一彳) 2 + ( 1 一x 1 ) 2 n 4 一p o w e l1b a d l ys c a l e df u n c t i o n 厂( x ) = ( 1 0 0 x i x 2 1 ) 2 + ( 一。1 + 口一毛- 1 。o 0 0 1 ) 2 n 5 wb e a lf u n c t i o n m = 1 5 ，坎= 2 2 5 ，y 3 = 2 6 2 5 厂( x ) = ( y 1 一x l ( 1 一x 2 ) ) 2 + ( 歹2 - x i ( 1 - x 2 ) ) 2 + ( 儿一( 1 一霉) ) 2 n 6 一p e n a lt y if u n c ti o n 口矿= 1 0 巧 厂( x ) = 口矿( 五一1 ) 2 + a r ( x 2 1 ) 2 + ( 彳+ 托2 0 2 5 ) 2 n 7 - 一f r e u d e n s t e i n r o t hf u n c t i o n 厂( x ) = ( - 1 3 + 五+ ( ( 5 - x 2 ) x 2 - 2 ) x 2 ) 2 + ( - 2 9 + x l + ( ( 毛+ 1 ) x 2 - 1 4 ) x 2 ) 2 1 。5 本文要做的工作 本文将对求解信赖域子问题的混合折线法和不定折线法进行研究第二章及第 三章与第四章分别对混合折线法和不定折线法进行了研究 传统的信赖域方法当试探步不被接受时，往往需要重解信赖域子问题，这就增 加了问题的计算量，为了避免这个缺点，袁亚湘和n o c e d a l j 给出了结合a r m i j o 线 搜索的信赖域方法由于信赖域半径的大小会影响算法的效率，却没有一般的规则来 指导在算法中如何调节信赖域半径的大小李改弟口7 1 充分利用了目标函数在当前迭 代点的梯度和h e s s i a n 矩阵的信息，提出的一个自动确定信赖域半径的方法鉴于这 两种思想，本文将线搜索和自动确定信赖域半径的方法引入到混合折线法中构造了 种带线搜索的自动确定信赖域半径的混合折线信赖域算法，这也就是本文第二章 的要做的工作 求解信赖域子问题的折线算法研究 传统的信赖域算法要求产生的点列的目标函数值是单调下降的，这样当目标函 数在可行域中存在细长弯曲的峡谷时，单调算法就会很大程度地失去它的计算效 率，基于这种情形，l g r i p p o 等提出了一个非单调线搜索算法，此后，许多学者将 非单调算法引入到信赖域算法中，都得到了不错的计算效果所以本文的第三章在第 二章提出算法的基础上引入了非单调技术，构造了一种非单调自适应的混合折线信 赖域算法 本文第四章构造了一种自适应非单调的不定折线信赖域算法张建中、徐成贤 等提出的不定折线法在鼠不正定时，运用b u n c h p a r l e t t 分解产生搜索路径来确 定下降方向，避免了由于最修正而造成的信赖域子问题逼近原问题效果不佳的缺 点h e il o n g 心刚构造了一个尺。( 吒) 函数，根据实际下降量与预估计下降量的比值按 照变化的速率对信赖域半径进行调整，使信赖域半径的调节取决于问题本身，更具 客观性受这些文章的启发，本文将非单调算法也引入到自适应不定折线信赖域算 法中，并且进行了初步的数值试验，对某些测试函数，该算法比第二章及第三章中 提出的算法有更好的数值结果 1 2 第二章一种带有线搜索的白适应1 卜单调混合折线信赖域算法 第二章一种带有线搜索的自适应混合折线信赖域算法 本章将求解信赖域子问题的混合折线法与自动确定信赖域半径的方法相结合， 并且在试探步不可接受时，采用线搜索来计算下一个迭代点，提出了求解无约束优 化问题的一种带有线搜索的自动调节信赖域半径的混合折线信赖域算法在通常条 件下，证明了算法的全局收敛性，数值结果验证了新方法的有效性 2 1 引言 考虑无约束优化问题 m i n 厂( x ) ，x r ” ( 2 1 ) 其中厂：r ”专r 二次连续可微 当吃变化时，s 的解形成一条空间曲线，称为最优曲线在信赖域内沿着从x 。出 发的曲线近似求解信赖域子问题是一个非常吸引人的思想张立将p o w e l l 提出的单 折线、d e n n i s 的双折线法和赵良英、徐成贤的切线单折线法结合起来，给出了求解 ( 1 2 ) 的混合折线法，张立在计算机上进行了二次规划子问题和优化的标准测试函 数两种类型的数值试验，数据表明，混合折线法优于单折线法。 传统的信赖域算法实现过程中，信赖域半径的选取是一个关键因素，它直接决 定着当前迭代的方向和步长。然而传统的信赖域方法信赖域半径的更新是根据比值 吒人为规定的按常数倍放大或缩小，基于此，许多关于信赖域半径的自适应算法被 提出 3 3 、 3 5 s a r t e n e a r t 3 0 1 给出了个能自动决定信赖域半径的算法，即信赖域半径具有自 适应性，能够根据迭代中产生的信息作自我修正，其基本思想是通过近似模型( 1 2 ) 和目标函数f ( x 。+ s ) 沿负梯度方向的近似程度，调节初始信赖域半径f a n 与 y u a n l 3 1 1 提出信赖域半径收敛到零的算法，其信赖域半径是关于目标函数梯度的0 0 函数章祥荪、张菊亮【3 2 】等人又对这一算法进行了改进，每次迭代信赖域半径 h 。= c p l 忙训恬。0 ，这里f ( 0 ，1 ) ，p 是非负整数如果上次迭代，试探步s 被接受， 则p = 0 ，否则p = p + 1 该算法的优点是如果p = 0 ，n e w t o n 步或拟n e w t o n 步总是 可行的，保证了超线性收敛性缺点是每开始一个新的迭代( g 。，玩被更新的迭代) ， 信赖域半径总是置于充分大，与无关，增加了盲目尝试性，即“很可能很小，但 h 。仍然充分大此外，每开始一个新的迭代，都要计算0 所10 才能确定玩于是李改 1 3 求解信赖域子问题的折线算法研究 弟【2 7 】提出一个自适应的信赖域方法，每次迭代都充分利用当前迭代点包含的二次信 息自动产生一个信赖域半径，所用的计算信赖域半径的策略没有增加额外的计算量 比值眇。s 。0 包含目标函数的二次信息，这里y 川= g 。- g ，= 一吒_ 1 文 2 7 z 2 h k = 0 k 一。| i i | 儿一。l l 】i g 。l l ，再根据比值气的大小，调节，数值结果验证了新方 法的有效性 本章借鉴文献 1 1 和 2 7 的思路，将文献 2 7 提出的自适应技术引入文献 1 1 为了提高信赖域算法的有效性，将新算法与线搜索技术相结合，在试探步不可接受 时，采用线搜索来计算下一个迭代点，使得每一次迭代只计算一次信赖域子问题， 从而提出了一种带线搜索的自动确定信赖域半径的信赖域算法，提高了算法的效率 在通常条件下，证明了算法的全局收敛性，数值试验结果验证了新方法是有效的 2 2 算法 在本章中用到的线搜索是彳删和型线性搜索：给定吼( o ，1 ) ，取a 。 0 ，使 得 f ( x k + o r t s i ) f ( x k ) + c r l a t g t t s t 如果试探步不被接受，则采用a r m i j o 型线性搜索来确定一个步长，避免重新计 算信赖域子问题 下面给出本章的算法： 算法2 1 s t e p l 给定灭”，磊r “”对称，6 ( o ，1 2 ) ，允( o ，1 ) ，s 0 ，h 。= l l g 。8 ， 1 c 2 c o o ，c 6 = 0 ，k ：= 0 s t e p 2 如果恬。忙s ，贝, u f q ，否则利用算法1 1 求信赖域子问题( 1 2 ) l 懈s 。 s t e p 3 计算 = a r e d i p r e d i 如果 c o ，更新h + l = 砟+ s t ，否则解f 使得 f ( x t + 兄s ) f ( x 女) + 觐g t j ( 2 2 ) 4 - a i = a ， s 2 口女是，z t + l2 x 女+ s i s t e p 4 如果 气，c 。= i l s k0 y 。0 ，这里几= g 川- g 。否则c 。= c 。4 更新 1 4 第二章一种带有线搜索的白适应1 = 单调混合折线信赖域算法 h ：如果。c ：，h = m a x c 。g 川，4 1 ) 否则+ 。= 气恢+ l | i s t e p 5 修正反+ l ，k ：= k + l ；转s t e p 2 对于b k + l 的修正，若初始h e s s i a n 阵正定，则取b l 为初始h e s s i a n 阵，否则置 p = 4 卢，直到b 。+ 肛正定为止 b 女) 由b f g s 公式修正，即 咄+ 篝u t 一鬻y k s k u j sk s k 这里 f y i 如果s k t 少女 o ； 儿- g g ”2 1 几+ 0 h i如果s ；y k ：o 【几十u l s i 则禾 2u 此外，当t 儿 m ，使得 l i v v ( x l l - - ，v x 上( x 。) ( 2 3 ) 为了方便起见，现在定义两个集合如下： ，= k ：c o ) 和j = k ： 国k 刀 由于连续可微，两边同时取极限f 0 0 ，1 z 哥士u t 唧 3 9 r s i 由于6 ( o ，1 2 ) ，故有g ； 0 ，由引理2 1 ，& 满足( 2 5 ) 显然有j ；既 f ( x i ) + 飘一1 口女g t j i ( 2 7 ) 由t a y l o r 展开有 f ( x i + 扩1 口s t ) = f ( x t ) + a - 1 a 女g t s i + 1 2a _ 2 a 1 2 s 女t v 2 厂( 考) s t ( 2 8 ) 其中考( 坼，x + 允- 1 a s ) ，由( 2 3 ) ，( 2 7 ) ，( 2 8 ) 有 - - ( 1 - 3 ) g s 。 c o ( q ( o ) 一九& ) ) 圳g t i i m i n 叫州呻 如果k j ，则 f ( x , + a k s k ) 厂( x 。) 一6 a 。0 9 。0 m i n h , , 0 9 。i i 0 b 。肛 第二章一种带有线搜索的白适应非单调混合折线信赖域算法 s ( x 。) 一( 1 - _ 云6 函) 6 2 一, m0 9 。0 m i n 办。，0 9 。0 0 b 。忪 定义少= m i n c o 2 ，( 1 - s ) , s a , m 2 m ) ，则有 + 。以一y i i g 。i m i n h 。，l i g 。l ib 。忪， ( 2 11 ) 故有序列 六) 是单调非增的证毕 这里我们定义一个序列，m t = l + m 。郇a x l b , i f ，对v 后 定理2 5 如果假设2 1 ，2 2 成立，并且 毋) 满足1 m 。= o o ，则由算法2 1 产生的序列 坼) i i 蔫足 ! i m 。i n f 慨gi = o ( 2 1 2 ) 证明假设( 2 1 2 ) 不成立，即存在s 使得恬。忙s ，v k 由( 2 1 1 ) 式有 以+ l 六一炉m i n h k ，s m 女) 一炉m i n h ，s 4 m ) ( 2 1 3 ) 由算法2 1 的第3 步有 k ，端恬川忙糕彘 对v k ，有h k ，所以由( 2 1 3 ) 得 4 m 。 f k f k “2 ve , 2 | 4 mk ， 由引理2 4 及假设2 1 有 因此有1 m 。 一 、，+ 一 以，- 。心 求解信赖域子问题的折线算法研究 较，本文还将文献 2 7 提出的自适应技术引入文献 1 1 构造的自适应混合折线算法 作了初步的数值试验，也对其与算法2 1 作了比较，我们根据7 个标准测试函数来 说明算法的有效性，算法的数值结果分别由表2 1 ，表2 2 ，表2 3 给出，其中“一” 表示迭代次数超过3 0 0 0 次但算法仍没有找到解通过不同的参数测试，列出了数值 结果较好的参数如下： c 0 2 0 i ：c 2 2 0