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

一j 摘要 摘要 j i i ii i ir i l li ii l lii iipiif 17 8 9 3 8 8 对于无约束优化问题，信赖域算法是一类重要的数值计算方法，传统的信赖域算法 采用二次模型逼近目标函数然而，对于非二次性念强、曲率变化比较剧烈的函数，用 锥函数逼近目标函数的效果相对较好，进而锥模型信赖域算法引起了研究者们的普遍关 注，特别是在2 0 0 5 年新锥模型信赖域算法的提出和研究，突破了传统锥模型信赖域算 法只在平面一侧求解函数最优值的局限 本文主要研究新锥模型信赖域算法框架本身的构造与改进，共分五章，第一章简 单介绍了信赖域算法的基本思想及研究现状第二章主要介绍了锥模型信赖域算法的理 论基础，给出求解新锥模型信赖域子问题的算法第三、四及第五章是本文的核心所 在其中第三章是在用折线法求解新锥模型信赖域算法子问题的基础上，提出了一种结 合线搜索的新锥模型信赖域算法( 加入了非单调技术和自适应技术) ，将新算法与传统锥 模型信赖域算法的数值结果进行比较，并给出了新算法的全局收敛性证明第四章结合 过滤技术，提出了一类带过滤技术的新锥模型信赖域算法，并对两个经典的大规模测试 函数进行检验，得到了理想的数值结果第五章提出了一种混合算法，将过滤技术与线 搜索结合提出了一种多重过滤线搜索新锥模型信赖域算法，证明了新算法的全局收敛 性，得到了较好的数值结果 关键词：新锥模型；信赖域算法；非单调技术；自适应技术；过滤技术；线搜索 新锥模型信赖域算法研究 a b s t r a c t a b s t r a c t f o rt h eu 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 ，t h et r u s tr e g i o na l g o r i t h mi s a ni m p r o t a n tc l a s so fn u m e r i c a lc a l c u l a t i o nm e t h o d ，a n dt h et r a d i t i o n a lt r u s t r e g i o nm e t h o df o rs o l v i n gt h i sp r o b l e m i sb a s e do nq u a d r a t i cm o d e l s h o w e v e r , f o rs t r o n g l yn o n q u a d r a t i cf o r ma n dm o r ed r a m a t i cc h a n g eo fc u r v a t u r ef u n c t i o n ， t h ec o n i cf u n c t i o nw i t ha p p r o x i m a t i o no ft h er e l a t i v ee f f e c to ft h eo b je c t i v e f u n c t i o ni sb e t t e r s ot h et r u s tr e g i o nm e t h o do fc o n i cm o d e la t t r a c t e dw i d e a t t e n t i o nf r o mr e s e a r c h e r s e s p e c i a l l y , t h en e wt r u s tr e g i o na l g o r i t h mo fc o n i c m o d e li sp r o p o s e da n ds t u d i e di n2 0 0 5 ，i tb r o k e nt h r o u g ht h el i m i t a t i o n so f t r a d i t i o n a lc o n i cm 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 eo p t i m a lv a l u eo n l y o n es i d eo ft h eh y p e r p l a n e t h i sa r t i c l e m a i n l y s t u d i e st h e a l g o r i t h m f r a m e ss t r u c t u r ea n d i m p r o v e m e n t i ti sd i v i d e di n t of i v ec h a p t e r s i nt h ef i r s tc h a p t e r , t h eb a s i ci d e a a n dr e s e a r c ho ft h et r a d i t i o n a lt r u s tr e g i o na l g o r i t h mi si n t r o d u c e d i nt h es e c o n d c h a p t e r , t h et h e o r e t i c a lb a s i so ft h ec o n i cm o d e lt r u s tr e g i o na l g o r i t h mi s i n t r o d u c e d ，a n dt h en e wc o n i cm 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 e s u b - p r o b l e mi sa n a l y s i s e d t h et h i r d f o r t ha n df i f t hc h a p t e r a r et h ec o r eo ft h i s a r t i c l e i nt h et h i r dc h a p t e r , an o n m o n o t o n es e l f - a d a p t i v et r u s tr e g i o na l g o r i t h m w i t hl i n es e a r c hb a s e do nt h en e wc o n i cm o d e li s p r o p o s e d a n dt h e s u b p r o b l e m sa r es l o v e db yt h ed o g l e gm e t h o d t h et h en u m e r i c a l r e s u l t so ft h e n e wc o n i cm o d e la r eb e t t e rt h a nt h et r a d i t i o n a lt r u s tr e g i o na l g o r i t h m g l o b a l c o n v e r g e n c ei sp r o v e du n d e rc e r t a i nc o n d i t i o n s i nt h ef o 砒c h a p t e r , af i l t e r s e l f - a d a p t i v et r u s tr e g i o na l g o r i t h mo ft h en e w c o n i cm o d e li sp r o p o s e d t h e t w oc l a s s i cl a r g e s c a l et e s tf u n c t i o n sa r et e s t e d ，a n dg e ts o m eg o o dn u m e r i c a l r e s u l t s i nt h ef i f t hc h a p t e r , am u l t i d i m e n s i o n a ll i n es e a t c hf i l t e rt r u s tr e g i o n a l g o r i t h mo ft h en e wc o n i cm o d e li sp r o p o s e d t h i sm a ya l l o wac o n s i d e r a b l e c o m p u t a t i o n a ls a v i n g ，a n dt 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 mi sg i v e n u n d e rc e r t a i nc o n d i t i o n s 儿j 新锥模型信赖域算法研究 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 e t e c h n i q u e s ；a d a p t i v et e c h n i q u e s ；f i l t e rt e c h n i q u e s ；l i n es e a r c h i v 目录 目录 第1 章绪论1 1 1 传统信赖域算法l 1 2 锥模型信赖域算法2 1 2 1 锥函数2 1 2 2 传统锥模型信赖域算法3 1 2 3 新锥模型信赖域算法4 1 3 本文的主要工作内容5 第2 章新锥模型信赖域子问题的性质及求解。7 2 1 新锥模型信赖域子问题的性质7 2 2 子问题的最优性条件1 1 2 3 求解子问题的折线法1 2 2 4 几种经典测试函数1 5 第3 章一种带线搜索的新锥模型信赖域算法2 1 3 1 引言2 1 3 2 算法2 l 3 3 算法的收敛性2 2 3 4 数值试验2 6 第4 章一种带过滤技术的新锥模型信赖域算法2 9 4 1 引。言2 9 4 2 算法2 9 4 3 算法的收敛性3 l 4 4 数值试验3 3 第5 章一种基于新锥模型的多重过滤线搜索的信赖域算法3 7 5 。l 引言3 7 5 2 算法3 7 5 3 算法的收敛性3 8 5 4 数值试验3 9 结论4 3 参考文献4 5 致谢4 9 v 新锥模型信赖域算法研究 硕士期间发表的学术论文目录5 1 v i 第l 章绪论 第l 章绪论 信赖域方法的研究起始于p o w e l l l l l ，是非线性优化的一类重要的数值计算方法，因 该方法有很好的稳定性和很强的收敛性，所以自2 0 世纪七十年代以来一直受到优化界 的重视，是非线性优化的研究热点，目前信赖域方法已经和传统的线搜索方法并列为非 线性规划的两类主要数值方法人们发现信赖域方法的基本技巧在一定意义下等价于十 分著名的求解非线性最小二乘的l e v e n b e r g - - m a r q u a d t 方法，所以人们提及信赖域方法 的历史总是追溯到l e v e n b e r g - m a r q u a d t 方法 1 1 传统信赖域算法 传统的信赖域算法采用二次模型来逼近原问题，目前理论和算法都已经相对成 熟求解光滑无约束和约束优化问题的信赖域算法参见文献 1 】，【2 】，【3 】，【6 】，求解非 光滑优化问题的信赖域方法参见文献【1 9 】一 2 0 】 信赖域方法的基本思想是构造并求解信赖域子问题，即在当前迭代点处，构造近似 于原问题的逼近模型，然后在信赖域内求解试探步信赖域算法的构造和逼近是密切相 关的，在当自订迭代点以处，构造一个近似于原问题的逼近模型，如果模型在当前迭代点 较好地逼近原问题，则信赖域半径可扩大，否则信赖域半径应缩小 针对无约束优化问题 m 。i 。n 。f ( x ) ( 1 1 ) j e “ 其中厂：r ”一r 为连续可微函数 传统的信赖域算法采用二次逼近，构造的子问题如下： m 。i n 痧k ( d ) = 五+ 反t d + z 2 d 7 1 最j ( 1 2 ) s d i i d l - 0 是 信赖域半径设以是信赖域子问题( 1 2 ) - ( 1 3 ) 的解，称目标函数( x ) 在第k 步的实际下 降量 a r e d k = 五- f ( x k + 矾) ( 1 4 ) 为真实下降量，称二次模型函数丸p ) 的下降量 p r e d k = 唬( o ) 一吮( 矾) ( 1 5 ) 为预估下降量定义比值 1 新锥模型信赖域算法研究 a r e d 。， , o k2 百茄 它衡量了二次模型唬( d ) 与目标函数厂( + d ) 的逼近程度 下面给出求解无约束优化问题( 1 1 ) 的传统信赖域算法： 算法1 1 s t e p l 给出x o r ”，b o 尺”。”，a o o ，s 0 ，朋o ，0 鸬 1 ， k = 0 ： ( 1 6 ) 0 届 屈 1 l 或配d l ，由于d = o 在锥函数定义域中，一般情况下 都限制d 的取值范围为硭d 1 从锥函数的表示形式中可以看到，当b k = 0 时，锥函数化为二次函数，因此锥函数 是二次函数的推广，有更多参数选择的自由度 1 2 2 传统锥模型信赖域算法 根据锥函数的定义，构造锥函数需要确定参数g k ，吮，反，其中g 。是处的梯度值， 所以锥模型信赖域子问题的构造实质上就是确定仇，反，确定皖，最的方法有多种，主要 研究的有三种：共线调比拟牛顿法、拟牛顿法和直线搜索法共线调比拟牛顿法利用共 线调比推导出了广义拟牛顿方程，利用广义拟牛顿方程来确定玩，反，其详细构造方法 参见文献【2 2 】- 【2 6 ；拟牛顿法是将基于二次模型的标准拟牛顿法应用到锥模型中来确定 玩，玩，参见文献 2 7 】- 3 2 】；直接搜索法4 5 1 利用了目标函数值插值来构造锥模型 文献 2 7 】一 3 2 1 用拟牛顿法确定，反，提出了多种阮的构造方法下面给出钆的几 种表达式： 令以一，= l + 雏以- p 畋一。= 砟一稚1 ，反一。为黾一。处梯度值，则玩的表达式有： 玩= 紫趾。 仇= f 1 一l + f 2 ，l ，乞为待定系数 钆屯r t ) 卜丽g k - i + ( 1 叫焘 舢酬 3 新锥模型信赖域算法研究 玩= ( 1 一以州( 以麓y k - l g 纽一g - ：，g ) k 瓦 仇= 碡( 万1 - 谰y ：) g k 玩= 蹬屯 忙一+ 端t 一+ 3 t “ 虹掣；一一虎鼬 驴磊磊一 1 9 9 6 年，d i 和s u n 在文献 2 2 】中提出了如下锥模型信赖域子问题： 卜确) = 崭+ 互1 器 ( 1 1 2 ) k i l a l l - a 。且酲d 0 ，将新可行集分为三种情形，得到三种不同类型的锥模型信赖域子问题，并 对每一种情形下的锥模型信赖域子问题的求解给出了最优性的充分和必要条件，为进一 步研究锥模型子问题的有效方法提供了合理的基础提出的新锥模型信赖域子问题为： 卜州，= 尚毛尚 【豇 d q 其中q = b n s ，b = d r ”i d l l - - o ，岛为一个在。到l 之间 的一个正数在文献 3 9 】中将上述子问题的可行域重新分类得到的三种不同的锥模型信 第1 章绪论 赖域子问题如下： ( p 1 ) ：当1 - 8 0 a 。慨0 时，子问题转换为： m i n o k ( d ) 豇l i d i _ a 。 ( 1 1 5 ) ( p 2 ) ： 当| 1 一色慨 0 ，则“和原点d 位于超平面l b 7 d = 0 的同侧； 若1 一b ，b 。1 9 0 ，g 0 ( 1 ) 若g 7 船g g r g o 且6 7 f g 0 ，则函数肌( _ 曙) 在o f 1 = l i 上严格单调递增，在r ：l j 二* 上达到 g lb g b ig g lgg ib g b lg g lg 最小值 ( 2 ) 材船。矿g 0 助 志删馓肌在 新锥模型信赖域算法研究 巍一诸上严格单调递增，同时函数聊在砭罱和 0 r 0 ，则锥函数在线段 d ( ，) = 以，+ ，( d 一以p ) ， o t l 上沿，增加方向为非增函数 ( i i ) 若1 一b b 。1 9 o ，五= 譬，= 一旯g ，历( 五) = 妒( 一2 9 ) 。b g 得到 令 ( 2 4 ) ( 2 5 ) v n - - - = 1 - b r 九= 高，= l - b y 略= 警 ( 2 6 ) 。堕q 盟m 麓赢 d 砧 第2 章堑堡垡型笪整垫塑墼丝竺里墨查坚 一 同时令 得 孑( f ) = 如+ f ( “一略) = 砜+ ( 1 一f ) ( ，印 ；：l + b 7 - d ( t ) = t v n + ( 卜，) 屹 定义函数办( ，) = 缈( 否( f ) ) ，则由( 2 4 ) ，( 2 6 ) 和( 2 8 ) 得 j l z ( ，) = 专( 巩一) 7 ( 讨一6 万) ( 珐+ 丽) 由n e w t o n 点满足v 妒( 氐) = o 得 ( 2 7 ) ( 2 8 ) ( 2 9 ) v n g + b d = o ( 2 l o ) 由( 2 5 ) 知历。( ) = o ，再由定义可以得到历( ) = 一9 7 v 缈( 略) = 0 ，得 即可得 g r ( y ，+ 6 嘭) ( g + 6 ) = o 略7 1 ( y ，+ 6 ) ( g + 6 略) = o 由d = 一了二，d 。p = - 2 * g 和( 2 6 ) 式得 和 ( 2 1 1 ) 咖峥篇，v c p i + b = 学 仁 v c p g + 醐c n = 将( 2 7 ) ( 2 8 ) 代入( 2 9 ) 式并考虑( 2 1o ) 可得 g r b g g b 9 9 7 g c b g ( 2 1 3 ) 向( r ) ：去( 九一略) 7 ( ；，一6 万7 ) ( 珐+ 口万) ：当( d 二一) 7 卜( v ，+ 6 d _ j ：) + ( 1 一，) ( v 叩，+ 6 ) r ( v g + 砜) + ( 1 一州g 十b 略) 1 ， 1 - - 3 1 ， “一如) 7 ，( v ，+ 6 d ：) 十( 1 一，) ( ，+ 6 ) ( 1 一叭g + b d p ) 由( 2 1 1 ) 式得( 1 一，) 2 略。，( y ，+ 6 ) ( g + 6 略) = 0 ，将此结果与( 2 1 2 ) 。( 2 1 3 ) 代入上式得 9 新锥模型信赖域算法研究 却h 肌训7 唑等掣 + ( 1 _ z 丛颦掣盟l 将“= 一i 摄- 1 ，d , p = - 2 * g 代入上面的式子得到 由( 2 6 ) , 1 1 ( 2 8 ) 得 - - 1 ，31 一b 7 b1 9 ) + ( 1 一f ) 2 厅。) = 型瓮一 i + i l - ，l ( 2 1 4 ) 下面分两种情况考虑： ( i ) 若1 一b 7 b 一g o ，由已知条件b o ，c o g o ，0 r l 及( 2 6 ) 式知 0 ， 0 ， 由柯西不等式知g r b g g7 b 。1 9 - g r g g7 g 0 ，故由( 2 1 4 ) 矢hh ( ，) 0 ，即乃( ，) 为0 0 ，f 1 及( 2 6 ) 式知 o ，v o ，故由( 2 1 4 ) 矢hh ( ，) 0 ，即向( f ) 为f 1 时沿减小方向为非增函数证毕 定理2 5 4 0 1 设若b 为正定对称矩阵，g 0 ，一= 一r g 为1 h i 题( 1 1 4 ) 的最速下降点， 则r + 的表达式为： 1 0 嗄 8 门u 斛 r + 材 移 + 心 引 j + 、 【 )2 一 ， 卜 一 r 1 l + 一 =v = “：， 门川1 b 一 堕啦 兰协纠一一 0一二， 船一 矿一 型嘏业兰协竺 叫| | 谵一 0一“二，一 誊 第2 章新锥模型信赖域子问题的性质及求解 _ 二一 f r ( )c ( 姆) 0 ( 1 ) 削喝 o 叫m 精f 2 m i n ，) o ( 2 ) 当l l - a i i b l l l o 卟，老，商 b r g 0 ( 3 ) 当a l i b l i - l + c 。时，f 的定义同( 2 ) 中的定义 2 2 子问题的最优性条件 本节给1 t i 新锥模型信赖域子问题的最优性条件 定理2 6 t 3 明设氏( 0 ，1 ) ，a 0 ，b 尺”满足刽圳 l - g 。，则d 。是子问题( p 1 ) 的解 当且仅当存在z 0 ，有 f b 一驴7 + 五+ ，) d + = 一g + 2 + a 2 b ( 2 1 5 ) 。力+ ( 1 i d + l i 一) = o ，l i c l ( 2 1 6 ) _ rb + z o 一2 的，) 是半正定矩阵，若b + 名o 一2 6 6 7 ) j 下定，则是( p 1 ) 的唯一解 定理2 7 设一占。 0 ，d + 为( 1 1 4 ) 的解若存在l a g r a n g e 乘子彳使得 1 6 r 【b + 石j ) g 0 ，则有 d=一(b+彳，)一i三量兰圣三孑芋铲g+(正氏一彳2)6l ( 2 2 5 ) 2 3 求解子问题的折线法 2 1 节中的性质定理及2 2 节中子问题的最优性条件为折线法的求解提供了理论依 据，根据，氏和a 的关系，( 1 1 4 ) 式总能转化为子问题( 尸1 ) ( 尸2 ) ( 尸3 ) 之一下面给出 求解三种精确子问题的算法【4 0 l ： 子算法1 ( 解子问题( 尸1 ) ) s t e p l 计算式= - b 一1 9 ( 1 - b 7 b 。1 9 ) ； s t e p 2 如果| l 九1 1 - 0 时，取，+ = ，l ；当1 - b7 b 一1 9 0 时，f = ，2 其中 f l =一c + x 肛c 2 - a d ，t ，2一c x 肛c z - a d 。 口口 d = 忱| | 2 - 2 ，o ，。 ，则d = 矾，其中f 满足l + r b 7 g = 氏停止； s t e p 6 如果l i 略l i ，令d = d ( ，) = ，d + ( 1 一n 略，其中，+ 满足 ) l l = _ = d = 1 2 一2 ， 一c + x c 2 - a d ，t 12 0 t l l ，t 2 o 时，若d ( f 1 ) q ，以= d ( ) ，否则计算噍= 乞九+ ( 1 一乞) ， 其中0 ，岛 1 使得1 一b 7 。噍= 毛成立，若氏q ，则d + = 噍，停止；否则d + = 反； s t e p 8 当l b 7 b g o 时，耿f = f 2 ；d = 8 略1 1 2 一2 ，0 t 1 1 ，2 0 子算法3 ( 解子问题( p 3 ) ) 步1 7 同子算法2 的步1 7 ； s t e p 8 当1 - b r b g 0 时，计算，一，使得l b7 ( t _ d u + ( 1 一，- ) ) = 一e o 成立，如果 0 t ， 0 ， 0 r l r 2 l ，0 7 l 1 y 2 ，k = 0 ； s t e p l 如果恬女忙s ，则停止；否则转s t e p 2 ： s t e p 2 求解新锥模型信赖域子问题： 当1 一g 。俐时，调用子算法l ；当 i - abi 时，调用子算法2 ；当a l b l - - - l + c o 时，调用子算法3 转s t e p 2 ； s t e p 3 计算n = 粤p r e c l k = 错t a k ，进行试探步可接受性掀 一9 k) s t e p 4 修正坑+ l ，b k + l ，置尼= k + l ，转s t e p l 注：本文中b + ，魄+ 。的构造采用锥模型拟牛顿法2 7 1 ，形式如下： ( 2 2 6 ) = 壤+ 糍一觜 ，= 饼，此t 鼬巩亿2 7 ， 儿+。=鳟u+。=(五一五+)2一(或反)(盛。以) ( 2 2 8 ) 定理2 1 3 1 4 0 】令巩是算法2 1 产生的解，则有 嘲c 咖扣l m t n 南，黼，肃) 亿2 9 ， 1 4 第2 章新锥模型信赖域子问题的性质及求解 2 4 几种经典测试函数 在本节中，给出几种经典的测试函数及有代表性的三维空间中的八个函数图像在 无约束优化问题中，针对不同的具体问题，算法的设计也不同，测试函数用以检验新算 法的可行性及收敛效果 ( 1 ) c o n i cf u n c t i o n ： 厂g ) = ( x ? + x ；) ( 1 一x ，) 2 ( 2 ) b e a lf u n c t i o n ： y l = 1 5 ；y 2 = 2 2 5 ；y 3 = 2 6 2 5 g ) = ( y l x i ( 1 一x 2 ) ) 2 + ( j ，2 一而( 1 一x ；) ) 2 + ( y 3 一一( 1 一x ；) ) 2 ( 3 ) p e n a l t y if u n c t i o n ： 厂g ) = a ( x l 一1 ) 2 + 口( x 2 1 ) 2 + ( x ? + x ；一o 2 5 ) 2 ( 口= 1 0 - 5 ) ( 4 ) p o w e l lb a d l ys c a l e df u n c t i o n ： 厂g ) = ( 1 0 4 x l x 2 1 ) + ( p 一1 + p 一“一1 0 0 0 1 ) 2 ( 5 ) r o s e n b r o c kf u n c t i o n g ) = 1 0 0 ( x ：一x ? ) 2 + ( 1 一而) 2 ( 6 ) 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 + x i + ( ( 5 一x 2 ) x 2 2 ) x 2 ) 2 + ( - 2 9 + x l + ( ( x 2 + 1 ) x 2 - 1 4 ) x 2 ) 2 ( 7 ) c u b ef u n c t i o n ： 厂g ) = 1 0 0 ( x ：一x ? ) 2 + ( 1 一x 。) 2 ( 8 ) b r o w nb a d l ys c a l e df u n c t i o n ： 厂( x ) = ( ) f l 一1 0 6 ) 2 + ( ( z 2 2 x l o 一6 ) - ( x l x 2 2 ) ) 2 在本文以后章节中，为了验证新算法的有效性，用到如下多维测试函数： ( 9 ) e x t e n d e dr o s e n b r o c kf u n c t i o n ： ( x ) = 喜 。( 一+ - 一# ) 2 + ( t 一薯) 2 ( 10 ) e x t e n d e dp o w e l ls i n g u l a rf u n c t i o n ： n - i i - i 厂( x ) = l ( 一+ l o x ，+ ) 2 + 5 ( 誓+ ：一x i + 3 ) 2 + ( 誓+ 。一2 薯+ ：) 4 + 1 0 ( 一一t + ，) 4i 下面给出三维空间中的八个函数图像： 1 5 新锥模型信赖域算法研究 图2 1c o i n c 函数 f i g u r e2 1c o n i cf u n c t i o n1 图2 2b e a l e 函数 f i g u r e2 2b e a l e cf u n c t i o n 1 6 。摹移“? 一rj 。：一；。尹： p o w e l ! b a d l ys c a j a d , f u n c t i o n = 蛾一? j ：? j 嫩j 图2 4p o w e l lb a d l ys c a l e d 函数 f i g u r e2 4p o w e l lb a d l ys c a l e df u n c t i o n 1 7 新锥模型信赖域算法研究 图2 5r o s e n b r o c k 函数 f i g u r e2 5r o s e n b r o c kf u n c t i o n f i g u r e2 6f r e u d e n s t e i na n dr o t hf u n c t i o n 1 8 第2 章新锥模型信赖域子问题的性质及求解 c u b ef u n c t i o n 图2 7 c u b e 函数 f i g u r e2 7c u b ef u n c t i o n 譬霹恶蕊冀雾曩静j 繇= f ，i j _ v ” 。1 ? b r o w nb a d l ys c a r e d 触簿踟彩 ；7 i 并lj7 靖。? ：善：= ：= 。：嚣一：”：茹 7 ，0 0 f i 。”i 。l “”弦? 。魄 -+ i f 蒡 每毒 麓 图2 8b r o w nb a d l ys c a l e d 函数 f i g u r e2 8b r o w nb a d l ys c a l e df u n c t i o n 1 9 膨惕修。o囊嚆m镌秀一秀。鬈“赫珊瑚躞麓掰弼：。穗嘴翟，；。，嚆!：一l， 新锥模型信赖域算法研究 2 0 第3 章一类带线搜索的新锥模型信赖域算法 第3 章一种带线搜索的新锥模型信赖域算法 本章提出了一种求解无约束优化问题的基于新锥模型的带线搜索的非单调自适应 信赖域算法，并在适当的条件下，证明了该算法具有全局收敛性信赖域半径的修正采 用自适应技术，充分利用了当前迭代点处的梯度信息算法在试探步不被接受时，采用 线搜索寻找下一迭代点，克服了传统信赖域算法中重新求解子问题代价高的问题初步 的数值试验证明算法对某类问题有较好的效果 3 1 引言 对于无约束优化问题( 1 1 ) ，选取新锥模型( 1 1 4 ) 逼近原函数，进而转化为三个精确 子问题( 1 1 5 ) 一( 1 1 6 ) 计算试探步 由于试验步不成功时重解子问题的代价很高，人们开始尝试把线搜索的技巧应用到 信赖域方法上，提出了一类带线搜索的信赖域算法”1 引传统的信赖域优化算法是一种 单调算法，即在迭代期间目标函数值递减，g r i p p 0 1 4 6 1 等提出了一种求解无约束优化问题 的非单调线搜索方法d e n g l 3 】等利用了g r i p p o 4 6 1 等的非单调技术提出了一种非单调信 赖域算法张华1 2 1 提出了一种非单调自适应信赖域算法，充分利用当前迭代点处的梯度 和h e s s a n 阵的信息，减少运算的花费 根据信赖域方法良好的收敛性和线搜索方法计算量小的优点，本章将线搜索应用到 新锥模型自适应信赖域方法上，结合非单调技术【6 】构造了一类新算法：当试验步以不成 功时，采用非单调a r m i j o 线搜索求得下一个迭代点，利用文献【l o 中的。= c pi l 何l | | l | 矾i i 来调节信赖域半径，