（计算数学专业论文）非线性规划超记忆梯度算法和glp投影算法.pdf

非线性规划超记忆梯度算法和6 l p 投影算法 程鹏( 计算数学) 指导教师：孙清滢( 教授) 摘要 非线性规划计算方法是数值计算领域中十分活跃的研究课题之 一快速地求解非线性规划问题，除了其自身的重要性外，还体现在 它也构成一些线性规划问题的子问题因此，对于非线性规划问题， 如何设计快速有效的算法一直都是优化工作者十分关心的问题本 文第二章提出了结合广义a r m i j o 步长搜索规则的一类带误差项的记 忆梯度求解算法，并在v 厂( x ) 一致连续的条件下，证明了算法的全局 收敛性同时给出带误差项的结合拟一n e w t o n 方程的记忆梯度算法 数值例子表明算法是有效的第三章利用广义投影矩阵，结合记忆梯 度算法建立了求解非线性不等式约束优化问题的一个记忆梯度广义 投影算法，并证明了算法的收敛性同时给出了结合f r 、p r 、h s 共 轭梯度参数和拟牛顿方程的记忆梯度广义投影算法数值例子表明 算法是有效的第四章给求解无约束规划问题的记忆梯度算法中的 参数一个特殊取法，得到目标函数的记忆梯度g o l d s t e i n - l a v i n t i n p o l y a k 投影下降方向，从而对凸约束的非线性规划问题构 造了一个记忆梯度g o l d s t e i n l a v i n t i n p o l y a k 投影算法，并在一维精确 步长搜索和去掉迭代点列有界的条件下，分析了算法的全局收敛性， 得到了一些较为深刻的收敛性结果同时给出了结合f r 、p r 、h s 共轭梯度算法的记忆梯度g o l d s t e i n - l a v i n t i n - p o l y a k 投影算法，从而 将经典共轭梯度算法推广用于求解凸约束的非线性规划问题数值 例子表明新算法比梯度投影算法有效 关键词：非线性规划，凸约束的非线性规划，g o l d s t e i n l a v i n t i n p o l y a k 投影算子，带误差项的记忆梯度法，广义n r m i j o 步长搜索 规则 s u p e r - m e m o r yg r a d i e n ta l g o r i t h ma n dg l p p r o j e c t i o na l g o r i t h mi nn o n l i n e a rp r o g r a m m i n g c h e n gp e n g ( c o m p u t a t i o n a lm a t h e m a t i c s ) d i r e c t e db yp r o f e s s o rs u n q i n g - y i n g a b s t r a c t n o n - l i n e a rp r o g r a m m i n gi so n eo ft h ea c t i v et o p i c si nn u m e r i c a l c o m p u t a t i o nf i e l d e x c e p tt h ei m p o r t a n c ei t s e l f , n o n l i n e a rp r o g r a m m i n g i ss o m e t i m e sas u b p r o b l e mo fl i n e a rp r o g r a m m i n gp r o b l e m f o rt h e o p t i m i z a t i o ns c h o l a r s ，h o wt od e s i g na ne f f e c t i v em e t h o dt os o l v et h e n o n l i n e a rp r o g r a m m i n gp r o b l e mi sa ni m p o r t a n tt o p i c t h i sp a p e ri sd i v i d e di n t of i v ec h a p t e r s i nc h a p t e r2 ，w ec o n s i d e r t h ec o n v e r g e n c ep r o p e r t i e so fan e wc l a s so fm e m o r yg r a d i e n tm e t h o d s w i t he l t o r sa n dg e n e r a l i z e d 缸r n i j o s t e ps i z er u l ef o rm i n i m i z i n ga c o n t i n u o u s l yd i f f e r e n t i a b l ef u n c t i o nfo nr ”a s s u m i n gt h a tv f ( x ) o f fi su n i f o r m l yc o n t i n u o u s c o m b i n i n gq u a s i n e w t o ne q u a t i o nw i t ho u r n e wm e t h o d ，q u a s i n e w t o nm e t h o d sw i t he r r o r sa r em o d i f i e dt oh a v e g l o b a lc o n v e r g e n c ep r o p e r t y n u m e r i c a lr e s u l t s s h o wt h a tt h en e w a l g o f i t h m sa r ce f f i c i e n t i nc h a p t e r3 b yu s i n gg e n e r a lp r o j e c t i o nm a t r i x c o n d i t i o n sa n dm e m o 叮g r a d i e n tm e t h o d ，ag e n e r a lm e m o r yg r a d i e n t p r o j e c t i o nm e t h o df o rn o n l i n e a rp r o g r a m m i n gw i t hn o n l i n e a ri n e q u a l i t y c o n s t r a i n t si sp r e s e n t e d t h eg l o b a lc o n v e r g e n c ep r o p e r t i e so ft h en e w m e t h o da r ed i s c u s s e d t h en u m e r i c a lr e s u l t si l l u s t r a t e t h a tt h en e w m e t h o d sa r ee f f e c t i v e i nc h a p t e r4 ，ag e n e r a l i z e dm e m o r yg r a d i e n t p r o j e c t i o nm e t h o df o rc o n v e xc o n s t r a i n e do p t i m i z a t i o ni sp r e s e n t e db y u s i n gg o l d s t e i n - l a v i n t i n - p o l y a kp r o j e c t i o n c o n d i t i o n sa r eg i v e no nt h e s c a l a rt oe n s u r et h a tt h eg e n e r a lm e m o 巧g r a d i e n tp r o j e c t i o nd i r e c t i o ni s d e s c e n t t h e g l o b a lc o n v e r g e n c ep r o p e r t i e s o ft h en e wm e t h o da r e d i s c u s s e dw i t ha l la c c u r a t es t e ps i z er o l ea n dw i t h o u ta s s u m i n gt h a tt h e s e q u e n c eo fi t e r a t i o ni sb o u n d e d c o m b i n i n gf r , p r , h sm e t h o d sw i t h o u rn e wm e t h o d ，t h r e en e wc l a s s e so fm e m o r y 黟a d i e n tp r o j e c t i o n m e t h o d sw i t hc o n j u g a t eg r a d i e ms c a l a ra r ep m s e n m d t h en e wm e t h o d s u s el i t t l es t o r a g e ，t h u st h em e t h o d sa r ea t t r a c t i v ef o rl a r g e s c a l ep r o b l e m s n u m e r i c a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f i c i e n tb yc o m p a r i n gw i m g o l d s t e i n l a v i n t i n p o l y a kg r a d i e n tp r o j e c t i o nm e t h o d k e yw o r d s ：n o n l i n e a rp r o g r a m m i n g ，c o n v e xc o n s t r a i n e do p t i m i z a t i o n ， g o l d s t e i n l a v i n t i n - p o l y a kp r o j e c t i o n ，m e m o 巧g r a d i e n tm e t h o d ， g e n e r a l i z e da r m i j os t e ps i z er u l e 全文通用记号 第k 次迭代点 第k 次迭代的步长因子 第k 次迭代的搜索方向 函数，( 功在处的函数值 函数f ( x ) 在以处的梯度向量w ( 以) 在处对h e s s e 近似的拟牛顿矩阵 f r o b e n i u s 范数 欧几里得范数 坼 巩 矗 吼 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 中国石油大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： 焦鹏 如落1 移 动研年f 月i b 日 q 年f 玛，b e l 中国石油大学( 华东) 硕十论文第l 章绪论 第1 章绪论 1 1 研究背景与进展 非线性规划是二十世纪5 0 年代才开始形成的一门新兴学科 1 9 5 1 年h w 库恩和a w 塔克发表的关于最优性条件( 后来称为 库恩一塔克条件) 的论文是非线性规划正式诞生的一个重要标志在 5 0 年代还得出了可分离规划和二次规划的n 种解法，它们大都是以 g b d a n t z i g 提出的解线性规划的单纯形法为基础的5 0 年代末到6 0 年代末出现了许多解非线性规划问题的有效的算法，7 0 年代又得到 进一步的发展非线性规划在工程、管理、经济、科研、军事等方面 都有广泛的应用，为最优设计提供了有力的工具 非线性规划是具有非线性约束条件或目标函数的数学规划，主要 讨论非线性决策问题的最佳选择之特性，构造寻求最优解的计算方 法，研究这些计算方法的理论性质及实际计算表现随着电子计算机 的发展和应用，非线性最优化理论和方法有了很大发展目前，已成 为运筹学的一个重要分支，并且在自然科学、工程技术、经济管理、 系统工程，特别是“优化设计”等诸多领域得到广泛应用，成为一门 十分活跃的学科【1 3 】 非线性规划研究一个n 元实函数在一组等式或不等式的约束条 件下的极值问题，且目标函数和约束条件中至少有一个是非线性函数 目标函数和约束条件都是线性函数的情形则属于线性规划 一般情况下，非线性规划中求解无约束优化问题的共轭梯度法是 求解大规模问题的有效算法，它能有效避免存储和计算矩阵【4 _ 6 】，目 前主要有f r 、p r 、h s 共轭梯度法三者比较，f r 算法具有较好的 中国石油大学( 华东) 硕士论文第1 章绪论 收敛性质，而后两者数值表现差不多，都优于f r 算法记忆梯度法 是共轭梯度法的变形与改进，这类方法在迭代中较多地利用了已经得 到的目标函数的某些信息，因而具有较快的收敛速度【7 8 】若能将此 法推广用于求解约束优化问题，可望改善现有算法的收敛速度【9 】 若不采取重开始技巧，标准共轭梯度法最多线性收敛然而重开 始策略抛弃了算法沿前一搜索方向得到的二阶信息，且在数值上重开 始时函数的即刻下降量常小于不重开始时函数的即刻下降量故文 献 10 12 研究了三项共轭梯度法三项记忆梯度法是记忆梯度法的 推广，文献f 1 3 ，1 4 研究了一类数值效果有效的三项记忆梯度下降算 法，算法搜索方向中的参数取值是一个区间然而由于计算机的舍入 误差和随机产生的误差，常常破坏搜索方向的下降性，因此研究带误 差项的算法具有实际应用价值对于此问题的研究，较早由 b e r t s e k a s 和t s i t s i k l i s 在文献【1 5 】中对带误差项的梯度算法在发散级 数步长搜索下给出算法的全局收敛性分析，但算法收敛分析过程需要 一个较强的假设条件，即厂( 功的梯度可丁( x ) 满足l i p s c h i t s 条件，即存 在常数l 0 使得 l l 洲一耵( 训上卜硎，v x , ；肛 本文研究带误差项的一类新的记忆梯度算法，算法中参数的取值 范围比文献【1 3 ，1 4 更大，并在v f ( x ) 一致连续和结合广义a r m i j o 步 长搜索条件下讨论算法的全局收敛性同时给出带误差项的结合拟 - n e w t o n 方程的记忆梯度算法数值例子表明算法是有效的 r o s e n 梯度投影法 1 6 ，1 7 是求解非线性约束优化问题的基本方 法之一，近年来梯度投影算法与其它方法结合，也得到了许多有效算 2 中国石油大学( 华东) 硕十论文第1 章绪论 法，在最优化领域占有重要地位如高自友【1 8 】建立了求解非线性不 等式约束优化问题的计算量小，稳定的广义梯度投影算法，但算法收 敛速度慢记忆梯度算法是求解无约束规划的有效算法，由于这类方 法在迭代中较多地利用了已经得到的目标函数的某些信息，因而具有 较快的收敛速度 1 9 ，2 0 因此若能将此法推广用于求解约束优化问 题可望改善现有梯度投影算法的收敛速度 本文利用广义投影矩阵，给求解无约束规划的记忆梯度算法中的 参数一个假设条件，确定参数的取值范围，以保证得到目标函数的记 忆梯度广义投影下降方向，进而建立求解非线性不等式约束优化问题 的一个记忆梯度广义投影算法，在厂( 曲一阶连续可微的条件下证明算 法的收敛性同时给出结合f r 、p r 、h s 共轭梯度参数的记忆梯度广 义投影算法，以及结合拟牛顿方程的记忆梯度广义投影算法并用数 值例子验证新算法的有效性 g l p 投影算法是求解非线性约束最优化问题的基本方法之一，在 最优化领域占有重要地位该算法最早由g o l d s t e i n ( 19 6 4 ) 、l e v i t i n 和p o l y a k ( 1 9 6 6 ) 提出【2 1 】，从此，国内外学者进行了大量的研究并 取得了丰硕的成果它的优点是具有良好的收敛性质因此，一直以 来受到了最优化研究界的重视特别是近几年来，一直是非线性最优 化的研究热点之一记忆梯度算法和g l p 投影结合求解带凸集约束 的非线性规划问题，可望改善现有g l p 梯度算法的收敛速度 本文给出求解无约束规划问题的记忆梯度算法中的参数一个特 殊取法，得到目标函数的记忆梯度g o l d s t e i n - l a v i n t i n p o l y a k 投影下 降方向，从而对凸约束的非线性规划问题构造了一个记忆梯度 g o l d s t e i n l a v i n t i n p o l y a k 投影算法，并在一维精确步长搜索和去掉 3 中国石油大学( 华东) 硕士论文第l 章绪论 迭代点列有界的条件下，分析了算法的全局收敛性，得到了一些较为 深刻的收敛性结果，这些结果是以往工作的进一步深入与加强同时 给出了具有好的收敛性质和较快收敛速度的结合f r 、p r 、h s 共轭 梯度算法的记忆梯度g o l d s t e i n - l a v i n t i n - p o l y a k 投影算法，从而将无 约束最优化方法中共轭梯度算法在限制取值意义下推广用于求解凸 约束的非线性规划问题新算法保留了梯度投影算法的优点，改进了 梯度投影算法的收敛速度算法需要较小的存储，适合于大规模非线 性凸集约束优化问题的计算数值例子表明新算法比梯度投影算法 有效 1 2 基本概念 给出最优化问题的数学模型 幽，( 鬯 ( 1 2 1 ) s t z e q 其中，函数厂：r ”一r 称为目标函数，q s r ”称为可行域，它是 由满足某种条件的点组成的集合，可行域有多种表现形式，一般 用等式和不等式来定义，如 q = i e r ”lc ，( x ) = o ，f g ；c ，( x ) o ，f j ) 对i 岛q ( 力= 0 称为等式约束，s 称为等式约束指标集；对 i e ，c ( 石) 0 称为不等式约束，门尔为不等式约束指标集 ( 一) 最优化问题的简单分类 常用的最优化问题的分类有一下两种： t 根据可行域划分 4 中国石油大学( 华东) 硕士论文第1 章绪论 若q = r ”，即工是自由变量，则( 1 2 1 ) 称为无约束优化 问题；否则，qcr ”称为约束优化问题这两类优化问题并不 是严格对立的，它们之间可以进行转化 2 根据函数的性质划分 若目标函数及约束函数都是线性的，称( 1 2 1 ) 为线性规划问 题；若目标函数与约束函数中至少有一个函数是非线性的，那 么称( 1 2 1 ) 为非线性规划问题，进一步，若目标函数是二次函 数，约束是线性的，称( 1 2 1 ) 为二次规划问题；若目标函数是 凸函数，等式约束是线性的，不等式约束是凹函数( 可行域q 为凸集) ，称( 1 2 1 ) 为凸规划问题有时将目标函数是凸函数， 可行域是非空闭凸集的最优化问题也称为凸规划问题 ( 二) 非线性规划问题解的概念 对于非线性规划问题( 1 2 1 ) ，我们给出( 1 2 1 ) 的解的定义 ( 1 ) 称x q 为( 1 2 1 ) 的可行解，若x q ( 2 ) 称x eq 为( 1 2 1 ) 的整体最优解( 整体最小值点) ，若对任意 x q ，有， ) ，( 功，其对应的目标函数值称为最优值( 最小值) ； 称x q 为( 1 2 1 ) 的严格整体最优解，若对任意x q ，x x 有 f ( x ) 0 ，使得对任意x l v ( x + ，j ) n q ，有f ( x ) ，( 力； 称x q 为( 1 2 1 ) 的严格局部最优解，若存在j 点的一个邻域 5 中国石油大学( 华东) 硕士论文第l 章绪论 n ( x + ，o 3 ，使得对任意工n ( x ，万) n q ，x x ，有f ( x ) ，( x ) 除非特别说明，最优化问题的( 整体或局部) 最优解就是指( 整 体或局部) 最小值解需要说明的是，即使对一个任意阶连续可微的 函数，最小值点和最小值的存在并不总是一致的也就是说，存在任 意阶连续可微的函数有最小值但不一定有最小值点 ( 4 ) 稳定点 对于一个最优化问题，求解和验证整体最优解是一件非常棘手的 事情，因此人们寄希望于求得局部最优解对于局部最优解，人们又 借用下面的最优性条件来讨论为此，我们先给出( 1 2 1 ) 的一个具体 的表现形式 m i n ，( 力 j j q ( 功= 0 ，i 占 ( 1 2 2 ) q ( 功0 ，i i 其中厂：r ”斗r ，c f ：r ”寸r ( f 占ui ) 均为连续可微函数 x + e q 称为( 1 2 2 ) 或( 1 2 1 ) 的稳定点，若任意的x q 成立 ( v f ( x ) ，x 一，) 0 显然，若q = r ”，则稳定点条件变为可y ( x + ) = 0 对于无约束优化问题，稳定点可能是局部极大值点也有可能是局 部极小值点，还有可能既不是局部极大值点也不是局部极小值点，称 满足最后一种情况的稳定点为无约束优化问题的鞍点 ( 一) 无约束优化问题的最优性条件 2 1 下面是无约束最优化问题 6 中国石油大学( 华东) 硕士论文第1 章绪论 卿厂( x ) ( 1 - 2 3 ) 的最优性条件其中，：r ”一r 为连续可微函数 定理1 2 1( 一阶必要条件)若x 是( 1 2 3 ) 的局部最小值点， 则、盯( x ) = 0 定理1 2 2( 二阶必要条件)若x 是( 1 2 3 ) 的局部最优解， f ( x ) 在x 点附近二阶连续可微则可y ( x + ) = 0 ，v 2 f ( x 。) 半正定 定理l2 3 ( 二阶充分条件)若v f ( x + ) = 0 ，且v 2 f ( x ) 正定 则x 是( 1 2 3 ) 的严格局部最优解 定理1 2 4 对( 1 2 3 ) ，若目标函数，是连续可微的凸函数，则 整体最优解，局部最优解和稳定点是等价的 1 3 求解非线性规划问题的线搜索方法算法 对非线性规划问题( 1 2 1 ) ，一般没有特别有效的方法得到最优 解，人们普遍采用迭代的方法求解，首先选择一个初始点，利用当前 迭代点的或已产生的迭代点的信息，如目标函数与约束函数的一阶导 数( 梯度) 与二阶导数( h e s s i a n 矩阵) ，产生下一个迭代点，一步 一步逼近最优解，进而得到一个迭代点列这样便构成求解( 1 2 1 ) 的迭代算法注意，并不是所有的算法产生的迭代点列对应的目标函 数值数列都是单调不增的对于约束优化问题，包括初始点在内，迭 代点未必都是可行的那么，在具体的算法中，如何由当前迭代点产 生下一个迭代点? 一般地，人们采用两种策略来实现：线搜索方法和 信赖域方法 7 中国石油大学( 华东) 硕士论文第l 章绪论 ( 一) 线搜索方法的算法框架 算法1 3 1 s t e p l 取初始点，令k = 0 ； s t e p 2 验证最优性条件( 终止规则) ； s t e p 3 求以点的搜索方向d i ； s t e p 4 求迭代步长； s t e p 5 产生下一迭代点x m = x t + 吼以，k = k + l ，转s t e p 2 由此可以看出，算法的关键在于搜索方向和迭代步长的选取搜 索方向喀一般取为下降方向，步长吼则由精确或非精确搜索规则确 定 ( 二) 下降算法 定义1 3 1 若向量以r ”满足d k 7 可( 以) o ，那么d k 就称为 厂 ) 在坼点的下降方向对厂( 石) 在砟的下降方向d k ，取充分小的正 数口，有 f ( x t + o d d = f ( x k ) + a v f ( x k ) 7 d k + d ) 0 为参数，幺v f ( x i ) 和s 的夹角 ( b ) ：误差项w 。满足 其中以满足 1 1 w 。忙儿( q + p l l v f ( x 冲 庀 o ，k = l 2 i = l 其中p , q o 为常数。由式( 3 ) 仿文献 1 3 ，1 4 g 取 区【曼。( ) ，t ( ) 】， 其中 壁。( ) = 两而丽1 下i l v f ( x r , l l ， 确) = 两丽1 可i l v f ( x , ) l l ( c ) ：以为步长，由下列规则确定： 如果夥( 以) 7 仅+ w 。) o ，取五= 九，否则，取以满足： ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ，( 以+ 以( + w i ) ) f ( x i ) + 以1 v ，( ) 7 ( + ) ，( 9 a ) 1 4 二-喇 h 靠 飞及 啪肥啊懒 h 二-嘲v 。q 厂怿 何协 w 啦夥 中国石油大学( 华东) 硕十论文第2 章带误差项的记忆梯度算法 且以歹。或者以r ：疋 0 ，( 9 b ) 其中正满足： f ( x i + 疋( 墨i + r i ) ) 厂( 以) + 2 , z k v f ( x t ) r ( s + w i ) ，( 9 c ) 这里l ，2 ( o ，1 ) 且朋s 2 ，l 2 0 为常数 注求解无约束优化问题( p ) 的算法，包括拟- n e w t o n 算法、有 限记忆b f g s 算法，其搜索方向s 。可表示为 b k sk2 一g k 其中毋是一个正定矩阵满删2 - n e w t o n 方程 e d k l = y 其中矾一l = 矗- - x ，y k l = g i - g ，因此 以7 y k 一= 1 ( 色) - 。g 女】7 y h = 一g k r ( 毋) y k l = 一7 以一1 再有s i = 一g t + 尻s 及上式得 风一= 盟丝宇呈 rrt j t iy k i 结合以上参数，在( m g m e ) 中可选取参数展为： 区= a r g m i n i p 一履咖一i ：卜星。( ) ，瓦( ) 】j ， 从而得到结合拟- n e w t o n 方程带误差项的记忆梯度法记为q g m e 引理2 2 1 若坼不是问题( p ) 的稳定点，屏满足( 6 8 ) ，则有 中国石油大学( 华东) 硕士论文第2 章带误差项的记忆梯度算法 恢0 圳v 瓴，其中c l2 l + i i 证明 由吼的定义易证【】 引理2 2 2 x k 不是问题( p ) 的稳定点，绞满足( 6 8 ) ，则有 v ( x d 7 以一吒l l v f c x , ) 1 1 2 ，其中c 2 = 而a 证明分两种情况( a ) 、证明： ( a )k = 1 ，显然成立 ( b )k 2 ，由吼的定义和式( 3 ) 知 v f ( x d 7 - - - - 1 i v j 0 ，集合，：n i ，其中 1 6 中国石油大学( 华东) 硕士论文第2 章带误差项的记忆梯度算法 n = l 2 ) 引理2 2 - 3 算法中，假设玩满足( 6 8 ) ，满足( 4 ) 、( 5 ) ，则 当i i 充分大时有i i v ( x ) 1 i 形t ，其中盯 0 为常数，进而 。l i 口夥( 以) = 0 e ， 瑚 证明v k i ，由，的定义知 一v f ( x i ) 7 8 t v f ( x i ) 7 w t ( 1 0 ) 由引理2 2 2 知 一v f ( x 。) 7 s 。c ：忭：“x 。) 1 1 2 ( 1 1 ) 由式( 4 ) 知 v f ( x 。) 7 w 。0 盯( 屯) 1 1 1 1 w 。0 0 ，当七，充分大时有0 夥( 以) 0 7 i 再由式( 5 ) 即得。u 皿可丁( 以) = 0 口 t e j 1 7 中国石油大学( 华东) 硕士论文第2 章带误差项的记忆梯鏖箩法 2 3 全局收敛性 定理2 3 1 设k ) 是由算法产生的无穷点列，扩( 坼) ) 存在有限 极限，如果存在一个开凸集d ) k k 。使得w ( 力在d 上一致连续， 则! 一a m v f ( x d = 0 证明 y ；鼓l i r a f ( x 。) = f 以下用反证法证明! i r a v f ( x t ) = 0 - - + r or一 事实上，若否，则存在无穷指标集k 。c j 和氏 0 使得 l 阿( 州s 。，v 七k o ( 1 3 ) 由k o = ( j n x o ) u n x o ) 知，当露j n k o 时，由引理2 2 3 知 。低l i m j j v ，( 叫i s m ! 恐。矾= o ， 故f r 、k 。最多只有无限个元素，不妨设f n x o = ，故k o c j v k k 。c j ，由引理2 2 2 、式( 5 ) 知t 当k ( k k o ) 充分大时有 w ( x 。) 7 ( s 。+ w ；) c ：忭丁( 书；) 4 2 一忭丁o 。) 4 ，。( , 1 + d l v y ( x 。) l i ) = o ：一r 。p ) u v f ( x 胛一r , q l v f ( x 。) 0 2 【( c 2 - 7 。p ) 岛- y 。q l f f ( x 。) ( 1 4 ) 由引理2 2 1 、式( 5 ) 得 i i s 。+ ，。0 c 10 夥( 黾川+ 以( g + 刊f 耵( 坼) 肛 s 0 。+ ( r , q ) e o + ，。力- l l v y ( x , ) 1 1 ( 1 5 ) 由式( 9 a ) 、( 1 4 ) 得 中国石油大学( 华东) 硕十论文第2 章带误差项的记忆梯度算法 f ( x i ) 一f ( x “i ) 一u 1 以v f ( 工t ) 7 ( s t + w k ) 由式( 1 3 ) 、( 1 6 ) 得 朋以【( 吒- y 。p ) 8 0 一，。g 】- i l v i ( x 。) ( 1 6 ) l i m 训w ( 圳i _ o ( 1 7 ) f ( x 。) 一f ( x k 。) - a 以岛【( c 2 一，。p ) e o 一，。g 】， 由式( 1 5 ) 、( 1 7 ) 得 。0 粤k 以5 0 。l i m 一2 k 恢+ w t 峨l i m 舢以( q + y k q ( 6 0 + y t p ) 桫( 圳= o 因此 ( 18 ) 。昱盟。训+ t l l = o ( 1 9 ) 由式( 1 8 ) 知，当七( 七e k 。) 充分大时有以 歹。，从而 歹：正，而t 满足( 9 c ) ，设+ = 以+ 疋( + ) ，由式( 1 8 ) 、( 1 9 ) 及以歹：正知， ( k k 。) 充分大时有 。l i m ，。一a = 0 l i m 五；l l & + w k l k - - 。o = o 拓k i e k o ， 。 因而 。l i m 。1 1 x ：+ 。一瓢0 = 。令p ：= z 可f ( 丽x ；+ 五1 ) i - - i f ( 干x k 丽) ，k ek o , 由式( 9 c ) 得 1 9 中国石油大学( 华东) 硕士论文第2 章带误差项的记忆梯度算法 p ： 2 1 ( 2 0 ) 由式( 5 ) 、( 1 3 ) 、( 1 4 ) 、( 1 5 ) 得 l i m s u p l p ；+ 盟i 划焉兽蹬岩一，i ：l i i i l s u p l 盟盥望弩监! 世! l t 幽，i lv 【j ( s k + )i ， iivy(g,)一1咿(xi)(q+，jp+7iq80)li m s u p 些 ：! 塑坐! ! 型! = 0 其中= 以+ 以( + l x k ) ，0 0 k 1 ( 2 1 ) 由式( 2 1 ) 知废= i 此与( 2 0 ) 矛盾故! 受l l v f ( x , ) l l = o f 3 定理2 3 2 设 t 是由算法产生的无穷点列，如果存在一个开凸 集d 己k 。 ，使得可( 功在d 上一致连续，则或者j i i i l 厂( 以) = 或者l i m 彤( 以) = 0 证明当k ，n r 充分大时，由引理2 2 1 、引理2 2 3 、式( 4 ) 、 ( 5 ) 知 ，。0 + w 。0 几k ，i i 可k ) + 以( p 0 w g 。) 】l + g ) 】 力陆l + o p y i + g 】( 2 2 ) 由式( 2 2 ) 及中值定理得 中国石油大学( 华东) 硕十论文第2 章带误差项的记忆梯度算法 f ( x 。) 一厂( ) = ，t ( 百y ( h + 吼，i ( + w 1 ) ) 一1 叮( x i ) ) 7 ( s i + w k ) + y k v f ( x k ) ，( 5 t + w d 以f p 。+ w 。q 1 盯( 以+ 幺，。( s 。+ w 。) ) 一v t ( x a i + f t ( x 。) i i ) s 霹( 贸l + 叩以+ 9 ) l l v f x i + a k r k ( s i + 毗) ) 一w ( 以) 忡吼) ( 2 3 ) 其中0 0 使得 f ( x k + 1 ) 一f ( x ) - 0 盯2 ，； ( 2 5 ) 取c r 3 = m a x p l ，仃2 ) ，由式( 2 4 ) 、( 2 5 ) 易得 ，( + 。) 一f ( x k ) o r 3 力，v k n ( 2 6 ) 则当k 充分大时有f ( x k + 1 ) + 瓦+ s 厂( t ) + 瓦 由式( 2 6 ) 知，当k 充分大时，厂( 也) + 乏 单调下降，再由 瓦_ o ( 七一o o ) 失d ，或者；i m 八以) = ，或者沙( 以) 存在有限极限， 此时由定理2 3 1 知l i m 可y ( 以) = 0 【】 f 呻 2 4 数值实验 本节选择了 2 8 中的几个算例，在p i i i 9 3 3 机器上对本章算法 2 l 中国石油大学( 华东) 硕士论文第2 章带误差项的记忆梯度算法 进行数值实验，利用m a r l a b 编制程序并与f r 、p r 、h s 共轭梯度法进 行比较，计算结果表明新算法是有效的 取力= - 石i ，蝴= 0 2 5 ，p = v 2 9 ，a = 0 0 6 7 ，用i n i t k = lk = l 表示风加”黼【壁。( a ) ，厦( ) 】的迭代次数，r r 表示算法的迭代 次数，t 表示所用时间，厶表示目标函数的最优值 例2 1 厂( 功= l o ( x 1 2 一x 2 ) 2 + ( 1 一_ ) 2 + 9 ( x 4 一x 3 2 ) 2 + ( 1 一毛) 2 + i o 1 ( ( x 2 - 1 ) 2 + ( _ 一1 ) 2 ) + 1 9 8 ( x 2 - - 1 ) ( x 4 1 ) n = 4 ，初时点而= ( - 3 ，- 1 ，一3 ，一1 ) 7 ；最优点善+ = ( 1 ，1 ，l ，1 ) ；最优值 f ( x ) = 0 精度要求0 w ( ) 忙1 0 。2 ，1 0 。的计算结果见表2 1 表2 1 算法哪 i tt f 磷 f r 1 9 5 2 8 0 0 2 7 0 0 s , 0 6 0 0 0 s1 0 6 7 0 e - 0 0 5 ，i 3 7 8 5 e - 0 0 7 h s 2 4 6 ，3 8 50 1 0 0 0 s ，0 4 6 1 0 s4 6 9 8 1 e - 0 0 5 ，4 9 4 4 6 e - 0 0 7 p r8 3 9 1 0 3 6 1 0 s , 0 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 e 4 2 ，6 50 0 4 7 0 s ，0 0 3 1 0 s 2 0 0 9 2 e - 0 0 5 ，3 4 1 3 9 e - 0 0 7 q 3 m e 1 8 2 5 3 1 ，3 8 0 0 3 2 0 s ，0 0 4 6 0 s 1 4 9 2 3 e - 0 0 5 2 引3 1 e - 0 0 8 n | 2 例2 2 ( 力= 艺【( 屯，一x 2 t _ 1 2 ) 2 + ( 1 - x ：。) 2 】， 中国石油大学( 华东) 硕士论文第2 章带误差项的记忆梯度算法 n = 1 2 0 ，初时点而= ( - 1 2 ，1 ，- 1 2 ，1 ) 7 ；最优点x + = ( 1 ，1 ，1 ) ；最 优值厂( 工) = 0 精度要求可丁( 以1 0 - 2 ，1 0 1 3 的计算结果见表2 2 表2 2 算法 烈n i t t 叩t 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 s 5 2 7 9 0 1l o o s ，0 1 4 1 0 s5 9 2 7 2 e - 0 0 5 9 6 3 9 4 e - 0 0 7 p r 1 1 ， 2 20 0 5 0 0 s 0 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 e1 6 2 0 0 0 4 7 0 s , o 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 e5 ，1 08 ， 1 4 0 0 4 7 0 s ，0 0 4 7 0 s1 8 3 7 5 e - 0 0 5 ，1 3 5 0 3 e - 0 0 7 例2 3 ，( ：舞以，- + l 骶。) ：+ 5 ( - 一) ：+ 阮：一2 h 。) ： + i o ( x 4 h x 4 t ) 4 】 n ：6 0 ，初时点而= ( 3 ，一1 ，0 ，3 ，3 ，一1 ，0 ，3 ) 7 ；最优点x + = ( 0 ，0 ，o ) ； 精度要求0 v 丁( ) 忙1 0 。2 ，1 0 4 的计算结果见表2 3 表2 3 算法n q i t i t t j 。 f r 4 7 ，5 l 0 11 0 0 s ，