（计算数学专业论文）解无约束优化的渐弱过滤集方法.pdf

摘要 许多重要的问题都可以表示成非凸非线性多变量无约束优化问题线搜索方 法和信赖域方法是解无约束优化问题的两类比较流行的算法过滤集技术自从 被f l e t c h e r 和l e y f f e r 于1 9 9 7 年提出随后正式发表于丈献【1 3 】以来，在许多方面都有 了广泛的研究与应用，取得了很好的效果 本论文为解大规模无约束优化问题，提出了一种新的渐弱过滤集技术我们知 道，为了保证全局收敛，多维过滤集技术1 2 1 ，2 5 ，2 7 】在禁止域外围加了一层固定厚度 的封套经过分析，我们指出固定厚度的封套不适合于回退线搜索过程，故而本论 文对其进行了一定的改进，进而提出了渐弱过滤集技术其核心思想在于：封套的 厚度不再是固定不变的，而是随着线搜索步长因子的减小而不断变薄且渐趋于无 很自然的，将渐弱过滤集新技术与二阶线搜索方法结合而成的新算法是过滤集 技术在解无约束优化问题时的一类重要算法理论分析表明新算法能够至少收敛到 一个二阶稳定点我们的数值实验，一方面研究了新算法的数值表现，另一方面说 明了利用计算机f o r t r a n 语言的链表结构可以较好的解决计算机实现问题在计 算中，我们发现存储渐弱过滤集元素所消耗的计算机内存空间的规模是中等的 然后，我们又注意到：信赖域方法往往比线搜索方法更为有效这就启发我们 将渐弱过滤集新技术与组合信赖域线搜索方法结合起来组成新的算法我们分析了 该算法的全局收敛性质，并证明了该算法能够至少收敛到一个二阶稳定点对标准 的c u t e r 测试函数问题集所做的数值实验表明该算法有上佳的数值表现数值实验 也表明存储渐弱过滤集元素所消耗的计算机内存空间的规模也是中等的 关键词：渐弱过滤集，无约束优化，线搜索、信赖域、二阶稳定点 a b s t r a c t m a n yi m p o r t a n tp r o b l e m sc 3 nb ee x p r e s s e di nt e r - u i 8o fn o n c o n v e xn o n f i n e a rm u l t i v a r i a t e u n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s t w ob r o a dc l a s s e so fm g o r i t h m sf o rt h eu n c o n s t r a i n e d o p t i m i z a t i o np r o b l e n m 口el i n e - s e a r c ha l g o r i t t n n sa n dt r u s t r e ；i o i l a l g o r i t h m s s i n c ef i l t e r t o c j m i q u cw a si n t r o d u ( c db yf l e t c h e ra n dl e y f f c ri n1 9 9 7m i ds u b s e q u e n t l yp u b l i s h e da s 【1 3 1 f i l t e rt e c h n i q u eh a sb e e ns t u d i e da n da p p l i e di nm a n ya r e a s ，a n di tp e r f o r m sw e l l w ep r o p o s e dan e wd w i n d l i n gf i l t e rt e c h n i q u ef o rl a r g e - s c a l eu n c o n s t r a i n e do p t i m i z a t i o n p r o b l e m s g e n e r a l l y ：f o rt h ep u r p o s eo f g i o b a lc o n v e r g e l t c e ，t h em u l t i d i m e n s i o n a lf i l t e rf 2 1 ，2 5 ， 2 7 1i sc o v e r e db yaf i x e de n v e l o p e s i n c eaf i x e de n v e l o p ei sn o ts u i t a b l ef o rb a c k t r a c k i n gl i n e - s e a r c hp r o c e s s ，w ef u r t h e rs t u d yi ti nt h i st h e s i sa n dp u tf o r w a r dac o n c e p t i o no fd w i n d l i n g f i l t e rt e c h n i q u e t h em a i ni d e ai st h a tt h ed w i n d l i n gf i l t e re n v e l o p ei sn o tf i x e d ，b u tb e c o m e s t h i n n e ra n dt h i n n e ra st h es t e p - l e n g t ho ft h eb a c k t r a c k i n gf i n e - s e a r c hb e c o m e ss m a l l e ra n d s m a l l e r n a t u r a l l y ，c o m b i n a t i o no ft h ed w i n d l i n gf i l t e rt e c h l i i q u ea n dt h es e c o n d o r d e rl i n e - s e a r c h m e t h o di sav e r ys i g n i f i c a n ta l g o r i t h mf 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 t h en e wa l g o r i t h mi s s h o w nt ob eg l o b a l l yc o n v e r g e n tt 0o n es e c o n d - o r d e rs t a t i o n a r yp o i n ta tl e a s t p r e l i m i n a r y n u m e r i c a le x p e r i m e n t so n as e to fc u t e rt e s tp r o b l e m si n d i c a t et h a tt h en e wa l g o r i t h m i sv e r yc o m p e t i t i v ew i t hs o l n ec l a s s i c a ll i n e - s e a r c ha l g o r i t h m s w es h o wt h a tt h el i n k e d - l i s t c o n s t r u c t i o ni nt h ef o r t r a n l a n g u a g ew o r k sw e l la a l dt h a tt h es t o r a g eo ft h ed w i n d l i n g f i i t e ri sm e d i u m a n dt h e n ，w en o t i c et h a tt h et r t l s t - r e g i o nm e t h o di sa h v a y sm o r ee f f e c t i v et h a nl i n e - s e a r c hm e t h o d t h i si n s p k e1 1 8t oa p p l yt h ed w i n d l i n gf i l t e rt e c h n i q u ei nt r u s t - r e 西o nl i n e - s e a r c hf r a m e w o r kt og i v ea n o t h e rn e wa l g o r i t h m w ep r o v et h a t u n d e rr e a s o n a b l em s u l l l p t i o n s t h en e wa l g o r i t h mc o n v e r g e st oo n es e c o n d - o r d e rs t a t i o n a r yp o i n ta tl e a s t s o m e p r e l i m i n a r yn u m e r i c a lr e s u l t so i las e to fc u t e rt e s tp r o b l e m sa r er e p o r t e d w h i c hs h o w t h a tt h i sn e wa l g o r i t h mh a sas i g n i f i c a n tp e r f o r m a n c ea n dt h a tt h es t o r a g eo ft h ed w i n d l i n g f i l t e r 扭m e d i u ma sw e l l k e y w o r d s ：f i l t e rt e c h n i q u e ，u n c o n s t r a i n e do p t i m i z a t i o n ，l i n es e a r c hm e t h o d ，t r u s t r e g i o nm e t h o d ，s e c o n d - o r d e rs t a t i o n a r yp o i n t 插图目录 1 1 n o c e d a l 和袁弧湘教授在文献m 】中的信赖域子问题的可行域 2 1 覆盖在渐弱过滤集上的封套的厚度随着石退线搜索步长冈子的缩小而交薄的 示意图， d f l s i i a l s 算法解e x t r o s n b i 题时的目标函数值与迭代次数的变化关系图 目标函数值求值次数， 梯度值求值次数 迭代次数， 共轭梯度迭代次数 计算时间，+ ， 渐弱过滤集迭代步与需保存的渐弱过滤集元素的规模， 存储渐弱过滤集元素所需的内存空间与变量维数的关系， 四种信赖域算法解e x t r o s n b 问题时的目标函数值与迭代次数的变化关系图 目标函数值求值次数， 梯度值求值次数， 迭代次数， ， 共轭梯度迭代次数 计算时问， 存储渐弱过滤襞元素所需的内存空间与变量维数的关系， 4 9 娼坞垮垮殂虬 盯弘勰昌；昌；如 l 2 3 4 5 6 7 8 1 2 3 4 5 6 7 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 表格目录 3 1c u t e r 狈i 试函数名及其维数1 6 3 2d f l s 算法解不同维数的f l e t c h c r 问题所需要的渐弱过滤集元素的存储空间2 2 4 1c u t e r 测试函数名及其维数 4 2 四种信赖域方法的成功率 3 5 3 6 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所傲的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名： 日期： 第一章绪论 许多重要的问题都可以表示为非凸非线性多变量无约束优化问题无约束优化问题就是 极小化个实变量的目标函数，其q j 对这些变量的取值范伟l 没有限制其数学表达式如卜 。r a 孙i n ，( 。) ， ( 1 or 1 ) 其中，是r n 空间上的实值目标函数若，( ) 二阶连续可微，则( 1 0 1 ) 称为光滑无约束优化问 题：否则，称之为非光滑无约柬优化问题如果没有特别说明，本论文所讲的无约束优化问 题就是毙滑无约束优化问题 第1 1 节解无约束优化问题的一般方法 解无约束优化问题的全局化方法般有两种：线搜索与信赖域方法这两种疗法部是迭 代法，在适的条件f ，都能够保证算法严生的迭代点列收敛到二阶稳定点，即在该点处， 目标函数的梯度为零，并且有h e s s i a n 阵正半定 经典的线搜索方法，在每一，步迭代，通常先选择个( 或两个) 搜索方向，然后沿选定 的，b 响进行直线( 或曲线) 搜索，寻找个合适的步长，这样就构成了 步迭代孽复这个 过程直至收敛为了保证线搜索方法，“尘的迭代点硎能够收敛剑二阶稳定点，在迭代的过 程中往往需要充分利用目标函数的曲率信息例如，m c c o r m i c k 在文献f 3 2 1 q j 义提出的二阶 线搜索方法这类方法的十要思想是：在每一一步迭代中，都选择对f 降方向( 船出) ，其 中8 是梯度相关方向，出是负曲率方向然后沿如下曲线进 亍搜索 。知+ l ( ) 望茹每+ s 七+ 佩出， 其中步长因子n k 由r 义a r m i j o 准则确定 梯度相关方向s 通常选择的是( 近似) n e w t o n 方向，有很多种方法可以计算，齐种具 体方法参考著作f 3 9 ，5 6 1 最理想的负曲率方向鼍然是目标函数h e s s i m i 阵的最负的特征值所对廊的特征向量，世 是，由于h e s s i a n 阵最负的特征值对应的特征向量不容易求得，所以通常都退步，仅考虑 计算个充分的负曲率疔- 向a i o r 6 和s o r e n s e n 在文献p 7 l 中指出：矩阵f l b u n d i p a r t e t t 分 解技术f 3 1 可以计算个充分的负曲率方向随后，f e r r i s ，l u c i d i 和r d m a 在文献【1 l 】中- 将这种二阶线搜索方法与非单调线搜索技术2 8 3 0 1 相缔合而得到了。种混合方法，并且 在适。的条件卜。征明了此算法能够全局收敛到二阶稳定点这种基于矩眸分解的技术对 于处理中小规模的问题是比较有效的但是，对于大规模问题，在每步迭代都进行 1 1 1 解无约束优化问题的一般方法 2 次矩阵分解无疑需要消耗大量宝贵的计算时间，并且需要消耗大量的内存空间1 因此， 许多作者考虑使用达代法来计算一个充分的负曲率方向，从两达到节省计算时间或者节 省内存空问的目的由于l m l c z o s 疗法2 0 l 在近似计算矩阵最大与最小特征值及其特祉向量 方面的良好表现，l u c i d i ，r o c h e t i c h 和r o m a n - 文献f 3 1 1 中考虑使用l a n c z o s h - 法来近似计 算最负的特征值所对应的特征向量该文献还沿用了非单调技术来解决大规模无约束优 化问题b o m a j l 和m u r r a y 在文献1 1 中还考虑用2 - 步l a n c z o s 方法和c h e b y s h e v 迭代来计算 个充分的负曲率方向注意到l a n c z o s h 法为了得到个充分的负曲率方向，通常需要存 储l a n c z 6 s 正交基，或者霞新生成之冈此，在使用l a n c z o s 疗法时，鱼和熊掌，不可兼得， 也就是说。我们不得不在牺牲内存空间和牺牲计算时间之间作出 个艰难的选择为了兜服 这个问题，f a s a n o 和r o m a 在文献f 1 0 1 中探索利珥 平面共轭梯度法【6 - 9 来计算个充分的负 曲率方向该方法既不需要存储，义不需要蕈新生成任何向量基，是一种相当划算的方法 同样的，步长冈子的选择是线搜索方法成功与否的另个蓑键问题注意剑，单位 步长对于近似n e w t o n 方向( 梯度相关方向) 通常是- 个不错的选择，但是对于负曲率方 向，如何选择步长冈子是个相当困难的问题为此，g o u l d ，l u c i d i ， i o l l l a 和t o h a t 在文 献f 2 2 1 中考虑避免这令人头痛的难题他们认为，近似n e w t o n h 向( 梯度相关方向) 的 主要作用在于确保全局收敛和快速局部收敛，而负曲率方向的作用在于促进迭代点列尽快离 开局部非凸区域他们的做法是在近似n e w t o n 方向( 梯度相关方向) 和负曲率方向之间选 择。个比较有前途的方向，然后沿这个片向进行直线搜索这里的选择是基于个自适应的 过程，就是看局部二次模型函数在哪个力向上f 降快就选择哪个方向最近，阁群艳和孙文 瑜教授在文献f 6 0 q y 将这种白适应的策略推广到非单i 周f i , j 情形 利用负曲率方向的良好性质也可以证明信赖域矗法的强收敛性质，详见文献p 圳 对予约束优化问题，m o g u e r z a 和p r i e t o 在文献f 3 6 j 中利用内点法处理非凸问题，并探索 利用负曲率方向确保迭代点列收敛剑二阶k k t 点这说明了充分利用负曲率信息对于提高 约束优化问题解的稳定性也是有帮助的 信赖域疗法以其卓越的理论性质捌良好的数值表现而备受青眯在每4 步迭代中，信赖 域方法首先在当前送代点附近定义卟可以信赖的区域，在此区域内，我们认为模型函数是 目标函数的- 个充分的近似然后，我们在此区域内选择模型函数的。个近似极小点作为f 步迭代点最甲的关于信赖域方法的阶收敛性的分析可见p o w e l l 的文献| 4 1 4 2 i 他证 明了信赖域方法存在个子列收敛到阶稳定点t h o m a s 在他的蹲十论文 4 7 q a 加强了这 结果，证明了迭代序列的所有极限点都是。阶稳定点s o r e n s e n 在文献f 4 1 5 1 中证明了信赖 域方法能够收敛到二阶稳定点f l e t c h e r 在他的专著f 1 2 ：t h e o r e m5 1 1 1 中也得到了这一结 果 定义信赖域子问题需要用到范数，其中攮常用的是欧氏范数l l 和无穷范数”8 。， 及其某些加权形式，如果我们用无穷范数，实际上就相当于在变量的两侧j j 玎上简单界约 束w i l s o n 的博十论文f 5 4 1 可能足最早使用基于无穷范数的信赖域予问题和目标函数的二次 模型逼近的方法 散情况f ，解基于无穷范数的信赖域子问题总比解基于欧氏范数的信赖 域子问题要容易些但是，在理论上相对要弱一些，阕此，在本论文中，我们用欧氏范数 定义信赖域子问题 m o r d 和s o r e n s e n 的方法f 3 8 1 有可能是求基于欧氏范数的信赖域子问题的一个近似解的 1 返埋我们假址目标函数的h e s s i a n 阼足稠褂的，或青4 ；具有特 殊的稀疏纳构网此无法利用稀疏矩l 咋的一些 直接分解技巧 1 1 解无约束优化问题的一般方法 3 最老于睦故的方法对于中小规馍问题，这种基于矩阵c h o l k y 分解的方法通常可以求得 信赖域子问题的+ 个精度很高的全局摄优解但是，列予大规模问题，我们主要关心迭代 法s t e i h a u g 在文献4 6 和t o i n t 在文献1 4 8 1 中分别独立提出用截断共轭梯度法解信赖域子 问题其主要思想是考虑连接共轭梯度迭代点之间的分片线性路径，当该分h 线性路释离 开信赖域时就进行截断由于通过该方法产生的点至少不会比c a u c h y 点差，所以该方法的 全局收敛性质是不难证明的但是，共轭梯度迭代过程基本上与信赖域边界没有关系，除 非分h 线性路径到达信赖域边界数值实验表明，该方法通常在最初的几步迭代中，在很 多情况f 往往就是在第一一步达代，就被截断这样，该方法返州的信赖域子问题的近似解 通常与c a u c h y 点相差不远这就意味着该方法在理论上全局收敛但是在实际上往往不收 敛为克服上述问题，g o u l d ，l u c i d i ，r o m a 耳l l t o i n t 在文献f 2 3 1 中提出了解信赖域子问题 的l a n c z o s 方法该方法将共轭梯度迭代过程弓信赖域边界条竹：有机的结合起来专共轭 梯度迭代过程察觉信赖域子问题的解落在边界上时研究发现信赖域子问题在迭代生成 的k r y l o v 子空问上具有非常特殊的结构作者深入考虑了这种结构，并利用这- 特征提高了 信赖域子问题解的精度 在相邻的两个不同豹迭代点之间，信赖域方法有可能需要解模型函数相同，但信赖域半 径不同的多个信赖域子问题，这主要是由于一开始选择的信赖域半释偏大造成的注意剑解 一个信赖域子问题需要消耗大量宝贵的计算时间，冈此，我们不必局限于简单的缩小信赖域 半径，而是沿着信赖域迭代步进行后退线援索，这样做方面可以避免解信赖域子问题，1 了 省宝贵的计算时间，3 方面可以找到个更好的近似最优点，促进迭代点列逼近最优点 t o i n t 在文献f 4 8 1 中描述了一。种在信赖域内部引进线搜索的h 法，这种疗法主要是基 于如f 事实：在信赖域内部用+ 个点圣代链当前迭代点2 k ，其中，( 岔kj 0 ，m 1 使得 ，( 。) i f - f 3 j l g ( z ) l lsg 和 “h ( z ) 1 i 矿( 1 ，5 1 ) 对所有的点z n 都成立 第二章渐弱过滤集技术 在本章中，我们蓠先川顾f 多维过滤熊技术【2 1 2 5 ，27 】，随后分析并指出其在线搜索 方法中的某种局限性然后，我们提出种新的渐弱过滤集技术，其将更适用于解无约束优 化闷题的线搜索方法最后，我们给出新的渐弱过滤集技术的个重要性质 第2 1 节多维过滤集技术 过滤集的概念是基于占优的：我们说点1 优于点z 2 ，就是说 9 f ( 茁1 ) i 0 2 - k = 0 初始化渐 1 1 3 2 渐弱过滤集二阶线搜索算法 1 2 弱过滤集，= 毋选择昂，( z o ) 和渐弱函数烈n ) ，置逻辑参数n o n c o n v e xtf a l s e 步1 ：停机准则 计算梯度g 的值若瓠i | = o j l u o n c o n v e x = f a l s e ，则停止计算 步2 ：计算搜索方向 计算一对下降方向( 8 e d k ) 满足( 3 1 1 ) 和( 3 1 2 ) 若局部二次模型函数“非凸， 置n o n c o n v e x = t r u e ，否则置n o n c o n v e x - f a l s e 步3 ：选择搜索方向 若交换条件 揣 ，( 茁七) + pf 珊蘸d 膏+ 弓tm 2 _ 。t h 。d 七) ， ( 3 2 3 ) 、 。 选择a k = 珊，其中z 是满足如下条件的最小的正整数 ，( z + 口k d k ) sf ( x k ) + ，上( o t 9 j d + o i 一2 _ t hd k ) ( 3 2 4 ) 。 否则，选择o = j ，f 啦，其中2 是满足( 3 2 4 ) 和( 3 2 5 ) 的最大的非负整数 ，( z + 芳如) ，( z m ) + p ( 警g j 蟊+ ；( 芳) 2 d j 帆巩) ( 3 2 5 ) 置2 k + l = 2 + n d k ，靠+ 1 = ，( z 知+ 1 ) ，七= 南+ 1 并且重新初始化渐弱过滤 集，= o ，然后转步1 注意到在算法的步4 ( b ) ，即渐弱过滤集迭代中。需要判断试验点z ：是否同时满足二个 条件：一、n o n c o n v e x f a l s e ；二、，( z ) ，。；二、z ；满足渐弱过滤集，的接收准 划( 23 1 ) 其中前两个条什用的数据是已知的，故容易判断；但第二个条什需要先求z 处 的梯度值g 佃吉) ，然后j 。能进行判断为了节省梯度值求值次数，我们通常先判断前两个条 3 , 3 二阶收敛性分析 1 3 件是否满足若满足，则求梯度值g 恤：) 并判断第二个条件若不满足，则直接跳过渐弱过 滤集迭代，从而节省次梯度求值 我们考虑大规模问题，若梯度向量空间r ”的维数很大，我们保存过滤集元素就需要大 量的存储空间，并且在比较试验点与过滤集元素的占优关系时，访问这些元素义需要很多宝 贵的计算时间所以，存实际上，我们考虑将梯度向量的某些分量想进行合并，从面构造4 个维数较小的过滤袋结构这种思想比较洋细的表述可见文献【2 1 ，2 5 2 7 1 第3 3 节二阶收敛性分析 现在，我们分析渐弱过滤集二阶线搜索算法的全局收敛性若算法只执行了有限步就停 止，则由停机准则，该点即为二阶稳定点f 面，仅讨论算法迭代了无穷次的情形，我们考 虑迭代点列的极限点的性质 为了便于分析，我们定义以f 一。些迭代点的指标集； c 竺 l 第k 步是渐弱过滤棠迭代 譬 女f 第女步是梯度相关方向迭代 坛”詈f i 第k 步是负曲率方向迭代) 显然，上述指标集两两不相交 不欠般性，我们可以假定在算法开始时f o = 厂( 2 0 ) ，则有第。章的假设条件a l a 2 可知，所有的迭代点及其极限点都在水平集冲目2 是紧的注意剑渐弱过滤集二阶线搜 索算法中f 最 的设置，我们有如下引理 引理3 3 1 - l k ：d = 衄 则有 巩 单调非增，且 凡，) 严格单调下降进一步的， 对所有的k 0 ，有 k f ( z o ) 一f f x k + 1 ) 喝一乃+ 1 】 ( 3 3 ，1 ) j = o 证明由渐弱过滤集二阶线搜索算法中最的设置，可得 民+ ，= 弓 钉出( 3 3 3 ) 和最的设置，我们有 ，( 七o ) 一f ( z k + 1 ) = f ( x , j ) 一，( 霉 r 1 ) + ，( z 竹+ 1 ) 一，( 2 七十1 ) 奸 2 孵一乃+ l j + 以一l 一最“ j = o k = 旧研】 3 3 二阶收敛性分析 1 4 冈此，不等式( 3 3 1 ) 成立 首先，我们证明如果渐弱过滤棠二阶线搜索算法，“尘的迭代点列 。卜p 有无穷多个迭 代点是由负曲率方向选代产生的，即i 坛d i = + ) 。时，算法广：生的迭代点列收敛到二阶稳定 点 定理3 3 2若假设a 1 a 2 成立，且i d i = + 则渐弱过滤集二阶线搜索算法产生 的迭代点列 z 收敛到二阶稳定点 证明 我们记 。hj 咒d ) 由 3 t 理3 3 ，1 知 f k 以及 ，( 。h ) ) 关于7 是严格单调卜降的 再由文献f 2 2 1 中的定理3 1 的证明过程可以证得算法，“生的迭代点列收敛到二阶稳定点证 申 三 现在，我们仅需要考虑迭代点列 z k 中仅有有限多个负曲率方向迭代点即假 设f d + 。， 援一r 来，我们考虑仅有有限多个渐弱过滤集迭代的情形，则梯度相关方向迭代必有无穷 步由于从一一个点列中删除有限个点升不影响其极限点的性质因此，我们可以假设算法t 2 尘的迭代都足梯度相关方向迭代，同样的，出文献f 2 2 】中的定理3 1 可得如卜定理， 定理3 3 3若假设a 1 a 2 成立如果i d i + e e r i e f l + 。则i 5 l = + o o ，渐 弱过滤集二阶线搜索算法产生的迭代点列和k ) 收敛到二阶稳定点 最石，我们还将考虑余卜的种情形，即迭代点列中仅有有限多个负曲率方向迭代点， 但是却有无限多个渐弱过滤榘迭代点，即i k d i + ，但是i 丘”l = + o 。我们有如卜0 理 定理3 3 4 若假设a 1 a 2 成立如果i d i 0 是。个正的常数 由于1 瓦d l 一号。j 乳 3 4 数值实验 1 5 堕篇竽刈裔 现在，我们从指标榘1 中提取个子列，其指标j 面1 c 1 ，满足 z t 一4 ，且南+ 由( 3 3 7 ) ，我们取极限女一可得( 1 一卢) 9 知+ ) 7 8 + 0 进一步的有 g ( 矿) 7 8 + 0 ， 由梯度相关条件( 3 1 1 1 可得 一i i s k i il l g i lsg j s i 一c 1i l g k l l 2 0 ， 冈此1 1 8 8 c 1 i 阢从而有 一 哿 _ e l 肌。 因此，当k ，一2 且趋于无穷时有 9 ( 2 4 ) t s 一i i g ( 2 ) i ts e ( 3 3 7 ) ( 3 3 8 ) 这于不等式( 3 3 8 ) 矛盾冈此假设( 3 35 ) 不成立，即有9 ( ) = 0 ，因此，( 3 3 g ) v 4 i i e 由假设算法产生的迭代点列收敛到惟一一极限点z + ，则易知g ( z + ) = 0 由于i 尼9 i = + ，即在无穷多个点处的局部二次模型非p q ，x 由目标函数，b ) 二阶连续可微，我们可知 极限点z + 处的h e s s l m l 阵h 佃+ ) 正半定所以$ 是二阶稳定点 口 第3 4 节数值实验 现在，我们看一一f 新算法的数值表现为此，我们从c u t e r 钡j j 试问题集( 参考b o n g a x t z ， c o r m ，g o u l d 希j t o i n t 的文献【2 】与i g o u l d ，o r b a n 和1 b i n t 的文献【2 4 】) 中挑选了5 5 个无约束 最优化问题，其变量的维数从2 至u o o o o 不等，详见袭3 1 每一个测试函数都使用默认的初始点，并且使用精确二阶导数，新算法的参数设载如 f ： 肛= l o 一4 ，芦= 0 5 ，r = 2 0 ，啪= 1 沿负曲率方向搜索时，初始步长吼设为最近次负曲率方向迭代步的步长我们选择 f o = n f i n 1 0 6 i f ( = o ) 1 ，( z o ) + 1 0 0 0 对于渐弱过滤集，我们取渐弱函数 如，= 一与 ) 9 = r a i n o o 。- ，去) 最后，当卜列条什满足时，算法停止 舵f ( z k 川1 0 6 而 且 n o n c o n v e x ；f a l s e 3 4 数值实验 n o p r o b t e mdn o p r o b l e mn lb a r d32 9h i m m e l b h2 2b i g g s 363 0h u m p s 2 3b i g g s 563 1l i a r w h di 0 0 0 0 4b r o w n d e n 4 3 2l m l n s u r f5 6 2 5 5c h a i n w o o4 0 0 03 3m a r a t o s b2 ， 6c h n r o s n b5 03 4m s q r t b l s1 0 2 4 7c u b e23 5n l h i s u r f5 6 2 5 8c u r l y l o1 0 0 0 03 6n o n d q u a r1 0 0 0 0 9c u r l y 2 01 0 0 0 03 7o s b o r n e a5 1 0d e c o n v u 6 1 3 8o s b o r n e bl l 1 1d i x m a a n a 3 0 0 03 9p a l m e r l c 8 1 2d m a a n f3 0 0 04 0p e n a l ，r y l1 0 0 0 1 3d i x m a a n h3 ( 1 0 04 1p f i t l l s3 1 4 d j t l 24 2p f i t 2 l s3 1 5e r r j n r o s5 04 3p f i t 3 l s 3 1 6e x t r o s n b2 0 0 0“p f i t 4 l s3 1 7f l e t c h c rl ( 0 04 5r o s e n b r2 1 8f m i n s r f 25 6 2 54 6s e n s o r s1 0 0 1 9f m i n s u r f5 6 2 54 7s i n e v a l 2 2 0f r t e u r o t h5 0 0 0 4 8 s i n q u a d 1 0 0 0 0 2 1g e n h u m p s1 0 0 04 9s n a i l2 2 2g e n r o s el o o o o5 0s p a r s l n e2 0 0 0 2 3g f “) w t h l s35 lt o i n t p s p5 0 2 4g u l f3 5 2t o u a r t i c 1 0 0 0 0 2 5h a t f l d e35 3v i b r b e a m8 2 6h e a r t 6 l s65 4w o o d s4 0 0 0 2 7h e a r t 8 l s85 5y f i t u3 2 8h e l i x3 表3 ，l ：c u t e r 测试函数名及其维数 3 ，4 数值实验 1 7 若新算法的迭代次数超j 生：o o o o 次或者计算时问超过1 0 0 0 砂，也停止计算 我们用平面共轭梯度法【8 ：l o j 来计算f 降力。向对( s 女，d k ) 我们近似解子问题v m ( z + 8 1 = o ：当s 满足条什 i i x 7 m e ( z t + s ) 雌m i n 而面翮而忑丽旧m t ( 酬 时，得剑一个较好的梯度相关方向，其中e 是机器精度；或者发现负曲率之后继续迭 代1 0 0 次，我们认为得到了个较好的负曲率方向，冈此，返川r 降方向对( s ，也) ，j 外， 若共轭梯度迭代次数达到或超过其理论上界( 即n ) 时，也返川 我们测试了两种不同的算法：一一个是本章看苹讨论的渐弱过滤集二阶线搜索算 法( d f l s ) ，3 个是文献2 2 1 t 扣的( a l s ) 算法在5 5 个测试问题中，d f l s 成功解决了9 3 ， 其中河题f m l n s r f 2 ，f m l n s u r f ，l m i n s u r f ，n l m s u r f 这四个问题冈超过了计算时间 而停止而a l s 解决了8 4 ，其中问题b r o w n d e n ，d j t l p a l m e r l c v i b r b e a m 这 四个问题超过了最大迭代次数，c u r i 1 0 c u r l y 2 0 ，f r e u r o t h g e n r o s e ，s i n - q u a d 这五个问题超过了计算时间从这里可以看出d f l s 算法 l a l s 算法更强健，说h 月了 渐弱过滤榘技术是个非常有效，值得研究的课题 图3 1 ：d f l s 和a l s 算法解e x t r o s n b i = 7 题时的目标函数值- 5 迭代次数的变化关系图 接卜- 来，我们给出图3l ，展示了d f l s 和a l s 算法解e x t r o s n b 问题时的目标函数值 随着迭代次数的变化关系这从一个方面解释了渐弱过滤集技术成功的原闳从图上可以看 出渐弱过滤集方法产生的迭代点的目标函数值具有明显的摆动行为然而却不影响其全局二 酚收敛的良好性质 根据d o m n 和m o r 6 的文献| 5 1 ，我们绐i f , 了两个算法的执行行为对比图分别从目标函 数值水值次数( 图3 2 ) ，梯度值求值次数( 图3 3 ) ，迭代次数( 图3 4 ) ，共轭梯度迭代 次数( 图3 5 ) 和计算时问( 图3 6 ) 五个方面进行比较从图3 2 和3 3 可以看出，新算法的 3 4 数值实验 1 8 图3 2 ：目标函数值求值次数 圈3 j 3 ：梯度值求值次数 3 4 数值实验 1 9 图3 4 ：迭代次数 图3 5 ：共轭梯度迭代次数 3 4 数值实验 2 0 图3 6 ：计算时问 目标函数值求值次数和梯度值求值次数比a l s 算法要少。些，执行效率要高些但是梯 度值求值次数的效率不如目标函数值求值次数来得显著，这主要是由于渐弱过滤榘技术的 商用依赖于梯度信息的收集图3 4 取j 3 5 说明了新算法在迭代次数和共轭梯度迭代次数方面 比a l s 算法要提高很多但是，遗憾的是在图3 6 中，我们没有看到这种优势在计算时间方 面有什么辊兽的体现这主要是出于，访问、比较、添加和删除渐弱过滤集元素消耗的计算 时问比较多，从而抵消了这种优势特别是对大规模问题，应用渐弱过滤集技术，在计算时 间方面的消耗将是一个不容忽视的问题 在我们的f o r t r a n 9 0 程序中我们用链袭来对渐弱过滤集进行操作图3 7 给出了渐弱过 滤集迭代步弓需要保存的渐弱过滤集元素的大小的刘比圈我们可以看出：在5 1 个d f l s 算 法成功解出的测试问题中，大部分测试问题( 4 9 个) 需要存储的渐弱过滤榘元素不超 过2 1 个，除了f l e t c t t c r 问题的4 9 4 个和t o i n t p s p 问题自 j 1 3 8 个在图3 8 中我们给出 存储