（数学专业论文）非线性最优化锥模型信赖域算法的改进.pdf

摘要 本文建立了求解非线性无约束最优化问题的三个锥模型信赖域算法主要内容如 下： 第二章基于一个简化的锥模型信赖域子问题模型，结合一个新的信赖域半径自适 应调整策略，建立了一个求解无约束最优化问题的自适应锥模型信赖域算法在一般假 设条件下，证明了算法的全局收敛性质和超线性收敛速度数值实验结果表明算法是有 效的 第三章基于上一章构造的简单锥模型信赖域子问题模型，结合非单调技术，建立了 一个非单调自适应锥模型信赖域算法，证明了算法的全局收敛性数值实验结果表明算 法是有效的，适于求解大规模问题 第四章基于简单的锥模型信赖域子问题，结合非精确线搜索技术，提出了一类带线 搜索的锥模型信赖域算法当试探步不成功时，算法不重新对信赖域子问题进行求解， 而是沿着试探步的方向进行非精确线搜索得到下一个迭代点在较弱条件下，证明了算 法的全局收敛性数值实验结果表明算法是有效的，适于求解大规模问题 关键词：锥模型，自适应，非单调，线搜索，信赖域算法，无约束最优化，全局收敛 i m p r o v e m e n to fc o n i c - m o d e lt r u s tr e g i o nm e t h o df o r n o n l i n e a r o p t i m i z a t i o n d o n gj i e h o n g ( m a t h e m a t i c s ) d i r e c t e db yp r o f s u nq i n g y i n g a b s t r a c t i nt h i s p a p e r , w ep r o p o s e t h r e ec o n i c - m o d e lt r u s tr e , o nm e t h o d sf o rn 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 n t h em a i nc o n t e n to ft h et h e s i si sp r e s e n t e da sf o l l o w s ： i nc h a p t e rt w o ，b a s e do nas i m p l em o d e lo ft h ec o n i c - m o d e lt r u s tr e g i o ns u b - p r o b l e m a n dc o m b i n ean e ws t r a t e g yo fa d j u s tt r u s tr e g i o nr a d i u s ，w ep r o p o s eas e l fa d a p t i v e c o n i c m o d e lt r u s tr e g i o nm e t h o df o ru n c o n s t r a i n e do p t i m i z a t i o n c o n v e r g e n c ep r o p e r t i e sa n d s 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 ep r o v e du n d e rc e r t a i nc o n d i t i o n s n u m e r i c a l e x p e r i m e n 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 e i n c h a p t e rt h r e e ，b a s e do nt h es i m p l ec o n i c m o d e lg i v e ni nc h a p t e rt w oa n dw i t h n o n - m o n o t o n et e c h n o l o g ya n o t h e rn e ws e l fa d a p t i v es t r a t e g yf o ra d j u s t i n gt h et r u s tr e g i o n r a d i u si sp r o p o s e d c o n v e r g e n c er e s u l t so ft h em e t h o da lep r o v e d n u m e r i c a le x p e r i m e n t s s h o wt h a tt h en e wm e t h o di se f f e c t i v e ，s u i t a b l et os o l v el a r g es c a l eo p t i m i z a t i o np r o b l e m s i nc h a p t e rf o u r b a s e do nt h es i m p l em o d e lo fc o n i c m o d e lt r u s tr e g i o nm e t h o da n d c o m b i n ew i t hal i n es e a r c ht e c h n i q u e an e wc o n i c - m o d e lt 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 ht e c h n i q u ei sp r o p o s e d i ft h et r i a ls t e pi su n s u c c e s s f u l ，t h en e wm e t h o dd o e s n tr e s o l v e t h es u b p r o b l e m ，b u to b t a i n st h en e x ti t e r a t i o np o i n tb yp e r f o r m i n gal i n es e a r c ht e c h n i q u e f r o mt h ef a i l e dp o i n ta l o n gt h et r i a l s t e p u n d e rs o m ew e a kc o n d i t i o n s ，c o n v e r g e n c e p r o p e r t i e sa 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 wt h a tt h en e wm e t h o d i se f f e c t i v e k e y w o r d s ：c o n i c m o d e l ，s e l fa d a p t i v e ，n o n m o n o t o n e ，l i n es e a r c h ，t r u s tr e g i o nm e t h o d ， u n c o n s t r a i n e do p t i m i z a t i o n ，g l o b a lc o n v e r g e n c e 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对 研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：茎一壶红 日期： 腑钿 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷 版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：童壶组 指导教师签名：! 垒全型岛 b 飙：如l d 年6 日 b 日期：) 卅岱 f 月1 日 中国石油大学( 华东) 硕士学位论文 第一章前言 非线性最优化是2 0 世纪5 0 年代发展起来的，主要讨论非线性决策问题的最佳选择 之特性，构造寻求最优解的计算方法自1 9 4 7 年d a n t z i g 1 1 提出求解一般线性规划问题 的单纯形法后，最优化才成为一门独立的学科许多亟待解决的大规模复杂科学问题和 工程问题本质上都是最优化问题这些问题的解决对国民经济有重大影响可见有效的 优化算法的研究科学意义重大 按照不同的划分标准最优化问题有很多分类，如线性规划和非线性规划，无约束优 化和约束优化等等 本文主要考虑如下形式的非线性无约束最优化问题： m i n f ( x ) ， ( 1 1 ) 工片 其中f ( x ) ：r ”专r 是二次连续可微的函数 非线性最优化的传统方法几乎都是线搜索类型的方法，即每次迭代时产生一个搜 索方向，然后在搜索方向上进行精确的或不精确的一维搜索，以得到下一个迭代点信 赖域方法是一类很新的方法，它和线搜索法并列为目前求解非线性无约束最优化问题 的两类主要的数值方法信赖域策略是目前求解无约束最优化问题的一种非常有效的 方法 锥模型信赖域方法是一类新的信赖域方法，由于锥函数是比二次函数更一般的函数 对于一些非二次性态强、曲率变化剧烈的函数，用二次函数逼近的效果是比较差的，而 改用锥函数逼近则可能改善逼近效果它不仅能很快地解决良态问题，而且也能有效地 求解病态的优化问题，因而对信赖域方法的研究特别是锥模型信赖域算法的研究是近 几十年来非线性规划领域的一个新的研究方向，受到了最优化研究界的重视 本文主要对锥模型信赖域算法进行了研究第一章简单介绍了锥模型信赖域方法， 第二章至第四章分别给出了用锥模型信赖域方法求解非线性无约束最优化问题的三种 算法，最后是结论 1 1 锥模型信赖域方法简介 作为求解非线性最优化问题的类重要的数值计算方法，1 9 7 0 年p o w c l l 2 最早对信 赖域算法进行了研究，但是人们发现，在定意义下著名的求解非线性最小二乘的 第一章前言 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 ) 的信赖域算法是目标函数f ( x ) 在当前 迭代点五近似展开到第三项，即 ，( + d ) 厂( 工 ) + g ：d + 去d ，h i d ， ( 1 2 ) 其中d r “，h 。是厂( 工) 在以点的h e s s i a i l 矩阵考虑如下定义的函数 g ( d ) ：= 厂( ) + g ：d + k 1d r h 女d ( 1 3 ) 由于鲛( d ) 用了厂( 石) 在当前迭代点靠的一阶和二阶导数信息，所以显然当矧i 不太大时， 函数厂( x ) 在以赡为中心的邻域内的最优点可由鲛( d ) 在6 小领域内求得的最优解巩满 足的+ 矾来近似确定对带约束的优化子问题g ( d ) ，称之为信赖域子问题 m 。i nq(d)：=厂(x)+g；d+drbkd，0-4)a，【 s 。0 d i i 。， 其中g 。= v f ( x 。) ，l i 1 j 为某一范数，通常采用e u c l i d 范数，矩阵坟r “”既可以是( 1 - 3 ) 中 的。，也可以是日。的拟牛顿近似 求解信赖域子问题( 1 4 ) 得解以，则目标函数厂( x ) 的实际下降量与其二次模型 q 。( d ) 的预估下降量的比值定义为 咋：一a r e d k ：丛止丝! 立掣 ( 1 5 ) p r e d ig ( 0 ) 一o t ( d t ) 以此来衡量当前迭代点好坏的标准 我们给出如下的传统信赖域算法： 算法1 1 s t e p l 给定初始点x o 尺”，玩e r “，常数c 1 0 ，0 c 2 1 ，0 殷 0 ，占0 ，令k = o ； 2 中国石油大学( 华东) 硕士学位论文 s t e p 2 如果恬。忙s ，g t l z ；否则，求解信赖域子问题( 1 - 4 ) 得解吐； s t e p 3 按照式( 1 - 5 ) 计算令 ：ix一噍q；(i-6)xk+l 2 l 。女， 否则； k 。 学生：乞；( i - 7 ) r , - 枷缸，3 否则； s t e p 4 修正b i ，令k = k + 1 ，返_ n s t e p 2 其中停机准则占和初始点一般都是给定的，而初始矩阵b o 一般取为刀阶单位矩阵，初 始信赖域半径a 。取为1 ，常参数c 1 ，c 2 可以取不同的值( 见 3 4 5 6 】) 下面我们给出子问题( 1 4 ) 有解的充要条件 引理1 1 【7 1 设艿r 是对称矩阵，则向量d r “是信赖域子问题( 1 4 ) 的解的充分 必要条件是，存在z o ，满足：( 1 ) ( 召+ ，) d + = 一g ；( 2 ) ( 召+ z ，) 半正定；( 3 ) 忙+ 忙； ( 4 ) f ( 一州1 ) = o 1 9 8 0 年，d a v i d o n 9 首次提出了锥函数下面给出锥函数的一个定义： 定义1 1 【9 】如下形式的函数厂：x _ r 称为锥函数： 似川m + 为+ 器舶。钒m m 8 ， 其中xc r ”，正r ，g t r ”，尺“，b k r “为对称矩阵 在x = 以+ d x 处，锥函数的梯度值为 g = 专( 几+ 钆d 顶厝。+ b d ) ：j ( 厶一瓯d r ) 一t ( 珞。+ 鼠d ) 其中y = l 一瓯r d 显然在处，锥函数厂的函数值为厶，梯度值为g 。通过计算还可得 到在以处，锥函数厂的h e s s i a n 阵为b k + 仇既7 + 繇瓯7 为了保证锥函数的定义域为一个 3 第一章前言 连续空间，只能有玩r d 1 或7 d 1 但是因为d = o 在锥函数的定义域中，所以我们在 定义1 1 中限制d 的取值范围为以7 d 0 , 0 c 3 c 4 1 c l ，0 0 ( 1 - 2 0 ) 则圆锥函数( 1 - 1 4 ) 删x i 一饽。m 0 ) 上有极小点 x k 毋= z t 一2 g t ，( 1 。2 1 ) 其中， 刀= _ 了i 粤譬i 一 o ( 1 2 2 ) g 。g 虽l 。g 女+ g l 。b g 女 、叫 并且以曩与位于奇平面l + 也7 0 一稚) = 0 的同侧 ( i i ) 如果下式成立： g , r g i b , r g 女+ g , r b g t 0 ( 1 - 2 3 ) 则圆锥函数( 1 - 1 4 ) 在射线以一饽。( 名o ) 上严格递减 定理1 4 【1 0 】设色为正定对称且( 1 1 9 ) 成立 6 中国石油大学( 华东) 硕士学位论文 ( i ) 若l + b k r b - 1 9 女 0 ，则圆锥函数( 1 1 4 ) 在线段 工= x i ，+ f ( x 一x i 廖) ，0 t 1 上沿t 增加方向为非增函数 ( i i ) 若z l + b k r b - 1 9 t 0 ，则圆锥函数( 1 1 4 ) 在半直线x = 口+ f ( h + 口) t 1 上沿t 减小方向为非增函数 1 1 2 锥模型信赖域子问题的解法 我们考虑求解如下的锥模型信赖域子问题 m ；n 聊m + 斋+ 三1 器， 豇d a i 为使信赖域矧l 。位于奇平面1 + 钆r d = 0 的同一侧，我们限定 ( 1 - 2 4 ) 女f 0 ，1 + 巩r b k g t o 及( 1 - 2 6 ) b - 1 2 、_ f f _ 若| l d lj a t ，则d r 即为子问题 ( 1 2 5 ) 的唯一解；否则( 1 。2 5 ) 的解必在信赖域的边界上达到 由上面的思想给出子问题( 1 2 5 ) 的如下算法： 算法1 3 s t 印1 计靴。= 蔫，如张陋棚f j 置弘“翻 s t 印2 计算吨酏耐，如果比 o ，贝i j 置以一舒，返回 s t e p 3 计算以一譬如果蚓训棚i j 置驴一箭，返吼 w g t s t e p 4 否则置畋= 峨+ ( 1 一f ) 以，返回 在s t e p 4 中t 的值满足方程 妒( f ) ：l i 以+ f ( d 。一吐) 1 1 2 一。：0 ( 1 - 2 7 ) 7 第一章前言 即f 为二次方程( 1 2 7 ) 1 撇，令口= 8 屯一吃| | 2 ，6 = 吃r ( 以一以) ，c = l 1 1 2 一。2 由i i 1 i b 2 0 于是二次方程有两个实根 ：- b + 巫痧- a c o 口 - b - 痧- a c r - - - - - - o i 乞，1 + 玩。最g t 0 如果1 + 么7 最g k = 0 ，则算法失败，停止 当然对于锥模型信赖域予问题还有不同的解法见 4 3 4 4 】 1 1 3 非单调技术 传统信赖域算法都是单调的，即要求迭代过程中函数值单调下降然而对许多函数， 单调算法并不理想近年来出现了非单调算法 1 3 - - 一2 0 ，即算法在某一步后，每试探一 步要求当前点的函数值和前面不固定个点的函数值中最大的进行比较当目标函数性 态好时，算法采用单调下降步；当它性态差时，算法采用非单调下降步，这样有利于算 法快速收敛但大多非单调信赖域算法是基于二次模型的，基于锥模型的非单调信赖域 算法尚不多见 八十年代中期，g r i p p o 、l a m p a d e l l o 雨 i l u c i d i 1 3 1 为拟牛顿方法引进了非单调线搜索策 略，即步长位。满足 厂( 工i + c r i d t ) 。m ：，；a 。x 。f ( x k j ) + 9 c r v f ( x , ) 丁d 女，( 1 - 2 8 ) 其中( 0 ，1 ) ，m ( 0 ) = 0 ，0 m t m i n m + 1 ，m ) ，m 是给定的非负整数当m t = 0 时， 上式即为a r m i j o 单调搜索随后又将该技术推广多j s q p 方法，理论分析和数值实验表明 非单调技术有一定的优越性1 9 9 3 年，邓乃扬【1 4 】等人利用非单调性策略这一技巧首次提 出了一类具有强收敛性的非单调信赖域算法，提出了非单调信赖域算法( n o n m o n o t o n e t r u s tr e g i o na l g o r i t h m ) 这一工作是开拓性的，有关非单调信赖域方法的其他研究成果都 是它的推广或修正之后，柯小伍和韩继业【1 5 1 从另一不同的角度也提出了一个求解无约 束优化问题的非单调信赖域方法t o i n t 1 6 1 对无约束与凸约束优化问题提出了另一种非单 调的信赖域算法 8 中国石油大学( 华东) 硕士学位论文 非单调锥模型信赖域算法的具体作法是，在式( 1 1 3 ) 中，将目标函数f ( x ) 的真实下 降量与其锥模型m 。( d ) 的预估下降量的比值改用下面的公式计算 ：盟：血掣，( 1 - 2 9 ) 一= - = - 二二一 p r e d i m i ( 0 ) 一m t ( d t ) 7 9 f k ) 2 厂( ) 。s m ，s a 。x ( i ) ( 矗一小r e ( o ) = 0 ，0 0 ，b o r “，常数0 c 3 c 4 1 c l ， 0 c 2 1 ，占0 ，令k = 0 ； s t e p 2 如果恬。忙占，停止；否则，求解信赖域子问题( 1 - 4 ) 得解噍； s t e p 3 计算f ( x k + 畋) ，如果f ( x k + 畋) f ( x k ) ，转s t e p 4 ；否则，按照某种线搜索规 则寻找最小的正整数i ，使得f ( x k + o r7 d 。) f ( x k ) ，其中口( o ，1 ) 为正常数，计算 以+ l = 以+ 口7 以，a 8 + l - x k 1 ，c 4 女 ，转s t e p 5 ； s t e p 4 令以+ 1 = x k + d k ，按照式( 1 5 ) 计算，令 a t + 1 a 女， c ，0 d 。】， a 女，c 1 a 女 ， s t e p 5 修正b 女，令k = k + 1 ，返回s t 印2 9 o3 - ，l 七 七 j i 慨 恢 如 以勿 人i l 咯 第一章前言 1 1 5 信赖域半径的调整 信赖域半径的调整策略是保证信赖域算法全局收敛性的一个关键传统的信赖域 半径的调整策略仅仅根据目标函数的实际下降量和预估下降量的比值以的大小，按常 数比例扩大或缩小信赖域半径，具有一定的盲目性，如算法1 1 、1 2 、1 4 中的。的调整， 而初始信赖域半径的选取也只是不加分辨的给出一个常数在锥模型信赖域算法的实 现过程中，信赖域半径的大小是一个很重要的量，锥模型信赖域的重要思想就是在合适 的范围内用锥模型代替目标函数如果信赖域半径太大，那么在信赖域内，锥模型不是 目标函数的好的近似，求解子问题得到的试探解d 。当然也就不能被接受；如果信赖域 半径太小，那么新的迭代点与前一步的迭代点相距太近，目标函数值不会下降太快，迭 代会很慢初始信赖域半径的选取也是同样重要的，我们希望得到的是在初始点附近使 锥模型与目标函数充分接近的最大的初始信赖域半径，那么传统信赖域算法里人为规 定如。：1 的做法显然是不适当的 鉴于以上思想，许多学者提出了信赖域半径的自适应算法s a r t e n a e r 在文 2 2 中研 究了初始信赖域半径的选取对算法有效性的影响，给出了一个自动确定初始信赖域半 径的算法文 2 3 中黑龙提出当前迭代的信赖域半径是上次迭代的步长范数归0 与关 于比值r k 的函数的乘积范金燕、袁亚湘2 4 】提出了信赖域半径是关于目标函数梯度 恬。0 的函数，给出了信赖域半径收敛到零的证明李改弟瞄1 依据比值炒i | i f d 8 包含目 标函数的二次信息提出a 。= 恬。d 0 y 0 信赖域半径调整策略，利用比值珞调节。 章祥荪、张菊亮和廖立志在文【2 6 中取自适应信赖域半径为。= c p l 艿训恬。0 ，c ( o ，1 ) ， p 是非负整数 1 2 本文主要工作 本文主要研究了用锥模型信赖域方法求解无约束最优化问题，把一般的信赖域算 法技巧推广到锥模型信赖域并进行了进一步改进，主要工作分为三个部分： 第二章首先构造了一个简化的锥模型信赖域子问题模型，该模型的求解简便，存储 量和计算量都很少基于这个简单锥模型信赖域子问题模型，并给出了一个新的自适应 1 0 中国石油大学( 华东) 硕士学位论文 信赖域半径调整策略，该策略充分利用当前点包含的信息来调整信赖域半径，提出了一 个自适应锥模型信赖域算法在一般假设条件下，证明了算法的收敛性质，并对算法进 行了数值实验 第三章给出了另一种锥模型信赖域半径自适应调整策略，基于上一章构造的简单 锥模型信赖域子问题模型，并结合张洪超等【2 7 】的非单调技术，建立一个新的非单调自适 应信赖域算法该算法计算简单，存储量和计算量少，适合求解大规模问题另外，在 迭代中，要求目标函数值不一定是单调的，这加快了算法在其最优点附近的收敛速度 在一般假设条件下，证明了算法的收敛性质从数值实验的结果来看，算法是有效的 第四章在简化的锥模型信赖域子问题的基础上，结合时贞军【2 8 】的非精确线搜索技 术，提出了一个带线搜索的锥模型信赖域算法当试探步不成功时，只沿着试探步的方 向进行线搜索而不需要重新求解子问题该非精确线搜索是加m i j o 线搜索的推广，在 每次线搜索时可产生一个较大步长，有利于算法的快速收敛在一般假设条件下，证明 了算法的收敛性质，并对算法进行了数值实验 第二章一类基于锥模型的自适应信赖域算法 第二章一类基于锥模型的自适应信赖域算法 本文建立一类新的求解无约束优化问题的自适应锥模型信赖域算法利用了一个 新的自适应信赖域半径的调整策略。该策略根据目标函数的实际下降量和预估下降量 的比值，并充分利用当前点包含的信息来调整信赖域半径同时利用了稀疏对角矩阵扩 大了算法的适用范围分析证明了这种算法的全局收敛性质和超线性收敛速度数值例 子证明了算法的有效性 2 1 锥模型信赖域子问题模型 信赖域子问题的求解是信赖域算法的一个重要工作许多学者对此进行了研究见 2 9 - 3 7 对于锥模型信赖域子问题，本节我们构造一个基于锥模型的简单的锥模型信 赖域子问题模型，该模型的存储量和计算量都很少，将锥模型信赖域算法推广到求解大 规模问题 对于锥模型信赖域y ：f - j 题，在t + 。领域逼近目标函数的锥函数为 脚( x k 1 + d + 黪t 篙铬 p ， 显然( 2 1 ) 满足 m ( x k + ，) = 以+ 。= f ( x m ) ( 2 2 ) v m ( x k + 1 ) = g ( x k + i ) = v f ( x k + 1 ) ( 2 - 3 ) 另外，类似可得 m ( x t ) = m ( x 一d 1 ) = 五( 2 - 4 ) v m ( x d = v m ( x k + 厂喀) = g k ( 2 - 5 ) 可以看出插值条件( 2 4 ) ( 2 5 ) 在二次函数中是不满足的，这可能是锥模型的一个非常好的 优势 1 主t ( 2 4 ) 可得 似沪讹+ 1 ) 一礁畦瑞 ( 2 6 ) 再e h ( 2 5 ) 可得 1 2 中国石油大学( 华东) 硕士学位论文 令 耵，= 去 箍纠一器， ( 2 7 ) y = 1 一瓯+ ，7 喀( 2 8 ) 结合( 2 6 ) ( 2 7 ) 可得 y 2 w 。( ) r d t + 2 r ( f ( x k ) 一f ( x k + 1 ) ) + v f ( 以+ 1 ) r d i = 0 ( 2 9 ) 对y 为一个二次方程，( 2 9 ) 有实根当且仅当p 2 = 五- a + 。 2 一( r 喀) ( + 。r 畋) 0 令尸= , p 2 ，则 y ：量掣( 2 - 1 0 ) 一g k 。d k 作为( 2 - 8 ) 的特殊情况，我们令 b k + , = 1 - 吼y 颤 ( 2 - 1 1 ) 再由( 2 - 7 ) 与( 2 1 1 ) 联立得 反+ 。畋：y g 一y ： ，+ 三反+ 。畋r 】1 = y g - y 2 i - b + l d k r k = y g t + l - y 2 9 t + y 2 ( d k r g k ) b k + l = y g i + l - y 3 9 k 2 y k 类似导出b f g s 公式，b + ，的一般迭代公式为 却舞一鬻，其帆硼可即 为减少算法的存储量扩大算法的使用范围，结合时贞军 6 】的稀疏对角拟牛顿方法， 给出毋+ ，如下的修正形式： 设b 为对角稀疏正定矩阵，令反+ 。= 最+ a b k 其中峨为对角矩阵，此时坟+ 。为对角 稀疏矩阵即反卅= - d i a g ( b k + l i , 喀+ 。2 ，b k + l n ) 且近似满足以下条件 m i n 反+ 。t - y k l l 2 ， ( 2 - 1 3 ) 1 3 第二章一类基于锥模型的自适应信赖域算法 其中y t = 7 9 - 7 3 9 t ，d t = + l - x k 同时，为保证反+ 。是i t _ 定矩阵，限制坟+ 。在一定范围内，即要求 o 量 喀+ 1 z ，v i = i ，2 ，z 其中o l l 为常数，此时( 2 _ 1 3 ) 变为 即 ，罂i n ，i l b + 。噍一儿i | 2 ， 量 乓+ l 。 l i = l 。2 ，一” “” ，罂in，。(玩+，i畋7-y。)2i 量地“( 厶= 1 ，2 ，。h = 。”。 解之得，对v i = 1 , 2 ，z ， ( 2 1 4 ) ( 2 - 1 5 ) 当噍。时，若互 若y k 0 并由式( 2 1 1 ) 迭代求得a 。0 为信赖域半径i i 1 | 为某一范数，通常采用 e u c l i d 范数 如何调整信赖域半径是信赖域算法的一个非常重要的问题章祥荪等 3 9 提出了一 种自适应信赖域方法，其中取信赖域半径。= c pi i g 圳b 一0 ，o c 1 ，p 为非负整数 h e i 2 3 】提出了另一种自适应信赖域算法，其信赖域半径由一个r 一函数和i i d 0 构成，即 1 4 中国石油大学( 华东) 硕士学位论文 取。- g ( t ) 1 d 0 ，其中焉( f ) h p ；0 r 一函数 定义2 1 闯( f ) 定义在( 咱，佃) 上，参数7 7 ( o ，1 ) ，( f ) 是一个r 一函数当且仅当它 满足 ( i ) 疋( f ) 在( 埘，佃) 上非减； ( i i ) 墼r ( f ) = ，其中卢( o ，1 ) 是常数； ( i i i ) r ( f ) 1 - 7 l ，v t r ，其中乃( o ，1 - , 8 ) 是常数； ( i v ) b ( ，7 ) = l + y 2 ，其中兄( o ，佃) 是一常数； ( v ) l i m 民( f ) = m ，其中m ( 1 + j 2 ，+ o o ) 是- - 常数 f 斗 定理2 1 设民( f ) 是一个尺函数，其中叩( 0 ，1 ) ，则 0 声r 。( f ) 1 一y l 1 ，v t ( - - - 0 0 ，叩) ； 1 l + y 2 ( f ) m + ，v t 叩，- + - o o ) 由定理2 1 可以知道r 一函数的图像为如下形式： 图2 - 1r 函数的图像 f i 9 2 1f i g u r eo f t h er - f u n c t o i n 为充分利用当前点的迭代信息及以上两种算法的优点，本文取如下的信赖域半径 1 5 ( 2 1 7 ) c q 人j 名 ， + 训陂“ 毋 川 洲悟“列 陬瓴 ， 疋 i i i i n “ ，j、l 第二章一类基于锥模型的自适应信赖域算法 其中0 c 。 c 2 1 均为常数且心( 咯) 满足定义2 1 2 2 算法步骤 本文的算法步骤如f 算法2 1 ( d a c t r ) s t e p 0 选取参数x o r ”，b o r ”，s o r ，0 c 1 ，0 一l 0 ，o g c 2 1 ， o p 1 ，0 1 + 圯，令p ：= 0 ，七：= o ； s t e p l 计算g i = g ( x i ) ，如果恬女0 占，停；否则，转s t e p 2 ； s t e p 2 求解锥模型信赖域子问题( 2 - 1 6 ) 得解d k ； s t e p 3 通过( 1 1 1 ) 一( 1 1 3 ) ；7 1 - 赁 a r e d k ，p r e d k 和r k ； s t e r r a 如果咯 c l ，x k + 。= ，色“= b k ，p ：= p + 1 ，m = c p i l g k + 。洲色+ 1 - 10 ，k ：= 后+ l ，转 s t e p 2 ；否则转s t e p 5 ； s t e p 5 如果气c l ，则令+ 。= 墨+ d k ，更新良十l 反+ l ，m = 心( ) i k 川l j l | 反+ 1 - i8 ， p ：= 0 ，k ：= k + 1 ，转s t e p l 为保证锥模型函数在信赖域半径川训。) 是有界的，假设对v 后，了仃( o ，1 ) ，使 i i 瓯i i a 。仃 ( 2 - 1 8 ) 在本算龇如果非阻令妒南，使得1 1 玩1 1 郇仃，0 0 ，使得0 b i l 墨，慨0 如，对所有j i 均成立 引理2 1 假设h 1 成立，同时( 2 1 8 ) 成立，则存在一个正常数五，使得 1 6 中国石油大学( 华东) 硕士学位论文 m 硎蜘i n k 鼢肌 ( 2 - 1 9 ) 证明首先，设畋( f ) ：一t g 。，其中f o ，。l l g 。1 1 使得喀( f ) 对( 2 1 6 ) 是可行的因此由 州旷纵删f 燃一导器 2 。， 丽iig,112皿搔-0-)22(1o - ) ) 一 + 、 ( 1 ”川 卸m a a 舻x 2 尚脚n t 南，筹舟 协2 2 ， 毗自( 2 - 2 1 ) ( 2 - 2 2 ) 可得磊= 器触 i i 畋l l c l l g 。0 ，k = l 2 一( 2 - 2 3 ) 证明因为0 或i l 。，由r 函数的定义知o ( 一。) m ，由第二节知0 色一0 为一致 有界的，即存在k ，使得任意的七有0 b 一1 忙k ，再由( 2 1 7 ) 式定义的。， 取三= m a x 加k ，k 。) ，则结论成立 1 7 第二章一类基于锥模型的自适应信赖域算法 正- f ( x k + 或) 一丹巩l = p 或一v 2 讹+ + 老+ j 1 一圭畋r ( v 2 厂( 五+ 哦吨) 一只) 反一圭矾r 色畋( 1 一百干乏弦了) l 掣+ 护肌+ 一b 一1 + o 兰o f ) l l l u 2 ( 2 - 2 5 其中色 0 ，1 ，由( 2 2 5 ) 与假设h 1 ，存在 疋掣书2 胞蝴h 峥，+ 高) 使矧理魁 引理2 4 设h l 成立， 以) 是由算法2 1 产生的无穷点列如果对任意的七，0 9 。忙c ， c ( o ，1 ) 为常数，则对v 七，存在整数p 0 ，满足噍+ ，c 1 证明用反证法证明 假设引理不成立，即存在非负整数，使得 + p 岛 定义集合丁= 后l0 氍i i - - 岛 ，由引理2 2 、引理2 4 ，对任意的尼丁都有 a t 0 ( 2 3 1 ) 另一方面，由算法知 f ( x k ) 一厂( 以+ 喀) c l ( m t ( o ) 一m i ( d t ) ) ( 2 - 3 2 ) 再由矿( 以) ) 是单调下降且有下界的，因此是收敛的则当七一，k t 时( 2 3 2 ) 左式满足 ! 鳃( ( o ) 一( 以) ) = 0 女盯 由引理l ，对任意的k t 有 聊棚州啦沌i l m i a ，鼢 狮砒池，争 对( 2 - 3 4 ) 两边同时取极限可得l i m a 。= 0 与( 2 3 1 ) 矛盾 。 1 9 ( 2 - 3 3 ) ( 2 3 4 ) 第二章一类基于锥模型的自适应信赖域算法 2 4 超线性收敛速度 定理2 6 设h 1 成立，算法2 1 产生的序列 以) 收敛于x ，h e s s i a n 阵日( z ) 是正定 矩阵，日( 工) 在工的一个邻域内l i p s c h i t z 连续若 ! 氅掣：o ， 仁3 5 ， 且 8 箍馏悔忙磊， 陋3 6 ， 其中憋袅= 0 ，则有 以) 超线性收敛于x 。 证明由h ( x ) 是正定矩阵且h ( x ) 在工+ 的个邻域内l i p s c h i t z 连续，则存在正数 m m 0 ，l 0 和a 0 使得 m 娜s j r h ( x ) s m 2 ，v s r ”，工q 一 ( 2 3 7 ) 1 1 日( 工) 一日( 少) 0 k 。，吒q 钳= 8 9 k + h k d k + f o + 锹k ) - h ( x k ) d k d o k o = i | g 。+ 了三毫；乞_ + c 一了； 矗，b 。d 。+ j ：c 日c 石。+ 鲫。，一日c x 。，d 。d 口+ c 日。一b 。，d 。i i , d 。 + 慨l剖铡引崦叫恢忡喈 剐+ 0 ( 1 刘1 ) + 皆 由( 2 3 7 ) 可得 0 9 k i i - i g m g k i l + l l g 洲m g 川， 上式两边同除归。i | ，得 2 0 ( 2 - 3 9 ) ( 2 - 4 0 ) 断 一 iiiiiiiiii一 一 中国石鎏莶兰! 堂垄竖圭兰垡迨茎二一 一二一。 糊错 ( 2 _ 4 1 ) 把( 2 - 4 1 ) 代人( 2 3 9 ) 可得 iig恢k1rll,-,_llig划*厂ii,砌慨”喈 进一步可得 错洲”呼肋+ 当七一时，有氧- 4 0 ，忙。1 1 - 0 再由条件( 2 3 5 ) 可得 l i r a ilg慨,*lrllk-+ao id，l i 又由咿。l l - c l 恼t8 可得 溉豺i i 观 女p ， ( 2 4 2 ) ( 2 4 3 ) ( 2 4 4 ) ( 2 - 4 5 ) 即证明了超线性收敛性 2 5 数值实验 本节选择了文献【1 0 】【4 0 的几个算例，利用m a t l a b 编程对本章算法2 1 进行数值实 验。如果算法e ob k 用b f g s 公式校正，则记为b f g s - d a c t r 取如下的数值例子： p 1 厂( x ) = ( 五2 + x 2 2 ) o 一一) 2 初始点x ：( - 1 ，一1 ) 丁，2 =