（应用数学专业论文）求无约束优化问题的过滤器算法.pdf

摘要 在第一章里，在介绍了课题研究意义、国内外现状分析以及简述了过滤器算法的发 展史之后，我们概述了无约束优化问题的最优性条件与求解无约束优化问题的基本模 型，并在指出了常用的下降算法之后，我们介绍了两种线性搜索，在确定下降方向吼之 后，通过线性搜索来确定搜索步长口。同时，将优化问题的序列二次规划算法作一个简 单的回顾之后，通过定义，引出过滤器算法的基本思想 第二章我们概述了拟n e w t 衄算法，就它的产生过程，做出了分析同时给出了一般 的算法步骤及收敛性结果并且阐述了修正拟n c w 咖l 算法，它是在拟n t 研自咂算法基础 上考虑目标函数非凸的情况，而参数的选取至关重要同时给出了一种选取方式接下 来描述了采用线性搜索的修正拟n 州衄算法，并给出了它的全局收敛性与超线性收敛 性 第三章里，我们讨论了求解无约束优化问题的信赖域算法阐述了该算法的基本结 构，并且简要介绍了算法的收敛性结果之后，介绍了信赖域算法应用于序列二次规划产 生的信赖域s q p 算法，同时也给出了该算法的收敛性结果最后介绍了经典的s q p 型过 滤器算法以及它的收敛性结果 在第四章里我们考虑无约束优化问题 磐，o )= 飒 是否接受以+ 嚷敏为新的迭代点时，其中实值函数，：一r 是二次连续可微的，构造 了一个求解无约束优化问题的新算法一求无约束优化问题的过滤器m b f g s 算法该 算法结合了修正b f g s ( m b f g s ) 算法的思想和多维过滤器算法策略一方面，搜索方向 的产生类似于m b f g s 算法；另一方面，在接受新的迭代点时，采用多维过滤器算法的 策略新算法是全局收敛的最后给出了该算法的数值试验 关键词：无约束优化；线性搜索；过滤器；拟n e w t 叫算法；m b f ( ；s 算法；信赖域算 法；多维过滤器 a b s t r a c t hf i r s tc h 印t e r ，w es u m m 捌z et h e 叩t i m a l 咖d i t i 彻s0 fu n c 0 璐蜘n c d 叩t i m i z a t i o n 柚d i t sb 硒i cm o d c lf b rs o l v i n g ，柚ds u m m a i i z cab r i c fh i s t o r yo ff i l t c fm e t h o d s ，a f t 盯i n _ 眦d u c 抽g t h ei n v e s t i 鲥i l l gs i g n i f i c a n c co ft h cq u 鼯t i o nf o rd i s c l l 鹦i o n 弛di 忸i n v e s t i g a t i o na c t u a l i t ya l l o 、，盯t h ew o d d 削a f t e ro 肌血gt h cc o m m d e c l i n ea l g o r i t h mw ei n 们d u c e 由哪m e 嘶d s o f1 i n es e 砌a f t c rt h ec 0 曲a t i o no ft h ed c c l i n cd i r e d i o n 噍，t h es e 盯c h j n gs t 印- s i 口t w mb ec o n 丘皿c db yt h cl i n es e a r c h a tt h cs 锄e 缸e ，w eb r i e n ym a k cas i m p l e f c 打a 印o c fo fs ( pa l g o f ! i t h mo f 叩t i m i z a t j p f o b l e m s ，锄db y i 岵d c 丘n i t j o 硝，w ec d u c c 出e i d e 鹤0 f 坷t c rm e t h o d hs e n dc h a p t c r ，w c 锄m 砌r i z eq u 硒i n e 咖a l g o r i t l l m o ni t sg c n e r a t i p t o c c 豁，w c h a wm a d et h e 柚a l y s i s s i m u l t a l 啪憾l yw eh a v eg i v t h eg e 榭a la l g o f i t h m 吼印a n dt h c 0 0 n v e r g c n tr c s u l t s a n dw ei n 仃叫u c ct h em o d i f i e dq u 弱i n 郫咖a l 鲥t h m hi su s c dj nt h e c o n d i t i o no fn 伽n v e xo fo b j c c t i v ef i i n d i o n 帆t h eb a o fq u 勰i n e 、t o na i g o r i t h m ，w h i l e m ec h s i n go fp a 姗c t 口r ii sv e r yi m p c i n 柚t a f t c raw h i l c ，w e0 日ha c h o o s j l l gm e t h o d b y t h c w a y ，w e d e s c f i b e t h e m o d 砸e d q u 弱i n e 叭鲫a 1 9 0 r i t l l m u s c d t h e l i n e a r c h ，a n d h v c g i v 饥i t sg l o b a lc o d v e r g e n c e 牡ds u p e d i n e 盯鲫e r g c n c c m 幽c h 印t e r w ed i 锨i s s c dt n i s t r e g i a i g 嘣t h mf o rt h c 硼鹪仃a l 妯c do p t 砌2 a t i o n 觚de l a b o r a t cb 嬲i cs t m c 眦o ft h i sa l g 吲t h m ，柚di i i b 吣d u c et h e 咖v e r g c mr 鹳u l t so f t h ea l g o 枷皿晡e n y a f t e 刑a r d s ，t h e 仇l s t r c g i a l g o 棚血a p p l y 堍 s q pi si n t 刚u 砌， w e s i m u l t a n e o 吣l y h a v ea l g i v 蛆t h e n v e r g 如tr 髓u l t so ft h ea l g 面t h 】札 f i n a l l yw e i n 仃0 d u c cn ”c l a s s i c a ls q pf i l t c ra l g o r i t h m 勰w e h 勰i 忸c o n v e r g e n tf 鹤u l t s a 且di nf o u n hc ：h a p t e r ，w eh v ed i s c u s sa 埘1 c 阻s 仃a i n e do p t i m a lp l _ o b l e m 卿， ) ， w h e r e ，：彤_ ri s 咖t i n u o u s l yd u a l - d i 疵啪t i a b l e ，w h 跖c o 璐i d e 血g 搬印t i n g 以+ 吼以勰an c wu p d a t i n gp o i n t w ec 0 咖c tan 哪a 1 9 0 r i t h mf o r 蝴蛐c d 叩t i l n i z a t i o 璐皿ea l g o r i t h mc o m b i n 髂t h ci d o fm b f g sm e t h o d 训t ht h es t r a t e g yo f 删n i d i m 卿i 伽i a l 丘n c ra l g o r i t h m o n es i d e ，t h ep i o d u c co f 舡c h i n gd i r 鳅i i ss i m i l 缸t o m b f g sm e t h o d ；t h co t h c rh a n d ，w h 朋n 圮n 钾p o i n tw i nb ca c c c p t c d w ea d o p t 也c s 打a t e g yo fm u l t j d i m e 璐i 伽a l 矗l t c fa l 鲥t h m ha d d i f j o n ，t h en e wa l 鲥m mh a sa 罾。砌 c o n v e f g 锄f i n a l l yw eo 断t h ea i g o r i t h 】叮，st r i a lo f 硼m c i i c a lv a l u e k e yw o r d s ：蛐e 蚰s t r a i e do p 痂n i 蠲h 蚰；h n es 1 1 c h ；石l t e r ；q n 懿i - n e w t o n m e 恤o d m b f g s a 1 9 0 一t h m s ；t n 塔t - r e g i o na i 印r i t h m s 舢i 蛞- d i m 如s i o n 埘t 盯 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写的成果作品对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明本人完全意识到本声明的法律后果由本人承担 作者签名：棘仁日期：砷年岁月2 2 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅 本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密团 ( 请在以上相应方框内打“”) 作者签名：太彳，；日期：力夕年芗月2 2 日 导师签名：划堤冶 日期：2 7 年岁月3 二日 第一章引言 1 1 课题研究意义、现状分析 过滤器算法是由f l e t c h c r - k y 断在1 9 9 7 年首次在文i l j 中提出，其主要目的是为了克 服利用罚函数求解非线性约束优化问题时，因罚参数太大或太小而造成的数值计算上的困 难当时主要结合序列二次规划方法、信赖域方法用于求解非线性约束优化问题，算法直接 以目标函数作为价值函数，因而有效地直接以目标函数作为价值函数，过滤器算法不仅数 值计算上效果好，并且在一定条件下，具有全局收敛性和超线性收敛性见文献 2 ， 3 自从f l e “c h e r - k 蛐f c r 提出过滤器算法到现在，由于过滤器算法本身的优势，该算法已 经广泛与各种算法结合起来应用与各种问题比如从2 0 0 0 年到2 0 0 5 年，r 日e 自c h 、s k y 断 与n lm c 0 u l d 等人将过滤器算法应用于求非线性规划( n u p ) 问题，发表诸如s q p 一过 滤器算法，过滤器信赖域算法等等! 见文献 2 ， 4 而第一个有关过滤器算法的全局收敛 性证明则是应用于序列线性规划( s l p ) ，见文献 5 这种证明后来在s q p 一过滤器算法得到 了总结他们将这些算法应用于非线性规划问题的求解，都产生了较好的效果 过滤器算法已经广泛渗透到其它优化领域，比如非线性等式约束问题、非序列规划问 题，见文献 4 ， 6 ， 7 ；还有非光滑优化问题，见文献 8 ， 9 ， 1 0 在各种拟n c 叭0 n 法的基础上，我们计划探讨多种拟n e 嘶法与过滤器算法结合起来， 应用于非线性优化问题并且应用于更广泛的情况g o u l d 等人在文州中利用过滤器的思想 去解非线性方程组，受其中思想的启发，很自然的想到把过滤器思想用到无约束优化问题 中，因为，无约束优化问题的求解就相当于求解非线性方程组w o ) 一o 另外，2 0 0 3 年，出现了求解无约束问题的n 嘲过滤器算法，产生了较好的效果众所周知，拟n e 叭 法克服了n 怕n 法的许多不足，修正拟n e 叭加法又克服了拟n e 咖n 法的许多不足，如 它没有对目标函数有凸性的要求因此，我们设想把拟- k t o n 、修正拟n e 咖n 法等与过滤 器思想相结合，构造出更好的混合算法 首先回顾求解无约束优化问题拟n e 耐衄法、过滤器算法、以及信赖域算法，在此基础 构造拟n e w 协n 法、信赖域算法与过滤器算法的混合算法，并且探讨他们的收敛性和收敛 速度最后，给出针对某些具体问题做了数值实验 1 2 无约束优化问题的最优性条件 最优化问题的数学模型如下： m i 丑，0 ) ，z d ( 1 2 1 ) 实值函数，：r “一r ，称为问题( 1 2 1 ) 的目标函数，集合d 为问题的可行域当d 一彤 时我们称( 1 2 1 ) 为无约束优化问题，而当d c 尺”时称为约束优化问题 最优化问题的解分为局部最优解和全局最优解，其定义如下： 定义1 2 1 设点z d ，若存在工的一个领域 ) 鲈r 4 肛一工9 ( 6 ) ，使得如 下不等式成立： ，g ) ，o ) ，d n u 。o ) ， ( 1 - 2 2 ) 则称工是( 1 2 1 ) 的一个局部最优解；若不等式( 1 1 2 ) 对所有的z d n o ) 忸成 立严格不等式，则称工是( 1 2 1 ) 的一个严格局部最优解若不等式 ，o ) 量，o ) ，协：d ( 1 2 3 ) 成立，则称工是( 1 2 1 ) 的一个全局最优解；若不等式( 1 2 3 ) 对所有的茗d 缸 成立 严格不等式，则称z 是( 1 2 1 ) 的一个严格全局最优解 我们考虑如下无约束优化问题 磐，o ) 其中实值函数，：彤一r ( 1 2 4 ) 下面的定理给出了点工+ 是无约束优化问题( 1 2 4 ) 的局部最优性的必要条件 定理1 2 1 设函数，：彤一只连续可微，工是无约束优化问题( 1 2 4 ) 的局部最优解 则工满足： 一 w ) - 0 无约束优化问题( 1 2 4 ) 的二阶必要条件由下面的定理给出 定理1 2 2 设函数，：r 一只二次连续可微，z 是无约束优化问题( 1 2 4 ) 的一个局 部最优解则x + 满足：v ，0 ) 一o ，并且v 2 ，o ) 半正定 下面的定理给出一个无约束优化问题( 1 2 4 ) 的二阶充分条件 定理1 2 3 设函数，：彤一只二次连续可微，若工满足：v 厂o ) 一o ，并且v 2 ，0 ) 正定，则石是无约束优化问题( 1 2 4 ) 的一个局部最优解 可以看出目标函数，的性质对问题的解决尤为重要，接下来我们简要介绍凸函数的概 念与性质 定义1 2 2 设s r “是凸集，若函数，：彤一r 满足； ，( c 噬+ ( 1 一口) ) ，) q r ( x ) + ( 1 一a ) ，( ) ，) ，、k ，y s ，v 口【o ，l 】 ( 1 2 5 ) 则称，是s 上的凸函数 下面定理给出了凸函数的几个等价性条件 定理1 2 4 设函数，：彤一r 二次连续可微，则下面的命题等价： ( 1 ) 函数，是凸函数， ( 2 ) 对魄，y r 6 ，一元函数伊o ) 垒， + ( 1 一f ) ) ，) 是【叫上的凸函数 ( 3 ) 对慨，y r 4 ，下面的不等式成立： 2 ，o ) 一，( y ) 芑v ，( y ) 1 一y ) ( 4 ) 梯度函数w 单调，即： ( v ，o ) 一v ，0 ) ) 7 一y ) 之0 ，) ，r “ ( 5 ) 对所有的工r 4 ，v 2 ， ) 半正定 下面的定理说明，若厂是凸函数，则，的任何局部极小值点也是其全局最小值点而 且，极值的一阶必要条件也是充分条件 定理1 2 5 设函数，：r “一矗连续可微的凸函数，则，的任何局部极小值点也是其全 局最小值点而且，x 是无约束优化问题( 1 2 4 ) 的解的充要条件是z + 满足 v ， ) = o 1 3 解无约束优化问题算法的基本模型 求解无约束优化问题( 1 2 4 ) 时，我们通常采用下降算法当给出函数，在点工处的下 降方向d 及确定下降方向的方式，在此基础上可以构造求解无约束优化问题( 1 2 4 ) 的下 降算法其基本思想是从初始点出发，按照使目标函数值下降的原则构造点列饥 ，即 点列协。 满足条件： ，瓴。) t ，瓴) ，v 七一咄 算法的最终目的是使点列 k ) 中的某个点或某个极限点是问题( 1 2 4 ) 的解或稳定点 以作为函数，在以处的下降方向，则满足： w 纯) 4 以c 0 ， 从而，当口，o 充分小时， ，瓴+ 础。) ，瓴) 成立因此，可取黾。黾+ a 。以，其中，o ，使得，( 磁+ 吼以) c ，( h ) 在此基础上我 们给出求解无约束优化问题( 1 2 4 ) 的下降算法的一般步骤如下： 算法1 3 1 ( 求解无约束优化问题的下降算法) 步0 ( 初始化) 给定初始点r 。，精度f o 设七一0 步1 当i 阿( k 川e 时，算法终止，得解以否则，转步2 步2确定下降方向以，使得 w 瓴) 1 丸t o 步3 确定步长口。，o ，使得 ，瓴+ 吼噍) 0 ，使得 ，纯+ 吼) s ，纯) + q q w 瓴y 以 ( 1 4 1 ) 在a | 胁i j o 型线性搜索中，可取步长叹为集合 户p ，f 一0 ：1 1 ，中使得不等式( 1 4 1 ) 成 立的最大者，即所谓的回朔方法删。型线性搜索可通过以下算法实现 算法1 4 1 渔蜘嘶。型线性搜索) 步0 若吼一1 满足( 1 4 1 ) ，则取吼一1 否则转下一步 步l 给定常数，0 ，p ( 呐令口。一 步2 若嗄满足( 1 4 1 ) ，则终止计算，并得步长嘎否则，转步3 。 步3 令以- 触，转步2 在a r m i j o 型线性搜索中，我们首先考虑a 。一1 满足( 1 4 1 ) ，因为步长为1 是算法超线 性收敛性的必要条件然后试探步按比例p 缩小若p ( 0 山较大，则相邻两次试探步相对 较小，此时，需要经过较多次搜索才能得到着p ( 哟较小( 如p 接近于o ) ，则相邻两次 试探步的改变相对较大，此时，可经过相对较少的试探步得至0 q ，但获得的步长q 可能很 小为了克服a m i j o 型线性搜索的这一缺陷，可采用下面的w 挑f c p o w c u 型非精确线性搜 索 w o i f e - p o w e h 型线性搜索：给定常数吼，盯2 满足o q ( 妄，吼盯2 1 取吼o 使得 l ，q t + a t d t ：， t ) + 盯产t 叼t ) 2 d t ( 1 4 2 ) iv 瓴+ 口。噍) 1 畋之v ，) 1 以 w b l f c p a w e 型线性搜索可通过下面的过程实现：首先，按a 衄崎。型线性搜索确定初始 点n ：o ) 一卢p i ( 1 是某个正的或负的整数) ，使得a o ) 满足( 1 4 2 ) 中的第一个不等式此时， p 1 口 o ) 垒艇不满足( 1 4 2 ) 中的第一个不等式若口 o ) 满足( 1 4 2 ) 中的第二个不等式，则 令吒- 口 o ) 否则，取岛( 哟，令口 1 ) 为集合忙 0 + 硝( 卢p 一口0 ) ，f - 吡 中使得( 1 4 2 ) 中的第一个不等式成立的最大者若a 1 ) 满足( 1 4 2 ) 中的第二个不等式，则令一口p 否 则，令声p 一所1 a ：1 ) 重复此过程，直至得到某个口l f 同时满足( 1 4 2 ) 中两个不等式以上 过程可总结为如下算法： 算法1 4 2 ( w o l f e p o w e n 型线性搜索) 4 步o 若一1 满足( 1 4 2 ) ，则取吒一1 否则转下一步 步1 给定常数卢 o ，j d ，p ，( o 山令口 o ) 为集合 励，f o ，1 ，2 中使得( 1 4 2 ) 中 的第一个不等式成立的最大者令f ，o 步2 若满足( 1 4 2 ) 中的第二个不等式，则终止计算，并得步长嚷一秽否则， 令麒一p - 1 口f 转步3 步3 令口? 哪为集合扣 + p ：( 甜一口f ) ，f o 工 中使得( 1 4 2 ) 中的第一个不等式 成立的最大者令f - f + 1 转步2 1 5 过滤器算法概述 我们先对序列二次规划算法作一个简单的回顾，然后给出算法的收敛性 设，：r 4 一且二次连续可微；c ：一r “同样二次连续可微，考察如下约束最优化 问题： 面密妇， ) 删龟f p d 幻c j o ) = o ，f - 1 ，2 ，m 。； c f 0 ) s 0 ，f 小。+ 1 ，肌 ( 1 5 1 ) 设是问题( 1 5 1 ) 的一个局部最优解且在此处某种约束规格成立，则存在向量刀r ” 使得： f v ，l ，r ) 。o ； c j ) 一o ，f 一1 2 ，历。 ( 1 5 2 ) i 乏0 c f ) s o + c j ) - of 坍。+ 1 ，册 其中l 称为问题( 1 5 1 ) 的l a g r a n 画趾函数，其定义为 工 ，a ) - ，o ) + z c t o ) ( 1 5 3 ) 其中向量刀称为相应的l a g r a n 百柚乘子 序列二次规划( s q p ) 算法是求解约束最优化问题( 1 5 1 ) 的有效算法，大量的数值 计算表明，它尤其对中、小规模的求解效果很好 s q p 算法的基本思想是利用一系列二次规划问题逼近约束问题( 1 5 1 ) ，使二次规划 问题的解逐次逼近约束问题( 1 5 1 ) 的解设缸。，九) 是s q p 算法产生的点列，则在处， s q p 算法的q p 子问题为如下二次规划问题： m 1 密切v ，o ) 7 d + 争7 口t d 蹦蜘c f 幻乳瓴y d + c j 瓴) = of 一1 ，2 ， 5 v c f ( 并t ) 7 d + c j ( x t ) 0 fi + 1 ，m( 1 5 4 ) 其中巩是问题( 1 5 1 ) 的b g r a n g i 蛆函数在瓴，九) 处的h e 辐i 孤阵或它的近似设以是 子问题( 1 5 4 ) 的解，l 是相应的b 伊蛐西a n 乘子，则下一个迭代点由。- 毛+ d i 及 九。- 九+ l 确定 使s q p 算法具有全局收敛性通常有两种途径，其一是在局部算法中引入线性搜索，使 算法的子问题产生的方向是某个效益函数的下降方向。约束问题的效益函数通常是某种罚 函数，罚函数满足如下性质：在问题的可行域内部，罚函数的值与问题的目标函数值相等， 而在可行域外部的点处，罚函数的值远大于目标函数值，即对可行域以外的函数值加以惩 罚，使函数在可行域外部达不到最小值 令 c + o ) 一( c ：o ) ，c ：) 7 ， ( 1 5 5 ) 其中c j o ) - c j o ) ，f 一1 ，2 ，肌。；c ? o ) - m 缸 c ， ) ，0 f - m 。+ 1 ，册 可知x 是问题 o 称为罚因子，f 是以正常数，帅是某种向量范数 可以证明，若风对称正定，罚函数( 1 5 7 ) 中取f 一1 ，范数为厶范数，则当罚因子口 充分大时，s c p 子问题( 1 。5 4 ) 产生的方向是上述罚函数在z 。处的下降方向从而，可利 用罚函数进行a m i j o 型线性搜索，即求吼( o 舯使得下面的不等式成立： p 。( x i + 口i d t ) s p ，( k ) + ，l 口i p ：( h ，d i ) ( 1 5 8 ) 其中常数满足p ( o 山，函数p 。可以是某个罚函数，p 二o ，d ) 表示函数p 。在x 处沿方向 d 的方向导数 在一定条件下，算法具有全局收敛性，如h 蛆( 1 9 7 7 ) 提出的逐步二次规划方法，实 质就是s q p 罚函数算法，该算法的全局收敛性定理如下： 定理1 5 1 假设问题( 1 5 1 ) 中的厂0 ) 和q o ) ，g = 1 ，2 ，m ；) 连续可微，存在常数， m 0 使得： 册。d 7 口。ds m 脚 对一切七和d r “都成立如果i k0 。盯对一切七均成立，则算法产生的点列 黾的任何聚 点都是问题( 1 5 1 ) 的k k t 点 6 由上面的描述可以看出，为了使s q p 算法具有全局收敛性，罚函数的罚因子盯起了很 重要的作用对罚因子盯的选取也十分重要罚因子盯太小，则算法可能不全局收敛，罚因 子太大。则容易使算法出现病态 避免使用罚函数的途径有很多，最近几年r e t c h e r k y f f c r 提出的所谓过滤器算法是一种 途径，求解约束问题的过滤器算法的思想最早是由f l e t c h e r - k y f f e r l 9 9 7 年提出来的当时 主要是为了避免在求解约束优化问题时使用罚函数 我们通过求解问题( 1 5 1 ) 来介绍过滤器算法，过滤器算法把约束问题近似地看成 一个多目标的优化问题： 磐( ， ) ，矗 其中，_ i l ( 力一m 瓤 1 0 0 ) i ，f 一1 2 ，m ) 或者j i l ( 力一k g ) i ，f 一1 ，2 ，m 我们首先介绍过滤器算法里的几个定义，为叙述方便，我们简记，瓴) ，矗瓴) 为五， 魂 定义1 5 1 所谓点支配点耳就是指 f t f l 且 s 呜 定义1 5 2 由形如( ，嚏) 的数对组成的集合被称为一个过滤器，记为f ，当且 仅当集合f 中的任何一个元素都不支配其它任何一个元素 一 有时为了方便，我们也用x ，表示( ，o ) ，j i l o ) ) f 或用f f 表示( 五，噍) ， 定义1 5 3 如果数对( ，_ 1 ) 被加入过滤器f 之后，在形成的新集合中没有一个元素 来支配它，那么称数对( ， ) 对过滤器f 是可接受的，或得称对( ，j 1 ) 可以被过滤器f 接 受 在具体的算法中，为了保证算法的收敛性，点x 对应的数对( ， ) ，1 1 0 ) ) 被过滤器f 接 受需要更严格的条件如在文“”中要求对f ，厂 ) 五一盯或者_ i lo ) ( 1 一p 池成 立，在文“4 中则要求对v f f ，要么， ) s 五一仃成立，要么_ i l o ) s ( 1 一p 溉成立，其 中， o ，盯都是很小的正数 过滤器算法还有一个必不可少的步骤，即恢复步该步的作用是通过求解无约束优化 问题 磐_ l 找到一个更可行且可被当前过滤器接受的迭代点 如果迭代点& 对应的数对( ，噍) 支配点而数对( 五，呜) ，那么点而对我们来 说没有任何意义，这样我们只需要留下那些不被它支配的迭代点，即如果数对( ，吃) 可 7 以被过滤器f 接受，在它被加入到过滤器f 之后形成的新集合f 中，再从新集合f 中删 去所有被对( ，惋) 支配的数对但是有时只有当 0 ) s 正一盯w 不成立而点以又可 被过滤器f 接受时，才把( ，) 加入过滤器，此时称产生了一个_ i i 一步否则称为，一步 见文献 1 1 ， 1 2 我们先用一个图形来描述数对( ，k ) 加入到过滤器f 之后的作用图中的虚线点 ( ，) 满足： 氏- f k o 嗽 瓦- 眺 图1 1 过滤器中的每一个点产生一串不被接受的点，而所有这些点都表示成不被过滤器接受的集 合 8 第二章拟n e w t o n 算法 2 1 拟n e w t 佃算法概述 本章介绍求解问题( 1 2 4 ) 的拟n e 啊o n 法拟n e w t o n 法的基本思想是在n c j l ，t o n 法 的子问题( 即求解关于d 的线性方程组v 2 ，( k v + v ，( k ) - o ) 中用v 2 ， 。) 的某个近似 矩阵以r ”取代v 2 ，o 。) 矩阵反应具有如下特点： ( 1 ) 在某中意义下有巩一v 2 ，o 。) ，使得相应的算法产生的方向是n e 讯衄方向的近 似，以保证算法具有较快的速度 ( 2 ) 对所有的七，最对称正定，从而使算法产生的方向是函数，o ) 在以处的下降方 向 ( 3 ) 矩阵风容易计算 下面介绍矩阵风的构造假设函数，：胄“一只是二次连续可微，利用多元函数t a y l o r 展开得如下近似式： v ，瓴) 一v ，瓴。) 一v 2 ，瓴。) + 。一以) 所以，使巩近似于v 2 ，瓴) 的一种合理取法是：用反+ ，取代v 2 ，( h + 。) 时，上面的近似式成 立等式，即色+ 。满足方程 风“& = y i ， ( 2 1 1 ) 其中，。屯。一以，“- v ， i 。) 一v ，o t ) 方程( 2 1 1 ) 称为拟n e 叭方程注意到 - z m 一赡一吼畋拟n e 州o n 方程( 2 1 1 ) 表明取+ ，与v 2 ，( h 。) 沿方向以( 拟n e 咖方 向) 近似相等因而拟n 州帆方向是n e w t o n 方向在某种意义上的一个近似 当弗，1 时，满足拟n c 帆阻方程的矩阵吼。有很多确定b 。的原则之一是使其在计算 上容易实现已有的拟n 州o n 法通过对取进行低秩修正产生b 。，即令 也。一巩+ 九 ( 2 1 2 ) 其中，矩阵九是秩为1 或2 的矩阵下面简单介绍几种常用的拟n c w t o n 修正公式 对称秩1 ( s r l ) 修正公式如下： ”皿+ 与篙蒜竽 秩2 修正公式： ”耻鬻+ 篾 ( 2 ) 公式( 2 2 3 ) 称为b f g s 修正公式 秩2 修正拟n e 叭衄法中另一个修正公式是d 即公式，其修正公式如下： 9 小舞只c ，一舞7 一筹y ；s ty ；s ty ；s i 哪址幽杀址燮一嘴m ；( 2 )y ；s t l y i s ij 其中，足是单位矩阵 下面给出拟n e 】n o n 算法的一般步骤 算法2 l l ( 拟w t 蛐算法) 步o ( 初始化) 给定初始点z 。r 。，初始对称正定矩阵既r 一，精度，o 设 七一0 步1 当舫o 。s f 时，算法终止，得解黾否则，转步2 步2解线性方程组 b d i + v r o t ) 一o ， 得解攻 步3由删。型线性搜索或w b i f c - p o 、张n 型线性搜索确定步长吒 步4 令以。- + 口。农，若0 v ，( k 。川se ，则得解。否则由以上的某个修正公 式确定以。 步5令七一七+ 1 转步2 在给定了假设的前提下，下面的定理给出了该算法的收敛性结果 假设2 1 1 ( ，1 ) 函数，：r 1 一r 是二次连续可微 ( 2 ) 水平集 q ) 一伽月“i ，o ) s ，( ) 是凸集且函数，o ) 在q g 。) 上是一致凸函数，即存在正常数肼材，使得 册肛0 2 d 7 v 2 厂0 ) d 墨j | l ，肛i f 2 ，k q 瓴) ，d r 。 定理2 1 1 设假设2 1 1 成立，则采用w b l f c - p o w c l l 型线性搜索或a m 匈。型线性搜索 的拟n e 叭o n 算法产生的点列收敛于问题( 1 2 4 ) 在q ( h ) 上的唯一极小值点 其实上面的全局收敛性定理中的条件在采用w b 玳p o w e u 型线性搜索时，可以放宽到 函数，o ) 在g 。) 上是凸函数相应的定理所述 定理2 1 2 设，：r 。一曰是二次连续可微的凸函数，在水平集 q o 。) 一缸l ，o ) ，0 。) ) 有界，且存在常数m ，o ，使得 l p 2 ，( x ) 0 m ，、暾q 瓴) ，d r 4 1 0 则采用w b l f e p o w e u 型线性搜索的拟n e 叭o n 算法产生的点列 h ) 满足： 1 1 凹桫) 忙o 拟n e w t 咖算法的超线性收敛性定理如下： 定理2 3 2 设假设2 1 1 成立，并且设函数，的海色阵v 2 ，在z 处觑j 如妨连续，即存 在x 的领域u0 ) 及常数 ，0 ，日 0 ，使得 i l v 2 ，o ) 一v 2 ，( ) ，) 0 h 肛一y n 慨，y u ) 对所有的x 【厂0 + ) 成立，则采用w b l 缸p o w c n 型线性搜索的拟n e 叭o n 算法产生的点列 仁。) 超线性收敛于石而且，当t 充分大时，口。一1 以上定理的证明可参照文“ 2 2 拟n e w t o n 算法的修正形式( m b f g s 算法) 拟n e 吼算法的全局收敛性要求目标函数，是凸函数当用于非凸函数极小值问题 求解时，采用w b 脆p o w c n 型线性搜索的拟n e 叭算法不一定收敛为了克服拟n e 州衄 算法的缺陷，本节我们介绍拟n 洲t o n 算法的修正形式( m b f g s 算法) 设，二次连续可微，考虑到v 2 ，( k + 。) 满足 v 2 ，瓴+ ，t 。一屯) 一v ，瓴。) 一v ，瓴) 乡t 令瓦。- v 2 ，( k 。) + 吒，其中，r “是单位矩阵，_ ，o 当充分小时，有 瓦。一v 2 ，0 。) 易知，瓦。满足如下近似关系： 吼“( 】t “一茗t ) - ( v 2 厂0 0 “) + ，) ( x “。一毒t ) - r t + 瓴“一z i ) 令& 一工。一，y t w o 。) 一v ，( k ) ，y t y t + ，则得如下近似关系： q 。& - ) ，t ( 2 2 1 ) 我们可以得到m b f g s 算法对应的修正公式： ”b 一警+ 鲁 ( 2 z 2 ) 其中，s t - x i + l j 吒，) ，i - y t + 噍j ti v ，( x i “) 一v ，( 工t ) + ( x t “一以) 在修正的拟n e 叭算法中，参数飞的确定很重要为了保证b 。的对称正定性，我们通 过对参数作如下调整，使得 ) ，： o ，v 七苫o 令 _ = d 。0 v ，瓴扩， ( 2 2 3 a ) 1 1 纠+ m a x ，爵舻1 舫蚶” ( 2 2 3 b ， 其中， o 和c 0 为常数此时我们有 _ ) ， 一r h + 吼i 阿瓴) k8 2 “舫鲥2 叫”2 一卜爵，o ) 乏c 舫瓴) 悱。4 2 基于以上事实我们总结：在用m b f g s 求解( 1 1 4 ) 时，搜索方向以满足如下方程组 口i d i + v ，0 4 ) 一0 其中以r 通过以下修正公式产生： b 一等+ 尝 、 其中x i “一黾一a 。以，“- v ，( 砍“) 一w o 。) 及y t 九+ 咯，具体的可由( 2 2 3 ) 确定，其中c ，o 为常数所以我们得出如下的算法： 算法2 2 1 ( m b l g s 算法) 步o ( 初始化) 给定初始点科，初始对称正定矩阵风r ，精度，o 设七一o 步1 当l 阿也) i l f 时，算法终止，得解黾否则转步2 步2解线性方程组 以以+ w 瓴) 一o 得解以转步3 步3由a m i j o 型线性搜索或w b 掩- p a w e n 型线性搜索确定步长吼，其中吼( o ，习， 步4 令黾。- 以+ 吼d 。，若桫o 。) i l s ，则得解工。否则由修正公式( 2 2 2 ) 确定吼。，其中参数气由( 2 2 3 ) 确定 步5令七- 七+ l 转步2 2 3m b f g s 算法的收敛性结果 m b f g s 算法具有全局收敛性定理与超线性收敛性定理，我们作逐一的描述 定理2 3 1 设水平集q 0 。) - 缸r “l ，o ) s ，o 。) 有界d 是包含了q o 。) 的某个有 界闭凸集函数，o ) 在d 上连续可微，且其梯度w ) u p s c h i t z 连续，即存在常数，o 使 得 i 阿 ) 一v ，( ) ，s l 降一y i l ，坛，) ，d 则由m b f g s 算法产生的点列忸。 满足： 1 哟到耵瓴) 忙o 定理2 3 2 设下列条件成立： ( 1 ) 由m b f g s 算法产生的点列缸。) 收敛于工 ( 2 ) 函数，在茗的某领域内二次连续可微，且v ，o ) 一0 ，v 2 ，o ) 对称正定 ( 3 ) 函数，的海色阵v 2 ，在z 处觑j 妇连续，即存在z 的领域u ) 及常数 ， 0 ，日 0 ，使得 忡2 ，o ) 一v 2 ，( ) ，) 0 s 日忙一_ ) ，l r ，、k ，y u o ) ( 4 ) f ) 满足： 善坤 ( 2 3 1 ) 则仁。 超线性收敛于z 而且，当七充分大时，吼- 1 m b f g s 算法的一个重要的优点是该算法用于求解非凸函数极小值问题时也具有全局 收敛性而且， 玩 的对称正定性与算法的线性搜索以及目标函数的凸性无关 m b f g s 算法的全局收敛性与超线性收敛性是处决于参数列 ) 的选择，因此它是否 合适就显得尤为重要，下面的定理说明d v ，瓴) 0 是个合适的选择 ” 定理2 4 1 设水平集q o 。) 一缸尺“l ，0 ) s ，( h ) ) 有界d 是包含了q ( ) 的某个有界 闭凸集函数厂o ) 在d 上连续可微，点列缸i 由采用w b 蜘- p o w c n 型线性搜索的m b f g s 算法2 1 1 产生，且其梯度w g ) l i p s c h i t z 连续，即存在常数工 0 使得 桫一v ，( ) ，川s 工峙一) ，i i ，坛，) ，d 如果参数选择成k 一i 阿 。) l | ，其中对所有的七有型墨万，常数o t 型墨石，那么我 们有： 峰掣舫瓴) 忙o 并且如果定理2 3 2 假设条件( 1 ) 一( 3 ) 成立，那么点列 k ) 超线性收敛 它的证明可参照李董辉“”，嘲，采用w b l f c p o w e u 型线性搜索时都是采用回朔策略确定 步长 第三章信赖域算法 3 1信赖域算法的基本结构 本章我们介绍求解无约束问题( 1 2 4 ) 的另一类算法信赖域算法信赖域算法与 前面介绍的线性搜索方法不同的是它在确定方向的同时确定单位步长作为搜索步长 信赖域算法的基本思想是：在当前迭代点以的附近用一个二次函数逼近目标函数， 用该二次函数在以的邻域内的极小值点作为下一个迭代点，即以。是下面问题的解： m i n ，( k ) + v ，o 。) 7 0 一以) + 去 一以) 7 以 一) 二 s j 肛一蕞8 主色 其中，以r 是，在以处的海色阵或其近似，参数色，o ，若令d x 一以，则上面的问 题可以改写为如下的等价的二次函数极小值问题 m i n ，( 以) + 1 盯( k ) 7 d + 去d 7 风d 目t ( d ) ( 3 1 1 ) 二 豇 s 色 设以是问题( 3 1 1 ) 的解则下一个迭代点为黾。略。+ 以问题( 3 1 1 ) 中的可行域 d 一翻掣咐忙乱) 称为信赖域，参数。，0 称为信赖域半径，问题( 3 1 1 ) 称为信赖域子问题 ： 设子问题( 3 1 1 ) 的解为以，定义甑为，在第七步的实际下降量： 甑一q i ( o ) 一，( 黾+ 噍) ( 3 1 2 ) 鼋。为对应的预测下降量： q i 一，( h ) 一口。( d 。) ( 3 1 3 ) 定义比值 丸。盟 ( 3 1 4 ) 魄 九从某种角度反映了二次模型q 膏( 0 ) 与目标函数，阮+ d ) 的近似程度若 接近于1 ，则 可以认为二次模型吼( o ) 在信赖域d 上与目标函数，瓴+ d ) 的近似程度很好因而，此时 可扩大信赖域域半径反之，丸离l 比较远，可以认为二次模型吼( 0 ) 在信赖域d 上与目 标函数，( k + d ) 的近似程度不够好因此，此时应该缩小信赖域半径，以提高吼( o ) 在信