（运筹学与控制论专业论文）psb信赖域线搜索型算法.pdf

硕十学化论史 摘要 首先，本文结合信赖域和线搜索技术提出一种信赖域一线搜索型拟n e w t o n 算法， 算法中采用p s b 修正公式对拟n e 毗o n 矩阵进行修正当信赖域试探步不被接受时， 我们得到一个下降方向，并使用a r m i i o 线性搜索后得到下一个迭代点，这样有效地 避免了重复计算信赖域子问题并且，在不要求鼠一致有界的前提下，我们证明算 法的全局收敛性和超线性收敛性 在此基础上，我们将g r i p p o 等提出的非单调线搜索技术引入本文提出的p s b 一 线搜索型信赖域算法中，并进行了数值计算数值计算结果证实了p s b 信赖域一线搜 索型算法2 5 1 的可行性和有效性而且，采用非单调线搜索算法的数值效果较单调 搜索算法好 关键词：p s b 修正；非单调线性搜索；信赖域方法；全局收敛性；超线性收敛性 a b s tr a c t i nt h i sp a p e r ，、v ep r o p o s eat r u s tr e g i o n 1 i n es e a r c hq u a s i n e w t o nt y p em e t h o df o r s o l v i n gu n c o i l 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 8 w bu s ep s bu p d a t ef o r m u l at ou p d a t e t h eq u a s i n e w t o nm e 七r i c s w h e nt h et r u s tr e g i o nt r i a ls t e pi sn o ta c c e p t a b l e ，w eo b t a i n ad e s c e n td i r e c t i o nf o rt h eo b j e c t i v ef u n c t i o n w bt h e nu s ea na r m i j ot y p el i n es e a r c h t oo b t a i na s t e p l e n 酷ha n dd e t e r m i n et h en e x ti t e r a t e u n d e ra p p r o p r i a t ec o n d i t i o i l s ， 伦p r o i v et h eg l o b a la n ds u p e r l i n e a rc o h v e r g e n e eo ft h e l e t h o dw i t h o u tr e q u i r e m e n t o ft h eb o 瑚1 d e d n e s so ft h eq u a s i - n e w t o nm e t r i c s ， w 色t h e ni n t r o d u c ean o n m o n o t o n el i n es e a r c ht e c h n i q u et ot h em e t h o da n d p r 伊 p o s eat r u s tr e g i o nn o n m o n o t o n el j n es e a r c hm e t h o d w _ ea l s od os o m en u m e r i c a l e x p e r i m e n t st ot e s tt h ep r o p o s e dm e t h o d s t h er e s u l t sa l s ot h ee 髓c t i v e n e s so ft h e p r o p o s e d 。m o r e o v e rt h ep e r f o 聊a n c eo ft h en o n m o n o t o n et y p em e t h o dp e r f o r m sb e t - t ：e r k e yw b r d s ：p s bu p d a t e ；n o n m o n o t o n el i n es e a r c h ；r 】u s tr e 百o nm e t h o d ；g l o b a l c o n v e r g e n c e ；s u p e r l i n e a rc o n v e r g e n c e i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均己在 文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者橼尹履国魄7 年岁月歹占日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密曰。 ( 请在以上相应方框内打“) 作者签名 导师签名 日期：哆年岁月“日 日期：d 罗年多月必日 硕士学位论文 第1 章绪论 1 1无约束优化问题算法概述 考察如下无约束优化问题的求解： m i n ，( z ) ， z 月， ( 1 1 ) 其中：，：郧h 尉匡续可微 求解非线性优化的常用方法有线搜索类型的方法和信赖域算法【1 】，两类算法 均为迭代法，算法产生迭代点序列 吼) 线搜索类算法的迭代过程大致如下，在当 前迭代点处按某种规则产生一个下降方向，然后沿该方向进行线性搜索确定下一 个迭代点，通常使得函数值序列呈单调递减性 下降方向的定义如下： 定义1 1 1 【1 l 设z ，d 毋若存在数a 0 ，使得 ，( z + q d ) 0 ，使得 v ，( z 七) t 毗 o 满足： 厂( z 南+ q 七d 忌) ，( z 奄) + 肛q 后v ，( z 七) t 以，( 1 3 ) v ，( z 七+ q 詹也) t d 七盯v 厂( z 知) t d 南，( 1 4 ) 另一种常用的线性搜索方法是强w - 0 1 f e 线性搜索：该线性搜索中a 七同时满足条 件( 1 3 ) 和下面的不等式 v 厂( z 詹+ q 凫毗) 丁也i 盯iv 厂( z 知) t 毗i ( 1 5 ) 当_ o 时，式( 1 5 ) 的极限就是精确线性搜索 有关线搜索类算法的全局收敛性研究已目趋成熟【1 】总结了该类算法的全局 收敛性我们介绍如下： 设以表示向量比与，的负梯度方向一v 厂( z 南) 的夹角，即 c o s 忙黼 线搜索类算法具有如下收敛性定理： 定理1 1 2 【1 】 设厂连续可微有下界，且v ，l 咖s c 九i t z 连续，即存在常数l 0 ，使 得 i iv 2 厂( z ) 一v 2 ，( 可) i i f 墨l | | z 一可i i ，v z ，可 硕士学位论文 z 知) 由采用a r m i j o 型线性搜索的算法1 1 1 产生，即q 七满足( 1 2 ) ，若存在常数e o ， 使得 l i v ，( z 七) l i c l l 比 则 l l v ，( z 詹) | 1 2 c o s 2 巩 0 ，使得c o s 巩6 ，则 ( 1 6 ) 1 蛔i l v ，( z 七) 0 = o 采用w o l 珏p o w e l l 型线性搜索的算法1 1 1 具有类似的收敛性定理而且此时条 件( 1 6 ) 可以去掉 定理1 1 3 【1 】 设定理1 1 2 的条件成立， z 七) 由采用w r o l 触p o w e l l 型线性搜索的算 法1 1 1 产生，即q 七满足( 1 3 ) 和( 1 4 ) 则 特别，若存在常数6 0 ，使得c o s 以6 ，则 ，l i ml i v ，( z 七) | i = o 关于线搜索类算法我们有如下收敛速度估计： 定理1 。1 。4 1 】设函数，：舻一冗二次连续可微点列 z 是) 南算法l 。1 。1 产生，其 中步长a 七由a r m i j o 型或w o l 俗p o w e l l 型线性搜索确定，若盯1 ( o ， ) 设 z 知) _ z + ， 且v ，( z + ) = o ，v 2 ，( z + ) 正定若 熙幽瑞孚剑- 0 ， ( 1 7 ) 则 ( 1 ) 当七充分大时，0 f 凫= 1 ( 2 ) 序列 矾) 超线性收敛于z + 信赖域方法是求解无约束优化问题( 1 1 ) 的另一类重要方法与线搜索方法产 生迭代点不同，信赖域方法首先定义一个在当前点与目标函数近似的二次模型，利 用目标函数在一定的区域内与二次模型的充分近似，取二次模型的最优值点作为 信赖域方法的下一个迭代点，这里一定的区域构成信赖域方法的信赖域若新的迭 代点不能使目标函数值有充分的下降，说明二次模型与目标函数的近似程度不够 好，需要缩小信赖域半径然后找对应于新的信赖域的二次模型的最优值点，将其 作为信赖域方法的新的迭代点 一3 一 p s b 信赖域一线搜索掣算法 信赖域半径对算法的效率至关重要如果信赖域半径较小，二次模型与目标函 数虽有较好的近似，但可能失去使下一个迭代点与目标函数的最小值点更靠近的 机会，当然会影响算法的效率如果信赖域半径过大，又会使得二次模型的极小点 与目标函数的极小点距离较远以致目标函数值得不到下降实际计算时，一般根 据上一次迭代过程中二次模型与目标函数的近似程度来确定下一个信赖域半径 一般地，信赖域模型为： m i n 吼( d ) = + 鲧d + 矿b 七d ， s t i idi l 知 ( 1 8 ) 其中： = ，( 轨) ，鲰表示厂( z ) 在处的梯度，反舻加是厂( z ) 在z 七处的h e s s i a n 矩阵 或其近似，知 一。称为信赖域半径 设( 1 8 ) 的最优解为毗，则 厂( z 七+ 比) 一饥( 以) = d ( i i 巩1 1 2 ) ， 进一步，若风= v 2 厶为厂在处的h e s s i a n 矩阵，则 ，( z 奄+ 毗) 一锨( d 七) = d ( 1 i d 岛1 1 2 ) 下面我们考虑吼( 毗) 与，( z 七+ 毗) 的近似程度，并依此作为决定下一次迭代时的 信赖域半径_ 为此j 定义预估下降量尸r 也和实际下降量a r e 出如下： 所啦- ，( 硝一删a 肌虻m 沪m 七+ 砒= 畿 一般地，p r e 以 0 。若弦 o t 步1 ( 收敛性检测) 若l i v 厂( z 七) i i s 则算法终止，得问题的解毗否则，转步2 步2 ( 子问题求解) 求解( 1 8 ) 得毗 步3 ( 信赖域修正) 计算“，若弦 ；，则恕+ l = m i n 2 七，) ；否则，七十1 = 七 步4( 可接受检测) 若 叩，则z 七+ 1 = z 七+ 也；否则，z 七十1 = z 岛，转步1 一4 硕十学位论文 由于子问题( 1 8 ) 的可行域有界，因此，算法1 1 2 的步2 中的如存在下面的定理 说明，若z 奄不是问题( 1 1 ) 的稳定点，则预估下降量纵( 如) = ，( z 惫) 一鲰( 如) o 因 此，算法是适定的 信赖域算法具有如下性质： 定理1 1 5 【1 j 设也是问题( 1 8 ) 的解，若v ，( z 七) o ，则 q 七( d 七) = ，( z 惫) 一q 知( d 知) o 推论1 1 1 【1 】设由算法1 1 2 产生，则序列 ，( z 七) ) 单调非增 定理1 1 6 【1 l设函数，连续可微有下界，且存在常数p o ，使得f i 瞰l i p 若算 法1 1 2 中取叼= 0 ，则 l i m i n f i | v ，( z 七) i l = o 定理1 1 7 f 1 j 定理1 4 6 的条件满足，且v 厂己印s c 危札舷连续若算法1 1 2 中取叩 0 ，则 。l i mi i v ，( z 七) i l = o 下面的定理给出了n e w t o n 型信赖域算法( 即算法1 1 2 中取玩= v 2 ，( z 膏) ) 的收 敛速度估计 定理1 1 8 f 1 】设，c 2 有下界，且由n e 毗o n 型信赖域算法产生的点列 z | | c ) 有界 则存在 z 蠢) 的聚点z + 满足一阶和二阶必要条件若在假设在2 + 处，的h e s s i a n 阵正定， 则 。l i m “= 1 ，l i m = 矿， i n f 知 0 而且，当七充分大时，ij 畋| | 0 为信赖域半径 记问题( 2 2 ) 的解为毗，由文献 1 】中定理6 3 1 知： 引理2 1 1 若也是子问题( 2 2 ) 的解，当且仅当存在k 0 ，使得： f i ( b 七+ 入惫j ) d 麾= 一鲰， a 七( 七一l | 以i i ) = o ， ( 2 3 ) l i i 呶临， 成立并且风+ 入七，是半正定矩阵 由此可得 一夕吾d 南= 霹( 玩+ a 七，) d 南o 而且，由( 2 3 ) 的第一个等式及矩阵风+ 久七，的半正定性知，一9 丢以= o 当且仅 当鲰= o ，即z 七是( 2 1 ) 的稳定点因此，只要z 七不是( 2 1 ) 的稳定点，则由( 2 3 ) 确定 的如是，( z ) 在z 凫处的一个下降方向 基于上述事实，我们提出如下信赖域一线搜索型算法，其中对鼠采用p s b 修正 公式 一1 0 算法2 1 1 步0 ：取初始点z o 即，对称矩阵玩形舰，常数m 口z 戚珏 0 ，取初始 信赖域半径o ( m 饥，仇口z ) ，参数j 1 ；p ，6 1 ，c 2 ，c 3 ( o ，1 ) 精 度e o ，令七= 0 ： 步1 ：若| j 鲰j i e ，则算法终止，得问题的解z 膏 步2 ：求解问题( 2 2 ) ，得以 步3 ：若 ，( z 七+ 呶) ，( z 七) 一6l i 比1 1 2 ( 2 4 ) 则令z 七+ 1 = + 也计算 a r e d ，( z 凫) 一，( z 七+ 巩) 仉2 万瓦2 雹丁袁瓦厂 若叼，则令+ 1 = m i n c 1 七，啪z ) ， 若 0 ，使得下式成立： v 2 厂( z ) 一v 2 厂( 可) l i f 三i | z 一可| l ， 比，可冗n ( c 2 ) ：函数厂( z ) 是一致凸函数，即存在常数m m o ，有： m i id | | 2 矿i iv 2 ，( z ) i id mi i d 1 1 2 ， v d ，z r n 在本文余下部分，若无特别说明，我们总假设条件( c 1 ) 和( c 2 ) 成立 2 2 2 全局收敛性 由条件( c 2 ) 知，对任何实数口r ，水平集 z l ，( z ) o ) 有界特别，由算 法2 1 1 产生的点列 z 惫) 有界 下面的引理给出了算法2 1 1 的一个好的性质 引理2 2 1 由算法2 1 1 产生的点列 z 南) 满足： l h + t z 詹1 1 2 0 ，使得 仇i iz 七十1 一z 知1 1 2 一9 吾s 知 综上可得，存在常数m + 0 ，使得，对于所有的七， z 七+ 1 一z 知| 1 2 m + ，( z 七) 一厂( z 南+ 1 ) 】 由于 0 是常数 证毕 n 2 + 1 ( o 后+ 6 七) 2 一q 叩：， 后= o ，1 ，( 2 9 ) 一1 2 硕士学位沦丈 t 有， 则条件 蕴含 同时，条件 蕴含 证明由条件( 2 9 ) 可知， 于是， 综上两式可得， o o 磋 o o ， 七= 0 熙昙雾籼 k o 。， 七= 0 壤 o o 七= 0 n 惫+ 1 o 七+ k n 0 + q 旌 q 碾( n o + k + k ) 2 七= 0 七= 0七= t l z 一1 2 ( o o + 6 j c ) 2 + 2 ( 氏) 2 七= o凫= t f 一1z 一1 = 2 ( o 。+ k ) 2 + 2 ( f 一亡) 6 ： 1 3 一 玩 七渤 p s b 信赖域一线搜索喇算法 两边同除以f ，并令? _ 得， 1 z 一1 口l i m f l o of - 七= 0 o 。 2 6 乏 凳= 因为亡是任意的正整数，结合式( 2 1 0 ) 和( 2 1 5 ) 即得( 2 1 1 ) 成立 引理2 2 3 设 z 七) 由算法2 1 1 产生，则存在无穷指标集k 使得： 1 i m & = l i m kk 七+ o o忌o o 证明令 ( v 2 厂( z 七) 一鼠) s 川 s 南 = l i m k k 知 盟毕生掣：o 1 i 如l l 一 氟- = z 1 v 2 m m s 渺， 则玑= 九+ 1 s 七由p s b 修正公式( 2 6 ) 得： b 南+ 1 一a 血+ 1 = ( ，一 两边取n o b e n i u s 范数得， 鼠s 蚕 s 七 ) ( 鼠一a 知+ ) ( j 兰堑7 i is 七1 1 2 少 i 取+ ，一a + l l l ；= l l ( ，一解) ( 鼠一4 知+ t ) ( j 一潞) l l 由条件( c 1 ) 知， 令 l i ( 鼠一a 七十1 ) ( s 七s 蚕 ：i | ( 反一a 七十。) l 瞎一j s 七 ) 幢 一a 七+ 1 ) s 1 1 2 0 吼1 1 2 = l l ( 晚一a 七+ t ) i 陪一生详 ，工 la 南+ 1 一a 南l i f i | v 2 厂( z + 亡s 七) 一v 2 ，( z 七一1 + 亡s 知一1 ) l l fd 亡 ，0 = = 删n 因此，当尼k 充分大时，总有i i 以i i o ，使得当后k 充分大时有：i | 纨i i 尬| i 毗i i 由此 及( 2 2 6 ) 得 1 i mi n f i | 鲰i i = o 上面的结果表明，存在 z 七) 的一个极限点牙使得v 厂( 牙) = o 由于厂( z ) 是一致凸 函数，因此，牙是问题( 2 1 ) 的全局唯一最小值点 另一方面，由于函数值序列l 厂( z 七) 单调递减，因而收敛于厂( 牙) 因此，序列 ) 的 每一个极限点都是问题( 2 1 ) 的最小值点由最小值点的唯一性知 z 七) 收敛于牙 证毕 一1 6 硕上学位论文 2 3 算法的超线性收敛性 本节我们证明算法2 1 1 的超线性收敛性 设z + 是问题( 2 1 ) 的唯一解由条件( c 2 ) 知，存在常数m m o ，使得 丢m i iz 一引1 2 0 ，有： 0g ( z ) 1 1 2 c ，( z ) 一，( z + ) 】 引理2 3 1 设 z 七) 由算法2 1 1 产生，则： l iz 七一矿i i 0 及指标n ，使得当尼k 且后时，q 岛a 从而，由线搜索条件( 2 5 ) 知，当后k ，且七时，有 f k 札一f 。sf k 一乱+ 6 l q k 靠d k 一厶一6 ，( m 一& ) q 七l | 以jj 2 一 一掣2 ( 1 一学叫 ( 2 3 1 ) 由上面的讨论及 ，( ) ) 的单调性，我们有 + 1 一 盯( 一 ) ， 尼k ，忌 ( 2 3 2 ) + 1 一 ( 丘一 ) ，后gk ， 或七k ，忌 一1 7 p s r 信赖域一线搜索犁算法 注意到k 中指标的数目至少有嘲个由此及引理( 2 2 2 ) ，( 2 2 3 ) 可推得， k 七、一 。冬毋| 翟一nl n l 、 矿2 一一1 ( 矗一 ) = 盯1 2 一( + 1 ) r 】7 ( 如一 ) 上式结合( 2 2 7 ) ，可推得( 2 3 0 ) 证毕 由上面的引理2 3 1 和引理2 2 2 可推得： 特别地，有： & ) 一o ，七一 类似于定理( 2 2 5 ) 的证明可得，l i ml l 如l i = o 从而算法2 1 1 还原为纯粹的线搜 索一p s b 算法而且，单位步长可以取到因而其超线性收敛性可由 4 6 】中的定理3 2 推 得 下面我们证明算法2 1 1 的超线性收敛性定理如下 定理2 3 2 若条件( c 1 ) ( c 2 ) 成立， z 南) 收敛到z + ，夕( 矿) = o ，v 2 ，( z 4 ) 正定则： 2 七) 超线性收敛到舅+ 证明：由式( 2 3 1 ) 和文献 4 6 引理3 6 得： 熙皆_ 0 ( 2 3 3 ) 于是有： 恕坚铲 甩+ o 。i js 厶l i熙坚掣拧+ o o | | s hl i + 1 i ml iv 2 ，( z ) 一v 2 ，( 。+ ) l l 甩+ o o = 0 即得： 熙坚韦争划加 七一o o | | 毗| | 此时，由文献 4 6 】定理3 2 可知： i | z 七+ d 七一z + i l = 。( 1 iz 南一z + 1 1 ) 又由式( 2 3 4 ) 和v 2 ，( 矿) 正定可知，当后充分大时，存在常数 0 ，有： 鼠比 i l 如1 1 2 ( 2 3 4 ) ( 2 3 5 ) ( 2 3 6 ) 醺 脚 硕士学位论丈 又由肌+ ( b 七+ 入屉j ) d 七= o 即得： n e 文= 三鼠以+ k i i 如j 1 2 。 由v 2 厂( z ) 的连续性和式( 2 3 4 ) 可得： a r e 以= 一鳍以一三v 2 厂( z + ) 毗+ 。( 1 | 毗1 1 2 ) = p r e 如+ 丢( 呶) t ( 鼠一v 2 ，( 矿) ) 呶+ 。( 1 i 以j j 2 ) = n e 也+ o ( 0 如1 1 2 ) 综上可得： 恕住= 瓮= 1 综合式( 2 3 5 ) 和( 2 3 8 ) 得，当七充分大时，总有： 即得 z 知) 超线性收敛到z + 2 4数值结果 s 七= z 七+ 1 一z 七。毗 ( 2 3 7 ) ( 2 3 8 ) 证毕 本节我们对本文算法2 1 1 进行数值测试，以检验算法的数值效果所有的测试 函数均来源于文献 4 7 】我们采用m a t l a b 编写程序，在1 5 0g h zc p u ，1 2 4g b 内 存的个人笔记本电脑上实现。 算法中子问题比的求解是由文献 1 】中信赖域子问题算法6 2 的精确求解得到，终 止准则为j | 鲰i | e 或i i z 詹+ 1 一z 南l | e 在测试时，算法2 1 1 中参数的选取如下： ) m a z = 2 ，m 讯= o 9 ，o = 1 ，? 7 = 要， o c 1 = 2 ，c 2 = c 3 = 0 5 ，p = 0 9 ，6 1 = 0 5 ，e = 1 0 5 然后，我们比较算法2 1 1 和文献【4 7 1 中的t m b f g s 算法的数值表现，数值结果见 表2 4 1 文献【3 7 】中的t m b f g s 算法中相同的参数与算法2 1 1 中一致 表中各列的意义如下： p r o b ：测试函数： n ：测试函数维数： i t e r ：迭代次数： 一】9 一 p s b 信赖域一线搜索制算法 t i m e ：c p ut i m e s 计算时间( 单位：秒) ： e r r o r = l i 鲰ij ：终止处，( z ) 的梯度值 我们共测试了1 5 个问题 由表2 4 1 可以看出在1 5 个测试问题中，算法2 1 1 成功的求解了1 4 个问题，而t m b f g s 算法只成功的求解了1 2 个问题；从迭代次数上比较两种算法均衡；从误差估 计上比较，算法2 1 1 略占优势但从计算时间上比较算法2 1 1 的计算结果绝大部分 都比t m b f g s 算法好 数值结果表明算法2 1 1 具有较明显的优越性 一2 0 硕十学位论丈 表2 4 1t p s b 算法与t b f g s 算法的数值结果比较 p r o bn t p s b 算法t b f g s 算法 i t e r t i m ee r r o ri t e rt i m ee r r o r r o s e2 6 88 3 0 9 b 0 l9 8 6 0 i 0 64 78 3 2 9 e 0 l5 3 6 9 b 0 6 f r o t h2 1 72 6 5 3 b 0 l1 0 0 9 b 一0 41 12 0 0 5 b 0 14 9 5 0 b 0 6 b e a l e2 4 95 7 4 7 8 0 13 2 7 6 8 0 21 51 5 9 0 e 一0 15 0 1 5 e 一0 6 b a r d 35 57 8 2 1 b 0 l3 9 4 2 b 一0 5 b i g g s 6 4 l6 7 6 7 8 0 11 。6 8 0 8 0 6 p e n l 3 0 6 49 5 7 5 b 0 l2 1 2 5 b 0 56 29 8 2 7 b 0 19 6 8 1 b 0 5 p e n 2 1 0 1 0 04 4 5 3 e + 0 02 8 7 1 b 0 32 16 4 3 5 b 0 12 9 9 4 b 0 4 v a r d i m1 02 1 8 8 9 9 b 0 11 0 5 5 b 0 6 2 1 9 1 8 6 b 0 l7 9 0 8 b 0 6 b v1 01 04 2 8 2 b 0 1 4 1 6 5 e + 0 0 5 0 013 9 2 2 b 0 12 4 3 2 b 一0 4l3 8 2 7 b 一0 12 4 3 2 b 0 4 6 0 01 5 4 0 7 b 0 11 6 9 0 b 0 415 5 8 6 e 一0 11 6 9 0 e 一0 4 l e1 091 6 4 2 e 一0 l 4 5 5 5 b 0 681 8 1 5 e 一0 18 2 5 5 e 一0 6 2 091 7 2 4 e 一0 19 7 3 5 正一0 61 02 1 3 0 e 广0 11 0 0 5 b 0 5 5 01 03 1 9 9 b 0 1 7 8 2 0 e 0 693 3 4 2 e 0 15 4 5 0 e 一0 6 1 0 01 08 0 7 7 l - 0 18 4 0 5 e 0 61 09 3 2 9 b 0 18 0 8 3 b 。0 6 2 0 0 1 02 6 4 7 e + 0 09 1 7 7 b 0 6l l4 1 0 7 e + 0 08 5 8 0 b 0 6 5 0 01 01 8 5 0 e + 0 18 6 6 3 e 0 6112 4 0 2 e + o l6 1 6 9 e 0 6 1 0 0 01 1 6 6 4 8 e + 0 17 6 9 9 e 0 61 11 0 7 8 e + 0 27 9 2 2 b 0 6 t r i d1 01 0 03 8 8 5 e + 0 0 2 9 5 5 e 一0 1 b a n d2 01 45 8 7 0 b 0 1 1 7 5 4 e + 0 2 l i n1 067 4 9 7 重0 2 2 2 3 2 b 1 568 4 8 2 b 0 23 0 7 7 e 一1 5 2 077 1 6 6 垂0 28 0 7 0 e _ 1 51 11 6 4 4 王0 14 2 7 1 b 1 5 5 01 42 1 0 7 b 0 1 7 8 9 2 e 一1 4 1 42 11 6 b 0 1 1 2 8 4 e 一0 6 1 0 01 32 2 6 8 b 0 11 8 2 7 b 一1 41 32 5 3 9 e _ 0 14 6 2 4 b 1 4 2 0 0 1 96 6 0 1 b 0 16 3 8 5 e 一1 41 99 3 1 7 b 0 17 2 3 5 b 1 4 5 0 02 9 5 4 6 4 e + 0 01 9 4 4 e 广1 3 2 7 1 1 0 8 e + 0 18 6 8 4 e 一1 4 1 0 0 03 62 5 8 0 e + 0 15 0 7 0 董一1 33 48 9 3 9 e + 0 13 2 7 9 e 一1 3 2 1 p s b 信赖域一线搜索型算法 ( 接前页) 表2 4 1t p s b 算法与t b f g s 算法的数值结果比较 p r o b n t p s b 算法t b f g s 算法 i t e rt i m e e r r o r i t e r t i m ee r r o r l i n l 1 046 4 3 2 e 一0 24 。6 0 1 e 一1146 。3 3 8 e 一0 21 9 3 6 e 1 0 2 057 4 6 7 b 0 22 9 3 1 e 1 057 6 1 9 e 一0 27 9 9 4 e 一1 0 5 062 3 4 3 b 0 19 9 4 8 e 一0 762 3 0 1 e 广0 16 7 8 8 e 一0 7 1 0 0 71 3 8 7 e 一0 12 2 7 8 e 一0 472 4 1 6 b 0 1 5 4 4 3 e 一0 5 2 0 093 8 0 1 b 0 14 5 9 9 e 0 395 1 1 1 b 0 11 5 8 6 e 一0 2 1 i n 01 045 8 0 2 e 一0 21 4 0 1 e 一1 147 8 8 1 b 0 27 7 5 9 b 11 2 056 6 9 1 b 0 21 1 9 7 e 0 957 6 3 6 e 一0 21 0 3 6 e 一0 9 5 0 68 6 7 8 b 0 29 7 6 1 b 0 769 9 9 9 e 一0 2 9 2 5 1 b 0 7 1 0 071 5 2 8 b 0 15 5 9 1 l 0 572 3 6 0 正一0 19 2 2 2 e 一0 5 2 0 094 5 3 7 e 0 11 7 0 0 e 0 21 07 7 4 4 e 0 11 5 3 1 b 0 2 3 0 0 1 09 4 6 8 b 0 11 6 9 9 b 0 1 1 01 4 1 0 e + 0 06 7 3 0 e 一0 2 5 0 01 23 4 5 4 e + 0 09 0 5 5 e o l1 37 6 8 2 e + o o6 2 7 6 e 一0 2 2 2 硕士学位论文 2 5p s b 信赖域一非单调线搜索型算法 本节我们将非单调线搜索技术引入上节提出的p s b 线搜索型信赖域算法中， 提出一种非单调p s b 信赖j 彝线搜索型算法 2 5 1 非单调线搜索背景 大量数值结果表明，非单调搜索比单调搜索数值表现要好得多，特别是非单调 方法能求些比较困难的问题非单调方法不要求，( z 知+ 1 ) ，( z 七) 最早提出非单 调线性搜索技术的是g r i p p o ，l a m p a r i e l l o 和l u c i d i 于1 9 8 6 年在文献 3 9 】中考虑了如 下一般格式的非单调线性搜索方式： 取一正整数m ，取步长q 七= 所帆，其中m 七是满足下式的最小非负整数： m 七+ 卢旷以) 。器的 一j ) + p 所m v m 七) 7 d 南， p ( 0 ) 1 ) ，( 2 3 9 ) 其中， m ( o ) = o ，o m ( 忌) m i n m ( 后一1 ) + 1 ，m ) 后来，他们在n e 毗o n 法中应用此非单调线搜索技术f 4 8 j ，在假设水平集有界q o 圭 z l ，( z ) ，( z o ) ) ，充分下降条件鲧畋c ，l l 鲰1 1 2 及l | 九l lsc 2 1 1 鲰l l 成立的条件下有下 列结论： 1 算法产生的序列 孤) 包含于q o ，并且每一个极限点牙都满足：v ，( 牙) = o 2 算法产生的序列 z 七) 的任何极限点都不会是函数，的局部最大点 3 若函数，在q o 内稳定点有限，则序列 z 七) 收敛 4 若整数f ( 后) 满足： 七一m ( 后) ，朋( 七) ) 2o 蹋蜘 一j ) ， 则序列 ，( 2 ( 后) ) ) 是非增的 注：与单调a r m i j o 型线性搜索相比较，非单调线性搜索条件( 2 3 9 ) 可以产生一 个相对较大的迭代步长而且，采用非单调线性搜索( 2 3 9 ) 的n e w t o n 法的收敛性与 采用单调a r m i j o 步长搜索准则的收敛性类似d a i ( 2 0 0 2 ) 在文献 4 9 也证明了在牛顿 法中，对于强凸函数和确定的常数m ，当七充分大时，序列 z 七) 具有尼线性收敛速度 但是，上面的非单调线性搜索也存在一些缺陷： 1 。当搽凫) 一j ) 可能丢弃了一些好点 2 r a y d a n ( 1 9 9 7 ) 和t o i n t ( 1 9 9 6 ) 指出：一些实例的数值实现取决于m 的选择 3 d a i ( 2 0 0 2 ) 指出：尽管它对于一些迭代方法使得强凸函数具有辟超线性收敛 速度，但当后充分大和m 固定时，一些迭代法产生的点列可能不满足式( 2 3 9 ) 一2 3 p s b 信赖域线搜索型算法 例如： 1 ，( z ) = 去z 2 ， z 冗，z o o ，d 七= 一z 忌， 厶 ， i1 2 一， = 2 ，t v ， i 2 ， d 九e r 叫t z e ， 迭代产生的点列 z 七) r 一超线性收敛于矿= o ，但当后充分大和m 固定时，上述 迭代产生的点列 z 向) 却不满足式( 2 3 9 ) 为此，在( 2 3 9 ) 的基础上z h a n g 和h a g e r ( 2 0 0 4 ) 在文献 5 0