（应用数学专业论文）非线性优化问题的一类共轭梯度算法研究.pdf

摘要 对于非线性优化问题寻找快速有效的算法一直是优化专家们研究的热门方 向之一经理论证明和实践检验，在所有需要计算导数的优化方法中。最速下降 法是最简单的，但它速度太慢；拟牛顿方法收敛速度较快。被广泛认为是非线性 优化最有效的方法之一；1 9 6 4 年f l e t c h e r 和p t e e v e 8 提出了求解无约束极小化 问题m i e 歹扛) 的共轭梯度法它是直接由l t e f l 懒和s t i e f e | 解线性方程组 的共轭梯度法发展而来的，共轭梯度法具有占用内存少。二次终止性和良好的数 值表现等优点，它的基本思想是把共轭性与最速下降方法相结合，经常用来解决 大规模问题然而当目标函数为一般的非线性函数时。即使在精确线搜索下，各 共轭梯度法的收敛性也很难保证在文献f 2 】中a i - b a a l i 证明了f l e t c h e r - r e e v e s 方法具有全局收敛性，文献f 5 】推广上述结果到非精确搜索即强w o l f e 线搜索 的情形，但因其可能连续产生小步长的性质使得f r 方法在数值计算中有时表 现很差：p r p 和h s 方法是数值表现较好的两种轭共梯度算法，但是p o w e l l 在【3 1 中指出，即使使用精确线搜索p l a k - p d b i 6 r e - p o l y a k 方法也不会有全局收 敛性。但此方法具有良好的数值表现( 详见【1 3 ，1 9 ，3 3 】) 随后有许多学者对这 些算法的全局收敛性做了更深刻的研究，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 l a k r i b i 6 r e - p o l y a k 方法的全局 收敛性( 参见f 2 7 ，2 8 1 ) 1 9 9 5 年戴或虹和袁亚湘提出了d y 法，并对这一方法的 全局收敛性和内在性质做了详细的研究d y 方法具有很好的收敛性，d a i 在 文献【1 0 】中系统的介绍了d y 方法在一般线搜索下的全局收敛性，但其数值表 现般为寻求既能保证具有较好收敛性质又具有良好数值表现的共轭梯度类算 法，在前述文献的基础上本文给出了求解无约束非线性优化问题的一类新的共轭 梯度算法数值实验表明此类算法是有效的 论文整体安排如蕾 在第一章中，我们首先简要介绍了最优化问题的提出以及判断最优解常用的 最优性条件，回顾了无约束优化问题常用的几类导数下降类算法 在第二章中，就一般共轭梯度法的迭代格式。受d a i - y u a n 共轭梯度算法提 出的启发，我们给出个新的共轭梯度算法，算法中新参数的选取保证了搜索方 向的下降性，并证明新算法在w o l f e 线搜索下具有全局收敛性 在第三章中，基于第二章中给出的新参数给出了另个新参数，并证明此算 法在强w o l f e 线搜索下具有搜索方向的充分下降性和算法的全局收敛性 关键词：共轭梯度法，非精确线性搜索。无约束最优化。全局收敛性 a b e t r a c t s e e k i n g f a s tt h e o r e t i c a l c o n v e r 学e u c ea n de f f e c t i v ea l g o r i t h m si nu n c o n s t r a i n e d o p t i m i z a t i o ni sav e r yi n t e r e s 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 a n de n g i n e e r s t h ef a v o r a b l en u m e r i c a le x p e r i e n c ea n dt h e o r e t i c sh a v ep r o v e d t h a tt h es t e e p e s td e c e n tm e t h o di st h es i m p l e s tm e t h o dw h e na p p l i e dt ou m c o n s t r a i n e do p t i m i z a t i o nh u ti t sc o n v e r g e n c er a t ei st o os l o w ；i ta t s os h o w s d e a r t yt h a tn o n - q u a s i - n e w t o nm e t h o d sa r ew i d l yc o n s i d e r e dt ob eo n eo ft h e m o s te f f i c i e n tm e t h o d sb e c a u s eo fi t sf a s t e rc o n v e r g e n c er a t e ；i n 1 9 6 4 ，f l e t c h e r a n dr e e v e sp r o p o s e dt h ec o n j u g a t eg r a d i e n tm e t h o df o rs o l v i n gt h em i n i m u m o f 仰锄t r a i n e do p t i m i z a t i o nz r a 田i nm ) w h i c hc k l n ef r o mt h ec o n j u g a t eg r a d i - e n tm e t h o df o rs o l v i n gl i n e a re q u a t i o n st h a th e s t e n e s sa n ds t i e f e lp r o p o s e d1 1 1 i np a p e r 2 1 ，a l - b a a l ip r o v e dt h eg l o b a lc o n v e r g e n c eo ff l e t c h e r - r e e v e sm e t h o d a n dp a p e r 1 5 jd e v e l o p e di tt ot t s eu n e x a c tl i n es e a r c h ：s t r o n gw o l f el i n es e a r c h ，b u tb e c a u s ei tm a y b ec a u s e ds m a l ls t e pt h ef rm e t h o di sv e r yb a di nn l l r n e r - i c a l “p e r i m e n t s p r pa n dh sm e t h o 出a r em o r eb e t t e rm e t h o d 8i nn u m e r i c a l e x p e r i m e n t s ，b u ti np a p e 1 3 】p o w e l lp r o p o s e dt h a tp r pm e t h o dc o u l dn o t c o n v e r g eg l o b a l l ye v e nu n d e re x a c tl i n ss e a r c h b u ti th a de f f e c t i v en u m e r i c a l p e r f o r m e n c e 【1 3 ，1 9 ，3 3 】a n dt h e nm a n ys p e c i a l i s t ss t u d i e dg b b a lc o n v e r g e n c e0 f t h o e s em e t h o d sd e e p l y i n1 9 9 7 l g r i p p oa n ds l u c i d ip r o p o s e dg r i p p o - l u c i d i l i n es e a r c ha n dp r o v e dt h eg l o b a lc o n v e r g e n c eo fp r pm e t h o du n d e rt h i sl i n e s e a r c h1 2 7 购i n1 9 9 5 ，d a iy u h o n ga n dy u a ny a x i a n gp r o p 0 8 e dd yn 蛐o da n d s t u d i e di t sg l o b a lc o n v e r g e n c ea n di t sp r o p e r t yd e e p l y t h ec o n v e r g e n c eo fd y m e t h o di 8v e r yw e l l i np a p e r 【1 0 1 d a ii n t r o d u c e dt h eg l o b a lc o n v e r g e n c eo fd y m e t h o du n d e rt h es i m p l el i n es e a r c h b u ti ti 8n o tv e r yg o o di nn u n e r i c a le x - p e r i m e n t s i no r d e rt of i n dg o o dm e t h o dt h a th a v eb e t t e rc o n v e r g e n c ea n dm o r e e f f e c t i v en u m e r i c a lp 捌o r m e n c e , t h i sp a p e rg i v e san e wc l a s so fa l g o r i t h mt h a t c a ns o l v eu n c o n s t r a i n e dn o n l i n e a ro p t i m i z a t i o np r o b l e m s n u m e r i c a le x p e r i m e n t s i n d i c a t ot h a tt h i sa l g o r i t h mi sv e r ye f f e c t i v e i nc h a p t e r1 ，w ef i r s ti 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 e e x t e n s i v eo p t i m a l i t yc o n d i t i o n sw h i c ht od e c i d et h eo p t i m u ms o l u t i o n w er e v i e w s e v e r a le 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 so fu 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 ，t h i n k i n go fe x p r e s s i o no fg e n e r a lc o n j u g a t eg r a d i e n tm e t h o d s a n dr e a 8 0 n i n go fd ym e t h o d ，w ep r o p o s enn e wc o n j u g a t eg r a d i e n ta l g o r i t h ma n d p r o v e dt h a tt h ec h o i c eo fn e wp a r a m e t e rc a ns e l n ye n s u r et h ed e c e n to fs e a r c h d i r e c t i o na n dg l o b a lc o n v e r g e n c eu n d e rw o l f el i n es e a r c h i nc h a p t e r 3 ，b a s e do nt h en e wp a r a m e t e ro fc h a p t e r2 ，w ep r o p n s ea n o t h o e r n e wp a r a m e t e r a n da ts 8 m et i m ew ep r o v et h ed e c e n ta n dg l o b a lc o n v e r g e n c eo f t h i sc o n j u g a t eg r a d i e n ta l g o r i t h m k e yw o r d s ：c o n j u g a t eg r a d i e n tm e t h o d ，i n e x a c tl i n es e a r c h ，u n c o n s t r a i n e d o p t i m i z a t i o n ，g l o b a lc o n v e r g e n c e 首都师范大学学位论文原创性声明 本人郑重声明- 所呈交的学位论文。是本人在导师的指导下，独立进行研究 工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或 集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体。 均巳在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学雠黼繇码、汹 日期溯年石月7 日 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将 学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将 学位论文的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出 版保密的学位论文在解密后适用本规定 学位论文作者签名。钓够f 日期洳彬月7 日 1 非线性优化问题简介 这一章里，我们简要介绍非线性优化问题的发展及现状在1 1 中。简 要地阐述最优化问题的提出以及判断最优解常用的最优性条件；在1 2 中 总结了无约束优化问题常用的线搜索和几类导数下降类算法，重点是共轭 梯度法的发展过程及基本理论；在1 3 中。介绍了我们提出新算法的主要 思想 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一门应用性很强的年轻学科虽然最优化可以追溯到十 分古老的极值问题，但直到1 9 4 7 年d a n t z i g 提出一般线性规划问题的单纯形法 之后，它才成为一门独立的学科随着现代科技的发展和计算机的广泛应用，进 一步推动了最优化理论和算法的研究今天，最优化理论与方法在经济规划、政 府决策生产管理、交通运输和军事国防等方面都得到了广泛的应用，已经成为 一门十分活跃的学科 一般来说，最优化问题可归结为求解如下的极小值问题 r a 邶i n 弛) ( 1 1 1 ) 其中。z d 是决策变量，f ( x ) 为目标函数，d 舻为可行域 根据变量的类型，最优化问题可分为连续型最优化和离散型最优化( 也称组 合优化) 连续型最优化问题又可分为目标函数和约束函数均为线性时的线性优 化问题，以及目标函数和约束函数中至少有个为非线性时的非线性优化问题 根据可行域d 的类型，非线性优化问题又可分为约束优化和无约束优化问题 即当d = 舻时，无约束最优化问题为， 翼象m ) 其中i ：j p r 为非线性连续函数 一般约束优化问题通常可描述为t ( 1 1 2 ) r a i n ，( z ) j t c ( z ) s0 ， = 1 ，2 ，m ； c i ( z ) = 0 ，i = m ，4 - 1 ，m 4 - 2 ，m ；( 1 1 3 ) 本文主要研究无约束最优化问题，即 勰，( z ) 其中，：j p 一月为非线性连续函数 下面我们给出全局最优解和局部最优解的定义 定义1 1 若矿j p 具有性质tv z 舻，均有，( z ) ，( 矿) ，则称矿为问 题( 1 1 2 ) 的全局最优解 定义1 2 若矿舻具有性质：存在矿的某个邻域( 矿) = zj i x - - x 0 0 为某个正数，使得v z n 6 ( 矿) ，均有，( z ) ，( 矿) ，则称r 为问 题( 1 1 2 ) 的一个局部最优解 当日标函数，( 髫) 是凸函数时，局部最优解就是全局最优解但在一般情 形下找出全局最优解非常困难。通常在非线性优化中我们认为局部最优解即为 所求的解在实际的算法中，一般是找出满足局部最优解的必要条件的点记 9 ( z ) = v f ( x ) 表示l ( x ) 的梯度。g ( z ) = v 2 ，( z ) 表示，( z ) 的h e s s i a n 矩阵 下面我们给出最优解的必要条件 2 则 引理1 1 【1 9 l ( 无约束优化一阶必要条件) 若矿为问题( 1 1 2 ) 的个局部最优解，且在矿的某个邻域内，( 对0 1 9 ( 矿) = 0 引理1 2 【1g 】( 无约束优化二阶必要条件) 若矿为问题( 1 1 2 ) 的个局部最优解， ( 1 1 4 ) 且在矿的某个邻域内，( z ) 0 2 则 9 ( 矿) = 0 ，g ( 矿) 0 引理1 3 1 9 1 ( k u h n - t u c k e r 条件) 若r 为问题( 1 1 3 ) 的个局部最优解。在正规性假定下， p + = ( p ；，成，p ：) t ，使得 n v ，( z + ) + 埘审q ( 矿) = 0 ， 心0 ，心vc i ( $ ) = 0 ， = 1 ，2 ，n 1 2 无约束优化问题的导数下降类算法 导数下降类算法是求解无约束优化问题 ( 1 1 5 ) 则必存在向量 ( 1 1 6 ) 翼豫m ) 常用的一类算法，它的基本思想是：对于当前的迭代点z ，首先确定一个搜索方 向呶，使得目标函数，( z ) 的值沿该方向是下降的，然后确定沿以方向行进的步 长k 并得到下一个迭代点z k + l = + k 氐 在这里，我们要确定的搜索方向应满足。 可，( 。女) 7 d k 0 以使，( z ) 在r 女点沿呔方向下降 为了行文的方便，在介绍线搜索和导数下降类算法之前，约定记号如下 = f ( x i ) ，鲰= 9 ( z k ) = v ，( 巩) ，鲰= 肌+ 1 一鲰，鼽= z 女+ l z 女= a i 呶 3 下面我们介绍常用的两种线搜索： 确定k 的过程多用线搜索( 也称一维搜索) 方法精确的线搜索就是在以 方向上寻求。最优。的行进距离k ，使得 f ( x k + a 女d t ) 2 恕3 ，( z k + a d i ) 由于目标函数的复杂性及计算误差的影响搜索通常为不精确的，非精确线 搜索不要求上式成立，而仅要求找到的k 能使目标函数在某种意义上达到令人 满意的下降常用的非精确线搜索如w o l f e 线搜索和a r m i j o 线搜索，现介绍如 下， w o l f e 线搜索：固定p ，口满足0 p 口 1 ，选取口 满足 舷统黪：二譬妒尸呔 强w j 线搜索；固定n 口满足0 p 口 1 ，选取钒满足 jf ( x k ) ，( z ，q k 以) p 帆9 扣k ) 7 也 1i g ( z k + o 以) 7 噍i 一口9 ( 孤) 如 推广w o l f e 线搜索。其中口l ( p ，1 ) ，观0 当0 1 = 眈时推广的w o l f e 线搜索 就是强w o l f e 线搜索，当观= 0 0 时推广的w o l f e 线搜索就是w o l f e 线搜索 、f ，( 1 w 程k ) 孰s f ( z k 意芝霉毫j s 警唑x ，：k ，) r d 弛k 标准a r m i j o 线搜索；固定a ( 0 ，1 ) ，6 ( 0 ，1 ) ，选取。女= 护，其中m 为使得下 式成立的最小非负整数 f ( w k + a ”d k ) 一，( z 女) 6 a ”g k 下面我们介绍几种常用的导数下降类算法。 最速下降法 人们在处理无约束最优化问题时，总希望从某一点出发，选择一个目标函数 值下降最快的方向，以利于尽快达到极小点正是基于这样一种愿望，早在1 8 4 7 4 年法国著名教学家c a u c h y 提出了最速下降法后来。c u r r y 等人作了进步的 研究该方法取d k = 一9 ( o i ) ，即每步都以负梯度方向作为搜索方向因为负 梯度方向是目标函数值下降最快的方向，所以该方法称为最速下降法这种方法 每次迭代的运算量不大，并且初始点翱不用很接近最优点矿，但最速下降方向 反映了目标函数的一种局部性质从局部看，最速下降方向是函数值下降最快的 方向，选择这样的方向进行搜索是有利的但从全局看，由于锯齿现象的影响， 即使向着极小点移近不太大的距离，也要经历不小的弯路，因此使收敛速率大为 减慢最速下降法并不是收敛最快的方法因此最速下降法一般适用于计算过程 的前期迭代或问摇步骤 共轭梯度法 共轭梯度法最初由h e s t e n e s s 和s t i e f e l ( 1 9 5 2 ) 为求解线性方程组而提出的， 它是最著名的共轭方向法由于解线性方程组等价于极小化个正定= 次函数， 故在1 9 6 4 年f l e t c h e r 和m 倒偿提出了求解无约束极小化问题m i n ，( z ) 的共轭 梯度法，它是直接由h e s o e 和s t i e f e l 解线性方程组的共轭梯度法发展而来 的1 1 1 共扼梯度法最本质的是共轭性质，1 9 3 6 年，b i r k h o f f 等学者引入了共轭 的概念在矩阵计算中，将g r a m - s e h m i d t 正交化方法推广为共轭方向法共扼 梯度法的基本思想是把共轭性与最速下降方法相结合。利用已知点处的梯度构造 一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点，从而提高算法 的有效性和可靠性当目标函数，( z ) 连续可微时，其迭代格式为 z k + i = x k + a d k( 1 2 1 ) 呶= 二赛+ 臃也。2 薹2 1 ( 1 2 2 ) 其中风为标量，g k = v f ( x k ) ，d k 为搜索方向而h 是通过某种线性搜索而获 得的步长对参数鼎的选取应满足所谓的共轭性，即当f ( x ) 为严格的凸二次 函数且采用精确线搜索时。方法( 1 2 1 ) j ( 1 2 2 ) 产生的搜索方向关于f ( x ) 的 h e s s i a n 阵共轭在算法中，初始点z l 被任意选定。终止标准是i ig kl i = 0 对 于参数反的选取著名的公式有t r 坐i i g k - 监l l l 2 ( f t e t c e r r e e 螂) ， 5 罐”：型掣( p l a k - r i b i 6 r e - p o l y a k ) ， jj u k - 1j i 一 艘2 若幕筠( h e s t e n e s s t i e f e l ) i i o 2 秽2 瓦两i i g k i i 。( d a i - y u a n ) 当h 是由精确线搜索确定的步长时，共轭梯度法具有二次终止性然而，当日标 函数为一般的非线性函数时。即使在精确线搜索下，某些共轭梯度法的收敛性也 很难保证在文献【2 】中a 1 - b a a l i 证明了f l e t c h e r - r e e v e s 方法具有全局收敛性， 文献【5 】推广上述结果到非精确搜索即强w o l f e 线搜索的情形，但因其可能连 续产生小步长的性质使得f r 方法在数值计算中有时表现很差p r p 和h s 方 法是数值表现较好的两种共轭梯度算法，但是p o w e l l 在【3 j 中指出。即使使用精 确线搜索p l a k - r i b i r e - p o l y a k 方法也不会有全局收敛性，但此方法具有良好的 数值表现( 详见1 1 3 ，1 9 ，3 3 】) 随后有许多学者对这些算法的全局收敛性傲了更深 刻的研究。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 l a k - r i b i & e - p o l y a k 方法的全局收敛性( 参见f 2 7 ，e s l ) 1 9 9 5 年 戴或虹和袁亚湘提出了d y 法，并对这一方法的全局收敛性和内在性质做了详 细的研究d y 方法具有很好的收敛性，d a i 在文献f l o 】中系统的介绍了d y 方法在一般线搜索下的全局收敛性，但其数值表现一般总的来说共轭梯度法在 求解高维的无约束优化问题时是一种有效的算法 牛顿法 牛顿法的基本思想是利用目标函数的二次t a y l o r 展开，并将其极小化取 d k = 一g ( x ) 一1 9 ( z k ) ，x k + l = 。- + d k 其中g ( z ) = v 2 ，( z ) ，这个方向呶源于牛顿方程g ( x k ) = 一g ( x k ) d k ，称为牛顿方 向对于正定的二次函数，牛顿法一步即可达到最优解对于非二次函数，由于 目标函数在极小点附近近似于二次函数，故当初始点靠近最优解时，牛顿法的收 敛速度较快，但若初始点远离最优解时，伉不一定正定，牛顿方向不一定是下 降方向，其收敛住就不能保证若瓯的逆不存在，算法将无法进行下去另外 确定搜索方向时需要计算h e s s e 矩阵。迭代的每一步都必须求解线性方程组，因 6 此计算量非常大 拟牛顿法 前面介绍了牛顿法，它的突出特点是收敛速度很快但是，运用牛顿法器要 计算二阶偏导数，而且目标函数的h e s m a n 矩阵可能非正定为了克服牛顿法的 缺点。人们提出了拟牛顿法拟牛顿算法的基本思想是t 用不包含二阶导数的矩 阵近似牛顿法中的h e a n 矩阵的逆矩阵由于构造近似矩阵的方法不同，因而 出现不同的拟牛顿法但近似f i n 阶对称正定矩阵h ( z k + 1 ) 必须满足拟牛顿 方程， 日针l 辙= 稚 拟牛顿法的搜索方向为d k = - - h ( x k ) g ( z k ) ，在著名的b r o y d e n 族拟牛顿法 中，刀；的校正迭代公式为； h k + l = k 一警+ 蓑州靠酬仇 哦珊s 2 一蕊+ 磊 其中0 p ，l 】，当0 分别为0 , 1 时即为著名的d f p 公式和b f g s 公式 经理论证明和实践检验，拟牛顿法已经成为求解无约束最优化同题中最有 效的一类算法它有许多优点，比如，迭代中仅需一阶导数不必计算h e s s i a n 矩 阵，当风正定时，算法产生的方向均为下降方向，并且这类算法具有二次终止 性，在一定的条件下，文f 1 9 ，2 9 ，3 0 ，3 1 ，7 j 等给出了除d f p 算法夕卜的b r o y d e n 族算法的超线性收敛性，而且还具有n 步二阶收敛速率可见，拟牛顿算法集中 了许多算法的长处但是拟牛顿算法的缺点是所需存储量较大，对于大型问题， 可能遇到存储方面的困难 非拟牛顿算法。 在研究拟牛顿法的同时，h u a n g ( 1 9 7 0 ) 提出一类比b r o y d e n 族更广泛的校 正公式，不要求校正矩阵满足拟牛顿方程，只要求当算法应用于凸二次函数时， 产生的搜索方向是共扼的，从而具有二次终止性1 9 9 1 年，袁亚湘1 2 0 1 提出了 一类非拟牛顿方法之后。1 9 9 7 年和2 0 0 0 年，陈兰平焦宝聪口3 3 2 1 又提出 7 了基于校正的非拟牛顿方程t 8 b k + 1 船= 阢( ) ，v t f 0 ，1 j 其中 q k ( t ) = t 醒乳+ 2 ( 1 一f ) r k r k 垒f k + l f t 一矗酝 k 为瓯的近似矩阵，由此得到具有双参数t ，饥的校正公式 ( t ，= 鼠一警十器鲰西坳k 曙 其中 。 k 娟r b k s k ) 。( 雏y k 五一舞) 记仇= 嚣1 ，则 风“厶纠= 风一警+ 毒裔十机玩翟 ( 1 2 3 ) 其中 忍娟暑砜呶) 5 ( 去一覆h 。k y 坐。玑) 文1 2 铷证明了该算法同样具有二次终止性及矩阵的正定对称传递性，并且由上 述算法产生的点列 。k 在一定的条件下具有全局收敛性和超线性收敛性其中 风的校正公式是一个具有双参数，九的公式当扛l 时，( 1 2 3 ) 即为b r o y d e n 族校正公式；当t = 0 时，得到伪n e w t o n - b 族校正公式 2 2 】 无记忆拟牛顿算法 2 0 世纪7 0 年代末，p e r r y 啦l 和s h a n n o 蕊9 ，儿l 首先提出了无记忆拟牛顿 方法较求解问题( 1 1 1 ) 的共轭梯度法，无记忆拟牛顿法无论在内存还是每次迭 代的计算量都没有增加多少。因此在求解高维无约束最优化同题( 1 1 1 ) 时，经 常采用无记忆拟牛顿法关于p e r r y - s h a n n o 无记忆拟牛顿方法的收敛性有下列 结果：对于一致凸函数。在a ”m i i o 线搜索或w j l f e 线搜索条件下算法收敛【o 】； 对于凸目标函数，在w o l f e 线搜索条件下，算法也是收敛的【“l ；但是对于非凸 目标函数，目前尚无统一的收敛结果鼢埘，l 圳 8 1 3 本文的创新点 共轭梯度法是求解无约束优化问题 砌u f i n 。m ) 的一类非常重要而且有效的方法，当目标函数f ( x ) 连续可微时。其迭代格式为 机+ l = 飘+ k 靠 d k = 咄- - g k + ，k d t - l 薹； 其中风为标量，肌= v ，( ) ，d k 为搜索方向而k 是通过某种线性搜索而获 得的步长对参数凤的选取应满足所谓的共轭性，即当，( z ) 为严格的凸= 次 函数且采用精确线搜索时。以上方法产生的搜索方向关于，( 。) 的h e s s i a n 阵共 轭 在设计反的计算公式方面有不少学者傲了不懈努力，除了著名的f r 、 p r p 和i - i s 公式外，近年来戴或虹和袁亚湘也提出了一个新的凤公式 殿= 瓦而i i g k t l 2 作者对此算法的全局收敛性和其内在性质作了很全面的研究由f l o 】我们知道 对于采用强w o l f e 线搜索的f r 共轭梯度法只要每步的搜索方向下降，则方法 在适当的假定下全局收敛在f r 共轭梯度法的基础上本文给出了两个确定的公 式，并证明了由它们确定的迭代算法在一定假定下具有全局收敛性，通过数值实 验表明新算法具有良好的数值结果 在第二章中，对一般的共轭梯度法的迭代公式( 1 2 1 ) ( 1 2 2 ) ，我们对其中的 参数像给出了一个新的公式，并且证明了此新算法在采用w o l f e 线搜索下具有 全局收敛性，这个新参数的选取本身保证了搜索方向的下降性 在第三章中，在第二章工作的基础上我幻给出了另一个计算参数段的公 式，并证明了在强w o l f e 线搜索下新算法具有搜索方向的充分下降性和全局收敛 性 在第二章和第三章中都做了适量的数值实验，其中的测试函数均出自文献 【1 4 】 9 2 在w o l f e 线搜索下一种新的共轭梯度法的全局收敛性 在这一章中，就一般共轭梯度法的迭代格式，受d a i - y u a n 共轭梯度算 法提出的启发，我们给出一个新的共轭梯度算法，并且本文还证明了算法 中新参数的选取保证了搜索方向的下降性及在w o l f e 线搜索下算法具有全 局收敛性 2 1 引言 共轭梯度法是求解无约束优化问题 。m 肿i n ，( z ) 的一类非常重要而且有效的方法，具有迭代简单，所需内存步等优点 当目标函数，( z ) 连续可微时，其迭代格式为 z k + l = z + a 毗( 2 1 1 ) 毗= 二蠢+ 凤一，d 。一。，2 主 ( 2 1 2 ) 其中臃一，为标量，著名的公式有t 鲻= 牌( f l e t 船r e e v e s ) 粥= 瞥( 眦x r i b i & e - p o t y a k ) 础= 蒜岩器c 胝e n 盼s t 喇， 魈；捣( d a i - y u a n ) 这里g k = v ，( o k ) ，噍代表搜索方向 当，( o ) 为凸函数时，适当选择参数压一1 使得以与d l ，d 2 ，出一1 关于，( o ) 的h e s s e n 矩阵共轭，n k 是由精确线搜索确定的步长。这时共轭梯度法具有二次 终止性 1 5 1 然而当日标函数为一般的非线性函数时，即使在精确线搜索下各共 轭梯度法的全局收敛性也很难保证另外，由于目标函数的复杂性及计算误差， 搜索通常为不精确的，这样算法的构造对算法的收敛性有重要影响 我们在研究的过程中首先要保证选取的步长o k 和搜索方向出能使相应的 共轭梯度算法是下降的，即满足旌以 0 使， j lg ( z ) 一g ( y ) 0 l0z y0 ，vz ，y 阢( 2 2 1 ) 1 1 本文算法中的步长o 由w o l f e 准则得到 ，( 钆+ n 以) 茎，( 觑) + g o o , g 彳d k 其中0 p d 0 ，d l = 一m ，七= 1 ( 2 2 2 ) ( 2 2 3 ) 步2 ：如果瓠l i e ，则停止否则t 由w o l f e 搜索( 2 2 2 ) ，( 2 2 3 ) 求得。女 缸+ 1 ；z k + n 以 步3 ：由( 2 1 4 ) 计算成，以+ l = - g k + 14 - 风呶，t ：+ 1 ，转步2 2 3 主要结果 引理2 3 1 国设目标函数满足假设h 考虑一般方法。k + l = z + n t 以，其 中呶满足d 幻i 0 ) 和c 为常数，如果正项级数体 对所有的都成 立 口2 l k + c t = l 1 2 则有 以及 萎譬= o 。 p 乙f 2 0 0 垃1 啦 = l 首先由假设条件( i ) ( i i ) 能够推出3 m 0 使i i9 ( z ) i i 0 ，使得 由( 2 3 5 ) ，( 2 3 6 ) 式易得 0 鲰0 mk = 1 ，2 ， 由如的非负性和( 2 3 ，7 ) ，则 符合引理2 3 2 条件 由( 2 3 5 ) 式可得 所以 则有 “一刍+ 杀妻n 士、m 2 ， 备啦丽膏 三 丝j l 如一2 占 乙q 与引理( 2 3 1 ) 矛盾! 此矛盾表明坚n ，0g k = 0 证毕 1 4 ( 2 3 5 ) ( 2 3 6 ) ( 2 3 7 ) ( 2 3 8 ) 南 。南。“ k 善勋 必 2 砑 瑶一“ 吼 群 纠 f | 口l 严邀 吼 2 4 数值试验 我们用来检验本算法的测试函数( 见文献【1 4 】) 如下 ，扣) = 1 0 0 【船一l o e ( x , ，z 2 ) 】2 + 1 0 0 ( x ；+ z ；) 一1 】2 + 霹 瑚= 窿：孰矗篡? ，( z ) = 斤( 刁 。 其中五( z ) = x s e x p - t i x l 】一x 4 e x p - t i x 2 l + x 6 e x p - t , x s 】一y l a n d 弘= e x p - - t i 】一5 e x p - - l o t i 】+ 3 e x p - 4 t 】 f ( x ) = e 斤( z ) 五( 。) ：。酬竺掣】_ 玑 w h e 毗：掣 ，( z ) = 【1 0 4 z l x 2 一l 】2 + i e x p ( - x , ) + e x p ( - x 2 ) 一1 0 0 0 1 2 f ( x 、= 结+ 绣+ 赡 其中： = e x p ( - t i x , ) 一e x p ( - t l x 2 ) 一如( 唧( 一屯) 一e x p ( - - l o t l ) ) 初始点：( o ，1 0 ，2 0 ) v a r i a b l e d i m e n s i o n a lf u n c t i o n 6 ) f ( x ) = ( 厅) + 缘。+ 岳2 其中：五= ( x i 一1 ) ，厶+ l = 0 ) ，厶+ 2 = 臆l 初始点；x 0 = ( 白) ，w h e r e 白= 1 0 n ) w a t s o nf u n c t i o nl ) f ( x ) = 费( z ) 其中五( z ) = 圭。一1 ) 一一( 麦q 牙。) 。一l =嘉，i 5 0 0 0f 5 0 0 0 536 27 0 1 7 1 1 6 5 【l 7 】 661 65 3 f l 7 | 5 2 【17 | 6l o o1 93 7 3 4 6 1 0 0 02 0 f4 2 65 0 0 0ff4 2 7 76 5 0 0 05 8 3 5 0 0 0 81 02 41 2 7 1 1 7 11 7 3 1 7 1 1 02 5 0 0 0f 5 0 0 0 1 323 8 44 39 2 1 4 1 46 93 6 1 7 18 1i l7 ) 1