（计算数学专业论文）无约束优化问题的回溯过滤信赖域算法.pdf

苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属在 年一月解密后适用本规定。 非涉密论文酉 论文作者签名：生毽 e l 期：一型! ! ! ! 呈! 导师签名：p 辱壁夜e l 期：一型! ! ! ! 三! 无约柬优化问题的回溯过滤信赖域算法中文摘要 中文摘要 信赖域方法是求解无约束优化问题的有效方法之一约束优化问题的过 滤技巧能够提高算法的计算效率，而最近提出的回溯思想能够给出信赖域 半径一个较好的估计因此，研究综合上述优点的算法具有十分重要的理论 意义和应用价值 本文基于回溯信赖域框架，结合多维滤子集技巧，提出了一个求解无约 束优化问题的回溯过滤信赖域算法，算法对当前信赖域半径给出了较好的 估计，放松了基本信赖域算法接受尝试步的条件在通常的假设条件下，分 析了算法的一阶和二阶收敛性，给出了初步的数值试验，其结果与基本信赖 域算法、过滤信赖域算法和回溯信赖域算法进行了比较，结果表明了新算法 的有效性 本文的算法作为一种自适应信赖域方法，与其他的自适应信赖域方法有 着不同的特征它并不直接引进辅助的函数值或梯度值，而是通过比较前后 两点对于新旧模型的适应性来及时调整信赖域半径，保持了信赖域算法框 架的强适性特点，进一步提高了算法的计算效果 关键词：无约束优化问题，回溯信赖域方法，滤子技术，多维滤子集， 全局收敛性 作者：卢越 指导老师：陈中文 a b s t r a c t ar f t ra 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 。一一 a b s t r a c t t r u s tr e g i o nm e t h o di so n eo ft h ee f f e c t i v em e t h o d sf 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 ef i l t c r i n gt e c h n i q u e sw h i c ha r eu s e di nc o n s t r a i n e do p t i m i z a t i o nc a ni m p r o v e t h ee 舭i e n c v0 ft h ea l g o r i t h m r e c e n t l y , t h er e t r o s p e c t i v ei d e ai sp r o p o s e d ，w h i c h c a ng i v eag o o de s t i m a t i o no ft r u s tr e g i o nr a d i u s t h e r e f o r e ，t h er e s e a r c hw i t ht h e a d v a n t a g e so ft h ea b o v ea l g o r i t h m si so fg r e a tt h e o r e t i c a ls i g n i f i c a n c ea n da p p l i c a t i o n v a l u e i nt h i sp a p e r ，w ep r o p o s ear e t r o s p e c t i v ef i l t e rt r u s tr e g i o na l g o r i t h mf o ra n - c o n s t r a i n e do p t i m i z a t i o n ，w h i c hi sb a s e do nt h ef r a m e w o r ko ft h er e t r o s p e c t i v et r u s t r e g i o nm e t h o da n da s s o c i a t e dw i t ht h et e c h n i q u eo ft h em u l t i - d i m e n s i o n a lf i l t e r t h e n e wa l g o r i t h mg i v e sag o o de s t i m a t i o no ft r u s tr e g i o nr a d i u s ，r e l a x e st h ec o n d i t i o no f a c c e p t i n gat r i a ls t e pf o rt h eu s u a lt r u s tr e g i o nm e t h o d s u n d e rr e a s o n a b l ea s s u m p - t i o n s w ea n a l y z et h ef i r s ta n ds e c o n dc o n v e r g e n c eo ft h en e wm e t h o da n dr e p o r tt h e d r e l i m i n a r yr e s u l t so fn u m e r i c a lt e s t s m e a n w h i l e ，w ec o m p a r et h e r e s u l t sw i t ht h o s eo f t h eb a s i ct r u s tr e g i o na l g o r i t h m ，t h ef i l t e rt r u s tr e g i o na l g o r i t h ma n dt h er e t r o s p e c t i v e t r u s tr e g i o na l g o r i t h m ，w h i c hs h o w st h ee f f i c i e n c yo ft h en e wa l g o r i t h m 0 u ra l g o r i t h ml o o k sl i k eas e l f - a d a p t i v em e t h o db a s e do nt h et r u s t r e g i o nf r a m e - w o r k h 刚i 博垤r ，o u ra l g o r i t h mi sn o tl i k et h eo t h e rs e l f - a d a p t i v em e t h o d s w h i c hn e e dt o c o m p u t et h eg r a d i e n tv a l u ea n df u n c t i o nv a l u e a tt h ea u x i l i a r yp o i n t ，b u tm a ym e a s u r e t h ea c c e p t a n c eo ft h ep r e v i o u si t e r a t ea n dt h ec u r r e n ti t e r a t ef o rt h en e w a n do l dm o d e l f u n c t i o n r e s p e c t i v e l y , w h i c hk e e pt h er o b u s t n e s sp r o p e r t yo ft h e t r u s t r e g i o nm e t h o d a n df u r t h e ri m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h m k e y w o r d s ：u n c o n s t r a i n e do p t i m i z a t i o n ，r e t r o s p e c t i v et r u s tr e g i o nm e t h o d ，f i l t e rt e c h - n i q u e s ，m u l t i d i m e n s i o n a lf i l t e rs e t ，g l o b a lc o n v e r g e n c e w r i t t e nb yl uy u e i i s u p e r v i s e db yp r o f c h e nz h o n g w e n 第一章 第二章 第三章 第四章 第五章 笔六童 弗，、早 第七章 参考文献 附录一 附录二 附录三 附录四 致谢5 0 无约束优化问题的回溯过滤信赖域算法第一章引言 考虑无约束最优化问题 第一章引言 其中z 钟，：形一r 是一个二阶连续可微函数 信赖域方法是非线性优化领域中的一类非常重要的数值计算方法它在 近三十年来受到了非线性优化领域的高度重视，特别是最近的十年对它的 研究更加深入细化，出现了大量的研究成果目前，信赖域框架已经和传统 的直线搜索框架并列成为非线性优化领域的两类主要的研究框架，基于上 述两类框架构造了众多实用而有效的优化算法 直线搜索方法与最优化这门学科一起出现和发展，其基本思想是在当前 迭代点处，根据收集到的关于优化问题的信息，确定一个有待进一步搜索的 方向，然后沿着该方向进行一维直线搜索，以便确定合适的步长，生成新的 迭代点，故此方法可以简单概括为先方向后步长信赖域方法，就其思想萌 芽而言，可追溯到由l e v e n b e r g 1 和m a r q u a r d t 2 提出的解决非线性最小二 乘问题的l e v e n b e r g - m a r q u a r d t 方法信赖域方法的基本思想是在当前迭代点 附近( 称为信赖域) 构造模型函数用以近似目标函数，通过求解信赖域子问 题得到尝试步，比较该尝试步下的实际下降量和预测下降量，判定尝试步是 否可接受，继而调整信赖域半径，直到成功产生下一个迭代点，故此方法可 以简单概括为先步长后方向 信赖域方法首先由p o w e l l 在文献 3 】3 中提出，用来解决无约束优化问题， 但文章并未给出收敛性证明后经过p o w c l l 4 ，5 ，s c h u l t z 等 6 】，s o r e n s e n 【7 】， 化问题、不等式约束优化问题、凸约束优化问题以及一般性约束优化问题 中，得到了相应的实用算法，其中b y r d 等 9 】，c e l i s 等【1 0 】，e 1 一a l e m 【1 1 ，l a l e e 等【1 2 ，p o w e l l 和y u a n 【1 3 ，v a r d i 【1 4 ，z h a n g 和z h u 【1 5 等都对等式约束的信赖 域方法进行了讨论，他们使用各种精确罚函数作为效益函数，给出了不同的 具有全局收敛性的信赖域算法针对简单界约束优化问题，c o r m 等 1 6 和 f r i e d l a n d e r 等 17 】分别提出了c g t 方法和f m s 方法前者利用投影的相关 技巧和广义c a u c h y 点的性质，保证了算法的全局收敛性后者通过求解一个 简单的二次规划子问题得到辅助点? 通过辅助点来证明算法的收敛性质，与 2 1 6 ，1 9 ，2 0 和g a y 2 1 讨论了线性不等式约束以及凸约束优化问题o m o j o k u n 【2 2 ，y u a n 【2 3 ，2 4 ，m a t i n e z 和s a n t o s 【2 5 】等将信赖域方法应用于一般性约束优 化问题的求解，给出了相应的信赖域算法，同时证明了算法的全局收敛性 和局部收敛性信赖域方法还与直线搜索法、有效集法、内点法等方法相结 合，给出了许多优秀的算法，极大的丰富了信赖域算法的内容其中，y u a n 和n o c e d a l 合作在1 9 9 1 年提出了直线搜索信赖域方法，可参见文献 2 6 】此 方法将直线搜索与信赖域结构两大框架有机的结合在一起，保持了各自的 优点，扩展了信赖域算法的研究视角在2 0 0 0 年，c o r m ，t o i n t 和g o u l d 发 表专著( 信赖域算法【2 7 ，系统对以上各种信赖域算法的研究成果进行了 总结，以一种普遍而自然的方式向我们展示了信赖域方法证明的相关技巧 及基本性质 最近，b a s t i n 等在文献 2 8 中研究了无约束优化问题的回溯信赖域方 法，与基本的信赖域算法相比，信赖域半径的更新方式不同，同时提出回溯 比值 ， f ( z k + 1 ) 一f ( x k + 1 一s )厂( z k ) 一f ( x k - 4 - 8 k ) p k + l2 瓦j 瓦万j 瓦不磊忑万2 元j 习= 赢j 雨 其中m t ( z + s ) 是目标函数f ( x ) 在迭代点孤处的近似二次模型，s 七是信赖 域子问题 m i n m 七( + s ) ， ( 1 2 ) s t i i s l i a k ， 的解，知是当前迭代点处的信赖域半径在基本的信赖域算法中，比值起 ，( z k ) 一f ( z k + 8 k ) p k 2 m k ( z k ) - m k ( x + l s k ) 3 无约束优化问题的回溯过滤信赖域算法 两个指标p 和卢来分别实现( 1 ) 和( 2 ) 的功能 的确定是一个重要而困难的问题，s a r t e n a e r 2 9 】 和章等 3 0 讨论了信赖域半径确定的方法，提出自适应信赖域算法文献 2 8 提出无约束优化问题的回溯信赖域方法，其中回溯比值利用了当前迭代点和 前一迭代点的信息，能够对信赖域半径作出更有效的估计，从而减少信赖域 子问题的求解次数，提高算法的计算效率 过滤法是近些年来产生的解决约束优化问题的一种新方法，它于1 9 9 7 年 首先由f l e t c h e r 等人提出并在2 0 0 2 年发表于文【3 1 过滤法针对罚函数方法 中罚因子的调整问题，以多目标规划的角度重新考虑了约束优化问题中目 标函数和约束函数的关系，提出将目标函数值与约束违反度函数值组成点 对( 即滤子) ，通过比较滤子的相互关系构造了精巧的滤子机制，由此来控制 程序使其收敛到问题的最优解，数值上表现出了很强的适应性和有效性 数值计算的成功激发了人们对于过滤方法的研究热情，经过十多年的研 究出现了许多实用的数值算法，同时也使过滤方法的研究框架更加清晰透 彻其中f l e t c h e r 等在文献 3 1 中首次将过滤思想与序列二次规划方法( s q p ) 结合，提出了过滤s q p 算法同时讨论计算的相关细节，如二阶校正步的 计算，恢复阶段的算法等文章给出大量的计算结果，但未给出相关收敛性 结果在2 0 0 2 年其与g o u n d ，l e y f f e r ，t o i n t 和w a c h t e r 在文献 3 2 】中给出了过 4 无约束优化问题的回溯过滤信赖域算法第一章引言 滤s q p 算法的收敛性结果，使得过滤方法成为研究约束优化问题的另一类 方法，丰富了非线性优化的理论结果此后u l b r i c h 等 3 3 ，w i c h t e r 等 3 4 ，3 5 分别将过滤思想和内点法、直线搜索法相结合，各自提出原始对偶内点过滤 算法和直线搜索过滤算法，同时得到了相应的收敛性结论f l e t c h e r ，l e y f f e r 和t o i n t 在文献 3 6 中，对于上述文章的思想框架进行了回顾与总结，也对 过滤法的应用进行了说明 近些年来带过滤技巧的方法层出不穷，其思想也被应用到对无导数型优 化和无约束优化等问题的研究中，同时滤子接受准则的选取样式也表现出 多元化的特征其中a u d e t 和d e n n i s 将过滤思想应用解决无导数型优化问 题，可参见文献 3 7 】g o u l d 等 3 8 】，缪等 3 9 和w a n g 等 4 0 把约束优化的过 滤技巧应用于无约束优化问题，其基本特征是放松了信赖域尝试步的接受条 件，从而在一定程度上提高了算法的计算效果这个特征类似于非单调算法 的技巧 4 1 ，4 2 关于滤子接受准则的选取方式，大致出现了三类标准第一 类以文献 3 1 ，3 2 为代表，称为正常滤子( n o r m a lf i l t e r ) ，此类滤子的图像为直 角型折线( 可参见附录二的图1 ) 第二类以文献【4 3 ，4 4 为代表，称为倾斜滤 子( s l a n t i n gf i l t e r ) ，此类滤子的图像为钝角型折线( 可参见附录二的图2 ) 第 三类以文献 4 5 】为代表，称为一般滤子( g e n e r a lf i l t e r ) ，此类滤子的图像随着 滤子位置的变更而表现出不同的折线( 可参见附录二的图3 ) 本文的滤子接 受准则为第二类 下面以不等式约束优化问题为例，简单介绍过滤方法的相关概念 im i n ，( z ) ， i8 t c ( z ) 0 ， 5 其中协( 0 ，1 ) 为常数 当 y h 很小时，规则( 1 3 ) 与规则( 1 4 ) 相差很小 定义1 4 当点对( ，( m ， ( ) 加入滤子集f 后，要去掉被其支配的点对， 即去掉所有( ) ，九( 。) ) f 满足 ，( 七) ，( 1 ) 且 ( 知) 脚 的点对，这称为滤子集的更新 6 无约束优化问题的回溯过滤信赖域算法第一章引言 本文基于信赖域框架，结合回溯思想 2 8 】和过滤技巧【3 8 ，3 9 ，提出了求 解无约束优化问题的回溯过滤信赖域算法，在通常的假设条件下，分析了算 法的全局收敛性，并进行了初步的数值试验，其结果与基本信赖域算法、过 滤信赖域算法、回溯信赖域算法进行了比较，结果表明了新算法的有效性 本文安排如下，第二部分是算法描述，第三部分是基本假设与引理，第 四部分和第五部分是算法的一阶收敛性和二阶收敛性分析，第六部分是数 值试验，最后是结论，并提出了有待进一步考虑的问题 7 第二章算法无约束优化问题的回溯过滤信赖域算法 第二章算法 g 七= 夕( 钆) ，g k ；表示g ( x 七) 的第i 个分量”i i 表示e u c l i d e a n 范数首先回顾 觎= 豢鲁糍篙 嘶- 七懒翥蓁竺篡 l 【a ，。) ， 如果p k 啦， a i + i 【仇七，七】，如果p k 【，7 l ，7 7 2 ) ， 【 h 1 七，仇 ，如果p k z ， 其中e p s 为算法的精度，k 。为算法的最大迭代次数，可将迭代停止的准则 置于步1 中算法的流程图可参见附录三 由无约束最优化问题的一阶必要条件可知，若矿是问题( 1 1 ) 的局部极 小点，则夕( 矿) = 0 受到过滤方法的启发，本文把i i g ( z ) l l 看成是衡量迭代 点优劣的一个指标在此给出过滤方法应用于问题( 1 1 ) 时的相关概念的定 义 定义2 1 称迭代点瓢支配迭代点勋，如果 协t i i g u i 对所有的i = 1 ，2 ，n 成立 定义2 2 多维滤子集f 是一个n 元组的集合，其元组的形式为( 玑，9 k 。) 若鲰，g f f ，则至少存在两个指标j l ，歹2 _ 【1 ，2 ，亿) 且j l j 2 满足 i g l j 。l i g k j 。i 且l g k j 。i h 血i 定义2 3 迭代点巩被滤子集f 接受当且仅当对所有的g t f ，存在 j ( 1 ，2 ，n ) 使得 i g k j l 1 9 1 j i 一j i9 l i i ， 其中( 0 ，l 何) 9 过滤信赖域算法 一，佗 都成立 0 ，常数 ： f ( z k 一1 ) 一，( z 七) m 2 而瓦j j ：商 i m _ 1 ， y 2 a j c 一1 ) ，如果厥 礼 a k 【他知一1 ，a k 一1 ) ，如果厥 面l ，镌) ， i 七一1 ，怕七一1 】，如果魂袍 m = 而f 瓦( x k ) f - - 雨f ( x 者) 为 情况3 若p k 。， 其中e p s 为算法的精度，七。为算法的最大迭代次数可将迭代停止的准则 置于步1 中算法的流程图可参见附录四 关于二次模型? t t 七的h e s s e 矩阵，可以利用迭代点处的h e s s e 矩阵v z f ( x t ) ， 也可以通过b f g s 校正公式产生 相对于基本的信赖域算法，本文的算法加入了回溯机制和滤子机制，前 者在于通过当前迭代点和前一迭代点的信息及时调整信赖域半径，给出了 信赖域半径的有效估计，后者在于放松了尝试步被接受的条件，在某种程度 上提高了算法的计算效率由算法可以看出，如果尝试步在步5 中未被接受 ( 情况3 发生) ，则算法与基本的信赖域算法几乎没有差别，只不过加入了回 溯机制而当尝试步在步5 被接受时( 情况1 或情况2 发生) ，滤子机制与回 溯机制共同起作用，使得迭代点更快更好的收敛到问题的稳定点 如果在第k 次迭代有x 七+ 。= z 知+ 8 。x 奄，则点x 知称为成功迭代点，第k 次迭代称为成功迭代 其中 熊= 1 + m a x z 玩ij v 黜m ) 鼠= z il l z 一瓢岛) ， 亿= r a i n o ，入m 饥( v 。m 七( 钆) ) 1 2 m k 一，( z 七) ：m 七一。( 一。) + v 。m 七一。 七一，) t s k - 。+ 丢s 己。v 。z m 血一- ( 靠一- ) s 七一，( 3 3 ) 其中乩幺一，在连接z 七一- 与z 南的线段上由假设条件a 3 知， 所以， 7 n k - 1 ( z 七一1 ) = f ( x k 一1 ) ，v 。，( z 七一1 ) = v 。7 礼七一1 ( z k 1 ) ，( z 七) 一m 七一，( ) i = j 互1 s 己。( v 。z ，( 靠一- ) 一v z 。仇七( 靠一，) ) s 知一 1 3 第三章基本假设与引理 无约束优化问题的回溯过滤信赖域算法 l 三s 己。v z 。厂( 靠一，) s 七一，i + l 三s 己。v m 膏一。( 靠一。) s 七一。 三( i h + m 一1 ) l k 一。1 1 2 丢( i h + m h 一1 ) 2 一， 后。6 2 1 类似地，由于目标函数厂( z ) 和模型函数m 知( z ) 二阶连续可微，由中值定 理知， f ( x k - 1 ) = m 七) 一v z m 七) t s k _ 1 - + 芝1 s 己。v 。卫，( 靠) s m ， m e ( 孤一- ) = m 七( ) 一v 。m m ( 巩) t s k - 1 + 三s o 。v 。m 七( 靠) s 知一。， 其中& ，血在连接z 七一，与z * 的线段上由假设条件a 3 知， 所以， m k ( x k ) = f ( x k ) ，v z f ( x k ) = v 。m k ( z ) f ( x k - 1 ) 一m * 七一- ) i = l 互1s 己。( v 黜，( 矗) 一v 。m t ( 血) ) 鼠一- l f 丢s 己。v 。z ，( & ) 鼠一- j + | 三s o 。v 。m 七( 厶) s * 一， 三( 忌。n + m ，l 1 ) i k 。1 1 2 丢( i h + , n h - 1 ) a ：一。 h ：一1 ( 3 4 ) 由于引入了回溯比值，需要比较两个比值的分母的误差界与信赖域半径 的关系，因此，给出下面的引理 引理3 2 假设a 1 一a 4 成立，则对每个成功迭代点一，有 ( r n 一1 ( z 七一1 ) 一m k 一1 ( z 知) ) 一( m 七( x k 一1 ) 一m k ( z k ) ) i 2 弛；一1 1 4 又i 阢一。一g k i i = l l v 。f ( x t 一。) 一v 。f ( x k ) 1 1 由中值定理得， v 。，( z 七) = v 。，( z 一- ) + 0 1v 。z ( z k - 1 + a s k - 1 ) s 七一d 口 由c a u c h y - s c h w a r z 不等式及假设条件a 2 ， il g k - 1 - g k ll z 1i v 。f ( x k - ，j r o l s k - - 1 ) s 训d a ， 慨“( 3 6 ) 由( 3 5 ) ，( 3 6 ) 知， i ( m j c 一1 ( z 一1 ) 一m 七一1 ( z j c ) ) 一m k ( x k 一1 ) 一m 七( z 知) ) i ( 尼让f h + k 。h ) l l s 一l i l 2 2 k 。m a 2 。一1 以上引理说明两个比值的分母的误差界与目标函数和模型函数之间的误 差界是同阶的应用这一结果对比文 27 】中定理6 4 2 ，有如下结论 引理3 3 假设a 1 一a 5 成立，g k 一1 0 且乱一满足 缸剑n 1 咖，高) 静训 7 ， 则第k 一1 迭代为成功迭代且 1 5 第三章 基本假设与引理 无约束优化问题的回溯过滤信赖域算法 让田七m d c ，r l ( 0 ，1 ) 及1 炭设条件a 3 ，a 5 知凤一1 b h 由( 3 7 ) 得到 h 百l l g k _ - 1 1 1 由假设条件a 5 知， 咻t ( 耻) m k - 1 ( 引忱l l i m i n 剀，k - ) = 忱l 缸“3 8 ) 另一方面，由引理3 1 知( 3 1 ) 成立，结合( 3 7 ) 有 l,ok_l-1i=if(xk)-tnk-l(xk)卜高缸-1咖 因此，p k 一r 。，即第k 一1 迭代为成功迭代 由于f i 2 ，七毗( 0 ，1 ) ，有 两( 1 - 0 2 ) 三且如龋 1 ( 3 - 9 ) 由( 3 7 ) ，( 3 9 ) 及侥一。的定义可得 k - 互1 面k i n & 恤一- i i 且k 0 使得6 d 对所有的k 成立 证假设指标k 是第一个使得下式成立的指标 岖俩 a o , m i n l 呻，隅) 警) 由算法r f t r 中步2 信赖域半径的更新方式可知，总有 1 a 七一。南结合 ( 3 1 1 ) 知七一。满足( 3 7 ) ，由引理3 3 知趣一。七，而这将导致与指标k 的取 法矛盾，从而假设不成立令 邓幽 ? t o , m i nh t ，端) 警) 命题得证 1 7 1 ) 一( a 5 ) 下， ，定义如下 记蚓表示集合s 中元素的个数由算法r f t r 知，指标集s 对应的 迭代点对应于步5 中的情况1 或情况2 ，指标集a 对应的迭代点对应于步5 中的情况2 ，指标集d 对应的迭代点对应于步5 中的情况1 所以有a s ， aud = s 下面证明只有有限次成功迭代点时，算法产生的迭代序列收敛到问题的 一阶稳定点 定理4 1 假设a 1 一a 5 成立且l s i 0 使得 g k l i 的 0 ( 4 1 ) 对所有k 成立记指标集a = 仇】由假设条件知 l l g t 吣有界，故存在 + 1 ) 的子列讹。+ 1 ) 满足 z n mi i g 岛f + 1 l i = i i g 。l l k l b g 由k t 。的定义，点z ，+ 1 被滤子集f 接受，且对每个1 1 都存在j l 1 ，2 ，扎) 使得 1 9 缸+ 1 ，血i 1 9 q 一，+ 1 ，血i 一i l 夕乜z 一。+ 1 ( 4 2 ) 1 9 无约束优化问题的回溯过滤信赖域算法 j 在( 4 2 ) 中令l - + 并利用( 4 1 ) l ，jj 一的 0 + o 。且l a i 0 使得( 4 1 ) 成立由于i a i 0 ( 5 1 ) 对所有充分大的i 成立进一步设l i m 汕佃慨。| | = 0 ，则第觑次迭代为成功迭 代，同时有 声+ l 镌 和 + 1 ( 5 2 ) 对所有充分大的i 成立 证首先证明第k i 次迭代为成功迭代由( 3 3 ) 和( 5 1 ) 知， i p k 。- 1 l = 【瓦f ( x 瓦k , + l 丁) - - 丽m k 丽, ( x k , + 1 ) i j i i ：瓣1 i s 乏( v z f f f 南；) v 。z 钉佗七。( 敛。) ) s 。l 互乏：= ：瓣1 | i s 七；1 1 2 i i v 。z ，( 。) 一v z z z 。( 靠；) i 嘉( 1 l v ( - v 。j ( x k , ) l l + v ( 训- - v x x ( 圳i + ij x t 船m k , ( x k i ) 一乳。m ( 厶。) jj ) ， 0 由假设条件a 6 和定理4 1 ，4 2 ，4 2 知上式的第二项也趋于0 故当i 趋于无 穷大时，故p h 趋于1 ，从而p k 。叩。即第k t 次迭代为成功迭代 下面来证明结论的第二部分由中值定理知， 使得 6 k , + z - 1 1 = i 而i f ( x 瓦k , ) f - - t 丽l z k i 磊+ l ( x 瓦k i ) 习 + z 1 i i v 。2 f ( x k , + a s k , ) 一v 。m + - ( 蠡汁- ) l i d a 由三角不等式可以得到 i i v 。f ( x - 4 - q s ) 一v 。m k 。( 厶；) i | i i v 。f ( x k 。- 4 - a s ) 一v 。f ( z k ；) | i + l l v 。，( z ) 一v 。z m k ；( x k 。) | i + i i v 。m k 。( x k 。) 一v 。m k ；( 血；) 1 1 类似的可以得到 l l v 2 。，( z - 4 - 0 1 8 k ；) 一v 。m k 汁1 ( 靠；+ 1 ) 1 i i l v 。z f ( z k 。- 4 - 口s ) 一v z z f ( x k 。+ 1 ) l l + l l v z 。厂( z + 1 ) 一v 卫z m k + 1 ( z + 1 ) 1 i - 4 - v z 。m k t + l ( x k t + 1 ) 一v z 。m k i + 1 ( e + 1 ) i i 由于 i l ( z - 4 - 0 1 8 k 。) 一x k i | | i l s | | ，i l 靠。一x k 。| | i l s l | ， i i ( z + q s ) 一x k ；+ 1 i i i i s i l ， i i 鼠+ 1 一z 乜+ 1 1 i i i s 利用假设条件及定理4 1 ，4 2 ，4 3 可知， l l v 。z f ( x - 4 - 0 1 8 k 。) 一v 。z m k 。( 厶。) l i 和 i i v z 。f ( x k 。 4 - q s ) 一v 。z m h + l ( 蠡汁1 ) 2 3 二阶收敛性分析 无约束优化问题的回溯过滤信赖域算法 故当i 充分大时，蛾k m q d 由( 5 3 ) ，( 5 6 ) 及三角不等式得 j s k i + t - 1 面1 慨2 聪m ) 一v z 。m “沁) 面1 ( f l v 。聪t + 1 ) - - v x x m 洲i i + l i v 。z ( x k t + 1 ) 一v 乙z m k 。+ 1 ( x k 。+ 1 ) + l i v z z m k 。+ l ( x k 州) 一v 。z m k m ( 鼠+ 1 ) 1 1 ) ( 5 7 ) 与第一部分证明相似，可知当i 趋于无穷大时， ( 5 7 ) 的右侧趋于0 ，故厥t + 1 趋于1 从而( 5 2 ) 成立。 定理5 2 假设a 1 一a 7 成立，且点列 z k ) 有唯一的极限点x ，则x 为问 题( 1 1 ) 的二阶稳定点 证由定理4 1 ，4 2 ，4 3 知夕( 矿) = 0 应用反证法，假设几= n ( v 。y ( z ) ) 0 ，则由假设条件a 6 知，存在k o ，使得当k k o 时有亿= 入m 机( v 。m 七( ) ) ；l 七啪z ) ，七一= 1 0 0 0 其中k 是最大迭代次数 在表1 ，表2 ，表3 中，p r o b l e m 表示测试问题名称，n 表示测试问题的维 数，n b t r ，n f t r ，n r t r ，n r f t r 分别表示算法b t r ，f t r ，r t r ，r f t r 的迭 代次数，n g l ，n 9 2 ，r i 9 3 ，n 9 4 分别表示算法b t r ，f t r ，r t r ，r f t r 计算梯度值 的次数f 表示迭代次数达到最大值m 仰= 1 0 0 0 时计算失败 六章 数值试验无约束优化问题的回溯过滤信赖域算法 p r o b l e mnn b t rn f t r n r t rn r f t rn g l n 9 2 n 9 39 4 $ 2 0 123 43 43 43 43 53 53 53 5 $ 2 0 226666777 7 $ 2 0 32666677 77 $ 2 0 5288889 999 $ 2 0 6 24444 5555 $ 2 0 7 2 9 71 17 891 09 $ 2 0 8 2 3 91 72 71 72 72 32 62 3 $ 2 0 921 0 84 59 95 38 65 59 36 1 $ 2 1 024 2 41 6 94 6 01 7 63 6 51 9 5 4 5 01 8 5 $ 2 1 123 71 33 71 22 91 73 21 6 $ 2 1 221 31 41 21 41 11 61 11 6 $ 2 1 322 72 72 72 72 82 82 82 8 $ 2 4 0355556666 $ 2 4 131 31 31 31 31 41 41 41 4 $ 2 4 631 071 071 091 09 $ 2 5 641 51 51 51 51 61 61 61 6 $ 2 6 046 93 35 33 34 73 74 83 7 $ 2 6 141 31 51 31 51 31 71 31 7 $ 2 7 1622223333 $ 2 7 3 61 01 01 01 01 11 11 11 1 $ 2 7 4 2 222 2 3333 $ 2 7 5 42 2223333 $ 2 7 6622223333 $ 3 0 821 191 191 01 11 01 1 无约束优化问题的回溯过滤信赖域算法第六章数值试验 表2 nn b t r n f t r n r t rn r f t rn g l n 9 2n 9 3 n 9 4 23 91 72 71 72 72 32 62 3 1 03 62 23 12 22 82 9 2 9 2 9 2 06 73 6 6 8 3 64 94 3 6 7 4 3 3 0 8 34 1 6 0 4 26 2 5 65 85 5 4 0 1 1 1 5 21 0 05 2 8 1 7 09 87 0 5 01 5 06 91 3 06 91 0 59 31 2 79 1 6 01 7 08 21 4 78 21 2 2 1 0 9 1 4 4 1 0 7 7 01 9 91 0 21 6 21 0 11 4 11 4 0 1 5 91 3 5 8 02 1 81 2 11 7 11 2 01 5 7 1 5 5 1 7 0 1 4 7 9 02 4 81 2 82 0 91 2 11 7 71 7 12 0 7 1