（应用数学专业论文）无约束优化问题信赖域过滤算法的研究.pdf

y 荆1 螋必 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均已在论文中明确说明并致谢。 论文作者签名：缘劫洋 学位论文使用授权说明 山，u 年6 月，p 日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：屏劫拳 导师签名：年月 日 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 无约束优化问题信赖域过滤算法的研究 摘要 本学位论文结合非单调技术、过滤技术等提出了求解无约束优化问 题基于二次模型的信赖域算法和基于新锥模型的信赖域算法在适当条 件下给出了算法的全局收敛性证明初步数值试验结果表明所提出的算 法是有效的 第一章介绍无约束优化化问题的信赖域算法、过滤子的基本知识以 及一些成果 在无约束极小化问题的基本信赖域算法中，若比值p k 叼，则要重 新求解信赖域子问题得到迭代步长s 凳为了减少求解信赖域子问题的次 数，第二章通过对当前目标函数下降量与成功迭代的目标函数下降量最 小值的比较，接受使目标函数下降量大于以往成功迭代的目标函数下降 量最小值的试验点，得到一个新算法在一定的条件下给出算法的全局收 敛性证明初步的数值试验结果表明算法是有效的 结合多重滤子、线搜索和非单调技术，第三章对无约束优化问题提 出非单调信赖域过滤算法当试验点迭代不成功时，采用多重滤子线搜 索，尽量减少重新求解信赖域子问题的次数，从而降低了计算量在一定 的条件下，给出新算法的全局收敛性证明初步的数值试验结果表明算法 是有效的 基于新锥模型，结合非单调和滤子技术，第四章提出求解无约束优化 广西大学硕士学位论文( 2 0 1 0 年)垂竺柬优化问题信赖域过滤算法的研究 问题信赖域算法在适当的条件下，证明了算法的全局收敛收敛性初步 的数值试验结果表明算法是有效的 关键词：信赖域算法二次模型锥模型多重过滤子 全局收敛性 _ _ 一一 r e s e a r c ho nf i i j t e rt r u s tr e g i o n m e t h o df o ru n c o n s t r a i n e d o p t i m i z a t l 0 n a b s t r a c t i nt h i sp a p e r ，b yc o m b i n i n gf i l t e ra n dn o n m o n o t o n e t e c h n i q u ew i t h t h eb a s i ct r u s t r e g i o na l g o r i t h m ( b t r ) ，t h e t r u s t r e g i o na l g o r i t h mb a s e d o nq u a d r a t i cm o d e la n dt h e t r u s t r e g i o na l g o r i t h mb a s e do i ln e wc o n i c m o d e la r ep r e s e n t e df o rs o l v i n gu 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 h eg l o b a lc o n v e r g e n c er e s u l t so ft h e s en e wa l g o r i t h m sd j ee s t a b l i s h e d u n d e rp r o p e rc o n d i t i o n s p r e l i m i n a r yn u m e r i c a lr e s u l t ss h o wt h a tt h e y a t ee f f i c i e n t t h ef o u n d a t i o n a lk n o w l e d g ea n ds o m er e s e a r c h e sa b o u tt r u s tr e g i o n m e t h o d sa n df i l t e ra r er e c a l l e di nc h a p t e r1 i fm o ) 内定义一个模型7 7 z k ( x k + s ) 近似f ( x k + 5 ) ，通过解子问题 僻l 高f 兰曲 2 ， 确定搜索方向5 若模型m k ( x k + 8 ) 的下降量与目标函数f ( x ) 的下降量比较一致，则 取z 七+ l = z 七4 - s ，且尽量扩大七；否则取x k + l = z 七，且减少七，重解上述子问题由 此建立的算法记为b t r 算法( b a s i ct r u s t r e g i o na l g o r i t h m ) ，其中七称为信赖 域半径，玩称为信赖域 b t r 算法的步骤为： s t e p 0取初始值z o 舻，初始信赖域半径o ，常数吼，7 7 2 和7 l ，仇分别满足 条件0 7 7 l 7 7 2 1 ，0 ，y l 他 o ) 内定义模型t i t , k ( x k - 4 - 8 ) 近似f ( x k + s ) ，解信赖域子问题( 1 2 ) ，得到，记z 毒= z 七+ 8 k s t e p 3 计算比值 f ( z k ，x , 1 j 一, j ，f x z i 土。、i m 2 砥万确 若p k 叩l ，则令z 七+ 1 = x k 上, 否则令x k + l = 砜 1 ( 1 3 ) 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 如t 泌七，赫， ( 1 4 ) 记k = k + 1 ，转s t e p l 在s t e p 2 中通常用如t - - 次模型近似，( 瓢+ 5 ) ， m 七( x k + s ) = m ( 硝+ 出七) t 8 i f - 去s t 凰s ， ( 1 5 ) 其中m ( 孤) = f ( x k ) ，g ( x k ) = v ，( ) ，h k 是( x ) 在孤处的h e s s e 阵v 2 f ( x k ) 的一 个近似对称阵 用二次模型近似目标函数已被大多数的信赖域算法采用，但是用二次模型近似非 二次性态较强，且曲率变化很大的函数效果可能较差为此d a v i d o n 3 7 1 提出用锥模型 近似目标函数，即上述b t r 算法中的模型定义如下： 嘶m ) c ) 4 - 而g ( x k ) t 8 + 互1 尚， 其中k 是一个礼维向量，c ( x k ) = f ( x k ) 显然锥模型是二次模型的推广 b t r 算法既具有总体收敛性，又具有牛顿法的快速局部收敛性用b t r 算法求 解问题( 1 1 ) 时，目标函数f ( x ) 在迭代点 z 知) 处的函数值 ，( ) ) 是单调减小的，导 致迭代次数变多，计算量变大 为了克服b t r 算法的缺点，减少迭代过程中的计算量，许多学者在b t r 算法的 基础上提出各种形式的非单调信赖域算法，如：邓肖一周算法，柯韩算法，t o i n t 自适应非单调算法n m t r 2 以及n m t r 2 一d l 算法【3 1 它们大多是对b t r 算法的 s t e p 3 作修改，把m 改为 五( 七) 一，( z 吉) p k2 m ( x k ) - m ( x + ) 其中五( 七) 有以下几种形式： ( 1 ) f l ( k ) = m a x a 一( p 一1 ) ， ) ，厶= f ( x k ) ，p 是一个给定的参数 ( 2 ) ( 的= m a x a j l o 歹p ( 七) ) ，而p ( k ) 定义为 p ( 七) ： 0 i f p k 一1 一 im i n p ( k 一1 ) + 1 ，尸 i fp l , 一l 7 7 l ， 其中p 是某一正整数 2 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化囹錾隹塑蜜垫滤笋法的研究 ( 3 ) z ( k ) = m a x a j l o 歹p ( 七) ) ，v ( k ) 定义为 p ( k ) = m i n p ( k 一1 ) + 1 ，2 尸，r 】i ， 其中v ( o ) = 0 ，p 0 是某一整数，p k = p k + 1 这些非单调算法的总体特点是：它不要求下一个迭代点的目标函数值比当前迭代 点的目标函数值下降，只要求下一个迭代点的目标函数值比以前某一成功迭代点的目 标函数值有所下降即可非单调算法放宽试验点+ 8 被接受的条件，加大z 七+ s 被 接受的可能性，减少了算法迭代次数和计算工作量 在b t r 算法中，当p k m 时，重解子问题( 1 2 ) ，需要较大的计算量为了减 少求解子问题的次数，在文 4 】给出的算法中，当p k 7 7 1 时，采用非单调线搜索：取 入= k 为 1 ，p ，卢2 ，) 中满足下式的最大数， f ( x k + a s k ) 一i t ( k ) a 入9 ；。s 南， 令x k + 1 = x k + ) k s k ，其中p ( 0 ，1 ) ，q ( o ，0 5 ) 在文【5 】的算法中，当p k m 时， 进行固定步长的线搜索：取步长儿为 m 、c 夕is 奄 机2 一币丽 u l t u 七 令z j b + l = z 七+ ) , k s k ，其中6 ( 0 ，1 ) 文【4 ，5 】把非单调技术和线搜索结合起来，得到带线搜索的非单调信赖域算法， 数值结果表明这些算法的效率都得到了提高 1 2过滤子的基本概念 在2 0 0 2 年，f l e t c h e r 和l e y f f e r 在文【9 】中提出了解决如下( n p ) 问题的滤子算 法。 s m t ? 搿 0 6 ， c ( 传统上，采用罚函数法求解上述( n p ) 问题；但罚函数的使用会带来应用上的困 难，特别是罚参数的选择，且一些精确罚函数不可微 为了避开使用罚函数，考虑( n p ) 问题中两个相互竞争的目标，一个是极小化目 标函数， ) ，另一个是迭代点的可行性，即 m i n f ( x ) 3 广西大学硕士学位论文( 2 0 1 0 年)无约束优化问錾信赖域过滤算法的研究 和 r a i n 九( c ( z ) ) 其中九( c ) ) = 0 c + ) i i - = 哼 ) ，哼= m a x o ，勺) 若 f ( x k ) ( x 1 ) 且 h ( c ( x k ) ) 危( c ( 铆) ) ， 则称( f ( x k ) ， ( c ( 。七) ) ) 控制( ，( 现) ，九( c ( 黝) ) ) ，这表明x k 至少不会比动差 利用此概念定义滤子：由不能相互控制的数对( f ( x 1 ) ，九( c ( 勋) ) ) 组成的表 若( ，( 钆) ， ( c ( z 南) ) ) 不被滤子中的任一数对所控制，则称( f ( x k ) ， ( c 七) ) ) 被滤 子接受，此时也称瓢被滤子接受 过滤子算法的基本思想是：通过求解( n p ) 问题的信赖域子问题 r a i n t 1 2 k ( x k + 8 ) = f ( x k ) + 9 ( z 七) t s + 8 t h k s s t c ( x k ) + v c ( x k ) t 8 0 i i s i l k ( 1 7 ) 得到搜索方向s 若矾+ s 被滤子接受，则取z 七+ 1 = + 8 且尽量扩大a k ；否则 z 七+ l = 孤且减少七已经证明信赖域滤子算法具有全局收敛性和很好的数值结果 一些学者把过滤子算法的思想与线搜索相结合，用滤子线搜索代替传统的线搜 索，得到求解( n p ) 问题的线搜索滤子方法 1 4 , 1 5 , 3 3 1 其主要思想是： ( 1 ) 解子问题( 1 7 ) ，得到迭代方向8 ( 2 ) 取以l = 1 令z 毒= x k - 4 - s ，若砧被滤子接受，则转向；否则令如+ 1 = 以f ，z = z - 4 - 1 ， 转向，其中卢( 0 ，1 ) ； 令以= 6 斛，z 七+ 1 = z 七+ 6 k s 在求解无约束优化问题的算法的收敛性分析中，通常关注迭代点是否收敛于一阶 稳定点，即梯度g ( x k ) 是否趋于零另外，为了把( n p ) 问题过滤子算法的思想用于求 解无约束优化问题，考虑梯度的各个分量g ( x k ) = ( 9 。( z ) ，鲰( z ) ) t 4 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 定义1 1 任给两个点z l ，z 2 ，若 l 仇 1 ) i i 吼( z 2 ) i ，v z = 1 ，n ， 则称数组( g l 1 ) ，g n ( x 1 ) ) t 控制数组( g l ( z 2 ) ，鲰( z 2 ) ) t ，也称x l 优于z 2 或z 2 次于z 1 定义1 2 记，= 夕( z 七) = ( g k ，1 ，鲰，n ) t i k j ) ，其中g k ，i = g i ( x k ) 是点z 南处 梯度向量的第i 个分量，是一个指标集若对垤，z i ，都存在某个i l ，佗) 使得 i g k ，一 l g l ，一 成立，则称，是由n 维梯度向量组成的过滤集或过滤子 显然过滤集厂是由互不控制的梯度组成如果试验点z 吉的梯度( 9 l 毒) ，锄( z 毒) ) r 不被过滤集厂中的向量所控制，则接受试验点z 吉在实际计算中，对于很接近过滤集 的点也不打算接受，为此作如下定义 定义1 3试验点z 孝被过滤集厂接受当且仅当对厂的所有向量夕( 勋) ，存在 歹 1 ，死) ，使得 l 缈( z 吉) i l g t j | _ 似锄) i l ， 其中( 0 ，击) 如果z 毒被过滤集厂接受，则把9 ( z 古) 加入厂中，并从其中移去所有被9 ( z 吉) 控 制的向量 文【1 l ，1 2 ，3 1 】把n 维过滤子引入b t r 算法中，提出求解无约束优化问题的过滤 信赖域方法其主要思想是：当风 叼1 时，考察试验点z 者= z 七+ s 是否被n 维过滤 子接受，若z 吉被n 维过滤子接受，则令x k + l = z k + s ；否则重解信赖域子问题数值 结果表明，对于中大规模问题，无约束优化问题的过滤信赖域方法相比b t r 算法有 较大的改进 1 3本文的工作 在基本信赖域算法基础上建立起来的非单调信赖域算法是解无约束优化问题的 效率较高的方法之一，它具有全局收敛性和局部快速收敛性的特点研究如何进一步 提高非单调信赖域算法的效率，是许多研究者关注的问题之一当p k r l 时，除了使 用线搜索，减少求解信赖域子问题的次数，提高算法效率外，挢讨其它更有效的方法加 5 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 大试验点z 知+ s 被接受的可能性也是值得研究的从解有约束优化问题的信赖域过 滤算法的全局收敛性和良好的数值结果得到启发，在无约束优化问题的非单调信赖域 算法中引入过滤技术将会有助于提高算法的效率 本文的工作之一是对基本信赖域算法进行修改，给出一个改进的信赖域算法工 作之二是在文【4 ，5 】的基础上，当, o k 7 7 1 时，把线搜索与z , 维过滤子结合起来，进行 所谓的n 维过滤子线搜索以提高试验点被接受的可能性，由此得到基于二次模型的 非单调信赖域过滤算法该算法把信赖域算法的全局收敛性和局部快速收敛性与过滤 技术具有的良好数值结果的特点相结合，在一定的条件下，给出算法的全局收敛性证 明，进行初步的数值试验对一些非二次性态强，且曲率变化强烈的函数，用二次函数 近似效果较差，为此本文的工作之三是用锥函数近似目标函数用文【4 7 中提出的新 锥模型代替二次模型，再结合线搜索与n 维过滤子，得到基于新锥模型的非单调信赖 域过滤算法在一定的条件下，给出算法的全局收敛性证明，进行初步的数值试验 6 广西大学硕士学位论文( 2 0 1 0 年)无约查垡塑瞿堡塑壅垫避鎏箜堑窒 2 1引言 第二章一个改进的信赖域算法 在求解无约束极小化问题( 1 1 ) 的b t r 算法中，迭代步长s 七通过解如下信赖域 子问题得到， r a i n m k ( x k i - s ) = m ( 钆) + 删：s + 8 t 风s ( 2 1 ) s t i i s l i 知 其中m ( x k ) = f ( x k ) ，g ( x k ) = v f ( x k ) ，h k 是，( z ) 在x k 处的h e s s e 阵v 2 ，( z 七) 的一 个近似对称阵，1 1 0 为欧氏模，七为信赖域半径，点z 吉= z 七+ 8 称为试验点 记 触=揣mlxk) ， 一仇p j 对于0 叼 1 ，若p k 叩，则称迭代成功，试验点z 毒= 钆+ 8 被接受，令x k + 1 = z 吉； 若p 七 叩，则称迭代失败此时在b t r 算法中通常是压缩信赖域半径，重解子问题 ( 2 1 ) 在迭代失败的点中可能存在对极小化目标函数f ( x ) 有用的点，如何加大这些点 被接受的可能性值得探讨下面通过分析p 七与目标函数下降量和模型下降量的关系， 寻找加大试验点被接受可能性的途径 记 以= f ( x k ) 一，( z j ) ， o k = m ( x k ) 一m ( z j ) ， 分别称为目标函数下降量和模型下降量 注意到当 p k = 薏2 叩2 瓦2 叩 时，可能出现以、以都很小；而当 p j , 叼 时，以有可能较大，它可能比“成功”迭代时的目标函数的下降量要大，但此时的迭 代却被认为是“失败”的，这显然是不合理的下面对此情形给出改进方法 7 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 2 2 算法 在b t r 算法中，仅当触，7 时，试验点z 喜= x k + 8 才被接受，为了提高试验点 z 去被接受的可能性，给出如下处理方法： ( 1 ) 当p k 叼时，试验点z = + 8 被接受； ( 2 ) 当p k 0 ，常数7 7 和饥，他，舶分别满 足条件0 ，7 1 ，0 饥7 2 1 铂，计算( x o ) ，记k = 0 ，取脚为足够大的常数 s t e p l计算9 ( z 七) ，若满足终止条件，则终止 s t e p 2解信赖域子问题( 2 1 ) 得到s k ，记z 毒= x k + 8 k s t e p 3 计算 以 m 2 砥百确 s t e p 4 确定试验点的可接受性： 若p k 7 7 ，则( i ) x k + 1 = z 毒，( i i ) 若以 鲰则纵= 以；若风 7 7 且以纵，则 。知+ 1 = z 毒；否贝0x k + 1 = x k s t e p 5更新信赖域半径，取 i 7 1 a k ，能】 p 七 7 7 ， a k + l = 乱 m 7 7a n d 恢i l 0 ，使得i i 风l l k u m b 设j = 歹。是满足下列条件的最小正整数， z 七o ) 2 瓢一赢 m k ( x k ( j ) ) r f z k ( x k ) + 6 。蘸。( z k ( j ) 一z 七) 其中k k ( 0 ，1 ) ，k 幽( 0 ，j 1 ) 是常数记z 斧c = x k ( j c ) ，称z 参c 为信赖域子问题( 2 1 ) 的近似柯西点由文【1 】中定理6 3 3 可得如下引理 引理2 3 1 设a 1 、a 2 和a 3 成立，z 参c 是信赖域子问题( 2 1 ) 的近似柯西点， 则 州引一州铲) 酬鲰i i 幽 黼，七 ， ( 2 3 ) 其中( 0 ，1 ) 是常数 用a m i n 【三k 】表示上k 的最小特征值，当= 入m i n 【上k 】 o ，对全部的南满足l i g k l l e ， 则存在常数 0 ，使得a k y 证明见文【1 】中定理6 4 3 引进记号： s = k l z k + l = x k + s k ， c = k l p 七 0 ，z + = x k o + l = x k o 钾，有 由算法的s t e p 5 得 由此可推出 + j 0 ，使得 b + j 这与( 2 8 ) 式矛盾故有1 1 9 b l i = 0 定理2 3 5设假定a 1 、a 2 和a 3 成立，且集合c 的元素个数i c i = + 。o ，则 1 i mi n f l l g 知l l = o ( 2 9 ) i c - - - o o 】0 广西大学硕士学位论丈( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 证明设存在e 0 ，对任意的七下列不等式成立， i 0 e 记集合c 中所有指标为 如) ，则由( 2 2 ) 式可知 5 k j = ( x k j ) 一，( z 码+ 1 ) 弘k j + 1 设在前b + 1 次成功迭代中的第殇+ 1 次迭代的目标函数的下降量最小，即 惭。= 屯= 。g 蠹* ，p 舻爰叼) 撕圳n 端a ( 磅+ 一码) 卵蒯e m i n 【三，叫 窑( 吲概俐b1 = ( k i + 1 - - k 1 ) 叼晰m i n 去，1 _ 帆 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 由i s i = + 。o ，i c i 时，有k 属于s ，而k 不属于c ，则 f ( w k ) 一f ( x k + 1 ) 7 7 【m k ( x k ) 一m k ( x k + 1 ) 】 叩训i 叫端a ( 2 1 4 ) 叩m i n 【忐，j - 由( 2 1 4 ) 式得到 ，( z b ) 一f ( x k + 1 ) = f ( x j ) 一f ( x j + 1 ) 】 j = k o ， ( 尼一) 枇u 俐七却e m 洫【三，叫_ + 。， 这表明f ( x ) 无下界，与假定a 1 、a 2 矛盾定理得证 2 4数值结果 本章用m a t l a b 编程来实现算法算法中参数选择如下：t = 0 2 5 ，o = 0 5 ，设 定的终止准则是m a x l l v f ( x k ) i ，i ，( z 膏) 一f ( x ) l s1 0 一程序的运行过程中，利用 b f g s 公式修正得到凰+ 1 用下面列出的4 个函数刚对算法进行测试，本算法记为 a l g o r i t h m 2 2 1 ，数值试验的结果见表2 1 ，其中n 是变量的维数，分别取值为3 2 ，6 4 ， 1 2 8 ，2 5 6 ；z o 是初始点；数值按迭代次数目标函数计算次数梯度计算次数( 风 ，7 的 次数) 的形式给出 问题1e x t e n d e dr o s e n b r o c k 函数： n 2 ，( z ) = 1 0 0 ( x v z 毛一1 ) 2 + ( 1 一z 巧一1 ) 2 】，z 渺 j = l 问题2e x t e n d e dp o w e l l 函数： n f ( x ) = 【( z 句一3 + 1 0 x 4 j 一2 ) 2 + 5 ( z 4 j 一1 一z 句) 2 j = l + ( z 句一2 2 x 4 j 一1 ) 4 + 1 0 ( x 4 j 一3 一z 句) 4 】，z 舻 问题3e x t e n d e db e a l e 函数： t l 2 m ) 5 心一z 驸( 1 - x 2 j ) 2 + 【2 筋一z 纠( i - - x 掰 + 2 6 2 5 一z 2 j 一1 ( 1 一。乞) 】2 ) ，z 舻 1 2 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 问题4e p e n a l t y l 函数： 从数值结果看，算法2 1 1 在迭代次数的平均值、目标函数和梯度计算次数的平 均值方面比b t r 算法有所减小，因此本算法是有效的 2 5本章小结 本章通过接受那些使p 知 ，7 ，但目标函数的下降量大于以前成功迭代的目标函数 下降量的最小值的试验点，得到了新算法讨论了新算法的全局收敛性，且进行了初 步的数值试验数值的结果表明，对所给出的函数，新算法的表现不比b t r 算法差， 新算法在迭代次数的平均值、目标函数和梯度计算次数的平均值方面比b t r 算法有 所减小如果把新算法与非单调技术结合，算法的效率将会有进一步的提高 1 3 铲z 2 翻 2o一 2 ， z 。触 八 + 2 1 一 5 一 o1 n 岸 i i z ， 广西大学硕士学位论文( 2 0 1 0 年)无约束优化问题信赖域过滤算法的研究 塞窒：! 塾笪岜蕉 问题n 卸 b t r a l g o r i t h m 2 2 1 1 4 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 第三章基于二次模型的非单调信赖域过滤算法 3 1引言 考虑无约束极小化问题z r a i n f ( x ) ，它的信赖域子问题是 r a i n m k ( x k + 8 ) = m ( x k ) + 夕( z 七) t 8 + 8 t - k s s t l 七 其中m ( x k ) = f ( x k ) ，g ( x k ) = v ，( 钆) ，日是近似于f ( x ) 在z 七处的h e s s e 阵v 2 ，( z 七) 的对称阵 记 靠= f t ( k ) 一， 七+ 8 k ) ， o k = m ( x k ) 一m ( x k + s 七) ， 风= 孕， ( 3 1 ) 其中 ( 七) = m a x a j 1 0 j p ( 七) ) ，而p ( k ) 定义为 p ( 忌) = ：n ( p ( 七一1 ) + 1 ，p 薹p 触k - 一。1 刀7 7 ，, ( 3 2 ) p 是大于1 的正整数，叩( 0 ，1 ) 当m 7 7 时，接受s 七，得到新的迭代点z 七+ l = x k + s k ；当p k 刀时，在传统的 信赖域算法中，通常是重解子问题( 2 1 ) ，但现在不立刻重解该子问题，而是按以下两 种情形处理，加大试验点z 毒= x k + 8 k 被接受的可能性 一方面，类似于算法2 2 1 中的讨论，若m 叼，则称迭代失败当p k = 舞叼 时，可能出现以，o k 都i p 4 , ，而当p k 叼时，以有可能较大，它可能比某一次“成功 迭代的目标函数下降量要大，但此时却被认为是“失败”的，这显然是不合理的记 肌为前k 次迭代中成功迭代的目标函数下降量的最小值，即 肌= 。恕。p 成= 爱叩) ， c 3 渤 肌2 。恕。p 成。薏叩， ( 3 3 ) 若以胀，则接受试验点z 毒= 。知+ s 七是合理的 另一方面，在文【1 1 】中为了加大试验点被接受的可能性，考察点z 吉= z 奄+ s 七是 否被过滤子接受，若z 毒= z 七+ 8 k 被过滤子接受，则接受s 七，否则重解子问题在这里 进一步结合文【1 4 ，1 5 】中滤子线搜索的思想，提出n 维滤子线搜索 1 5 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 设j = 矗是使得x k - f 8 k 被滤子接受的最小正整数，其中0 卢 0 ，对称矩阵h o 乳n 肌，常数 7 7 ( o ，1 ) ，卢( o ，1 ) ，( o ，击) ，0 c 2 c 3 1 e l ，p 1 ，计算f ( x o ) ，9 ( 黝) ，令 p ( o ) = 0 ，七= 0 ，q 和p c 是很大的正数，初始化过滤集压 ( 9 0 ，1 ，g o ，n ) t ) s t e p l如果g k 满足终止条件，则终止；否则转s t e p 2 s t e p 2求解子问题( 2 1 ) 得近似解s 奄，0 s 七| l 凫且满足 唑h 七( x k - 4 - 8 k m i i 鲰i im i n 黼a 和 如剑蚓岫 黼a ， 其中丁( 0 ，1 1 s t e p 3 依据( 3 1 ) 式计算p k s t e p 4确定试验步的可接受性 令z 七+ 1 = x k + s k ；若& p 七，则p 七= 以转s t e p 5 ； 贝0 令z 七+ l = z 七+ 8 k ，转s t e p 5 ； 则 ( 3 4 ) ( 3 5 ) l = z 知，转s t e p 5 ；否则转； 若点z 幻被当前过滤集厂接受，则转；否则令q 幻= p q 幻， 孤+ o l s k ，转s t e p 5 1 6 广西大学硕士学位论文( 2 0 1 0 年)无约束优化问题信赖域过滤算法的研究 f 吲蚓l ，c 3 恢1 1 p 奄 1 ，动 1 ，礼) 使得 i 鲰。j i - l 一，j i 一“| | (3109kt i i g k )i 鲰t j i ll j i 0 ，有不等式 i k0 吾，k = 0 ，l ，2 ， ( 3 1 2 ) b k 成立，其中反。麟 i i h , t l + 1 证明令 c = m i n 。磊，c 2 7 e ( 蓟1 - - 西r ) 一z o ，c 2 ，下e c 2 ( 1 - r ) ， 下面利用数学归纳法证明 当1 1 5 七0 a k 时，由s 七的最优性条件知 g k + h k 8 k = 0 1 于是由0 c 2 1 ，有 | i s 圳锗= 黼二i i 风l lzk 6 - k c 当l l s o i i = a o 时，有i i s o l i = a o c a o ，故当k = 0 时，不等式( 3 1 2 ) 成立 假设不等式( 3 1 2 ) 对k 成立，下证不等式( 3 1 2 ) 对南+ 1 成立 ( 3 1 3 ) ( 3 1 4 ) 当l l s 七+ l l l 笔铲豪 因此，在引理剩下的证明中，可假设 川 7 丢5 丢风 由( 3 4 ) 式得 一g t s k 爷1 融孤m i n 南，l i s 川 ( 3 2 1 ) ( 3 2 2 ) 将( 3 2 2 ) 式乘( 1 一叼) 加到( 3 2 1 ) 式，结合i i s 七1 1 2 i i h , i l 一s 舌风s 知，可得 i i s , , 1 1 2 i i h 七i t ( 1 - ? ) 代血n 淼一i i s 七i i 肭i ii i ， ( 3 2 3 ) 根据( 3 2 3 ) 式可知1 1 8 七1 1 1 1 风0 ( 1 一r ) r e 或l i s k l t l l h k l l e 成立，从而由( 3 1 3 ) 式有 i i s k l ll l h 七l l r a i n ( 1 一叩) 7 - ，e ) ， 所以 “t c 2 i i s 七i i 晚南2 赢 麦 至此引理证明完毕 定理3 3 4 设a 1 、a 2 和a 3 成立，l s i = + ，i a i 0 ( 3 2 5 ) 若七c ，设在前k 次成功迭代中的第q k + 1 次迭代的目标函数的下降量最小， 即 p 七= 5 q 。= 3 r a 。3 i 挖n 一。 也i 成= 爰叼) ， 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 由集合c 的定义，有 五( 七) 一 + 1 p 知= = 五( “) 一f q k + 1 冲1 1 乳, , 1 1m i n 卜巡i t h 瓠i i ) o ， 因此由( 3 2 5 ) 、( 3 2 6 ) 式得到五( 七) + 1 ，v k 老1 由( 3 2 ) 式知p ( k 中1 ) p ( k ) + 1 ，从而有 f l ( k + 1 ) = m a x f k + x _ j l o j p ( k + 1 ) ) + l o l o 歹p ( k ) + 1 ) = + l ，l ( 南) ) = 五( 七) ， 所以【五( 七) ) 知 知。非增，又由假定a 1 、a 2 知 五( k ) 七 知。收敛 ( 3 2 6 ) 以下用反证法证明若( 3 2 4 ) 式不成立，则存在常数e 0 ，使得对任意的k ，有 玑i i e ，由引理3 3 3 和( 3 2 5 ) 、( 3 2 6 ) 式以及玩的单调上升性，可得 凤一“三攀r p - e m i n c , e ，麦 由( 3 2 8 ) 式得到 五( k ) 一y k + i a z k ，l ( 七)a + i + a z k + l + n 磊+ p + l ， f l ( k + 1 ) a + 2 + o 磊+ 1 + 2 + o 玩+ p + l ， ： f l ( k + p ) a + v + 1 + a z k + p f k + p + l + o 瓦+ p + l ， 在( 3 2 9 ) 式的两边取最大值，得 f l ( k ) 之m a c h + ：， + 2 ， + p + l 】+ a z k + p + l ，v k k l ， 又 五( 缸+ _ p + 1 ) m a x + l ，a + 2 ，f k + p + l ， 从而有 五( 七) 一五佧+ p + 1 ) a z k + p + 1 ( 3 2 7 ) ( 3 2 8 ) ( 3 2 9 ) ( 3 3 0 ) 广西大学硕士学位论文( 2 0 1 0 年) 无约束优化问题信赖域过滤算法的研究 利用( 3 3 0 ) 式得到 e 1 k k lz k + p + 1 去荟( ，f “叶蹦) )一。岛u u 叫 “制川 = 去( 斯圹觚口+ 1 ) ) ：七七lq 2 0 = 去( 如一如) ) 十。 一2 七l 这与定理假设矛盾定理得证 3 4数值结果 用m a t l a b 编程来实现该算法算法中参数选择与文 5 】相同，分别选叼= o 2 5 ， a o = 0 5 设定的终止准则是m a x l l v f ( x k ) l l ，i f ( x k ) 一f ( x + ) 仔1 0 “或迭代次数超过 3 0 0 时终止程序的运行，利用b f g s 公式修正得到上k + 1 本算法记为a l g o r i t h m 3 2 1 ， 数值试验的结果见表3 - 1 ，其中n 是变量的维数，分别取值为3 2 ，6 4 ，1 2 8 ，2 5 6 ，5 1 2 ；x 0 是初始点；a l g o r i t h m l 是文【5 】给出的带固定步长线搜索的非单调信赖域算法；数值按 迭代次数目标函数计算次数梯度计算次数( p k 叼的次数) 的形式给出 从数值结果看，a l g o r i t h m 3 2 1 比a l g o r i t h m l 有所改善，因此a l g o r i t h m 3 2 1 是 有效的 3 5本章小结 本章在文【4 ，5 】及第二章新算法的基础上，结合非单调技术、过滤技术提出了新 算法，在一定的条件下讨论了新算法的全局收敛性，并进行了数值试验，且与文【5 】的 算法做比较，比较结果是：对所给出的测试函数，新算法在迭代次数的平均值、目标 函数和梯度计算次数的平均值方面比文【5 】5 的算法小 2 1 耋墨! 墼焦些筮 问题 n x 0a l g o r i t h m la l g