（应用数学专业论文）自适应非单调信赖域法.pdf

摘要自适应非单调信赖域法 摘要 信赖域法具有很强的全局收敛性，其收敛性的证明不要求对函数作较强的假设， 不要求初始点靠近最优点，也不要求海森矩阵保持正定，因而备受优化领域专家的关 注。虽然信赖域法具有全局收敛性，但是收敛速度并不一定快，尤其是在一个很窄的 弯谷时，会产生锯齿现象。 对于无约束优化问题的信赖域算法，其关键是子问题中二次模型的逼近精度即可 接受比率和信赖域半径大小的选择。本文采用张洪超等提出的带凸组合的非单调技巧 调节信赖域法中的可接受比率，可以避免锯齿现象的产生。对于信赖域半径进行如下 修改：用非负整数p 自动调节信赖域半径，其中信赖域半径瓯：c p 怯。i l ，。之所以选 用这个模型是因为：在所有的自适应信赖域法中都是用常数c ，梯度信息和目标函数 的二次信息来构造信赖域半径。但是在目标函数的二次信息中也含有梯度信息，并且 在数值试验中发现常数c 并不敏感，因此可以只用梯度信息调节信赖域半径。 又因为初始信赖域半径也会影响算法的效率，并且初始信赖域半径的选择无章可 循，这也是本文考虑用自适应法的原因，这样既可以消除初始半径对算法的影响又可 以自动调节信赖域半径。 第一章主要介绍了传统信赖域法的背景知识，非单调技巧的发展现状，自适应法 的发展现状以及子问题的求解；第二章给出了具体的算法，并证明了算法的全局收敛 性和局部二次收敛性。第三章为数值验证，数值结果表明算法有效。 关键词：信赖域法，非单调，自适应，收敛性 a b s t r a c t自适应非单调信赖域法 a b s t r a c t t h et r u s tr e g i o nm e t h o dh a sas t r o n gc o n v e r g e n c e a n dt h ei n i t i a lp o i n td o e sn o tn e e d s e a l t h eo p t i m i z e dp o i n ti nt h ep r o v eo ft h ec o n v e r g e n c ea n dn on e e dm u c hm o r es u p p o s e ! 。 o ft h ef u n c t i o n ，a l s on on e e dt h eh e s s e nm a t r i xp o s i t i v ed e f i n e d s om a n yp e o p l ea r e s t u d d i n gi nt h i sf i e l d t h ek e yo ft h et r u s tr e g i o nm e t h o df o ru n c o n s t r a i n e do p t i m i z a t i o ni s t h ea c c e p t a b l el e v e lo fa g r e e m e n ta n dt h et r u s tr e g i o nr a d i u s an e wn o n m o n o t o n el i n e s e a r c ha l g o r i t h mp r o p o s e db yh o n g c h a oz h a n gi su s e di nt h i sa r t i c l ef o ra d j u s tt h e a c c e p t a b l el e v e lo fa g r e e m e n tb e t w e e nt h eq u a d r a t i cm o d e la n dt h eo b j e c t i v ef u n c t i o n a f t e rt h a t ，w ea d j u s tt h et r u s tr e g i o nr a d i u sb yan o n n e g a t i v ei n t e g e rpa n dt h er a d i u si s 0 c k = c pi i g 女1 1 7 ，b e c a u s ea l lt h ea d a p t i v et r u s tr e g i o nr a d i u si sa d j u s tb yc o n s t a n tc ，g r a d i e n t a n dt w ot i m e sd i f f e r e n t i a l 砌o r m a t i o n b mn u m e r i c a lr e s u l t ss h o wt h a tci si n s e n s i t i v e a n dg r a d i e n ti n c l u d ei nt w ot i m e s d i f f e r e n t i a li n f o r m a t i o n s ow ec a na d j u s tt h er a d i u so n l yb yg r a d i e n ti n f o r m a t i o n f o rt h e t r u s tr e g i o nm e t h o d s ，t h ec h o i c eo ft h ei n i t i a lr a d i u si sv e r yi m p o r t a n t ，s i n c ei ta f f e c t st h e n m n i n ge f f i c i e n c yo ft h em e t h o d s i nt r a d i t i o n a lm e t h o d si ti sn og e n e r a lr u l ef o rt h ec h o i c e o ft h ei n i t i a lt r u s tr e g i o nr a d i u s s oi ti sb e s tt ou s ea d a p t i v em e t h o d i ns e c t i o ni ，w ed e s c r i b et h ed e v e l o p m e n to fu s u a lt r u s tr e g i o nm e t h o d ，s o l u t i o no ft h e s u b p r o b l e m ，t h en o n m o n o t o n el i n es e a r c ha n dt h ea d a p t i v et r u s tr e g i o nm e t h o d i ns e c t i o n i i ，w ep r o p o s e dt h ea l g o r i t h ma n dp r o v e dt h eg l o b a lc o n v e r g e n c ea n dt h el o c a lq u a d r a t i c c o n v e r g e n c e ；i ns e c t i o ni l l ，n u m e r i c a lr e s u l t ss h o w t h a tt h ea l g o r i t h mi se f f i c i e n c y k e y w o r d s ：t r u s tr e g i o nm e t h o d ，n o n m o n o t o n e ，a d a p t i v e ，c o n v e r g e n c e n 声明严明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 ? t 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名： 学位论文使用授权声明 日 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：刁萨宕年- 7 月日 硕士学位论文自适应非单调信赖域法 1 绪论 1 1 关于信赖域法 1 1 1 信赖域法的研究背景 信赖域方法是相对于线性搜索方法的另一类求解非线性优化问题的著名方法。它 因为具有十分出色的理论基础，很好的可靠性和强壮的收敛性而备受优化领域的专家 们的关注。大致来说，信赖域方法是围绕当前迭代点定义一个区域，使二次模型在此 区域内能充分代替目标函数，之后求解二次模型在此区域内的近似最小值作为新迭代 点，即同时产生了方向和步长。如果这个步长不可接受，则减小信赖域半径并重新计 算新的迭代点。当信赖域大小改变时迭代方向也是改变的。 一般而言，线性搜索先确定方向再求步长，信赖域先确定步长再求方向。信赖域 大小选择是影响每一步迭代效率的关键。如果这个区域太小，则算法就可能错过了求 解使函数下降量最大的点的机会，会使迭代速度缓慢；相反如果区域太大，则二次模 型的最小值点将和目标函数最小值点相差甚远，因而不得不减少区域并重新计算。在 实际计算中，我们通过前一迭代点的表现情况来决定当前区域的大小。如果模型精确 的逼近了目标函数，并产生较好迭代点，则信赖域大小将稳步增大；否则一个不可接 受迭代点表明模型在此区域内已不能充分代表目标函数，则需减小信赖域半径。信赖 域方法也是一个迭代求解的优化算法。首先给出其模型函数： 一 1 一 “ m ，i 。nl ( d ) = 繇1 d + d 1 最d ( 1 ) qtn 二 s d a 七 这里为无约束优化问题r d m f ( x ) 的最优解x 的一个当前估计，d = x 一， g k = v 厂( 以) ，盈或者为f ( x ) 的海森矩阵v 2 厂( 黾) ，或者为v 2 f ( x t ) 的一个近似，参 数色称为信赖域半径，它的大小取决于二次模型唬( d ) 在当前迭代点的以a j i 为半径 的邻域内对f ( x ) 的拟合程度。为避免对。的过分限制，在确保么( 刀) 很好的拟合 厂( x ) 的条件下应选取尽可能大的七。设反为问题( 1 ) 的解，则么( d ) 在的l 邻域 内对厂( x ) 的拟合程度可以通过比较厂( x ) 在点吒+ 反所得的实际下降量a r e d ( d k ) 和由拟合模型唬( d ) 确定的估计下降量p r e d ( d i ) 来确定，这里 a r e d ( d k ) = f ( x d - f ( x k + 反) p r e d ( d k ) = 一么( 反) 。 舍n ：f ( x k ) - - f ( x k + d k ) 私( 畋) l 绪论 硕士学位论文 如果反的值接近1 ，表明6 ( a ) 在杖的赴邻域内对f ( x ) 的拟合程度好，。可以 保持不变或增大，如果反的值接近o 或取负值，表明苁( d ) 在x k 的趣邻域内对f ( x ) 的 拟合程度不够理想，因此必须减小趣，缩小邻域，以改善吮( d ) 在新邻域内对f ( x ) 的 拟合程度。 基于上述分析，下面给出传统信赖域方法见【3 6 】，算法( 1 1 ) ：、 s t e p l 初始化：给定初始点而，初始值a 。，j ( 0 ，1 ) ，置k = - i 。 s t e p 2 收敛性检测：计算g k ，若0 既0 岛，f 1 则信赖域子问题为： 赌i c a ) 。g k h d l 2d r 最d s t 4 d = 0 ，f e 刃( x k + d ) 6 l ，f 1( 幸幸) 8 叱s 趣 不难看出上式是一个二次规划，可以用二次规划的方法求解。 下面给出线性约束问题的信赖域算法： s t e p l 给出初始可行点五，给出马r 脚，l 0 ，s 0 ，k = l 。 s t e p 2 求解子问题( 料) 得出反；如果例l o 占则停；否则计算 a e d ( d k ) p r e d ( d k ) 2 掣箍产 如果见 0 ，令吒+ l = 黾+ 吨，否则x k + l = 黾； s t e p 3 由p k 修正信赖域半径趣。 该方法实际上是可行点法与信赖域法的结合。对于有约束问题的子问题的求解可以将 二次规划子问题和信赖域技巧结合起来，以及用零空间法，p o w e l l - y u a n 方法等，详 见 3 6 。 1 1 2 信赖域法的研究现状 1 )刻度矩阵 当目标函数的刻度很差，即目标函数对自变量的微小变化会有较大的波动时。从 几何上看，最优点x 周围的等高线图使其位于一狭窄的扁行区域中心，x 附近呈现 为超不规则椭圆形。而信赖域的定义是以第k 步点以为中心的一圆形区域，故对目 标函数的近似程度在短轴方向，即目标函数的变化最敏锐方向严重失真。而补救方法 就是在这些方向上缩小信赖域大小，并在变化缓慢的方向增加信赖域半径。因而考虑 下述信赖域 i i o d l l - a 其中d 为正定对角矩阵，对角元素在目标函数敏锐方向较大，缓慢方向较小从而达到 1 绪论 硕士学位论文 信赖区域有效控制。相应的子问题便是 卿q ( d ) = 叨d + 圭d 丁毋d ， 趣 d 的构造信息可以通过计算二阶导数a 2 f & ? 得到。d 随迭代的每一步进行更 新，并限定其对角元在预先指定的区域【研，a h 】内变化，其中o q a h o o 。因为d 只需大致反映出目标函数的曲折信息即可，故不必非常精确。 将这一方法应用于前述的所有方法中便可得出了具有刻度矩阵的相应信赖域方 法。 2 )非欧范数信赖域 应用除欧式范数的其他范数来定义信赖域，如 i l a l i 。 和 i i d u 。 特别当应用无穷范数时，可行域变成为 黾+ d 0 ，d - a i e ， e = ( 1 , 1 ，1 ) 丁，子问题的求解便可应用标准的二次规划方法。 3 )结合线性搜索策略 为了提高信赖域算法的收敛速度，1 9 8 2 年，t o m 最先提出了在信赖域方法中加 入线性搜索的想法，他的方法是当步长不可接受时，取x m 代替以，其中 f ( x k + - ) f ( x 。) ，但没有给出有关下降量的具体条件，也不影响算法的收敛性。1 9 9 8 年n o c e d a l 和y u a n 提出了在信赖域子问题的解不可接受的情况时，即当 f ( x k + 畋) f ( x k ) 时，在或方向应用后退方法进行线性搜索得到x m ，使 f ( x ) f ( x i ) 。下面给出n o c e d a l 和y u a n 的算法。，。 通常指定常数0 7 l y 2 l ) ，3 ，当信赖域半径色需要减少时取 a m 0 是为防 止信赖域半径任意的减小，但在收敛性证明中乃并不起作用。 推广的信赖域算法 取常数尼眦，0 7 7 l 刁2 l 和0s 乃 儿 1 儿。 七= l ，攻= a o ，效= x o ； 当k k 且不收敛 令巩表示子问题( 1 ) 的近似解。 凸：f ( x k + d k ) - - f ( x k ) “ 苁( 反) 如果p k r 1 ，+ l = 黾+ 反； 否则，应用简单准则的后退算法解得磁“，满足0 黾+ 。- x , l l 0 为常数。如果方法不终止于某一点稚，则方法所形成 的序列 x k ) 至少有一个极限点x ，使g ( x ) = 0 。 下述引理给出了子问题( 1 ) 的解的特性【3 7 】。 引理2 设畋为问题( 1 ) 的解，如果矩阵反正定，且l l 何1 9 k 0 ，如m l l a ( o ) l l - 0 由方程( 1 2 ) 唯一确定。 ( i i )b k 不定，以0 ，_ rv 。0 。这时必有 一以，因而由( 1 1 ) 式有忖0 ) 0 = 女， 因此反也由d ) 确定，其中 以由方程( 1 2 ) 唯一确定。 ( i ) 最不定，且对所有的i ，= f 丑= ) 有= 0 。令 孑= 一了兰- = 。，则反由d ( ) 确定，其中 一丸由方程( 1 2 ) 唯一确定；如果0 司卜七， 则以取 哝= 孑+ 肛q ( 1 5 ) 其中以，f ，的值由方程归以) 0 = 趣确定。 上面分析表明除去以 o ，i d ( o ) l l a t 和毛o ，对所有的f 门芎v f = o 且矧l 肼确定，其中 朋= m a x 一九，o ) 对于五 o ，1 1 4 0 ) 1 1 - 0 ，其中m = m a x - 以，0 ) 。 函数伊) 在区间魄，4 - o o ) 内是连续、单调下降的凸函数，且当专佃时， 缈( ) - + - a i ，由于伊 ) 的凸性，可以用牛顿法来产生一个迭代序列伽，) ，使得，收 敛于方程( 1 9 ) 的解。但是由于对所有的 h 有矽0 ) 0 ，由牛顿 7 l 绪论 硕士学位论文 法产生的序列均为方程( 1 9 ) 的解+ 的过低估计。由于每次迭代要求解一个相应的 线性方程组，因此需要有效的求解方法以减少迭代次数。h e b d e n 3 1 在1 9 7 3 年利用 问题的特殊结构构造了一个比较有效的迭代方法。 算法( 1 2 ) ( i )如果忍正定，计算吨= 一巧1 9 k 。如果0 磊i 【赴，取吨= d o 。 ( i i )给定参数p ( 0 ，1 ) ，初始值“ 以及，置= 1 。 ( i i i ) 如果一诺( ，“，) ，, u j = m a x o 0 0 1 u j ，( “) 2 ，求解方程组( 盈+ 竹j 矽= 一繇，得 d ( ，) ，并计算缈( ，) 。 ( i v ) 如果i 妒( 一) l ，取畋= d ( 一) 。 )如果妒( ，) “时，h e b d e n 算法产生的序列讧0 二次收敛 于。数值计算表明当a = 0 1 时，平均二次迭代即可求得满足( ) 要求的近似解。 另一个求解子问题( 1 ) 的可供选择的方法叫做折线法。如果令信赖域的半径色在 区间【0 ，佃) 内连续变化，则子问题的解d o ) 在空间r ”中形成一条光滑的连续曲线， 称为最优曲线，即为碟，这时子问题( 1 ) 等价于在信赖域内在最优曲线礞上确定一 点使二次函数九( d ) 取极小值。即等价于求下列问题的解： m i n 九( d ) ， s t d 惑，i l a l l - 。 由于最优曲线的确定需要计算矩阵最的所有特征值和特征向量，相当费时，折线法 在于用低纬空间内满足一定要求的折线，记为，( ，代替最优曲线。通过求解下列问 题 m i n 吮( d ) ， s t d e 7 让，i l a l l - o 一1+ 秽，否贝0 ， 其中稚= 一( 最+ i ) 一g f ，盈+ i 正定。 下面给出折线法的算法( 1 3 ) ( 1 ) 矩阵分解，最= l d l t 并计算矩阵d 的特征值和特征向量。 ( 2 ) 如果d 正定，解方程组l y = 一，l z d = - d y ，得础。如果或= 础，转 ( 4 ) 。 ( 3 ) 如果d 不定，计算负曲率方向反，后形成折线7 ( t ) = 膨。 ( 4 ) 确定二次方程耖( t ) 旷= ：的解t ，并置破= 7 ( t ) 。 ( 5 ) 如果而+ 噍是可接受的，磁卅= 五+ 吼；否则减小信赖域半径k 转( 4 ) 。 1 9 8 3 年s t e i h a u g 2 7 提出了用预条件共轭梯度法求解子问题。考虑与子问题相应 的线性方程组 最d = 一 ( 2 0 ) 当矩阵毋正定时运算精确的共轭梯度法至多经过n 次迭代可求得( 2 0 ) 的解 b 一。而预条件共轭梯度法首先通过引入预条件矩阵以改善系数矩阵毋的条件数， 达到改善共轭梯度法收敛性的目的。 设选取的预条件矩阵为皿，s t e i h a u g 提出的方法解决的是下列问题的近似解： 册吨( d ) = d + i 2 d r 嘎d 9 i 绪论 硕士学位论文 j f 0 皿d 0 t ( 2 1 ) 当砬= ，时，( 2 1 ) 即为子问题的解，下述方法即为正常的共轭梯度法。给定初始近似 解西，并记乃= v 吼( 4 ) = 一( 既+ 反面) ，以b 为预条件矩阵的预条件共轭梯度法采 用下述迭代格式 。d j n = d j + aj p j ，j = l ，2 ，”， a = ( q 1 皿) 。1 乃 ， 。 p ，：( 砬r d i ) - r j 博l p ，一。 心3 ， 厂，r ( q r o k ) 一厂7 q 2 薪 岛，霜f f 西( o ：葡v a 瓦- r j 当下述三种情况之一出现是，迭代终止，并确定一个近似最优解。 ( i ) 8 q t i i 趣时，取反= 嘭一。+ 奶以作为近似最优解，其中t 值应满足方程 i i p i ( d 卜l + 勿，一1 ) 8 = a i ( i d d e , p , o ，即乃为不定矩阵反的一个负曲率方向，这时取畋= d ，+ p ，作为近似最 优解，t 值应满足方程 l 皿( d ，+ 矽) | i - a t ( i i i ) 0 q t 0 s ，则趣_ 0 ，r x 1 ) 收敛。 p 2 ：如果存在占使得恬。0 s 且 h 收敛，则趣不趋于o 。 然后可立即得出任意满足p 1 和p 2 的算法，厂( 砟) 下无界或l i i i l i i 吒郴恬。l i = o 二者必 1 0 硕士学位论文 自适应非单调信赖域法 居其一。 为证明信赖域算法的一阶全局收敛性，p o w e l l 对信赖域子问题的近似解吨，在下 降量上，给出了以下要求，即存在常数f o 使反满足 一( 哝) f0 i l m i l l ( 趣，0 颤i 反i i ) l i d , l l - 0 ，则 奴卜o c 9 0 = - a g o g + 鼍一最b t g 存在一个无约束的最小值，且当口= 氍t g l g ；色g 。取的最小值 斛训一1 ：6 矧t 盎肛号l l g , 1 1 2 1 1 b , 1 1 ： 开且壤a k0 & 0 ，则i i 口g , i i 赴凼此在口处取得有约柬f 的最小值。如 果爵& 西恳 赴i l 8 ，则口= 。l l g 。8 处取得有约束下的最小值 特嘲一敝( 南h 口厕a k 版t 色 如锅) + l ( 躲( 甜色繇 一l ：6 0 川t o 、( a k ，, 、 一监2 睑 如果g ；b 0 ，则不存在无约束的最小值且在口= 赴川8 处取得最小值 c a - a g i ) = 一口g i + 专口2 最一口爵g 七= 一0 i i 七 引理得证。 如果嚷是子问题的不精确，则下降量至少大于柯西点。如果矾为精确解，由于 吮( d ) 的最小值至少小于等于其在负梯度方向上最小值，上述引理给出了丸( j ) 最小值 的一个上界，由此也可得出充分下降量( 2 2 ) 中7 的一个上界，即取r 占，则算法或者找到一些满足收敛条件的点或者有破专0h x 。) 收敛。 证明：假设推广的信赖域算法不终止于满足收敛的点x 。由于厂有下界， 。f ( x 。) 一f ( x m ) o ，可得脚f ( x 。) 一f ( x m ) - - t o ，。s l i g 。i l m i r x ( a 。，0 9 。i i i i b 。i i ) 有由于存在占使得恬。1 1 s 及0 色0 一致上有界可知必有下式成立 埘i 如果不存在成功的迭代，则。以一a ，此时显然有y 。 ，a 。砖士1 a f + l ，同理有。枷。 o o 。 另一方面如果存在无穷个成功的迭代点，令，表示任一成功的迭代，但，+ 1 不成功， 令m 表示满足七叠s v i + i k m ，此时有七龙一- 1 a ，+ l 砖一1 乃，因此 三郇托k - l - i 艄- - k = l + lz k = i 砖2 南i t 2 f i = ，+ l一， 因此 。互s 郇( 1 + 南) 酗锄 立即可知。一趣 占，则( 2 2 ) 表明当t 充分小时存在口 o 使得 一唬( 畋) 以。由于轨) 收敛，所有点列都位于一个紧集中，v f ( x 七) 在此集中一 致连续，所以如假设a 。一0 ，则 磷阿( 吨+ 善畋) 一v f ( x ) l l - - , o 。 而此时不等式( 2 3 ) 趋于零表明成寸1 。但此时根据信赖域半径的修正法则有趣不趋 于零。由此矛盾可知赴必定不趋于零，引理得证。 由上述引理算法满足p 1 和p 2 ，可得如下定理。 定理1 7 ( p o w e l l ) 设厂在区域qcr ”上连续可微，由推广的信赖域算法产生的序列 稚) cq 。假设子问题( 1 ) 中g 。= v f ( x 。) 且其近似解反满足( 2 2 ) ，l 陂0 一致有界，如 果厂在q 上有下界，则算法或者终止于一些满足收敛条件的点以或者有 l i m i n f k 。i i g 。1 1 = o 。 1 2 关于非单调信赖域法 1 2 1 非单调线性搜索法 到目前为止，大多数经典的求解非线性优化的信赖域方法都是与上述过程相类似 的单调的信赖域方法，也就是在迭代过程中目标函数( 或价值函数) 值是单调下降的， 并且单调性在收敛性的证明中起着非常重要的作用用单调性来保证全局收敛性。 即使初始点远离最优点，全局收敛性也可以通过一个合适的线性搜索来实现。但这不 是使算法收敛的本质要求。并且线性搜索也有它的缺点：当迭代点进入一个很窄的弯 谷时，强迫目标函数单调会产生小步长或者锯齿现象，因此会降低算法的效率。偶尔 允许迭代点的目标函数值上升会提高收敛率。 早在1 9 8 2 年，c h a m b e r l a i n 3 4 为了克服m a r o t o s 效应而提出的w a t c h d o g 技术就 含有非单调的思想，这种方法的迭代策略是，进行一次通常的线性搜索，如果效益函 数下降很多，则下一步用松弛搜索。经过这次松弛搜索后若效益函数值下降，则继续 用松弛搜索做下去。若果用松弛搜索得到的新点使效益函数值上升，则把用松弛搜索 前的那个点视为“看守点。由松弛搜索得出的一点出发进行线性搜索。若迭代了一 定次数后得到的效益函数值比看守点的函数值小，则由此点再用松弛搜索做下去：反 之，则退回到看守点用标准线性搜索进行迭代。 下面给出带极大值非单调线性搜索算法： 对无约束优化 1 3 1 绪论硕士学位论文 m i n7 r ( x )x r ” 若g k 0 ，则由线性搜索确定一个方向反，沿着以确定一个, y , 长o c k ，然后给出下一 个近似点x k + l = x k + a k d k 在传统线性搜索法中要求目标函数值单调下降，即t f ( x k + 。) f ( x k ) 非单调线性搜索并不要求迭代的每一步函数值下降，而是要求 f ( x k + 1 ) m a xf ( x k 。) o句细(。(24) 其中m ( 0 ) = 0 ，0 m ( k ) r d m m ( k 一1 ) + 1 ，m 】，m 为一固定常数。这样当迭代进入一 个很窄的弯谷时可以克服小步长或锯齿现象。 2 0 0 4 年张洪超等【8 】提出了一种凸组合的非单调线性搜索法， 算法( 1 4 ) ： s t e p l ：初始化：给定初始, ax o ，参数o 1 ，0 万 盯 1 0 ， 令c o = f ( x o ) ，0 0 = 1 ，k = - 0 ； s t e p 2 ：收敛性检测：8 0 儿= 苁( 畋) 【 m = 0 儿= m i n g ，段) a = 掣老 若反以，令x k + l = x k + 矾；若o k - - 以 以时，接受畋，某些时候太严格( 成 以) 。但是构造的以不 一定是正的，所以并不意味着厂( 吒+ ) f ( x k ) 尽管么( 畋) 0 ，因此 厂( 耳) ) 不一定是 单调下降的。其中他们在收敛性的证明中用到例卜c0 0 ，这也是本文选用只有梯度 信息修正信赖域半径的模型的原因之一。 1 9 9 7 年，p h i l i p p el t o i n t 2 给出了另一种非单调信赖域法。其方法同传统信赖域 法的主要区别是：在可接受检测中 t o l , k 血堕堕地) j = m o 以。：! 垒2 二f 兰亟2 一 苁( 稚) 一办( + 畋) 并且以= m a x p l 戊，i ) 他修正的成通常比标准的可接受比率大或者相等。因此用标准信赖域法删去的 步长在这种方法中是可以接受的，并且在作最后p 个成功迭代后可以保证目标函数值 充分下降。由于在实验中发现参数p ( 要考虑的成功迭代) 并不总是最好的，后来 t o i n t 又提出了对可行域是闭凸集的自适应非单调信赖域法，其中p 是由算法本身隐 式定义的。总之，正如t o 疏在此文中所说，非单调信赖域算法相对非单调线性搜索 算法还很不成熟，这方面的现有文献也比较少。 最近出现了一种新的非单调优化算法：f i l t e r 方法，它是针对带约束的优化问题 而提出的，并且由于其思想新颖，计算效果突出而备受关注。非单调优化方法的另一 个最新进展是由m u l b r i c h 和s u l b r i c h 给出的一个不用罚参数的对等式约束的非单调 信赖域方法该方法也是受f i l t e 方法的启发才产生的，但是它与f i l t e r 方法的最大不同 之处在于它并不是用f i l t e r 的概念来选择新的接受点，而是用与经典的非单调信赖域 技巧非常类似的方法分别判断是否接受对零空间和值空间的子问题所求得的解。 迄今为止，大多数的非单调信赖域算法也只是对无约束优化问题设计的，并且它 的理论基础很不完善，到目前为止，我们还不能根据目标函数的一些显性特征来判断 哪一类函数适合用非单调的优化算法，而只能在算出大量的题目后给出一个与单调优 化算法相比较的统计结果显然能否将单调与非单调的思想融合到一个算法中是在实 际计算中的一个重要问题。 i 绪论硕士学位论文 1 2 3 自适应信赖域法 2 0 0 3 年，张菊亮等【8 】提出了非单调自适应信赖域法。他们重新构造了信赖域子 问题： 爨磐么( 以) = r d + i ，d 7 鼠d s t 瓯 其中= c p o 反| | 府t ，0 c 0 使 g d i s t ( x ，x ) 2 厂( x ) 一厂 哆 c 2 d i s t ( x ，x + ) sl i g ( x ) 得到了信赖域法的超线性收敛性。他们重新构造了信赖域子问题，他们的子问题为 袈粤吮( 反) = 丁d + k ，d r 色j s t i l a l l - 口, - - c ，r 其中o c l ，o y 0 使 c l d i s t ( x ，x ) 2 厂( 功一 宰) c 2 d i s t ( x ，x ) - i g ( x ) i 证明了信赖域法的超线性收敛性。其中它们重新构造了信赖域子问题： 装碧么( 以) = & r d + 壹最d s t l i d l l c pi i g 。1 7a 。 这里0 c l ，0 y 0 段= 么( 以) 【 m = 0 ( 2 6 ) ，：( 垒! 二! 兰生2 以 一我( 畋) 其中厶表示m 个后续数中最大的一个，( 2 6 ) 式表明可接受步长应该保证目标函数 充分下降棚与训啦m m i n 卜端保持相近。 硕士学位论文 自适应非单调信赖域法 如果反 心，令故+ 1 - - x k 。否则，定义黾+ l = x k + 以。在这篇文章中，邓乃扬等 考虑的是无约束优化问题。当步长趋向于0 时他们允许用一个渐近精确的向量近似梯 度。其中他们在收敛性证明中用到m i ，0 繇这也是本文选用只带有梯度信息的 信赖域半径的原因之一。在数值实验中，段长m 他们只选用了5 和1 0 。 ( 2 ) t o i n t 修正的反 1 0 非单调信赖域法 。 z 是一个常数，p 是非负整数，用来调节所要比较的后续数的个数， 无( i ) 一f ( x k + 噍) 只。七2 1 一 丑 驴刺粼 反2 m a x p l , k ，户2 。， 厶( ”= 扭麟m a x 咀，z 岛= 矽( 薯) 一矽( 薯+ z ) 如果反 。 如果岛 编，定义矗+ l = t 返回解子问题。否则，令最们2 五+ 吐，继续下一步并 且修正和吒，其中 吒2 吒一么( 吃) q = 啡一九( 吨) b 修正到目前为止最好的值。 如果五+ l z ，令z = 五+ l 并且吒= 0 。 d 重置相关值 如果，= h ，令o = 以。r 他们证明了上述两种方法的全局收敛性。 ( 3 ) 为了克服不同段长m 所带来的影响，张洪超等提出了凸组合的非单调线性搜索准 则，以w o l f e 准则为例 f ( x i + 口j d k ) c 女+ 阮i v f ( x t ) d i 可( 以+ 吒d k ) o v f ( x t ) 以 其中g + l 2 r k q k + l 。一c k + l = ( r l k q g + f ( x m ) ) 级+ l 我们可以看到q + 。是c k 和( x ) 的凸组合，因为c 。= f ( x 。) ，所以q 是f ( x 。) ， f ( x k ) 的凸组合。如果7 7 = o 即是标准的w | 0 l f e 准则，如果r = 1 则4 = c = l _ 厂( ) ，是所有函数值的平均值。在( 2 4 ) 只考虑了最后m 个函数值。我 i , 1 1 “ 们不难发现，任意巩【o ，1 ，q 在石和4 之间，这表明方法的可行性。 尽管极大值形式的非单调技巧在很多情况下能够得到较好的结果，但是这种方法 一方面能丢掉一些好的函数值，另一方面段长m 影响算法的效率。文献【1 7 】中举了一 个特例： f ( x ) = 音矿，x r ，x o 0 ，反= - x k ，并且 f1 2 廿如果k = i 2 吼2 1 2 其它 算法超线性收敛于o ，但是当k 充分大时对任意固定的m 都不满足极大值形式的 非单调线性搜索： f ( x k + 反) m 竖、f ( x j , 一，) + 1 t f z k g ：反 u j 肘i 丘i 本文的目的是用这种非单调线性搜索准则修正岛。用以上的模型函数( 幸) 和修正 的成构造自适应非单调信赖域法。 下面给出具体的算法( 2 1 ) ： s t e p l 初始化：给定初始点c ( o ，1 ) ，厂( o ，1 ) ，( 0 ，1 ) ，巩( o ，1 ) ，p 为非负整数， q 0 = l ，c o = f ( x o ) 置k = - i 。 s t e p 2 收敛性检测：计算，若0 0 k 时有恬( ) i l 。 因为 覆) 为无穷序列，故反= 伽d ( 畋) 胖d ( 以) r l ，即a r e d t _ _ r l p r e d i 又咖训啦i i i l m i n 卜厕i i g 女1 1 ) 所以q 川磁圳洲i n i n 卜厕i i g , i i ) ( 2 7 ) 令彬= 则( 2 7 ) 式为 c ：- f ( x + 畋) i 1 9 10 i 所以八+ 破) q - ， l l g , l l a 。- - l l g , 1 1 1 + ，扩 又= 掣型嘎也呤篆慨i i + ，( 2 8 )故“x么+l x ，七+ l 所以g + 。q ，q 是单调递减的。 下面证明( 毪) 下有界。 因为五q c o = f ( x o ) ， 所以f ( x k ) 所 o ，对所有z x i l i x - x l l 0 便得 f ( x k ) f ( x k + 4 ) 刀 一九( 以) 所以学掣箍产刁 所以吨是可接受的。 同文献 1 1 中定理4 2 的证明类似，我们能证明h 。钳_ 0 ， 因此，h 钳一o ， 2 4 关于子问题的求解 在这一部分中我们考虑如何得到子问题的近似解，使得满足充分f 降条件和f 降 方向： p 二 删洮i il