（运筹学与控制论专业论文）一类非单调修正拟牛顿算法及其收敛性分析.pdf

硕士论文 一类非单调修正拟牛顿算法及其收敛性分析 摘要 对于无约束优化问题，拟牛顿算法是一种非常有效的算法。近几十年来，国内外 许多学者【3 7 1 1 3 1 【4 】【5 1 都致力于拟牛顿算法的研究。根据所采用的搜索准则，拟牛顿算法可 以分为单调的算法和非单调的算法。 x i a o w e i ，f e n g j i a ns u i l l 5 j 利用传统的拟牛顿方程的变形及泰勒展开式得到了一类修 正的拟牛顿方程。并利用b f g s 修正公式和w o l f 线性搜索准则得到了一类修正的拟牛 顿算法。在一定条件下证明了算法具有全局收敛性和局部超线性收敛性。l i uh a na n d s u n 9 j 于1 9 9 5 年首次将非单调搜索准则应用到拟牛顿算法中得到了非单调b f g s 算法， 在一定条件下证明了算法具有全局收敛性和局部超线性收敛性。并且数值试验表明，对 于某些函数非单调算法比单调算法更有效。 本文基于x i a o w e i ，f e n g j i a ns u n t 5 j 提出的一类带函数值信息的修正的拟牛顿方程，采 用非单调线性搜索及改进的b f g s 校正公式得到了一类非单调修正拟牛顿算法。在一定 条件下，证明了该类算法具有全局收敛性和局部超线性收敛性。最后通过数值试验，证 明了此类算法是有效的。 关键词：非单调线性搜索b f g s 方法无约束优化全局收敛局部超线性收敛 a b s t r a c t 一 堡主笙塞 a b s t r a c t u u a s i - n e w t o nm e t h o d sa r e r e g a r d e d a st h em o s t e f f i c i e n t o n e sf o rs o l v i n g 眦o n s t r a i n e dp r o b l e m s i nr e c e n t2 0y e a r s ，m a n ya u t h o r s 【3 7 】【3 j 【4 j f 5 jh a v em a d e g r e a te f f o r t st o s t u d y t h e q u a s i - n e w t o n m e t h o d s a c c o r d i n g t ot h el i n e a rs e a r c h t e c h n i q u e ，t h e u u a s i - n e w t o na l g o r i t h mc a nb ed i v i d e di n t o m o n o t o n e a l g o r i t l l i l l a 1 1 d n o n m o n o t o n e a l g o r i t h m u s l n gt h et r a n s f o r m a t i o no ft r a d i t i o n a lq u a s i n e w t o ne q u m i o na n dt a y l o re x p a n s i 呱 x l a o 、v e l ，t e n 固1 a l ls u n h g e tac l a s so fm o d i f i e dq u a s i n e w t o ne q u a t i o nu s i n gt h eb f g s f o n n u l aa n dw o l fl i n e a rs e a r c ht e c h n i q u e ，t h e y g e tac l a s so fm o d i f i e dq u a s i n e 叭o n a l g o n s u n d e rs o m es u i t a b l e c o n d i t i o n s ，t h e yp r o v et h eg l o b a la n dl o c a l s u p e r - l i n e a r c o n v e 喀e n c eo fm ea l g o r i t h m s l i uh a na n ds u n 1 9 a p p l i e dn o n - m o n o t o n el i n e a rs e a r c h t h n i q u et ot h eq u a s i - n e w t o na l g o r i t h mf i r s t l ya n du n d e rs o m es u i t a b l ec o n d i t i o n s t h e v p m v et h e 羽o b 引a n dl o c a ls u p e r - l i n e a rc o n v e r g e n c eo f t h ea l g o r i t h m s n u m e r i c a le x p e r i m e n t s n o wt h a t 锄s o m ec a s e s ，n o n m o n o t o n ea l g o r i t h m m a y b em o r ee f f i c i e n tt h a nm o n o t o n eo n e i nt h i sp a p e r ，u s i n gt h en o n m o n o t o n el i n e a rs e a r c h t e c h n i q u ea n dm o d i f i e db f g s 士o m u 地w eg e tac l a s so fn o n 。m o n o t o n em o d i f i e dq u a s i n e w t o na l g o 枷l i i l sb a s e do nt h e c l a s so f m o d i f i o dq u a s i - n e w t o ne q u a t i o nx i a o w e i ，f e n g j i a n s u n 5 】p r o p o s e d u 1 1 d e rs o m e s u l 纰l ec o n d i t i o n s ，w ep r o v et h eg l o b a la n dl o c a l s d 蔑d - l i n e a rc o n v e r g e n c eo fo u r 。a l 鲥s a tl a s t ，恤n u m e r i c a lt e s tr e s u l t ss h o wt h a to u ra l g o r i t h m s a r ee m c i e n tf o r 蚰c o n s t a i n e d o p t i m i z a t i o np r o b l e m s k e y w o r d s ：n o n ，m 。n o t 。n el i n e a rs e a r c h t e c h n i q u e b f g sm e t r i o d u n c 。n s t r a j n e d 0 p t i m i z a t i 。n g l o b a lc o n v e r g e n c el o c a ls u p e r - l i n e a rc o n v e 唱e n c e i i 声明尸i 刃 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谓| 的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名：监竖 p 尹多月嵋 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：至! 量杰 泸歹年6 月以日 硕士论文一类非单调修正拟牛顿算法及其收敛性分析 1 引言 1 1 拟牛顿法的起源 一般的非线性无约束最优化问题 卿( x ) 其中厂：r ”一r 是二阶连续可微函数。 它的求解方法有最速下降法，牛顿法和拟牛顿法等，其中拟牛顿法是最重要的一种 方法，现代许多求解无约束优化问题的算法都是对拟牛顿算法进行改进得到的。以下简 要介绍拟牛顿法的原理。 回顾牛顿法的基本思想：在目标函数厂( x ) 极小点x 的近似点x 。处将( x ) 二阶泰勒 展开即 ( 工) 吼( x ) = 厂( 黾) + 夥( 黾) 7 ( x 一) + 妻( x 一) 2v 2 f ( x k ) ( x - - x k ) ( 1 1 ) 也就是用q k ( x ) 去逼近厂( x ) ，将吼( x ) 的极小点稚+ 。作为x 的一个新的近似点。对( 1 1 ) 式的两端关于x 求导，且令 v q l , ( x ) = 夥( ) + v 2 f ( x k ) ( x - - x k ) = 0 即得 v 2 f ( x k ) ( x - - x k ) = - - v f ( x k ) 若v 2 f ( x k ) l - e - 定，则v 2 f ( x k ) 卅存在，由此解得的就是二次函数的极小值点 砟+ 。= - v 2 f ( x k ) 。1w ( 靠) 给定x 的初始近似点而后，迭代点列 x k ) 由上述公式产生，上述公式称为牛顿迭代公式， 相应的算法称为牛顿法。 牛顿法具有收敛速度快的特点，但是从上面的牛顿迭代公式中我们可以看出在迭代 过程中的每一步构造搜索方向时，首先要计算目标函数的海森矩阵，然后需要解一个方 程组，计算量很大，这就抵消了牛顿法收敛速度快的优点。 为了在保留牛顿法优点的同时，克服其缺点，需要寻求新算法。牛顿法是利用二次 函数逼近目标函数的算法，因此人们设想能否以某种正定矩阵最来代替海森矩阵q ， 并使迭代具有牛顿法的性质。为此目的，我们将厂( x ) 在x k + 。处作泰勒展开，得 厂( x ) 厂( + 。) + v f ( x 。+ 。) 7 ( x x k + 。) + 去( x 一气+ 。) rv f 2x k + 。) r ( x 一砟+ 。) 于是 v y ( x ) 耵( 磁+ 。) + v 2 厂( + 。) ( x 一五+ ，) 令x = x 。，贝4 l 引言硕士论文 w ( 椎) 耵( 以+ 。) + v 2 ( + ，) ( x 一+ 。) 即 v 2 厂( + ，) ( + 。- x k ) 耵( 屯+ ；) 一夥( 稚) 作为v 2 厂( 坼+ 。) 的近似，用尾+ 。替代v 2 ( + 。) ，要求满足 反+ 。峨= 败( 1 2 ) 其中 反= + l 一故，儿= 夥( + 1 ) 一夥( 以) 我们称( 1 2 ) 式为拟牛顿方程( 亦即原始的拟牛顿方程) 。 如何寻找适合方程( 1 2 ) 的矩阵b 卅，有许多方法，我们通常采用的是修正方法，即 令反“= 壤+ 峨，当最已知时，给出修正矩阵幄，可得到玩+ 。修正矩阵不同，得到 的境+ 。不同，由此形成的迭代算法也不同，我们统称这类算法为拟牛顿算法。 1 2b r o y d e n 族拟牛顿算法 秩一修正公式 却辫 n 3 ， ( 其中，( 败一8 a ) r 反o ) 其缺点是算法不能保证正定性。 为克服秩一对称拟牛顿算法数值计算的困难，p o w e l l 1 1 提出一种用秩一方法构造对 称拟牛顿法的技巧，利用这种技巧可以导出很多常见的拟牛顿校正公式。 ( 1 ) p s b 1 】公式 瑚去弦驯“( ? , - b a ) r _ 铲瓯硭 ( 1 4 ) 即p o w e l l 导出的对称b r o y d e n 校正公式。 ( 2 ) d f p 公式 嘶掣+ 舞+ ( 彰反瓯) 魄 ( 1 5 ) ( 其中魄2 者一盘) 最早由d a v i d o n 导出，并由f l e t c h e r 与p o w e l l ( 1 9 6 3 ) 1 1 1 所改善，现称为d f p 校正公式。 ( 3 ) b f g s 公式 哪矗一焉掣 ( 1 6 ) 硕上论文一类非单调修正拟牛顿算法及其收敛性分析 此公式由b r o y d e n f e l t c h e r - g o l d f a r b - s h a n n o 提出。 ( 4 ) b r o y d e n 族拟牛顿校正公式 耻境一焉磐+ 矗+ 矽( 壤瓯) 碱吲叫 ( 1 7 ) 当 o 1 ) 时，我们称为限制布鲁丹族拟牛顿校正公式。可以看出在上式中：令声= 1 即 得d f p 校正公式；令矽= 0 ，即得b f g s 校正公式。 1 3h u a n g 族算法 1 9 7 0 年，h u a n g 2 】提出了一类比b r o y d e n 族更广泛的算法族，该算法族中包含三 个自由参数，将b r o y d e n 族算法要求的条件放松，他的条件是： ( 1 ) 矩阵风不要求对称性； ( 2 ) 矩阵甄+ 。满足广义拟牛顿方程峨+ 。败= 砖，p r ( 3 ) 要求当算法应用于二次凸函数g ( x ) = i 1x r g x + b r x + c 时，产生的方向关于g 共轭，从 而具有二次有限终止性。 根据以上要求，他导出了一类新的含三个参数的h u a n g 算法族，当算法中的也满足对 称性要求且参数中的p = l 时，h u a n g 算法族就变成单参数的b r o y d e n 族，因此b r o y d e n 族是h u a n g 族的子集。 记校正矩阵为皿，迭代方向由 以= 一碰&( 1 8 ) 得到。按照上述条件，他导出了h u a n g 族校正公式的形式如下： 以+ l = 巩+ 暖+ h k y k o r k ， ( 1 9 ) 其中 以= a 1 1 瓯+ 口1 2 职儿， ( 1 1 0 ) = q 2 瓯+ a 2 2 酬虮，( 1 1 1 ) 且满足关系式 彳几= p 以- r t ，。t j ，= 一1 ( 1 1 2 ) 关系式( 1 1 2 ) q p 五个参数q 。，a t ：，a 2 。，a 2 2 ，p 中只有三个自由参数h u a n g 族校正公式依赖 于这三个参数，选取不同的参数，便得不同的算法事实上，当户= 1 时，若让h 。是对 称矩阵，只要a 1 2 = a 2 。，则日m 也对称，这时h u a n g 族只有一个参数将a 。取为自由参 数，若令 ”去+ 糌以 功 2 瓦+ 赢苒乩 ( 1 - 3 ) 联合( 1 1 0 ) ( 1 1 1 ) ( 1 1 2 ) 式可得 1 引言硕士论文 铲铲一最以她：= 而0 - 瓦1 将这些参数代a ( 1 9 ) 式，便得 = 4 罐一等掣+ 毋( y r h k 如 其中 吒= 去一厩- k y k 这就是关于巩的b r o y d e n 族拟牛顿校正公式。所以在h u a n g 族校正公式中也包含了d f p 校正公式和b f g s 校正公式。 1 4 线性搜索准则 在用拟牛顿算法求解无约束优化问题的迭代过程中，为了保证函数值的“充分下降 和迭代序列的全局收敛性，我们需要引入步长因子瓯，在拟牛顿算法中经常使用的是精 确线性搜索和不精确线性搜索准则。 ( 一) 精确线性搜索 精确线性搜索就是要求选择步长口。满足 以t + d t ) 2r 必厂k + 积t ) 以便获得厂( x ) 最大可能的下降精确线性搜索使得目标函数在迭代过程中下降量最大， 但是精确线性搜索的计算量较大，因此我们在求解无约束优化问题时，通常采取不精确 线性搜索求解迭代步长7 l 。 ( 二) 不精确线性搜索 l 。戈德史丹准则： 给定，o 90 2 。，令班= 0 ，1 ，2 ，检验不等式 f ( x 。) 一厂b + ”。) 一矽”y v f ( x 。) 丁以 ( 1 1 8 ) 是否成立，记使得上面不等式成立的第一个m 为豫，则令吃= 仇厂因为吱是下降方 向，当m 充分大时，上面不等式总是成立，因此上述的m 。总是存在的 1 5 修正的拟牛顿方程和改进的b f g s 校正公式的研究现状 1 5 1 修正的拟牛顿方程 最初的拟牛顿方程为 毋+ 。反= 败，反= x k + 。一毪，儿= v f ( x , + 。) 一v ( 黾) 而 y k = v j ( x , + 。) 一夥( 讫) = lf v 2 厂( 稚+ 纸) d 秒l 皖 ( 1 。1 9 ) 比较( 1 1 9 ) 式和最初的拟牛顿方程可以看出，反+ 。应该是逼近海森矩阵在和故+ 。之间的 均值，若让最+ 。逼近海森矩阵q “，对于非二次函数，色+ 。瓯和职之间存在误差，因此 拟牛顿方程和暖的校正公式有待进一步的提高。而最初的拟牛顿方程和修正的公式仅涉 及到g k 小g k ，而忽略了目标函数的函数值。为了利用更多的信息，国内外大量研究人员 致力于拟牛顿法的研究，拟牛顿算法的拓广有了很多研究成果。 1 j z z h a n g ，c x x u 3 】于2 0 0 1 年通过张量分析提出了一族新拟牛顿方程 瓯2 儿+ 嚣 j 肿r = 3 ( g m + 繇) r 瓯一6 ( 五+ 。一以) ，尺”且露o 从上式可以看出： 当2 反时，( 1 2 0 ) 式可写成坑。职+ 爵 ( 1 2 0 ) 硕士论文 当= 儿时棚加，式可写成瓯= ( + 表卜属于n u a n g 族拟牛顿法。 2 z ，x ，w e i 【4 1 于2 0 0 6 给出了另外一族新拟牛顿方程，如果在第k 步迭代时利用函数 五( x ) = ( x ) + 去( x 一黾) 7 4 ( x x k ) 其中4 一个对称正定矩阵，我们可以得到下面的新拟牛顿方程 毋+ 。瓯= 以( 1 2 1 ) 其中以= y k + 4 瓯，从上式我们可以看出当k _ ，瓯0 时，这个新拟牛顿方程就接近 于一般的拟牛顿方程了。 选择4 使得新拟牛顿方程的右边i ：t - 般的拟牛顿方程的右边更好的接近目标函数在点 x k + 。处的二阶导数g + 。与瓯的乘积他给出t - - - 种4 的选择。 ( 1 ) 4 = ， q m 2 爵l q 4 2 裔( 圳 其中以= 2 ( 以- a + 。) + ( & + g k + 。) 2 瓯 3 w e ix i a o ，f e n g j i a ns u n l 5 l 于2 0 0 8 年提出一类修正的拟牛顿方程。在一般的拟牛顿 方程b + 。& = m 右边加入一些信息量，如下 坟+ 。坑= ( ，+ 4 ) 败= 败+ 4 儿= 以( 1 2 2 ) 从而有 酲b k 。p = a y t + 6 ：a k y q 2 3 ) 而 厂( x ) = 以+ l + o 一+ 1 ) r g k + l + i 1 ( z 一黾+ 1 ) r q + l o 一赡+ 1 ) 因此有 五= 以+ 。一醪g k + 。+ i 1 吼t 瓯+ 。 所以 配q + 。瓯= 2 ( 五- a + 1 ) + 2 彰+ 1 = 2 ( 六- a + 1 ) + ( 繇+ ，+ g d7 瓯+ 儿( 1 2 4 ) 由( 1 2 3 ) ( 1 2 4 ) 知 6 ：a k y k = y k 其中 以= 2 ( 以- l + 1 ) + ( & + l + 瓯) 丁皖 他给出了4 的三种选择： 硕上论文一类非单调修正拟牛顿算法及其收敛性分析 ( 1 ) 铲轰， ( 2 ) a 2 t2 赤暖配 ( 3 ) 如。矾蕊( 皖+ y k ) a 善 1 5 2 改进的b f g s 校正公式 大量的的数值试验表明b f g s 校正公式的数值稳定性比其它的校正公式要好，而且 它与不精确线性搜索方法结合使用能收到较好的结果，所以在实际计算中大多采用 b f g s 方法。为了提高计算效率，许多学者提出了各种改进形式。 1 l i a oa ip i n g 6 i1 9 9 7 年提出了一种改进的b f g s 校正公式，其形式为： 嘶反糍+ 以爱 ( 1 2 5 ) 当t 霉选一f 时t 一b k s k + s k y k 、 ( ，_ ( 纛r b ，燕t 当茎氅f时t s k b k s k + s ：y t ( 壤，儿) = ( f ，1 ) 其中0 f 1 ，有以上可知 f 瓯1 r o 儿1 2 x i a oy u n h a i 7 2 0 0 3 年对常规的b f g s 公式 卟鼍掣+ 舞 第三项进行了改进，将分子中的虬改为以，这里采用w e i 4 】提出的形式，而分母中的败 不变，即 7 硕卜论文 嘶掣+ 菩 1 6 非单调线性搜索准则及非单调拟牛顿算法 ( 1 2 6 ) 1 6 1 非单调线性搜索准则 最优化方法通常是用迭代法来逐步产生它的最优解。现在广泛用来求解优化问题 的绝大多数方法都是单调的算法，也就是产生的点列要求目标函数值在每一步都是下降 的，即： 厂( + i ) ( 稚) ( 1 2 7 ) 这种单调性的要求好像是很自然的，因为算法的目的就是要找到可行域内使目标函数值 最小的点。 但是这种要求目标函数在迭代过程中严格下降的性质有一个缺点，当目标函数在可 行域中存在细长弯曲的峡谷的情形时( 这在目标函数非线性程度较高时很容易出现，如 r o s e n b r o c k 函数) ，单调性算法就会大大丧失它的计算效率。基于对这种现象的观察， l g r i p p o ，e l a m p a r i e l l o 和s l n e i d i l 8 j 在1 9 8 6 年对于牛顿法提出了一个最初的非单调的线 性搜索准则。另外有些优化算法本身具有某种局部超线性收敛性，但并不要求目标函数 单调下降( 如逐步二次规划法，两点梯度法等) ，这也是要研究非单调算法的原因之一。 非单调算法的特点就是，在算法中并不要求单调下降在每一步都得到满足，而是对于迭 代给出一个更宽松的条件，但仍能保证算法的收敛性。由于非单调算法在实际中获得了 很好的计算效果，很多学者都对它进行了进一步的研究。如 p h i l l i p e ，t o i n t 3 3 】f 3 4 】，n y d e n g l 3 判，j y h a n 1 5 4 0 】，e b o r m a n s ，e p a n i e r , a t i t sa n dj l 。z h o u 4 1 】【2 2 】， y h d a i 【2 1 】等。 ( 1 ) 非单调线性搜索准则最早由l g r i p p o ，e l a m p a r i e l l o 和s l n c i d ii s j 于1 9 8 6 年在牛顿算 法中提出。 他们的方法大致是这样的：给定参数丑，如，仃，占，m ，其中o 五 乃，o r ，艿( o ，1 ) ，m 为某 个固定常数，并且令吼= 吼仃惋，这里( ，五) 是试探步长，魄是最小的非负整数满 足 厂( + a k d k ) m a xf ( x k 一，) + 慨w ( & ) 反 ( 1 2 8 ) 这里的m k 满足= 0 ，0 m k m i n m k l + 1 ，m ) ，k 1 当m k = 0 时，这种非单调线性搜索准则就变成了单调的阿弥佳线性搜索准则了，因此我 们把它称为非单调阿弥佳线性搜索准则。后来许多文章都采用了这种非单调线性搜索准 则，比如文献【1 2 】【1 4 】【8 】【1 1 】【1 5 】【1 引 ( 2 ) h a njyl i ugh 【9 1 得到了下面的非单调线性搜索准则，把它称为g l l 线性搜索： r 硕士论文 一类非单调修正拟牛顿算法及其收敛性分析 选择步长满足： 厂( 魂+ o e k 矾) m a x c 2 ，1 一( 吼1 吨矿g r d k ，p - - - 0 0 ，1 ) ( 1 2 9 ) ( 1 3 0 ) 其中q ( o ，1 ) ，岛io ，_ 1j ，m 是非负整数，很明显当m = o ，p = o 时就得到了我们经常使 l 用的沃尔夫线性搜索准则。 ( 3 ) h o n gc h a oz h a n g ，w i l l i 锄w h a g e r l lo 】于2 0 0 4 年提出了另外一种非单调线性搜索 方法，他们的非单调线性搜索方法如下： 参数0 r u r m 积1 ，0 五 五 1 o ，c o = ( ) ，九= 1 厂( 峻+ 吼畋) g + ；q a k g ( x k ) 以 ( 1 3 1 ) g ( x k + 喀) 以4 9 ( x k ) 噍 ( 1 3 2 ) 选择仇( ，) ，并且饥。= 仇纠& ，= ( 仇吮q + 他+ 1 。 ， 我们把上述准则称为非单调沃尔夫线性搜索准则。 ( 4 ) n e n gz h ug u ，j i a n gt a om o l l l 】提出了一种新的改进的非单调线性搜索： 选择步长满足 ，b k + a k d 、s o k + p 仅t g k t d 俄题t 钏枷凸滁q - 袋1 譬t 三1 川舱2 一胛t o ，1 ) 1 7 7 一+一刁j ，i j ，庀2 ，巧，l j ( 5 ) s u nwyh a nj ，j 【1 2 1 于2 0 0 2 年提出了非单调戈德史丹搜索： ( + 吼以) 一厂而( i ) ) p l a i d r g k 厂( 吆+ 以) 一厂( ) 仍吼t 其中 ( 1 3 3 ) ( 1 3 4 ) ( 1 3 5 ) ( 1 3 6 ) 厂( 瓢七) ) = 。嬲，厂( 一小 m ( o ) = o ，o 肌( 七) m i n 聊( 七一1 ) + 1 ，m ，k 1 ，m 是非负整数。 ( 6 ) w e ny us u n ，q u ny a nz h o u l l 3 】于2 0 0 7 年将非单调技术和新的二阶戈德史丹搜索准则 相结合得到了一个新的非单调二阶戈德史丹线性搜索方法。 如果靠是不确定点，( & ，矾) 是处的下降对，则线性搜索终止当吃满足下面的条件： ， 稚( ) 一厂( h 。) ) 局i 繇+ 吾q 喀i ( 1 3 7 ) 9 l 引言 硕上论文 厂 耳( 吼) 一，( ) 仍彳 s ；+ 圭q 喀 ( 1 3 8 ) 其中稚( ) = 黾+ + 畋，厂( _ ( 。) ) = 。爨蒜) ( 以一，) ， m ( o ) - - o ，o m ( k ) m i n m ( k - 1 ) + l ，m ，七1 ，m 是非负整数。 1 6 2 非单调拟牛顿算法 由于大量的数值试验表明非单调算法比单调的算法更有效，因此许多专家学者在拟 牛顿算法中采用了非单调技术，因此就得到了非单调拟牛顿算法。 i l i uh a n a n ds u n 9 j 于1 9 9 5 年首次将非单调搜索准则( 1 2 9 ) ( 1 3 0 ) 应用到b f g s 拟牛顿算 法中得到了非单调b g f s 算法。其算法如下： 步骤1 给出初始点r ”和初始正定矩阵b 。r “”，以及0 占 l ，k = 0 步骤2 若l g ( x s ，则停止，否则计算b k d k + g 。= 0 ，求得搜索方向噍 步骤3 利用非单调搜索准贝t j ( 1 2 9 ) ( 1 3 0 ) 求得步长，令x k “= 以+ 吼以 步骤4 利用公地。瑚番焉掣更新斛蛾飘。 步骤5 令k = k + 1 ，转步骤2 并且还证明了在适当的条件下算法对于一直凸函数和凸函数具有全局收敛性和局部超 线性收敛性。数值试验表明对于某些函数非单调b f g s 算法比传统的b f g s 算法更有效。 2 h o n gx i a y i na n dd o n gl e id u 1 4 j 将非单调搜索准贝j j ( 1 31 ) ( 1 3 2 ) 应用到自度量b f g s 算 法中，得到了非单调自度量b f g s 算法。 其算法如下： 步骤1 给出初始点r ”和初始正定矩阵b o r “，令k = 0 步骤2 差i ，g ( x 。川= 0 ，则停止，否则计算b k d k + = 0 ，求得搜索方向d 步骤3 利用非单调搜索准则( 1 。3 1 ) ( 1 3 2 ) 求得步长，令& 钉= + 吼d 鼎利用公枫。= 小一焉掣卜羞更新斛玩瓢斟 , o k2 丽y 。o k称舶度量因子。 步骤5 令k = k + 1 ，转步骤2 并证明了在一定的条件下算法对于非凸函数具有全局收敛性。 1 7 本文的主要工作结论和相关安排 1 0 硕士论文一类非单调修正拟牛顿算法及其收敛性分析 本文主要围绕带函数值信息的拟牛顿算法和非单调线性搜索准则展开，提出一类非 单调修正拟牛顿算法。文献f 5 】利用传统的拟牛顿方程的变形以及泰勒展开式得n t - - 类 带函数值信息的修正的拟牛顿方程：最+ 。瓯= ( ，+ 4 ) 几= y k + 4 儿= y k 给出了矩阵4 的三种选择： ( 1 ) 4 广赣， ( 2 ) 2 卉蠹骈 ( 3 ) a 3 , k 丽靠( 反+ 坛) 簟 其中= 2 ( 五一五+ 。) + ( + g k + 。) 7 皖。 利用b f g s 修正公式及w o l f 搜索准则得到了一类单调的修正拟牛顿算法。根据文献 【7 】【9 1 4 】的思想，基于文献f 5 】中提出的带函数值信息的一类修正的拟牛顿方程，我们采用 文献1 7 j 中改进的b f g s 校正公式，对于步长瓯我们采用非单调线性搜索准n ( 1 2 9 ) ( 1 3 0 ) 得到，相应的我们得到了一类非单调修正拟牛顿算法。并在一定的条件下，根据文献【1 5 】【1 6 】 对于非单调算法收敛性的证明思路证明了此类非单调修正拟牛顿算法具有全局收敛性 和局部超线性收敛性。 本文的主要结论：全局收敛性和局部超线性收敛性结论 本文的结构安排： 第一章引言：综述拟牛顿法的发展历程，研究现状以及本文的主要工作。 第二章提出本文的一类非单调修正的拟牛顿算法。 第三章对本文提出的一类非单调修正的拟牛顿算法的收敛性进行分析，在一定的 条件下，证明了该类算法的全局收敛性和局部超线性收敛性。 第四章给出算法的数值验证结果。 2 一类非单调修正的拟牛顿算法 硕十论文 2 一类非单调修正的拟牛顿算法 w e ix i a o ，f e n g j i a ns u n 5 1 提出一类修正的拟牛顿方程 从而有 而 因此有 所以 反+ l 瓯= ( ，+ 4 ) 坛= 欺+ 4 败= 戎 6 ：b k 、6 = 6 k t y k + 6 ：a k y t 厂( x ) = 五+ 。+ 一+ 1 ) f + 。+ 兰。一k + 1 ) r q + l ( x 一矗+ 1 ) 以= 五+ 。一+ 。+ 兰q + 。 罐q + ，瓯= 2 ( a - a + 。) + 2 8 g k + l = 2 ( f k - a + 1 ) + ( + l + ) r 瓯+ 坛 由( 2 1 ) ( 2 2 ) 知 a k y = y t 其中以= 2 ( f k - a + 1 ) + ( + l + ) r 反 他们给出了4 的三种选择： ( 1 ) 4 i：乓l ， 6 ：y k ( 2 ) 如2 志皖 ( 3 ) 4 乒2 丽靠( 暖+ 儿) 霹 因此得到了一类带函数值信息的修正的拟牛顿方程。 对于无约束优化问题，m i n 厂( x ) l x r ” ， 拟牛顿算法要求下一个迭代点稚+ 。由下面的迭代公式得到 诈+ l = + 喀 ( 2 1 ) ( 2 2 ) ( 2 3 ) 在上面的公式中，吼是步长，哦是搜索方向，并且吨= 一何1 ，对于最我们采用 文献f 7 1 中的改进的b f g s 型修正公式得到即 1 2 。毋瓯( 反瓯) 。 反+ l _ 色一箫 ( 2 4 ) 掣 + 硕上论文 一类非单调修正拟牛顿算法及其收敛性分析 下面我们给出本文提出的一类非单调修正拟牛顿算法的具体步骤： ( 1 ) 给定初始点x o r 疗，玩= ，令k = 0 ( 2 ) 如果既0 = 0 则停止，否则转到第( 3 ) 步。 ( 3 ) 解方程反反= - g 。得到搜索方向吨。 ( 4 ) 利用g l l 线性搜索 f ( x k + a k d k ) 。m ，a xf ( 、x k ) + q g t t 巩 g ( x k + 以) r 以m a x 乞，1 一( 吼。巩o ) p g 反，p - o o ，1 ) 其中q ( o ，1 ) ，乞( 。专) ，m 是非负整数 ( 1 2 9 ) ( 1 3 0 ) 得到步长，利用公式( 2 3 ) 得到下一个迭代点。 ( 5 ) 令瓯= 故+ 。- x k ，如果敝+ 。- x , i l = 0 ，则停止。否则，计算 y ：= y k + a k y k ，, y k 詈g ，- 1 ) 配耽 ( 2 5 ) 败2 1 以，段 ( f 1 ) 欺 u 。， 其中占充分小，如6 = 1 0 _ 1 8 。利用公式( 2 4 ) 得到对称正定矩阵忍+ 。 ( 6 ) 令k = k + 1 ，转到第( 2 ) 步。 对于上面的算法，在( 2 5 ) 中当4 分别取4 p 4 p 4 ，七时，得到了三种不同的算法， 我们把它们分别记作n m b f g s l 算法，n m b f g s 2 算法，n m b f g s 3 算法。 3 算法的收敛性分析硕：l 论文 3 算法的收敛性分析 本章我们将证明本文提出的此类n m b f g s 算法的全局收敛性和局部超线性收敛 性，我们现在做出如下假设： 假设( 1 ) ： 水平集q = x i ( x ) 厂( ) 包含于一个有界凸集d 上。 假设( 2 ) ：目标函数( x ) 是一致凸的，即存在正常数q ，c 2 ，使得 c l l z l l 2 z 7 g ( x ) z c 2 2v x ，z r ”( 3 1 ) 假设( 3 ) ： 目标函数( x ) 是二阶连续可微的。 3 1n m b f g s 算法的全局收敛性分析 引理3 1 如果假设条件( 1 ) ，( 2 ) ，( 3 ) 成立，则存在一个正常数m l 满足 蜓纵矧2 n 2 ， 证明：首先我们证明序列 是由n m b f g s l 算法产生的，因为y ：= y k 时，文献【1 7 l 已证 明此式成立，因此在这里我们只证明y i = 儿+ 4 ，。儿时结论成立。所以 ( 兀。) r 吨= ( 以+ 4 ，。以) 7 ( 儿+ 4 ，。虮) = 欺t 儿十儿t 4 ，。儿+ ( 4 ，。儿) 7 儿+ ( 4 儿) 7 ( 4 ，。儿) ( 3 3 ) 由假设条件( 2 ) ，我们可以得到以c ：20 哦n 因为 钆2 轰 其中 以= 2 ( 五一五+ ，) + ( & + + ，) r 瓯 根据假设条件( 2 ) 1 2 ( 以一五+ 。) + ( g k + + 。) r 瓯i i 配g ( q ) 瓯一罐g ( 乞) 瓯i 2 c 20 坑0 2 欺= 硭( + 。一既) = 霹g ( s ) 皖q0 瓯1 1 2 1 4 硕士论文一类非单调修正拟牛顿算法及其收敛性分析 其中 所以 则 又因为 所以 = x k + 眠，q = 磁+ o l 女瓯，乞+ 岛瓯，0 ，岛 ，岛i ( o ，1 ) h 忙 6 ：y t 4 ，。儿- e , i i a , ，。02 囟瓯1 1 2 0 l 堡螳：垒 l i l i 2 一 a l , k y k ) r ( 彳。，。j ，。) = y ：彳。a t , k y k y ：y 。l l 彳。，。1 1 2 4 c c ；：4 。i 万。1 1 2 6 ；y k 一+ 等+ 等 c 1c ： = m l 当序列 稚 是由n m b f g s 2 算法产生时，因为y ：。= y k + 4 。以，其中 所以 则 又因为 所以 小赢瓯 阻| i 蚓1 2 几 4 儿一儿1 1 4 ，。i i 2 鲁i l 皖1 1 2 1 2 6 ：y l ( a 2 , k y k ) r ( a 2 k y k ) = 少。t 彳：r a ，y 一 y 。t y 。i i 彳：，。1 1 2 4 c c - - - 。兰2 4 1 1 6 , 1 1 2 6 ：y k t + 等+ 等 ga = 鹚 丝 c l 1 5 瓯一 峭互塑 瓯一瓯嵋互q + 一 瓯一 警 撬一 一塑 州 一 张一饿蝴礤一亿 荆 一 瓯一 v i 3 算法的收敛性分析硕上论文 当序列 稚) 是由n m b f g s 3 算法产生时，因为j ，：j = y k + 鸣，。y k ，其中 所以 则 所以 2 丽靠( 瓯+ y k ) 8 ： 4 ，。0唑梨掣淝训争 一 彰( 瓯+ 儿) 霹儿r 川以7 一c l 4 ，。儿儿i i a 3 i | 2 鲁。瓯1 1 2 a 3 , k y k ) r ( a 3 , 。y k ) 叫彳3 r k a 3 , k y k y i i a 3 , , 雌等2 6 ：y k 竺! 兰墅二兰! 兰鬈：釜! 兰墅：璀：m q 2 q 1 综上所述结论成立。 引理3 2 【4 】如果假设条件( 1 ) ( 2 ) ( 3 ) 成立， x k ) 由n m b f g s 算法产生，则存在正常数 、h n 嘲，m 2 ，m 3 捅疋 鸭儿i 阪8 2 硭盛 引理3 3 d e t ( 嘎+ 。) d e t ( 坟) 砖毒害妄，其中d e t ( 反) 代表矩阵反的行列式。 证明：根据( 2 4 ) 式 哥 所以d e t c 最。= d e t c 壤， ( 一 1 6 b k 6 k b k 6 k a e 她，燃 ) 1 + 斗瓣+ 掣 警 ( - 躺卜i 瓯 j 【壤( 鼠皖) j r 竹心儿7i 磐 硕士论文 一类非单调修正拟牛顿算法及其收敛性分析 根据引理3 2 我们可得 d e t ( ) 砖盎 芒j i n _ 3 4 若假设条件( 3 ) 成立，则存在正常数满足 其吣莆 岛面nr k ，( 气) 训) 证明：根据假设条件( 2 ) ，可以得到下面的式子成立 g ( + 巩) 一 r 反= 衫f g ( 吒+ f 吼畋k 出0 以1 1 2 ( c ：+ 1 ) 另一方面由( 1 3 0 ) 式可得 g ( + 吒巩) 一反 r 畋一m i n1 一岛，( 0 皖矿g r d k 因此 ( 乞+ 1 ) m i n1 一岛，( ) ，r k 比较1 一乞，( 0 瓯矿，由上式很容易得到 。瓯i i m i n i 【1 c ：- + 6 2 ，i 乏j l - 琢：i ( 吒) 一p ，) 氏正n 珞，( ) 一p ， 其悻商n 降丽1c2( + 1 ) 必卜p ) j z j l 理3 5 记厂( ) = o s j m a xf ( x , 一) ，七一m 。办( 七) 后， ( 3 4 ) 如果厂( + 。) 厂( 似) ) ，后= o ，1 ，则序