（运筹学与控制论专业论文）求无约束优化问题的一类非单调信赖域算法.pdf

摘要 捅要 对一般的无约束优化问题而言，信赖域方法是一类有效的方法。由于它具 有较好的可靠性和很强的收敛性，在近三十年来受到了最优化研究界的重视。 目前，信赖域方法已经和传统的线搜索方法并列为非线性规划的两类主要数值 方法。信赖域半径的选取对信赖域方法的效率有着很大的影响。迄今为止，经 过国内外许多学者的研究，已提出多种信赖域方法：拟牛顿信赖域方法，信赖 域内点方法，自适应性信赖域方法，非单调信赖域方法等。本文给出一类新的 非单调信赖域算法，进一步丰富了信赖域方法的研究。 第一章对无约束优化问题的线搜索方法进行总结；第二章回顾信赖域方法的 基本思想，理论及有关研究成果；第三章我们将非单调线搜索技术与自动确定信 赖域半径的方法相结合来构造了一类求解无约束优化问题的非单调自动确定信 赖域半径的算法，并研究其全局收敛性；第四章中提出的算法是在每步都采用非 单调w o l f e 线搜索技术得到下一个迭代点，这样得到的新算法不仅不需重解子问 题，而且在每一步迭代满足拟牛顿方程的同时保证目标函数的近似h e s s i a n 矩阵 b k 的正定性。在适当的条件下，证明了此算法的全局收敛性。 关键词：无约束优化问题，线搜索，非单调信赖域方法，全局收敛性 a b s t r a c t t h et r u s tr e g i o nm e t h o di sak i n de f f i c i e n t u 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 s b e c a u s e a n dr o b u s tm e t h o dt os o l v et h eg e n e r a l o fi t sr e m a r k a b l en u m e r i c a lr e l i a b i l i t y i nc o n j u n c t i o nw i t has o u n da n dc o m p l e t ec o n v e r g e n c et h e o r y , r e s e a r c h e r si nn o n l i n e a r o p t i m i z a t i o na r e ah a v ep a i dg r e a ta t t e n t i o nt oi t t h ep a s t3 0y e a r s a tp r e s e n t ，劬s t r e g i o nm e t h o d sa n dl i n er e s e a r c hm e t h o d sa r e t w om a i n l yt y p en u m e r i c a la l g o r i t h m s f o rn o n l i n e a rp r o g r a m m i n g t h ec h o i c eo ft h et r u s tr e g i o nr a d i u sh a sa ni m p o r t a n t e f r e c to nt h ee f f i c i e n c yo ft h et r u s tr e g i o nm e t h o d s t i l ln o w ，a f t e rm a k i n gg r e a t e f f o r t s ，m a n yr e s e a r c h e r sh a v ep r o p o s e dm a n y k i n d so f t r u s tr e g i o nm e t h o d s ，s u c ha s q u a s i - n e w t o nt r u s tr e g i o nm e t h o d ，t r u s tr e g i o ni n t e r i o rp o i n tm e t h o d ，n o n m o n o t o n e t r u s tr e g i o nm e t h o d ，s e f - a d a p t i v et r u s tr e g i o nm e t h o d ，a n ds oo n an e wk i n d o f n o n m o n o t o n et r u s tr e g i o nm e t h o dw h i c hf u r t h e re n r i c h e st h er e s e a r c ho nt h i sa r e ai s p r e s e n t e di nt h i st h e s i s i nc h a p t e r1 w em a k eac o n c l u s i o no ft h el i n e a rr e s e a r c hm e t h o do f u n c o n s t r a i n e d 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 r2 ，w em a i n l yr e v i e wt h e b a s i ci d e a , m a i nt h e o r i e sa n d c o r r e s p o n d i n gr e s e a r c hr e s u l t so ft r u s tr e g i o n m e t h o d s i nc h a p t e r3 ，w ec o m b i n e a d a p t i v et r u s tm e t h o da n dn o n m o n o t o n e l i n e a rr e s e a r c ht op r o p o s ean e wm e t h o dt o r u i l c o n s t r a i n e do p t i m a lm e t h o d ，a n ds t u d yi t sg l o b a lc o n v e r g e n c e i nc h a p t e r4 ，w e p r e s e n t aq u a s i n e 、t o nn o n m o n o t o n et r u s tr e g i o na l g o r i t h m u n l i k et r a d i t i o n a l n o n m o n o t o n et r u s tr e g i o na l g o r i t h m s ，o u ra l g o r i t h mg e t st h en e x tp o i n tb y t h e n o n m o n o t o n ew o lf el i n er e s e a r c ha te a c hi t e r a t i o n u n d e rt h i sc o n d i t i o n ，w ep r o v et h e g l o b a lc o n v e r g e n c e 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 ；l i n e a rr e s e a r c h ；n o n m o n o t o n et r u s t r e g i o nm e t h o d ；g l o b a lc o n v e r g e n c e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，l i p 学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后遵循此规定) 签 名： 垂轻 导师签名： 日 第一章绪论 第1 章绪论 1 1 背景知识及主要结果 最优化理论与方法是一门与当今社会密切相关的年轻学科。它讨论决策问题 的最佳选择及特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质 及实际计算表现。它一般是指在某种状况下做出最好决策。具体的说，就是把现 实生活中的实际问题转化为求在一定的约束条件下，使得目标函数最小( 或最大) 的解。虽然最优化可以追溯到十分古老的极值问题7 】【8 】，但直到1 9 4 7 年d a n t z i g 提出一般线性规划问题的单纯形法之后，它才成为一门受人关注的独立的学科。 随着现代科技的发展和计算机的广泛应用，进一步推动了最优化理论和算法的研 究。今天，最优化理论与方法在经济计划、工程设计、政府决策、生产管理、交 通运输和军事国防等重要领域都得到了广泛的应用脚】，已经成为一门十分活 跃的学科。 一般来说，最优化问题可归结为求解如下的极小值问题： m i nf ( x )( 1 1 ) x d 其中，x d 是决策变量，f ( x ) 为目标函数，d r 。为可行域。 根据变量的类型，最优化问题可分为连续型最优化问题和离散型最优化问题 ( 也称组合优化问题) 。连续型最优化问题又可分为目标函数和约束函数均为线性 函数时的线性规划问题，以及目标函数和约束函数中至少有一个是变量x 的非 线性函数时的非线性最优化问题。当d = r “时，下列最优化问题： m i nf ( x ) ( 1 2 ) x r “ 即为无约束优化问题，是本文主要研究的问题。 下面我们给出全局最优解和局部最优解的定义： 定义1 1 若x + d 具有性质：v x d ，均有f ( x ) f ( x ) ，则称x 为问题 ( 1 1 ) 的全局最优解 3 3 1 。 定义1 2 若x + d 具有性质： 北京工业大学理学硕士学位论文 存在x 的某个邻域，n 万( x ) = 酬l x x i l o 为某个正数，使得 v xd n n 占( x ) ，均有f ( x ) f ( x ) ，则称x 为问题( 1 1 ) 的一个局部最优解 1 3 3 1 。 当目标函数f ( x ) 是凸函数时，局部最优解就是全局最优解。但在一般情形 下找出全局最优解非常困难，通常在非线性优化中我们只能求得局部最优解。在 实际的算法中，通常是找出满足局部最优解的必要条件的点。若记g ( x ) = v f ( x ) 表示f ( x ) 的梯度，g ( x ) = v 2f ( x ) 表示f ( x ) 的h e s s i a n 矩阵下面我们给出这些必 要条件： ， 引理1 1 【1 1( 无约束优化一阶必要条件) 若x 为问题( i 2 ) 的一个局部最优 解，且在x 的邻域内f c 1 ，则 g ( x ) = 0 ( 1 3 ) 引理1 2 t 1 】( 无约束优化二阶必要条件) 若x + 为问题( 1 2 ) 的一个局部最优 解，且在x 的邻域内f c 2 ，则 g ( x + ) = 0 ，g ( x ) 0( 1 - 4 7 1 2 求解无约束优化问题的线搜索算法。 迭代法是求解无约束优化问题： r a i n f ( x ) x r n 的基本方法，在具体实现上可分为线搜索方法和信赖域方法两种不同的策略。我 们首先来看线搜索方法，它的基本思想是：对于当前的迭代点k ，首先确定一个 搜索方向d 。，使得目标函数f ( x ) 的值沿该方向是下降的，然后确定沿d 。方向行 进的步长丑并得到下一个迭代点瓦+ 。= 迄+ 以d 。在线搜索策略中关键的两步是 构造搜索方向d 。和确定步长以。事实上构造搜索方向和确定步长有许多种方法， 不同的方法构成了求解非线性规划的不同的算法。 第一章绪论 为了方便起见，我们作如下记号： = f ( x k ) ，g 。= g ( ) ( k ) = v f ( k ) ， y k2g k + l g k ， s k = x k + l x k = 口k d k ，g k = g ( x i 【) = v 2f ( x k ) 。 一般的，线搜索算法要求d 。是一个下降方向，也就是 v f ( ) ( t 【) 1d k o i nf ( x k + 朋k ) ( 1 6 ) 来得到。 若是精确求解( 1 6 ) 可以最大限度的发挥方向d 。的作用，但求( 1 6 ) 的精确 解通常是代价昂贵而不必要的，故人们通常满足于获得( 1 - 6 ) 足够好的近似解， 这一类方法通称为不精确线搜索方法。 针对不精确线搜索步长，人们提出了多种多样的线搜索规则，常用的非精确 搜索如下： 1 ) w o l f e 线搜索：固定，仃满足o p 矿 1 ，选取丑满足： if ( k + a k d k ) f ( x k ) + p a k g ( x k ) t d k 【g ( x 1 + 以d k ) t d k 昭( k ) t d k 2 ) 强w o l f e 线搜索：固定p ，口满足o p 仃 1 ，选取九满足： if ( k + 九d k ) f ( x k ) + p & g ( x k ) t d k 【ig ( ) 【k + 以d k ) t d ki - o g ( x k ) t d k 3 ) a r m i j o 线搜索，固定p ( o ，1 ) ，选取九满足： f ( x k + 以d k ) f ( x k ) + p 以g ( x k ) td k 4 ) g o l d s t e i n 线搜索：固定l ，2 ，0 l 0 ，占0 ，屈 l 及 0 ，0 屈 0 ，b r “对称，则d r n 是子问题( 2 1 ) 一( 2 2 ) 的充分必要条件是存在唯一的z 0 ，使得 ( b + z i ) d = 一g d ，且z ( 一i i d l i ) = 0 其中b + 彳i 是半正定矩阵。 关于此定理的证明可见【1 3 】。基于这一定理，可将求解信赖域子问题化为计 算满足( 2 1 ) 一( 2 2 ) 的，zn - 7 利用n e w t o n 法计算，具体算法已由【1 4 】和【1 5 】给 出。子问题的解具有很好的下降性质： 定理2 2 设d 是信赖域子问题( 2 1 ) 一( 2 2 ) 的解，则必有 妒( o ) 一矽( d ) - 专 i g l l m i n ，i l g l l l l b i l ( 2 3 ) g t d 一号l l g l l m i n a ，i l g l l 2 l l b l 1 ( 2 4 ) 不等式( 2 3 ) 的证明参见文献【1 6 】，不等式( 2 4 ) 的证明参见文献【3 】。 下面给出文献 3 1 q b 求解信赖域子问题( 2 1 ) 一( 2 2 ) 的非精确算法。 算法2 2 ( n o c e d a l & y u a n ) 1 5 1 步1 ：给出y 1 ，占 0 ，令彳：= 0 ；如果r 正定，转步2 ；否则，寻找 名【o ，i i b i i + ( 1 + c ) l l g l a ，使得b + m 正定； 步2 ：分解b + m = r t r ，其中r 为上三角矩阵，求解r t r d = 一g ，得d ； 步3 ：如果i l d i l a ，则停；否则求解r t d = q ，计算 9 北京工业大学理学硕士学位论文 名车力+ 蜂删兰 | | q i l 2 转步25 n o c e d a l 和y u a n 证明了这样求得的非精确解满足下面的性质： 引理2 1 1 3 1 d ( 五) = 一( b + m ) - 1g 是信赖域子问题( 2 1 ) 一( 2 2 ) 的非精确解， 满足 a i y i i d 1 ，或者 名 0 ，使得 矽( o ) 一矽( d ( 五) ) r l l g l l m i n a ，i l g l l l l b i l ( 2 5 ) g t d ( 旯) 一f o g0 m i n ，i l g l l l l b i l ( 2 6 ) 由此可见，求解信赖域子问题时，无论我们用何种技巧，选取的试探步d 。需要 满足式( 2 5 ) 一( 2 6 ) 。 信赖域子问题的求解可以分为近似求解与精确求解，前面已经介绍了精确求 解和一种非精确求解方法。近似求解方法还有折线法和在某一低维子空间上非精 确求解的算法等。 2 3 信赖域算法的全局收敛性 当接近局部最优解时牛顿法具有二阶收敛速度，但如果初始点很远就无法利 用牛顿法的快速收敛性。为了弥补这个不足，使算法具有全局收敛性，一种方法 是对牛顿法进行线搜索，另一种方法是在一系列局部区域内构造二次模型近似目 标函数，通过对模型求解逼近目标函数的最优点。这就是基于牛顿型的线搜索方 法和信赖域方法。信赖域方法的一个突出优点就是它具有全局收敛性，这样就可 以降低对初始点选取的要求。在无约束优化中，如果满足适当的假设条件，还可 l o 第二章信赖域方法简介 以得到信赖域方法二阶收敛的结果1 1 7 】【1 9 】。 定理2 3 8 1 ( 信赖域方法总体收敛性定理) 设gcr 。是有界集，x k g ，v k ， 若f c 2 ，在有界集g 上0b l 【0 ：m ，m o ，则信赖域算法产生一个满足一阶和 二阶必要条件的聚点x 。 定理2 4 t 8 1 如果定理2 3 中的聚点妒还满足f 的h e s s i a n 矩阵g 。是正定的条 件，那么，对于主序列，有r k 专1 ，x k _ x 。，g l b ( h k ) 0 ，以及对于充分大 的k ，约束l i s i l ： 0 是信赖域半径。 信赖域方法每次通过求解信赖域子问题得到试验步d 。，然后计算实际下降 量与预测下降量的比值7 】 d ：a r e d l ： n 2 而。2 1 1 羔2 二! ! 奎业 ( 3 3 ) 丸( 0 ) 一九( d 。) 它衡量了二次模型丸( d ) 目标函数f ( x k + d ) 的逼近程度，成越接近于l ，表 明接近程度越好，根据比值见决定是否接受试验步d 。以及对信赖域半径。进行 调节3 1 】【3 3 】。 在传统的信赖域方法的实现过程中，信赖域半径的选取是一个关键因素 1 3 5 】1 3 6 1 ，它直接决定着当前迭代的方向和步长。然而传统的信赖域方法中信赖域 半径的更新是根据比值见人为规定地按常数倍放大或缩小，没有利用 1 2 第三章一种非单调自适应性信赖域算法 g 。，巨，y k _ ，d 。一等变量包含的一次，二次导数信息呲1 。初始信赖域半径的选取 只是不加分辨地给一个常数。基于此，许多关于信赖域半径的自适应性算法被提 出1 2 8 1 3 们。 1 9 9 1 年，袁亚湘和n o c e d a lj 合作首创性地提出了用信赖域方法和传统的线 搜索方法相结合来构造新的计算方法，并以此给出了一个利用信赖域以及回溯 ( b a c k - - t r a c k i n g ) 技巧求解无约束优化问题的算法”6 1 。在传统的信赖域算法中， 当由子问题( 3 1 3 2 ) 求得的试验步d 。不被接受时，令x k 卅= x k ，缩小信赖域半 径重新求解子问题。然而求解信赖域子问题的代价很高，线搜索方法求解试验步 的计算量相对小一些，因此，在一定的条件下，当试验步不成功时我们用线搜索 来求得下一个试验步，这样有效的节省了计算量。不同于一般的带线搜索的信赖 域算法，新算法充分利用了仇的信息来调整信赖域半径的大小1 。理论分析和 数值实验都证明了新算法的有效性。 s a r t e n a e r 【3 8 1 研究了初始信赖域半径。的选取对算法有效性的影响，给出 了一个自动确定初始信赖域半径的算法的i t r r 算法，其基本思想是通过近似模 型( d ) 和目标函数f ( x o + d ) 沿负梯度方向的近似程度，调节初始信赖域半径。 章【1 1 】【1 3 】【3 7 1 等把这一思想应用到信赖域半径的自适应性。黑龙 1 提出当前迭代的 信赖域半径是使关于比值凤的函数与上次迭代的步长忙。一。0 乘积。章 1 3 1 7 等 提出另一个自适应性的信赖域算法，每次迭代信赖域半径。= c p0b l 一l l l g 。这 里c ( o ，1 ) ，p 是非负整数。如果上次迭代，试探步d 。_ 被接受，则p = 0 ，否则 p = p + l 。该方法的优点是如果p = 0 ，n e w t o n 步或拟牛顿步总是可行的，保证 了超线性收敛性。缺点是每开始一个新的迭代，信赖域半径总是置于充分大，与 成无关，增加了盲目尝试性旧，即很可能p k 很小，但。仍然充分大；此外， 每开始一个新的迭代，都要计算0 b l 【- 10 才能计算。 3 2 新算法的提出 北京工业大学理学硕士学位论文 考虑无约束优化问题：m i nf ( x ) ，其中f ：r “专r 是一个二次连续可微函 数。信赖域方法是一种比较稳定的迭代方法。一般而言，在当前迭代点x k 处， 信赖域方法通过求解下述信赖域子问题得到试探步d 。， 震蛩丸( d ) 2g k r d + l 2 d t b l 【d ， s t 帆忙a k ( 3 4 ) 其中g 。= v f ( k ) ，b l 【r “是近似于h e s s i a n 阵v 2f ( x ) 的对称矩阵，k 是信赖 域半径。 传统的信赖域算法的实现过程中，信赖域半径。与g 。、b i 【无关。因此每一 个迭代点k ，当它离最优点较远时，我们不知道拟牛顿步一k 1g 。是否可行。此 时，尽管检验条件满足，我们却不能接受它。这种情况会影响算法的效率。由此， 章祥荪等0 3 1 1 1 7 1 提出在求解信赖域子问题式( 3 4 ) 时将信赖域半径取为 a 。= c p i i g 。i i 吼t ，其中o c l ，p 为一非负整数，魄t = l i 训，氐是一个正定 矩阵。这里用调节p 来代替传统信赖域方法中对信赖域半径。的调节。 最近，张菊亮等及傅锦华等分别对文献 11 】引入两种不同的非单调技术，研 究非单调技术对文献【1 】中自动确定信赖域半径的信赖域算法的效率的提高。本 文借鉴文献【1 3 ，1 4 的思路，提出另一个新的非单调自动确定信赖域半径的算法， 每次迭代，a 拿a k - 夥黜忙。i i ，根据见的大小，适当调节。，并研究算法全局收 敛性。数值结果显示该算法是有效的。 下面给出本章重要算法： 算法3 1 非单调自动确定信赖域半径的信赖域算法： 步1 ：给定x r “，b i r 一对称，占0 ，0 c o 有界且目标函数f ( x ) 在水平集l ( ) 1 ) 上连续可微。 b ：矩阵序列 b l 【) 一致有界，即存在m 0 ，使得对v k ，有6 耽忙m 。 引理1 如果假设1 成立，在当前迭代点k ，有p r e d t 矛_ b 瓦i i g t i l 2 ，其 中m 。= 0b i 【0 ，p 。是当前迭代点) l c 到下次迭代点之间信赖域子问题被计算的次数 减去1 。 北京工业大学理学硕士学位论文 证明：由算法3 1 知，在当前迭代点) l 【处信赖域半径满足关系 一啦魁 因此五= 一孑专i g t 是信赖域子问题( 3 - 1 ) 的一个可行解。所以 、_ p r e d 。= g t d 。+ d ：1 3 k d k 锚t 。m 。+ 三五b 。瓦 = 一面1 恬t i l 2 + 志“g t 弘石1 m 。- i i 盯i i + 击i i “i t = 一石蠢i i g k | 1 2 。 从而引理1 获证。 弓i 理2 ”1 p r e d k = 丸( 0 ) 一九( d ) x k 万0 9 。 i m i n a 。，i i g 。i i i i b 。i i ，万 0 ( 3 5 ) 引理3 如果假设1 成立，则算法3 2 是成立的，即算法3 2 不会在“步3 步5 步3 ”这个循环内无限次循环。 证明：反正法。假设算法1 在迭代点x k 处于步3 至步5 之间无限次循环。 记k ( i ) 是当前迭代点x k 处的循环指标，则有r k ( i ) c 0i = l ，2 ，即 从而 有引理2 有 ，：鱼芸 业钒，i = l ，2 ， k o 一1 而i 一如0 悼1 厶 塾! 二垫垫! 血二垫垫! - - - c o , i = 1 ，2 ， (36，p r c d l 【( i ) p r e d k ( i ) 一7 i 盟畿p r e d 掣一l k ( 1 ) 1 6 第三章一种非单调自适应性信赖域算法 由 可知 一。( i ) | 1 2 ) 陬( o ) 一九( d l 【( i ) ) i 研ilminai i i i b 。i i ) ，一万慨k ( i ，慨 = 吉剀帖川州；专佃， 一i 专0 ( i 佃，。 从而有 里止竺苎盟 c 。，( i 专佃) p r e d l 【( i ) ”、 。 这与式( 3 6 ) 矛盾。故假设不成立，引理3 获证。 引理4 如果假设1 成立， 】k 为由算法3 2 产生的序列，则随) cl ( x ) ，v k 。 证明：当k = 1 时，由l ( x 1 ) = x lf ( x ) f ( x ) ) 知结论显然成立；假设当k m ， m 为任一正整数时，有x k l ( ) 【1 ) ，即f ( x k ) f ( x t ) ，k = 1 , 2 ，m 。则当k = m + l 时，根据r m = 玉盟掣 c 。，有： f i ( 。) o l + c o p r e d 。 o l ( 3 7 ) 因为l ( m ) m ，从而f ：( m ) 。由式( 3 7 ) 有f 叶。即x 叶。l ( 】( i ) 。由数学 归纳法可知，x k l ( ) ( 1 ) ，v k ，有引理4 获证。 引理5 如果假设1 成立，则 f ；( 。) ) 非增且收敛。 证明：由引理4 ，我们有 丘( k ) f k + l ，v k ( 3 8 ) 北京工业大学理学硕士学位论文 分情况讨论如f ： ( 1 ) 当k n 时，显然此时n k + l ，故n ( k ) = m i n n ，k ) = n ， n ( k + 1 ) = m i n n ，k + 1 ) = n 。 由( k ) 定义知 f l ( k + 1 ) 2 。j 翌瑟卜。 f k + - 一j = 。璺聚。 f ：【+ j ) = m a x f k + - ，f i 【，丘砣一n ， 2 。；黼_ f ：【一j = 。搿。 f k j ) = m a x f k ，f k 伽n ，k n ) ， 结合式( 3 8 ) 有 m a x 四鐾， 一j ) = f l 占。，v k ( 3 1 0 ) 1 8 第j 章一种非单调自适应性信赖域算法 由式( 3 1 0 ) ，假设1 中b 及引理1 可知， p r e d k r 1 。i i “i i 志2 。 记a = 嘉，则p r e d 。石a ， 记a ：皇) - ，则，i ， 2 m 4 吒 从而 即 因此 f i ( k ) f k + ! + c op r e d k 丘+ l + 石a c o f k + 一石a c o - ) ) - 万a c o 由式( 3 1 1 ) 及引理5 推出p l ( k ) 专- 卜o o ( k 专佃) ，故可以假设p l ( k ) 1 。 使得 ( 3 1 1 ) 由算法3 1 的定义，知道五( 。) 相应于下列子问题的解不可接受 m 。i r n 。硒t 。) ( d ) = g i 。) d + 三d t 商( 。) d 归忙掣捌北蚺， 否则不会在内循环内进一步修正以得到。( 。) ，也就是说 血掣掣 0 ，对充分大的k 有 d 。tb l 【d 。盯帆1 1 2 由于d 。是信赖域子i - j 题的解，故存在九0 ，满足 g k + 【魄+ 以1 ) d k2 0 从而 p r e d 。：要d jb l ( d 。+ & l i d 。1 1 2 利用v 2f ( x ) 的连续性和( 3 1 9 ) 可得 灯e d 。= 一g 。t d 。一妻d j v 2f ( x ) d 。+ o ( 1 l d 。1 1 2 ) ：p r e d 。+ 当d ：( r v zf ( x ) ) d k + o ( 1 l d 。1 1 2 ) = p r e d k + o ( 帆d 从而有! 骢见= 等_ 1 0 根据 1 2 1 ，由m o r e l 3 8 1 的结果可知算法3 1 是超线性收敛的。 3 4 数值实验 ( 3 2 0 ) ( 3 2 1 ) ( 3 2 2 ) 我们对算法3 1 进行了数值实验，并与传统的信赖域算法【6 1 作了比较。对于 这几个算法，我们都用n o c e d a l 与y u a n l l 6 1 中的算法2 6 求解信赖域子问题。我 们取b l 为单位矩阵， b k ) 由b f g s 公式来修正，即 b k + l b f g s = 龟+ 舞s k 一警掣ks i 魄s k 北京工业大学理学硕士学位论文 拙。电，- y k = g k + l - - g k 孔= h ，东： s k y k 01 对, b l = 巨。 实验问题来自于附录中的函数，参考文献 4 3 。所有算法的停机条件是 忙。i i - 1 0 ，表4 1 中，“f n ”、“g n 和“i t ”分别代表函数的计算次数、梯度 的计算次数和迭代次数。 表3 1 算法3 1 的计算结果 单调时的情形非单调时的情形( f n g n i t ) p r o b ( f n g n i t ) n = 3n = 5 n = 1 0 l7 06 05 35 3 24 13 53 63 6 33 93 63 33 3 43 8 3 93 5 3 5 55 84 54 34 2 64 42 82 92 8 73 83 53 4 3 3 s u m3 2 82 7 82 6 32 6 0 对于传统的信赖域算法吲，参数o 。= 1 0 ，我们用如下方式更新信赖域半径 aj，些悭，rk 0 为信赖域半径，对称矩阵b i 【r 是v 2f ( x k ) 或其近似 矩阵。上述子问题的最优解或近似最优解d 。是目标函数f ( x ) 在点x k 的搜索方向