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

摘要 最优化方法是- f - j 应用性很强的年轻学科，它主要运用数学方法研究各种系 统的优化途径及方案，从数学的角度表达了人们处理实际问题时所遵循的一种理 念。无约束优化作为最优化的一个主要分支，现已成为众多学者们研究的焦点。 在实际问题的求解过程中，对于无约束优化算法的研究具有重要的理论意义。 全文共分为三章： 第一章为绪论部分，主要介绍了最优化的概况，求解无约束优化问题所涉及 的基本概念，无约束优化问题中常用的线搜索规则和几种主要的下降算法，以及 本文的内容安排。 第二章基于最速下降法、两点步长梯度法及两者杂交的交叉步长梯度法，提 出一种新的交叉步长梯度法，在理论上证明了算法的收敛性，通过数值实验说明 了算法的可行性。 第三章以共轭梯度法为基础进行研究，提出一种新的下降算法，证明了在 w o l f e 不精确线搜索下无需给定下降条件算法亦是全局收敛的。并将此算法与其它 杂交共轭梯度法进行比较，以好的数值结果说明了算法的有效性。 关键词：无约束优化最速下降法两点步长梯度法共轭梯度法全局收敛性 a b s t r a c t t h eo p t i i l l i z e dm e t h o di s ay o u n gd i s c i p l i n ew i t hv e r ys t r o n gu t i l i t y i tm a i n l y s t u m e st h eo p t i m i z e dw a ya n dp l a no fe a c hs y s t e mb ym a t h e m a t i c a lm e t h o d ，e x p r e s s e s m ei d e am a ta c t u a lp r o b l e m sa r ep r o c e s s e df r o mt h em a t h e m a t i c a la n g l e u n c o n s t r a i n e d o 砌叽妇i o ni sa ni m p o r t a n tb r a n c hi no p t i m i z a t i o na n d h a sb e c o m et h ef o c u st h a tm a l l y s c h o l a r s 洲y i nt h ep r o c e s s o ft h ea c t u a lp r o b l e m ss o l u t i o n , u n e o n s t r a i n e d o p t i m i z a t i o nh a sa ni m p o r t a n tt h e o r ys i g n i f i c a n c et om a k e as t u d yo f t h et h e s i si sd i v i d e di n t ot h r e ec h a p t e r s ： c h a p t e r1 i st h ei n t r o d u c t i o n , w h i c h o p t i m i z a t i o n , t h eb a s i cc o n c e p t ，s o m el i n e m a i n l yc o n t a i n s t h eg e n e r a ls i t u a t i o no f s e a r c hm e t h o d s ，s e v e r a le x t e n s i v ed e s c e n t m e 1 0 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 ，a n dt h ea r t i c l ea r r a n g e m e n t i i lc h 蛳2 ，b a s e do ns t e e p e s td e s c e n tm e t h o d ，b bg r a d i e n tm e t h o da n dt h e i r h y b r i dm e t h o d ，an e wa l t e r n a t es t e p s i z e g r a d i e n tm e t h o d i sp r o p o s e d ，a n di t s c o n v e r g e n c ei sp r o v e dt h e o r e t i c a l l y n u m e r i c a le x p e r i m e n ts h o w st h a t t h em e t h o d1 s f e a s i b l e i nc h a p t e r3 ，i nl i g h to ft h ec h a r a c t e ro fc o n j u g a t eg r a d i e n tm e t h o d ，an e w d c s c c n t m e t l o di sp r o p o s e d t h ep r o o fo f t h em e t h o d sg l o b a lc o n v e r g e n c ei sg i v e nu n d e rw o l f e l i i 圮s e a r c h 、析t 1 1 0 u tt h ed e s c e n tp r o p e r t y n u m e r i c a le x p e r i m e n ts h o w s t h a tt h em e t h o d i se 伍c i e n t k e 啊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 s t e e p e s td e s c e n tm e t h o d b bg r a d i e n t m e t h o d c o n ju g a t eg r a d i e n tm e t h o d g l o b a lc o n v e r g e n c e 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：血 日期磁：堑 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位仍然为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：取 剔醛轹牡 日期竺2 ：竺 日期蚓，出f 第一章绪论 第一章绪论 本章主要介绍了最优化的应用背景和它的分支无约束最优化的概况，阐述了 无约束最优化中的基本概念、线搜索方法及其主要算法。最后列出了本文的章节 安排。 1 1 引言 运筹学作为一门最早形成的软科学，综合了多种学科，把科学的方法、技术 和工具应用到包括系统管理在内的各种问题中，从而为掌管系统的决策者们提供 了最佳的解决问题的方法。运筹学应用科学的方法研究与某一系统的最优管理相 关的问题，帮助决策人解决那些可以用定理方法和相关理论来处理的问题。因此， 运筹学是有重要应用价值的学科，特别在现代科学管理中更是处处可见。古语有 云“运筹帷幄，决胜千里 ，运筹学的重要性不言则明。运筹学的研究范围囊括一 切可以定量化的管理系统。 最优化理论【1 1 是应用性很强的学科之一。它主要研究数学上所定义问题的最优 解，即对于给出的实际问题，从众多方案中择优。最优化方法又称为数学规划， 它是运筹学的一个重要分支，也是应用数学中联系实际最为密切的部分，涉及的 领域包括自然科学、社会科学、工程设计、工业生产和现代管理等等。最优化的 思想早在古代已产生，但作为一门独立的学科还是在1 9 4 7 年一般线性规划问题的 单纯形法提出之后。科技的飞速发展和计算机的广泛应用进一步推动了最优化理 论与方法的研究。如今最优化理论与方法在经济规划、政府决策、交通运输和军 事国防等方面得到了广泛的应用，成为一门十分活跃的学科。 最优化问题的一般形式为： 卿厂( x ) ( 1 - 1 ) 其中x z 是决策变量，f ( x ) 为目标函数，zcr “为约束集或可行域。 约束最优化问题的形式为： m i n f ( x ) s t c ( z ) = 0 ， i e ， q ( x ) 0 ， i i ， 2 求解无约束优化问题的算法研究 这里e 和，分别是等式约束和不等式约束的指标集。c 。( x ) 是约束函数。当目标函 数和约束函数均为线性函数时，问题称为线性规划；当目标函数和约束函数中至 少有一个是变量z 的非线性函数时，问题称为非线性规划。 如果约束集z = r ”，则最优化问题( 1 1 ) 称为无约束最优化问题： m 西f ( x ) r n- 亡 ， 本文主要针对无约束优化问题进行研究。 1 2 基本概念介绍 无约束优化计算方法是数值计算领域中十分活跃的研究课题。快速地求解无 约束优化问题已经成为当今的焦点，除了其自身的重要性外，还由于目前求解约 束优化问题的基本思想之一就是把约束问题变换为一系列无约束子问题进行求 解。因此，无约束优化算法的求解效率将直接影响到约束问题的求解，尤其是在 大规模优化问题中。所以，对无约束优化算法的研究具有重要的理论意义和实际 价值。 在无约束优化中，目标函数的最小化取决于某些不受约束制约的变量。其一 般形式为： m i n f ( x ) ( 1 - 2 ) 其中x r ”为n 维实变量，刀1 ，f ：r ”一r 是光滑函数。 求解无约束优化问题时将会涉及到以下概念【2 】【3 1 。 ( 1 ) 驻点、鞍点：若f ( x ) 在点x 处可微，并且可( x ) = 0 ，则x 称为f ( x ) 的 一个驻点( 或者平稳点) 。既不是极小点，也不是极大点的驻点称为鞍点。 ( 2 ) 全局最优解：若x z ，v x r ”均有f ( x ) f ( x ) ，则称x 为问题( 1 1 ) 的 全局最优解。 ( 3 ) 局部最优解：若工z 且存在x 的某个邻域m ( x ) = x i i x - x 8 0 为某个正数，使得zc r ”，v x z n 以( x ) 均有f ( x ) f ( x ) ，则称x 为 问题( 1 1 ) 的一个局部最优解。 当目标函数f ( x ) 为凸函数时，我们认为全局最优解即是局部最优解，然而， 通常寻求全局最优解并不容易。因此，在非线性优化中我们认为局部最优解即为 所求。 ( 4 ) 非极小点的充分条件：设f ( x ) 在点x 处可微，若存在方向d r ” 0 ) ， 使得耵( 工+ ) r d 0 ，使得v 五( 0 ，万) ，有f ( x + 2 d ) f ( x ) 。此时， 我们称d 为函数f ( x ) 在x 的一个下降方向。 第一章绪论 3 ( 5 ) 无约束优化一阶必要条件：若x 为问题( 1 2 ) 的一个局部最优解，f ( x ) 在x 的某个开邻域连续可微，则耵( x ) = 0 。 ( 6 ) 无约束优化二阶必要条件：若工为问题( 1 - 2 ) 的一个局部最优解，v 2 f ( x ) 在 f 的某个开邻域连续可微，则耵( x ) = 0 ，v 2 f ( x ) 是半正定的。 ( 7 ) 无约束优化二阶充分条件：假设v 2 f ( x ) 在工的某个开邻域连续可微， w ( x ) = o 且v 2 f ( x ) 半正定，则x 为问题( 1 - 2 ) 的局部极小解，特别的，对于邻域 内的任意一点z 工，若v 2 f ( x ) 是正定矩阵，则x 也是一个严格局部极小解。 ( 8 ) 无约束优化的充要条件：假设函数f ：r ”j r 为可微的凸函数，则x 是问 题( 1 2 ) 的全局最小点，当且仅当w ( x ) = 0 。 ( 9 ) 下降条件： 线搜索方法的主要任务是在每次迭代过程中选择搜索方向并确定沿搜索方向 的步长。搜索方向一般满足 反反 0 是一个常数。迸一步，我们需要畋涌足三角性质： c 。s ( 嘞，畋) = 一畋( j k | 1 i | 以8 ) ( 1 - 5 ) 其中( o ，1 】为一常数，( 一，盔) 表示向量一与盔之间的夹角。 ( 1 0 ) 收敛速率： q 一因子：假设 耳 cr ”是任意一个收敛的序列，记其极限为x 。，误差 & = i i x - x 。任意常数p 【1 ，佃) ，定义 鳞瓴) = 0 ， 1 i ms u p 血， ” & 。 + ， 除有限个矽k = x 除有限个k # b x x ( 1 6 ) 其他情形 则称g ( t 为序列瓴) 的比值收敛因子，简称q 一因子。 假设c ( i ，石) 表示由迭代过程f 生成，以x 为极限的所有序列的集合，令 鳞( f ，工) = s u p g 矗) i 耳) c ( f ，z ) ) ， 跏【l ，佃) 则g ( 砸 ，x ) 称为迭代过程i 在x 点的q 一因子。 4 求解无约束优化问题的算法研究 若q ( f ，石) = 0 ，则称迭代过程f 在工点是q 一超线性收敛的；若 0 q ( f ，z ) 1 则称& 瓴) 为序列瓴 的根式收敛因子，简称r - 因子。 假设c ( f ，x ) 表示由迭代过程f 生成，以x 为极限的所有序列的集合，令 r p ( f ，x ) = s u p 彤 吒) i ) c ( f ，x ) ) ， 即 1 ，佃) ( 1 - 9 ) 则r p ( f ，x ) 称为迭代过程 在x 的r _ 因子。 r - 阶：设r p ( f ，工) 是迭代过程f 在x 的r 一因子，定义 幺e 耻 ；p 叩，：麓专嚣篙鬟 m 。， 称昧( f ，工) 为迭代过程f 在x 的根式收敛阶，简称为l 卜阶。 若存在非负标量序列 咋) 满足 恢l l u 再采用某 ( 1 - 1 5 ) 即要求下一个迭代点是方向以上的精确极小点。由于使用精确线搜索的计算量非 常大，特别是当迭代点远离问题的解时。另外，在实际计算中很多优化方法收敛 速度不依赖于精确搜索过程，因为精确一维搜索需要付出较高的代价，而对加速 收敛作用不大。因此实际中往往使用非精确线搜索。 求解无约束优化问题的算法研究 ( 2 ) g o l d s t e i n 线搜索：选择固定的标量夕0 ，) 及吒满足 f ( x k + 畋砍) f ( x k ) + ( 1 - p ) c q g ；d k ( 1 - 1 6 ) ( 1 1 7 ) 注意到：若函数厂( x ) 有下界，则存在步长的一个区间满足上述不等式组，并存 在简易的算法通过有限次操作便可找到这样的步长。 ( 3 ) a n n i j 0 线躲给定标量& ，“ 0 ，满足& 2 ：) ， ( o ，1 ) ，p ( o ，) 。令为序列也，触，2 & ， 中使下式成立的最大非负整 数 f ( x k ) 一f ( x k + 畋) 一胆或喀 ( 1 1 8 ) 其中0 p 1 是常数。 ( 4 ) w o l f e p o w e l l 线搜索：要求满足 f ( x k + 畋) - f ( x t ) + p c q , g r 4 g ( x j , + 饯k d jd k 2 a 最d k ( 1 - 1 9 ) ( 1 2 0 ) 其中0 p 盯 l 是两个常数。 ( 5 ) 强w o l f e 线搜索：若将( 1 - 2 0 ) 改写成如下形式： l g ( x 。, + o q d k ) r 喀卜一仃以( 1 - 2 1 ) 满i f ：( 1 1 9 ) ，( 1 - 2 1 ) 称为强w o l f e 线搜索。 ( 6 ) g r i p p o 线搜索：固定0 c l 1 0 ( 1 2 7 ) 时，由( 1 2 6 ) 式得到的以+ ，才能保证正定性；其次，即使( 1 2 7 ) 成立，由于误差的 影响，可能产生数值计算上的困难。 秩2 对称算法是另一种常用的拟牛顿法，一般秩2 对称算法的修正矩阵公式 可写成： c = a k u u r + 展w r ( 1 - 2 8 ) 其中“，v 为待定的疗维向量，a k ，展为待定常数。 著名的拟牛顿法要算b r o y d e n 族拟牛顿法，其中巩的校正迭代公式为： 叫一鬻+ 袅坝锄h m 2 9 ， u 。一盟y k r h k y 。+ 石s k 其中0 【0 ，1 】。 当0 = 0 时即为著名的d f p 公式： = 皿一等癸+ 袅 m 3 。， y ihk y ks ky k 第一章绪论 d f p 法是构造h e s s i a n 逆矩阵最早的，最巧妙的一种格式，也称为变尺度法，它是 由d a v i d o n 提出，后来由f l e t c h e r 和p o w e l l 作了改进。如果梯度g k 0 ，k = 1 ，2 ，刀， 那么d f p 法构造的h e s s i a n 逆矩阵具有正定性。并且，d f p 方法也具有二次终止 性【2 0 1 。 当口= l 时即为著名的b f g s 公式： 瓯啦一鬻+ 岳也饵从 m 3 。， 吒一惫+ 磊s k 这个重要的公式是由b r o y d e n ，f l e t c h e r ，g o l d f a r b 和s h a n n o 于1 9 7 0 年提出的。它 可以像d f p 公式( 1 3 0 ) 一样的使用。数值计算表明b f g s 算法比较好，目前得到广 泛的应用。 b f g s 法和d f p 法的区别在于b f g s 法构造近似h e s s i a n 矩阵，需要计算逆矩 阵，d f p 法直接构造h e s s i a n 矩阵的逆，因此不需要计算逆矩阵。 1 5 本文内容安排 优化问题是描述自然界，分析人们生活的一个重要工具。自然界中优化的应 用普遍存在，例如：物理系统常常趋于最小能量状态演化；江河中的流水是沿着 势能的最速下降方向流动：在封闭的化学系统中，分子之间相互作用直到它们的 电子总体势能达到最小；光射线传播所经过的路径使得它所需要的传播时间最短 等等。人们生活中优化的作用也比比皆是，例如：怎样设计比较好的证券组合或 投资项目组合，以便在可接受的风险限度内获得尽可能大的投资回报；如何选择 恰当的参数，使得工业设计方案既满足实际要求，又能够降低工程的造价；如何 设计汽车或者飞机的最佳外形，使其既能保证运动的稳定性，又能减少其运动的 阻力，还能满足隐身性的要求：如何控制一个化学过程，既优化其性能，又保证 其满足鲁棒性要求等等。随着科技的发展，优化问题无疑成为人们关注的焦点。 优化问题分为两大类：约束优化和无约束优化。由于约束优化问题可经过转换变 为无约束优化问题。因而，近年来无约束优化问题的研究更加受到众多学者的青 睐。 最速下降法、牛顿法、共轭梯度法、拟牛顿法是无约束优化中几种主要的算 法，在无约束优化中应用相当广泛。本文就是针对其中的算法深入研究。 本论文的结构和主要研究内容概括如下： 第一章为绪论部分。概述了最优化问题的背景、研究现状及其重要性，简述 求解无约束优化问题的算法研究 了本文所用到的一些概念，概括的介绍了几种常用的求解无约束问题的算法，并 陈述了论文的研究内容。 第二章简要介绍了最速下降法、两点步长梯度法及交叉步长梯度法，在此基 础上，针对各个算法的优劣，提出一种求解无约束优化问题的新的步长梯度算法， 并对算法的收敛性进行分析，最后，对此算法进行了数值实验，得到较好的数值 结果。 第三章介绍了几种著名的共轭梯度法，以及由共轭梯度法拓展而来的杂交算 法，结合前人的研究，基于共轭梯度法的性质，提出一种新的下降算法，并给出 了该算法的收敛性证明，最后，通过仿真实验说明了算法的有效性。 第二章一种新的交叉步长梯度算法 1 3 第二章一种新的交叉步长梯度算法 本章在最速下降法和b b 梯度法的基础上，综合两者优势，提出了一种求解无 约束优化问题的新的交叉步长梯度算法，给出了算法的收敛性证明。数值实验表 明算法十分有效。 2 1 引言 求解线性系统 等价于求解最小化问题 a x = b ， a r ，b r ” ( 2 _ 1 ) m i n q ( 加血珂x ，( 2 - 2 ) 其中么是实对称正定矩阵。这是因为f l e t c h e r & r e e v e s 2 1 1 将线性共轭梯度法应用 到解无约束优化问题 m ，i n f ( x ) ( 2 3 ) 工“” 其中f r 刀专r 是连续可微的函数。最速下降法是求解问题( 2 3 ) 的一类方法，其 迭代形式为： x k + l = x k 一吒既，七= 1 ，2 ， ( 2 - 4 ) 搜索方向破取为负梯度方向，为步长，由以下形式给出： 弘怒 ( 2 - 5 ) 其中= g ( x k ) = 可( t ) 。 步长( 2 5 ) 线性最小化函数f ( x ) ，然而，在实际的应用中，最速下降法的表现 并不是很好。这种算法的最大弊端是它容易产生锯齿现象。a k a i k e t l 3 i 己证明最速 下降法最终将趋于两个不同的方向： 1 4 求解无约束优化问题的算法研究 l i m 墨2 1：孑 。i | 9 2 女| i l i m 墨坐! ：0 + 。i | 9 2 t + li i ( 2 6 ) ( 2 7 ) b a r z i l a i & b o r w e i n t l 4 1 提出另一种步长选择两点步长梯度法。其基本思想 就是利用当前迭代点以及前一点的信息来确定步长因子。迭代公式鼍+ 。= x k a k g k 可以看成是 x k + l = x k q g k ( 2 - 8 ) 其中q = a f t 是一个矩阵。为了使矩阵q 具有拟牛顿性质，计算吼满足 m i n i l & 一i 一砬儿一l ( 2 - 9 ) 或者 其中， 可分别求得 及 m i n 研1 一l 一儿一l ( 2 - 1 0 ) s k 一12x k x k 一1 y k 一12g k g k 一1 伍 ：每丛 以一l 儿一l 妒：车盟 一i 儿一l 由s k l = 一一l g k l 和儿一l = a s k l 知，( 2 一1 1 ) 式等价为 妒= 瓦g k r _ ia 酝g k _ l ( 2 - 1 2 ) 式等价为 ( 2 1 1 ) ( 2 - 1 2 ) ( 2 - 1 3 ) ( 2 - 1 4 ) 本文称( 2 _ 4 ) ，( 2 - 1 1 ) 或( 2 4 ) ，( 2 - 1 2 ) 为b a r z i l a i & b o r w e i n ( b b ) 梯度法。 b b 梯度法与最速下降法相比，在理论方面和数值结果上都占优势。我们知道 最速下降法的收敛性是线性的，并且易受病态条件的影响 1 3 l1 2 3 1 。而b b 梯度法对 第二章一种新的交叉步长梯度算法 于二维严格凸二次函数是r 线性收敛的，而且收敛速率相对较快【1 4 】。对于任意维 凸函数b b 梯度法是r 线性收敛的1 1 6 1 。对于非二次函数，在求解大规模无约束优 化问题上，b b 梯度法所得的结果可与一些著名的共轭梯度法相提并论。b b 梯度 法的运行时间短【2 4 1 ，但是它不能保证每次迭代过程中函数值呈下降趋势。 最速下降法在相邻两次迭代中产生锯齿形状，通过将其中一个步长替换为b b 步长，即得到所谓的交叉步长( a s ) 梯度法【2 5 j 。交叉步长梯度法的步长有如下形式： f 铲，f o ，o d dk 酽= ( 2 - 1 5 ) i 妒，f o ，e 1 ，e g lk 由于口芦= 诺= 曙，因此该算法可以看作是循环最速下降法的特例【2 6 1 。交叉步 长梯度法不仅能避免锯齿现象的发生，而且具有良好的收敛性。d a i 在2 0 0 3 年对 交叉步长梯度法的收敛性做了充分的证明 2 s l 。文中指出，在半正定系统下，对于 二维例子，任意选取初始点，交叉步长梯度法都是两步q 一超线性收敛的，而对于 任意维的例子，交叉步长梯度法是r 一线性收敛的。 2 2 算法及其收敛性质 针对两点步长梯度法和交叉步长梯度法的优缺点， 上，将它们的步长进行凸组合： = o a ? b + ( 1 一秒) 口芦 本节在这两种算法的基础 ( 2 - 1 6 ) 其中0 【0 ，1 】，提出一种新的杂交算法。所得到的步长( 2 - 1 6 ) 可视为交叉步长梯度 法的一个特例。 算法的具体步骤如下给出。 算法2 1 ： s t e p l 给定初始点五r ”，0 f l ，k ：= l ： s t e p 2 计算矾= - g i ；如果| ig kf i 0 ，如果g ( 七一j ，) g ，( 反写) 2 - g 占对_ e o ，m i n k ，聊) - 。1 】 成立，则町1 ( 2 3 ) 2 1 + i o 性质2 1 中( a ) 说明步长的倒数是有界的，由此可以得到颤的第一个特征元q - 线性收敛到零。( b ) 要求对于任意整数，步长的倒数足够大使得若的前，个特征 元充分小，则它的第1 + 1 个特征元将减小。 结合性质2 1 及文献 1 6 1 5 b 的结果，我们给出r 一线性收敛定理。 定理2 1 考虑线性系统( 2 1 ) ，其中a 具有形式( 2 1 7 ) 且l = 丑五以。式 ( 2 - 4 ) 吼具有性质2 1 。则或者对于有限的七有g k = 0 ，或者序列 i j 敝吣r 一线性 收敛到0 。 证明：由式( 2 - 4 ) 和( 2 1 7 ) 知 占g 川o ) = ( 卜名) 酲o ( 2 - 1 9 ) 定义7 7 l = m a x ( 1 一( c 1 ) ) 2 ，1 4 ( o ，1 ) 及7 7 2 = m a x ( 1 - ( c 。五) ) 2 ，2 ) 。 由式( 2 1 9 ) 和g ( k ，1 ) 的定义易得，对任意的k i ， g ( k + 1 ，i ) r l l g ( k ，1 ) ( g ：3 ) 2 仉( g ：o ) 2 ， i = l ，2 ，甩 + l1 1 2 ，7 2i i 1 1 2 ( 2 2 0 ) ( 2 - 2 1 ) ( 2 2 2 ) 接下来的证明分为三部分。 ( a ) 首先证明对于任意整数l ， ( 2 3 ) 2 1 “ ( 2 2 7 ) ( 反絮。) 2 7 7 l ( 喇) 2 ( 2 2 s ) 其中 + m ，+ 聊+ f 】。 由( 2 2 1 ) ，( 2 - 2 8 ) 和a ，的定义得 ( g 踹a + 1 ) 2s 铲+ 1 ( 贼+ 。) 2 s 铲“穆棚( 彰“) 2 c 2 岛i | f f 2 ( 2 2 9 ) 因此，( 2 - 2 4 ) 式成立。 ( b ) 定义+ l = 啊+ m + ，+ 1 及6 t + l = ( 1 + c 2 秽) q ，接下来证明如果( 2 2 3 ) 式成 立，则 g ( 七+ ，+ 1 ) q + li i 1 1 2 ，w 竹+ l ( 2 3 0 ) 及 事实上，由( a ) 知，存在无穷多个整数五和五满足五 石五使得 ( 喇) 2 - g 8 1 | ig 。1 1 2 ，j e j 。+ l ，五- 1 ( 2 3 2 ) 1 8 求解无约束优化问题的算法研究 则由( 2 2 1 ) 和( 2 - 3 1 ) 知 ( 删) 2 彬( 蝴) 2 c 2 彬q0 颤| 1 2 其中歹u + l ， + 聊】。 如果左 五+ 历，则由性质2 1 ，( 2 1 9 ) ，( 2 - 2 3 ) 和( 2 - 3 2 ) 知 昕1 ( 2 3 ) 乃+ 。 及 ( 或絮。) 2 ( 或z ) 2 ，【 + 聊，五一1 】 由( 2 - 2 2 ) ，( 2 - 31 ) ，( 2 - 3 4 ) 知 ( 喇) 2 磋( 或臻。) 2 c 2 彬句l i 1 1 2 ( 2 - 3 3 ) ( 2 3 4 ) ( 2 - 3 5 ) ( 2 3 6 ) 其中，u + 朋+ 1 ，五】。 再由 和五的任意性及( 2 3 3 ) ，( 2 3 6 ) 知对任意的五有 ( 喇) 2 c 2 彬圳1 1 2 ( 2 3 7 ) 因为矗确+ l 由( 2 - 2 3 ) ，( 2 - 3 7 ) ) 3 2 g ( k ，) 的定义得( 2 - 3 0 ) 式成立。 ( c ) 对任意1 ，刀，定义 岛= 丢( 1 + c 2 啪弘帕 ( 2 - 3 8 ) 令= 1 0 9 c t l o g r 1 ，m l + l = m t + 所+ ，+ l ，其中，= l ，2 ，疗一1 ，= m 。 下面由归纳法证明对所有的l ，刀， g ( k + j ，) q | f nw 坼 ( 2 3 9 ) 事实上，由( 2 2 0 ) 和m a 的定义知，当，= l 时式( 2 3 9 ) 显然成立。假设当1 ， - - l 时，( 2 3 9 ) 式成立。由( b ) 的证明过程可知( 2 3 9 ) 式在n + l 时也成立。故由归纳法可 得，当1 ，刀时，( 2 - 3 9 ) 式成立。 注意到毛= 且g ( 七，1 ) 爿i g ki | 2 ，由( 2 - 3 9 ) 有 t l i 反删1 1 2 钏1 1 2 ( 2 - 4 0 ) 第二章一种新的交叉步长梯度算法 1 9 因为= m 仅依赖于矗，c l 和c 2 ，1 圭1 ( 2 2 2 ) 和( 2 - 4 0 ) 得到序列 i l g il f ) 是i 卜线 性收敛到0 的。 2 3 数值实验结果 用于检验本章算法的测试函数为最小化函数： m ) = f 血搿x 本节列出5 个不同维数的函数进行仿真，通过将最速下降法、两点步长梯度 法、交叉步长梯度法所得数据结果与本章提出的算法所得数据结果进行比较，进 而分析所提出算法的优劣性。 i ；7 题l ： a = m a g ( o 2 ，2 ) ，b = ( 0 ，0 ) ， 初始点= ( 1 0 0 0 ，1 0 0 0 ) r 。 问题2 ： a = d i a g ( 2 0 ，1 0 ，2 ，1 ) ，b = e 4 ， 其中e 4 为元素全1 的4 维向量， 初始点x o = ( o ，0 ，0 ，o ) 7 。 问题3 ： a = d i a g ( 2 0 0 0 ，1 0 0 0 ，2 0 0 ，1 0 0 ，2 0 ，1 0 ，2 ，1 ) ，b = e 8 ， 其中e 8 为元素全1 的8 维向量， 初始点而= ( o ，0 ，0 ，0 ，0 ，0 ，0 ，o 厂。 问题4 ： i2 。i f i = j 彳= ( ) 一， = 一l ，f i = j + l ， l 0 ， o t h e r w i s e 吲城， 6 f = 扣( 熹) ， 初始点为x o = ( 0 ，0 ，0 ) 7 ， 求解无约束优化问题的算法研究 问题5 ： f 2 ，i f i = j 彳= ( ) 一， = 一l ， i f i = j + l ， 【0 ， o t h e r w i s e 吲铖， 岛= 扣( 并， 初始点为拧维全零向量， 其中刀= 1 0 0 0 。 算法的任何一个实验比较在一定程度上受编制此算法的计算机程序的影响， 为了避免这种影响，在编制程序时对各种算法采用了相同的终止条件。由于测试 问题均是连续可导的，根据无约束问题的最优性条件，梯度趋于零的快慢程度可 以反映迭代点趋于最优点的快慢。因此本章采用了函数梯度作为终止条件。根据 迭代次数的多少来评价四种算法的相对求解效率。 算法的程序和数值实验均在m a t l a b 7 0 环境中进行。算法的终止条件为 i i l l 1 2 时的情况。在相同线搜索条件下，g i l b e r t 和n o c e d a l 证明了当l 展i 胪时的全局收敛性。 3 2 算法的提出 为了达到既具有良好的收敛性又具有良好的数值实验结果的目标，许多学者 对杂交算法进行了l ；k 较深入的研究。t o u a t i a h m e d 和s t o e r y 3 0 j 提出了一种杂交共 轭梯度法，它要求当o 5 夕知卯且0 & + ，0 2 ( 2 ) 时取屏= 胪，否则取 孱= 矿，其中0 口 髟，并且证明了在强w o l f e 线搜索下算法的全局收敛 性。在相麟搜索条件下，h u s t o r e y l 3 1 1 绌了如i 卜吼取履= 胪， 否则取屏= 的杂交算法的收敛性证明。 1 9 9 9 年d a i 和y u a n 3 2 1 提出了d y 方法在w o l f e 线搜索下，无需给定下降条件 求解无约束优化问题的算法研究 即 ( 3 - 1 1 ) 算法具有全局收敛性。后来，这两位学者又对其相关算法进行系统的研究，文献 3 3 】 提出了与d y 方法相关的一类算法： 展( ( 仃o - + - 1 1 ) ) - ，1 】矽 ( 3 1 2 ) 【仃+ l j 并证明了展满足上述条件产生的迭代算法在标准w r o l f e 线搜索下的全局收敛性。 2 0 0 1 年，其二人又提出了一类三参数共轭梯度法簇【3 4 j ： 展= 鬲蓑陟塞蔫鬲p 其中五【o ，1 】，版 0 ，1 】，魄 0 ，1 一熊】。上式( 3 - 1 3 ) 可视为( 3 - 5 卜( 3 1 0 ) 这六种共 轭梯度法的各种凸组合形式。文献 3 5 】提出了求解无约束优化问题的p c 下降算法： 其中o 0 使得： 0 9 ( 力一g ( y ) l l mj j x yj i ，v x ，y n ( 3 - 1 8 ) 本文算法中步长哝由w | o l f e 准则得到，其中0 p 盯 1 ： f ( x k + 畋) 厂( ) + 鹏反d k ( 3 1 9 ) g ( x k + 吼畋) 7 以o r g ：反 ( 3 2 0 ) 算法3 1 s t e p l 取初始点五r ”，0 sf l ，西= - g l ，k ：= 1 。 s t e p 2 判断| | g k | i 占是否成立，若是，则停止；否则转到下一步。 s t e p 3由w o l f e 线搜索( 3 19 ) ，( 3 - 2 0 ) 求得。 s t e p 4 计算迭代点鼍+ l = x k + 畋。 s t e p 5由( 3 1 7 ) 式计算屈+ l ，并求以+ l = 一+ 1 + 展+ l 矾，令k _ k + l ，转s t e p 2 。 3 4 全局收敛性分析 引理3 1 ( 下降性条件) 设目标函数满足假设h ，考虑一般方法( 3 3 ) ，( 3 - 4 ) ，步 长因子由w 0 l f e 线搜索( 3 1 9 ) ，( 3 2 0 ) 求得，若颤0 ，则当愿取( 3 - 1 7 ) 1 对，对所 有的k l ，都有 吨 o ( 3 - 2 1 ) 证明：当力= 1 时，g j 碣= 2 0 ( 3 2 2 ) 2 8 求解无约束优化问题的算法研究 爵破= 一& 2 + 屏吨一。 = 一旷+ 鼓 吱 ( g 一c o g ) 当g k l 0 时，结合( 3 - 2 0 ) 式，假设及( 3 2 2 ) 式，有 当爵一1 0 时，同理 吨。一。4 ， 西吨一。 d d , - l i 酬2 + c o g ；, a 冀k 丽如一i 一反一l 吼1 o 吨= 一1 1 2 + 更 羲 ( g k c o g ) 一缈l i 2 ( g r ( 矾。一9 0 。矾。 d 畋一。) + g 。1 1 2 ( 吐。反一，) 矾。一。4 。) l l 2 ( 以一。) 一缈g ；。噍。 ( 吨_ l _ 吐。反。) ，( 彻一盯一1 ) i ig k1 1 2 ( 一或一l 以一i ) ( 国g ：反d 一一。反。) o 彻g ；，( 一吐。哝。) ( c o g r d k 1 - 吐1 吨1 ) + ( 3 2 3 ) ( 3 2 4 ) ( 3 - 2 5 ) f l j ( 3 2 4 ) ，( 3 - 2 5 ) 式知下降性条件成立。 引理3 2 若式( 3 3 ) 中4 满足下降条件，即g r 4 l蛑 佃 i i 反2 ( 3 2 6 ) 证明：- 记f k = f ( x k ) ，g k = 可( 砟) ，k = 1 ，2 ，。根据迭代形式( 3 3 ) 及w o l f e 条 件( 3 2 0 ) 知 纽 盘瞅孬一一d瓮 丝 第三章解无约束优化问题的下降算法 由l i p s c h i t z 条件知 ( g i + l g k ) 7 噍( o - 1 ) g r 4 ( 3 2 7 ) l i g m - g 。l l - ml x , “- x i i - m 1 1 d k l i = 口, m i l 4 1 i ( 3 - 2 8 ) 再由c a u c h y s c h w a r z 不等式知 i i ( + 。一) 7 巩l 卜0 + 。一| i 1 1 吨0 圳训2 ( 3 2 9 ) 由( 3 2 7 ) ，( 3 2 9 ) 式得 由w o l f e 条件( 3 - 1