（应用数学专业论文）无约束最优化问题的一类非单调信赖域算法研究.pdf

摘要 本文主要研究非单调信赖域方法目前。信赖域方法和线性搜索方法是求 解非线性优化问题的两类主要的数值方法与线性搜索方法相比。信赖域方法 思想新颖具有可靠性。有效性和很强的收敛性鉴于信赖域方法的优点。由它 来构造新的优化方法成为非线性优化界许多学者关注的焦点但是人们发现t 在实际计算中，对于某些问题单调算法并不能保证算法的有效性 1 9 8 6 年， g r i p p o 等人l 删，砌提出了种非单调线搜索，并将此技术分另u 运用到n e w t o n 法和截n e w t o n 法中1 9 9 3 年，邓乃扬等人口l j 首次将非单调技术应用到信 赖域方法中在一定条件下证明了其全局收敛性和超线性收敛性。数值试验表 明对某些问题。非单调倍赖域方法比相应的单调算法有更好的数值结果以上 提到的非单调技术都是以，l 时一粤峰。f ( x - j ) 为参考函数值来实现的，其中 r e ( o ) ；0 ，0 s m ( k ) s r a i n 【m 一1 ) + 1 ，卅，m 是给定的正整数但是，这 种非单调技术对于某些检验函数其数值结果依赖于m 的选取为此柯小伍。 韩继业弘胡提出，在某一步后，每试探一步要求当前点的函数值与前不固定( 如 肘 + 1 ) 个点中函数值最大的进行比较。而且m k 可进行调整；t o i n t 弘训给出 了自适应非单调倍赖域算法n m t r 2 ，在此算法中参数m 是由算法本身隐式定 义的，而不是某一预先给定值；z h a n ghc 和w ，w ，h a g e r 弘o j 提出了一种新的 非单调线搜索方法，也很好的避免了上述缺点另外1 9 8 0 年，d a v i d o n 瞄6 j 首 次提出锥模型。它比二次模型更一般鉴于以上工作的基础上，本文提出了两类 新的非单调信赖域方法 第一章我们首先简要的介绍了最优化问题的提出以及判断最优解常用的最 优性条件。其次回顾求解无约束最优化问题的线性搜索方法和信赖域方法的基本 思想及其研究成果 第二章，我们提出了一类拟牛顿非单调信赖域方法不同于传统的非单调信 赖域算法此算法在每步都采用非单调w o l f e 线搜索得到下一个迭代点这样得 到的新算法不仅不需重解子问题。而且在每步迭代满足拟牛顿方程同时保证目标 函数的近似海赛阵风的正定性在适当的条件下，证明了此算法的全局收敛性 和q 二次收敛性数值结果表明该算法的有效性 第三章，我们提出了一类基于锥模型的非单调信赖域算法基于二次模型的 相应算法是该算法的特例该算法克服了用于产生非单调性的参考函数值依赖于 某一正整数m 的缺点当试探步不被接受时，采用非单调线搜索，从而减少了 计算量在适当的条件下。证明了该算法的全局收敛性和q 二次收敛性数值 试验证实该算法是有效的 关键词：无约束最优化问题，非单调倍赖域方法。非单调线搜索，二次模型， 锥模型全局收敛性 1 1 a b s t r a c t i nt h i sp a p e r ，w em a i n l ys t u d yn o n m o n o t o n i ct r u s tr e g i o nm e t h o d s a t p r e s e n t ，t r u s tr a g i o nm e t h o da n dl i n es e a r c hm e t h o da r em a i n l yt w ot y p i e so f n u m e r i c a la l g o r i t h m sf o rn o n f i n e a ro p t i m i z a t i o n c o m p a r e dw i t hl i n es e a r c h m e t h o d ，t r u s tr e g i o nm e t h o dh a sn e wi d e a , r o b u s t n e s s ，v a l i d i t y , s t r o n g l yc o i l - v e r g e n c e i nv i e wo ft h ea d v a n t a g eo ft r u s tr e g i o nm e t h o d ，m a n yr e s e n r c h e m i nn o n l i n e a ro p t i m i z a t i o na mf o c u so ns t r u c t u r i n gt h en e wa l g o r i t h mb yt r u s t r e g i o nm e t h o d h o w e v e r ，p e o p l ef o u n dt h a tm o n o t o n i ca l g o r i t h mc o u l d tp l e d g e t h ev a l i d i t yf o r ee x a m p l e s i n1 9 8 6 g r i p p oa n do t h e r s1 1 9 2 qp o n dak i n d o fn o n m o n o t o n i cl i n es e a r c ht e c h n i q u ea n da p p l i e di tt on e w t o nm e t h o da n d c u t t e dn e w t o nm e t h o d i n1 9 9 3 n a ly a n g d e n ga n do t h e r s 弘j if i r s t l ya p p l i e d n o n m o n o t o n i ct e c h n i q u et ot r u s tr e g i o nm e t h o da n dp r o v e di t s9 1 0 b a la n ds t l - p e r l i n e a rc o n v e r g e n c eu n d e rs u i t a b l ec o n d i t i o n s n u m e r i c a le x p e r i m e n t ss h o w e d 如a tt h en o n m o n o t o n i ct r u s tr e g i o nm e t h o dw a ss u p e r i o rt ot h ec o w e s p o n d i n g m o n o t o n i cm e t h o df o r8 0 m ep r o b l e m s t h en o n m o n o t o n i ct e c h n i q u em e n t i o n e d a b 0 、，ei sr e a l i z e db y 确2 o 。m 渤a x ( z 一j ) ，”h e r em ( o ) 2o ，o m ( 。) s r a i nm 传一1 ) + 1 ，卅，mi st h eg i v e np o s i t i v ei n t e g e r h o w e v e r ，f o rs o m et e s t f u n c t i o n ，t h en u m e r i c a lr e s u l t so ft h i sn o n m o n o t o n i ct e c h n i q u er e l i e so nt h ec h o i c e o fm t h e r e f o r x i a ow u k ea n dj iy e h a n 口功p r o p o s e dt h a ta f t e rs o m es t e p ，t h e f u n c t i o nv a l u eo ft h ec u r r e n ti t e r a t ep o i n ts h o u l db ec o m p a r e dw i t ht h em a x i m a l f u n c t i o nv a l u ei ns o m ef o r m e ri t e r a t ep o i n t s ( m k + 1 ) ，w h e r et h en u m b e ro fi t e r - a t ep o i n t sw a sn o tf i x e d ，m o r e o v e r ，m kc o u l db ea d j u s t e d t o i n ti z 训p r o p o s e d t h ea d a p t i v en o n m o n o t o u i ct r u s tr e g i o na l g o r i t h mn m t r 2 ，w h e r et h ep a r a m e - t e rmw a sd e f i e db yt h ea l g o r i t h mi t s e l fa n dw a s h tap r e f i x e dv a l u e z h a n gh ca n dw w h a g e r1 2 6 1 p r o p e s e dan e wn o n m o n o t o n i cl i n e - s e a r c hm e t h o d ，w h i c h s u c c e s s f u l l ya v o i d e dt h ep r e c e d i n gs h o r t c o m i n g b e s i d e s ，i n1 9 8 0 ，d a v i d o n 【2 铷 f i r s t l yp r o p o dt h ec o n i om o d e lw h i c hi sm o r eg e n e r a lt h a nq u a d r a t i cm o d e l b a s e do nt h ep r e c e d i n gw o r k w ep r o p o s et w ok i n d so fn e wn o n m o n o t o n i et r u s t r e g i o na l g o r i t h m s i nc h a p t e r1 ，f i r s t l y , w ei n t r o d u c et h ed e v e l o p m e n to fo p t i m i z a t i o na n ds o m e e x t e n s i v eo p t i m a l i t yc o n d i t i o n sw h i c ht od e c i d et h eo p t i m u ms o l u t i o n s e c o n d l y w er e v i e wt h eb a s i ci d e ao fl i n es e a r c hm e t h o d sa n dt r u s tr e g i o nm e t h o d sf o r u 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 sa n dt h e i r sr e s e a r c hw o r k s i nc h a p t e r2 ，w ep r e s e n t8q u a s i - n e w t o nn o n m o n o t o n i ct r u s tr e g i o na l g o - r i t h m u n l i k et r a d i t i o n a ln o n m o n o t o n i ct r u s tr e g i o na l g o r i t h m s ，o u ra l g o r i t h m g e t st h en e x tp o i n tb yt h en o n m o n o t o n i cw d l i n es e a r c h a te a c hi t e r a t i o n ， t h i 8n e wa l g o r i t h mn o to n l yd o e sn o tr e s o l v et h es u b p r o b l e mb u ta l s os a t i s f i e s t h eq u a s i - n e w t o nc o n d i t i o na te a c hi t e r a t i o na n ds i m u l t a n e o u s l ym a i n t a i n sa p c e i t i v e * d e f i n i t ea p p r o x i n m t i o nt ot h eh e i n no ft h eo b j e c t i v ef u n c t i o n u n d e r m i l dc o n d i t i o n s ，w ep r o v et h eg l o b a lc o n v e r g e n c ee n dq - q u a d r a t i cc o n v e r g e n c eo f t h ea l g o r i t h m n u m e r i c a lr e 8 u l t bs h o wi t se f f i c i e n c y i nc h a p t e r3 w ep r e s e n tnn o n m o n o t o n l ct n l 就r e g i o na l g o r i t h mb a s e do nt h e c o n i cm o d e l t h ea l g o r i t h mb a s e d 傩t h eq u a d r a t i cm o d e li sas p e c i a le x m a p l e o fo u ra l g o r i t h m o u ra l g o r i t h mo m c o m e 8as h o r t c o m i n g i e t h er e f e r e n c e f u n c t i o nw l u eu s e dt og e n e r a t en o n - m o n o t o n i c i t yr e l y so i ls o m ep o s i t i v ei n t e g e r m w h 镪t h et f i a ls t e pi sn o ta c c e p t e d w ee m p l o y & n o n m o n o t o m i cl i n es e a r c h t or e d u c et h ec o s t u n d e rm i l dc o n d i t i o n s w ep r o v et h eg l o b a lc o n v e r g e n c ea n d q - q u a d r a t i cc o n v e r g e n c eo ft h ea l g o r i t h m ，n u m e r i c a lr e s u l t ss h o wi t se f f i c i e n c y k e yw o r d s ：u n c o n s t r a i n e do p t i m i z a t i o n ，n o n m o n o t o n i ct r a s v - r e g i o nm e t h o d ， n o n m o n o t o n i cl i n es e a r c h ，q u a d r a t i cm o d e l ，c o n i cm o d e l ，g l o b a lc o n v e r g e n c e 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或 集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体。 均已在文申以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名芰，h 苦诰 日期碲多月多日 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留使用学位论文的规定学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子舨和纸质版有权将 学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将 学位论文的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出 版保密的学位论文在解密后适用本规定 学位论文作者签名：支f 1 耄姥 日期；五7 f 舌月6 日 1 最优化问题简介 这一章我们简要介绍最优化问题的发展现状第一节简要地阐述最 优化问题的提出以及判断最优解常用的最优性条件；第二节。总结了求解 无约束优化问题常用的几类线搜索算法t 第三节给出了求解无约束优化 问题的信赖域算法的基本框架及其基本理论。总结了信赖域算法近年来的 研究成果；最后一节介绍了本文的主要工作 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一仃应用性很强的年轻学穰虽然最优化可以追溯到十 分古老的极值问题。但是直到1 9 4 7 年d a n t z i g 提出一般线性规划问题的单纯形 法之后。它才成为- n 独立的学科随着现代科技的发展和计算机的广泛应用， 进步推动了最优化理论和算法的研究今天，最优化理论与方法在经济规划、 政府决策生产管理，交通运输和军事国防等方面都得到了广泛的应用，已经成 为一门十分活跃的学科 最优化问题的一般形式可归结为求解如下的极小值问题 m 枷i n 雕) ( 1 1 - 1 ) 其中，舻是决策变量，( 正) 为目标函数，d 舻为可行域 根据变量的类型，最优化问题可分为连续型最优化问题和离散型最优化问题 ( 也称组合优化) 连续型最优化问题又可分为目标函数和约束函数均为线性时的 线性规划问题，以及目标函数和约束函数中至少有个为非线性时的非线性优化 问题根据可行域d 的类型，最优化问题又可分为约束优化问题和无约束优化 问题特别地当可行域d = r r l 时。则最优化问题( 1 1 1 ) 称为无约束最优化 问题 一般地，约束优化问题通常可描述为 砌r a i n 。m ) s t q ( z ) 一0 ， q ( z ) z0 ， i l ，2 ，r a ； i = m + 1 ，m + 2 ，n 本文主要研究无约束最优化问题，即 ( 1 1 2 ) ( 1 1 3 ) ( 1 1 4 ) 罢舞，( z ) ( 1 1 5 ) 其中，：j p r 为连续可微函数 本文主要的符号约定- 除特别说明外1 i 指e u c l i n d e a n 范数；v 2 y ( z ) 指目标函数，( z ) 的h e s g m n 矩阵；岛指9 2 ，( 瓢) 或其近似 下面我们给出全局最优解和局部最优解的定义 定义1 1 着矿舻具有性质，比舻，均有，扣) ，( 矿) ，则称矿为问 题( 1 1 5 ) 的全局最优解 定义1 2 若矿舻具有性质：存在矿的某个邻域眦( 矿) = 扛z 一矿0 0 为某个正数，使得v e m ( 矿) ，均有，( z ) 2 i ( x ) ，则称矿为问 题( 1 1 5 ) 的一个局部最优解 在一般情形下找出全局最优解非常困难，但在许多实际应用中，求局部最优 解已满足了问题的需要因此，在实际算法中我们通常是找出满足一定条件( 最 优性条件) 的局部最优解即可当目标函数，( z ) 是凸函数时，局部最优解就是 全局最优解 设目标函数的一阶导数和二阶导数存在，且分别记为9 ( z ) ：三v ，( z ) ，g ( z ) = v 2 ，扛) ，下面我们给出最优解的必要条件。 引理1 1f 1 j ( 无约束优化一阶必要条件) 若矿为问题( 1 1 5 ) 的一个局部最优解，且在矿的某个邻域内，( z ) c 1 ， 2 则 则 a ( x ) = o ( 1 1 6 ) 引理1 2i l 】( 无约束优化二阶必要条件) 若矿为问题( 1 1 5 ) 的一个局部最优解，且在矿的某个邻域内，( 功伊， 夕扛) 一0 ，g ( ) 20 1 2 求解无约束优化问题的线搜索算法 ( 1 1 7 ) 目翦。求解无约束最优化问题( 1 1 5 ) 的计算方法主要是迭代法其基本思 想是，给定个初始点粕j p ，然后由算法产生迭代点列 “ ，希望某个点 互i 是问题的局部最优点或者点列 以 收敛于莱个局部最优点现有的求解无 约束最优化问题( 1 1 5 ) 的计算方法可分为两大类一类是线搜索方法。另一类 是信赖域方法本节主要介绍几种常见的线搜索算法 线搜索方法是一类比较成熟的方法其基本思想是，对于当前的迭代点乳，首 先由算法确定一个搜索方向d h 一般情况下，搜索方向呶应使目标函数，( z ) 下 降，然后确定沿也方向行进的步长k 0 ，并得到下一个迭代点z k + l 一巩+ k d k 其中步长k 可由精确线搜索和非精确线搜索求得常用的非精确线搜索是： a r m i j o 线搜索，w o l f e 线搜索和a r m i j o - g o l d s t e i n 线搜索由于寻求搜索方向 血有不同的方法，所以常用的线搜索方法可分为以下几大类t 最速下降法，牛顿 法，共轭梯度法。拟牛顿法等现简单介绍如下t a r m i j o 线搜索准则： 确定k 0 ，使k 为集合 矿l f = 0 ，l ，p ( 0 ，1 ) 中满足如下不等式 ，( + a 女呶) ，( z i ) + 口a k g ( z k ) t 出， 盯( o ，互1 ) ， ( 1 2 1 ) 的最大元素 w o l f e 线搜索准则： 3 确定札 o ，使k 满足如下不等式 ，( 巩+ 扎血) s ，( i ) + 盯a i g ( ) r 也， 盯( o ，互1 ) g ( 霉l 十x t d k ) 7 d i2p 9 ( z ) 7 血， 芦ep ，1 ) ， 如果用下面的不等式 i g ( z k4 - a i 矾) r 如ls 一卢9 ( 巩) 7 出，卢( 口，1 ) ， 代替( 1 2 3 ) ，则( 1 2 2 ) 一( 1 2 4 ) 常被称为强w o l f e 线搜索准则 a r m i j o - g o l d s t e i n 线搜索准则： 确定k 0 ，使k 满足如下不等式 ，( 班+ k 以) s ，( 瓢) + 口a 姆( z ) 7 也， ，( 戤+ 扎血) ，( ) - f ( 1 一a ) a k g ( x k ) r d k ( 1 2 2 ) ( 1 2 3 ) ( 1 2 ，4 ) ( 1 2 5 ) 口( o ，j 1 ) ( 1 2 6 ) 最速下降法 最速下降法，又称梯度法。是法国著名数学家c a u c h y 在1 8 4 7 年提出的， 是无约束最优化算法中最简单的也是最基本的方法该方法是以负梯度方向- - g k 作为极小化算法的搜索方向。其迭代格式为+ l = o 女一a 女鲰最速下降法具有 简单可靠，运算量小等优点。在最优化中具有重要的理论意义但是，最速下降 方向仅反映了目标函数的局部性质，对许多问题收敛较慢。仅有线性收敛速度， 这是因为相继两次迭代的搜索方向正交而产生。锯齿。现象为改进最速下降法 的收敛速度，一些学者在步长的选取上做了一些工作，如b a r z i l a i 和b o r w e i n 于 1 9 8 8 年提出了两点步长梯度法( 可参见文献( 2 1 中算法3 1 7 ) ，并且证明了此算法 是r - 超线性收敛的，这些表明最速下降法中的步长选取对算法的影响十分大， 对这个问题有待更深入的研究 牛顿法 4 牛顿法是求解无约柬优化问题最古老的算法之一。但到目前为止它的改进形 式仍不失为最有效的算法之一牛顿法的基本思想是利用目标函数的二次t a y l o r 展开。并将其极小化记目标函数的h e s s i a n 矩阵为吼，则搜索方向取为也= 一( 1 m 所得的方法就是牛顿法对于正定二次函数，牛顿法一步即可达到最优 解对于非二次函数，牛顿法并不能保证经有限次迭代求得最优解但由于目标 函数在最优点矿附近近似予- i t 函数故当初始点l 充分接近最优点矿时， 该方法= 阶收敛并且对二次凸函数具有二次终止性；当初始点远离最优点矿 对。吼不一定正定。从而牛顿方向不一定是下降方向。其收敛性不能得到保证 为克服瓯不正定这一困难，人们提出了许多修正措施最早的修正牛顿步 的方法是g o l d s t e i n 和p r i c e 在1 9 6 7 年提出的。即当吼不正定时，采用最速下 降方向一鳜代替牛顿方向1 9 7 2 年。m u r r a y 提出了一种对一般对称矩阵进行 强制性工矿分解的修正方法，其实质是对v 2 f ( x - ) + d k 进行二驴分解。其中 i k 是一对角阵此外，修正牛顿步的方法还有负曲率下降方向法有限差分牛 顿法等在牛顿法中。h e s s i a n 矩阵的存储量、计算量都很大。迭代的每一步都 必须求解线性方程组，计算量也很大 共轭梯度法 共轭梯度法最早是由h e s t e n e 8 和s t i e f e l 在1 9 5 2 年为求解线性方程组而提 出的，后经f l e t c h e r 和r e e v e s 发展，把这种方法用于求解无约柬最优化问题，使 之成为最优化算法中最常用的方法之一共扼梯度法的基本思想是：利用负梯度 方向和已有的搜索方向产生新的搜索方向。使得这些方向在，缸) 为凸二次函数 时相互共轭。并沿这组方向进行搜索，求出目标函数的极小点当目标函数，( z ) 连续可微时。其迭代格式为 z - + - = 巩+ 扎也，呶一 二爨+ 凤血一，l 主5 其中风为标量，著名的公式有s ，f r ：f f i 卷( f l e t c 胁一触吼 筇瞥( p i 出m b i r e - p o 触) ， 5 酽2 蒜喾夥( h e s t e n e s - s t i e f e l ) ， 卯72 石掣而( d a i - y u s n ) r 共轭梯度法具有二次终止性，即对于二次函数，采用精确一维搜索的共轭梯 度法在n 次迭代后终止然而，当目标函数为一般的非线性函数时。一些学者 对各共轭梯度法的收敛性做了不少有意义的工作在文献f 3 l 中a i - b a a l i 证明了 f r 方法具有全局收敛性但是p o w e u 指出，即使采用精确线搜索p r p 方法也 不一定有全局收敛性直到1 9 9 7 年l g r i p p o 和s l u d d i 提出了g r i p p o - l u c i d i 线搜索，并在此线搜索下证明了p r p 方法的全局收敛性( 参见【4 ，5 i ) 但p r p 方法具有良好的数值表现船方法的性质类似于p r p 方法d n i 和y u n n 严 格证明了采用w o l f e 线搜索的d y 方法在每一步均产生个下降方向。并且方 法全局收敛此外，考虑到以上方法各自的优缺点。人们提出了各类杂交共轭梯 度法，并且取得了一定的成效共轭梯度法具有算法简便。存储需求小等优点。 是解大规模优化问题的一类主要方法 拟牛顿法 拟牛顿算法是无约柬最优化问题中应用最广、理论上也最为成熟的方法之 一拟牛顿法的基本思想是；用不包含二阶导数的矩阵近似牛顿法中的h e s s i a n 矩阵的逆矩阵该算法的关键是z k 的选取，一般要求风对称正定并且满足拟 牛顿方程， h k “k s k ( 1 2 7 ) 拟牛顿法的搜索方向为如一一日( z 女) 孽( 缸) ，在著名的b r o y d e n 族拟牛顿法中， 日的校正迭代公式为； z 风一訾+ 簇州卿咖t ( 1 2 8 ) 一蒜+ 旦( l z 9 ) s k r u k2 一霸瓯+ 其中口f o ，1 】当8 分别为0 , 1 时，即为著名的d f p 公式和b f g s 公式 6 d f p 校正公式t h k + 1 风一繁警+ 舞 z 加， b f g s 校正公式； t 凰一等警+ 蓑似驯饥( 1 2 1 1 ) 此外，h u a n g 于1 9 7 ) 年提出了类比b r o y d e n 族更广泛的校正公式，我们 称之为h u a n g 族校正公式七十年代是拟牛顿法应用和理论发展最快的时期。其 中b r o y d e n 族是最著名的。其收敛性一直是研究的热点1 9 7 6 年。p o w e l l 证明 了若目标函数，( ) 是凸的二阶连续可微函数。且( x ) 有下界，则当采用w o l f e 线搜索准则确定步长时b f g s 方法总体收敛这是在不精确线搜索下拟牛顿算法 的第个全局收敛结果。具有重要的理论和实际意义1 9 8 5 年，b y r d ，n o c e d a l 和y u a n 进步将p o w e l l 的结果推广到除d f p 方法外的b r o y d e n 族证明了 对于凸的二阶连续可微函数，采用w o l f e 线搜索准则的b r o y d e n 族方法都是总 体收敛的拟牛顿算法在迭代过程中仅需一阶导数不必计算h e s s i a n 矩阵。并且 具有收敛速度快的优点，是最有效的一类无约束优化算法。但是它需要存储矩阵 及通过线性方程组来计算搜索方向。因而不适用于大型同题 1 3 求解无约束优化问题的信赖域算法 与线搜索方法不同，信赖域方法是另一类保证算法全局收敛的好方法它在 近三十年来受到了非线性优化界非常的重视信赖域方法的研究起源于p o w e u 1 9 7 0 年的工作f 0 1 后来，人们发现信赖域方法的基本技巧在一定意义下等价于 十分著名的求解非线性最小二乘的l e v e n b e r g - m a r q u a d t 方法 信赖域方法是一类较新的方法其基本思想是t 对于当前的迭代点轧，给定 个信赖域半径a k 0 ，然后在以矾为中心i 为半径的小邻域内，构造一个 逼近目标函数的模型。这个模型称为信赖域子问题，求解子问题得试探步毗，然 后利用某一评价函数来决定是否接受该试探步以及确定下一次迭代的信赖域半 径。如果试探步被接受。则瓢+ l 一+ d k ，否则o i + l x k ；信赖域半径的大小 通过迭代逐步调节，粗略地说。如果当前迭代模型较好地逼近原问题，则信赖域 半径可扩大，否则将缩小 7 一般情况下。在当前的迭代点2 女附近，用二次函数逼近目标函数f c x ) ，可 构造信赖域子问题如下， 瓣歌( d ) = o + i d f b k d ， ( 1 3 1 ) s t 1 i d l isa k ( 1 3 2 ) 其中弧一v f ( x k ) ，a k 0 为信赖域半径。对称阵b k 舻”是v 2 ，( z k ) 或其 近似矩阵记也为子问题的解。计算目标函数的实际下降量a r e d k 和预测下降 量p r e d 的比值得t m 一丝p r e d k 一笔攒， ( 1 s j 3 ) m 1 丽f 瓦i j 万一 【l j 石j 剐是否接受该试探步以及如何调节信赖域半径将根据这一比值来决定 下面给出求解问题( 1 1 5 ) 的倍赖域方法的基本形式， 算法1 2 1 圆 步1给出x le 冗，l ，b 1 舻椰，a l 0 ，0 ，风 1 岛 0 0 岛 ：峨n ) 的条件下证明了求解无约束优化问题的信赖域方法的超线性收敛 i 1 1 ， 性 1 9 8 4 年i 圳，p o w e l l 又在f 鼠0 出的假定下且要求迭代点是下降点的条 件下，证明了方法的弱收敛性1 9 9 4 年鸭袁亚湘对信赖域方法的收敛性证明 给出了详细的总结 虽然信赖域方法还不够成熟。目前。在实际虚用中信赖域方法还没有线搜索 方法那样广泛。但是，与线搜索方法相比。信赖域方法具有显著的优点：它具有很 强的收敛性并且能有效地勰决病态问题基于这些优点，它已经引起了优化界非 常的重视它的应用将会更加的广泛然而在基本的信赖域算法( 如算法1 2 1 ) 中也存在一个主要的缺点。即t 当试探步不被接受时需重解子问题。有时需重 解多次从而导致计算量的大最增加，因而这种策略不适用求解大规模问题，限 制了信被域方法的应用范围考虑到线搜索方法易于求得新的迭代点。袁亚湘和 n o c e d a l j 首创性地提出了将倍赖域方法和线搜索方法相结合来构造新计算方法 酌思想，并依此绘出了结合a r m i j o 线搜索的信赖域方法【i i l ，在此算法中当试 撵步不被接受时进行a r m i j o 线搜察。数值试验表明x - - ) c 减少了计算量另外。 g e r t z 在交1 1 6 】中研究了结合w o l f e 线搜索的信赖域方法，作者在每步迭代都 进行w o l f e 线搜索。这样做不仅减少了计算量，而且保证了序列 风 的正定性 且同时满足拟牛顿方程，使信赖域子问题( 1 3 1 ) 一( 1 ，3 2 ) 更加逼近原问题( 1 1 5 ) 关于这类算法还可见文【1 7 1 8 】， 算法1 2 1 是单调算法即在迭代过程中要求目标函数值比当前点的值严格 单调下降但是在实骑；计算中。人们发现t 对于某些问题，这样做并不能保证算 法的有效性例如。对著名的检验函数- r 0 6 e n b r o c k 函数。当迭代点接近最优点 时出现类似于m a r o t o s 效应的现象1 9 8 6 年。g r i p p o ，l a m p a r i e l l o ，l u c i d i1 1 川 提出了一种非单调线搜索技术，如下t ，( 瓢+ 盯n 血) 蜒m j a 州x q 【，( z 。) 】+ r 口 d 靠血， ( 1 3 1 3 ) 其中m ( 0 ) = 0 ，0sm ( ) sm i n ( m 佧一1 ) + 1 ，叫，r ( 0 ，1 ) ，口( 0 ，1 ) ，o 0 , m 是给定的正整数并且将此种非单调技术运用刭n e w t o n 法l l g l 和截n e w t o n 法【2 0 】中此后，各类非单调算法得到了广泛的研究 1 9 9 3 年，d e n g ，x i a o 和 z h o u 口1 1 首次将非单调技术运用到信赖域算法中提出了非单调信赖域算法，数 值试验表明对相当一部分检验函数非单调策略明显加快算法在其最优点附近的 1 0 收敛速度。得到精度更高的最优解 以上提列的非单调技术都是以 硒2 。嚣”m i 叫) ， ( 1 3 1 4 ) 为参考函数值来实现的。其中m ( 0 ) = 0 ，0 m ( t ) r a i n m 佧一i ) + 1 ，m ，m 是给定的正整数虽然这种策略是有效的。但也存在不足首先由于取当前迭代 点及其前m ( k ) 个点中函数值最大的f t ( k ) 作为参考函数值因而可能会在某些 步中丢失更优点；其次，对某些检验函数其数值结果依赖于m 的选取为此。 柯小伍，韩继业弘竭又提出了一种新的非单调信赖域算法。即算法在某一步 后，每试探步要求当前点的函数值与前不固定( 如肘i + 1 ) 个点中函数值最大 的进行比较丙且胁可进行调整对目标函数。当它性态好对甚至 缸可减 少为零。此时算法采用单调下降步i 当它性态越坏 如越大。此时算法采用非 单调下降步有利于算法快速收敛另外。t o i u t 【z 珥给出了自适应非单调信赖 域算法n m t r 2 ，在此算法中参数m 是由算法本身倦式定义的，而不是菜一预先 给定值有关非单调算法还见文1 1 8 ，2 4 ，2 5 ，2 6 1 以上提到的信赖域算法都是基于二次模型的，然而对一些非二次性态强。曲 率变化剧烈的函数用二次函数模型逼近效果较差为此，d a v i d o ni 删在1 9 8 0 年首次提出了无约束极小化的锥模型方法，其摸型比二次模型更加般随后， s o r e n s e n 【z 切和a r i y a w a n s a 等人p u l 对使用锥模型的拟牛顿法做了不少有意义 的工作1 9 9 5 年，诸梅芳、薛毅和张风圣卜，l j 将锥模型运用到信赖域算法中， 则对无约束最优化问题( 1 1 5 ) ，在第k 步，信赖域子问题采用下面的形式t tj 耵r0 瓣钆( d ) 2 r 硒g t a + 褊， ( 1 心) s t 0 d 0 t( 1 3 1 6 ) 其中g k = v f ( x k ) ，k 0 为信赖域半径，k 和风分别是n 维向量和n n 阶 对称矩阵( 1 3 1 5 ) 一( 1 3 ，1 6 ) 称为锥模型信赖域子问题，并且文【3 1 】给出了它的 求解方法及“和风的迭代公式之后，李正峰和邓乃扬p 习提出了基于锥模 型的一般信赖域算法，并做了收敛往分析张建科和刘三阳p 瑚结合非单调技 术给出了基于锥模型的非单调信赖域算法，数值实验表明对曲率变化剧烈的函数 基于锥模型的算法更加适用 1 1 1 4 本文的创新点 信赖域方法实现的关键是如何求得信赖域子问题，传统的信赖域方法往往 需重解子问题。特别是对大规模问题增加了计算量为避免这个缺点，袁亚湘 和n o c e d a l j 给出了结合a r m i j o 线搜索的信赖域方法【l “，但是算法在实现过 程中，为保证序列 b ) 的正定性当由修正公式给出的某个风+ l 不定时令 凤+ l = 鼠，从而信赖域子问题( 1 3 1 ) 一( 1 3 ，2 ) 逼近原问题( 1 1 5 ) 效果不佳另 外，g e r t z 在文【1 6 】中研究了结合w o l f e 线搜索的信赖域方法。作者在每步迭 代都进行w o l f e 线搜索，这样做不仅继承了文f l l j 的优点，而且改进了文f l l j 的缺点此外，近年来许多学者已在牛顿法。拟牛顿法。共轭梯度法。信赖域方 法等无约柬方法中引入非单调类搜索技巧并且许多数值实验已经证明了对某些 情况，非单调类算法比单调类算法更加有效【埘刎 受文【1 6 1 的启发。我们将非单调w o l f e 线搜索应用至b 传统的菲单调信穰域 算法中。在第二章中。我们提出了一类拟牛顿非单调信赖域方法此算法在每步 都采用非单谓w o l f e 线搜索得到下个迭代点这样得到的新算法不仅不需重 解子问题。丽且保证目标函数的近似海赛阵序列 凤 芷定。同时满足拟牛顿方 程。使倍赖域子问题( 1 3 1 ) ( 1 3 2 ) 更加逼近原忍隧( l 1 5 ) 并且证明了此算法 的全局收敛性和q 二次收敛性数值结果表明该算法十分有效 在第二章中采用的非单调w o l f e 线搜索是以( 1 3 1 4 ) 式定义的五( 耐为参考 函数值。这样做使得对一些检验函数其数值结果严重依赖于某一正整数m 的选 取。为克服这一缺点。我们将z h a n ghc 和w w h a g e r 【捌提出的非单调搜索 技术运用到信赖域方法中。在第三章中提出了一类基于锥模型的非单调信赖域 算法在该算法中。非单调线搜索和非单调信赖域方法的