（应用数学专业论文）无约束最优化问题的算法研究与实现.pdf

论文题目： 专业： 硕士生： 指导老师： 无约束最优化问题的算法研究与实现 应用数学 景慧丽( 签名) ： 王雪峰( 签名) ： 摘要 无约束最优化计算方法是数值计算领域中十分活跃的研究课题之一，快速地求解无 约束最优化问题，除了其自身的重要性外，还体现在它也构成一些约束最优化问题的子 问题。因此，对于无约束最优化问题，如何设计快速有效的算法一直都是优化工作者十 分关心的问题。 论文研究求解无约束最优化问题的非线性共轭梯度法，提出了两类新的非线性共轭 梯度方法，并讨论了这些方法的全局收敛性和数值表现。论文的主要工作如下： ( 1 ) 我们首先简要的介绍了求解无约束最优化问题的发展现状，回顾了论文将要 研究的问题的背景和已有结果，并介绍了论文的主要工作。 ( 2 ) 我们将传统的h s 算法和d a i y u a n 算法相结合，充分利用两者的优势，提出 了求解无约束最优化问题的一类混合型非线性共轭梯度算法。我们证明了该算法当采用 w - o l f e 型线性搜索方法时，不需要给定下降条件就具有全局收敛性，并用数值结果说明 了这类算法的有效性。 ( 3 ) 我们提出了几种改进的加m i j o 型线性搜索方法和一种改进的非线性共轭梯度 方法即m p i 冲方法。我们证明了m p r p 方法在改进的加m i j o 型线性搜索方法3 下求解 非凸极小化问题的全局收敛性。m p r p 方法的一个最重要的特征是能产生充分下降方 向，即搜索方向畋满足d f g 。= 一恬。n 这种性质不依赖所采用的线性搜索方法，这也 是论文提出的算法与已有的非线性共轭梯度法的主要区别之一。此外，当采取精确线性 搜索方法时，m p r p 方法退化为标准的p r p 方法。最后用数值结果说明了这类算法的有 效性。 关键词：无约束最优化；非线性共轭梯度法；线性搜索；全局收敛性 研究类型：理论研究 s u b j e c t ：o nt h em e t h o d sf o ru 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 i e m sa n d t h e i 体r e a l i z e s s p e c i a l t y ：a p p l i e dm a t h e m a t i c s n a m e ：j i n gh u i l i i n s t r u c t o r ：w a n gx u e - f e n g a b s t r a c t ( s i g n a t u r e ) ( s i g n a t ur e ) n 岫甜c a lm e t h o d sf o ru n c o n 咖i n e do p t i m i z a t i o ni sa i la c t i v es u 功e c ti nn 啪e r i c a l 狃a i y s i s ni sv e r ) ，i m p o n a n tt os o l v e 吼c o n s t r a i n e do p t i m i 刎i o nr 印i d l ya i l de 虢c t i v e l y w h i c hi sn o t0 1 1 l yi t s e l fo fg r e a ti i i l p o n a n c eb u ta l s oi tf o m ss u b p r o b l e m si nm a i l yc 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 s t h e r e f o r e ，h o wt od e s i g n 触龇de 仃e c t i v ea l g o r i t h m s f o r u n c o n s t r a i n e do p t i m i z a t i o ni s 觚i i l l p o r t a n tp r o b l e mt b a to p t i m i z a t i o nr e s e a r c h e r sc a r ev e 巧 m u c h i i lt h j sp 印e r ，w ep r o p o s e d 似on e wn o n - l i n e a rc o 巧u g a t e 伊a d i e n tm e t h o d sf o rs o l v i n g 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 w be s t a _ b l i s h e dt h e 酉o b a lc o n v e r g e r l c et h e o 巧f o rt l l e p r o p o s e dm e m o d sa r l dr e p o r t e de s t e n s i v ei m m e r i c a lr c s u h s t h em 句o rt a s k si nt l l i sp a p e r i 1 1 c l u i i e ： ( 1 ) w b i n 仃o d u c e dt h ed e v e l o p m e n to fn l eu n c o n s 仃a i n e do p t i l l l i z a t i o np r o b l e m s ，锄dt h e m 咖r e s u l t so b t a i n e di nt h i st h e s i s m o r e o v e r ，、) ，ei n t r o d u c e dt h eb a c k g r o u n da 1 1 dt h ea l r e l d y r e s u l t so ft h i sa n i c l ew o u l dn e e dt 0s t u d y ( 2 ) w 色p r e s e m e dah y b r i dc o 珂u g a 土eg r a d i e n tm 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 b a s e do nh e s t e n e s s t i e f e l a l g o r i t l l l i l a i l dd a i y - 啪a l g o r i t l i i l ，州c hh a dt a k e nm e a d v a n t a g e so ft l l e 铆oa l o 面t l l n l s w bp r o v e di tc a ne n s u r et l l ec o i e 唱e n c eo ft 1 1 ei l e w m e m o d su n d e rt 1 1 ew 6 l f el i n es e a r c ha n d 讪t h o u tt h ed e s c e n tc o n d i t i o n a d d i t i o n a l l y ，o u r p r e l i m i n a r yn 啪e r i c a le x p e r i m e m sw e r ec a r r i e do u t ，、 ，：i l i c hs u g g e s t e dt h a tt h ea l g o r i m mw 邪 v 甜i d i 够 ( 3 ) s o m em o d i f i e da m 坷ot y p el i n es e a r c h2 h 1 dam o d i f i e dn o n l i n e a rc o n j u g a t e 黟a d i e n t m e t h o dw h i c hi sc a l l e dm p r pm e t h o d 、e r ep r o p o s e d i i la d d i t i o n ，ag l o b a lc o r e 唱e n c e t t l e o 巧f o rt h em p r pm e t h o d 谢t hm em o d i f i e d 加m i j ot ) ，p el i n es e a r c h3 、a sp r o v e d a n i m p o i r t 觚tp r o p e n yo ft i l em p r pm e t l l o di st h a ta te a c hi t e r a t i o n ，t l l em e t h o dc a i lg e n e r a t ea s u f f i c i e n td e s c e n td i r e c t i o n 以w 1 1 i c hs a t i s 鸟i n g d 二g t = 一恬t1 1 2 t h i sp r o p e n y i si n d e p e n d e n t o fl i n es e a r c hu s e d w h i c hi sa l s oo n eo fm em a i nd i 能r e n c e sb e t w e e nt h em p r pm e t h o da 1 1 d t l l ek n o w nn o n l i n e a rc o 玛u g a t eg r a d i e n tm e t l l o d s m o r e o v e r ，i fe x a c tl i n es e a r c hi su s e d ，t h e m p i 冲m e t h o dr e d u c e st 0t h es t a n d a r dp i 冲m e t h o d f i n a i l y o l l re x p e r i m e n t a lr e s u l t s 谢t n e s s e dt h ea p p l i e dv a l u eo ft h i sn e wm e t h o d 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 n o n - 1 i n e a rc o n j u g a t e 鲈a d i e n tm e m o d s t h e s i s ：t i l e o r yr e s e a r c h g l o b a lc o n v e 唱e n c e 符号表 符号表 本文所用的符号，除文中特殊说明外，均按如下规定： 尺”：n 维向量空间 x ：n 维列向量 厂g ) ：目标函数 x 7 ：向量的转置 曰r ：矩阵的转置 召一：矩阵的逆矩阵 x ：最优化问题的最优解 ：第七次迭代点 吒：第七次迭代的步长因子 或：第七次迭代的的搜索方向 以：函数厂g ) 在处的函数值 & ：函数厂g ) 在稚处的梯度向量夥g 。) | i | | ：向量或矩阵的范数且：g r x 声 m i n ( x ，y ) ：x ，y 中取较小的数 m a x 阮y ) ：x ，y 中取较大的数 v ：任意的 了：存在 ：无穷和 瓯+ 。= g g ) y t2g i + 1 一g t 荆= 夥皓( 掣，掣 2戗1 i i 妻料技丈学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究t 作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名嘎懑伤日期：巧f 7 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者躲喜兹确毫蚋 研年了月日 1 绪论 1 绪论 追求最优化目标是人类的理想，最优化( o p t i m i z a t i o n ) 就是从众多可能方案中选择最 佳者，以达到最优目标。最优化理论和方法是第二次世界大战后迅速发展起来的一门新 兴的应用数学分支，它是一门应用性很强的年轻学科。虽然最优化可以追溯到十分古老 的极值问题，但是直到1 9 4 7 年d 趾t z i g 提出一般线性规划问题的单纯形法之后，它才成 为一门独立的学科。近三、四十年来随着现代科技的发展和电子计算机的广泛应用，进 一步推动了最优化的迅猛发展及其理论和算法的研究。今天，最优化理论与方法已经广 泛地应用于国民经济的各个部门和科学技术的各个领域中，它已渗透到生产、管理、商 业、军事国防、政府决策、交通运输、经济规划等方面，成为一门十分活跃的学科。 一般来说，最优化问题可归结为求解如下的极小值问题： m 填厂( x ) 工j 9 。 其中，x d 是决策变量，厂( x ) 为目标函数，d r ”为可行域。 根据变量的类型，最优化问题可分为连续型最优化问题和离散型最优化问题( 也称 组合最优化问题) 。连续型最优化问题又可分为目标函数和约束函数均为线性时的线性 规划问题，以及目标函数和约束函数中至少有一个为非线性时的非线性最优化问题。又 根据可行域d 的类型，非线性最优化问题可分为约束最优化和无约束最优化问题。 对于最优化问题，实际应用最广的就是按可行域d 的的类型来分类的约束最优化和 无约束最优化问题。由于无约束最优化计算方法不仅本身有着不少实际应用，而且与约 束最优化计算方法也有着紧密的联系：一方面，有些处理无约束最优问题的方法能够直 接推广而且应用于约束最优化问题；另一方面，还可以把一些约束最优化问题转化为无 约束最优化问题来处理。因此从这个意义上讲，无约束最优化计算方法也是处理约束最 优化问题的基本方法。 研究求解无约束最优化问题的有关理论和算法，在近几十年来迅速发展并同趋成 熟。随着计算机的发展和普遍应用，作为一种有效的最优化方法，无约束最优化方法在 工程设计、管理优化、系统分析等多方面的应用同益开拓，愈来愈受到应用部门的重视， 所以研究无约束最优化问题的计算方法是意义重大的。下面我们简单的介绍一下无约束 最优化问题的发展现状。 西安科技大学硕士学位论文 1 1 无约束最优化问题的发展现状 无约束最优化问题的一般模型为： m i p 厂g ) ( 1 1 1 ) 托r ”。、7 其中只”为力维欧式空间，厂( x ) ：足”专犬为连续可微函数。 在过去的几十年里，涌现出许多的比较优秀的解无约束最优化问题( 1 1 1 ) 的算法。 对于所有的求解无约束最优化问题的算法，都需要用户给定一个初始点五，用户根据实 际问题的应用背景和数据来源等一些信息，可能更容易给出问题解的一个比较合理的估 计，否则的话，初始点的选取将是任意的。 从初始点而出发，最优化算法将产生一个迭代点列k 。在算法迭代过程中，如果 发现不能进一步提高当前迭代点的质量，或者已经得到一个相当精度的解的近似，就终 止算法。在当前迭代点处，如何决定下一个点+ 。? 算法通常是利用目标函数厂g ) 在 当前迭代点z 。处的信息，包括函数值、一阶导数和二阶导数等信息，或者也可能利用在 迭代过程中已经得到的关于迭代点j c l ，x ：，一。的一些信息，利用这些信息去得到下一 个点+ 。，使得在点+ ，处目标函数几) 具有比在点也处更小的函数值( 也有一些非单 调算法，它们不要求目标函数值每一步都有一定的下降，而是要求目标函数值在连续的 聊步之内必须有好的下降，即要求厂k ) u 即要求下一个迭代点是搜索方向以上的精确极小值点。由于使用精确线性搜索计算量非 常大，特别是当迭代点远离问题的解时，精确地求解一个一维问题的解通常不是十分有 效的。另外，很多最优化方法，如牛顿法和拟牛顿法，其收敛速度并不依赖于精确线性 搜索过程，故而在实际计算中往往使用非精确线性搜索方法。下面我们就简单地介绍几 种常用的确定步长因子吼的非精确线性搜索方法。 ( 2 ) 加m i j o 型线性搜索 加m i j o 型线性搜索即为：给定o p l ，求步长因子= m a x 7 ，j f = o ，1 ，2 ， 满足 不等式 厂g t + 口i d t ) 厂g 。) + 6 口g ；以 ( 1 3 2 ) 其中o 万 1 。 ( 3 ) w 6 l f e p o 、e l l 型线性搜索 5 西安科技大学硕士学位论文 w | o l f e p o w e n 型线性搜索即为：求步长因子口。满足 g t + 吒以) 厂g t ) + 融。g ；以 ( 1 3 3 ) 和 g g + 口 以) ，d t 昭；d ( 1 3 4 ) 其中0 艿 盯 l 是两个常数。粗略的说，( 1 3 3 ) 式是为了保证算法在每次迭代都能够 有满意的下降，而( 1 3 4 ) 式是保证步长因子吼不会太小，因为如果步长因子吼太小， 可能导致算法收敛于一个非稳定点。 ( 4 ) 强w r o l f e 型线性搜索 强w 0 1 f e 型线性搜索即为：求步长因子吼满足 厂g 。+ 以) 厂g 。) + 沈。g ：畋 ( 1 3 5 ) 和 l g k + 以) 7 1 矾l 盯陂以i ( 1 3 6 ) 其中o 万盯 l 。当仃= o 时，必有g 五。巩= o ，因此强w b l f e 型线性搜索可看成是精 确线性搜索的一种推广。 ( 5 ) 推广的w o l f e 型线性搜索 推广的w r o l f e 型线性搜索即为：求步长因子口。满足 厂g t + 口或) 厂g 女) + 6 口。g ；d i ( 1 3 7 ) 和 仃l g ；d t g g 女+ 口 d 女) 7 d t 一仃2 9 ；d t ( 1 3 8 ) 其中盯l p ，1 ) ，仃2 o 。当仃。= 盯：时，推广的w r o l f e 型线性搜索就是强w o l f e 型线性搜 索；当仃，= 佃时，推广的w 6 l f e 型线性搜索就是w b l f e 型线性搜索。 ( 6 ) g 0 1 d s t e i n 型线性搜索 g o l d s t e i n 型线性搜索即为：求步长因子a 。满足 厂g + 口 畋) 厂g ) + 融t g ；以 ( 1 3 9 ) 和 厂g 。+ 口。d 。) 厂g 。) + ( 1 一万b t g ；丸 ( 1 3 1 0 ) 其中o 万 是常数。 z 精确线性搜索在理论分析时具有重要意义，但是，由于它具体实现起来计算量很大， 6 1 绪论 因此在实际计算中，一般采用加m i j o 型线性搜索和w r o l f e 型线性搜索等非精确线性搜 索方法。有关上述那些线性搜索方法的实现方式可参见文献 3 】。 我们称满足d ：g 。 o 的搜索方向畋为下降方向，称总是能产生下降方向的算法为下 降算法。由搜索方向以的定义，我们容易知道，当采用精确线性搜索方法时，有 g ；也= _ l 陪。1 1 2 o ，万 o 和p ( 0 ，1 ) ，令 一a x p 7 掣乒叫， 4 使其满足 和 厂g ) 厂g 。) 一毋到以1 1 2 ( 1 4 3 ) 一c 。恬g m 2 g g ) r 畋+ 。一c ：恬g 2 ( 1 4 4 ) 其中0 c 2 o 为常数。 h a g e r 和z h a i l g 在文献 2 5 】中证明了h z + 方法满足：g ；巩一割g t l l 2 ，而且这种充 分下降条件不依赖于任何的线性搜索方法。此外，h a g e r 和z l l a l l g 还提出了一种近似的 强w b l f e 型线性搜索方法并且给出了大量的数值结果f 2 5 】，这些数值结果表明h z + 方法在 这种近似的强w 6 l f e 型线性搜索方法下表现非常好，甚至比l b f g s 方法和p r p 十方法 还好。尽管如此，h z + 方法与p i 冲+ 方法、d l + 方法及y r 方法一样不再是一种标准的共 轭梯度法，而是一种修j 下的方法，在精确线性搜索方法下，它不能退化为相应的标准的 h s 共轭梯度法，其全局收敛性的证明类似于d l 十方法和y r 方法的证明。 ( 4 ) c d 方法 共轭下降法首先是由f l e t c h e r 在1 9 8 7 年引入的，简称为c d 方法，这种方法的一个 很重要的性质是：只要强w | 0 l f e 型线性搜索准则即式子( 1 3 3 ) 和( 1 3 4 ) 中的参数仃 o ，d a i 和m 【5 6 】发现，这时恼。旷 可能以指数级数增长。由此，他们给出了一个一般性的证明，表明对任意的正常数仃， 线性搜索方法满足( 1 3 7 ) 和( 1 3 8 ) 式的共轭下降法必不收敛。此外，他们还构造了 一个凸二次目标函数厂( x ) 的例子，说明条件q o ，使得 l i g g ) 一g 翊0 x 一少8 v x ，y u ( 1 5 1 ) 由假设1 5 1 ，我们容易得到，必存在正数，使得 l i g g 】l _ v x 三 ( 1 5 2 ) 下面我们给出本文所需的定理。 定理1 5 1 设目标函数厂g ) 有下界，且其梯度函数g g ) 满足l i p s c l l i t z 条件，即存 在常数三 o ，使得 0 9 g ) 一g 】l 0 x y 0 v 戈，y r ” 考虑迭代格式+ 。= 坼+ 口。以，其中搜索方向以满足g ；以 o ，步长因子吒满足w b l f e 型线性搜索方法( 1 3 3 ) 和( 1 3 4 ) 式，则有 y 篮垡 佃 ( 1 5 3 ) 钉1 2 其中，关系式( 1 5 3 ) 称为z o u t e n 叫k 条件。下面我们来证明定理1 5 1 。 证明由式子( 1 3 4 ) 可知 bk n 9 0dk = g ：“d 。一g ：dk 昭：吮一g ；d 女 = p 一1 k ；以 ( 1 5 4 ) 又由l i p s c l l i t z 条件即恬g ) 一g ) i i 驯x y i i ，有 1 4 1 绪论 瓴+ 。一g 。) 7 以吼1 2 所以，由式子( 1 5 4 ) 和( 1 5 5 ) 可得 即 p 一1 k ；以吼三l 阢0 2 啦孚爵 f k f k n 一砘k g ：dk 根据式子( 1 5 7 ) 及0 万 盯 1 可得 m 。掣静 即 羽镨 ( 1 5 5 ) ( 1 5 6 ) ( 1 5 7 ) ( 1 5 8 ) ( 1 5 9 ) 其中c = 亟 型。对( 1 5 9 ) 式从后= l ，2 求和，并注意到目标函数厂g ) 有下界，且 批掣为徽所燃丢瞥 0 由某种线性搜索得到，下降方向反由下式得到 巩= 二三：+ 履畋一。 妻茎三 c 2 2 2 ， 其中反= 夥k ) ，参数屈为标量。孱的不同取法对应于不同的非线性共轭梯度法，著 名的有f r 方法、p r p 方法、h s 方法、c d 方法、l s 方法和d y 方法。其中h s 方法和 d y 方法的参数厦由以下公式计算： 胪= 铡 包2 ( 2 2 4 ) 其中i l j f 是欧式范数。 当目标函数厂b ) 为二次函数时，以上几种共轭梯度方法即h s 方法、f r 方法、p r p 方法、c d 方法、l s 方法和d y 方法的计算公式是等价的，但是，当目标函数厂( x ) 为一 般非线性函数时，这些计算公式的性质可能大相径庭。 h s 方法的一个重要性质是：共轭梯度关系式衫儿一。= o 不论线性搜索是否精确总是 成立的。h s 方法的理论性质和计算表现类似于p r p 方法，数值实验表明h s 方法与p r p 方法的计算效果都很好，不过关于h s 方法的收敛性结果还不多。我国著名学者戚后铎、 韩继业和刘光辉于1 9 9 2 年给出了一种修正的h s 方法【2 0 1 ，并对一般的非凸目标函数 厂g ) ，证明了算法的全局收敛性。 d y 方法最早是由戴或红和袁亚湘在1 9 9 5 年提出的。1 9 9 9 年，d a i 和啪【2 4 】在 w o l f e 型线性搜索方法下，不需要给定下降条件即彰& o ，证明了d y 方法的全局收 敛性，文献 2 4 】中进一步研究了与d y 方法相关的混合型非线性共轭梯度算法，其中 屏：席r ，1 l 竺丢，ll ，并且在相同条件下证明了算法的全局收敛性。d y 方法的一个 1 9 西安科技大学硕士学位论丈 重要性质是在w r o l f e 型线性搜索方法下( 而不是强w b i f e 型线性搜索方法) 每一步均产生 一个下降方向，并且方法全局收敛，这一结果进一步揭示了非线性共轭梯度算法不同于 线性共轭梯度算法的一面。d a i 和y u a j l 在文献 5 2 】的第五章中在不使用任何线性搜索方 法的情况下，分析了其内在性质，证明了d y 方法在远离最优点时，充分下降条件必对 大部分的迭代点都成立。利用该性质，可证明d y 方法在一般的线性搜索方法下全局收 敛。 考虑到h s 方法好的数值表现和d y 方法良好的收敛性及良好的内在性质( 即在不 考虑线性搜索方法的情况下，方法在远离最优点时，充分下降条件对大部分的迭代点都 成立。) ，并充分利用前面迭代点的信息，本文提出了一种新的混合型的非线性共轭梯度 算法，即h s d y 型非线性共轭梯度算法。 我们首先给出该算法的迭代格式，然后我们给出具体的算法。该混合型非线性共轭 梯度法的迭代格式如下： 坼+ l = 故+ 嚷以 ( 2 2 5 ) d t = 二羔+ 孱以一。+ g 。一。 妻茎三 c 2 2 6 ， 其中 尾：j 胪。 咖 幽( 2 勘“ 。2 删 【群y 其它情况 吒：j 静展g ；g 。一。 o ( 2 2 8 ) ，；2 2 0 9 一。0 2 “。”8 1 ( 2 2 8 ) 【 o 其它情况 其中胪和形7 分别按( 2 2 3 ) 式和( 2 2 4 ) 式来计算，步长因子口由w r o l f e p o w e n 型线性搜索方法得到，盯是w | 0 l f e p o 、e u 型线性搜索方法中限制条件的参数，所以，我 们给出如下的w b l f e p o 、e l l 型线性搜索准则： 求步长因子口。满足 厂g + 口d ) g ) + 6 口g ；d t ( 2 2 9 ) 和 g k + 矾) r 矾曙；反 ( 2 2 1 0 ) 其中0 万 盯 o ，矾= 一g l ，令七：= 1 ； s 卸2 如果恬t l i s ，则算法终止，得问题的解以。否则，转s t e p 3 ； s t 印3由w r o l f e 型线性搜索方法即( 2 2 9 ) 和( 2 2 1 0 ) 式确定步长因子口t ； s t e p4 根据式子以= 二羔懈 是来计算巩，其中鼽分另i j 根 据式子( 2 2 7 ) 和( 2 2 8 ) 来计算。 s t e p5令以+ i = 砟+ 吨，g m = g g 川) 。令七：= 七十1 ，转s t e p 2 。 该算法具有很好的性质，就是不需给定下降条件，在标准的w b l f e 型线性搜索( 2 2 9 ) 和( 2 2 1 0 ) 式下，算法就具有全局收敛性，下面我们给出该算法的全局收敛性定理及 其证明。 2 3 算法的全局收敛性分析 对于我们在2 2 节所提出的混合型非线性共轭梯度算法，我们有如下的全局收敛性 定理。 定理2 3 1 设目标函数厂g ) 满足假设条件1 5 1 ，考虑方法( 2 2 5 ) 和( 2 2 6 ) 式， 其中展按式子( 2 2 7 ) 和( 2 2 8 ) 来计算，步长因子吼满足w 6 l f e 型线性搜索条件( 2 2 9 ) 和( 2 2 1 0 ) 式，则或者= 0 对某个七成立，或者 1 1 婴i 酬酬= o ( 2 3 1 ) 膏 ” 因为定理2 3 1 的证明，需要一些条件，所以在这里，我们先不证明定理2 3 1 ，而 是在证明该定理前，我们先给出下列引理及其证明。 引理2 3 1 设目标函数厂g ) 满足假设条件1 5 1 ，考虑一般方法( 2 2 5 ) 和( 2 2 6 ) 式，步长因子口。由w o l f e 型线性搜索方法即式子( 2 2 9 ) 和( 2 2 1 0 ) 求得，当鼠按式 子( 2 2 7 ) 和( 2 2 8 ) 来计算时，算法对所有七l ，有g ：以 o 。 下面我们采用归纳法来证明引理2 3 1 。 证明 当刀= 1 时，因为面= 一g 。，所以有g j 反= _ l l g 。0 2 o 。 假设刀；尼一l 时，结论g 乙或一l o 成立，则由( 2 2 1 0 ) 式及归纳假设可得 2 1 西安科技大学硕士学位论丈 d 工。q 。一g 。一。) = g ；d 。一。一9 0 。d 。一。 o g 工。以一l g 五。以一。 = p 一1 k ：。以一。 由于o 盯 o 因此 即 p ? = 慨 d ：。b 。一g 。一，) o 下面我们分别讨论三盯 1 及o 盯 丢时的两种情况： 当三盯 o ，则 g ；以= 一f f g 。| f 2 + 捣g j 以一。+ g j g 。一。 g ：dk = 2 。g 。一一。 g 三l d 女一l + 厂七g ；g t l ( 2 3 2 ) ( 2 3 3 ) ( 2 3 4 ) 当g ；g t t 。时，反g ：g t 一- 2 夕7 9 ；g t 一 。，因 此g j g t 一1 o ，又因为 慨 。一g ) g ：l 矾一l o ，因此g ；畋 o ，所以= o ，又因为 慨 d 乙b 。 0 2 一g ) g 工l d “ o ，因此g ；矾 o 。 综上，若级= 鲜7 ，则g ；以 o 。 2 2 瓯 一盯况 情 它 冶其 g o 2 扣 d 2 混合非线性共轭梯度法 因此 即 ( 2 ) 若成= 胪，则 o 昭；繇一。 一g t 一1 一g i 一1 ( 2 3 7 ) ( 2 3 8 ) ( 2 3 9 ) ( 2 3 1 0 ) g ；g 一l o ，所以= o ，因此g ；g t l = o ， 又由我们的假设即g 乙以一， o ，及( 2 3 1 0 ) 式，可推出 所以，若反= 胪，则g ；以 o 。 综上，当圭仃 1 时，有 g ；噍 o g ：dk o 2 3 西安科技大学硕士学位论丈 当o 盯 去时 展= 答紫。2 u 鼠0 2 包3 m ， ( i ) 若孱= 雕y ，同当去仃 l 时的( 1 ) 中的证明，同理有( 2 3 3 ) 式成立。因 此有： g ；矾 o ( 2 3 1 2 ) ( i i ) 若反= 胪，因为 o ( g ；g t 一- 2 0 9 t0 2 吉o g t f l 2 ( 2 3 1 3 ) 所以由当妻盯 l 时的( 2 ) 的证明知g ：以 o 。 综上，当o 盯 去时，有 g ：d o 综上所证，我们知道当刀= 七时结论g ；以 o 也成立。由归纳假设法可知，g ；矾 o 恒成立，即引理2 3 1 得证。证毕 引理2 3 2 设目标函数g ) 满足假设条件1 5 1 ，考虑一般方法( 2 2 5 ) 和( 2 2 6 ) 式，步长因子吼由w 6 l f e 型线性搜索方法即式子( 2 2 9 ) 和( 2 2 1 0 ) 求得，当反按式 子( 2 2 7 ) 和( 2 2 8 ) 来计算时，有 o 仃 去，展= 吃鲜7 ，吃【- l ，l 】 ( 2 3 1 4 ) 抛删拈职吩( 孚， 眨3 朋， 从而慨i 劈7 成立。 对于引理2 3 2 ，我们对结论( 2 3 7 ) 和( 2 3 8 ) 式不做太详细的证明，我们只对结 论i 成l 船y 加以详细的证明，而且我们容易知道吃，- 的取植范围均超过了文献【2 4 】中1 的取值范围，下面我们来证明该结论。 证明当o 仃 寺时，履按( 2 3 1 1 ) 式取值，即 反= 臀紫。2 u 瓯“2 眩3 舶， 2