（计算数学专业论文）非线性最优化自适应信赖域算法的改进.pdf

摘要 本文提出了三个求解非线性无约束最优化问题的自适应信赖域算法主要内容如 下： 第二章基于一个简单信赖域子问题模型，提出了一个求解无约束最优化问题的自 适应信赖域算法文中先构造了一个简甲子问题模型，该模型需要的存储量和计算量较 少对于信赖域半径的调整，给出了一个新的自适应调整策略，该策略根据目标函数的 实际下降量和预估下降量的比值，并充分利用当前点包含的信息来调整信赖域半径在 一般假设条件下，证明了算法的收敛性质，并对算法进行了数值试验，试验结果表明算 法是有效的 第三章给出另一种信赖域半径自适应调整策略，基于上一章构造的简单信赖域子 问题模型，并结合非单调技术，提出了一个非单调自适应信赖域算法在迭代过程中， 算法允许目标函数值是非单调的在w ( j c ) l i p s c h i t z 连续条件下，证明了算法的收敛性 质，并对算法进行了数值试验，试验结果表明算法是有效的 第四章在第二章算法的基础卜，结合非精确线搜索技术，提出了一个带线搜索的自 适应信赖域算法当试探步不成功时，算法不重新求解信赖域子问题，而是沿着试探步 的方向进行线搜索得到下一个迭代点在较弱条件下，证明了算法的收敛性质，并对算 法进行了数值试验，试验结果表明算法是有效的 关键词：简单模型，自适应，非单调，线搜索，信赖域算法，无约束最优化，全局收 敛 i m p r o v e m e n to fs e l f a d a p t i v et r u s tr e g i o nm e t h o df o r n o n l i n e a ro p t i m i z a t i o n s a n gz h a o y a n g ( c o m p u t a t i o n a lm 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 sp a p e r ，w ep r o p o s et h r e es e l fa d a p t i v et r u s t r e g i o nm e t h o d sf o r n 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 r2 ，w ep r o p o s eas e l fa d a p t i v et 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 d o p t i m i z a t i o nb a s e do nas i m p l em o d e lo ft h et r u s tr e g i o ns u b p r o b l e m t h es i m p l em o d e l n e e d sl e s sm e m o r yc a p a c i t a n c ea n dc o m p u t a t i o n a lc o m p l e x i t y m o r e o v e la c c o r d i n gt ot h e r a t i ob e t w e e nt h ea c t u a lr e d u c t i o na n dt 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 a d j u s tt h et r u s tr e g i o nr a d i u sw i t han e ws t r a t e g yw h i c hm a k e sf u l lu s eo ft h ei n f o r m a t i o na t t h ec u r r e n tp o i n t c o n v e r g e n c ep r o p e r t i e so 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 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 di se f f e c t i v e i nc h a p t e r3 ，a 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 nr a d i u si s p r o p o s e d b a s e do nt h es i m p l em o d e lg i v e ni nc h a p t e r2 ，an e wn o n m o n o t o n es e l fa d a p t i v e t r u s tr e g i o nm e t h o di sp r e s e n t e d d u r i n gt h ei t e r a t i v ep r o c e s s ，t h ev a l u eo ft h eo b j e c t i v e f u n c t i o ni sa l l o w e dt ob en o n - m o n o t o n e 。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 r ep r o v e du n d e r v f ( x ) l i p s c h i t zc o n t i n u o u s 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 di se f f e c t i v e i nc h a p t e r4 ，o nt h eb a s eo ft h em e t h o dp r e s e n t e di nc h a p t e r2 ，an e ws e l fa d a p t i v et r u s t r e g i o nm e t h o dw i t hl i n es 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 w m e t h o dd o e s n tr e s o l v et 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 ga l i n es e a r c ht e c h n i q u ef r o mt h ef a i l e dp o i n ta l o n gt h et r i a ls 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 ep 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 di s e f f e c t i v e 。 k e y w o r d s ：s i m p l em o d e l ，s e l fa d a p t i v e ，n o l l 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 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：叁丝z 量 日期：年月 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电了版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门 ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被 查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用 影印、缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：篡些翌建 。 指导教师签名：之堑芝趔 日期： 日期： 年 月 日 年月日 中国石油大学( 华东) 硕士学位论文 第一章前言 最优化是一门应用相当广泛的年轻学科，自1 9 4 7 年d a n t z i g 1 1 提出求解一般线性规 划问题的单纯形法后，它才成为- - f q 独立的学科最优化主要研究如何使得目标函数值 达到最大或者最小，在众多的方案中如何选取最佳方案等等许多亟待解决的对国民经 济有重大影响的大规模复杂科学问题和工程问题本质上都是最优化问题这些问题有 的规模巨大，有的规模虽不十分巨大但却是非常复杂的优化问题因此，研究高效的优 化计算方法不仅具有重要的科学意义，而且有着很大的应用前景，对促进优化方法在国 民生产等方面的应用将起到重大作用 最优化问题按照不同的标准可以分为许多类，如线性规划和非线性规划，无约束优 化和约束优化，整数规划、随机规划、非光滑规划、多目标规划、几何规划等等 本文主要考虑如下形式的非线性无约束最优化问题， r a i n f ( x ) ， ( 1 _ 1 ) 其中( 石) ：r ”一只是连续可微的函数 对问题( 1 一1 ) ，通常采用迭代方法求它的最优解，其基本思想是：给定一个初始点 x o r ”，按照某种迭代规则产生一个点列 以) ，使得当 矗) 是有穷点列时，其最后一个 点是最优化问题的最优解；当 砟，是无穷点列时，它有极限点，且其极限点是最优化问 题的最优解个好的算法应具备的典型特征是：迭代点心能稳定地接近局部极小点 x 的邻域，然后快速收敛到x 。，当给定的某种收敛准则满足时，迭代即终止，目前，线 搜索方法和信赖域方法是求解非线性无约束最优化问题的两类主要数值方法，它们都 是基于迭代思想构造的 本文主要研究求解非线性无约束最优化问题的自适应信赖域方法第一章简单介 绍了信赖域方法，第二章到第四章分别给出了求解非线性无约束最优化问题的自适应 信赖域方法，最后是结论 1 1 信赖域方法简介 信赖域方法( t m s tr e g i o nm e t h o d ) 是求解非线性最优化问题的一类重要的数值计算 方法 第一章前言 信赖域方法的研究起始于2 0 世纪6 0 年代的p o w e l l t 2 1 ，其基本技巧在一定意义下等 价于著名的求解非线性最小二乘问题的l e v e b e r g m a r q u a r d t 算法1 9 7 5 年，p o w e l l t 3 1 给出 了信赖域法的第一个收敛性结果与线搜索方法相比，信赖域方法具有很好的可靠性、 稳健性和较强的收敛性，不仅能很好地解决良态问题，而且也能有效地求解病态 ( 1 1 1 c o n d i t i o n e d ) 的优化问题因此在近几十年来受到了最优化研究界的重视，特别是近 几年，一直是非线性最优化的研究热点 对非线性无约束最优化问题( 1 1 ) ，我们将目标函数( x ) 在当前迭代点_ 近似展开 到第三项，即 f ( x t + d ) ：z f ( x i ) + g ；d + l d r h d ， ( 1 2 ) 其中，d er ”，日。是( 曲在点的h e s s e 矩阵考虑如下定义的函数 q ( d ) _ 厂( 稚) + g k d + o - d 7 h t d ( 1 3 ) 因为用到了目标函数在当前迭代点x k 的一阶和二阶导数信息，所以显然当矧 不太大时， g ( d 必是函数( x ) 在以点的二次t a y l o r 近似不妨认为在的邻域万= dl l | 刎氐 内， 幺( 矗) 可以代替( x ) ，其中邻域万称为信赖域( 酗s tr e g i o n ) ，a t 0 称为信赖域半径 ( t r u s tr e g i o nr a d i u s ) 那么，g ( d ) 在6 内的最优解反应该可以使得+ 巩是函数f ( x ) 在以瓦为中心的邻域内的最优点换言之，我们需要求解约束优化子问题，称之为信赖 域子问题( t r u s tr e g i o ns u b - p r o b l e m ) m i n q 女( d ) ：= ( 以) + g t 扎2 l _ _ d r 反办( 1 4 ) s t i d l l - a 。， 其中g t = 夥( 坼) ，| | 1 i 为某一范数，通常采用e u c l i d 范数，矩阵b k r 舳既可以是( 1 3 ) 中 的日。，也可以是日。的拟牛顿近似 为了检验我们的假设，在求解子问题( 1 4 ) 得到试探解瓯以后，计算目标函数厂( x ) 的真实下降量与其二次模型g ( d ) 的预估下降量的比值 n ：a r e d t _ ：f 墨2 二! 益互2 p r e d tq k ( 0 ) 一g ( 以) 2 ( 1 5 ) 巾国石油大学( 华东) 硕士学位论文 一般地，将值的大小作为判断幺( d ) 近似目标函数厂( x ) 好坏的标准：气越大，鲛( d ) 应 该越好地近似目标函数；反之，噍越小，g ( d ) 则越不能很好地拟合目标函数因此，我 们可以事先设定r k 的阀值，如果珞大予该阂值，我们认为试探解破是一个“好的”解，接 受它，得到下一个迭代点_ + 。= x k + d k ，同时扩大信赖域半径；相反，如果珞小于该阈值， 我们认为矾是一个“不好的”解，抛弃它，保持迭代点不变，同时减小信赖域半径并重新 求解子问题当然，我们完全可以在考虑是否接受试探解和如何修正信赖域半径这两个 问题时，对设置不同的阀值，但原则总是以的值作为衡量二次模型好坏的标准 我们将上述的思想写成如下的传统信赖域算法( t r a d i t i o n a lt r u s tr e g i o nm e t h o d ) ： 算法1 2 7 s t e p l ：给定初始迭代点j c 0 r ”，b 0 r 棚，常数c l 0 ，0 c 2 1 ，0 屈 0 ，0 ，令七= 0 ； s t e p 2 ：如果慨l i - c l l g 。m i n 黔 其中c e ( 0 ，1 ) 是个常数因此，许多学者提出了信赖域予问题的近似求解，主要有折 线法、二维搜索法和预共轭梯度法 p o w e l l 在 2 】中提出折线法，即当反正定时，用条折线来近似d ，其做法是连接柯 西点和全步长( q ( d ) 的无约束最小值点以一所1 9 。) ，取其与信赖域边界的交点为黾柑 d e n n i s 和m e i 1 2 1 提出了双折线法，他们发现如果在信赖域迭代中产生的点一开始就偏向 于全步长方向，则算法的性态将得到改善把柯西点和全步长方向上的一点连接起来， 取连线与信赖域边界的交点为x k + 1 二维子空间搜索法由s h u l t z 、s c h n a b e l 、b y r d 1 3 1 4 】 提出，即当乓正定时，在由最速下降方向和全步长方向张成的子空间s p a n g 。，所1 9 。】 上求解目标函数的极小值当鼠有负特征值时，在子空间s p a n g 。，( 反+ 耐) g 。】上求解 目标函数的极小值，其中口( 一a ，一2 丑】，五为暖的最负特征值；当反有零特征值无负 特征值时，取柯西点为近似解s t e i h a u g 巧j 提出了预共轭梯度法，即运用共轭梯度法求解 子问题如果所有迭代点列都在信赖域内部，则它就是共扼梯度法，此时方法终止于信 赖域内部，否则迭代点可在信赖域外得到一个毋负曲率方向无论哪种情况，都能在边 界上解得一个修正步长另外，n o c e d a l 和y u a n 在文【16 】中给出了一种近似求解信赖域 子问题的算法，即 4 中国石油大学( 华东) 硕士学位论文 算法1 3 ( 近似求解信赖域子问题的算法，n o c e d a l 和y u a n 1 6 1 ) s t e p i ：设常数y l ， 0 ，令五暑o ，如果b 正定，转s t e p 2 ；否则找到一个 a 【o ，1 1 8 1 1 + ( 1 + ) l l g l l a l ，使得曰+ 刀正定； s t e p 2 ：分解艿+ 舡= r 7 r ，其中r 是上三角阵，解r7 尉= 一g 得d ； s t e p 3 ：如果l ，停；否则，解尺r g = d 得9 ，计算 榭酱华， 转s t e p 2 1 1 2 非单调技术 传统的信赖域方法有一个特点：算法是单调的，即，只有当目标函数值严格小于当 前迭代点的函数值时，试探解才被接受，这保证得到的目标函数值序列是单调下降的 但在实际计算中，对于某些问题，这样做并不能保证算法的有效性例如对r o s e n b r o c k 函数，当迭代点接近最优点时，收敛速度变得很慢，会出现类似于m a r o t o s 效应的现象 对一一些等高线是由一簇斜率非常陡的曲线所组成的函数也是如此 1 9 8 6 年，g r i p p o 、l 锄p a r i e l l o 和l u c i d i 为拟牛顿方法引进了非单调线搜索策略【1 7 】，即 步长瓯满足 歹t x t r , d , ) _ ( 乓) 时，也允许接受试探解当然，这样做需要有某种限度， 5 第一章前言 即试探解反必须至少使得f ( x k + 畋) 跟过去的某些迭代点上的函数值相比较仍然是下 降的对于某些问题而言，这样的作法可以使迭代点序列跳出目标函数的“峡谷”，从而 提高算法的效率数值实验表明，非单调性策略对相当一部分实验函数可以明显加快算 法在其最优点附近的收敛速度，得到精度更高的最优解 非单调信赖域算法的具体作法是，在式( 1 5 ) 中，将目标函数f ( x ) 的真实下降量与其 二次模型g ( d ) 的预估下降量的比值_ 改用下面的公式计算 r k ：a r e d k ：每兰粤掣，( 1 - 9 ) = = 二二_ 一 p r e d k 石一g ( 以) 7 其中彳( i ) 5 厂“( t ) ) = m 圳a x 。) f ( x k 一) ，r e ( o ) = 0 ，0 _ r e ( k ) 0 ，b o r 胀”，常数0 c 3 c 4 1 c 1 ， 0 c ， l ，0 ，令k = 0 ； 6 中国石油人学( 华东) 硕士学位论文 s t e p 2 ：如果慨 | ，停止；否则，求解信赖域子问题( 1 - 4 ) 得解4 ； s t e p 3 ：计算厂( 以+ 巩) ，o h 果f ( x i + 以) f ( x t ) ，转s t e p 4 ；否则，按照某种线搜索规 则寻找最小的正整数z ，使得( + 矾) ( 气) ，其中翻( o ，1 ) 为正常数，计算 磁+ l = x k + 吹，a + l t l l x i + l x 女0 ，c 4 a i 】，转s t e p 5 ； f 女，r k q ，慨i i ； a c 3 l i d 女4 】， t ，那么令l i 衄圳i g , 2 t ，其中删解之得口2 网a k 则 以= 一嘶1 铲一网a k 瑰 但是，这里存在一一个问题，在实际问题中，何1 不一定存在，即使存在，当b 。的规模较 大或者是稠密矩阵时，计算b 一的工作量也会非常大，因此求解子问题模型( 1 4 ) 是非常 困难的而如果蛾是一个实的稀疏正定矩阵，那么按照上面的过程，信赖域子问题( 1 4 ) 的解就可以很容易地计算出来 9 第二章基于简单子问题模型的臼适应信赖域算法 为实现上述想法，利用拟牛顿法中矩阵修正技巧设峨一。= 幽曙( 磷书酲l 一，6 0 。) 是一个实对角正定矩阵，蛾一。= d z a g ( a b l 小a b l l ，一，a b k 。) 是一个实对角矩阵令 色= 吼一。+ 地则吼是一个对角矩阵令反近似满足拟牛顿方程，即求解 r a i nf y k 一。一玩以胛， ( 2 1 ) 其中以一。= 以一一，儿一。= 瓯一g h 同时，为保证玩是正定的，将磷的取值限定在一 定范围之内，即令o l 玩z ，v i = l ，2 ，玎，其中量和z 是常数于是式( 2 _ 1 ) 变为 即 鳓墨蛩。i k 一一一盈矾一- | | 2 ， 娥邮m i u l , i = 1 , 2 - - n 善( y o ( 反_ l + 舶2 ， 求解式( 2 3 ) ，得 ( 2 2 ) ( 2 3 ) ( i ) 当九。时，若量篆i 氨则= 老越。；若老 z ，则噬一；= z 一磋一。； 一。 ”1” ( i i ) 当。= o 时，取6 l 一。= 0 这样，我们就得到了一个实对角正定矩阵b k = b 一。+ 峨_ l ，且近似满足拟牛顿方程显 然，计算所1 的工作量非常小再由前面的分析，我们就可以很容易地得到信赖域子问 题( 1 4 ) 的一个近似解 基于上面地分析，我们构造一个简单的信赖域子问题模型 卿珐( d ) # 低) + g ；d + p b k 也 ( 2 - 4 ) s t f i d l l a 。， 其中毋是实对角正定矩阵，且满足式( 2 2 ) 显然，求解子问题( 2 4 ) 所需的存储量和计算 量要少于求解子问题( 1 4 ) ，且子问题( 2 4 ) 的近似解可以很容易的得到因此，我们称子 问题( 2 4 ) 为一个简单的信赖域子问题模型 1 0 中国石油人学( 华东) 硕士学位论文 2 2 信赖域半径自适应调整策略 在信赖域算法中，信赖域半径的调整策略也是一个十分重要的内容，它关系到信赖 域算法的收敛速度在第七次迭代，令d 。表示信赖域子问题的一个近似解，定义目标函 数的实际下降量 a r e 以= f ( x k ) - f ( x k + 以) ( 2 5 ) 和预估下降量 p r e d k = q k ( 0 ) 一级( 矾) ( 2 6 ) 两者的比值定义为 r k ：尝：磐唉掣 ( 2 7 ) p r e 砍珐( o ) 一q ( 以) 、。 传统的信赖域半径调整策略是：给定参数0 r ， r h l ，o 届 l 厦，其中r l ， 仍，届，屈是常数，令 f 屈t ，r k i 2 ， ( 2 - 8 ) 【t ，刀ls 咯s7 7 2 上述调整策略仅仅以常数倍扩大或缩小信赖域半径，没有充分利用当前点的信息， 比如目标函数在当前点的一阶、二阶导数因此，许多学者提出了自适应信赖域算法 s a r t e n a e r t 2 6 1 提出了一个自动确定初始信赖域半径的算法，并研究了初始信赖域半 径对算法有效性的影响范金燕和袁亚湘【2 8 】给出了信赖域半径收敛到零的算法算法中 取川= 版+ jj k + ，j l ，其中o c 2 l ，o 巳 1 c 6 ， f c s 以，r k 吉i ， l 从， 其它 章祥荪、张菊亮和廖立志删提出了另一个新的自适应信赖域算法，取信赖域半径 a 。= c p 恬洲何1 0 ，其中o c 1 ，p 是非负整数每次迭代时只需要调整p 的值，即，当 试探步被接受时，令p = 0 ，否则，令p = p + 1 第_ 章基于简单子闯题模型的臼适应信赖域算法 受文献 2 8 】 3 0 】的启发，本章给出一个新的信赖域半径的自适应调整策略，该策略 充分利用了当前点的一些信息给定参数0 碾 7 7 2 1 ，o 兀 l 携，令 川= 从+ 。i i g 卅i 。0 ， ( 2 - 9 ) l x 乜，r k r h ， 【从，r 1 r k 砚 2 3 算法模型 r a i nq k ( d ) ：= f ( x k ) + g ；j + p 色d ， ( 2 _ 1 0 ) s 1 1 4 - 0 ， 0 ，0 玩 7 7 2 1 ，0 托 1 兄， 0 量 l ，令k ：= 0 ； s t e p 2 若恬 8 ，则停；否则，转s t e p 3 ； s t e p 3 求解信赖域子问题( 2 一1 0 ) ，得解以，由式( 2 5 ) ，式( 2 6 ) 和式( 2 7 ) t - t - 算- r , ； s t e p 4 若咯 r l ，则 以+ l = 兀以， ( 2 一1 1 ) = 版+ 。黻2 8 ， ( 2 - 1 2 ) 转s t e p 3 ；否则，转s t e p 5 ； s t e p 5 令以+ l = 以+ 巩，求解式( 2 2 ) 得到反+ l ，令 1 2 中国石油大学( 华东) 硕士学位论文 篾，糍 p = 段+ 舨+ l | l 。， ( 2 - 1 4 ) k ：= k + 1 ，转s t e p 2 注2 1 “s t e p 3 一s t e p 4 一s t e p 3 ”称为内循环 注2 2 如果在算法2 1 的信赖域半径调整部分使用式( 2 8 ) 、范金燕等和章祥荪 等t 3 0 j l 钓策略则得到相应的基于简单模型的信赖域算法，记为s t t r 、s f j y 和s z x s 2 4 全局收敛性 在这一部分，我们将在一般条件下讨论算法的全局收敛性 假设h 2 1 对任意给定的而r ”，水平集( ) = 缸i ( x ) f ( x 。) ) 有界，且对任意 给定的x o r ”，( j c ) 在l ( x o ) t - _ 连续可微 假设h 2 。2w ( x ) 在r ”上一致连续 引理2 1a r e 巩- p r e 么= o ( 1 l d , 1 1 2 ) 证明由式( 2 5 ) ，式( 2 6 ) 和t a y l o r 展式知，引理成立口 引理2 2 设 反 是南算法2 1 产生的序列，则反是正定矩阵，且互刮或| | l 证明由b k = 成昭( 6 l ，瑶，鬈) 和0 量碳l ，( i = l ，2 ，刀。) 知，引理成立口 设当前进行第七次迭代，定义c a u c h y 点 “= 一觋a k 跏 其中 f 1 ， g 。t 俄g t o ， 铲b 甚趣“地 由引理2 二蛾是正定的，因此有气= m i n t 面坚磊，t ， 引理2 3 对c a u c h y 点，我们有 1 3 第一：章基于简单子问题模型的自适应信赖域算法 幺( o ) 吲朋净堋m i n ，黜) 证明下面分两种情况进行证明 髁悬 三盟 一2 l i g k l l 2 | | 反 l = 2蚓l 扣o m i n ，a i g k l l ) 如果旦扎那么 a 女g ：b g 。 瓦叫“一尚联r b 舨 0 因此有 f ( x t ) - f ( x i + 1 ) r lp r e 以。 由式( 2 6 ) 和引理2 4 ，有 p r e 矾= g ( o ) 一g ( 以) 0 ， 这意味着厂( 以) 一( 以+ ，) o ，即( 效) ( 以+ i ) 由矗l ( x o ) 知，f ( x k ) 佃) ， 从而。l 。i m 扣( ，) = i 因此，对充分大的f ，有气( ，) 叩，这与式( 2 1 6 ) 矛盾引理得证口 1 6 中国石油人学( 华东) 硕士学位论文 定理2 1 设h 2 1 和h 2 2 成立。如果= 0 ，那么算法2 1 或者有限步终止，或者产 生无穷点列 ) ，满足 l i 。m 。扣i n f g = 0 ( 2 1 7 ) 证明若算法2 1 有限步终止，则定理成立以下假设算法2 1 产生无穷点列 若式( 2 - 1 7 ) 不成立，则存在0 0 ，满足 g t 忙岛，v k ， 由引理2 2 、引理2 4 和引理2 6 知， + o o f ( x k ) - - f ( x k + 。) 】_ 一 。 矗= l 因此 ( 赡) 一f ( x k + 。) 】 - e 7 7 1 q k ( 0 ) - q k ( d k ) 专碾恢 i m i n 料 = 驯陂l l m i n 讹慨1 1 1 1 8 ；10 ，黼 鲁m i n b t 一) ， m i n t k ，l 扣 七e j ( 2 1 9 ) 如果j 是有限集，由算法2 1 知，对充分大的k ，有t t , + 。= 7 , , u k 于是 1 i m 从= 0 ( 2 - 2 0 ) 枷 如果j 是无限集，由式( 2 1 9 ) 戋1 1 ， l i m u k = 0 cj 再由式( 2 1 1 ) 和式( 2 一1 3 ) 可以得到式( 2 - 2 0 ) 由引理2 2 、h 2 2 、式( 2 1 2 ) 、式( 2 1 4 ) 和式( 2 2 0 ) ，有熙t2 0 因此有 一i _ l 箐l 1 7 ( 2 - 2 1 ) 第_ 章基f 简单子问题模型的自适应信赖域算法 ，这与式( 2 2 0 ) 矛盾定理得证口 2 5 超线性收敛速度 定理2 2 设厂( 工) 是二阶连续可微的函数，且由算法2 1 产生的序列 坼 收敛于石， v 2 f ( x + ) 是正定矩阵若 牌掣= o ， ， 则 x 。 超线性收敛于x + 证明由条件知，j m 聊 o 使得对慨q ，= x l l l x x | | ) ，为一d t e , j 、的常数 硎例2 z r v 2 o ) z - m l l z | | 2 ，v z er ”，( 2 2 3 ) 且存在充分大的正整数氏，使得对v 七七0 有噍q 。由巾值定理知，对v 七有 别x k - - x * 卜五川x ) 三叫卜x + j j 2 ，( 2 - 2 4 ) 且 所恢0 8 2 - k o 有 1 8 中国石油大学( 华东) 硕士学位论文 胁一v 2 f ( x k ) ) d 。| | 驯1 吼 由式( 2 2 6 ) ，式( 2 - 2 9 ) ，引理2 4 及m o ，故式( 2 _ 2 7 ) 成立下证，当七充分大时，7 7 ， 五一f ( x k + 喀) 一( g ( o ) 一q ( 以) ) = 扣砸。一v 2 m 枷以+ 扣丁( v 2 似沪v 2 弛。+ g d k ) ) d t ， ( 2 - 2 8 ) ( 2 2 9 ) ( 2 - 3 0 ) 其中点( o ，1 ) 由瓴 是收敛的知，d k o ( 露一o o ) 再由v 2 ( x ) 连续和式( 2 2 2 ) 矢1 1 六一f ( x k + 以) 一( g ( o ) 一g ( 矾) ) = 。( 1 l d , 1 1 2 ) 由式( 2 2 7 ) 和式( 2 31 ) ，有 l 屹一l l = 从而 1 9 ( 2 3 1 ) o ( i f a 节, l ( ) ，( 2 - 3 2 ) 。4 d , 1 1 2 第二章基丁简单子问题模型的臼适应信赖域算法 l i m r k = 1 t 0 4 ( 2 - 3 3 ) 因此，当露充分大时有咯r 1 再由算法知，对充分大的七，信赖域半径。是增大的，即 对充分大的k ，存在正常数口满足 a 口 ( 2 3 4 ) 由条件和定理2 1 知， i m l l g t i i = 0 由引理2 2 知， b ) 一致正定，冈此! 到j 反一g 。1 1 = o ， ! i 1 。l i ，m 。d , i i = 0 由中值定理有 g l + i = g t + b k d k + ( v 2 f ( x 女) 一b t ) d 女+ e i v 2 ( x t + t a r ) 一v2 ( x 女) d k d t = ( v 2 f ( x t ) 一b k ) d k + “v 2 厂( + 峨) 一v2 厂( ) h a r t 。 再由v 2 f ( x ) 的连续性知，8 9 k + l i l - l l m 2 ( 故) 一反) 破8 + 。( 1 l d 。1 1 ) ，即 饼掣+ 等 亿3 5 ， l 一lf q 叫 由式( 2 2 2 ) ，式( 2 3 5 ) 知 l i mi i 丽g , + , i i = 。 再由式( 2 2 9 ) 知，。l i r a i l 牿g , 。+ 4 , i i = 。由式( 2 2 5 ) ，有 。翱mi 谢 一x 8 l 令七一喁! 鲤黼一o 她愀性收敛定理觚口 2 6 数值试验 ( 2 3 6 ) ( 2 3 7 ) 在这一部分，8 1 j 用m a t l a b 7 0 编写程序，对算法2 1 进行了数值试验，并与算 f 杰- s t t r 、 s f j y 、s z x s 进行了比较数值试验问题来自于f 3 l 】f 3 2 】 h p 1 f ( x ) - ( 3 - 2 x ) x ，一再i - 2 h 。+ 1 】2 i = 1 x o = ( - 1 ，一l ，- 1 ) r ，f - - 0 ，l = o 7 2 ，一l = 2 5 9 1 2 0 中国石油大学( 华东) 硕士学位论文 h i 2 p 2 厂( x ) = i 一工：2 h ) 2 + ( 1 - x 2 h ) 2 】 x o = ( - 1 2 ，l ，1 ，一1 2 ，1 ) 7 ，f = 0 一l = 1 3 8 6 1 ，l = 5 9 9 6 9 nh p 3 ( x ) = 甩一c o s x j + i ( 1 - c o s x , ) - s i n x , 2 i = l j = 1 = ( 1 n ，l 刀，i n ) ? ，f + = 0 ，一l = o 3 9 4 9 ，l = 8 7 9 9 8 3 n ，2 p 4 ( x ) = 慨一x ：( 1 - x ：，) 】2 + y ：x 2 棚一磅) 】2 “乃一x ：h ( 1 一爰，) 】2 y l = 1 5 ，y 2 = 2 2 5 ，y 3 = 2 6 2 5 ，x o = ( 1 ，l ，1 ) r ，f = o ，l 一= 6 。9 0 4 2 ，l = 2 9 6 9 8 3 h ，1 0l o j l p 5 ( x ) = ( 1 - x z o 一) 2 + ( 1 - - x l 。，) 2 + ( 弓一。) 2 】 x o = ( - 2 ，- 2 ，一2 ) 7 ，f = 0 ，一l = 1 3 4 4 1 ，l = 8 0 0 8 9 在所有的算法中，停机准则均为| i 夥( 以) 4 1 0 - 6 ，b o 取为单位矩阵，初始信赖域半 径。= 恬。| i 对算法2 1 ，取参数为扬= o 2 ，仍= o 8 ，苁= o 5 ，7 2 = 2 ，m = 1 对算法 s t t r ，取参数为玩= o 2 ，仍= o 8 ，屈= o 5 ，屈= 2 对算法s f j y 和s z x s ，参数的取值 与文献【2 8 】和【3 0 】中的相同 对每一个数值试验问题，我们都给出了维数n = 1 0 0 ，5 0 0 ，1 0 0 0 ，5 0 0 0 ，1 0 0 0 0 ，2 0 0 0 0 时 的数值计算结果，见表2 1 表中的k 、n f y d l f o p t 分别表示算法的迭代次数、函数值的计算 次数和目标函数的近似最优值 由表2 1 ，我们可以看出，对p l ，算法s f j y ( 当n = 5 0 0 0 ，1 0 0 0 0 ，2 0 0 0 0 时) 和算法 s z x s ( 当n = 5 0 0 ，1 0 0 0 ，5 0 0 0 ，1 0 0 0 0 ，2 0 0 0 0 时) 的数值结果并不理想，目标函数近似最优值 的计算精度很低，可以认为迭代失败而对所有的试验问题，算法2 1 的迭代次数都少于 其他算法，且计算精度相当 因此，算法2 1 的数值效果好于其他的算法，并且从数值试验结果可以看出基于简 单子问题模型( 2 1 0 ) 的新的自适应信赖域算法适于求解大规模问题另外，在实验过程 中我们发现，参数的和z 选取对算法的结果有一定的影响，适当的选取参数值能够加 快算法的收敛速度 2 1 第二：章基于简单子问题模型的自适应信赖域算法 表2 - 1 算法2 1 、s t t r 、s f j y 和s z x s 的数值计算结果 算法2 1s t t rs f j y s z x s pn k n f f o p t k n f f o p t k n f f o p tk n f f o p t p l1 0 01 5 l 1 6 5 1 7 2 e 1 419 6 2 3 3 9 2 5 e l5 5 3 6 5 3 7 4 7 6 e 15 211 2 2 4 5 4 3 3 e 一1 5 5 0 02 7 5 2 9 6 8 3 0 e 153 0 9 3 4 5 8 7 6 e l57 5 2 7 5 3 1 5 5 e 1 44 4 9 5 0 9 0 o 7l3 1 0 0 04 4 0 4 5 7 9 0 1e 1 5 4 2 3 4 6 0 8 2 3 e 15 9 7 4 9 7 5 1 4 6 e 1 44 5 4