（应用数学专业论文）一类混合型共轭梯度算法.pdf

首都师范大学学位论文原创性声明 、8 6 8 9 8 7 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所 式标明。本人完全意识到本声明的法律结果由本人承担。 靴敝储摊：馘如听 噼。胭日 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学位论 文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用于非 赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有 关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后 适用本规定。 学位论文作者签名。夜如f 5 寄 日期：。年。月。日 硕士学位论文；一类混合型共轭梯度算法 摘要 最优化是- - i - 应用广泛、发展迅速的学科尤其对于非线性优化问题寻找快 速有效的算法一直是优化专家们研究的热门方向之一最近人们提出了不少有 效地算法如t 共轭梯度算法和拟牛顿算法等，并试图证明它们的收敛性质本文 主要考虑求解无约束最优化问题的共轭梯度法基于传统的h e s t e n e s - s t i e f e l 算法 和d a i - y u a n 算法，我们综合考虑二者的优势，提出了一类新型混合共轭梯度算 法，在w o l f e 线搜索下，不需给定下降条件，证明了算法的全局收敛性依照新 算法，数值试验表明，新算法较之h s 方法和p r 方法更加有效 在第一章我们首先简要的介绍了最优化问题的提出以及判断最优解常用的 最优性条件，回顾了无约束优化问题常用的几类导数下降类算法 在第二章中我们提出了一种混合的h s - d y 共轭梯庹法1 1 6 j ，基本思想是本文 在h s 方法和d y 方法的基础上，综合两者的优势，提出了一种求解无约束优化 阿题的新的混合共轭梯度法在w o l f e 线搜索下，不需给定下降条件。证明了算 法的全局收敛性数值试验表明，新算法较之h s 方法和p r 方法更加有效 在第三章中我们改进了文献f 1 8 1 中的h s - d y 混合共轭梯度法。扩大了参数 风的取值范围，基于同样的考虑，给出了d y 与p r p 算法相结合的混合共轭梯 度法，在w o l f e 线搜索下不需给定下降条件，即证明了它们的全局收敛性数值 实验表明这类的算法十分有效 关键词：无约束最优化，共轭梯度法，w o l f e 线搜索，全局收敛性 硕士学位论文；一类混合型共轭梯度算法 a b s t r a c t w i t hi t sr a p i dd e v e l o p m e n t , o p t i m i z a t i o ni su s e do nal a r g es c a l eb yu sn o w 自t - d a y s e s p e c i a l l y , f i n d i n gh i g hp e r f o r m a n c ea l g o r i t h m si nn o n l i n e a ro p t i m i z a t i o ni sa v e r yh e a t e dr e s e a r c ht o p i cf o rt h eo p t i m i z a t i o ns p e c i a l i s t s m a n ya l g o r i t h m sw e r e d e v e l o p e di nr e c e n ty e a r s ，a m o n gt h e s ea r ec o n j u g a t eg r a d i e n tm e t h o d ，q u a s i - n e w t o n m e t h o d ，a n ds oo n a n dp e o p l et r yt op r o v et h ec o n v e r g e n c eo ft h em e t h o d s ，t h i sp a p e r p r e s e n t ss o m en e wc o n j u g a t eg r a d i e n tm 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 n w h i c h a r eb a s e do nh e e t e n e s - s t i e f e la l g o r i t h ma n dd a i - y u a na l g o r i t h m 灿aa t t e m p t w eg e t t ou s eb o t ho ft h ea d v a n t a g e so fh e s t e n e s - s t i e f e la l g o r i t h ma n dd a i - y u a na l g o r i t h m s y n t h e t i c a l l y s i m u l t a n e o u s l y , w ep r o v e di tc a ne u s u r et h ec o n v e r g e n c eo ft h en e wm e t h - o d su n d e rt h ew o l f el l n es e a r c ha n dw i t h o u tt h ed e s c e n tc a ) n d i t i o n f i n a l l y , 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 ea l g o r i t hi se f f i c i e n tb yc o m p a r i n gw i t hh sc o n j u g a t eg r a d i e n t m e t h o da n dp rc o n j u g a t eg r a d i e n tm e t h o d i c h a p t e r1 w ei n t r o d u c et h ed e v e l o p m e n to fo p t i m i z a t i o na n ds o m ee x t e n s i v e o p t i m a l i t yc o n d i t i o n st od e t e r m i n et h eo p t i m u ms o l u t i o n t h e nw er e v i e ws e v e r a l e x t e n s i v ed e r i v a t i v ed e s c e n tm e t h o d sf o ru n c o n s t r a l n e dp r o g r a m m i n g i nc h a p t e r2 ，w ep r e s e n t sam i x e do f c o n j u g a t eg r a d i e n tm e t h o d sf 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 nh e s t e n e 8 - s t i e f e la l g o r i t h m sa n dd a i - y u a na l g o r i t h m s 1 6 ，w h i c h h a dt a k e nt h ea d v a n t a g e so ft w oa l g o r i t h m s w ep r o v e di tc a e n s u r et h ec o n v e r g e n c e o f t h en e wm e t h o d su n d e rt h ew o l f el i n es e a r c ha n dw i t h o u tt h ed e s c e n tc o n d i t i o n 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 ea l g o r i t hi se f f i c i e n tb yc o m p a r i n gw i t hh sc o n j u g a t e g r a d i e n tm e t h o da n dp rc o n j u g a t eg r a d i e n tm e t h o d i nc h a p t e r3 w ei m p r o v et h em i x e do fc o n j u g a t eg r a d i e n tm e t h o d sf o rn n c o n - s t r a i n e do p t i m i z a t i o nb a s e do nh e s t e n e s - s t i e f e la l g o r i t h m sa n dd a i - y u a na l g o r i t h m s i n 【16 】，t h i 8p a p e ra l l o w s 凤t ob es e l e c t e di naw i d e rt h a ni l6 】b a s e dt h e s a l v et h i n k i n g ，w ep r o p o s eam i x e dc o n j u g a t 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 nb a s e d 0 np o l a k - r i b i b r e - p o l y a ka l g o r i t h m sa n dd a l - y u a na l g o r i t h m s w h i c hh a st a k e nt h e a d v a n t a g e so ft w oa l g o r i t h m s w ep r o v e dt h e yc a ne u s u r et h ec o n v e r g e n c eo ft h en e w m e t h o d su n d e rt h e 、 ，o l f el i n es e a r c ha n dw i t h o u tt h ed e s c e n tc o n d i t i o n 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 ea l g o r i t h sa r ee f f i c i e n t k e y w 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 ，c o n j a g a t eg r a d i e n tm e t h o d ，b l f e 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 2 硕士学位论文；一类混合型共轭梯度算法 4 第一章 非线性优化问题简介 这一章里，我们筒要介绍最优化问题的提出以及判断最优解常用的最优性条件； 在第二节总结了无约束优化问题常用的几类导数下降类算法，重点是共轭梯度算法； 在最后一节，介绍了我们提出新算法的主要总想和新算法的共同性质 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一门应用性很强的年轻学科虽然最优化可以追溯到十 分古老的极值问题，但直到1 9 4 7 年d a n t z l g 提出一般线性规划问题的单纯形法 之后，它才成为一门独立的学科随着现代科技的发展和计算机的广泛应用，进 一步推动了最优化理论和算法的研究今天，最优化理论与方法在经济规划、政 府决策、生产管理、交通运输和军事国防等方面得到了广泛的应用。成为一门十 分活跃的学科 一般来说，最优化问题可归结为求解如下的极小值问题： 。r a e i d n ， ( 1 ) 其中，z d 是决策变量，( z ) 为目标函数，d 舻为可行域 根据变量的类型，最优化问题可分为连续型最优化和离散型最优化( 也称组 合优化) 连续型最优化同题又可分为目标函数和约束函效均为线性时的线性规 划阿题，以及目标函数和约束函数中至少有一个为非线性时的非线往优化同题 又根据可行域d 的类型，非线性优化问题可分为无约束优化和约束优化问题 即当d = 舻时，无约束优化问题为 。r a e i nm ) ( 2 ) 其中，：舻一r 为非线性连续函数这也是本文主要研究的问题 一般优化约束问题通常可记为t ：r a 印i n m ) s t q ( ) 0 ， = i ，2 ，- 一，m ； g 0 ) = 0 ， = m + 1 ，m + 2 ，一，n 下面我们给出全局最优解和局部最优解的定义 ( 3 ) ( 4 ) ( 5 ) 硕士学位论文：一类混合型共轭梯度算法 定义1 1 若矿d 具有性质：忱d ，均有，( 。) ，( 矿) ，则称矿为问题 ( 1 ) 的全局最优解 定义1 2 若矿d 具有陛质，存在矿的某个邻域坼( 矿) ： z 。一矿| | 0 为某个正数，使得d n n 5 ( x ) ，均有，( $ ) ，( 矿) ，则称矿为问题 ( 1 ) 的一个局部最优解 当目标函数，( z ) 是凸函数时，局部最优解就是全局最优解但在一般情形 下我岛全局最优解非常困难，通常在菲线性优化中我们认为局部最优解即为所求 的解在实际的算法中，我们通常是找出满足局部最优解的必要条件的点下面 我们给出这些必要条件； 引理1 1 【2 l ( 无约束优化一阶必要条件) 若矿为问题( 2 ) 的个局部最优解，且在矿的某个邻域内，扛) c 1 ，则 g 扛) = 0 - ( 6 ) 引理1 2 阁( 无约束优化二阶必要条件 若矿为问题( 2 ) 的个局部最优解，且在矿的某个邻域内，( 。) g 2 ，则 g 扛+ ) = v f ( x + ) = 0 ，c ( x ) = v 2 ，( $ + ) 0( 7 ) 由于一般约束优化问题的必要条件叙述起来比较复杂，我们仅给出一个最常 用的一阶必要条件 引理1 3 2 ( k u l m - t u c k e r 必要条件) 若矿为问题( 3 ) 一( 5 ) 的个局部最优解，又v c x ( z ) 岛u 而( 矿) ) 线性无 关，则必存在向量旷= ，越，p ：) 7 ，使得 n v ，( 矿) + 鹰v c x ( x + ) = o ， t = 1 成0 ，店v q ( 矿) = 0 ，i l 1 1 2 无约束优化的导数下降类算法 导数下降类算法是求解无约束问题： 。r a ，i n f ( 。) ( 8 ) ( 9 ) ( 1 0 ) 5 塑生垡堕叁! 二羞墨垒墼茎亟堂鏖墨造 6 常用的一类算法，它的基本思想是t 对于已有的迭代点z ，首先确定一个搜索 方向出，使得目标函数，扛) 的值沿该方向是下降的，然后确定沿如方向行进 的步长k 并得到下一个迭代点z + 1 = 。k + q k d k 在这里，我i 门要确定的搜索方向应满足： v ，( z k ) t d k 0( 1 1 ) 以使f ( x ) 在z 点沿靠方向下降 确定k 的过程就是线搜索( 也称一维搜索) ，精确的线搜索就是在如方向 上寻求。最优。的行进距离，使得 f ( w k + a d k ) 22 舞，( k + a d k )( 1 2 ) 非精确线搜索不要求上式成立，而仅要求找到的蛳能使目标函数在某种意义上 达到令人满意的下降常用的非精确线搜索如w o f f e 线搜索t 步长n 满足以下不等式t j b k + o t l c d 由| l b 心+ p a k g 看d b g ( x k + a 女呶) t 呶a g 蚕d k 其中0 p 盯 0 的情况下，证明了当凤= ”m o ，雠r ) 且线搜索 满足强w o l f e 线搜索时，算法具有全局收敛性，而且结论对瓜= m 一 o ，卯8 ) 也 成立，但p r 方法和h s 方法数值表现往往比f r 方法更有效1 9 9 9 年，d a i 和 y u a a s l ，在w o l f e 线搜索下，不需给定下降条件即露d k 0 使： g ( x ) 一9 ( 口) l l 兰l l lz y m v m ，y u 基于以上假设本文首先在第二章中考虑到h s 方法好的数值表现和d y 方法 好的收敛性，提出了一个新的h s d y 的混合算法，其中t 凤= 滞? 秭“州州2 ，蜘川蚓| 2 ； 汹， 新算法不需给定下降条件，在标准w o l f e 线搜索下，证明了算法的全局收敛性 同时得到； 0 o - 1 2 ，熊一吨卯7 ，吃( - 1 ，1 】( 2 7 ) 9 硕士学位论文；一类混台型共轭梯度算法 1 2 一 o ； ( 3 1 ) 陬一1 卯y e l s e 婶叫 数值算例表明两种新算法都具有良好的计算效能 第二章 一种混合的共轭梯度法 2 , 1 引言 共轭梯度法是求解无约束优化问题。m a i n 。，( z ) 的一类非常有效的方法当 目标函数，( z ) 连续可微时，其迭代格式为 o + 12 x k + o k d k ( 2 ，1 ) 1 0 ， 凹 盯 2 v d帆胆0 g p 盯 卜 畎泓 ，jlll d帆 乳 2 一鲰 曩 0 证明了当凤= m a z o ，蘼凡 且线 搜索满足强w o l f e 线搜索时，算法具有全局收敛性，而且结论对展= m 一 o ，硝5 ) 也成立，但p r 方法和h s 方法数值表现往往比f r 方法更有效1 9 9 9 年， d a i 和y u a n 6 1 ，在w o l f e 线搜索下，不需给定下降条件即露也 0 ，证明了d y 方法的全局收敛性，文献【6 】中进一步研究了与d y 方法相关的混合算法，其中 风= n 卯y ，n 【蠢，l 】，在相同条件下证明了全局收敛性考虑到h s 方法好的 数值表现和d y 方法好的收敛性，本文给出了一个新的h s - d y 的混合算法，其 中t 尻= 髫生? 嘶_ l 一伽国，v “蚓1 2 ； ( 2 - s ) 新算法不需给定下降条件，在标准w o l f e 线搜索下，证明了算法的全局收敛性 同时得到； 0 o - 1 2 ，臃= 您彰，死( 一1 ，1 】( 2 ，4 ) 1 2 茎口 0 使t 0 9 ( z ) 一g ( y ) l j s 上i jz y v 。，y u 步长n k 由w o l f e 准则得到- ，+ 毗也) y ( x k ) + 胆k 靠呔( 2 6 ) 9 ( x k + a k d ) t 如碟如( 2 7 ) 其中0 p 盯 0 ，d t = 一m ，k 譬1 步2 ：如果i i 珊 e ，则停止否则，由w o l f e 搜索( 2 6 ) ，( 2 7 ) 求得o 茁k + l = + o 量如 步3 ：由( 1 3 ) 计算风+ 1 1d + l = 一鳜+ i + 成+ 1 d k ，k ：= k + l ，转步2 2 3 全局收敛性证明 引理1 e 1 目设日标函数满足假定h ，考虑一般方法z 女+ 1 = z k + n k d k ，其中呶 满足鲰 0 ，步长o k 由w o l f e 搜索( 2 6 ) ，( 2 7 ) 求得，则有 鲽i l d d 佃 急 2 。 此关系式称为z o u t e n d i j k 条件 si 理2 考虑一般方法( 2 1 ) ，( 2 2 ) ，步长n r 由w o l f e 搜索( 2 6 ) ，( 2 7 ) 求得， 当风取为( 2 3 ) 时，对所有k 1 ，有碓肌 0 证明。 1 2 硕士学位论文：一类混合型共轭梯度算法 当n = 1 时，g t d l = 一l 1 9 10 2 。 下面分别讨论1 2 茎口 1 及0 s 口 l 2 两种情况； ( i ) 当1 2 口 o 则t 以一2 + 石拦志露d k - 1 = 磊瓦i i g l l 而= 罹 “。 ( 2 ) 若凤= 硝8 ，则 0 a g t g k l 从而有： q td k 0 1 3 啡 吣 ” 亿 硕士学位论文t 一受混合型共轭梯度算法 ( i i ) 当0 口兰1 2 时 0 9 t g k “1 口2 ( 2 1 3 ) e s 6 ( 1 ) 若风= 卯7 ，同理有( 2 1 0 ) 式成立因此有 最d k 0 ( 2 ) 若风= 硝8 ，因为0 露鲰一l 2 1 1 瓤r 1 2 1 口 l g k 1 2 所以由( 2 ) ，知鳍靠 0 引理3 同引理2 中的条件，则有( 2 4 ) ，( 2 5 ) ，从而慨fs 卵7 成立 证明当d 口 l 2 。风按( 2 1 3 ) 取值时 若 0 嚣k 一1 2 1 1 0 k l l 2 ( 2 1 4 ) 则 凤= 彬鹅= 一捣 由( 2 8 ) ，( 2 1 4 ) 可得 由( 2 1 5 ) 可得： 由( 2 1 3 ) 可知； 从而可知下式成立： 夏五- 2 1 l e 巧k l l = 西 一耀面g 手g j & - i 函 。 一卯7 风= 茚8 船7 一卯。 职“卯7 i 胛h i ! 卯y 当l 2 蔓口 l ，凤按【2 1 3 ) 取值时 若 o 蠢 知鳜2 尉 b k = 8 h s ( 2 ，1 5 ) ( 2 1 6 ) 酽 ，、l = 风 硕士学位论文：一类混合型共轭梯度算法 由( 2 8 ) ，( 2 1 6 ) 可知 一；1 覆而j l g 葡k l l 2 一夏而g 雨g k - - 1 。一；j 善：i 磊_ = 葡一i ：瓦忑_ = 雨o 由( 2 1 5 ) 可知： ( 1 一圭) 卯7 臃= 解8 雎7 由( 2 1 3 ) 可知t ( 1 一寺) 卯7 0 ，使得 0 2 2c ，k = l ，2 ， d + g k = 忍d k 一1 上式两端取模平方，并移项可得。 j d k l l 2 = ( 凤) 2 l l d k l ij 2 2 9 罩d k 一| | 肌1 1 2 由引理3 可知t 恢j 兰卯7 i l d k l l 2s ( 卢? 7 ) 2 l l d k 一1 1 1 2 2 9 d 一| | g k l l 2 由( 2 1 0 ) 可知， 2 器 将( 2 2 1 ) 代入( 2 2 0 ) ，两边除以( 磋出) 2 可得t 丽 i d y l l = 监( g _ l d 业k - 1 ) 。一去器 ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 2 2 1 ) 1 5 硕士学位论文：一类混合型共轭梯度算法 又因为 所以由( 2 2 2 ) 递推 一dk-l12(gt l d k - 1 ) 2 ( 志+ 羰) 2 + 上l g 。1 1 2 一t 丽十瓢十一 劣剑岛+ 志 (222)d 2 ( 船1k 一1 ) 2 。1 2 卜 石j l 弼d l 1 2 = 丽1 由( 2 2 3 ) 可得； 簖以) 2 、c i 1 1 2 。k 所以 霎错 与引理1 中z o u t e n d 日k 条件矛盾定理得证 1 6 2 4 数值试验与分析 我们用来检验本算法的测试函数( 见文献【l3 1 ) 如下t h e l i c a l 住l l 唧f a n e t i o n 口，： f ( x ) = ( 1 0 ( x z l o o ( x l ，z 2 ) ) ) 2 + ( 1 0 ( x i + z ；) 1 2 1 ) 2 + $ ；其中； 口( z - ，。) = ：7 ( 2 2 ”，r ) ”a r 。e t “a n 8 ( x 。2 2 7 x 。1 1 ) + 。5 i ，f ：；： 初始点t ( 一1 0 ，0 ，0 ) b o xt h r e e d i m e n s i o n a lf u n c t i o n 5 ) ： ，( z ) = 砰+ 露+ 詹其中：，i = 唧( 一t i z l ) 一e ) c p ( 一t i x 2 ) 一z 3 ( e ) 【p ( 一屯) 一唧( 一l o t ) ) w h e r et = ( 0 1 ) t ， 初始点t ( o ，1 0 ，2 0 ) v a r i a b l e - d i m e n s i o n a l f u n c t i o n ( 6 ) ： ，( z ) = ( 砰) + 缘- + 螺+ 。其中t = ( 甄一1 ) ，n + 1 = e ( i f d ，n + 2 = 斑l 上训 。 一 黯 塑主至垒笙圭! 二壅墨垒型苎堡堡垒墨盗j 7 初始点：x o = ( 白) ，w h e r e 白= 1 一( 6 t u ) p e n a l t yf u n c t i o n1 8 ) ： 。 ，扛) = 量( 芹) + 启十i 其中： = a 1 2 涵一1 ) ，厶+ l = ( 三司) w eo = 1 0 ， 初始点t ( 1 , 2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ) e x t e n d e dr o s e n b r o c ka n c “o n 口4 j ： ，0 ) = ( 绣一1 + 熙) 其中：亿= l o ( x 2 | i z 象“) 缸= 1 一x 2 i 一1 ， 初始点t ( - 1 ，2 ，1 ，一1 2 ，l ，r 1 2 ，1 ) e w t e n d e dp o w e l l $ 1 u n c t l o n 1 5 ) ： ，( 曲= 誉( 路一a + 尼一2 + 矗一l + 赡) 其中t 知一3 = 一3 + l o x 4 1 “一2 = 5 1 2 ( z 4 i l x 4 i ；，4 i l = ( x 4 i 一2 十2 x 4 。一1 ) 2 ； = 1 0 1 2 ( z 舢一3 + l o x 4 , ) 2 ； 审口婚点：( 3 r 1 弗，t ，- 0 r l ，o 1 ) b m l ef a n c t i o n i 6 ) ： ，( $ ) = ( 1 5 一x l ( 1 一近) ) 2 + ( 2 2 5 一l ( 1 一z ；) ) 2 + ( 2 6 2 5 一x t ( 1 一z ) ) 2 ， 初始点t ( 1 ，i ) w o o dr a n e t i o n ( 1 7 ) ： ，p ) = f “2 1 0 0 ( , 一2 一x “2 3 ) 2 + ( 1 一z 4 i 一3 ) 2 十9 0 ( 一z 氢一1 ) 2 十( 1 一z 4 t 一1 ) 2 + l o ( x 4 i 一2 + 岱“一2 ) 2 + 1 0 1 ( z 4 i 一2 一$ 靠) 2 】， 初始点：( - 3 , - i ，一3 ，- 1 ，r 3 , - 1 ，3 ，- 1 ) 取e = 1 0 ，且均不采用重开始策略实验数据如下表所示( 其中d c 表示本算法的迭代次数，p r 表示文献 l4 】中采用p r 算法的最佳迭代次数，h s 表示文献1 1 4 】中采用h s 算法的最佳迭代次数) 硕士学位论文：一类混合型共轭梯度算法 试验数据表 问题维数 d ch sp r l 33 91 3 92 6 5 532 07 01 6 5 661 35 35 2 81 0 2 91 2 71 7 3 1 4 1 44 13 68 1 1 51 61 2 32 7 9 1 0 0 9 1 621 97 82 3 1 1 7 48 12 5 06 6 0 1 41 0 0 05 9 1 4 5 0 0 05 9 以上数值试验的比较可以看出，混合h s = d v 的共轭梯度算法具有良好的计算效 能，特别适合求解大规模的最优化问题在以上数值试验中，当0 2 p 口 0 证明了当觑= m a x o ，筐2 且线 搜索满足强w o l f e 线搜索时，算法具有全局收敛性，而且结论对风= m a x 0 ，卢f l 也成立，但p r 方法和h s 方法数值表现往往比f r 方法更有效1 9 9 9 年。 d a i 秘h 吲，在w o l f e 线搜索下，不需给定下降条件郭靠矗 0 证明了d y 方法的全局收敛性，文献 6 1 中进一步研究了与d y 方法相关的混合算法，其中 1 9 硕士学位论文：一类混合型共靶梯度算法 熊= 丁1 带7 ，t i 【t a 藉- i ，1 1 ，在相同条件下证明了全局收敛性考虑到h s 方法好的 数值表现和d y 方法好的收敛性，文献【1 6 1 中给出了一个新的h s - d y 的混合算 法，其中； 成= 滔：? 理舭“而州2 ，叫“训| 2 ； ( 3 _ 3 ) 算法不需给定下降条件，在标准w o l f e 线搜索下，证明了算法的全局收敛性同 时得到； 0 盯 l 2 ，凤= 印卯7 ，吨( 一1 ，i 】 ( 3 4 ) 1 2 口 o ； ( 3 f 8 ) 悱一1 e l s e p 0 数值算例表明两种新算法都具有良好的计算效能 3 2 混合共轭共轭梯度法 假设i l ： ( i ) 水平集三= 忙r r i ：，( z ) ，( 。1 ) ) 有界，其中z l 为初始点； 砷 1 乱 一 衽 鳜 o 苦 露 0 使： l 9 ( 。) 一g ( ) 茎l | 1 一l f ，v 。，口u 步长。女由w o l f e 准则得到： f ( z k + a k d k ) ，0 k ) + p 盘k 9 罩d 女( 3 9 ) 9 ( x k + c t k d k ) 7 d k f t g t d k r 3 1 0 ) 其中0 p 盯 0 ，d l = 一9 1 ，；1 步2 ：如果i f 鳜| e ，则停止否则t 由w o l f e 搜索( 3 9 ) ，( 3 1 0 ) 求得n x k + l2 0 k + n d k 步3 ：计算凤+ 1 ，呶+ l = 一瓠+ 1 + 反+ l 蟊，知：= k + 1 转步2 ， 3 3 全局收敛性证明 引理1 【1 q 设目标函数满足假设h ，考虑一般方法x k + 1 = 瓢+ n 女d k ，其中d k 满足m 0 ，步长o t k 由w o l f e 搜索( 3 9 ) ，( 3 1 0 ) 求得，则有 锚 + 。 惫恻| 2 此关系式称为z o u t e n d i j k 条件 引理2 考虑一般方法( 3 1 ) ，( 3 2 ) ，步长a k 由w o l f e 搜索( 3 9 ) ，( 3 1 0 ) 求得， 当凤取为( 3 6 ) 时，对所有1 ，有唾m 0 证明： 当n = 1 时，9 f d l = 一i 口1j 1 2 。 由( 3 6 ) 可知；若卯日= 雎5 ，则有： 0 菇鲰一l 2 1 1 9 k l l 2 又因为 职世= 雎s = 器铃= 卯y 一耀忑g 而g k - 1 由( 3 1 1 ) ，( 3 1 3 ) 可得t 琵丽- 2 雨1 1 a k l l = - - g t i g k _ 瓦1 5 - ：( g k 可 o 赇 孤一2 + 孤警志靠“= 瓣警j 靠“ 0 ( 3 朋) ( 2 ) 若卯8 = 雕5 ，而且 0 1 2 9 g k l d 取一1从而有：靠d k 0 ( 3 ) 若解”= 卯8 ，而且有t 0 g r g k 一1 0 ，1 2 0 ，使得 i 撅护c ，k = 1 ，2 ， d k 七9 k ：8 r d k l 上式两端取模平方，并移项可得； i d k l l 2 = ( 卯盯) 2 l l d k 一, 1 1 2 2 9 著d k i l g k l l 2 由( 3 1 5 ) ，( 3 - 1 6 ) 可得r 雠1 鲥k 蕊t 将( 3 2 3 ) 代入( 3 2 2 ) ，两边除以( 蠢d k ) 2 可得： i i d y l l 2 ，i l 呶一11 1 2 2 i i g k | 2 丽( t d k 、21 丽丽一丽一礤( t 莽d k 、2 = 老番一c 南+ 糕) 2 + 赤5 礤i 万1 丽+ 菰厂+ 砰 ( 3 2 0 ) ( 3 , 2 1 ) ( 3 2 2 ) 硕士学位论文：一类混合型共轭梯度算法 磺莉十研 又因为 研i l d 砑l l l = = 丽1 所以由( 3 2 4 ) 递推： 丽 l d ；l 2 茎砉赤三k 由( 3 2 5 ) 可得； ( 卵也) 2 、c i 俨：。k 所以 薹群 与引理1 中z o u t e n d i j k 条件矛盾定理得证 3 5 p r p 方法与d y 方法的混合算法 ( 3 2 4 ) 引理4 1 考虑一般方法( 3 1 ) ，( 3 2 ) ，步长o z k 由w o l f e 搜索( 3 9 ) ，( 3 1 0 ) 求得， 当凤取为( 3 8 ) 时，对所有k 1 ，有耀鲰 0 证明t 当n = 1 时，卵d l = 一i l g l l l 2 。 ( 3 2 7 ) 若卯9 = 雎5 则有：i 雕3 l 曼船y 且靠d k l 0 显然不论摩p = 硝3 还是卯p = 卯都有； 9 ；d k = - 1 1 靠1 1 2 + 雎p g r d k l 一i l g k l l 2 + 卵y 9 看d k 一1 一2 + 石拦高靠“ 硕士学位论文：一类混合型共轭梯度算法 = 孤警刍豇，讪= 砖7 正- “ 0 ，使得 i m | | 2 c ，k = 1 ，2 ， 如+ g k = 醒p d k _ 上式两端取模平方，并移项可得： i l d k l l 2 = ( 属p 9 ) 2 l i d 女一, 1 1 2 2 9 t d k 1 1 9 k 2 由( 3 8 ) ，( 3 2 8 ) 可得t i 卯p i 卯7s 监g t _ l d b - i 下同定理4 的证明 ( 3 2 8 ) ( 3 2 9 ) 3 5 数值试验与分析 我们用来检验本算法的测试函数( 见文献【1 3 】) 如下。 h e l i c a lv a l l e yf u n e t i o n ( 1 ) ： f ( x ) = ( 1 0 ( z 3 一1 0 0 ( x a ，2 ) ) ) 2 + ( 1 0 ( x + 茹1 ) 1 2 1 ) 2 + 。i 其中t 口( z ，z ：) = ；( ( 2 2 。”) ) 。a 。r 。c 。t 。a 。n ( ( 。x 。2 。x ，1 ) ) + 。5 i ，f ：；： 初始点：( 一1 0 ，0 ，0 ) b o zt h r e e - d i m e r i o n a lf u n c t i o n 5 ) ： ，( 茹) = ，i 2 1 j 2 2 1 _ j 3 2 喜# 中： = e x p ( 一t i x l ) - e x p ( 一t i x 2 ) 一z z ( e x p ( 一t i ) 一e ) 【p ( 一1 0 t i ) ) 埘h e r et j = ( 0 1 ) i ， 初始点；( o ，1 0 ，2 0 ) 硕士学位论文：一类混合型共轭梯度算法 v a r i a b l e - d i r a e n 3 i o n a lf u n c t i o n 6 ) ： ，( z ) = 妻( 砰) + 露+ l + 露+ 2 其中： = ( 以一1 ) ，厶+ 1 = 0 ) ，a + 2 = 舞+ i l = l4 = l 初始点：x o = ( 白) ，w h e r e6 = 1 一( j 加) p e n a l t y f u n c t l o nl 8 ) ： ，( ) = ( 坪) + 螺+ 1 其中t = a l 2 ( 毛 初始点：( 1 , 2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ) e z t e n d e dr o s e n b r o e kf u n c t i o n i ( 1 4 ) ： ，= ( 癌一。+ 璧) 其申血= 1 0 ( z * 初始点t ( - i 2 ，1 r 1 2 ，l i 1 一，1 2 ，1 ) 1 ) ，n + 1 = ( $ ) w h e r en = 1 0 “ t = l 壤一1 ) ，2 i = 1 一一1 ， e o t e n d e dp o w e l ll n c t i o n ( 1 5 ) ： 4 m ，( z ) = ( 路一3 + 强一2 + 跨一1 + 躁) 其中： 厶一3 = x 4 i 一3 + 1 0 x 4 1 - 2 ，4 i 一2 = 5 1 2 ( x 瓤一1 一z 4 i ；凡一l = ( x 4 一2 + 2 x 舡一1 ) 2 ； i = 1 0 1 2 ( 钆一3 + l o z 4 i ) 2 ； 初始点t ( 3 , - 1 ，0 1 一，3 , - 1 ，0 ，1 ) b e a l ef u n c t i o n 1 8 ) ： ，( $ ) = ( 1 , 5 一z 1 ( 1 一。；) ) 2 + ( 2 2 5 一$ 1 ( 1 一z ；) ) 2 + ( 2 6 2 5 一z 1 ( 1 一递) ) 2 。 韧始点t ( 1 ，1 ) w o o df u n c t i o n ( 1 7 ) ： ，( z ) = 1 0 0 ( x 4 i 一2 一一3 ) 2 + ( 1 一x 4 i 一3 ) 2 + 9 0 ( 。4 i 一霹i 1 ) 2 q - ( 1 - - x l i 一1 ) 2 + 1 0 ( x 4 1 2 + 舡一2 ) 2 + 1 0 1 ( 茁啦一2 一茁舢) 2 1 ， 初始点；( - 3 r l r 3 ，一1 ，f 3 , - 1 ，- 3 ，1 ) 取= 1 0 - 6 ，且均不采用重开始策略实验数据如下表所示( 其中d i ：i ，d p 分别表示本文中d y 与h s 和d y 与p r p 的混合算法的最佳迭代次数，d c 表 示文献【1 6 1 中算法的最佳迭代次数，p r 表示文献【1 4 】中采用p r 算法的最佳迭 代次数，h s 表示文献 14 中采用h s 算法的最佳迭代次数) 硕士学位论文t 一类混合型共轭梯度算法 实验数据表 函数维数 d pd hd c h sp r _ p 136 0 3 93 9 1 8 9 2 6 5 536 42 02 07 01 6 5 66 2 61 31 35 35 2 81 03 62 92 91 2 71 7 3 1 41 4 4 83 64 13 68 1 1 51 61 6 11 2 31 2 32 7 91 0 0 9 1 623 1 1 91 97 82 3 1 1 741 0 48 18 12 5 0 6