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

硕士学位论文t 一类新型共轭梯度算法 摘要 最优化是一门应用广泛、发展迅速的学科尤其对于非线性优化问 题寻找快速有效的算法一直是优化专家们研究的热门方向之一。最近 人们提出了不少有效地算法如：共轭梯度算法和拟牛顿算法等，并试图 证明它们的收敛性质本文主要考虑求解无约束最优化问题的共轭梯 度法基于传统的p o l a k r i b i e r e 算法和f l e t c h e r - r e e v e s 算法，我们综合考虑 二者的优势，提出了两种新型共轭梯度算法，在g r i p p o 线搜索下证明了 算法的全局收敛性依照新算法，本文也取得了比较理想的数值结果 在第一章我们首先简要的介绍了最优化问题的提出以及判断最优 解常用的最优性条件，回顾了无约束优化问题常用的几类导数下降类 算法 在第二章中我们改进并证明了文【1 】中的算法基本思想是采用可 以计算机实现的g r l p p o 线搜索而不是文f l 】中仅有理论意义的精确线 搜索，并削弱文【1 】1 中要求目标函数在水平集上= 阶连续可微的前提条 件，在较弱的条件下证明了算法的全局收敛性而且，随后的数值实 验结果也说明了算法较传统的算法更有效 在第三章中我们将传统的p o l a k - r i b i e r e 算法和f l e t c h e r - r e e v e s 算法以 参数形式楣结合，给出了求解无约束线性规划问题的一类带参数根号 形式的新算法采用g r i p p o 线搜索，在适当的条件下我们证明了算法 的全局收敛性，并以较优的数值结果说明了这类新算法的实用价值 关键词：无约束最优化，共轭梯度法，g r i p p o 线搜索，全局收敛性 硕士学位论文- 一类新型共轭梯度算法 a b s t r a c t w i t hi t s r 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 s u s e do nal a r g es c a l eb yu sn o w a - 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 s a 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 x 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 o o n a n d p e o p l e t r y t o p r o v e t h e c o n v e r g e n c e o f t h e m e t h o d s t h i s p a p e r p r e s e n t ss o m en e wc o n j n g a t eg r a d i e n tm e t h o d s f 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 np o l a k - r i b i e r ea l g o r i t h ma n df l e t c h e r - r e e v e sa l g o r i t h m a saa t t e m p t ，w e g e tt o1 1 8 eb o t ho ft h ea d v a n t a g e so fp o l a k - r i b i e ma l g o r i t h ma n d f l e t c h e r - r e e v e sa l - g o r i t h ms 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 et h a tt h eg r i p p o l l n es e a r c hc o n d i t i o n c a , ne n s u r et h eg l o b a lc o n v e r g e n c e f i n a l l y , w ea l s og e tb e t t e rn u m e r i c a lr e s u l t sw i t h t h en e wa l g o r i t h m i nc 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 d8 0 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 i n e dp r o g r a m m i n g i nc h a p t e r2 ，w ei m p r o v et h ea l g o r i t h mi np a p e r 1 】a n dp r o v et h eg l o b a lc o n v e r - g e n c eo ft h ea l g o r i t h mw i h r e a l i z a b l eg r i p p ol i n es e a r c ha n dw e a t k d rp r e c o n d i t i o n sb u t n o tt h et h e o r e t i ce x a c tl i n es e a r c ha n dt h et w i c ec o n t i n u o u s l yd i f f e r e n t i a b l ec o n d i t i o n o nb o u n d e ds e t so fc o s tf u n c t i o ni np a p e r 【1 】1 m o r e o v e r ，w ef i n dt h a tt h e8 u b s e q u e n t e x p e r i m e n t a lp e r f o r m a n c e a l em o r ee m e i e n tt h a nt h a to ft r a d i t i o n a l a l g o r i t h m s i nc h a p t e r3 骶p r o p o s ean e wc l a s so fc o n j u g a t eg r a d i e n tm e t h o dw i t hi n e x - a c tg r i p p ol i n es e a r c hf o ru n c o n s t r a i n e dn o n l i n e a rp r o g r e m m i n gp r o b l e m sb yc o m b i n - i n gp o l a k - r i b i e r ea l g o r i t h mw i t hf l e t c h e r - r e e v e sa l g o r i t h mv i aa d j u s t a b l ep a x a m e - t e r t h i sa l g o r i t h mh a sas p e c i a lf o r mo fr a d i c a ls i g n i t sg l o b a lc o n v e r g e n c ei sp r o v e d u n d e rs u i t a b l ec o n d i t i o n s a d d i t i o n a l l y , o l l re x p e r i m e n t a lr e s u l t sw i t n e s st h ea p p l i e d v a l u eo ft h i sn e wm e t h o d 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 u g a t eg r a d i e n tm e t h o d ，g r i p p o 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 3 硕士学位论文t 一类新型共轭梯度算法 第一章 非线性优化问题简介 这一章里，我们简要介绍最优化问题的提出以及判断最优解常用的最优性条件； 在第二节总结丁无约束优化问题常用的几类导数下降类算法。重点是共轭梯度算法； 在最后一节，介绍了我们提出新算法的主要思想和新算法的共同性质 1 1 最优化问题的提出及最优性条件 最优化理论与方法是- - i i 应用性很强的年轻学科虽然最优化可 以追溯到十分古老的极值问题，但直到1 9 4 7 年d s n t z i g 提出一般线性规 划问题的单纯形法之后，它才成为- - f i 独立的学科随着现代科技的 发展和计算机的广泛应用，进一步推动了最优化理论和算法的研究 今天，最优化理论与方法在经济规划、政府决策、生产管理、交通运 输和军事国防等方面得到了广泛的应用，成为- - n 十分活跃的学科 一般来说，最优化问题可归结为求解如下的极小值问题： 。r a i n ，( 。) ( 1 ) 其中，。d 是决策变量，f ( x ) 为目标函数，d s 舻为可行域 根据变量的类型，最优化问题可分为连续型最优化和离散型最优 化( 也称组合优化) 连续型最优化问题又可分为目标函数和约束函数 均为线性时的线性规划问题，以及目标函数和约束函数中至少有一个 为非线性时的非线性优化问题又根据可行域d 的类型，非线性优化 问题可分为无约束优化和约束优化问题即当d = 矗n 时，无约束优化 问题为： 其中，：册_ 冗为非线性连续函数这也是本文主要研究的问题 一般优化约束问题通常可记为： 删r a i n 。m ) s t q ( o ) 0 ，i = l ，2 ，- 一，m ； c f 0 ) = 0 ，= m + 1 ，m + 2 ，一，l ； ( 3 ) ( 4 ) ( 5 ) 硕士学位论文t 一类新型共轭梯度算法 下面我们给出全局最优解和局部最优缌的定义 定义1 1 若。+ d 具有性质；v s d ，均有，( z ) ，( 矿) ，则称矿为问 题( 1 ) 的全局最优解。 定义1 2 若矿d 具有性质：存在矿的某个邻域( 矿) = 和ii i z - - x * i i 0 为某个正数，使得v ：r d n ( 矿) ，均有f ( x ) ，( 矿) ，则称矿 为问题( 1 ) 的一个局部最优解 当目标函数，( z ) 是凸函数时，局部最优解就是全局最优解但在 一般情形下找出全局最优解非常困难，通常在非线性优化中我们认为 局部最优解即为所求的解在实际的算法中，我们通常是找出满足局 部最优解的必要条件的点。下面我f 给出这些必要条件： 则 则 引理11 n ( 无约束优化一阶必要条件) 若矿为问题( 2 ) 的一个局部最优解，且在矿的某个邻域内，( z ) c , 1 引理1 2 2 1 ( 无约束优化二阶必要条件) 若，为阊题( 2 ) 的一个局部最优解，且在矿的某个邻域内，0 ) 俨 g ( 。) = v f ( x + ) = 0 ，g ( + ) = v 2 ，( z ) 0( 7 ) 由于一般约束优化问题的必要条件叙述起来比较复杂，我们仅给 出一个最常用的一阶必要条件 引理1 3 【2 ( k u h n - i u c k e r 必要条件) 若z + 为问题( 3 ) 一( 5 ) 的一个局部最优解，又v c i ( x ) 0 l 2u 而( 矿) ) 线 性无关，则必存在向量旷= ( 卢i ，p ；，麻) t ，使得 n 审，( 矿) + 心v c l ( x ) = 0 ， l = i p ；0 ，p ：v g ( z + ) = 0 ，i l 1 6 硕士学位论文，一类新型共轭梯度算法 1 2 无约束优化的导数下降类算法 导数下降类算法是求解无约束问题： 三竖，( z ) ( 1 0 ) 常用的一类算法，它的基本思想是：对于已有的迭代点z e ，首先确定 一个搜索方向出，使得目标函数f ( x ) 的值沿该方向是下降的，然后确 定沿血方向行进的步长h 并得到下一个迭代点+ ，= z 女+ 血 在这里，我们要确定的搜索方向应满足： v f ( x k ) 7 d k 0 ( 儿) 以使，( z ) 在z t 点沿如方向下降 确定h 的过程就是线搜索( 也称一维搜索) ，精确的线搜索就是在 也方向上寻求“最优”的行进距离，使得 ，( 。女+ a 矗) = q 卿，扛 + x d k ) ( 1 2 ) 非精确线搜索不要求上式成立，而仅要求找到的h 能使目标函数在某 种意义上达到令人满意的下降常用的非精确线搜索如w o l f e 线搜索： 固定6 1 ( o ， ) ，如( d 1 ，1 ) ，选取吼满足t 出f ( x m k ) f ( w k + a 猢k d k ) - ( 订6 1 a k 出g ( ( 1 3 )【g ( 。k + q 呶) 丁饥如9 ( 。) t d 七 7 本文出现的g r i p p o 线搜索： 固定0 c l 1 0 ，0 c 1 五时， 丝止掣二+ 。l i d o l l 。o 即，f ( x o + 如) 一，( z o ) 一n ( 碥) 2 i l d o l l 2 另一方面，根据参数选择：0 c 。 1 0 ，当 j 2 时， 一c 2 怕( 爿) 1 1 2s9 ( 矗) t ( 一g ( 雹) + 藤d d ) ! 一c ，m 珥) 0 2 塑芏垒篓墨! = 墓煎兰羞堑竖垒墨盗 1 , 5 成立 由以上两方面可得：必存在有限数j o ( j o m a z j 1 ，j 2 ) 使a 。= o d o a 。满足 ( 2 1 ) ( 22 ) 。 所以，= 0 时，引理成立。 2 ) 我们假设在k 次迭代时，存在 使n = o d 趣满足( 2 1 ) ( 2 2 ) ，下面 证明对于第+ 1 次迭代，也存在靠+ 1 使o m = 砂+ z m 满足( 2 1 ) ( 2 2 ) 同前面女= 0 时的证明类似。 记： 一f 盟# 躲掣9 ( 吨。) r g ( 。) o ； 班 藏妒一裟? 叫刈；t _ 丌而诃r 口州 一方面由归纳假设有 2 1 恐【地出粤) 二幽+ 。l l d , 1 1 2 】；飒s _ c l l l g , i i ： 0 ，当j 时， 坐蝉二蚴+ 。i l d k i t 。冬o 一 嚷 即，( z + 以d k ) 一，( z ) s 一口( ) 2 i l a k l l 2 另一方面，根据参数选择：0 c l 1 0 ，当， 如时，一c 2 1 1 9 ( + 。) 1 1 2 9 ( + 。) r ( 一9 ( + i ) + 鹾呶) 一c + 。) 1 1 2 成立 由以上两方面可得： a j k + - a 满足( 2 1 ) ( 2 ，2 ) 。 必存在有限数j k + l ( 靠+ 。”m 。 z ，五) ) 使n 川= 所以，k + 1 时，引理成立。 综上1 ) 、2 ) ，引理对于所有成立。引理证毕 2 4 算法的收敛性分析 引理2 2若弧0 ，且i l g k l l 彳，则 对所有女存在正常数反使：讯、- 燃i l d k l l ： 证明：分n 女= a 和o 一口( 警) 2 i l d k l l 2 因为， a a ( g ( z k ) t d k 一西靠) + 警西靠 一o ( 警) 2 i i 也n 1 6 硕士学位论文r 一类新型共轭梯度算法 所以( 挚) 2 l l l d k l l 2 + 警靠d 七一n ( 警) 2 f l d k r 1 2 故a e 南糯裂 如果警使( 2 2 ) 不成立，即有下面 9 ( h ) t 一g ( “氇) + 凤( ( 工，k ) d 女】 一c l lj g ( c o 女) 1 1 2 或 g ( w k ) t f 一9 ( u k ) + 风( u k ) d 】 一c 1i i g ( u k ) 1 1 2 所以， 雎r ( u k ) 9 ( u k ) r d k ( 1 一c 1 ) l l g ( u k ) 1 1 2 所以，9 ( 咄) 7 d k 0 ，即( g ( 峨) 一g k ) r 也- i - 鳍也 0 ，且鳍d 七 i g 著d k l 则，讯 擗 若凤( u 女) = 筇r ( 峨) ，则茚r ( 啡) g ( ) 了d k ( 1 一c 1 ) 慨) 1 1 2 即： ( 2 3 ) ( 2 4 ) g ( o j k i ) t 而q ( w k ) - - g ( x k ) 9 ( ) t d ( 1 一c t ) 胛 左边取模扩大并利用l i p s c h i t z 连续的条件有，工挚慨lj 2 ( 1 一c 1 ) 1 1 珊1 1 2 利 用线搜索的条件有， 舭 专笋鼎i l a , 。 c 2 厶旷 如果( 2 4 ) 成立，则， 若凤) = 雎r ) ，则，必有g ( u 女) l l g ( ， ) 1 1 2 因此，利用l i p s c h i t z 连续的条件有， l 譬l l d k l l 似呱) o ( 1 ) 由( 2 4 ) 得，一i 恼( j k ) 0 2 + 卵r ( u r ) g ( “，七) t d k ( c 2 1 ) 1 1 出* ) 1 1 2 1 7 塑主堂垒堡圭! 二盎堑翌叁塑壁垒墨鎏 1 8 一g ( 。k ) 1d k ( c 2 1 ) l l g k 由l i p s c h i t z 连续的条件和上面结论l 警慨0 i i g c , , - k ) l l 有， l 警l l d k l l 2 ( c 2 1 ) i g k l l 2 因此， 啦警镣 若仇( u ) = 雎r ( u ) ，则，必有9 ( u ) t g k 0 由( 2 4 ) 得，- i i g ( w d i l 2 + 筇8 ( u ) 一9 ( “撬) t d k (。一1)119(。)11。iigc x k ) 1 1 2 。、w 8 。、。、 左边取模扩大并利用l i p s c h i t z 连续的条件有， i i g ( 。女) 一g k l l l l d k l l ( c 2 1 ) l l g ( x ) 1 1 2 l 警l l d k l l 2 ( c 2 1 ) l l g c z k ) 1 1 2 啦警鼎 最后，令万= m i n p ，z ，生c 2 业l ，( c 2 。- 幽1 0 a ，t 所以引理成立 定理2 , 1若在假设( h ) 下，( z ) 为本文讨论的算法求解第一章( 2 6 ) 式 时产生的点列，则 熙i n y i i g c x k ) l l = 0 -( 2 ) 证明：反证法，若( 2 ) 不成立，则存在常数e 0 使得l l g k l l s ，对所有k 成立从而有， l l d k l i = l l g k + 凤一l d k 一1 1 1 i l g k l l + i 凤一l i l i d k 一1 | | 若g t g k l 慨i i 则， i i d t l l 鲫黔恪计业铲蝌字( 。* i l d k l l 2 曼施_ 2 ，v k ) 塑堂堡堡主! = 耋堑型墨堑壁垒墨墨 一 1 9 若程弧一l 0 ，由第一章引理1 4 贝0 ， 训旧+ 与掣i l d k 一+ 地一陆川2 搏，州施彳2 ) 墨 两种情况下都有，i i d i l l 有界所以 l i d t i i 有界 因为第一章引理1 4 ，l i r ao i i d 女l l = 0 ，和i i d l 有界则， e t u o 又根据引理2 2 ， 代入可得 1 j mn i l d k l l 2 = 0 。e 槲 女1 i m 。i g d k l ；0 由线搜索可知，0 骢m z k ) l l = 0 ， 这与假设条件恢陀s ( 垤) 矛盾所以，原命题成立。 2 5 数值实验与分析 我们用来检验本算法的测试函数( 部分详见【1 3 j ) 如下： s a m p l e 5 _ 2f u n c t i o n ( p i ) ： f l = 1 0 0 ( z 2 一z 2 ) 2 + ( 1 一1 ) 2 ，初始点：( - x 7 - 2 1 ) s a m p l e 5 _ 1f u n c t i o n ( p 2 ) ： 矗= 霹+ z ；+ 2 z ；十z i 一5 ( z l + 2 ) 一2 1 x 3 + 7 x 4 ，初始点： ( 1 ，l ，1 ，1 ) b e a l ef u n c t i o n p 3 ) ： b ：( 1 5 一。1 ( 1 一z i ) ) 2 + ( 2 2 5 一l ( 1 一遽) ) 2 + ( 2 6 2 5 一x l ( 1 一$ 2 ) ) 2 ，初始点： ( 1 ，1 ) w o o d 。f u n c t i o n ( p 4 ) ： 1 4 = 妻【1 0 0 ( $ 4 i 一2 一z ：，一3 ) 2 + ( 1 一x 4 i 一3 ) 2 + 9 0 ( 茁4 t 一一1 ) 2 + ( 1 一互4 卜1 ) 2 + l o ( x 4 1 2 + z 4 一2 ) 2 + 1 0 1 ( $ 扣2 一x 4 i ) 2 】，初始点l ( - 3 ，一1 ，一3 ，1 ，一3 ，- l ，3 ，1 ) h e l i c a l v a l l e yf u n e t i o n ( p 5 1 ： ，5 = 1 0 0 x 3 一1 0 0 ( x l ，z 2 ) j 2 + 1 0 0 ( a ：t 2 + z ；) 1 2 1 j 2 + z i 硕士学位论文t 一类新型共轭梯度算法 其中： 初始点：( 1 , 0 ，0 ) 丽1a r c t a n ( 署) 若x l 0 e x t e n d e dr o s e n b r o c kf u n c t i o n t p 6 ) ： ，6 = ( 咒一1 + 珐) 其中：，2 l = l o ( z 2 i z ；“) ，2 l = 1 一z “一。，初始点： t = l ( - 1 _ 2 ，1 ，- 1 2 ，1 ，- 1 2 ，1 ) 取e = 1 0 ，且均不采用重开始策略实验数据如下表所示。( 其 中b j l 表示本算法的迭代次数，w h w 表示文献 1 4 】中采用p r 算法的 最佳迭代次数) 实验数据表 问题维数b j l 迭代次数w h w 迭代次数 p 122 7 6 p 246 p 323 92 3 1 1 4 p 441 9 06 6 0 1 4 p 41 0 0 02 4 1 p 532 3 12 6 5 1 4 p 61 45 28 1 1 4 p 65 0 0 06 4 由上可见，本算法数值结果较好，特别是计算高维问题结果比较理想 同时，我们也跟踪了算法各分支选择的情况，发现各算倒选择每个分 支的频率并不一致所以如何采用更合适的标准来决定分支的选择是 我们进一步研究的问题。 塑主堂堡煎墨! = 墓堑翌盎塾璺鏖墨姿 2 1 第三章 带根号的共轭梯度算法 本章考虑求解无约束最优化同题的共轭梯度法，基于传统的f r 和p r 算法，综 合考虑二者的优势，提出了一类新型共轭梯度算法，在g r i p p o 线搜索下证明了其全 局收敛性依照本算法，我们取得了比较理想的数值结果 共轭梯度法是求解无约束优化问题。m 。i n ，( 。) 的一类非常有效的方 法。当目标函数，( z ) 连续可微时，其迭代格式为 。* + - = 。t + 。t 巩，呶= 一- 肌g k + 凤一。也一。，。k = o ， 其中凤一。为标量，著名的公式有； l l1 1 2 凤一1 = 船= 熙( f l e t c h e r r e e v e s ) ， i i 掣女一1i i 凤一l = 髓= 掣警：掣( p o l a k r i b i 6 r e - p o l y a k ) ， j l y k - 1 i 这里珊= v f ( x k ) ，靠代表搜索方向当，( z ) 为二次凸函数时，适当选 择系数风，使得d 女与d l ，d 2 ，以一1 关于，( z ) 的h e s s e n 矩阵共轭当o k 是 由精确线搜索确定的步长时，共轭梯度法具有二次终止性然而当目 标函数为一般的非线性函数时，即使在精确线搜索下，某些共轭梯度 法的收敛性也很难保证在文献【3 中a i - b a a l i 证明了f l e t c h e r r e e v e s 方 法具有全局收敛性，但是p o w e l l 在【4 】中指出，即使采用精确线搜索， p o l a k p d b i r e p o l y a k 方法也不具有全局收敛性，但此方法具有良好的 数值表现【5 1 1 9 9 7 年l g r i p p o 和s l u c i d i 提出了g r i p p o - l u c i d i 线搜索，并证明了在 此线搜索下p o l a k p d b i 6 r e p o l y a k 方法的全局收敛性【6 一。 近年来出现了不少混合算法，它们或将传统算法限定条件使用， 或将各现有算法杂交，相继得到了一些好的结果作为一种尝试本章 也将提出一种带根号的新算法 硕士学位论文。一类新型共轭梯度算法 3 2 带根号的共轭梯度法 本文提出一类基于g r i p p o - l u c i d i 线搜索的新型共轭梯度法，其放满 足： 凤= 迹、l i g ( x 团k + 1 ) l 匣4cos20+g蕊(xk+1)t(g(x正k+1)-砸g(xk)2 s i n t 0 其中：p ( o ，”2 ) 。并且证明了在g r i p p o - l u c i d i 线搜索下新算法具有全 局收敛性当日= o 和口= 时，新算法分别退化为f r 算法和取绝对值 的p r 算法算例表明，该类新算法有较好的数值表现 算法描述 取参数芦p 0 ，口( o ，1 ) ，口 0 ，o c 1 1 时， 丝止避删+ 。喝z o 铴 即，f ( x o - i - d o ) 一，( t o ) 一口( 确) 2 l l d o l l 2 另一方面，根据参数选择：0 c l 1 矗丽 0 ，当j 以时， 一啦怕(d川z，(嗣)r(一，()+羔j旦生墨型二竺竺：竺j；叠；品；竺il二螋a。) 一c l 慨矗) lj 2 成立 由以上两方面可得：必存在有限数j o ( i o m z j l ，如 ) 使a o = o j o a * 满足 ( 3 1 与( 3 2 ) 所以，k = 0 时，引理成立 硕士学位论文t 一类新型共轭梯度算法 2 ) 我们假设在k 次迭代时，存在血使a 女= 扣趣满足( 3 1 ) ( 3 2 ) ，下面 证明对于第+ 1 次迭代，也存在j m 使a = a j k + , a 州满足( 3 1 ) ( 3 2 ) 同前面k = 0 时的证明类似： 一方面有 l i 。丝生塑掣：瓠r d k _ c l i l g k 忆o 1 a ； 所以，3 j 1 0 ，当j j 1 时， 地吐型掣+ 。刚础 o 即，f ( x k + d k ) 一f ( x e ) 一o ( 嗥) 2 i f d k l l 2 另一方面，根据参数选择：0 c l l 葡1 莉 0 ，当j 以时， 一c 2 + 1 ) 1 1 2 ，c+。，r卜，c。；+。，+，!iiii：ii!iiij!j：i：l：；iiiiii；i匦毗 5 一c 愀+ 。) 1 1 2 成立 硕士学位论文：一类新型共轭梯度算法 由以上两方面可得：必存在有限数靠+ ( j 川m n z 正，) ) 使a = o “+ - 越+ 。 满足1 3 1 ) 与( 3 2 ) 。 所以，k + 1 时，引理成立。 综上1 ) 、2 ) ，引理对于所有女成立。引理证毕。 另外，此算法在目标函数为二次凸函数，且采用精确线搜索的情况 下可以证明其共轭性。 3 4 算法的收敛性分析 本节主要证明算法的全局收敛性首先，给出以下引理。 引理3 2若g k 0 ，且恢| 1 彳，则对所有k 存在正常数茸使 啦榴 证明：我们分n 。= 。和a 女 一。( 警) 2 | | 也l | 2 因为 警如( ) 7 靠一鳜t d , , 。t k t d t 一。( 警) 2 j | d 七峨 所以 ( 警) 2 l l j d k l l 2 + 警靠如三一n ( 警) 2 j j 如庐 故n t 彘徘 硕士学位论文t 一类新型共轭梯度算法 如果挚使( 3 2 ) 不成立，目p 9 ( 。) r 【一9 ( 。) + 3 臼地竺生二曼翌：旦二；! 等；：鱼竺! ! _ = 堕! l ：堕兰竺毗 一。1 1 9 ( 。) l l z l l f k | | ( 3 3 ) 或 出舻h ( 峨) + 业熊妞堕罐喾蛐止塑堂至一c-119(u一划2 所以 娅唑业坚生唑祭地止避9 ( 峨) t d k ( 1 _ c 1 ) l l g ( 。) 1 1 ： o ， i i 鲰| | 2 “”7 1 。 所以g ( ) 7 d k 0 ，( 9 ( 7 k ) 一g k ) 7 d k + 9 靠 0 ，且9 吾呶 i g 吾d k l 则，n 女 群 如果( 3 4 ) 成立，可得： 一似) n 、l l g k ) 1 1 4 c o s 2 0 + 币 g ( f m 矿k ) t ( g ( o j k ) - - g k 一) 2 s i n 2 0 9 ) t d ： - - 0 2 胛 故 nllgk)l14cos20+gf(ojk万)t(g(ojk)-gk)2sin20一g(蚍)rdk(1一c2)llg(uk)112i。g k l l 2 。”、一 jllg(cok)114cos2o+可gk)而t(gk)-gl：)2sin2叫0(u)t如 。( 3 5 ) 又因为 口( “) t d k = l g ( w k ) t d t i = 1 0 ( “礓) 一g k ) t d k + g r kd k fsi 扫( u ) 一g k ) r d k i + i 霸f d ( 晚一1 ) l l g k l l 2 l - 警l l d k l l 2 c o s o + c 2 1 1 9 k l t 2 c o s o + l ? i l d k l l 2 s i n 口 ( c 2 1 ) l l g k l l 2 ( c o s o + s i n o ) l - q 芋l l d k l l 2 ( c 2 一c 2 c o s 0 1 ) l l g k l l 2 因为，c 2 丽1所以，c 2 一c 2 c o s o 一1 0 可得， 咿焉鬻导三o 丽i i g , k l f f2 篙蒜劣等髂 最后，令 石= i n i n p i l + 。a ，三， 。( 2 c o s ( 1 - c 0 6 i n o ) - 工1 也1 ， 所以弓i 理成立 定理3 1若在假设(