（计算数学专业论文）优化算法与虚拟企业伙伴选择问题的研究.pdf

摘要 对求解无约束优化问题的记忆梯度法中的方向参数给定一个新的区间取法，确定其 取值范围以保证搜索方向是目标函数的充分下降方向，在此基础上，提出了一类新的带 误差项的的记忆梯度算法，算法中参数的取值范围更大，考虑了误差项，使得新算法对 许多实际问题很有用并在目标函数的梯度一致连续和结合删。步长搜索条件下，证 明了算法的全局收敛性同时给出带误差项的结合拟一n e w t o n 方程的记忆梯度算法数值 例子表明算法是有效的 设计了求解无约束最优化问题的新的非单调线搜索规则的带误差项l 锄p 撕e u 修正 对角稀疏拟牛顿算法新的步长规则类似于嘶p p o 非单调线搜索规则并包含僦p p o 非单 调线搜索规则作为特例新的步长规则在每一次线搜索时得到一个相对于g d p p o 非单调 线搜索规则的较大步长，有利于算法快速收敛，同时保证算法的全局收敛性数值例子 表明算法是有效的，适合求解大规模问题 讨论了虚拟企业伙伴选择与管理问题提出了初选、精选、优化组合的虚拟企业伙 伴选择三步法并建立了基于遗传一模拟退火算法的虚拟企业合作伙伴优化组合模型，克 服了遗传算法早熟现象对虚拟企业伙伴选择的影响进而分析了伙伴关系管理的复杂 性，提出了“动态合同+ 信任机制 的双重管理方法 关键词：记忆梯度算法，对角稀疏拟牛顿算法，误差，收敛，虚拟企业伙伴选择 o p t i m i z a t i o na l g o r i t h ma n dt h ev i n u a le n t e r p r i s ep a r t n e r s e l e c t i o np r o b l e m s ( 沁y a l i ( c o m p u t a t i o n a lm a f h e m a t i c s ) d i r e c t e db yp r 0 s u l lq i n g 灿g a b s t r a c t a n e w 嬲s 瑚叩t i o ni s 百v 胁o nm es c a l a ro fc o 巧u g a t e 黟a d i e n tm e t h o dt 0e i l s u r et l l a tt h e d i r e c t i o ni sas u 伍c i e n td e s c e n td i r e c t i o n an e wc 1 嬲so fm e m o r y 黟a d i e n tm e m o dw i t l le n o r s i sp r e s e n t e d t h en e wm e t h o di sa p p l i c a b l et 0v 撕o u sd i 伍c u hp r o b l e m se i l c o u n t e di np r a c t i c e b e c a u s eo ft l l a ti tc o n s i d e r st l l ee 盯0 r s 锄d 啪go fm es c a l a ri sw i d 既t h e9 1 0 b a lc o n v e 唱e 1 1 c e p r o p e r t i e so ft h en e wa l g o r i t h l i l 盯ed i s c u s s e d0 nc o n d i t i o nt l l a tt h e 伊a d i e n to ft h eo b j e c t i v e f i l n i m o ni su n i f o m l yc o m i 肌o u sa n da 肋i j os t 印s i z e1 1 l l e c o m b i i l i n g 删i n e 、玑o n e q u a t i o nw i t ho u rn e wm e t h o d ，q u 豁i - n e 、玑o nm e t h o dw i t he 玎o r si sm o d i f i e dt 0h a v e 酉o b a l c o n 、，e 玛e 1 1 c ep r o p e r t y n 眦e r i c a lr e s u l t ss h o wt h a tt h en e wa l g o r i m m sa r ee 伍c i e n t w bp r o p o s ean e wn o n m o n o t o n es t 印s i z em l ea i l da n a l y z em e9 1 0 b a lc o n v e r g e i l c eo fa l 锄叩a r i e l l om o d i f i e dd i a g o n a l - s p a r s eq u a s i n e 、矾o nm e t h o dw i me r r o r s t h en e ws t 印s i z e m l ei ss i i i l i l a rt ot l l eg r i p p on o n m o n o t o n es t 印s i z em l e 锄dc o n t a i 璐i t 嬲as p e c i a lc a s e w b c 觚c i l o o s eal a 唱e rs t 印s i z ei i le a c hl i i l es e a r c hp r o c e d u 鹏a n dm 曲m l i n 廿l e 9 1 0 b a l c o n v e 唱e 1 1 c ep r o p e n yo fo u rl a m p a d e l l om o d i f i e dd i a g o n a l - s p a r s eq u 弱i - n 创n o nm e t l l o d n u m e r i c a lr e s u l t ss h o wm a tt h en e w a l g o r i t l l m sa r ee 伍c i e n t w bc o i l s i d e rt h ev i r t i l a le n t e 印r i s ep a m l c rs e l e c t i o na n dm a n a g e m e m h lt h i sp a p e r a t h r e e s t 印s 仃a t e g yi sp r o p o s e d w ec l e 砌ye l a t 0 r a t em e0 p t i m i z a t i o nm o d e lb 硒e d0 ng e n e t i c s i m u l a t e d 猢e a l i n ga l g o r i t l l i l l a 1 s 0 ，am a i l a g e m e n tm o d e lo fv i r t l l a le 1 1 t e 印r i s ep a n n e ri s 百v e ni 1 1t h ep a p 钌 k e yw o r d s ：m e m o 巧g r a d i e n tm e t h o d ，d i a g o n a l s p a r s eq u a s i n e w t o nm e t h o d ，e i t o r c o n v e 唱e i l c e ，v i r t u a le n t e 印r i s ep a n i l e rs e l e c t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：幺釜堡厘 日期：沙8 年，月矽日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：鲤丘百 指导教师签名：厶1 盆 鱼 _ ， 日期：2 哟年 日期：2 四年 厂月土7 日 ，月，7 日 j 中国石油大学( 华东) 硕士学位论文 第一章绪论 最优化问题是在多种( 有限或无限种) 决策中挑选最好决策的问题，它广泛应用于农 业、国防、交通、金融、能源等许多领域，如在资源利用、结构优化、调度管理、后勤 供应等许多问题中产生了巨大的经济效益和社会效应优化在结构力学、生命科学、环 境科学等其他科学研究领域和方向也有广泛应用 非线性最优化是在二十世纪5 0 年代发展起来的，主要讨论非线性决策问题的最佳 选择之特性，构造寻求最优解的计算方法，研究这些计算方法的理论性质及实际计算表 现许多急需解决的、对国民经济有重大影响的大规模复杂科学和工程问题本质上都是 优化问题它们有的规模十分巨大( 维数达上百万，如大气科学中的四维同化问题) ，有 的规模并不十分巨大却是非常复杂的优化问题( 如化工工业中的多相流计算问题) 因 此，研究高效的优化计算方法不仅具有重要的科学意义，而且具有广泛的应用前景，将 对促进优化方法在国民生产等方面的应用起到重大作用 随着经济全球化、市场国际化，信息技术和通信技术的快速发展，时间和反应速度 已经取代成本和质量成为企业第一竞争要素同时由于企业的资源有限，单个企业很难 在竞争激烈、快速多变的市场环境中靠自己的能力将产品快速推向市场满足客户的需求 在这样的竞争环境下，企业逐渐意识到，必须组建虚拟企业，从合作伙伴企业中获得互 补性的资源，以取得竞争优势虚拟企业是由多个具有不同核心能力的合作伙伴构成的、 暂时性的企业联盟虚拟企业间的伙伴关系的好坏将直接关系到虚拟企业的成败因此， 对虚拟企业合作伙伴选择问题的研究，将为虚拟企业选择合适的合作伙伴提供科学、可 行的改进建议有助于更多的企业运用虚拟企业的管理思想，提高自身的市场竞争能力 本文包括求解无约束优化问题的带误差项算法研究和虚拟企业伙伴选择方法研究 两部分全文共分五章，第一章是绪论，简单介绍了记忆梯度算法、对角稀疏拟牛顿算 法、带误差项算法、非单调线搜索技术和虚拟企业伙伴选择方法的发展；第二章、第三 章讨论了求解无约束优化问题的带误差项的记忆梯度算法、对角稀疏拟牛顿算法；第四 章论述了对虚拟企业如何选择并管理合作伙伴以使得企业获得最大利润：最后是结论 第一章绪论 1 1 优化算法简介 1 1 1 记忆梯度算法简介 考虑无约束优化问题： ( p ) 卿厂( x ) 其中厂( x ) ：尺4 一尺1 是一阶连续可微函数 求解问题( p ) 的共轭梯度法，收敛速度快，存储量小，适于求解大规模问题记 = 夥瓴) ，它具有如下迭代公式形式 x i + l = 以+ 以d t ， ( 1 1 ) 小 o 眦甚 m 2 ， 以是步长可通过某种策略确定；级是参数，反不同算法不同如 胪- i ig i1 1 2 | lg 七- l1 1 2 ， 但l e t l c h e r - r e e v e s ，1 9 6 4 ) 酬豫= ( g i r ( g i g i 1 ) ) | jg t l1 1 2 ，( p o l a k i u b i e r e p o l y a l 【，1 9 6 9 ) 酬据= ( g tr ( g t g i 1 ) ) ( d 三1 ( g t g i 1 ) ) ，( h e s t e l l e s s t i e f e l ，l9 5 2 ) 分别对应f r ，p r ，h s 共轭梯度法三者比较，f r 算法具有较好的收敛性质，而后两者 数值表现差不多，都优于f r 算法 记忆梯度法是共轭梯度法的变形与改进，具有更快的收敛速度m i e l e a 【1 1 介绍了记 忆梯度算法，基本公式为： 协麓黧裂二黧嚣啦。， m 3 ， 1 刃j ，万r ：m i n 厂( 工t 一万。可歹( x t ) + 万l 工i 1 ) 、1 。7 随后，文献 2 4 】，利用记忆梯度算法的基本思想，增加记忆项的项数，引入超记 忆梯度算法，由于这类算法在迭代中较多的利用了目标函数已得到的某些信息，因而具 有比记忆梯度算法更快的收敛速度，大量的数值例子证明了这一点 其基本公式为： 2 中国石油大学( 华东) 硕士学位论文 以+ 。= 以一刃w ( 以) + 万y 缸， f = l 硪，刃：，唾厂( 以一万。耵( 以) + 呒缸，) 口t，巧r： 其中，缸。一，； 耄：三：x i 。，七z = ，2 ， ( 1 4 ) 可见，记忆梯度算法在每一次迭代中都需要作一次二维搜索，而超记忆梯度算法在 每一次迭代中需要作一次，+ 1 维搜索，这一点很不理想为此，很多文献对算法进行了改 进【5 6 】赵庆祯5 1 首先将超记忆梯度法的多维精确搜索改为一维非精确搜索，并证明了改 进算法具有n 步超线性收敛速度，从而使超记忆梯度算法更具实用性 超记忆梯度算法的本质在于用前几次迭代方向去修正当前点的负梯度，得到下降的 迭代方向，即 d i = 一v 厂( 以) + 反，l j i l + 反，2 d t 一2 + + 级，d i 一， 其中，以为当前点以处的下降方向，本质上是展1 ，展，的取法时贞军【7 川1 对无约束 优化问题在，= l 时，提出了孱。为区间取值的超记忆梯度算法，并在水平集有界的条件 下证明了算法的收敛性质；孙清滢【9 1 给出共轭梯度方向( 1 2 ) 的参数鼠的取值范围，建立 了求解问题( p ) 的新三项共轭梯度算法，在去掉水平集有界和广义知1 1 1 i j o 搜索下讨论了 算法的全局收敛性；随后，孙清滢【1 2 1 又建立了求解问题( p ) 的三项记忆梯度算法，并在 非单调线搜索下讨论了算法的全局收敛性，算法搜索方向中的参数取值是一个区间； l g r i p p o 等【1 3 】首先对牛顿法提出了一个非单调线搜索框架，z h a n gh c 改进了传统非 单调线搜索参考值的选取，提出了一种新的选取方法，克服了传统非单调线搜索的缺点， 并在一定条件下证明了算法的全局收敛性及r 线性收敛性；s l l iz j 提出了一种新的非 精确线搜索准则，该线搜索在每一步迭代时能得到较大的步长，包含m i j o 线搜索作 为其特例，并讨论了下降算法的全局收敛性及线性收敛速率 1 1 2 对角稀疏拟牛顿算法简介 求解问题( p ) 的拟牛顿算法收敛速度快，每次迭代不需要计算目标函数的h e s s e 矩 阵及其逆矩阵，记g 。= 可( 吒) ，其基本迭代形式为： 第一章绪论 以+ l = x t + 口t d i ， 其中吼为搜索步长可通过某种策略确定；搜索方向为 d k = 一hk g t ， 其中h 。为目标函数的h e s s e 矩阵的逆矩阵之近似，要求正定且满足拟牛顿条件： 其中，y i 一12g i g t l ，j i l = 以一工t 1 ( 1 - 5 ) ( 1 6 ) ( 1 - 7 ) 求解问题( p ) 的稀疏拟牛顿法是由s c h b e n ( 1 9 7 0 ) 首先把拟牛顿校正公式推广到不对 称稀疏矩阵上，提出了解非线性方程组的稀疏拟牛顿法p o w e l l ( 1 9 7 6 ) ，t o i n t ( 1 9 7 7 ) ， s h a l l i l o ( 1 9 8 0 ) 先后推导了稀疏拟牛顿校正公式，s t e i h a u g ( 1 9 8 4 ) 给出了一个采用预处理策 略的稀疏拟牛顿法，并给出了收敛性证明2 0 0 6 年，时贞军和孙国【1 6 1 在系统科学与数学 上发表文章无约束优化问题的对角稀疏拟牛顿法，对无约束优化问题提出了对角稀疏拟 牛顿法，采用了加m i j o 非精确线搜索，并且在每次迭代中利用了对角矩阵近似拟牛顿 算法中的校正矩阵，使计算搜索方向的存储量和工作计算量明显的减少，为大型无约束 优化问题的求解提供了新的解题思路 假设而，而，五已经确定，定义噍= 一巩为拟牛顿方向，其中以为h e s s e 矩阵的 逆近似，= 耵( & ) ，要求以正定且满足拟牛顿条件( 1 - 7 ) ，迭代具有如下形式： 以“= t + 吼噍，这里吼采用某种搜索得到的步长我们知道在拟牛顿算法中需要存储 矩阵，它的存储量至少为d 0 2 ) ，因此在处理大型问题时，需要的存储量是相当大的， 如果我们用稀疏矩阵来逼近这样的大型问题的矩阵，对于稀疏矩阵来说，它需要的存储 量为d 0 ) ，因此当变量的个数很多时，这种思想是可取的 1 9 8 8 年，b a r z i l a i 和b o 邢e i n 旧提出了两点步长梯度法，其基本思想是利用迭代当前 点以及前一点的信息来确定步长因子，其迭代公式以= 以一吒致，可以看成是： 黾+ l = 一级g i 其中，q = 吒，是一个矩阵为了使q 具有拟玎性质，计算吼使 4 中国石油大学( 华东) 硕士学位论文 m i n 恢一。一q 儿一。| | 或者 m i n 恢1 。一儿扎 其中，s i2 x i + l x i ，y t2 9 i + l g t 于是，可分别求得： 铲静 及 吒= 蛙 很多学者对这类算法进行了研究，得到了若干重要结论【1 8 2 1 1 ，数值试验的结果也证 明了这种算法比最速下降法，共轭梯度法有效，适用于求解大规模问题，但该算法不能 保证具有全局收敛性 s c h u b e n 首先对非线性方程组提出了稀疏拟牛顿澍2 2 1 ，主要强调保持拟牛顿矩阵和 j a c o b i 矩阵具有相同的稀疏性，这无疑增加了算法的计算工作量，有关传统的稀疏拟牛 顿算法理论结果可见【2 3 】 稀疏拟牛顿法的主要思想为在拟牛顿算法中，限制也为正定稀疏矩阵且近似满足 拟牛顿条件( 1 - 7 ) ，可以通过求解 m i n j i 。儿一。一一。旺 而得到矾，从而可构造稀疏拟牛顿法这种方法的存储量小，并且具有较好的收敛性质， 适合求解大型问题 2 0 0 6 年时贞军和孙国【1 6 1 设计了对角稀疏拟牛顿法的实现形式，证明了对角稀疏拟牛 顿法的全局收敛性，讨论了线性收敛速度和超线性收敛特性，并对算法进行了数值试验， 结果表明算法比通常的共轭梯度法有效，适于求解目标函数h e s s e 矩阵为稀疏的大型问 题 下面介绍对角稀疏拟牛顿法 设校正矩阵风= 幽曙( 磋，磁，磁) 为对角矩阵，计算以使得 5 第一章绪论 m i n 峥。y h s 1 1 2 其中i i 1 | 为欧氏范数因 l l l i n0 吼儿- l - 哐：i i l i n 窆( 吃以i - 。) z 括l j ：一。分别表示向量j ，h ，s 的第f 个分量， 求得磁= 砉( “。) 为保证 喀= 一以为厂( 石) 的下降方向，限制噬在一定范围内，即要求o 有界此假设说明，厂( 力和 g ( 石) = w ( x ) 在三( ) 上都有界 对角稀疏拟牛顿算法的全局收敛性结果如下： 定理l 一1 若假设1 1 成立，则算法或有限步终止于问题的稳定点，或产生无穷迭代点 列k ，其任意极限点都是问题( p ) 的稳定点 假设1 - 2 设厂( 力在极小点石的领域内二次连续可微，且j 占 o ，肘 聊 0 ，使得 当峙一x + 0 o ， 坛，y ( x ，s ) ，有下式成立 0 v 2 厂( y ) 一v 2 ( x ) 0 ，i i y z 0 6 中国石油大学( 华东) 硕士学位论文 其中， o 定理1 2 若假设1 1 ，1 2 ，1 3 成立，若算法产生无穷迭代点列瓴 收敛到极小点x ， 即，以寸x + ，但以x ，则当且仅当 1 i m 七 蚓i 时，瓴) 超线性收敛到x = o 1 1 3 带误差项的算法和非单调线搜索技术简介 对于下降算法，由于计算机的舍入误差和随机产生的误差，常常破坏搜索方向的下 降性，因此研究带误差项的算法具有实际应用价值对于此问题的研究，较早由b e n s e k 勰 和t s i t s i k l i s 在文献 2 4 】中对带误差项的梯度算法在发散级数步长搜索下给出算法的全局 收敛性分析，但算法收敛分析过程需要一个较强的假设条件，即厂( x ) 的梯度夥( 工) 满足 l i p s c l l i t s 条件，即存在常数三 o 使得： 慨工) 一可侧三卜孙v x ，；肛 因此去掉这一较强的假设条件分析算法的全局收敛性具有理论意义 非单调线搜索技术由于其有利于求解全局最优解和算法的快速收敛而受到许多最 优化爱好者的青喇2 5 瑚】近年来，许多学者己在牛顿法，拟牛顿法，共轭梯度法等无约 束方法中引入非单调类搜索技巧，并且许多数值实验已经证明了在某些情况，非单调类 算法比单调类算法更加有效，g 五p p ol ，l 锄p 耐e l l ef ，l u c i d is ( 1 9 8 9 ) 【2 9 1 提出了如下非 单调线搜索技术： 给定口 0 ， o o 为参数，吼是可( 孔) 和s k 一，的夹角 ( b ) ：误差项心满足 慨i j 7 。( g + p i | 夥( ) d ( 2 4 ) 其中以满足 ： o ，后= 1 ，2 ( 2 5 ) 由式( 2 3 ) 仿文献 5 ，6 可取 风 一壁。( ) ，t ( ) 】， ( 2 - 6 ) 其中， 删= 阿击面臀， ) 酏= 阿南面钳 仁8 ， ( c ) ：以为步长，由下列规则确定： 如果耵o 。) r ( j 。+ m ) o ，取以= 以：否则取以= 厂心，其中朋。为满足下面不等式 的最少非负整数： 厂( x i + 以( s i + ) ) 一厂( 工t ) 丑“v ，r ( x i ) r ( j t + ) ( 2 9 ) 其中( o ，1 ) ，y ( 0 ，1 ) 为常数 第二章结合a n l 嘶。步长搜索的带误差项的记忆梯度算法 注求解无约束优化问题( p ) 的算法，包括拟一n 喇o n 算法，有限记忆b f g s 算法， 其搜索方向可表示为瓯s 。= 一鼠，其中反是一个正定对称矩阵满足拟一n e 叭o n 方程 皿缸= 缈， 其中血t l = x t z t 一1 ，少t l = g i g t - l ，因此 j i r 知t l = - ( 曰t ) 一1g t 】r 少i l = 一g t ，( b t ) 一1 缈t l = 一g l r 缸t 一1 再有= 一瓯+ 反s h 及上式得 屈蛳卜：蓝坐芷纽 s 1 缈h 结合以上参数，在( m g m e ) 中可选取参数以为 展= a r g m i f l 一履细扣m 栅i ： 坦。( ) ，万。( ) 】 从而得到结合拟卟t e 叭o n 方程的带误差项的记忆梯度法记为q g m e 引理2 - 1 若以不是问题( p ) 的稳定点，孱满足( 2 6 2 8 ) ，则有慨l l c 。l 阿( 以) 0 ， 其中q = 1 + 去 证明 由& 的定义易证 引理2 2 若以不是问题的稳定点，展满足( 2 6 2 - 8 ) ，则有 夥( 小t o ，当七，充分大时有 0 可( 以) i i o 使得 l l 可丁( x 。) 0 氏， v 七k 。 由= ( ，nk o ) u ( ，nk ) 知，当七，r 、k 。时，由引理2 - 3 知 m 腮_ 。桫( 训树船。吖t 2 0 故，r 、k 。最多只有有限个元素，不妨设，r 、k = 故k 。c ， v 后k 。c ，由引理2 - 2 ，式( 2 - 4 ) 知 一丫厂( 工。) r ( j 七+ m ) c ：0 v 厂( x 。) 0 2 0 v 厂( x 。) l y 。( g + p 8 v 厂( x 。) 1 1 ) = ( c ：一y 。p ) i l 町( x 。) 0 2 一以g i i 夥( x 。) l 【( c ：一7 。p ) 岛一厂。9 1 | 可丁( 石。) 0 由引理2 1 ，式( 2 4 ) 得 i p 。+ 0 c 。i l v 厂( x 。) 0 + 以( g + p 0 v 厂( x 。) 1 1 ) = ( c 。+ 以g | l 耵( 黾) l i + 九p ) i 阿( ) i i ( c ，+ 7 。g 岛+ y 。p ) j i 夥( x 。) 0 由式( 2 9 ) ，( 2 - 1 3 ) 得 厂( 以) 一厂( 以) 一乒以v 厂( z i ) r ( s 七+ ) 乒k 【( c ：一以p ) s 。一儿g l l i 可丁( x 。) 0 令七马得 。是盟。五桫( 圳= o 由式( 2 1 5 ) 及0 可( 以) i l 占。，v 后知 厂( 以) 一厂( 工i “) 一声吸占o 【( c 2 一厂i p ) s o y g 】 令后马得 1 i m 九= 0 t e ，t _ 1 4 ( 2 一1 3 ) ( 2 1 4 ) ( 2 - 1 5 ) 中国石油大学( 华东) 硕士学位论文 设以= 以，则由( 2 9 ) 知 厂( x t ) 一厂( x t + 以( s i + w 七) ) 胛( 以) r ( s i + m ) ， 其中o 吼 一1 一) 耵( 黾) r ( j 。+ m ) ( 2 1 7 ) 由式( 2 1 3 ) ，( 2 1 4 ) 及式( 2 - 1 7 ) 得 一川耵( 以+ 幺石( + m ) ) 一v 厂( 训帜+ 8 1 一生；_ j l 一 。 一v 厂( x i ) 7 ( s t + 心) 吆兰：竺坐! ：型二! 剑匣兰竺：型竺( 2 - 1 8 ) 【c 2 一y i p j 民一厂t g 由式( 2 1 4 ) 知 瓦t 恢+ 0 专以0 町k ) 肌c - + 儿p + 以g s 。) 令七马得 。业盟。邳t + i i = o ( 2 1 9 ) 再由夥( 以) 得一致连续及式( 2 1 8 ) ，( 2 - 1 9 ) ，令七马o o 得l 一o 即1 此与 o 1 矛盾故有舰町( ) = o 定理2 2 设k ) 是由算法产生的无穷点列，如果存在一个凸集d2k 。e ，使得 耵( 工) 在d 上一致连续，则或者! i m ( 以) = o o 或者! i m 耵( ) = o 丘膏- 证明 当后，n 充分大时，由引理2 1 ，引理2 - 3 ，式( 2 4 ) ，( 2 - 5 ) 知 “忙。+ w 10 儿【c 。0 夥g 。) 】f + 儿( p 0 夥g 。) 翊+ g ) 1 力【0 q + 印厂i + g 】 ( 2 - 2 0 ) 由式( 2 2 0 ) 及中值定理得 厂( x t + 1 ) 一厂( x t ) 1 5 第二章 结合a r n l i j o 步长搜索的带误差项的记忆梯度算法 亍7 t ( v 厂( x i + 吼7 t ( s t + ) ) 一可y ( x i ) ) r ( s t + ) + y t v 厂( x i ) r ( s t + ) “忙。+ | i ( | i w ( 以+ 幺以( & + ) ) 一v 厂( 砟) 0 + 0 夥( 以) 0 ) 7 ；( 。+ 印以+ g ) ( i i v 厂( x i + 吼以( s i + ) ) 一v ，( ) 0 + d 以) ， 其中0 o 使得 厂( 也+ 1 ) 一厂( 工t ) o 盯2 以 取盯，= m a x p 。，盯2 ，由式( 2 2 1 ) ，( 2 2 2 ) 易得 厂( z t + 。) 一厂( x i ) 仃3 7 ； 令： 互= 盯，巧，则当后充分大时有 厂( 工t + 。) + 互+ 。厂( 以) + 互 ( 2 - 2 2 ) ( 2 2 3 ) ( 2 - 2 4 ) 由式( 2 2 4 ) 知，当七充分大时，沙( a ) + 疋) 单调下降，再由互_ o ( 七一) 知，或者 ! i m 厂( 以) = 棚，或者纱( 坼) ) 存在有限极限，此时由定理2 1 知，! i m v ( 以) = o - i 2 4 数值实验 本节选择了文献 4 7 】中的几个算例，利用m a t l a b 编制程序并与f r ，p r ，h s 共轭梯 度法进行比较，在p 9 3 3 机器上对本文算法进行数值实验以= 吉，“= o 2 5 ， 七= l七= l p = 1 2 9 ，= o 0 6 7 ；用i n i t 表示以帅卜胁咖【一丝k ( ) ，厦( ) 】的迭代次数，i t 表示 算法的迭代次数，t 表示所用时间，厶，表示目标函数的最优值 例1厂( x ) = l o ( x 1 2 一x 2 ) 2 + ( 1 一工1 ) 2 + 9 ( z 4 一黾2 ) 2 + ( 1 一工3 ) 2 + 1 0 1 ( ( x 2 1 ) 2 + ( _ 一1 ) 2 ) + 1 9 8 ( x 2 1 ) ( x 4 1 ) n = 4 ，初时点= ( 一3 ，一1 ，一3 ，一1 ) r ；最优点x 叫= ( 1 ，1 ，1 ，1 ) ；厂( x 叫) = o 精度要求 1 6 中国石油大学( 华东) 硕士学位论文 0 w ( 以) i | l o - 2 ，l o 。3 的计算结果见表2 一1 表2 1 t h b l e 2 1 算法 烈r rr rt p i 风1 9 5 2 8 00 2 7 0 0 s ，0 6 0 0 0 s1 0 6 7 0 e - 0 0 5 ， 1 3 7 8 5 e 0 0 7 h s2 4 6 3 8 50 1 0 0 0 s 0 4 6 l o s4 6 9 81 e - 0 0 5 ，4 9 4 4 6 e - 0 0 7 p r 8 3 ， 9 1 o 3 6 1 0 s ，o 1 1 0 0 s2 8 8 0 6 e 0 0 6 ， 1 9 7 0 3 e 一0 0 7 m g m 匣4 2 6 50 0 4 7 0 s ，0 0 31o s 2 0 0 9 2 e 0 0 5 3 4 13 9 e 一0 0 7 q g m e 1 8 ， 2 5 3 l ， 3 8o 0 3 2 0 s 0 0 4 6 0 s1 4 9 2 3 e 一0 0 5 ，2 8 1 3 1 e - 0 0 8 例2 2 厂( x ) = 萄( 石：，一工：h 2 ) 2 + ( 1 一x ：扣。) 2 】， n _ 1 2 0 ，初时点而= ( 一1 2 ，l ，一1 2 ，1 ) r ；最优点x 叫= ( 1 ，1 ，1 ) ；厂( 工叫) = 0 精度 要求0 耵( 以) 忙l o 之，l o 。3 的计算结果见表2 2 表2 - 2 】陆b l e 2 2 算法 烈n r rt 啦 f r 1 3 4 2 0 2 0 4 7 1 0 s ， 0 3 1 0 0 s 1 4 2 8 6 e - 0 0 4 ，3 1 3 2 3 e _ 0 0 7 h s5 2 7 9 0 1 1 0 0 s ，0 1 4 1 0 s 5 9 2 7 2 e - 0 0 5 ， 9 6 3 9 4 e 0 0 7 p r 1 1 ， 2 2 0 0 5 0 0 s 。o 1 1 0 0 s 7 0 0 3 2 e 0 0 5 ，2 0 0 6 6 e 0 0 7 m g m e 1 6 ， 2 0 o 0 4 7 0 s ， 0 0 4 7 0 s4 2 8 8 3 e - 0 0 6 1 5 3 4 3 e 0 0 7 q g m e 5 ，1 0 8 ， 1 4 0 0 4 7 0 s ，0 0 4 7 0 s 1 8 3 7 5 e _ 0 0 5 1 3 5 0 3 e - 0 0 7 例3 厂( z ) = x r q x x r 6 ， 其中， f ，9 6 4 55 3 2 37 8 9 86 1 3 3 q = i ；主：言主竺：耋言：三錾：三：i ， 6 = c t ，4 ，2 ，3 ，r 。 i7 8 9 86 2 1 48 9 1 46 2 4 5l 。 一。 6 1 3 34 5 1 16 2 4 54 7 0 5 初始点毛= ( o ，o ，o ，0 ) r ；最优点工叫= ( o 1 3 0 4 ，0 8 2 4 5 ，_ o 4 0 6 8 ，o 3 8 8 6 ) r ， 1 7 第二章结合a m i j o 步长搜索的带误差项的记忆梯度算法 厂( ) = - o 7 2 4 5 精度要求l l 夥( ) j i 1 0 - 2 ，1 0 。3 的计算结果见表2 3 表2 - 3 1 r a b l e 2 3 算法 烈i tr rt 啦 f r1 4 8 2 6 50 15 6 0 s o 2 6 6 0 s- o 7 2 4 5 一o 7 2 4 5 h s 6 9 8 ， 1 2 5 10 6 4 0 0 s 1 1 4 0 0 s一0 7 2 4 4 旬7 2 4 5 p r1 3 7 2 1 l0 1 4 0 0 s 0 2 5 0 0 s 一0 7 2 4 5 ， 0 7 2 4 5 m g m 匣1 5 4 2 4 90 15 6 0 s o 2 3 4 0 s一0 7 2 4 4 7 2 4 5 q g m e 4 8 7 2 5 7 ， 8 2 o 0 6 2 0 s ， 0 0 7 8 0 s- o 7 2 4 5 - 0 7 2 4 5 计算结果表明新算法是有效的，另外在结合拟n e 叭o n 方程的带误差项的记忆梯度 法中，展大部分取为成细扣咖 1 8 中国石油大学( 华东) 硕士学位论文 第三章新的非单调线搜索规则的带误差项l a m p 撕e l l o 修正对角 稀疏拟牛顿算法 本章在非单调线搜索规则基础上，结合s h iz j 大步长线搜索技巧提出新的增大步长 的非单调线搜索规则，设计求解无约束最优化问题的大步长非单调线搜索规则的带误差 项的l a l n p 撕e 1 1 0 修正对角稀疏拟牛顿算法，在w ( 石) 一致连续的条件下给出算法的全局 收敛性，并分析算法的超线性收敛性用数值例子验证算法的有效性 3 1 引言 考虑无约束优化问题：( p ) 理磐( z ) ，其中厂( x ) ：r ”啼r 1 是一阶连续可微函数求 解问题( p ) 的拟牛顿算法收敛速度快，每次迭代不需要计算目标函数的h e s s e 矩阵及其 逆矩阵，记巩= 町( ) ，其基本迭代形式为 以+ l = 以+ o c t 以， ( 3 - 1 ) 其中口。为搜索步长可通过某种策略确定；搜索方向为 d t = 一日i g i ， ( 3 2 ) 其中日。为目标函数的h e s s e 矩阵的逆矩阵之近似，要求正定且满足拟牛顿条件 其中儿一。= 一g 。一，一。= 以一以十但算法存储量至少为d ( 靠2 ) ，这给求解大规模问 题带来困难为此，1 9 8 8 年，b a r z i l a i 和b o 刑e i n 【1 7 1 提出了如下两点步长梯度法，其迭 代公式为以+ 。= 以一q g 。，其中以= 0 c 。，是一个数量矩阵为使4 具有拟牛顿性质， 计算步长九。满足 m i n l l q y h 一一，l i ， 1 9 第三章 新的非单调线搜索规则的带误差项l 蚰币撕e l l o 修正对角稀疏拟牛顿算法 其中y h = g i 一瓯一l ，s h = 以一工求解得 2 静撕_ 眵糌舭搏 法进行研究，并得到许多重要结论m 1 9 2 l 】为使取更加充分接近目标函数的h e s s e 矩阵的 逆矩阵，时贞军m 1 提出了如下对角稀疏拟牛顿算法，其存储量降为d ( 以) 即在拟牛顿算 法中限制校正矩阵日。为对角正定稀疏矩阵且近似满足拟牛顿条件，即： 设日。=