（应用数学专业论文）一类带步长的信赖域算法.pdf

摘要 信赖域是解决最优化问题的最有效的算法之一，它具有可靠性、 有效性及很强的收敛性。迄今为止，国内外的许多学者经过研究提出 了多种信赖域方法：拟牛顿信赖域方法，非单调信赖域方法，自适应 信赖域方法等等。本文的主要内容如下： 第一章主要介绍了最优化的相关知识。 第二章介绍了信赖域方法的基本思想，理论，以及几种改进的信 赖域方法。 第三章提出了一种新的带线搜索的信赖域算法。该信赖域算法结 合了线性模型和一维线性搜索。线性模型可以保证在一定的条件下信 赖域产生的方向是下降的，并且可以通过固定的下降方向的公式产生 下降方向，这样可以减少计算量。而当信赖域试探步不满意时，可以 采用线性搜索得到下一个迭代点在适当的条件下，在适当的条件下我 们证明了算法的收敛性和超线性收敛性。数值实验的结果表明该方法 具有有效性。 与第三章中的方法不同的是，在本文的第四章中介绍了一种带固 定步长的信赖域方法。因此这种方法的搜索方向和步长都可以通过固 定的公式产生，得到下一个迭代点。这样可以大大减少计算量。在适 当的条件下，该算法也具有收敛性和超线性收敛性。 关键词无约束优化问题，线性搜索，信赖域方法线性模型，收敛性 a b s t r a c t t r u s tr e g i o nm e t h o di sak i n do fe f f i c i e n ta n dr o b u s tm e t h o dt os o l v e g e n e r a lu n c o n s t r a i n e do p t i m i z a t i o n b e c a u s eo fi t ss t r o n gc o n v e r g e n c e ， r o b u s t n e s sa n dv a l i d i t y , r e s e a r c h e r sh a v ep a i dg r e a ta t t e n t i o nt oi ts i n c e 19 7 0 s m a n yk i n d so ft r u s tr e g i o nm e t h o d s ，s u c ha sq u a s i n e w t o nt r u s t r e g i o nm e t h o d ，n o n m o n o t o n et r u s tr e g i o nm e t h o d ，s e l f - a d a p t i v et r u s t r e g i o nm e t h o dh a v e b e e np r o p o s e d i nc h a p t e r1 ，w eb r i e f l yd e s c r i b et h ea c h i e v e m e n to fu n c o n s t r a i n e d o p t i m i z a t i o n i nc h a p t e r2 ，w em a i n l yi n t r o d u c et h et r u s tr e g i o nm e t h o da n ds o m e r e l a t e dw o r k s t w ok i n d so fn o n m o n o t o n et r u s tr e g i o nm e t h o d sw i t hl i n e s e a r c ht e c h n i q u ea n dac l a s so ft r u s tm e t h o dw i t hl i n e a rm o d e la r e i n t r o d u c e d i nc h a p t e r3 ，an o v e l t yt r u s tr e g i o na l g o r i t h mw i t hl i n es e a r c hf o r u n c o n s t r m n e do p t i m i z a t i o ni s p r e s e n t e d t h ea l g o r i t h mc o m b i n et h e l i n e a rm o d e lw i t ht h el i h es e a r c h i tw o u l dr e d u c et h ec o m p u t a t i o n b e c a u s ei tn o to n l yg e t sd e c e n tt r i a ls t e pi ne v e r yi t e r a t ep o i n tb u ta l s o a v o i d st h ed i f f i c u l t yo fr e s o l v i n gt h e s u b p r o b l e mr e p e a t e d ly g l o b a l c o n v e r g e n c e i so b t a i n e du n d e rs o m es u i t a b l ec o n d i t i o n s n u m e r i c a l r e s u l t si n d i c a t et h a tt h em e t h o di se f f e c t i v ea n dp r a c t i c a l i nc h a p t e r4 ，an e wt r u s tr e g i o na l g o r i t h mc o m b i n i n gl i n e a rm o d e la n d i i f i x e ds t e p s i z ei sp r o p o s e d ，w h i c hr e d u c e st h en u m b e r so fc o m p u t i n g f u n c t i o nv a l u e si nt h el i n es e a r c ha l g o r i t h m u n d e rm i l dc o n d i t i o n s ，w e p r o v et h a tt h eg l o b a lc o n v e r g e n c ea n ds u p e r l i n e a rc o n v e r g e n c eo fo u r a l g o r i t h mu n d e rs u i t a b l ec o n d i t i o n s k e yw o r d su n c o n s t r a i n e do p t i m i z a t i o n ，t r u s tr e g i o nm e t h o d ，l i n e s e a r c h ，l i n e a rm o d e l ，g l o b a lc o n v e r g e n c e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位沦文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：导师签名兰查墨姿日期：丛年上月上日 中南大学硕士学位论文 第一章序言 第一章序言 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一门应用性很强的年轻学科。它研究某些数学上定义的 问题的最优解，即根据实际情况列出目标函数，然后通过合适的方法寻求变量的 值使得目标函数最优。虽然最优化可以追溯到十分古老的极值问题。但是直到 1 9 4 7 年d a n t z i g 提出一般线性规划问题的单纯形法后，它才成为一门独立的学科。 现代科技的发展和计算机的广泛应用，进一步推动了最优化理论和算法的研究。 现在最优化理论与方法已成为决策科学和工程系统分析的重要工具，在经济规 划、政府决策、生产管理、交通运输和军事国防等方面都取得了广泛的应用。并 且已经受到政府部门、科研机构和产业部门的高度重视。 最优化问题的一般形式可归结为求解如下的极小值问题 m i n f ( x ) ( 1 - 1 ) j e r “ 其中，x r “是决策变量，( 力为目标函数。 凸性在最优化理论和方法中的研究中起着重要的作用，因此我们首先介绍凸 集和凸函数的基本概念。 定义1 1 设s 亡r ”，如果对任意x 。，x 2 s ，有 a z l + ( 1 一a ) x 2 s ，v a l o ，1 j ， 则称s 是凸集。 定义1 2 设s 尺“是凸集。若函数f ：r ”jr 满足： f ( a x + ( 1 一口) 少) a f ( 石) + ( 1 一a ) f ( y ) ， v x ，y s ，v a 【o ，l j ， 则称厂是s 上的凸函数。 下面我们给出全局最优解和局部最优解的定义。 定义1 3 若x ”r ”具有性质：v x r ”，均有f ( x ) f ( x 。) ，则称x 为问题( 1 - 1 ) 的全局最优解。 定义1 4 若x “r ”具有性质：存在x 的某个邻域艿( z ) = kx - - x * 0 0 为某个正数，使得v x n a ( 工+ ) ，均有f ( x ) f ( x + ) ，则称x + 为问题( 1 1 ) 的一个局部最优解。 中南人学硕士学位论文第一章序言 在一般情形下找出全局最优解是一个非常困难的任务，通常在许多实际应用 中，求局部最优解已经满足了问题的需要。因此，在实际算法中，我们通常是找 出满足一定条件( 最优性条件) 的局部最优解即可。当目标函数f ( x ) 是凸函数 时，局部最优解就是全局最优解。本文采用如下的记号：以= f ( x k ) ，g 。= v f ( 以) ， g ( x ) = v 2 ( 功。下面我们给出点工是无约束问题( i - i ) 的局部最优解的必要条 件： 引理1 i i l i ( 无约束优化的一阶必要条件) 若x 为问题( i - i ) 的一个局部最优 解，且在工+ 的领域内f c 1 ，则 g ( x + ) = 0 。 引理1 2 1 1 i ( 无约束优化的二阶必要条件) 若x + 为问题( 1 - 1 ) 的一个局部最优 解，且在石的领域内f c 2 ，则 g ( x ) = 0 ，g ( x ) 0 。 收敛速度是衡量最优化方法有效性的重要方面，下面我们给出关于收敛速度 的定义。 定义1 5 设点列 x 。) cr ”收敛于x 。 ( 1 ) 若存在常数u ( o ，1 ) ，使得当j | 充分大时， i i x 。+ 。一x i i 1 ，存在常数m 0 ，使得当k 充分大时， h x x 忙m 恢一石n 则称x 。) 的收敛速度是p 。 ( 3 ) 若存在常数m 0 ，使得当k 充分大时， 0 石。+ 。x i _ mx 。- - x * 1 1 2 ， 则称x 。) 二次收敛于x + ，或称k 的收敛速度是二次的。 一般认为，具有超线性收敛速度和二阶收敛速度的方法是比较快速的。但是 对于任何一个算法，收敛性和收敛速度的理论结果并不保证算法在实际执行时一 2 中南人学硕十学位论文第一章序言 1 2 无约束优化问题的主要方法简介 迭代法是求解无约束优化问题( 1 1 ) 的基本方法。其基本思想是给定一个初始 点而r ”，按照某一迭代规则产生一个点列扛。 ，使得当k 是有穷点列时， 其最后一个点是最优化模型问题的最优解。当扛。 是无穷点列时，它有极限点， 且其极限点是最优化模型问题的最优解。 一个好的算法应具备的典型特征为：迭代点以能稳定地接近局部极小点石 的邻域，然后迅速收敛于x 。当给定的某种收敛准则满足时，迭代即终止。一 般的，我们要证明迭代点列b 。 的聚点为一局部极小点。在具体实现上可分为线 搜索方法和信赖域方法两种不同的策略。我们首先来看线搜索方法。它的基本思 想是：对于当前的迭代点以，首先确定一个搜索方向d 。，使得目标函数f ( x ) 的 值沿该方向是下降的，然后确定沿d 。方向行进的步长以并得到下一个迭代点 x k + 。= x k + 2 k d 。在线搜索策略中关键的两步是构造搜索方向d 。和确定步长以。 事实上构造搜索方向和确定步长有很多种方法，不同的步长九和不同的搜索方 向d 。构成不同的方法。绝大多数的线性搜索算法要求d 。是一个下降方向，也就 是 g ：畋 0 ， 以此保证函数f ( x ) 在以点沿以方向下降。 求解无约束问题的下降算法的基本思想是从某个初始点出发，按照使目 标函数值下降的原则构造点列，即点列扛。 满足条件f ( x 川) 0 ，令尼= 0 。 步2 若恬。忙g ，则终止算法，得解以。否则，转步3 。 步3 确定下降方向d 。，使得 g ：dk 0 ，使得 f ( x t + d ) 0 ，p ( o ，1 ) 。令以= 。 步3 若以满足( 1 - 2 ) ，则终止计算，并得步长以。否则，转步4 。 步4 令以：_ 肌。转步3 。 w 6 l f e 搜索准则 步长以满足 一 + l 一仃i 五女g 女t d 女， g k r l d t 盯2 9 女t d 。 ( 1 3 ) ( 1 4 ) 其中0 q 盯2 0 ，p ，( 0 ，1 ) 。令雒集合 力7 ，i = 0 ，l ，2 ， 中使 4 中南大学硕士学位论文第一章序言 得( 1 3 ) 成立的最大者。令f = 0 。 步3 若疋满足( 1 - 4 ) ，则终止计算，并得步长以= 雒。否则，令= p - 1 雒。 转步4 。 步4 令雒+ 1 是集合般+ ( 以n 一雒，f = 0 , 1 ， 中使得( 1 - 3 ) 成立的最大者。 令i ：= i + l 。转步3 。 强w o l f e 搜索准则 步长以满足 一以+ l 一仃l 允女g t j i ， l g , r 。d 。i o r ：g 。t 或。 其中0 q ， 参数反的确定有很多种方法，主要有 胪= 砾g r ( g 瓦, - g k q j ) 霞= 器 酽2 紫 孵= 肛热 ( h s 算法) ( f r 算法) ( p r t 算法) ( c d 算法) ( d y 算法) 这些共轭梯度法采用线性搜索在适当的条件下具有全局收敛性l9 1 5 l 。 中南大学硕士学位论文第二章信赖域算法 第二章信赖域算法 2 1 传统的信赖域方法 信赖域方法是另一类保证算法全局收敛的好办法。它在近三十年来受到了非 线性优化界非常的重视。信赖域方法是一类较新的方法。信赖域方法的研究起源 可以追溯到l e v e n b e r g l l 5 1 和m a r q u a r d t l l 6 i 关于非线性最小二乘问题的求解。1 9 7 0 年p o w e l l 在 1 7 中讨论了无约束优化问题的信赖域算法及子问题的求解，并且在 1 8 中 = i e 明了信赖域算法的收敛性。自此以后越来越多的学者开始关注并研究这 种方法1 1 9 - 2 6 l 。目前，信赖域方法和线性搜索方法并列为非线性最优化的两类主要 的数值计算方法。与线性搜索方法相比，信赖域方法直接通过模型求解得到试探 步长，而不是先确定搜索方向，再寻找步长。 信赖域算法的基本思想是：在当前迭代点x 。，给定一个信赖域半径a 。 0 ， 然后在以赡为中心。为半径的小领域内，用一个二次函数逼近目标函数f ( x ) 。 用该二次函数在屯的邻域内的极小值点发作为下一个迭代点，。设以是下面问题 的解： 1 m i n 仇( d ) = 厶+ g ：d + 去d 7 b 女d ( 2 - 1 ) 二 s j i i d l l a t ， ( 2 - 2 ) 其中b r ”是f ( x ) 在以的h e s s i a n 阵或其近似。( 2 一1 ) - ( 2 - 2 ) 称为信赖域子 问题。通过求解子问题得试探步d 。，然后利用某一评价函数来决定是否接受试 探步以及确定下一次迭代的信赖域半径，如果试探步被接受，则以+ 。= 屯- i - d 。， 否则坼+ 。= ；信赖域半径的大小通过迭代逐步调节，粗略地说，如果当前迭代 模型较好地逼近原问题，则信赖域半径可扩大，否则将缩小。 设信赖域子问题的解为矾，定义a r e d 。为f ( x ) 在第k 步的实际下降量： a r e d t = 以一f ( x 女+ d 女) ， p r e d 。为对应的预测下降量： 定义比值 p r e d t = 六一吼( d ) ， 9 中南火学硕十学位论文第二二章信赖域算法 一a r e d i 成2 而 n 从某种角度反映了二次模型仇( 以) 与目标函数( x 。+ 以) 的近似程度。若r 接 近1 ，则认为二次模型纯( 以) 在信赖域d 上与目标函数f ( x 。+ 以) 的近似程度很 好。因而，此时可扩大信赖域半径。反之，若成离1 较远，则可认为二次模型 依( 以) 在信赖域d 上与目标函数f ( x 。+ 以) 的近似程度不好。因而，此时应缩小 信赖域半径，以提高纯( 以) 在信赖域d 上与e t 标函数f ( x 。+ 以) 的近似程度。下 面的信赖域模型是由p o w e l l ( 1 9 7 5 ) 给出的。 算法2 1 步1 给定初始点x o ，0 占 0 ，b o r 删，0 c 3 c 4 1 c l ， 0 c 2 0 ，x 川= x t + d 女，否则x k + i = 吒。 选取a 川使其满足 。+ 。t c , i i d ，c k 。i ! , 。c 。4 】a i 1 髁如果p ，9 k 。 1 ，占 0 ，令兄：= 0 。如果b 是正定的，转步2 ；否则，在 o ，i i b i i + ( 1 + f ) l l g l l a i 中寻找使得b + 甜证定的五。 步2 做c h o l e s k y 分解b + 甜= r r r 。解方程组 r 7 r d = 一g 得到d 。 步3 如果i ，停止；否则解 r 7 g = d ， 得q 。计算 兄：五十l l d l l _ = r l l d l l - a ， 2 转步2 。 信赖域方法的一个突出特点是它具有总体收敛性。 定理2 1 川( 信赖域方法总体收敛性) 设gcr ”是有界集，以g ，对任何的k 中南大学硕士学位论文第二章信赖域算法 都成立，若厂c 2 ，在有界集g 上忙。忙m ，m 0 。则信赖域算法产生一个满 足一阶和二阶必要条件的聚点x 。 定理2 2 1 l l 如果定理2 1 中的聚点x 。还满足厂( 石) 的h e s s i a n 矩阵g 。是正定的条 件，那么，对于主序列，有以专l ，吒专z 。，g l b ( a i ) 0 ，( g l b ( a t ) 表示女的 总体最小界) ，以及对于充分大的k ，约束侧 0 ，c 1 ，c 2 ，c 3 ，c 4 满足0 c 3 c 4 1 c i ，0 c 2 1 。 令k - 1 。 步2 求解子问题( 2 1 ) 一( 2 - 2 ) 得近似解畋，0 d 。i i a 。且满足 ( a ) p r e d 。f i g 。 m i n a 。，i i g 。i i b , i i ， ( b ) g 。t d 。一f o g 。u m i n a 。，0 9 。l l i i b 。i l 。 步3 计算厂( 五十矾) ，如果厂( 吒+ 以) f ( x t ) ，转步4 ；否则取i 。是满足 f ( x k + d f ( x 。) 的最小正整数，其中碰满足 计算 转步5 。 步4 计算 和 + 1 | l k ：状 c o s ( ( d 黔一g 。) ) c o s ( ( 以，一g 。) ) ； x k + l = x k + d ， 。+ 。 i k + 。一以l i ，c 。 ； x t + l = + d t ， p k2 1 k f k “ 纯( 0 ) 一纯( d ) 如果p k c ：并且0 以f l a 。令= a 。否则，定义 a + l 如果成 c 2 0 口l 口2 1 如果以c 2hi i , z 。l l = 。 步5 计算g 川和b 川：令k = k + 1 ；转步2 。 作者在 3 7 中i i e n 了算法的收敛性。 假设2 1 1 ) 由算法2 3 生成的点列k 是有界的，也就是说 x k s ， 1 3 ， 以， 垆加以夕 j ik 陋 ，j、【 中南人学硕十学位论文 第二章信赖域算法 对所有的k 都成立，s r ”是闭凸集。 2 ) f 二次可微并且存在常数m 使得 g ( x ) 忙m ， 对所有的孔s 都成立。 引理2 3 。3 7 。如果存在o 万 o 对所有的k 都成立，并且假设 2 1 成立， 椎+ 。是由算法2 3 的步4 产生的，或者以 c 2 ，那么当k 充分大， a 。l l d 。忙m i n , u ( 1 - c ：，o m 。， 成立。 引理2 4 3 7 。如果存在o 万 o 对所有的k 都成立，并且假设 2 1 成立。+ 。是由算法2 3 的步3 产生，那么存在常数0 m i n t 7 0 - - c ：，1 ) m 。， 成立。 引理2 5 。3 7 1 如果存在o 0 ，f 0 ，( 0 , 1 ) ，( 0 , 1 ) ，c l ，c 2 ，c 3 ，满 足0 c 3 c 2 0 ，使得l 旧。i l 仃对所有的后 都成立，那么由算法2 4 产生的点列满足 h m i n f l l g t l l = 0 。 2 3 带线性模型的信赖域方法 近来，一种基于线性模型构造出来的信赖域算法被提出，该算法与一般的信 赖域算法有所不同，它不是用一个二次函数去逼近目标函数，而是采用一个线性 模型去逼近目标函数，这种带线性模型的信赖域方法在约束中利用的是椭球范 数。这种算法的优点在于线性模型能够直接求出迭代步，并日每次迭代步产生的 方向都是下降方向。因此该算法大大地减少了计算量，从而提高了算法的效率。 首先考虑目标函数的泰勒展式 1 一 厂( + j ) = 以+ g ：j + j 。g ( 六) s ， ( 2 - 7 ) 其中，g ( x ) 是目标函数的h e s s i a n 矩阵。那么我们可以得到( 2 - 7 ) 的线性模型 1 5 中南大学硕士学位论文第二章信赖域算法 为， m i n m t ( d ) = 以+ g r d 她j d r b 。d 卜缱 g r d 0 ， ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 因为五+ g r d 是一个线性函数，那么g r d o 不是一个有效约束。因此，( 2 - 8 ) 一 ( 2 1 0 ) 等价于子问题 m i n m 女( d ) = 以+ g r d ( 2 - 1 1 ) 姒l d r b 。d l 缱， ( 2 1 2 ) 引理2 4 1 5 9 l 如果b 。是正定的，那么子问题等价于 m i n m ( d ) = 六十g 女t d ( 2 1 3 ) 姒i d r b 。d i = 。 ( 2 1 4 ) 引理2 5 1 5 9 i 如果b 是正定的，那么子问题( 2 1 1 ) ( 2 1 2 ) 的解为 如一惫哦t 。 ( 2 - 1 5 ) 证明由引理2 4 可知，( 2 1 0 ) ( 2 1 1 ) 等价于问题( 2 1 2 ) ( 2 1 3 ) ，根据约 束问题的最优化条件町知，问题( 2 1 2 ) - ( 2 - 1 3 ) 的l a g r a n g e 函数为 l ( d 。，f 1 ) = f ( x 。) + g 。t d 。一( i d 二曰。d 。i 一：) 。 根据约束问题的一阶最优化条件，得 v d ( d 女，) = g 一8 t d = 0 。 ( 2 1 6 ) 因此 小学- 1 。 沼1 7 ) 将( 2 1 6 ) 代入( 2 1 7 ) 得 即。= 学吼字= 訾4 那么 = 訾， 1 6 中南大学硕士学位论文第二章信赖域算法 将( 2 - 1 8 ) 代入( 2 - 1 7 ) 得 驴一惫何t 。 算法2 5 步1 给定0 ，z o ，【0 ，0 2 5 ) ，0 气 1 ，以+ l = 以+ 以，用适当的方式修正b 得到b 川。k ：= k + 1 ， 转步2 。否则吒+ l = 以，b k + l = b t 。k ：= k + l ，转步3 。 定理2 6 印假设f 。= 0 ，k ) 是有算法2 5 产生的点列，并且满足 ( 1 ) g ( x ) 是一致连续的； ( 2 ) 1 1 8 忙m 。，何1 m 2 。 那么，l i m i n f l l g 。0 = 0 。 r ，一 1 7 中南大学硕士学位论文 第三章一种新的带线性搜索的算法 第三章一种新的带线性搜索的算法 考虑求解无约束优化问题 m 删i n f ( x ) ， ( 3 - 1 ) 其中厂：r ”- - r 是连续可微的。信赖域方法是求解( 3 1 ) 的一个非常有效方法。在 第二章我们介绍了【4 8 构造的信赖域与一维搜索组合的非单调信赖域算法，即当 信赖域试探步不满意时，再采用线性搜索得到下一个迭代点，这样就避免了传统 信赖域方法中有时要解若干次信赖域子问题的缺陷。但 3 8 中的信赖算法产生的 方向不一定是下降方向，因此线搜索是不一定成功的。而与 3 7 ，4 8 等算法有所 不同，【5 9 基于线性模型构造的一个信赖域算法，每次迭代步产生的方向是下降 方向。因此，可以与线性搜索结合来减少计算量。本文采取将 5 9 】中提出的信赖 域线性模型和线性搜索相结合的方法，从而提高了算法的效率，最后证明了该算 法的全局收敛性和超线性收敛性。 3 1 算法 考虑子i 司题 m i n m 女( d ) = 五+ g t d ，( 3 2 ) j tl d k b 。d i 缱( 3 - 3 ) 根据 5 9 中的结论可知当b 。正定时， 子问题( 3 - 2 ) 一( 3 3 ) 的解为 咖一惫瑰。 下面给出算法： 步1给定x 0 r ”，b o = ，o 0 ，( o ，1 ) ，( 0 , 1 ) ，口( 0 , 1 2 ) ， 0 f l f 2 1 r 3 ，0 s 0 雠4i g ( x ) - g ( y ) 0 lx - y i ， v x ，y r ”。 假设3 3 慨i i - q , ，恢i i - 0 ，使得恬。忙占， v k ，则存在u 0 ，有 a t v z ， k ，( 3 6 ) 其中z t2m a xb ti i + 1 。 证明假设不存在u 0 ，使得对所有的k j ，( 3 6 ) 成立。即对于任何u 0 ， 存在k 1 ，使得 根据算法可知， a 0 ，存在后i ，使得 a t 0 ，有 a u 乙，( 3 8 ) 对充分大的尼都成立，其中乙= 懋f l 反1 1 + 1 。 证明如果只有有限多个七使得川。，那么存在常数万 o ，使得。 8x c n 有的后都成立，那么 岭跏象 令p = 钇o ，( 3 8 ) 成立。 如果有无限多的后使得m 女成立，由引理3 2 可知，存在云，当后f ， 2 l 中南人学硕士学位论文 第三章一种新的带线性搜索的算法 并且m 。成立时，( 3 8 ) 成立。令= m a x j j ej j t j 七 。根据的定义 可知 v z i ，并且+ j i 叉e f s = l ，2 ，k j j c 都成立。因此 ；+ l a i + 2 + ：a k ， 如果r ，l r , v z i + 2 r l v z i , + ， 因此可知存在u 0 ，使得a 。v z 。对充分大的k 都成立。 弓l 理3 4 1 设 。 和 m 。 是任意两证数列。如果存在j 下常数d 0 ，o c ， 1 ，使得 则必有 a 女+ l e l a t ， a j + l c 2 a t a i v z | i ， m + l m t ， y1 m 。 0 ，使得。v z 。，对于充分大 中南大学硕士学位论文 第三章一种新的带线性搜索的算法 的尼都成立。因为b 。正定并且假设3 3 成立，因此可知1 z i = 。由引理3 4 可知( 3 - 9 ) 式成立。矛盾。因此1 凹刊g t i i = o 。 假设3 4 由算法3 1 产生的点列x k 收敛于点x ，g ( x + ) = 0 ，g ( x + ) 正定。 假设3 5 厂在开凸集dcr ”中二阶连续可微，且存在x 的一个邻域( x 。，占) 和 常数y 0 ，使得 i i g ( 工) 一g ( 孑) 0 r l l x - 孑l | ，五孑( x ，g ) 。 定理3 2 如果假设3 1 假设3 5 都成立，并且 则算法3 1 产生的点列k ) 超线性收敛于工+ 。 = 0 ， 证明 因为g ( x ) 正定，那么存在常数m 0 ，使得 z r g ( x ) z - m i i z l 2 ，v z r ” 对所有的z q = xx - - x * i i 都成立，其中是很小的数。 历吨卜g 二d k = d j c 訾枞 1 ) 如果以 1 ，那么 由泰勒展式可得 n a g ：d k - 眠+ 每 m 。+ 告= 以+ 告咖。+ 参粕( 驯。 ili引l j 一 ” 一 一 一 g 一 一 一j 川反一忪 i 慨 。一 t ( 1 - , z ) p o ( 1 t d 。n m i l d 。1 1 2 成立。 2 ) 如果以= 1 ，以 堕铲也成立。 因为1 ) 和2 ) 可知k 充分大时，有以 ( 1 一口) 夕 成立。又因为 i i x 川一以0 = 忆以忙a k di o 因为x 。) 收敛，因此当七一o o 时，i i d 。0 专0 。综上所述，当七专0 0 时，i i d 。l lj 0 。 由于x 。 收敛于点x 。，g ( x + ) j 下定， 办- 1 l =1 k f ( x t+ d 女) 又由中值定理可得 l m t ( d ) 一f ( x 因此， r e ( o ) 一m ( d t )斗 m 女( d 女) 一f ( x t + d 女) m ( o ) 一m ( d ) ， + d 。) l = k + g 飘一( 以+ l g ( + 甜。) 7 以d 秒) = i l ( 出。+ ) 强) d 叫 扣1 1 2 = o ( 1 l d 。1 1 2 ) ， p t - 1 i = 2 4 一 竺必 o 专 0 一h以k 训一伙 中南人学硕十学位论文 第三章一种新的带线性搜索的算法 因此可知，当以专1 。也就是说当k 充分大时，以= 1 ，s i = d i 。 由于风铲一瓯m k g t 峙 a t g t ，那么 曰。一g c x ， s 。= 一g 。一g c 石，s 。 = 【g t + i g i g ( x ) s t 】一g + i ， 那么，l i g 川一乳一g + ) s 。0 = f g ( + 乡( 石川一以) ) d ( + ，一坼) d o g ( x + ) j 。 又因为 那么， = i i f g ( 石。+ o ( x k + i - - x k ) ) 一g ( 石+ ) 】s 。d o i l l g ( x 。+ 秒( z 。+ 。一工。) ) 一g ( x + ) j 。l p 秒 厂l | j x 。+ 秒( 石。+ 。一x k ) - - x * 洲s 。i p 臼 恢+ 乡( 。- x 。) - x = o - a ) x t + 良“l 一石 忪一p ) ( 以一工) + 口( 。一x ) j i - l i i x k + 。一x l l 。 因此 蚴坐竺二剑 u s k l l 一( 0 x 。一石+ 0 + i i x “。一x 0 ) 其中，= ( k ，一x l l l x k x 机 因为( 3 1 3 ) 成立，所以 显然， 这就意味着k ) 超线性收敛于x 。 l i m r k = 0 ， 七 一 3 3 最小二乘问题的信赖域方法 作为一个最优化问题，非线性最小二乘问题l j 丁以用一般的最优化方法求解， 因此我们可以用类似于算法3 1 的方法来解决非线性最小二乘问题。 考虑无约束最小二乘问题 m i n f ( x ) 2 互1 州以) = 三私( 列2 ， ( 3 - 1 4 ) 其中x r ”，( 工) r ”，( x ) 是非线性残量函数。 考虑( 3 1 4 ) 的泰勒展式 中南大学硕十学位论文 第三章一种新的带线性搜索的算法 g ( d ) = f ( x k ) + g ：d + 三d 7 j r j k d ， ( 3 一1 5 ) 其中，j 女表示，( x ) 在x i 处的j a c o b i 矩阵。 为了保证，7 j 的正定性，一般在( 3 1 5 ) 中加入一个扰动得到 g ( d ) = f ( x k ) + g ：d + 三d 7 ( j r j k + 从i ) a ， 其中心= l l r ( x 。) 0 。为了方便，记哌= ( j 二以+ 以j ) 。 根据上一节的讨论，可得到问题( 3 1 4 ) 的带线性模型的信赖域的模型为 m i n g ( d ) = f ( x ) + g t t j ( 3 1 6 ) s j d7 d 之，( 3 1 7 ) 因为q ( c 1 ) 是线性函数，因此，问题( 3 1 6 ) 一( 3 1 7 ) 等价于 m i n q ( d ) = f ( x k ) + g r d ( 3 1 8 ) s t d r 睨d = ， ( 3 1 9 ) 毗删砸i j ( 3 1 6 ) - ( 3 1 7 埔砌妒一南吼t 。 对于问题( 3 1 6 ) ( 3 1 7 ) ，我们同样可以给出类似于算法3 1 的算法。 算法3 2 步1 取x o r ”，( 0 , 1 ) ，a o 0 ，k ：= 0 。 步2o n 果l l g 。l l = 0 ，算法终止。 步3 求解子问题( 3 1 6 ) 一( 3 - 1 7 ) 得 d k - 一彘w k 计算 鲈掣。 步4 如果n 转s t e p4 ；否则取九为 l ，2 ， 中满足下式的最大数： f l x k + 2 dk ) - ls a 九g ：dk ， 令以+ l = 以+ 以d i ，a 川= r l a t ，f 2 a 女】，转步6 。 2 7 中南大学硕十学位论文第三章一种新的带线性搜索的算法 步5 令坼+ l = 吒+ d t ，a 川 女，f 3 a 】，转步6 。 步6k - k + 1 转步2 。 记集合，= 取：p k ) ，j = 伽：p i ) 。 我们同样可以得到算法3 2 的收敛性定理。 引理3 5 以单调下降。 证明如果k ，由算法可知五“一 c t 2 9 r d t 0 ，那么有 “ 0 ，以+ l 以也成立。因此可知 单调下降。 定理3 3 假设g ( x ) 是l i p s c h i t z 连续的，i i h 。i i - - q , ，i i 町1 i i 0 ，当k 充分大时 有l l 哌l i q 3 。由此，接下来我们可以用类似定理3 1 的方法证明算法3 2 的收敛 悻。 3 4 数值实验 在本小节中，我们分别用传统的