（运筹学与控制论专业论文）一类修改的信赖域算法.pdf

一类修改的信赖域算法 摘要 信赖域方法是近二十年来发展起来的一类重要的数值计算方法。由于 具有很好的可靠性、强适性，以及很强的收敛性，目前它和传统的的线搜 索方法并列为求解非线性规划的两类主要的数值计算方法。本文主要研究 一个修改的b f g s 公式在信赖域方法中的应用，其结构如下： 第一章，回顾了信赖域算法的基本思想和研究状况，根据韦增欣等给 出的新的拟牛顿方程，给出了一个新的b f g s 校正公式，并分析了相关性 质。 第二章，结合新的校正公式，我们提出一种求解无约束优化问题的非 单调的b f g s 信赖域方法，并证明该方法求解非凸极小化问题的全局收敛 性。该算法的优点是信赖域子问题的目标函数是一个严格凸二次函数，因 而信赖域子问题的求解相对容易。而且，我们在不假设迭代矩阵序列有界 的前提下建立算法的全局收敛性定理。 第三章，将修改的b f g s 公式与a r m u o 线搜索相结合，得到一个新的 信赖域算法。在适当条件下，证明了该算法具有全局收敛性和超线性收敛 性。数值结果表明此算法对无约束优化问题是有效的。 关键词：b f g s 方法信赖域方法线搜索全局收敛性超线性收敛性 ac l a s so fm o d i f i e dt r u s tr e g i o nm e t h o d s a b s t r a c t t r u s tr e g i o nm e t h o di sa ni m p o r t a n tn u m e r i c a lm e t h o dd e v e l o p e do v e rt h el a s tt w o d e c a d e s b e c a u s eo fi t sr e l i a b i l i t y , r o b u s t n e s sa n ds t r o n gc o n v e r g e n c e ，t r u s tr e g i o nm e t h o d ， t o g e t h e rw i t hl i n es e a r c hm e t h o d ，h a sb e c o m eo n eo ft h et w om a i nn u m e r i c a lm e t h o d sf o r s o l v i n gn o n l i n e a rp r o g r a m m i n g w em a i n l yd i s c u s st h ea p p l i c a t i o no fam o d i f i e db f g s f o r m u l at ot r u s tr e g i o nm e t h o d t h et h e s i si so r g a n i z e da sf o l l o w s ： i nc h a p t e r1 w er e v i e wt h eb a s i ct h o u g h ta n dr e s e a r c ho ft h et r u s tr e g l o nm e t h o d a c c o r d i n g t ot h en e w q u a s in e w t o ne q u a t i o np r o p o s e db yw e ia ta l 。w eg i v ean e wm o d i f i e d b f g sf o r m u l aa n da n a l y z et h ec o r r e s p o n d i n gp r o p e r t i e s i nc h a p t e r2 ，c o r r e s p o n d i n gt ot h en e wf o r m u l a , w ed e v e l o pan o n m o n o t o n eb f g s t r u s t - r e g i o nm e t h o df o rs o l v i n gu 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 ag o o dp r o p e r t yo f t h e m e t h o di st h a tt h eo b j e c t i v ef u n c t i o no ft h et r u s t - r e g i o ns u b p r o b l e mi sas t r i c t l yc o n v e x q u a d r a t i cf u n c t i o n c o n s e q u e n t l y , i ti sr e l a t i v e l ye a s yt os o l v et h es u b p r o b l e m w ee s t a b l i s ha g l o b a lc o n v e r g e n c et h e o r e mf o rt h em e t h o dw i t h o u tr e q u i r e m e n to ft h eb o u n d e d n e s so ft h e g e n e r a t e dm a t r i xs e q u e n c e i nc h a p t e r3 c o m b i n i n gt h em o d i f i e db f g sf o r m u l aw i t l la r m i j ol i n es e a r c h , w e p r o p o s ean e wt r u s tr e g i o nm e t h o d , a n dp r o v et h a tt h ea l g o r i t h m sa r eg l o b a la n ds u p e r l i n e a r c o n v e r g e n c eu n d e rs o m em i l dc o n d i t i o n s p r e l i m i n a r yn u m e r i c a lr e s u l t ss h o wt h a tt h em e t h o d i se f f i c i e n ta n da d v i s a b l ef o rn o n l i n e a ro p t i m i z a t i o n k e yw o r d s b f g sm e t h o d ；t r u s tr e g i o nm e t h o d ；l i n es e a r c h ：g l o b a lc o n v e r g e n c e ； s u p e r l i n e a rc o n v e r g e n c e 符号 冗 册 r “。“ i i 钆 t 0 r g k 舻 f k 俨” v 2 ，( 矿) 舻。4 ，j p 。“ 符号说明 含义 实致集 n 维实数空间 实数域上的礼维矩阵空间 自然数集 绝对值 欧几里德范数 第k 个迭代点 巩点的信赖域半径 z t 点的函数值 z t 点的梯度值 孤点的h e s s i a n 矩阵或其近似 矿点的h e s s i a n 矩阵 单位矩阵 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导_ 卜完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均己在论文中明确说明并致谢。 论文作者签名。阀 学位论文使用授权说明 年，月2 ，日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口面时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 赦储鹕：阀哟聊摊： 胡年i 月矿日 广西大学硕士学位论文 一嘉修改的信槭域算法 第一章绪论 1 1 信赖域算法的研究概况 信赖域方法是非线性优化的一类重要的数值计算方法它在近二十年来受到非线性优 化领域许多研究者的关注，是非线性优化的研究热点与线搜索相比，信赖域有两个突出 的优点：一是它有很强的稳定性和强适性，二是它具有很强的收敛性由于信赖域的有界 性，它可以处理非凸的近似模型目前，信赖域方法已经和传统的线搜索方法并列为非线 性规划的两类主要数值方法 信赖域方法的研究起源于p o w e l l1 9 7 0 年的工作【1 】，他提出了一个求解无约束优化问 题的算法，该算法在每次迭代时强制性地要求新的迭代点与当前的迭代点之间的距离不 超过某一控制量引入控制步长是因为传统的线搜索方法常常由于步长过大而导致算法 失败，尤其是对于病态问题后来，人们发现信赖域方法的基本技巧在一定意义下等价于 十分著名的求解非线性最小二乘问题的e v e n b e r g - m a r q u a d t 方法【2 】 1 9 8 2 年，f l e t c h e rr 提出了用信赖域法求解复合非光滑优化( c o m p o s i t en o n s m o o t h o p t i m i z a t i o n ) 问题，他给出了一个模型算法【3 1 ，并在模型二次函数的h e s s e n 矩阵一致有 界的条件下证明了该算法的全局收敛性 关于非光滑优化的信赖域方法的研究，已经得到一系列结果，可参考文献睁7 】1 9 9 8 年，袁亚湘和n o e e d a lj 合作，首创性地提出了用信赖域方法和传统的线搜索方法相结合 来构造新的计算方法，并依此给出了一个利用信赖域以及回溯( b a c k - t r a c k i n g ) 技巧来求 解无约束优化的算法【8 】这是综合了两大类方法优点的一个大胆尝试 上面提到的信赖域方法都有一个共同的特点。那就是为了保证算法的整体收敛性，都 要求算法的每一步迭代全是。成功迭代。( s u c c e s s f u li t e r a t i o n ) ，即新的迭代点能保证目 标函数值或价值函数值比当前的值要严格单调减少然而，人们在实际计算中发现：对于 某些问题，这样做并不能保证算法是有效的例如，对著名的检验函数一r o s e n b r o c k 函 数，若用通常的信赖域方法求解，则当迭代点接近最优点时，收敛速度变得非常慢，出现 类似于m a r o t o s 效应的现象1 9 9 3 年，邓乃扬等人利用非单调性策略【9 】，首次提出了一 类具有强收敛性的非单调信赖域算法该算法的数值实验表明：非单调性策略对相当一部 分实验函数可以明显加快算法在其最优点附近的收敛速度，得到精度更高的最优解这一 工作是开拓性的，有关非单调信赖域方法的其他研究成果都是它的推广或修正【1 0 - 1 5 】 1 广西大学硕士学位论丈 一粪修改的信赖域算法 除上述的信赖域方法外，教学工作者们还提出了另外几种方法，如s 曲线搜索信赖域 方法 1 6 】，即在信赖域范围内采用曲线路径搜索下一个迭代点而得到具有整体收敛性的算 法；自适应信赖域方法【1 7 1 ，即每次迭代时都充分利用当前迭代点的信息自动产生一个恰 当的信赖域半径在此区域内，二次模型与目标函数尽可能一致，从而避免了盲目的搜索 尝试，提高了计算效率信赖域方法的第一本专著由c o n n ，g o u l d ，t o i n t 【1 8 】给出，关于 信赖域方法的综述文章可见文【1 9 】 考虑无约束最优化问题： 删m i n ? m ) ， ( 1 1 ) 其中f ( x ) 是定义在j p 上的连续可微函数利用二次逼近，可构造信赖域子问题如下， 1 m i n q 女( d ) = 去矿鼠d + f f d s t i i d l l sa k ， ( 1 2 ) 其中g k = v ，( 巩) ，b k j p “是实对称矩阵，a k 0 是信赖域半径解子问题( 1 2 ) 得 到试探步呶然后令 p r e d k = 瓠( o ) 一q k ( d k )( 1 3 ) 为预测下降， a r e d k = ，( z ) 一，( 孤+ d k )( 1 4 ) 为实际下降再定义实际下降和预测下降的比率为 = p 氅r e d k ( 1 5 ) 信赖域方法利用这一比值的信息来调节信赖域半径粗略地讲，仇越大，呶使函数f ( x ) 下降就越多，因而可考虑扩大信赖域半径t 反之，则得考虑拒绝接受以，并缩小信赖 域半径t 利用上述原理，我们给出求解无约束优化问题( 1 i ) 的信赖域算法的一般步骤如下： 算法1 1 ( 见【2 0 】) 步1 ：给出：c o r ，i ，a 1 0 ，e 之0 ，0 c 3 c a 1 0 ，则信赖域算法产生一个满足一阶和二阶必要条件的 聚点z 。 1 2b f g s 算法及其修改形式 拟牛顿法是目前应用最广泛，理论上也最为成熟的方法之一其一般迭代形式为： x k + l = z + q d k ， 其中毗是步长，出是搜索方向，由线性方程组鲰+ 鼠d k = 0 决定风是h e s s i a n 阵 g ( x ) 的近似，满足拟牛顿方程 b k + l $ k 。弧 3 ( 1 6 ) 广西大学硕士学位论文一套修改的信鞭域算法 其中g k = v f ( x k ) ，3 k = 酞+ 1 一瓢，鲰= g k + 1 一g k b k 的不同修正方式将构成不同的拟 牛顿法，其中b f g s 方法被认为数值效果最好的方法，该方法的校正公式为 b k + l 风一雩s k 擎2 s k 8 k + 攀y k8 k ( ) j 校正公式( 1 7 ) 具有一个重要性质如下： 设b k + l 是由b f g s 校正公式产生，若矩阵且k 是对称正定阵且靠s k 0 ，则k + 1 也 是对称正定的 校正公式( 1 7 ) 使得鼠保持正定是非常重要的若k 正定，则目标函数，的局部 二次模型就是严格凸的，有唯一的局部极小点，算法产生的搜索方向以就是，在z 处 的下降方向我们知道，鼠正定的充分必要条件是靠s 女 0 显然，若，是一致凸函 数，则总有y t s 女 0 成立，而与线搜索无关；对于非凸函数，则当采取精确线搜索或 w o l f e - p o w e l l 非精确线搜索时，靠s 0 也成立此时，相应的拟牛顿方向是函数，在 z 处的下降方向 在文【2 4 】中，韦增欣等利用目标函数f ( x ) 的t a y l o r 展式； ，( z ) 型，( z 七十1 ) + v ，( z i + 1 ) r 扛一z 七+ 1 ) + 互1 一z 七十。) rv 2 ，( z 七+ ，) ( z z + ，) 其中取z = 张，即得 s 看v 2 f ( x 州) s 竺 由此，给出一类新的拟牛顿方程： 其中 2 f ( x ) 一f ( x + 1 ) 】+ 2vf ( x k + 1 ) r s 2 f ( x ) 一，( z 女+ 1 ) 】+ g k + l + 鲰】r 8 k + s 暑鲰 鼠+ 1 3 - = 以= y k + a k 8 女 小坠尘错乒监， ( 1 8 ) ( 1 9 ) 修改拟牛顿方程( 1 8 ) 比拟牛顿方程( 1 6 ) 有更高的精度，这点从下面来自文【2 4 】结论中 不难得到 定理1 2 1 若鼠+ l 满足( 1 8 ) 和( 1 9 ) ，则有 f ( x k ) 一m 州) + v ，( 钆+ t ) r 一坼。) + ；( x k - - x k + 1 ) r 鼠+ tx k - - x k + 1 ) 4 广西大学硕士学位论丈 一类# g - 改的信较域算法 定理1 2 2 若函数f ( x ) 是光滑的，b k + 1 满足( 1 8 ) 和( 1 9 ) ，则当0 s 0 充分小的时 候。有 s t u 州s k 一t 2 = j 1s 暑( 疋+ - s t ) s 女+ o ( 1 1 s t i l 4 ) 孵l s 丢g s k s 看鲰：。：( 疋+ l s 。) 。k + o ( 1 1 钆i i t ) ， 其中瓦+ 1 是，在张+ l 点的张量，满足： s 看( 死+ 1 8 k ) s k = s 溉s 0 文【2 5 j 在一定条件下证明了文【2 4 中拟牛顿算法的超线性收敛性 受公式( 1 8 ) 的启发，我们先作如下修改： b k + l = 鼠一挚s k j k 8 k + 蓑， ( 1 1 0 ) 颤4s t 其中虻= 丧；旨以，以= y k + a k s k 由瞻的定义，显然有 y ：t 8 k = 锚珊s 删i 我们知道取具有正定遗传性当且仅当虻t 钆 0 为了保证b k 的正定性，我们给出新 的占k 校正公式如下： 晰：j 取一鬻+ 瓣艨乳o ( 1 1 1 ) i 玩，否则 显然k + 1 继承了b k 的正定性 本文主要研究无约束优化问题的信赖域算法，我们给出了两种结合修改的b f g s 公 式的信赖域算法，并傲出了算法的收敛性分析 在第二章中我们将修改的b f g s 公式和非单调技术应用到信赖域方法中，提出了一 个新的非单调信赖域算法在不需要假设矩阵序列 b k 有界的情况下，我们证明了算法 的全局收敛性数值结果表明此算法对某些问题要优于传统的非单调信赖域算法 在第三章中我们结合a r m i j o 线搜索。给出了一个修改的b f g s 信赖域算法在不需 要假设矩阵序列 鼠) 有界的情况下，我们证明了算法的全局收敛性和超线性收敛性数 值结果表明算法对于无约束优化问题是有效的 5 广西大学硕士学位论丈 一奏修改的信赖域算法 第二章一种非单调的信赖域方法 2 1 算法 最近，l i 和f u k u s h i m a 在文献f 2 6 ，2 7 1 中修正了b f g s 公式，提出了m b f g s 和 c b f g s 公式，并证明了这两种b f g s 方法求解非凸极小化问题的全局收敛性l i 和q i 基于上述m b f g s 方法和c b f g s 方法，提出了一种b f g s 信赖域方法【2 8 1 ，无须假设 取) 有界就证明了该信赖域方法对非凸目标函数全局收敛和超线性收敛文献1 2 9 也给 出了一个修改b f g s 的信赖域算法，并证明了算法的全局收敛性和超线性收敛性但是， 他们都只讨论了单调的b f g s 信赖域方法，即要求f ( x k + 1 ) ( x k ) 本章。我们提出一种求解( 1 1 ) 的非单调b f g s 信赖域算法，与已有的非单调信赖域 算法相比，本章算法具有如下优点：( 1 ) 能够保持风的正定性( 2 ) 全局收敛性所需的 假设条件更弱 在给出算法之前，先定义 五( 叼= ，( 观( 砷) ；o g r l l a m x ( 砧，( 孤叫) ， ( 2 1 ) 其中m ( k ) = m m m ( k 一1 ) + 1 ，m ) ，m ( o ) = 0 ，m20 为给定的整数 下面给出算法的计算步骤 算法2 1 ( m b s 非单调信赖域算法) 步0 ：给定初始点2 ：0 j p ，s o 为对称正定阵，给定常数：l ，e 2 ，。，m 见 1 ， m 0 ，丁1 l 0 ，因此鼠总是对称正定的，从而子问题( 1 2 ) 有唯一解d k 由约束条件的最优性条件，存在乘子a k 0 使得t b k d k + a k 也一 ( 2 3 ) 1q ( 1 l d k l l 一) _ o 。 由上式可知 。t = - - g t 可d k - r d ：k b k & , ， ( 2 4 ) 即 d 蚕b k d k + 靠d k = 一o f k l i d k i l 2 0 故有 弧( 呶) = 1 2 露b - 以+ 。 也 0 使得 i i g ( x ) 一g ( y ) l i i | z 一可玑坛，q ( 2 7 ) ( 3 ) ：存在a ( 0 ，1 ) ，角0 ，尾0 及风0 使得对所有t 历l l d , 1 1 2 d ，鼠d i 屈i l d , 1 1 2 ，j i s , d , l i 风i i 函f |( 2 8 ) 对至少n 明个i 值成立，其中 k 将【1 ，叫中使得不等式( 2 8 ) 成立的下标从小到大依次记为： 0 0 瓦= l i 2 靠) ，k = u 玩= i l i 2 m ， 使得对所有k 0 均满足 高狐警鳞 ( 2 1 3 ) 则对于任意的a ( 0 ，1 ) ，存在常数展 o ( i = l ，2 ，3 ) ，使得对任意k 0 ，至少有n 明个 i ( 其中i k ) 满足不等式 卢l l l d , 1 1 2 砑玩反s 恳l l d , 1 1 2 ，j f 最也0 岛l l d , 1 1 ( 2 1 4 ) 引理2 2 3 假设点列 z 女) 由算法3 1 产生，其中岛是对称正定阵则存在正常数 m m 和m 7 ，使得对所有k 0 均满足 m i l s k l l 2 冬虻t s m l l s 1 1 2 ，l i v ；l i m 7 l l s m( 2 1 5 ) 广西大学硕士学位论文一舞修改的信鞭域算法 且对任意a ( 0 ，1 ) ，存在常数屈 0 ( i = 1 ，2 ，3 ) ，使得对任意七0 ，至少存在【a k 】个i 值 满足( 3 4 ) ，其中i k 证明：由嫉的定义和( 2 1 2 ) 可得 炳t = 篱啪s 扣 ( y k + a k s k 几一 = i s t 鲰+ 2 f ( x t ) 一，( z k + 1 ) 】+ ( g k + 1 + g k ) t s i = 2 f ( x k ) 一，( z 女+ 1 ) + 9 玉1 s i = 2 i 一函1 s k + 二i t g ( 6 1 ) 乳+ 靠+ 1 s i = s t g ( f 1 1 ) s k 卢l 恢限 ( 2 1 6 ) 其中6 1 = z k + 秽1 1 ( x k + 1 一z ) ，锣l l ( 0 ，i ) 同理可得 令m = 角，m = 岛，得到( 2 1 5 ) 中第一个不等式下面证明( 2 1 5 ) 中第二个不等式由 ( 2 7 ) 和( 2 8 ) ，可知 蚝0s m ，可将( 2 6 ) 写成： f ( z t ( 1 ( k ) - 1 ) ) 一，( 锄( 姊) ；p l d l ( k ) - i b t ( k ) 一1 d f ( ) 一1 ( 2 1 9 ) 9 广西大学硕士学位论丈一套修改的信粳域算藩 利用引理2 2 1 ，即得 l i r a 税 ) 一1 b l ( k ) 一l d l ( k ) 一1 = 0 由假设a 可知 ，l i mi id r ( k ) 一1i i = 0 k 1 ” 由于f ( x ) 一致连续，有 墨恐五( k ) 一l5 是恐五( t ) k r + 记2 ( 七) = l ( k + m + 2 ) 现在归纳法证明，对任意j 1 ，下面两式成立： 舰i i d r k ) - j l l = 0 ， ( 2 2 0 ) ( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) 墨恐，( 瓢铲) 2 占恐舶 ( 2 2 4 ) 如果j = 1 ，由于 f ( 矗) ) c z ( ) ) ，则由( 2 2 1 ) 及( 2 2 2 ) 容易得到( 2 2 3 ) 和( 2 2 4 ) 成立 假设对给定的j 使得( 2 2 3 ) 和( 2 2 4 ) 成立由( 2 6 ) 得 f ( x t ( f ( ) 一j 一1 ) ) 一，( 吼女) 。) ；n d 瓢) - j - 1 & t ) 一j 一1d f ( ) _ j 1 ( 2 2 s ) 同理可得 墨恐椎) 十1b f ( 妒d i ( 铲= 0 ( 2 2 6 ) 由假设a 可知 h l i m 。0d i ( k ) - j 一1 i l - 0 ( 2 2 7 ) 由，( 曲的一致连续性，得 k l 。i m 。f ( z i ( k ) - j 一1 ) 2 占恐，( 。“女) 一j ) 2 墨霉。五( ) ( 2 2 8 ) 因此，( 2 2 3 ) 和( 2 2 4 ) 对所有j21 成立由于对任意的詹，有 “ ) 一 一1 x k + l = 强k ) 一d f ( t ) 寸 ( 2 2 9 ) j = l 由l 的定义，有f ( 七) ( k4 - 1 ) = l ( k + m + 2 ) 一( 七+ 1 ) m 4 - 1 ，这意味着 l i m 。0x k + l x i ( k ) 0 = o ( 2 3 0 ) 广西大学硕士学位论丈 一类修改的信校域算法 因为f ( x ) 一致连续，则 t l 。i m 。f ( x k ) 2 是恐，( z 训2 是恐，( 锄( ) ) ( 2 3 1 ) 利用( 2 6 ) ，可得 五( ) 一f ( x k + 1 ) 2 去p 1 a c 手kb k d k 结合( 2 3 1 ) ，有 女l 。i m 。b k d k 20 由假设a 得 l i r a , oi i d ki i = 0 类似于文献 2 9 】中的证明，我们可得到下面的引理 引理2 2 5 如果假设a 成立，点列 z ) 由算法2 1 产生， 常数q ，晚臼使得 ( 2 3 2 ) ( 2 3 3 ) 对任意i t k ；，则存在正 c 2 l l 鳜。f l | l d “0sc 3 1 1 9 , 。0 ，o sc 1 ( 2 3 5 ) 证明；如果i l 屯i i a 。，由( 2 3 ) 可知o q 。= 0 及鼠。如= 一鲰结合( 2 8 ) ，得到 l i d , 。1 1 2s d 乏g 。l i d , 。i i i i g , 。0 以及 0 一皿。0 = i i g , 。i i 岛l i d , 。叭 令c a = 去sc 3 = 击，c l = 0 ，即可得( 2 3 2 ) 成立 假若i i d , 。0 = “，令乞= i i l i n 删。，t f l “ ，设也。7 为下面问题的解： n l i n ；矿民d + g 乏d s t i i d l l ，。 ( 2 3 6 ) 因为厶。 a i 。，显然有魄( 。) 饥( 屯) ，也就是 c i k t b i 。+ 鳐。；d i 。t b i 。屯+ 屯 一鲧屯；嚷民屯一鲠。( 扣+ 再l t i - - 2 ) 1 2 ( 2 3 9 ) 再利用( 2 8 ) 和( 2 4 ) ，得 帆雌嚷( 、 陵1 1 - + , 耍1 1 1 啦 c i j ；孝 ；喜+ - 川虮川“也川 =竖群等掣ii圳iip2 屁( 1 一) + 2 l 7 | f 2 * 川”“唯。 因此 i i 妃0 c 3 l l g , 。m 其中c 3 = 击尘瓮筹蓑帮由( 2 8 ) ，得到 | i 皿。i i i i b , 。也。0 + o “i t d , 。0 ( 风+ c 1 ) i i 也。i i 因此( 2 3 5 ) 成立 以下定理表明算法2 1 全局收敛 定理2 2 1 如果假设a 成立， z ) 由算法2 1 产生，则有 。l i mi n f l l 鲰l l = 0 ( 2 4 0 ) 1 2 广西太学硕士学位论文一奏修改的信赖域算法 证明；根据引理2 2 4 和( 2 8 ) ，有 ；古巴。l i d t i i2 墨恐l i d , t i i = 0 ( 2 4 1 ) 结合( 2 3 5 ) 和( 2 4 1 ) ，得到 lim一一iig,。ii=0ke k k _ o 。 因而( 2 4 0 ) 成立 2 3 数值结果 为了检验算法的有效性，在这一部分我们将给出初步的数值结果我们用文【1 3 】提 出的非单调信赖域方法( s n t r ) 和本章给出的算法2 1 进行比较，所有的测试函数来自于 文献【3 l 】 在进行数值计算时，我们对算法2 1 中的参数选取如下；p l = 0 2 5 ，化= o 7 5 ， n = 0 5 ，他= 0 2 ，e l = e 2 = 1 0 一，厶。= 2 0 0 0 9 ，初始信赖域半径取为l | 9 0 1 1 我们 分别在m 一2 ，m = 4 ，m = 6 ，m = 8 ，m = 1 0 的情况下得到两种算法的数值结果由 于m 达到一定值后，计算结果不再发生改变我们仅给出m = 1 0 的数值结果，其余类 似其中p r o b l e m 表示测试函数名，d i m 表示测试函数的维数，m 代表总的迭代次数， 扎，和嘞分别代表总的函数计算次数和总的梯度计算次数 1 3 广西大学硕士学位论丈 一娄修改的信赖域算法 室! ! 蔓些! ：! 笪墼笪笙墨f 塑丛三! 1 2 p r o b l e md i m s n t r 算法2 1 n t | n i | n n , - i - 9 b e a l e2 h e l i ) 【3 b a r d 3 b o x 3 s i n g 4 b d4 o s b 21 1 r o s e x1 0 0 5 0 0 s i n g x 1 0 0 v a r d i m2 0 0 5 0 0 i e 5 0 0 1 i d2 0 0 5 0 0 1 0 0 0 1 4 1 5 1 5 3 0 3 1 3 1 1 1 1 2 1 2 3 5 3 6 3 6 3 3 3 4 3 4 4 4 4 5 4 5 1 2 2 1 1 1 2 1 2 1 5 1 6 1 6 4 2 4 3 4 3 4 6 4 9 4 9 6 3 6 4 6 4 6 6 7 2 4 2 5 2 5 3 9 4 0 4 0 5 2 5 3 5 3 2 2 2 3 2 3 8 9 9 3 4 4 2 6 2 7 2 7 3 4 4 3 0 3 1 3 1 1 2 2 6 7 7 3 1 3 2 3 2 3 0 3 1 3 1 4 1 4 2 4 2 3 3 3 4 3 4 7 8 8 2 7 2 8 2 8 2 7 2 6 5 6 2 7 2 8 2 8 广西大学硕士学位论丈 一叁修改的信鞭域算法 在表2 中我们比较了算法2 1 中m = 2 ，m = 0 的两种情况及一般的信赖域方法( t r ) 的数值结果从表中可以看出，在许多情况下，非单调搜索比单调搜索要好，而且数值相 对稳定 表2 ：数值结果 1 5 广西大学硕士学位论太 一嘉修改的信赖域算鲁 第三章一个带线搜索的信赖域算法 3 1 算法 信赖域方法能够求解当k 不正定和z 为鞍点等困难的情况然而，当占k 不定时， 信赖域方法可能只有线性收敛速度【3 2 】当吼正定时，子问题有唯一解，此时可以利用 文献i s 3 中的方法求解如果目标函数，是强凸的，且当b 0 正定时，则由b f g s 公式 生成的b k 也是正定的文【8 】在采用a r m i j o 线搜索的b f g s 信赖域方法中建议，只有 当占k 1 的正定性得到保证时，才修正鼠，从而产生i k + 1 该算法的基本思想是；当试 探步不可接受。即 ，( + d k ) f ( x k ) 时，并不重新求解信赖域子问题，而是采用回退技术得到新的步长g e r t z 3 4 在信赖域 算法中采用了w o l f e - p o w e l l 线搜索技术，使得试探步也满足不等式 f ( x + d k ) ，( z k ) + p g t d k 和 矗1 d k a g t d k ， 其中，0 0 ，0 州。 o ( i = l ，2 ，3 ) ，使得对任意k 0 ，至少有协明个 i ( 其中i k ) 满足不等式 角| l 畦1 1 2 毋鼠破岛| | 画悒i b i d tj i 风函m( 3 4 ) 类似于第二章，我们引入下列记号； 将【1 ，叫中使得不等式( 3 4 ) 成立的下标从小到大依次记为； k k = i 1 i 2 缸，k = u 玩= i l i 2 0 0 = 1 ，2 ，3 ) ，使得对任意k 0 ，至少存在江叫个i 值 满足( 3 4 ) ，其中i 七 引理3 2 3 对所有的k ，试探步q k 满足 啦n l i n 1 半d ：k b 圳k d k ， ( 3 7 ) 其中l 0 是g 的l i p s c h i t z 常数 证明。显然，对所有的k 都有口 s1 如果a 1 ，则它由算法3 1 中步4 确定 根据线搜索规则，容易得到q p 不满足( 3 2 ) ，即 ，( z + p - * n 靠) 一f ( x k ) p - 1 0 k 甄t 以( 3 8 ) 由中值定理可知，存在靠( 0 ，1 ) 满足 ，( z k + p - 1 a d k ) 一f ( x ) = p - 1 a k g ( x k + & p a k d k ) r d k = p - 1 讯露如+ p - 1 0 幽+ 矗p 一1 , ，k d k ) 一船】t d k p - * n 9 也+ p - 1 0 j jg ( x k + f k p 一1 0 七d k ) 一g k ) id 七0 p - 1 a k g 吾d k + 蠊p - 2 n 纠呶0 2 p - 1 0 t k g d k + l p _ 2 q 纠也n 由( 3 8 ) 我们可以得到 q t 学瓣- - g t d k 结合( 2 5 ) ，得到( 3 7 ) 下面的定理证明了采用标准b f g s 校正公式的信赖域线搜索方法对一致凸函数的全 局收敛性问题 定理3 2 1 如果f 二次连续可微且一致凸， z k ) 由标准b f g s 信赖域线搜索方法产 生，则 z t ) 收敛到( 1 1 ) 的唯一解 证明：因为算法3 1 保证了 ，( 孤) ) 单调递减，且，一致凸，所以只需证明 ，l i r am f l l g k l l = 0 ( 3 9 ) 因为，是二次连续可微的凸函数，则存在常数m 0 及m 0 ，使得不等式( 3 3 ) 对所有k 成立因此，由( 3 5 ) 定义的指标集k 是无限集另外从( 3 4 ) 和( 3 7 ) 可知， 对所有l k 。有 q m i n 1 ，( 1 一a ) p 卢l l 一1 ) 三丘 0 1 8 广酉大学硕士学位论丈 一蠢修改的信赖域算告 下面分两种情况讨论： ( 1 ) ，如果( 3 1 ) 成立，则对所有i k ，我们有 f ( x i ) 一，( z 件，) q ( 儡( o ) 一吼( 也) ) 2 ；t i l t i id , 1 1 2 ( 3 1 0 ) ( 2 ) ，如果( 3 1 ) 不成立，则 f ( x i ) 一f ( 3 7 件1 ) 2 一盯q i 毋哦口o q d b f 也盯a 伪i id f 1 2 ( 3 1 1 ) 因此存在常数p 0 ，使得对所有i k ， ，( 毛) 一f ( 3 7 , + 1 ) p0 噍0 2( 3 1 2 ) 成立由于序列 ，) ) 单调递减，它的极限存在于是得 埏i f l i m ；。i l d i i = o ( 3 1 3 ) 注意到，对所有t ，氆。机成立则对任意i k ，不等式j i d , ij 厶对所有充分大 i k 成立结合( 2 3 ) ，我们得到o ：i = o ；另外，从( 3 4 ) , - 7 j $ l i g d i = i i b , d , i l 岛i l d d l ( 3 1 4 ) 结合( 2 3 5 ) 和( 3 1 3 ) ，就可得到l i m i n fl l 鲰0 = 0 定理3 2 2 假设a 成立，点列 z ) 由m b s 信赖域算法产生，则 1 i mi n f i i g , , i l = 0 + ( 3 1 5 ) 证明：由f ( 3 7 k ) 的下降性，得 瓢) cq 有界如果( 3 1 5 ) 非真，则存在6 使得i i g , , i i 6 对所有成立根据引理3 2 1 ，类似定理3 2 1 的证明，推出矛盾，从而结论成立 我们将在下一节讨论算法3 1 的超线性收敛性 3 3超线性收敛性 在这一节中，我们将给出算法3 1 的超线性收敛性为此，我们先作出如下假设 假设b ： ( 4 ) ：由算法3 1 产生的序列 z k ) 收敛到3 7 。，且v ，( 矿) = 0 ( 5 ) ：函数，在矿的邻域内二次连续可微，且v 2 f ( x ) 正定 1 9 广西大学硕士学位论太一奏修改的信鞭域算告 ( 6 ) ：h e s s i a n 矩阵c ( x ) 在r 处h 6 1 d e r 连续，即存在正常数 ，妒使得不等式 i l g ( z ) 一g ( z + ) 0 妒i i z z i i ”( 3 1 6 ) 对于矿邻域内的任一点z 成立 引理3 3 1 若假设b 成