（应用数学专业论文）带线搜索的非单调信赖域算法.pdf

硕士论文 带线搜索的非单调信赖域算法 摘要 现在广泛用来求解优化问题的方法大多数是单调的方法，当目标函数在可行域中存 在细长弯曲的峡谷的情形时单调性算法就会大大丧失它的计算效率。由此非单调算法引 起了学者们的重视，产生了许多有效的非单调的算法，特别是非单调线搜索与信赖域法 相结合表现了突出的计算效果。 本文将非单调线搜索与非单调信赖域法相结合，信赖域法中每一步都实施线搜索， 使得迭代每一步都充分下降，加快了迭代速度。对于无约束优化问题的传统非单调信赖 域算法，子问题的求解是信赖域法的关键，也是信赖域法计算量的主要部分，如果试探 步瓯不可接受，令五+ = 黾，减小信赖域半径，重新求解子问题。这样就有可能多次求 解子问题才能得到可接受的新的试探步盈，如果问题的规模比较大时，多次重新求解 子问题加大了计算量，而线搜索确定一个新试验点黾“只要求非常小的计算量。因此将 线搜索与信赖域相结合，可减少子问题求解次数，从而减小信赖域法的计算量。引入线 搜索要求子问题的解必须是下降方向，即g ：反 名，乃= m a x o ，一a ( 最) ， a ( 反) 表示反的最负特征值。 1 0 、3 0 的情况问题的求解都不存在任何困难，困难主要在于2 0 这种情况，因此2 0 被 成为困难情形“t h eh a r dc a s e ，m o r es o r e n s e n l 9 8 3 1 3 给出了这种情况下近似求解的一 2 硕士论文 带线搜索的非单调信赖域算法 种方法，但是由于盈的计算需要相当的工作量，我们一般尽量避免这种情况下的求解。 1 3 子问题的近似解解法 虽然原则上是要求解子问题( 1 i 2 ) ( 1 i 3 ) 的最优解，但实际中只要找到使模 型达到充分下降量的点，即使算法达到全局收敛的点即可。基于这一点，p o w e l l 4 】 5 】 给出了柯西点的计算方法，这也是所有近似解法的基础。柯西点的取法如下： 露= 町翮a k ( 1 3 - 1 ) 弘 曲t 血 i l 哦五反v s o m ：矿舒如 a a 2 易知柯西点的下降量为： c k ( 0 ) - 九( p d t o 一寺露r 壤寺赴0 0 ( 1 3 3 ) 由此p o 、e l l ( 1 9 7 5 ) 1 7 1 证明，如果精确求解( 1 1 2 ) - ( 1 1 3 ) ，子问题的解一定满足“模 型充分下降条件”，这是解瓯的一个根本性质，它在信赖域全局收敛性的证明中起着关 键作用，即：若瓯为子问题的解，则必满足 们h ( 驴恻i i 曲a ，) 其中刚 n o c e d a l 和y 啪( 1 9 9 8 ) 【1 6 】证明了子问题近似解盈满足“模型充分下降条件的同 时又给出了解的一个“充分下降条件即下引理1 3 2 。 引理1 3 1 设况为( 1 1 2 ) ( 1 1 3 ) 的解，则必有 们h ( 啦扣i i m i i l k 粉 ( 1 3 4 ) 引理1 3 2 设盈为( 1 1 2 ) ( 1 1 3 ) 的解，则必有【见【1 6 】引理2 4 】 忙扣i l m m 糌 ( 1 3 5 ) 这说明子问题的解总是保证和负梯度的方向的夹角不接近9 0 度。通过引理1 3 2 ， 我们知道子问题的一个“好 解，应该靠近负梯度方向以保证方向的充分下降性。最重 要的是应该满足使模型有充分的下降量，这样才能使算法收敛。近似解求法就是从“模 型充分下降条件出发来求解的，着重介绍一下折线法。 折线法分为有界折线，无界折线法，都是通过构造近似最优曲线 4 5 【6 】【7 】，沿近 l 信赖域法的研究硕士论文 似最优曲线确定解瓯，避免了s o r s e n l 9 8 3 1 3 】中的困难情形( “t h eh a r dc a s e ”) 时的求解。 折线法区别直接求解线性系统的方法在于缩小了求解空间，无需求解线性方程组。让。 在子问题内变化，解点形成一个曲线，色作为一个全维空间内的参数，这个曲线称为 最优曲线，记作, t - - o p ，那么子问题( 1 1 2 ) 一( 1 i 3 ) 等价于在最优曲线r 磐上找一个点 使得二次函数吮( 万) 取极小值，即： 哦= r a i n ( d , ( 8 ) = g k r 8 + 去万7 最万，万r 寥，8 万0 i ) ( 1 3 6 ) 由于最优曲线的确定需要计算矩阵最的所有特征值和特征向量，相当费时，因此专家 们考虑在低维空间内构造满足一定要求的折线，记为i q ) ，来近似最优曲线i 蜜，通过 求解下列问题： 曲吮( 万) 2 或万+ 尹最万( 1 3 7 ) s ，r 万r o ，0 艿8 a 七 得子问题( 1 1 2 ) - ( 1 1 3 ) 的近似解瓯。求解问题( 1 3 7 ) 的一个突出特点在于，近 似折线r ( 。) 一经确定，对于给定色以及必要时减少的色的值，无需再解任何线性方程 组，即能相当有效地确定问题( 1 1 2 ) - ( 1 1 3 ) 的近似解。在构造近似最优曲线r 兽的 折线时，一般应满足下述基本要求：当点x 从点黾出发沿折线前进时，( p 1 ) 点x 到点矗 的距离忙一9 = 例l 单调增。( p 2 ) 函数值吮( 艿) 严格单调降。性质p 1 确保对任意给定的 。的值，折线上的近似解唯一，性质p 2 确保在折线上所确定的近似解盈能满足“模型 充分下降条件 。 下面总结一下主要的几种折线路径。 1 0 p o w e l l 【5 】单折线r 譬= k ，露，x n ( p k 】 ( 1 3 8 ) 其中= 矗+ 睇，影= 以+ 磷，嚣= 一展反，磷= 一巧1 f ，r o 展= 警 g k d k g k 2 0d a n n i s 和m e i 6 】的双折线路径哟= k ，葛，磋，礴) 】( 1 3 9 ) 其中虿2 故一砩，盘万虮 1 0 、2 0 解决的是当矩阵反正定时的情况，均为有界折线且满足性质( p 1 ) ( p 2 ) 6 】【7 】。 当b 不正定时，用1 0 、2 0 的方法无法构造近似最优曲线的折线。z h a n g 和x u n l 9 9 4 1 7 】 研究了当反不正定时可以利用实对称矩阵的本齐- 伯利特( b u n c h ，k a t f f m a n , d a r l e t t ，1 9 7 6 【1 8 】) 分解，来构造负曲率方向d ，沿d 构造无界折线来近似最优曲线。 一个实对称矩阵反一般具有唯一的l d l r 分解，其中l 为单位下三角矩阵，d 为对 硕士论文带线搜索的非单调信赖域算法 角矩阵。当反正定时，这样的分解是稳定的，而当反不正定时，这样的分解不一定存 在，即使存在，这样的分解往往是不稳定的。而本奇伯利特分解是一种稳定的分解方 法，它把实对阵矩阵屏分解成 p b k 矿= l d l r ( 1 3 1 0 ) 其中p 为置换阵，三为单位下三角阵，d 为一块对角阵，对角块的阶数是1 或2 。如果 晟是正定的，则d 为对角元素全为正的对角阵，如果d 具有2 阶的对角块，则最具有 负特征值。事实上，分解式( 1 3 1 0 ) 具有下列有用的性质【7 】( z h a n g , x u n1 9 9 4 ) ( i )矩阵d 和毋有相同的惯性，即它们具有相同数目的正特征值，零特征值和负 特征值。 m )矩阵l 和f 1 有界，即存在正数q ，岛，c ，q ，使得 c l 肛8 5 乞，c 3 8 f 1 0 q ( 1 3 1 1 ) ( 1 1 1 )如果盈不定，设 和4 分别为矩阵反和d 的最负特征值，则成立关系 圳1 2 五1 1 2 3 1 2 ) 在矩阵最不定时，可以从矩阵d 的相应于负特征值的特征向量确定矩阵最的负曲率方 向d 。设萌畋以是d 的特征值，u 1 , 2 ，矿是相应的正交特征向量。令 n 一= - i l z 0 ) ，负曲率方向为 d = a - s 烈r 。) f ，。s ：枷。：以v t r ( 1 3 1 3 ) 因为d r 最d = 矿d o = 4 ( 0 2 - 0 。事实上，如果 d c = d i u = 彤甜 c s ，当乃= 7 仲f 甜，7 忙) - f = 7 , u ，则 g r b k g = - s g n ( g v r d ) 爵三d d = 一s 烈爵f r v ) d r 反d ( 1 3 14 ) d c 的一个比较好的选者是： d = 托矿 ( 1 3 1 5 1 31 5 ) d = 乃“ () 对于这个特殊的向量p ，有 堋黔啦州砰且槲蝰- i | 川撬 3 舶， 由( 1 3 1 2 ) 的前半部分和性质( t o ，可以得到方向d 的一个性质： 5 l 信赖域法的研究 硕士论文 d r b k d 南： ( 1 3 1 7 ) 根据上述叙述可以看出，采用本奇伯利特分解有下列几个特性：( 1 ) 、分解稳定。( 2 ) 、 可以根据分解式判别矩阵反是否正定。( 3 ) 、如果吃正定，l d l r 可用于求解方程组 最万= 一得磷。( 4 ) 、如果嘎不正定，即可由( 1 3 1 3 ) 式确定负曲率方向d 。 由本奇伯利特分解确定的负曲率方向d ，z h a n g 和x u n1 9 9 4 年构造了几种无界折 线来近似最优曲线，见文献【7 】，并证明了构造的折线满足性质( p 1 ) 、( p 2 ) 且沿折线确定 的近似解反满足全局收敛的“模型充分下降条件”。另外，w a n gc h e n g j i n g2 0 0 6 1 9 年 证明了l o 、2 0 和z h a n g 和x u n l 9 9 4 年构造的折线确定的近似解瓯还满足“充分下降条 件 ： 酊皖如i i s 陋 a k 鳓i i g t t l ) ( 1 3 1 8 ) 这是近似解的一个非常重要的性质，这样求得的解可以安全实施线搜索，w a n g2 0 0 6 年 1 9 】文将这种求解子问题的方法应用到信赖域法中，并让信赖域法与线搜索相结合得出 了一种十分有效的信赖域算法，w a n 9 2 0 0 6 1 9 的算法思想是本文的出发点，本文也将在 下文证明一些子问题求解方法同样满足“充分下降条件”，因此当信赖域与线搜索相结 合时子问题求得的解可以安全实施线搜索。 z h a n g 和x u n l 9 9 9 1 2 0 年又提出了另外几种折线路径，给出了r 的四种选取方法， 详见构造方法如下： ( a ) 弼壤繇卜若i - r v 0 且急 - 1 是使式子右边大 于左边的常数。易知对于这样的名，反+ 4 1 正定且 1 1 8 , + 2 i l l ： - 醋r 诺 - 0 骘眶 ( 1 3 2 4 ) 哗= k ，葛，蛰】 ( 1 3 2 5 ) ( c ) ( i ) 当g ；色卜。时，若0 磷i la 。或刮l 甜贬诺r 睇- - - 0 ，r 一r ? 上得到 的近似解瓯满足： 删c 驴瓣搬蚓酬：曲卜群) 3 瑚， 事实上，折线r 一r ? 上找到的近似解瓯同样也满足“充分下降条件 ，下面我们 给出证明。 引理1 3 4 若引理1 3 3 假设条件满足，瓯是r 窘一r ? 上找到的近似解，则存在f - o 使 得： 瓯刮训幽卜丽i i g , r 1 ( 1 3 力， 证明：( 1 ) 若解驻曙上，榔) ，贝峨- 南 靠瓯= - - 瓯a k ，g g , - - - , 1 1 0 若锑 - o 7 俐网 g ： 6 k = 一( 1 一_ ) 反+ - g ；d 一万( 1 一以j 乳t = 一q 一2 ) ( g g r b g k k g ) 2 ： 纠向，惭 故有铲训训幽卜黜 g r d o f = m a x 1 ，1 一- ( 2 ) 假设解瓯在r 上，若睇趣，则 瓯2 南掣 若弦卜。矽0 ， 盈= - a 。慨0 则反：锤) + 页( 磷，一锑，) ，万满足蚓i ：赴且万 o 瓯= ( 1 一- ) 锩+ 碡嚣 = 一( 1 一- ) 砝一碹徊+ 力圹1 9 k - ( 1 - 见) ( g ：) 2 吱b k g k一万龋 纠m ，龋一万龋 二晶 因磷) _ - ( 反埘1 ，俐i = i i ( 川盯1 9 , l l 阱1 1 踹恼| l ，小) 是矩阵 的条件数。 奄最6 。 8 - - i h l 鼎 c o ，忙+ 允州坞可知 r 哆= 阻研陋2 1 ) 一1 | i - o 使得慨0 = 七 瓯= ( + 从) = 繇t t + 碗d 一( b + 五d - 1 9 一 l b + 2 1 1 l一罟l l g , l l a 七m 故有矗瓯圳酬幽卜丽l l g , i i )f = 一忙爿 假设盈在r ? 上，若0 碟a 七，则瓯= 磷，瓦 - o 使得0 疋0 = 。 _ 一_ ， g ：6 k = 一；l g ：哆+ ；l 玎1g t s - - 竺mu 若0 磷，则壤= 磊+ - ( 一) ，万 - o 使得0 皖i i = 。成立。 g a = 爵( 黪一砘) 9 谒 1 信赖域法的研究 硕士论文 = 酿6 紫一j l 吱g k s g ；( b + 允，) 一1 9 k - 0 则转s t e p 2 。 否则计算f 卜。使得0 p 。托0 = i ，令万= b + 碣，停止。 ( 1 4 4 ) s t e p 2 计算q = 譬，只+ l = 只+ 墨，如果8 a + l8 - o 使得i l 研+ q l i 一，令万= 仍+ 碣，停止。 ( 1 4 5 ) s t 印3 计算r m = r ，- a , 盈墨，如果删磊，令= 只+ 哪停止o ( 1 4 6 ) 否则，计算屈= 互乒，t + l = 墨+ 屈，令f = i + 1 ，转s t e p l 。 设 乃 ( _ = o ，1 ，力是算法产生的迭代点，万是最终迭代方向a 则有： h 1 ，删地l | | 氇，错矧脚3 ) i p j + ， 肌0 万= p j + f 岛，仇 - o 且l i 易+ 10 女( s t e p 2 ) ( 1 4 7 ) k + q ， 当场 - - l l p , i l 。 ( i i )二次函数苁( 万) 的值沿路径单调减，即：吮( 万) 九( b ) - o ，但l l p , + ，l l 七，则万= a + 碣，用上述证明方法有兰矿最万 - o 故有 爵暖一釉i 曲卜觋l l g t l l c 舔e 2 若仇o ，贝0 万= a + q 九( 艿) = g r 艿+ 三艿丁b 6 = g r p i + r g r s j + 1 b p 一菇b s i + b s i = 争( 、p ) + z 誊s t + 1 史b s i 姒小地净扣i 吵卜粉 函为g r s i - - a l ，且哌。，氏为子问题当a t = l ，a i = a 2 时对应的解，则有： c o s ( ) c o s ( ) ( 2 ) 、方向反过分大，这时信赖域法通过减小半径得到新试探步的方向相对于前一 个方向几乎没改变。这种情况下，信赖域法类似于线搜索法，只是计算量较大。 由于线搜索要求搜索方向必须是下降方向，即瓯 0 ，对于情况( 2 ) ，如果实施线 搜索会非常有效。但如果( 1 ) 发生时，线搜索就无法实施。因此，瓯被拒绝，沿皖实施 线搜索不总是成功的。由此，y u a n1 9 9 8 年提出了一种新的求子问题的方法，得到的近 似解瓯保证了酊瓯 - o ，0 乃 托 1 乃， 0 r h _ 0 ，k = 0 。 s t e p l 计算，如果满足终止条件，则终止；否则，转s t e p 2 。 s t e p 2 求子问题得近似解反，0 疋忙且满足 m 制i i 陋卜厕i i g , i i ) 酲壤酬训幽卜厕i l g k l l 其中p r e 3 , = 九( o ) 一九( 瓯) = 一疋一去霹最壤 s t e p 3 计算厂o + 万) ，若厂( 黾+ 艿) 厂( 妖)转s t e p 4 否则，用简单 后退准则找到雄使得： ( & + 毋) - - 0 ，0 乃_ 乃 1 乃， o 仇 r h 1 0 ，k - 0 。 s t e p l计算，如果满足终止条件，则终止；否则，转s t e p 2 。 求解子问题得近似解瓯，8 皖| i 赴。 令石( ”2 。句l l l 蜘a x ( 的a - j ，0 r e ( k ) - 矾令“= x t + 五转s t e p 5 ；否则，令墨+ l = ，