（计算数学专业论文）非线性最优化的几种算法研究.pdf

非线性最优化的几种算法研究 郑艳梅( 计算数学) 指导教师：孙清滢教授 摘要 对求解无约束优化问题的共轭梯度法中的方向参数给定了一种新的 区间取法以保证搜索方向是目标函数的充分下降方向，在此基础上提出 了一种新的记忆梯度算法，在目标函数的梯度一致连续的条件下证明了 算法的全局收敛性，数值试验表明新算法是有效的然后将该算法应用于 以下两个方面的研究：( i ) 在将互补问题转化为无约束优化问题的基础 上，应用记忆梯度算法求解之并证明了算法的收敛性和线性收敛速度； ( i i ) 在通过广义d - g a p 函数将半定互补问题转化为无约束优化问题的基 础上，应用记忆梯度算法求解之并证明了算法的收敛性进一步，增加 记忆项的项数，将记忆梯度算法推广到三项记忆梯度算法，在算法的步 长选取上提出了一种新的非单调线搜索技巧，该线搜索在每一迭代步内 得到较大的步长，有利于算法的快速收敛，在目标函数的梯度一致连续 的条件下证明了算法的全局收敛性，并在一定条件下讨论了算法线性收 敛速度最后，应用三项记忆梯度算法求解信赖域子问题，该方法保证试 探步的充分下降性，并结合线搜索技巧，即在试探步不成功时，不重解 信赖域子问题，而采用非精确a r m i j o 线搜索获得下一迭代点，从而减少 了计算量在此基础上，提出了一种带线搜索的信赖域算法，在一定的 条件下证明了算法的全局收敛性数值试验表明新算法是有效的 关键词：记忆梯度法，半定互补问题，非单调线搜索，信赖域子问题，非精确a r m i j o 线搜索 s o m e a l g o t i t h m si nn 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 z h e n g y a n - m e i ( 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 d 时p r o f e s s o rs u nq i n g - y i n g a b s t r a c t an e wa s s u m p t i o ni sg i v e no nt h es c a l a ro f c o n j u g a t eg r a d i e n tm e t h o dt o e n s i l r et h a tt h ed i i e c t i o ni sas u f f i c i e n td e s c e n td i r e c t i o nan e wc l a s so f m e m o r yg r a d i e n tm e t h o df o ru n c 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 da n d 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 wa l g o r i t h ma r ed i s c u s s e do n c o n d i t i o nt h a tt h eg r a d i e n to ft h eo b j e c t i v ef u n c t i o ni su n i f o r m l yc o n t i n u o u s n u m 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 t h mi se f f i c i e n t a n dt h e nt h e a l g o r i t h mi sa p p l i e dt ot h ef o l l o w i n ga 呵 e c t s ：( i ) b a s e do nar e f o r m u l a t i o no f t h ec o m p l e m e n t a r i t yp r o b l e ma su n c o n s t r a i n e do p t i m i z a t i o n ，t h em e m o r y g r a d i e n tm e t h o di su s e df o rs o l v i n gt h ec o m p l e m e n t a r i t yp r o b l e m t h eg i o b a l c o n v e r g e n c ea n dt h el i n e a rc o n v e r g e n c eo ft h en e wa l g o r i t h ma r es h o w n n u m 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 t h mi se f f i c i e n t ( i i ) b a s e do na m f o r m u l a t i o no f t h es e m i - d e f i n i t ec o m p l e m e n t a r i 锣p r o b l e ma su n c o n s t r a i n e d o p t i m i z a t i o nb yt h eg e n e r a l i z e dd - g a pm e r i tf u n c t i o n , t h em e m o r yg r a d i e n t a l g o r i t h mi su s e df o rs o l v i n gt h es e m i - d e f i n i t ec o m p l e m e n t a r i t yp r o b l e m , w h i c hi sp r o v e dg l o b a l l yc o n v e r g e n t f u r t h e r m o r e ，b ya d d i n gt h en u m b e r so f m e m o r yt e r m , t h em e m o r yg r a d i e n ta l g o r i t h mi sg e n e r a l i z e dt ot h et h r e e - t e r r a m e m o r yg r a d i e n tm e t h o d o nc h o o s i n gt h es t e ps i z eo ft h ea l g o f i t h m ，an e w n o n - m o n o t o n el i n e - s e a r c hr u l ei sp r o p o s e dw h i c hc 铋g e tal a r g e rs t e ps i z ea t e a c hi t e r a t i o na n db eb e n e f i tt ot h ef a s tc o n v e r g e n c eo ft h ea l g o r i t h m t h e i i i g l o b a lc o n v e r g e n c ep r o p e r t yo ft h en e wa l g o r i t h mi sd i s c u s s e x io nc o n d i t i o n t h a tt h eg r a d i e n to ft h eo b j e c t i v ef u n c t i o ni su n i f o r m l yc o n t i n u o u sa n dt h e l i n e a rc o n v a g e n c ei sa l s od i u s s e du n d e rc 埘t a i nc o n d i t i o n s n u m e r i c a l r e s u l t ss h o wt h a tt h en e wa l g o r i t h mi se f f i c i e n t f i n a l l y ，t h en e wt h r e c - t c r t l l m e m o r yg r a d i e n tm e t h o di su s e dt os o l v et h et r u s tr e g i o ns u b - p r o b l e m , w h i c h e i i s u r e st h et r i a ls t e pi ss u f f i c i e n td e s c e n t an e wa l g o r i t h mf o ru n c o n s t r a i n e d o p f m l i z a t i o nt h a te m p l o y sb o t ht r u s tr e g i o na n dl i n e - s e a r c hi sp r o p o s e d , a n d t h ea l g o r i t h md o e sn o tr e s o l v et h es u b - p r o b l e mi ft h et r i a ls t e pr e s u l t si na n i n c r e a s ei nt h eo b j e c t i v ef u n c t i o n , b u tp e r f o r m san e wi n e x a c ta r m i j ol i n e s e a r c ht oo b t a i nt h en e x ti t e r a t i o np o i n t t h ec o n v e r g e n c ep r o p e r t yo ft h e a l g o r i t h mi sp r o v e du n d e r c e r t a i nc o n d i t i o n s n u m e r i c a lr e s u l t ss h o wt h a tt h e n e w a l g o r i t h mi se f f i c i e n t k e yw o r d s ：m e m o r yo r a d i e r am e t h o c ks e m i - d e f i n i t ec o m p l e m e n t a r i t yp r o b l e m , n o n - m o n o t o n el i n e s c a r c l l ，s u b p r o b l e mo ft r u s tr e g i o na l g o r i t h m , i n e x a c ta r m i j o l ：, i n e - s e a r c h 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国 石油大学或其它教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 签名：叠整堑参一年广a 渤b 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅：学 校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名：谭整蕴乒芦x - 月，6 日一 导师签名：兰盘丑鱼 垒弦印年r 月易日一 中国石油大学( 华东) 硕士论文第1 章前言 第1 章前言 最优化问题是在多种( 有限或无限种) 决策中挑选最好决策的问题，它 广泛应用于农业、国防、交通、金融、能源、通信等许多领域，如在资 源利用、结构优化、调度管理、后勤供应等许多问题中产生了巨大的经 济效益和社会效应优化在结构力学、生命科学、环境科学等其他科学研 究领域和方向也有广泛应用 非线性最优化是在二十世纪5 0 年代发展起来的，主要讨论非线性决 策问题的最佳选择之特性，构造寻求最优解的计算方法，研究这些计算 方法的理论性质及实际计算表现随着电子计算机的发展和应用，非线 性最优化理论和方法有了很大发展，目前，已成为一门十分活跃的学科 许多急需解决的、对国民经济有重大影响的大规模复杂科学和工程问题 本质上都是优化问题它们有的规模十分巨大( 维数达上百万，如大气科 学中的四维同化问题) ，有的规模并不十分巨大却是非常复杂的优化问题 ( 如化工工业中的多相流计算问题) 因此，研究高效的优化计算方法不仅 具有重要的科学意义，而且具有广泛的应用前景，将对促进优化方法在 国民生产等方面的应用起到重大作用 本文主要研究求解无约束优化问题的记忆梯度方法及其应用全文 共分七章，第一章是前言，简单介绍了记忆梯度算法、互补问题、半定 互补问题和信赖域算法的发展；第二章到第四章主要对求解无约束优化 问题的记忆梯度算法及其在互补、半定互补问题中的应用进行了讨论； 第五章到第六章主要对三项记忆梯度算法及其在信赖域子问题求解中的 应用进行了讨论第七章是结论 1 1 记忆梯度算法简介 考虑无约束优化问题 1 中国石油大学( 华东) 硕士论文 第1 章前言 凹厂( x ) 其中八力：掣专r 是一阶连续可微函数，记反= v f ( x d 共轭梯度算法是求解问题( p ) 的一种有效的方法，其迭代公式为 气“= x k + 坼喀， ( 1 1 ) 4 = 巴触；是 ( 1 2 ) 其中，吒是线搜索的步长，可通过某种策略得到；孱是一参数，不同的 参数对应不同的共轭梯度算法如 展“= 黔= 皆胪= 丽g k r ( g k - g k - 1 ) 分别对应f r ( f l e t c h e r - r e e v e s ) 、p r ( p o l a k - r i b i e r e ) 、h s ( h e s t e n e s - s t i e f e l ) 共轭梯度法f r 算法具有较好的收敛性质，而后两者的数值表现差不多， 都优于f r 算法 记忆梯度算法是共轭梯度算法的一种变形和改进，具有更快的收敛 速度m i e l e 久【1 】介绍了记忆梯度算法，基本公式为 协0 3 0 ( k ) , 黧m i n f ( x 奠, 蝎c o o v f 忙( k x , ) “+ c o , a x m ， 1q 耻卜啪 一 - 一) u 。 其中，q 钟= o ，觇- l = 气- x , - l 七1 随后，文献 2 4 1 利用记忆梯度算法的基本思想，增加记忆项的项数， 引入超记忆梯度算法，由于这类算法在迭代中较多的利用了目标函数已 得到的某些信息，因而具有比记忆梯度算法更快的收敛速度，大量的数 值例子证明了这一点 2 中国石油大学( 华东) 硕士论文第1 章前言 鼽屹= 肛1 麓川，2 ， 可见，记忆梯度算法在每一次迭代中都需要作一次二维搜索，而超 记忆梯度算法在每一次迭代中需要作一次r + l 维搜索，这一点很不理想 为此，很多文献对算法进行了改进 5 6 】赵庆祯【5 】首先将超记忆梯度法 的多维精确搜索改为一维非精确搜索，并证明了改进算法具有疗步超线 性收敛速度，从而使超记忆梯度算法更具实用性 超记忆梯度算法的本质在于用前几次迭代方向去修正当前点的负梯 度，得到下降的迭代方向，即 反= 一v f ( 坼) + 展。以一1 + 孱2 以一2 + + 成，以_ ， ( 1 5 ) 其中，d k 为当前点以处的下降方向，本质上是屏，l ，展，的取法时贞军 7 8 对无约束优化问题在，= l 时，提出了尻为区间取值的超记忆梯度 算法，并在水平集有界的条件下证明了算法的收敛性质；孙清滢【9 】给出 共轭梯度方向( 1 2 ) 的参数反的取值范围，建立了求解问题口) 的新三项共 轭梯度算法，在去掉水平集有界和广义a r m i j o 搜索下讨论了算法的全局 收敛性；随后，孙清滢 1 2 1 又建立了求解问题的三项记忆梯度算法， 并在非单调线搜索下讨论了算法的全局收敛性；l g d p p o 等【1 3 】首先对牛 顿法提出了一个非单调线搜索框架，z h a n gh c 【1 4 改进了传统非单调线 搜索参考值的选取，提出了一种新的选取方法，克服了传统非单调线搜 3 中国石油大学( 华东) 硕士论文第1 章前言 索的缺点，并在一定条件下证明了算法的全局收敛性及震线性收敛性； s h iz j 1 5 提出了一种新的非精确线搜索准则，该线搜索在每一步迭代 时能得到较大的步长，包含a r m i j o 线搜索作为其特例，并讨论了下降算 法的全局收敛性及线性收敛速率 1 2 互补问题与半定互补问题算法简介 1 2 1 互补问题算法简介 标准形式的互补问题：给定向量函数f ( d ：r ”- - - h r ，求一向量 工毫掣满足 ，f ( x ) = o ，工o ，f o ) o ( 1 6 ) 当，( x ) 是线性函数( 令f ( 力= m x + q ，m 置”，q r ”) 时，称( 1 6 ) 为线性 互补问题，记为l c p ( m , q ) ；否则，称( 1 6 ) 为非线性互补问题，记为n c p ( f ) 称函数中：r 2 寸r 是一个n c p 函数，如果它满足以下互补条件： o ( 口，6 ) = o a o ，b 0 ，a b = 0 ( 1 7 ) 对互补问题的研究，特别是算法方面的研究至今未衰k a n z o w 1 9 按照如 下方法给出了一种价值函数： 设。是一个n c p 函数，f ：r ”专r ”，设f ：r ”- - h 卫表示f 的第i 个 分量，定义壬，。：r ”- - h r 为 甲，( 功= m ( 葺，只0 ) ) ，f ，= 1 ，2 ，” ， ( 1 8 ) 同时，定义甲：r ”一r 为 甲( 功= 甲，( j ) ( 1 9 ) i t l 函数￥。f j 和函数甲要依靠n c p 函数的选择 4 中国石油大学( 华东) 硕士论文第1 章前言 在文献 1 9 1 中，k a n z o w 得到如下定理： 定理1 1 假设互补问题( 1 6 ) 是可解的，设m 是n c p 函数，且对所有 的( 口，6 ) 7 r 2 都有m ( 口，6 ) 0 ，设一，f i 和、壬，分别由式( 1 8 ) ，式( 1 9 ) 所 定义，则有x + 是甲的全局最小解当且仅当x 是互补问题( 1 6 ) 的解 定理1 2 设f ：矗”专r ”是连续可微的，且对于v x r ”，j a c o b i a n 矩 阵v f ( x ) 是正定的假设互补问题( 1 6 ) 是可解的，设巾是个连续可微的 n c p 函数，且对所有的( 口，6 ) 7 r 2 都有m ( 口，0 ，假设还满足以下 条件 ( i ) 西( 口，6 ) = 0 当且仅当v o ( 毋6 ) = 0 ； ( i i ) 娑( 吼6 ) 娑( 以6 ) 2o ，v ( 以6 ) 7 r 2 o a 则x 是甲的一个稳定点当且仅当x 是互补问题( 1 6 ) 的一个解 由定理1 1 可知，互补问题可以等价地转化为如下无约束极小化问 题 ( p ) 墨甲( 石) 而且可以证明在合适的条件下，无约束目标函数的任一稳定点是非线性 互补问题的一个解 屈彪 3 0 1 在互补问题转化为无约束优化问题的基础上，提出了一种求 解标准形式的互补问题的混合梯度算法，并在较弱的条件下证明了算法 的全局收敛性 1 2 2 半定互补问题算法简介 半定线性互补问题是线性互补问题的推广，即用对称半正定实锥代 替原来的非负实向量锥而得到的相应问题，在工程和组合优化中具有重 中国石油大学( 华东) 硕士论文第1 章前言 要的应用近年来，利用价值函数求解线性互补问题、非线性互补问题以 及由此发展而来的求解方法，如基于f i s h e r - b u r m c i s t e r 价值函数的牛顿 法被证明优越于内点算法t s e n gp a u l 2 4 】最早用此类方法来求解半定 互补问题 下面给出半定互补问题的描述： 令z 表示胛甩块对角实矩阵组成的空间( 有脚个固定块，每块大小分 别是瑰，嘞，) ，于是z 对矩阵加法、乘法、转置、求逆运算是封闭的 定义z 的内积和范数： x ，) ，) 伊 x 7 y ，4 x - 耳习 其中，x , y z ，州】表示矩阵的迹，表示x 的f r o b e n i u s 范数 所谓半定互补问题( s d c p ) 就是：寻找矩阵芹s 使得 ( s d c p ) x 墨，f ( 力墨，( f ( 力，x ) = o ( 1 1 0 ) 其中，s 是y x 实对称矩阵组成的子空间，墨( 足+ ) 表示s 中半正定阵( i e 定阵) 组成的凸锥，f 是s s 的映射易知若s 是由对角阵组成的空间。 该问题就退化为非线性互补问题，因此可以将求解非线性互补问题的方 法推广到半定互补问题 近年来，已有学者提出了将互补问题转化为无约束优化问题的方 法t s e n g 2 4 i 正明了下列函数是半定互补问题的价值函数，并证明了它们 有许多好的性质，包括可微性，稳定点为全局点的条件及误差界成立的 条件： 1 g a p 函数： ，( 力= f 哗 0 ， 厶( 曲= m ，啦a x ( ( x , f ( x ) 一”一去护( 曲一卅2 ，t j +z f z 3 隐l a g r 缸西a i l 函数： f ( x , a o = x f ( 卅去( i ( 一a f ( x ) + 习+ 1 2 一删2 + l l ( 吲+ 瞰) ) + 0 2 一u r ( x 如 其中范数取为2 范数f t ( z ) + 定义为( z + ) 。= m a x z f ，0 ) ，f = 1 , 2 ，“，玎 4 f i s e h e r - b u r m e r i s t e r 函数： ( 力= 去眵，( 功l ， i 其中，函数妒：s s - - ) s 定义为0 ，b ) = ( a 2 + 6 2 ) 2 一( 口+ 6 ) p e n g 等 2 5 1 通过d g a p 函数给出了求解变分不等式的一个混合牛顿算法； y a m a s h i t a 等 2 6 1 推广了文献 2 5 1 的结果提出了广义d g a p 函数并研究了 该函数的各种性质；张立平 2 9 1 将求解变分不等式的d - g a p 函数推广到半 定互补问题，并通过此d g a p 函数将半定互补问题转化为一个无约束优 化问题 1 3 信赖域算法简介 信赖域算法是非线性优化的一类重要的数值计算算法在近二十多 年来受到了非线性优化界的高度重视，特别是近几年，一直是非线性优 化的研究热点目前信赖域算法和传统的线搜索算法并列为非线性优化 的主要算法信赖域算法的研究起始于2 0 世纪六十年代的p o w e l l ，其基本 技巧在一定意义下等价于著名的求解非线性最d r - - 乘问题的l e v e n b e r g - m a r q u a r d t 算法由于信赖域算法的每一次迭代都要解信赖域子问题，所 以找到有效的方法解信赖域子问题是非常重要的 考虑无约束优化问题 7 中国石油大学( 华东) 硕士论文第1 章前言 磐，( 通常采用的信赖域子问题是基于二次模型的，即 m i n q a j ) ；瓯7 尹1 即 ( 1 1 1 ) j 上i is 临a k 其中既是目标函数在当前点的梯度，毋是目标函数的h e s s e 阵或其近似， a 。0 是信赖域半径 求解子问题得到试验步，然后令p r e s k = q k ( o ) - - q k ( s k ) 为预测下降 量，令a r e s 。= 厂( 坼) 一八坼+ ) 为实际下降量，再定义预测下降量和实 际下降量的比率为吒= a r e s _ _ _ 丝k ，根据这一比率来决定是否接受试验步以及 f r e s 如何调节信赖域半径 目前已有一些算法可以直接计算信赖域子问题的近似解，主要有下 面三种方法：折线法、2 维搜索法以及截断共轭梯度法折线法是由p o w e l l 提出的，这种方法要求如果牛顿步在信赖域内，则取牛顿步；否则，沿 着最速下降方向找到c a u c h y 点，使其能最小化目标函数如果c a u c h y 点在 信赖域外，则选择缩小的c a u e h y 步作为近似解，当c a u c h y 点在信赖域内 部时，取连接c a u c h y 点和牛顿点的直线与信赖域边界的交点作为近似解 连接原点、c a u c h y 点和牛顿点的折线看起来就像d o g - l e g ，因此这种方法 称为d o g - l e g 法 2 维搜索法是在由最速下降方向和牛顿步生成的子空间内最小化目 标函数这种方法首先由s h u l t z ，s c h n a b e l 和b y r d 3 4 提出，它可以被看作 不定的折线步法另一方面，折线步是2 维子空间中b d = - g 的截共轭梯 8 中国石油大学( 华东) 硕士论文 第1 章前言 度解 截共轭梯度法就是简单地用标准的共轭梯度法去最小化子问题的目 标函数只要迭代点在信赖域内部，该方法就可看作标准的共轭梯度法 若共轭梯度法在信赖域范围内的某一点终止，该点就是目标函数的全局 最优解，否则，在信赖域边界上得到截步该方法的一个优点是子问题 的解有充分的下降性 s t e i h a u g ( 1 9 8 3 ) 3 2 提出用预处理共轭梯度法( 下简称p c g ) 求解信赖 域子问题他设计了三个停止准则，即除了正常情况下，按照p c g 方法得 到搜索方向( 或搜索点) 外，当搜索方向以在信赖域外或乱是模型的 h e s s i a n 负曲率方向时，都要求新的解点直接在信赖域边界上，即求口 0 使得慨+ 呶4 = a 。，并令& 。= + 峨作为下一次子问题的搜索方向 类似于通常的信赖域方法，对于成功迭代，s t e i h a u g 方法接受子问题的解 作为下一次迭代方向，对于不成功迭代，令x k + 。= x k ，丢掉了吼所含的 有用信息对于某些问题，如果频繁地令以。= 以，便大大减弱了方法的 效率为了克服这一问题，后六生等 3 7 】提出了一种求解信赖域子问题的 三项预处理共轭梯度法，对于不成功迭代，以吼+ 。为再开始方向，用三项 共轭梯度法重掰计算，得到了较好的数值结果，并证明了算法的全局收 敛性由于信赖域子问题的求解相对较难，因此多次求解子问题的计算量 很大为克服此困难，n o e e d a l 与y u a n 3 1 】给出了组合信赖域与线搜索技 术，即当信赖域试探步不能被接受时，不需要重新求解信赖域子问题， 利用线搜索获得下一迭代点，并证明了新算法仍能保证信赖域方法较强 的收敛性质鉴于单纯的下降算法在实际计算时不一定有好的收敛效 果，g r i p p o l 等i t 3 1 提出一类非单调牛顿算法t o i n tp h 。l 等 3 8 1 将这种非 9 中国石油大学( 华东) 硕士论文第1 章前言 单调策略应用于信赖域算法，提出非单调的信赖域算法，做了相应的收 敛性分析邓乃扬【3 9 】提出了一种具有强收敛性质的非单调信赖域算法， 随后，柯小伍等 4 0 】也提出一类非单调信赖域算法，并得到了算法的全局 收敛性 1 0 中国石油大学( 华东) 硕士论文 第2 章一种新记忆梯度算法及其全局收敛性 第2 章一种新记忆梯度算法及其全局收敛性 本章给出式( 1 2 ) 中的尻一种新的区间取法，扩大了文献【9 】中的取值 范围。得到一类新的记忆梯度算法，并在去掉迭代点列有界的条件下证 明算法在广义a r m i j o 线搜索下的全局收敛性数值试验结果表明，算法 具有一定的优越性 2 1 算法及性质 考虑问题( p ) ，为保证方向吨是目标函数的充分下降方向，假设对任 意的k 2 ，以满足 耵( 黾) 7 耵( ) q i 屈v f ( x , ) i i 0 吨。 ( 2 1 ) 其中气爿c o s e j + 0 ，o ( o ，1 ) 为常数，幺为w ( 气) 和4 一i 的夹角 式( 2 1 ) 实际上给定了尻的一个取值范围，即 屏 一瓦，瓦】， 鼽瓦= i 1 错 结合h s 共轭梯度算法，可取 展= a r g 1 i 1 1 目屏一展船i 慨卜瓦，瓦j ) ( 2 2 ) 从而得到修正h s 共轭梯度算法 注当盯( ) 和4 。的夹角c o s 吼 一i 1 时，取值范围比孙清滢【9 】中 尻的范围要广 算法2 1 求解问题t r ) 的记忆梯度算法( m c g ) s t e p l 给定初始点西，o ( o 1 ) ，占 0 ，4 = 一w 瓴) ，i ，尼 0 ， 中国石油大学( 华东) 硕士论文第2 章一种新记忆梯度算法及其全局收敛性 0 a l 1 6 a k w ( x a 7 喀( 2 5 ) 令耳“= x k + 吃，转蝴； s t e 】p 4 若i l 可趴。) 1 1 = o ，则停；否则，令d 厶= 一弓抓黾+ 。) + 展畋；其 中展满足式( 2 2 ) ；令k = k + l ，转s t e p 2 引理2 1 若而不是问题( p ) 的稳定点，则有 慨檄l + 彬( 圳| 引理2 2 若不是问题( p ) 的稳定点，则有 趴矗) 7 反一1 + - 去oi i w ( x d i l 2 证明 由算法及式( 2 1 ) ，式( 2 2 ) 得 1 2 中国石油大学( 华东) 硕士论文第2 章一种新记忆梯度算法及其全局收敛性 v f ( x d 7 矾= 一i i v f ( x d l 2 + p 。v f ( x d 7 以一， 一l i v f ( x k ) i 1 2 + l 。1 盯( _ ) 7 d ：一。l 一i i v f ( x k ) i i ：+ i c o s a , il l v f ( x , ) | | ： 刈一鼎i i v ( 洲 9 赤c o s o 。( 圳f ii + o ” 垫击l l v f ( 洲 2 2 算法的全局收敛性 设 ) 是由算法2 1 产生的点列，如果存在某一个七使得叭坼) = o ， 则黾是问题( p ) 的稳定点以下假设算法产生的点列 而 为一无穷点列， 全局收敛结果如下： 定理2 1 假设，( 力c 1 ，则 ( i ) 或者厂( 靠) 斗一，或者g 墨i n f0 w ( 以) = o ； ” ” ( i i ) 如果v f ( x ) 在r ”上一致连续，则或者厂( ) 斗一，或者 ! 鳃l l v m a l l = o - 证明由引理2 2 知，对任意k ，v f ( x d 7 或 o ，再由式( 2 3 ) 知 f ( x k + a d d 0 ，使得对v 七， 0 耵瓴) 8 岛 1 3 ( 2 6 ) 中国石油大学( 华东) 硕士论文第2 章一种新记忆梯度算法及其全局收敛性 由引理2 2 和式( 2 3 ) 得 厂( k + 瓯噍) 一f ( x d h w ( x d 7 以 一m 略1 + - - - 瓮1 1 v f ( 黾) 1 1 2 肛由2 i i v f c x ) i i i i d ti i 叫吼( 击) 2 氏i l a t t l 由式( 2 6 ) ，式( 2 7 ) 及 厂( 鼍) 单调下降且有界知， 再由x k “- x ki i - - - a ii l 喀| | 知， 吼l i a , l i 佃 1 l 也+ i x k l 吻u k v f ( x d td k 上式两边同除以得 地直通幽 鸬v f ( 耳) r 反 1 4 中国石油大学( 华东) 硕士论文第2 章一种新记忆梯度算法及其全局收敛性 令七一0 0 ，得! 鳃夥( 坼) 7 矾= o ，则由引理2 2 可得l i m i r w ( x , ) i i 2 = o 即i i 可，厂( x ) l i = 0 ，矛盾 ( i i ) 假设存在无穷子集墨c l ，2 ，3 ， a m * o 0 ，使得对坛k i ， i l w ( ) 8 岛 ( 2 9 ) 仿( i ) 的证明，由式( 2 7 ) 和式( 2 9 ) 得 。要置蜀吼。吨= o ( 2 1 0 ) 和 。熙蜀2 0 因而 i 皂而i i 矗+ l _ 磁i i _ o ( 2 1 1 ) 因此，对v 七k l ，当七充分大时 0 ，有 。燥丘+ 1 14 i i = o 成立，由t a y l o r 展式及+ 的定义知 q 。+ a ：d o f q 、= 氆0 毽一a 。 哆p ：飞 q 了d 。 由式( 2 1 0 ) ，式( 2 1 1 ) 及可y ( x ) 在r ”上一致连续知，当七一0 0 时， 反专0 ，w ( 磊) 一w ( 坼) ，则 ，( 雄+ 吼巩) 一( 矗) = w 。( 五) 7 吨+ d ( + ) 鸬吼。_ 歹) 7 4 因此， 0 川一鸬k 可瓴) 7 喀s d 嘛) 两边同除以+ 0 反令七专m 得 1 5 中国石油大学( 华东) 硕士论文第2 章一种新记忆梯度算法及其全局收敛性 l i m v f ( x j a , ；o t 娟 i i 以l i 再由引理2 1 ，引理2 2 可得 t l i m 。置i i v f ( x k ) i o - 与式( 2 9 ) 矛盾 2 3 数值试验 选择文献 9 q b 的几个算例对新算法进行数值试验，利用m a t l a b 编制 程序并与f r ，p r ，h s 共轭梯度法进行比较在以下列表中，仃表示算 法的迭代次数，n t 表示算法中履”f 吼，以】的迭代次数，t 表示计 算所用时间，表示目标函数的最优值，4 7 6 1 2 ( - 8 ) 代表4 7 6 1 2 x 1 0 4 取参数o = 0 0 3 4 ，p = 1 3 1 ，1 = o 1 ，2 = 0 6 ，占= 1 0 。 倒2 1 f ( x ) = l o ( x 1 2 - 毛) 2 + o 一焉) 2 + 9 瓴一x j 2 ) 2 + ( 1 一x 3 ) 2 + l o 1 ( ( x 2 1 ) 5 + 瓴一1 ) 2 ) + 1 9 8 ( x 2 一1 ) ( 】4 一1 ) 初始点一= ( o ，一l ，_ 3 ，一1 ) 7 ；最优点薯叫= ( 1 ，1 ，1 ，1 ) 7 ；最优值八五叫) = o 表2 1 例2 1 的计算结果 杰法n硪n 材s f 删 m c g2 32 30 0 5 0 0 1 2 3 5 l f 一7 ) f r1 4 201loo 2 7 2 4 2 ( - 7 1 p r2 800500 2 3 2 4 4 ( 一n h s2 3 0 0 5 0 01 2 3 5 1 ( 仂 , v 2 例2 2 ( 力= ( 恐，一恐h 2 ) 2 + ( 1 一而，一i ) 2 】；n = 1 2 0 1 - 1 初始点五= ( _ 1 21 ，- 1 2 ，1 ) 7 ；最优点置叫= ( 1 ，1 ，1 ) 7 ；最优值厂( x 叫) = o 1 6 中国石油大学( 华东) 硕士论文第2 章一种新记忆梯度算法及其全局收敛性 表2 - 2 例2 ，2 的计算结果 方法 nm nt s 峨 m c g 860 0 5 0 0 9 6 0 9 6 ( 9 ) f r 4 0038003 6 9 15 ( - 7 ) p r 1 901700 1 1 6 2 0 ( - 6 ) h s1 0-01 1 0 0 5 0 2 0 4 ( - 9 ) 肿 例2 3 ，= ! ! ： 。+ l o 讥) 2 + j d 铀户+ o 如罗+ 加( - ) 】；n = 6 0 ， 初始点而= 0 ，一1 ，0 3 ，3 一l ，o 3 ) 7 ；最优点h = ( o 0 ，0 ) r ；最优值u 掣) = 0 表2 - 3 例2 3 的计算结果( p = 1 3 ) 方法 i ti n i tt s m c g 3 83 60 1 7 0 01 3 7 l7 ( - 7 1 f r8 307200 1 2 1 1 5 ( - 6 ) p r 1 3 9 一1 3 7 0 0 9 s 5 9 7 ( - 6 ) h s1 0 2 一 o 7 6 0 0 1 0 3 3 4 ( - 5 ) 计算结果表明新算法较f r ，p r ，h s 共轭梯度法可在较少的迭代 次数内获得较高精度的结果，而且占机时间少，适合求解大规模优化问 题 中国石油大学( 华东) 硕士论文第3 章一类求解互补问题的新记忆梯度算法 第3 章一类求解互补问题的新记忆梯度算法 本章在互补问题转化为无约束优化问题( p ) 磐、l ，( 工) 的基础上，将第 2 章提出的记忆梯度算法用于求解互补问题，并在目标函数的梯度一致 连续的条件下证明了算法的全局收敛性，数值试验表明算法是有效的 3 1 算法及其性质 对任意的k 2 ，假设臃满足 v e ( x d 7 w 瓴) ( 1 c o s 吼l + o ) l 反w ( 黾) l 喀一，( 3 1 ) 其中以为w ( 磁) 和破一。的夹角 式( 3 1 ) 实际上给定了反的一个取值范围，即 屈卜反，压】( 3 2 ) 其中应= 蕊丽1 i f d 。- , u 算法3 1 求解问题0 e ) 的记忆梯度算法 s t e p l 给定初始点五e ，a o o ，f o ，西= 一v , e ( x j ，0 o 和一个子序列 耳 。，其中】_ c n o ，满足 1 9 中国石油大学( 华东) 硕士论文第3 章一类求解互补问题的新记忆梯度算法 l i 、”壬，( 矗) 8 毛，v 七 由引理3 1 ，z 2 1 理3 2 ，式( 3 - 3 ) 和式( 3 4 ) 得 ( 3 4 ) 甲( 赡+ a d d - w ( x d s “吒v 甲( 坼) 7 吨 s 确击。坩1 2 s 叫嘶尉a o 2 i i v q ( x t ) i i i i a t i i 确面a o ) 2 酬吼 ( 3 5 ) 由式( 3 4 ) ，式( 3 5 ) 及 甲( 而) ) 的非负性和单调下降性知 反 4 a ，。a t v q ( x d r 以， 利用中值定理，得 v w ( 磊尸 鲳w ( 稚) 7 喀 其中磊= x k + 馥m - 1 吨且以( o ，1 ) 由上述不等式得 ( 计( 磊) 一w e ( x d ) 7 破 ( 一一1 ) v 甲( x d 7 噍 ( 3 7 ) 利用c a u e h y s c h w a r z 不等式，引理3 1 ，引理3 2 ，式( 3 4 ) 及式( 3 7 ) 得 中国石油大学( 华东) 硕士论文第3 章一类求解互补问题的新记忆梯度算法 9 w ( 护w ( 排盟吲铲迎 = ；碧( 一w ( _ ) ) 7 4 0 以旷 7 而1 - h 面a o ”w ( 删20 4 i il + o ” “ ( 1 一m ) ( 向2 1 1 w e ( 以) 1 1 ( 1 - 1 1 ) 由2 毛 ( 3 8 ) 由式( 3 6 ) 得 拓墨慨一矗i = o ， ( 3 9 ) 再由v 、l ，在d 上的一致连续性可得 拓爰2 l v 、l ，( 蠡) 一v l 壬，( ) 0 = o ( 3 1 0 ) 这与式( 3 8 ) 矛盾所以假设不成立，原命题成立 3 3 线性收敛速率 引理3 3 假设甲c 2 为一致凸函数，则v k ，有 啦商岬，一百( 1 - 0 + 嵩馨卜 其中三为v - 壬，