（应用数学专业论文）求解大规模无约束优化与约束单调方程组的下降prp共轭梯度法.pdf

河南大学硕士学位论文 摘要 共轭梯度算法是求解最优化问题的有效算法，它特别适合于求解大规模的最优 化问题这一类算法的一个显著的优点是它具有较好的收敛性，而且存储量也很小 但是，大部分共轭梯度法不能保证产生下降方向，有些共轭梯度算法虽然具有下降 性，但是也很强地依赖于算法所采用的线搜索本论文研究一种基于新的共轭条件 的p r p 共轭梯度算法，主要讨论此方法的收敛性和数值表现全文共分四章 第一章，我们简要地介绍了数值最优化的发展背景，本文所用到的一些记号、基 本概念、定义及本文的主要结果 第二章，我们在l i ，t a n g 和w 西的修正p 1 0 如r i b 论渺p o l y a k ( p r p ) 共轭梯度法的基 础上( 1 1 ，提出一种求解非凸极小化化问题的新方法，此方法的一个显著特点是搜索 方向总保持下降，使用a r m i j o 型线搜索我们证明此方法具有全局收敛性，并对所提算 法做了大量的数值试验，结果表明我们的算法非常有效 第三章，我们提出求解凸约束的非线性单调方程组新的p r p 共轭梯度算法该 算法的优点是，可用于求解大规模非线性方程组的问题，并证明了该算法的全局收 敛性 第四章，总结本文，从而使我们对求解无约束的非线性共轭梯度法有了更进一 步的认识，并提出一些值得继续研究的问题 关键词：无约束最优化；共轭梯度法；p r p 方法；a r m i j o - t y p e 线搜索 i 河南大学硕士学位论文 a b s t r a c t c o n j u g a t eg r a d i e n tm e t h o di sa ni m p o r t a n ti t e r a t i v em e t h o df o rs o l v i n go p t i m i z a t i o n p r o b l e m s i ti sp a r t i c u l a r l yw e l c o m ei nt h es o l u t i o no fl a r g e - s c a l eo p t i m i z a t i o np r o b l e m s a g o o dp r o p e r t yo ft h ec o n j u g a t eg r a d i e n tm e t h o di si t sl o w e rs t o r a g ea n dg o o dc o n v e r g e n c e p r o p e r t y h o w e v e r ，m o s te x i s t i n gc o n j u g a t eg r a d i e n tm e t h o d sd on o tg u a r a b t e et og e t d e s c e n td i r e c t i o n sf o rt h eo b j e c t i v ef u n c t i o n a l t h o u g hs o m eh a v ed e s c e n t ，b u ta l s ov e r y d e p e n d e n to nt h ea l g o r i t h mu s e db yl i n es e a r c h i nt h i ss t u d y , b a s e do nt h ec o n d i t i o n so f n e wc o n j u g a t ep r pc o n j u g a t eg r a d i e n tm e t h o d t h i sm e t h o df o c u s e so nc o n v e r g e n c ea n d n u m e r i c a lp e r f o r m a n c e t h e r ea r ef o u rc h a p t e r si nt h i sp a p e r t h ef i r s tc h a p t e r ，w eb r i e f l yi n t r o d u c e dt h eb a c k g r o u n do ft h ed e v e l o p m e n to fn u - m e r i c a lo p t i m i z a t i o n ，s o m en o t a t i o n su s e di nt h i sp a p e r ，b a s i cc o n c e p t s ，d e f i n i t i o n sa n d m a i nr e s u l t s c h a p t e ri i ，b a s i n go nl i ，t a n ga n dw e ia m e n d m e n tp l o a k - r i b i 毛r e - p o l y a k ( p r p ) c o n j u g a t eg r a d i e n tm e t h o d 1 w ep r o p o s e dt ot h en e wm e t h o do fs o l v i n gt h ep r o b l e mo f n o n - c o n v e xm i n i m i z a t i o n t h i sm e t h o di sc h a r a c t e r i z e db yas i g n i f i c a n to v e r a l ld o w n w a r d d i r e c t i o no ft h es e a r c h ，u s i n ga r m i j o - t y p el i n es e a r c hp r o v et h i sm e t h o dh a v i n gg l o b a l c o n v e r g e n c e ，a n dt h ea l g o r r h mh a sd o n ea l o to fn u m e r i c a le x p e r i m e n t s t h er e s u l t s s h o wt h a to u ra l g o r i t h mi sv e r ye f f e c t i v e c h a p t e ri i i w ep r o p o s en e wp r pc o n j u g a t eg r a d i e n ta l g o r i t h mf o rs o l v i n gc o n - s t r a i n e dn o n l i n e a rm o n o t o n ee q u a t i o n s t h ea d v a n t a g eo ft h i si st h a ti tc a nb eu s e dt o s o l v el a r g e - s c a l en o n l i n e a re q u a t i o n so ft h ep r o b l e m ，a n dp r o v et h eg l o b a lc o n v e r g e n c eo f t h ea l g o r i t h m c h a p t e ri v ，t h o u g hc o n c l u d i n gt h i sp a p e r ，w eh a v ef u r t h e ru n d e r s t a n d i n go fm e t h o d w i t hs o l v i n gu n c o n s t r a i n e dn o n l i n e a rc o n j u g a t eg r a d i e n ta n dp r o p o s es o m ew o r t h w h i l et o c o n t i n u er e s e a r c h 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 ；c o n j u g a t eg r a d i e n tm e t h o d ；a r m i j o - t y p e l i n es e a r c h ；p r pm e t h o d i i 关于学位论文独立完成和内容创新的声明 了删僦= 露鲻釜一 ，? ：q 。 ：t薯。：j 。 ti ， ，x i ，1 1 ， 学位中请丸“e 学位论文作者) 一釜名：；：z 复! ! = = ! 萋? 一誓0 镰。0 五j f 移豫“l j ，j ：暑| j 。 ：爹譬? 孙t 镌j j 2 j 卑一j , z 硼，孽目 囊；、，；，i 霎”0 ：譬囊参- j ，7 、了j 一，享i o 、+ 一。! 善 j # 一一 “ 1 鬻，关于学位论文著作权使用授权书。荔 学位获得者( 学位论文作者) 釜名： 2 0年 月 日 学位论文指导教师鍪名：互毖么鸷 2 0年月 日 第一章绪论 最优化理论与方法是一门应用性很强的学科，它的起源可以追溯到微积分诞生 的年代然而，直到上世纪三四十年代，由于军事和工业生产的迫切需要，才使得最 优化技术得到蓬勃发展近年来，随着计算机的发展和网络的普及，各种优化模型的 数值优化算法在经济计划、工程设计、交通运输等领域得到广泛的应用 在生产管理、经济计划、石油勘探、大气模拟、航空航天、数据挖掘、工程设计 等以及许多高尖端的科技领域经常出现未知变量越来越多大规模问题可以视为目 标函数的结构非常复杂，而且约束条件数量也十分庞大的优化问题研究求解大规 模问题具有十分重要的理论和实际意义计算机领域的发展，以及国际互联网络的 出现，对求解大规模优化问题提供了方便进入2 1 世纪以来，求解大规模优化问题的 算法设计以及理论创新已经受到数学家们的广泛关注 1 1非线性共轭梯度法概述 无约束最优化问题的一般形式为： r a i nf ( z ) ，z r n ， ( 1 1 ) 其中函数，：r n _ 豫连续可微，且它在x k 处的梯度记作g ( x k ) ，并简写为g k 求解问题( 1 1 ) ，通常采用迭代算法即给一个初始点x o r 几，按照一定的准则产 生一个点列 z 知】- ，使当z 知是有限点列时，其最后一点是问题( 1 1 ) 的最优解；当z 七是无 穷点列时，它有极限点，且其极限点是问题( 1 1 ) 的最优解，其迭代形式为： x k + l2x k + q 七d k ， 其中步长o l 七由一些线搜索得出，毗为搜索方向 最速下降法，取d 七= 一g 七，即每步都以负梯度方向作为搜索方向由于负梯度 方向是目标函数值下降的方向，故该方法称为最速下降法这种方法每次迭代的运 算量不大，且初始点不用很接近最优点，但是其收敛速度慢 牛顿法是求解优化问题的古老而有效的方法，取嗾= 一g i l 9 k ，( g 七是目标函数 在z 七的h e s s e 矩阵) ，这个方向也源于牛顿方程g 七d 七+ g k = 0 ，称为牛顿方向相对于其 】 河南大学硕士学位论文 它的求解无约束问题的方法，该方法在找到最优点时需要较少的迭代次数和函数值 计算次数然而，牛顿法要求计算目标函数的二阶导数，并且当迭代点远离问题的解 时，h e s s e 矩阵可能不正定甚至奇异，从而导致牛顿法失败 共轭梯度算法仅需要利用一阶导数的信息，不仅克服了最速下降法收敛慢的 缺点，又避免了存储和计算拟牛顿法所需的二阶导数的信息共轭梯度法最早是 由h e s t e n e sf 2 1 和s t i e f e l 3 在1 9 5 2 年求解线性方程组 a x = b z 舻 ( 1 2 ) 时而独立提出的，合作文章 4 详细地讨论了求解线性方程组的共轭梯度法的性质以 及它和其他方法的联系在a 为正定矩阵时，线性方程组( 1 2 ) 就等价于无约束最优化 问题 1 一一 m i n f ( x ) = 丢za x + bz z r n ，( 1 3 ) 由此，h e s t e n e s 和s t i e f e l 的方法也可视为求二次函数极小值的共轭梯度法1 9 6 4 年f l e t c h e i 和r e e v e s 3 0 将此方法推广到求解非线性极小化问题中，提出了求解非凸函数极小值 的共轭梯度方法 非线性共轭梯度法的迭代公式是 x k + l = z 知+ a k d k ，k = 0 ，1 ，( 1 4 ) 其中步长o l k 由线搜索得出，x o 为初始迭代点，搜索方向毗由f 面公式得出 1 b 如果梏0 ( 1 5 ) 【一g k + 觎d k 一1 ，如果k 1 ， 其中鲰= v ，( 砜) ，仇是参数，凤的不同取法对应不同的非线性共轭梯度法，常见形 式为： 簇r ：磐( f l e t c h e r - r e e v e s 3 0 】，1 9 6 4 ) ； ( 1 6 ) “一1 鲰一1 茚哮掣 酽= 面9 ：丽( g k - - 了q k - 石1 ) ( p o l a k - r i b i e r e - p o l y a k 【5 】 1 9 6 9 ) ；( 1 7 ) 2 ( h e s t e n s e s - s t i e f e l 4 】，1 9 5 2 ) ； ( 1 8 ) 河南大学硕士学位论文 船k 面蓑争磊( d a i - y u a n 【6 ，1 9 9 9 ) ； ( 1 9 ) d 一嚣( c o n j u g a t e d e s c e n t f 7 1 9 8 7 ) ( 1 1 0 ) 舻一掣( l i u s t o r e y 【8 ，1 9 9 1 ) ( 1 1 1 ) 硭y 一日s = m a x 0 ，m i n z b y , p 日s ) ( d a i - y u a n 9 】，2 0 0 1 ) ( 1 1 2 ) 其相应的共轭方法缩写为f r 、p r p 、h s 、d y 、c d 、l s 、d y - h s 方法如果，是严格 二次凸函数，那么这些方法在使用精确线搜索且第一个搜索方向是最速下降方向时， 上面的非线性共轭梯度法等价对于非凸的极小化问题，这些方法则大不相同因 此，这些方法近年来受到广泛关注 1 0 、 1 1 、 1 2 、【1 3 、 1 4 、【1 5 、【1 6 、 17 】它具有 算法简单、易于实现、存储需求少等优点，非常适合于大规模优化问题因此，研究 共轭梯唐法有很日吕的理论和实际煮义 1 2线搜索 为了保证算法的全局收敛，需要利用某种线搜索方法来确定步长因子q 七，它是 从迭代点钆沿搜索方向九寻找一个“好”的点作为下一个迭代点显然，最好的点是 在这个方向函数值达到最小的点，步长因子q 詹的计算也至关重要，下面我们就给出 几种常用的确定步长因子a 知的线搜索准则 ( 1 ) 精确线搜索 求步长因子q 七满足 ，( z 七+ q 七d 七) = m i n f ( x k + a d k ) ，( 1 1 3 ) 即要求下一个迭代点是搜索方向如上的精确极小值点 因为精确线搜索要求一个单变量函数的极小值，计算量较大，所以在实际计算 中常用非精确线搜索下面介绍几种非精确线搜索： ( 2 ) a r m i j o 型线搜索 步长因子a 知 o 满足 ， 豇+ 口| c d ) f ( x 砖) + 6 q 七g - j d k ，( 1 1 4 ) 3 河南大学硕士学位论文 其中0 6 1 ( 3 ) 标准的w o l f e 线搜索 步长因子q 七满足 f ( x k + o t k d k ) ，( z 知) + , 5 a k g ；d k ， g ( x k + o e k d k ) ld k 盯9 2d k ， 其中0 6 0 - 1 是两个常数 ( 4 ) 强w o l f e 型线搜索 求步长因子a 七满足 ( 1 1 5 ) ( 1 1 6 ) f ( x k + a k d k ) s ( x k ) + 8 a k g - j d k ，( 1 1 7 ) i g ( x k + a k d k ) t d k l 0 - g - 丁d k ，( 1 1 8 ) 其中o 6 盯 1 是两个常数当仃= o 时，必有夕矗1 d k = 0 ，因此，强w | o l f e 型线搜索 是精确线搜索的一种推广 ( 5 ) 广义的w o l f e 型线搜索 求步长因子q 七满足 ，( z 七+ a k d k ) f ( x k ) + 6 a k g j d k ，( 1 1 9 ) 0 - 1 9 - j d k 冬g ( x k + a k d ) t d k 0 - 2 订d k ，( 1 2 0 ) 其中0 0 - 1 1 ，o 2 0 上面所有的线搜索准则，都要求搜索方向也是下降的，从而使目标函数，( z ) 找 到最好的点称满足纸t 也 o 的搜索方 h - j d k 为下降方向，称总是能产生下降方向的算 法为下降算法当采用非精确线搜索方法时，不一定所有的非线性共轭梯度算法都 能保证每一步都能产生下降方向，此时大家一般采用负梯度方向作为搜索方向，但 是如果多次使用负梯度方向收敛速度会很慢，所以大家常常会重新开始 1 3p r p 方法 p r p 方法是f h p o l a k 、r i b i 爸r e 和p o l y a k 在1 9 6 9 年分别独立提出的一种非线性共轭 梯度法，它简称为p r p 方法，此方法被认为是目前数值表现最好的共轭梯度法之一 4 河南大学硕士学位论文 因为当算法产生一个小步长时，f i j p a p 方法定义的搜索方向如会自动靠近负梯度方 向，从而具有自动开始的功能，较为有效的避免了f r 方法可能连续产生小步长的缺 点 p o w e l l 1 s 证明了当步长s 七一0 ，8 k = x k + 1 一z & = q 七d k 时p r p 方法的全局收敛性， 并且证明了采取精确线搜索的p r p 方法对于一致凸函数是全局收敛的但对于一般 的一致凸函数，p o w e l l 1 9 举出了一个反例，说明p f u p 方法也可能在几个迭代点附近 循环，而其中任何一个迭代点都不是目标函数，( z ) 的稳定点，因而破坏了算法的全局 收敛性 如果使用非精确线搜索，比如强w o l f e 型线搜索，d 面 2 0 】举例说明了即使原函数 一致凸，且参数0 0 和0 p 1 ，令 q 知= m a x 乃而# l g 矿d a l ，j = 0 1 ) ， ( 1 2 1 ) 使其满足 f ( x 知+ 1 ) 一f ( x 知) 一引j q 七d 知1 1 2 ，( 1 2 2 ) 和 c 1 9 ( x k + a ) 1 1 2 9 ( z 1 ) t d 七+ 1 - c 2 l l g ( x k + 1 ) 1 1 2 ，( 1 2 3 ) 其中o c 2 1 c 1 是常数 5 河南大学硕士学位论文 另外，d a i 采 y u a n 2 2 讨论t p r p 方法的一个新性质，即取常数因子的p r p 方法在 每次迭代都产生一个下降的方向，而且证明了其全局收敛性但这种常数步长因子 的选取依赖于l i p s c h i t z 常数厶而常数l 往往不能预先估计，因此在实际计算中不容 易操作 h a g e r 和z h a n g 2 3 提出了一种不依赖线性搜索能产生下降方向的非线性共轭梯 度法： 似坐掣- - s k _ l y k _ 1 k - 1 ) ，m 2 4 ， 1 rr - k - t 头下8 k2x k + l x k ，y k - 159 一g k - 1 近来，w e i ，y a o 和l i u 2 4 1 提出了一个结合f r 和p r p 方法的共轭梯度法公式： 硝y l ：g k t ( g a 丁- 黜一g k - 1 ) ( w e i - y a o - l i u 2 4 , 2 0 0 6 ) , 夕一l g k 一1 该方法在s w p 线搜索条件下具有充分下降和仇o 的性质，同时在g r i p p o - l u c i d i 线搜 索、w o l f e - p o w e l l 线搜索和精确线搜索条件下都具有全局收敛性除了以上对p r p 共 轭梯度方法的收敛性介绍以外，关于其他的共轭梯度算法，及其修正算法和相关算 法的收敛性分析等问题，可参考h a g e r $ f l z h a n g 笆j 综述性文献 1 2 及d a i 和y u a n 关于非 线性共轭梯度法的专著f 2 2 】 最后，我们给出求解问题( 1 1 ) 的非线性共轭梯度法( p r p 算法) 的算法步骤如 下： 算法1 3 1 步0 取初始点z o r n ，d o = 一g o 令k ：= 0 步1 若i | 鲰ij = 0 ，则算法终止，得问题的解瓢，否则，转步2 步2 由p 纠式确定d ，其中凤= 茚即 步3 由线搜索确定步长o e 七，令x k + 1 = z 七- i - a k d k 步4 令k ：= k + 1 ，转步1 6 河南大学硕士学位论文 1 4 本文主要工作 本论文研究新的共轭条件的p r p 共轭梯度算法，主要讨论此方法的收敛性和数 值表现 第二章，l i ，t a n g 和w e i z 提出了求解无约束最优化问题的一种p r p 方法，并分 析了该算法求解一致凸函数的及小化最优解的收敛性，本章基于【2 5 提出的共轭梯 度法，修正【1 中的算法，使之能够求解非凸极小化问题此方法的一个显著特点是搜 索方向总保持下降，使用a r m i j o - t y p e 线搜索我们证明此方法具有全局收敛性，并对 所提算法做了大量的数值试验，结果表明我们的算法非常有效 第三章，推广第二章所提算法使之求解凸约束的非线性单调方程组的问题该 方法不需要j a c o b i a n 矩阵信息，迭代简单，存储量小 7 河南大学硕士学位论文 1 5本文所用记号 z ：实变量 ，( z ) ：目标函数 n ：目标函数的维数 z 七：第k 次迭代点 酞：全体实数组成的集合 r n ：全体n 维实向量组成的集合 g k ：目标函数，( z ) 在点x k 处的梯度 j ：几阶单位矩阵 ：向量的无穷模 怙：矩阵的f r o b e n i u s 范数 i i ：向量的欧氏范数 f ( z ) ：非线性方程组 a t ：矩阵a 的转置 j ：单位矩阵 8 第二章一种基于新共轭条件的p r p 共轭梯度算法 2 1引言 本章我们考虑大规模无约束优化问题 r a i n ，( z ) ，z r n ， 其中函数，：时_ r 连续可微，且它在a ：k 处的梯度记作g ( x 知) ，并简写为g j c p r p 方法是由p o l a k 、r i b i 色r e 和p o l y a k 在1 9 6 9 年独立提出的种非线性共轭梯度 法，这种方法具有如下迭代形式： x k + l2x k 十o c k d k ，k = 0 ，1 ， ( 2 1 ) 其中 d 七= 一- - 9 9 知k , + 风d 惫一。，：蓁：蓁： c 2 2 ， 其中参数觑由以下公式计算： 雕r p ：亟拿二旦出 2 0 0 7 年，l i ，t a n g 和w e i 1 提出了求解无约束最优化问题的一种p r p 方法，并分析了该 算法求解一致凸函数的极小化最优解的收敛性，本章基于【2 5 提出的共轭梯度法，修 正【1 中的算法，使之能够求解非凸极小化问题 2 2算法设计 本节，简单描述l i ，t a n g 和w e i 1 提出的修正p r p 共轭梯度方法首先给出两个 假设条件： 假设2 2 1 水平集厂= z r n f ( z ) ，( z o ) ) 有界 假设2 2 2 在厂的邻域上，可微且梯度l 匆s 咖i t 琏续，即存在l 满足 i t g ( x ) 一g ( y ) l ls 工1 1 2 可忆比，y ( 2 3 ) q 河南大学硕士学位论文 由假设可知存在一个正常粉使得 i b ( z ) i i 可，v z 尸 ( 2 4 ) 在求解无约束最优化问题( 1 1 ) b f l ，为了得到目标函数的更精确逼近，w e i ，l i 和q i 提 出了一个新的割线条件【2 6 】： b k 8 k 一1 = 皖一1 = 讥一1 + a j c 一1 8 k 一1 ，( 2 5 ) 其中鼠是v 2 ，( z 知) 的一个近似，并且 址= 坐吐气黼 型生 ( 2 6 ) 在( 2 5 ) 式提出的新的割线条件的基础上，l i ，g 和w 西【1 修改了关于凤的p r p 方法， 即 卢f p r p _ 丞， ( 2 7 ) 其中玩一1 = y k 一1 + m a x a 一1 ，o s k 一1 由以上式子我们可以看出，这个新的方程不仅 包含梯度值信息，而且包含函数值信息结合强w 6 l 缸p o w e u 线搜索，由( 2 7 ) 式所定义 的共轭梯度法可用于求解一致凸极小化问题，但是求解非凸极小化问题的收敛性分 析没有给出 近来，z h a n g 、z h o u _ ； 1 l i 2 5 提出修正的p r p 共轭梯度法，即 d 七= 一- 鲰g k + 凤d 七一，一日七弧一。翥蓁：蓁；： c 2 8 ， 其中钆= 碳蛴结合( 2 5 ) 所定义的缑一1 ，有 虻 咄 如果枉o ( 2 9 ) 【一鲰+ 硝p 即呶一1 一靠玩一1 如果k 1 ， 。 其中靠= 秩蛴，易知，由上述所定义的比满足 g - j d k = 一i i 鲰忾 ( 2 1 0 ) 下面我们提出新的算法( n p r p 算法) ，如下 步0 取初始点z o r n ，假设o 6 1 ，d o = 一g o 令k ：= 0 河南大学硕士学位论文 步1 若i l 鲰l = 0 ，则算法终止 步2 由( 2 9 ) 式确定如 步3 由下式确定步长q 七 f ( x k + o e k d k ) 一f ( x k ) - - 5 1 1 a k d k 1 2 ，( 2 1 1 ) 令x k + 1 = z 七+ q 岛d 七 步4 令k ：= k + 1 ，转步1 2 3收敛性分析 本节我们给出新算法的收敛性分析为了证明的需要我们首先给出几个引理 引理2 3 1 在假设幺2 1 2 2 碱立的条件下，有 证明：由( 2 1 1 ) 式得口七因此，由( 2 1 0 ) 和( 2 1 1 ) n - i 得 + 1 一 一6 f q 七比i i 2 0 ， ( 2 1 2 ) ( 2 1 3 ) 且p i k 是递减序列，且 z 七】在，中，从假设2 2 1 2 2 2 可以得到存在一个常数，+ ，使 得 1 i m = ，+ ，( 2 1 4 ) 从( 2 1 4 ) 可得 ( 一 一1 ) + o o k - - o 再由( 2 1 3 ) 可得( 2 1 2 ) 证毕 引理2 3 2 在假设2 2 j 2 ，2 碱立的条件下，有 其中l 是由假设2 2 绽义的 i 玩一1 | 2 l i i s , i i ， 1 1 ( 2 1 5 ) 2 k d k q 6 脚 河南大学硕士学位论文 证明：由( 2 1 3 ) 式得 x k 厂，v k 1 另一方面，由中值定理可得存在讯【0 ，1 ，使得 ( 2 1 6 ) + 1 一 = 夕( 。知) + 叼( x k + 1 一z 七) t ( z 七+ 1 一z 七) = g ( x 七+ ，7 奄s 七) t 8 k ( 2 1 7 ) 1 ：1 = 1 ( 2 1 0 ) 式得 z i c + 辄s 七= x k + 吼( z 知+ 1 一。知) 静， 其中掰表示厂的闭凸包，吼定义为 入七 = 0 ，使得 g k l i ，v k 0 ， d k l i m ，v k 0 证明：f i 了d k 的定义和( 2 3 ) 、( 2 4 ) 、( 2 1 0 ) 、( 2 1 8 ) 可得 酬i l g k l l + 2 必笋 彳+ 1 2 ( 2 1 8 ) ( 2 1 9 ) 河南大学硕士学位论文 引理( 2 3 1 ) 表明当k 一。o 时a k d k 一0 ，存在一常数，y ( 0 ，1 ) 和一整数，使得对于所 有的k k o 有以下不等式成立： 裂尝吣。i l d k 一。雌7 百孺q 知一1 1 l i s7 因此，对任意k k o l 了+ 圳如一1 峪7 ( 1 + 7 十7 2 十+ 矿一幻一1 ) 4 - 7 k - k 。l j d k o l l 击+ l l d k 。i l ， 令m = m a x l l d l l l ，i i d 2 l l ，i l d k o l l ，吉+ i l d k 。i i ，一z 。到ii 以l f m 证毕 利用以上引理，给出定理以及证明 定理2 3 1 在以中，步长q 知由弱a 帆力d 型线搜索偿j 砂得到假设2 2 1 2 2 2 成 立，有 l i mi n fi i g kl l = 0 ( 2 2 0 ) 尤 o o 证明：假设结论不成立，则存在一个正常数使得 | f 鲰l ，k 0 ( 2 2 1 ) 如果l 蛐i n f q j c 0 ，由( 2 1 0 ) 和( 2 1 2 ) 知l 归i i l f l l = 0 ，与( 2 1 2 ) 矛盾假设岫i n f o l k = 尤啼o 。拧，c 斗o 。 0 ，存在一个无限集合k 使得 ，l i m a 南= 0 ， ( 2 2 2 ) k 。+ o 。 a 南由( 2 1 1 ) 得出，存在一个充分大的指枋诱使得七石，k i 存在p 一1 a k 不满足( 2 1 1 ) ， 即 ，( 。七4 - p - ：o , d k ) f ( x k ) 一p - 2 a l l a k d k1 1 2 ( 2 2 3 ) 由中值定理、引理2 3 1 和式( 2 3 ) 、( 2 1 0 ) ，可知，存在r k ( 0 ，1 ) ，使得 f ( x k 十p - z a k d k ) 一f ( x k ) = p - ：a k g ( x 七+ 班p 一1 q 膏d k ) t d k = p - ：a g 奄- r d k + p 一1 0 f ( 9 ( z 磨4 - 叼p 一1 a k d k ) 一夕七) t d k p - ：a k 夕七t d k + l p 2 a 20 比f 1 2 ， 1 3 河南大学硕士学位论文 代入不等式( 2 2 3 ) ，得到所有的七仡， i 旧七i | 2 p - 1 ( l + 6 ) 口南l i 毗l f 2 由_ 【如) 有界及啦i n f q k = 0 可得l 啦i n fl = 0 ，与( 2 。2 1 ) 矛盾，所以结论成立证毕 2 4 数值试验 本节，对给出的n p r p 算法，从数值计算的角度，检验其数值效果，并与标准p r p 方 法进行数值比较所有的算法都采用f o r t r a n 编程，并在c p u 处理器为1 6 g h z ，r a m 内 存为5 1 2 m 的电脑上实现，对7 3 个大规模无约束优化问题进行测试，对于每个问题，改 变其维数，测试维数1 0 0 0 ，2 0 0 0 ，1 0 0 0 0 部分测试问题是从c u t e 2 7 函数库里提取 的，其f o r t r a n 表达式可以见n a n d r e i 的主页采用下面的终止准则 l i g ( z k ) l i 1 0 ，( 2 2 4 ) 为了评估算法的性能，我们在同样的问题上还对常规的p r p 方法进行了试验，算法和 程序可以从j n o c e d a l s 的主页上下载，网址是h t t p ：w v w e c e n o r t h w e s t e r n e d u - n o c e d a l l s o f t w a r e h t m l 在运行上述程序的时候，所有的参数值都是默认的，并使 用终止准贝j j ( 2 2 4 ) ，此外，若算法求解问题时函数值计算次数超过2 0 0 0 ，则程序将被迫 终止 我 f 用d o l a n 和m o r d 2 s 提供的方式比较各种算法的性能，具体如下：假设使用 种算法同时求解唧个测试问题，对测试问鼢和算法s ，令如，。为算法s 求解问题p 所 用的时间，定义 亡d 8 坛s2 盂丽荔丽 即求解问题s 各种算法的效率，其中s 为算法集合，显然，。 1 对所有的s 和p ，取 参数7 m 仲，。，若算法s 不能成功求解问题p ，则直接取饰，。= r m 为了估计算法s 对 所有测试问题的效率，令 1 p s ( 7 ) 。恚防p ：伽7 1 ， 其中 】表示集合中元素的个数，p 表示测试问题集合p 8 ( 丁) 是饰一的分布函数且 有p 。( 7 ) 1 可见，几( 丁) 的值越大，则算法的数值效果越好下面两个图表是算 1 4 河南大学硕士学位论文 法n p r p 和p r p 分别基于迭代次数、函数值计算次数s s c e u 运_ 算时间的分布函数p ( 丁) 曲 线 数值试验表明，算法n p i ：l p 和p r p f i 邑成功算出所有的测试问题，从下面两个图表 我们清楚的看到，算法n p r p 的曲线总是在上面，这表明算法n p r p 是这两种方法中 最好方法，它需要更少的迭代次数、更少的函数值计算次数由图我们也可以看出， 算法n p r p 要比算法p r p 节省计算时间 1 5 河南大学硕士学位论文 图2 1 基于迭代次数的比较 1 6 河南大学硕士学位论文 图2 2 基于函数值计算次数的比较 1 7 第三章求解凸约束的单调非线性方程组的共轭梯度法 3 1引言 考虑下面的约束非线性方程组问题：定义向量z 瞅使得， f ( x ) = 0 ，z q ， 其中qc 舯是非空闭凸集，f ：舻_ 黔连续单调，即 ( 3 1 ) ( f ( x ) 一f ( 秒) ，z y ) 0 vi t , ，y r n ( 3 2 ) 本节，我们提出一种求解凸问题( 3 1 ) 共轭梯度算法该方法可以存储量小、迭代简 单 3 2 算法设计 令效益函数 p ( z ) = 1 1 1 f ( z ) 忾 则问题( 3 1 ) 等价如下无约束最优化问题 蛐 p ( z ) $ r n ) ，( 3 3 ) 其中p ：r n _ r 是连续可微函数本章所提共轭梯度法的迭代公式是 x k + l2x k + 口忌反， 其中步长q 奄由线搜索得出，搜索f j 向d 七由下式决定 呶= 二竺+ 凤毗一。一幺玩一。：蓁：三三： 其中矗= 矗譬泽，和菇一1 = 班一1 + m 越 a 七一1 ，o 8 七一1 且觑定义为 凤= 缛， ( 3 4 ) ( 3 5 ) ( 3 6 ) 河南大学硕士学位论文 与第二章所定义的a 南一1 不同，设 址，= 坠挚 ( 3 7 ) 可知也总满足 ( 风，d k ) = 一i | 最忾( 3 8 ) 为了引入我们的算法，我们先介绍下投影算子的定义：从映射q 是舯上的一个 非空闭凸子集： h ：= 盯g r a 分i n n 怕一z l l ，vx 舻， 其中i i 表示2 范数，算子的一个重要的性质是不扩张性，即 l i p q x 一p q 可川i i z y l l ，vz ，y 妒 算法3 2 1 步0 给定初始点z o q 和常数p ( 0 ，1 ) ，仃( 0 ，1 ) ，卢 0 ，令k ：= 0 步1 如果最= 0 ，算法终止，如由p 纠得到 步2 确定步长札= m a x p p i ：i = 0 ，1 ，) 满足 ( f ( x k + t 七d k ) ，d k ) 冬- - o t k l l d k l l 2 ， ( 3 9 ) 令魂：= x k + t k d k 步3 计算 x k + l = 【z 矗一a k f ( z k ) ， 其中 a 七= 耸播 步4 令：= 毙+ 1 ，转步i 注记3 2 2 孟是p j j 的解，使得f ( 2 ) = 0 ，并且互q 由f 是单调的，我们得到 伊( 钆) ，牙一z k ) 0 ， 假设给定某个搜索方向也，通过沿搜索方向毗实施某种线性搜索，产生点张= z 七- 4 - q 七d k ，若 ( f ( z k ) ，x k z k ) 0 ， 河南大学硕士学位论文 这意味着超平面 a 知= z r n l 0 使得 f ( x ) 一f ( y ) i i l i i x 一矽l l ，v z ，y q ( 3 1 0 ) 假设3 3 2 如果f 单调且三枷如t 比连续，则有 ( f ( z ) 一f ( 暑) ，z y ) 0vz ，y q ( 3 1 1 ) 假设3 3 31 ：1 墨4 ( s j ) 的解集s 非空 引理3 3 1 对所有忌 0 ，存在一个非负数满足p 圳 证明：首先，如果在第k 次迭代该算法终止，即风= 0 ，因此z 知是一个解下面假 设对于所有的七，凡0 ，因此由( 3 8 ) 矢g d k 0 假设算法产生有界无限序列 z 知 我 们现在证明线搜索( 3 9 ) 具有有限终止性，若t 如p ，贝u t k = p - i t k 不满足( 3 9 ) ，即 一怛( ) ，d k ) 0 ，使得 l i f ( x k ) l l m ( 3 1 4 ) 证明：对于任一牙s ，由不放大的投影算子，我们有 | i z 七+ 1 一牙1 1 2 = i i p q x k c t k f ( z k ) 】一面i | 2 i i z 七一a k f ( z k ) 一孟| | 2 = i l z j c 一孟1 1 2 2 a k i f ( z k ) ，x k 一牙) + a 2 1 l f ( z k ) 1 1 2 i | z 七一牙i f 2 2 a k ( f ( z k ) ，x k 一魂) + q 2 l l f ( z k ) 1 1 2 = i i x 七- z l l 2 一芦 i 慨一刮2 ，( 3 1 5 ) 所以对于所有的k 都有 f ( x k ) l i = l i f ( z k ) 一f ( 牙) i | l l l x 七一圣l i l l l x o 一牙m 河南大学硕士学位论文 令m = l i i x o 一别，即得( 3 1 4 ) 证毕 根据上面的引理，我们现在分析算法( 3 2 1 ) 的全局收敛性： 定理3 3 4 假设条t c 3 s s 一3 3 减立，序列 z 七) 和 魂) 由算法舅幺j 生成则有 l 徊i n fi l 凡0 = 0 ( 3 1 6 ) r - - - * 证明：假如( 3 1 6 ) 不成立，存在e 0 使得 l i 凡l i e vk 0 ( 3 1 7 ) 由( 3 8 ) 可知| | 最l i i i d y l l ，所以 i i d k l i e vk 0 ( 3 1 8 ) 由沁的定义得 址堕辞迅粼忪洲乩( 3 1 9 )饥2 可丽广一s 丽矿恻i 2l j 通过定义玩和假设2 2 2 ，可得 | i 玩一1 l f = i f 耖k + m a x ；l k ，o s k l i l 秒- 4 - l s k l f i l y k l f + l l t s 砖l l 2 l i i s k l l 类似引理2 3 3 的证明可知存在正标量c ，使得 i i d k l i d 所以对( 3 1 2 ) ，和不等式( 3 1 7 ) ，( 3 1 8 ) 所有足够大的七满足 枷凫i i m i n 掘而p 丽i i f k l l 2 川, 毗 n l i n i n e ，南) ， 这与( 3 1 3 ) 矛盾，所以结论成立证毕 ( 3 2 0 ) 第四章结论 本文主要研究求解无约束最优化问题，以及求解凸约束的非线性单调方程组的 共轭梯度算法，提出了改进的算法并对算法进行了收敛性分析首先在修正p r p 共 轭梯度法的基础上，提出求解大规模无约束优化问题的一种新方法，此方法的特殊 优势在于搜索方向总保持下降，并证