（运筹学与控制论专业论文）求解非凸无约束优化问题的非单调bfgs方法.pdf

河南大学硕士学位论文 摘要 本论文研究求解非凸无约束优化问题的非单调b f g s 算法建立算法的收敛性， 并通过数值实验验证算法的有效性 第二章，我们在l i 和眦u 8 l l i m a 提出的修正的拟牛顿方程的基础上，提出一种求 解非凸极小化问题的非单调修正b f g s ( m b f g s ) 方法，该算法的一个重要特点是对 于迭代给出了一个更宽松的条件，并不要求目标函数值在每一步都严格下降我们 证明该算法用于求解非凸极小化问题时具有全局收敛性 第三章是对第二章所提算法的进一步研究，建立算法的局部超线性收敛并做 数值实验，结果表明，采用非单调搜索的m b f g s 方法比单调的m b f g s 方法的数值效 果明显要好 关键词：非凸极小化问题；拟牛顿法；非单调线搜索；全局收敛；超线性收敛 河南大学硕士学位论文 a b s t r a c t t h ep i n p eo ft h et h 部i si 8t os t u d yb f g sm e t h o di nn o n c o n v 饮w i t ha n o i l m o n o t o 聃 n n e8 e a r c h d r 舳l v i n gu n c o 璐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 ee s t a b l i s ht h ec o n v e r g e n c e t h 鲫陀mo ft h ep r o p o s e dm e t h o d w ea l s ot 部tt h ep r o p e dm e t l l o d 蚀a8 e to fp r o b l e 脚 i i lc h 印t e r2 ，b 勰e d0 nt h em o d i 丘e dq u 弱i n e w 屯o ne q u a t 沁nb yl ia n df 址岫h i m a ，w e p r o p o 舱am o d 遗e db f g s ( m b f g s ) m e t h o dw i t ha n o n n l o n o t o n el i n es e a r c hf o rn o n c o n v 麟m i n i m i z a t i o n a na t t r a c t i v ef e a t u r eo ft h ep r o p o dm e t h o di 8t h a tt h ec o i l d i t i o nf o r c o n t r 0 1 i n gt h ea u c c e p t a n c eo ft h en e x tn e wi t e r a t i o np o i n tw mb em o r ew e m 砥玎，w h i c ht h e v a l u eo fo b j e c t i v ef u n c t i o nn e e d n td e s c e n d8 t r i c t l ya te 砌li t e r a t i o n w ep r o v et h a tt h e n l e t h o d 罢灿a l l yc o h v e r g e n t 8f o rs l n gn o n c o n v e xm i n i i i l i z a t i o np r o b l e m sw i t l l o u tc 0 1 w e x a s s u m p t i o no no b j e c t i v ef h n c t i o i l 8 t h e p u r p 0 8 e do fc ：h 印t e r3i st o 胁h e r8 t u d yt h em e t h o dw h i c hp r o p o s e di nc h 印t e r 2 ，u n d e r8 0 l e 叩p r o p r i a t ec o n d i t i o 瑚，w e 鹤t a b l i s ht h e8 u p e r l i n e 甜c o i e r g e n c eo ft h e m e t h o d n u m e r i c a le ) ( p e r i i n e n t ss l l o wt h a tt h en o n m d n o t o n em b f g sm e t h o dp e r f o r 瑚 b e t t e rt h a nt h em o n o t o n em b f g sm e t h o dd o 鹤 k e yw o r d s ：n o n c o l w e xm i n i m i z a t i o np r o b l e m ；q u a s i n e w t o nm e t h o d s ；n o n m o n o - t o n el i n e8 e a r c h ；g 1 0 b a lc o i l 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 关于学位论文独立完成和内容创藏薛声晴 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育。科研机构的学位或证书而 段休得、) 【鞠学位论灭( 纸质又奉和电亍又奉) ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名： 盔：蜜：垒 2 d0 孑年6 月f 目 学位论文指导教师茎名：羔迄坠互 2 0 夕持多月f 日 第一章绪论 最优化理论与方法是运筹学中的一个十分活跃的分支最优化问题及其理论和 算法来源于经济、管理、工程等许多重要的领域，同时和计算数学的微分方程解法， 非线性方程组数值解法等分支有着密切的联系和应用随着电子计算机的普及，它 已广泛应用于化工、航空、机械、建筑、无线电技术等许多工程部门，另外在生产组 织、资源分配等管理科学方面，最优化方法已成为一种重要的决策手段 最优化问题根据有无约束条件可分为约束和无约束最优化问题当目标函数不 可微时，可以通过某些处理将之转化为可微的无约束优化问题【l ，2 】对于无约束优 化问题，首先因为很多实际问题的数学模型本身就是无约束的，也由于无约束优化 问题的求解相对容易的多，而解法的基本思想又常常可以推广到一般有约束的情形 因此，从这个意义上讲，研究无约束优化问题的计算方法就显得尤为重要，人们对它 的研究也十分重视，新的数值计算方法不断出现，如共扼梯度法、拟牛顿法【3 ，4 】以 及信赖域法f 5 】等求解无约束优化问题的拟牛顿算法自从上个世纪6 0 年代末开始就 已被广泛地研究，成为目前最成熟，应用最广泛的解法之一 1 1无约束最优化问题 无约束最优化问题的基本形式： l i n ，( z ) ，$ 瓣n ( 1 1 ) 其中，：舻一瓣称为目标函数 求解问题( 1 1 ) 的方法通常是采取迭代的形式，迭代法的基本思想是给出一个初 始点z o 舻，按照一定的准则产生一个点列【z 毛) ，使当z 七是有限点列时，其最后一点 是问题( 1 1 ) 的最优解；当z 七是无穷点列时，它有极限点，且其极限点是问题( 1 1 ) 的最 优解如果对所有z 腑n ，( z ) ，( z + ) ( ，( z ) ，( z ) ) ，则称z + 为( 1 1 ) 全局最优解( 严 格全局最优解) 如果存在6 o ，使得对所有满足忙一矿0 ，( $ ) ) ，则称矿为( 1 1 ) 的局部最优解( 严格局部最优解) 判断矿扩是否是( 1 1 ) 的最优解的条件有如下三种形式 一阶必要条件设函数，连续可微，若$ 是( 1 1 ) 的局部最优解，则 v ，( 矿) = 0 其中，v ，( z ) 表示，( z ) 的梯度 二阶必要条件设函数，二阶连续可微，若矿是( 1 1 ) 的局部最优解，则 v ，( 矿) = o 且矿v 2 ，( 矿) 让o ，地妒 二阶充分条件设函数，二阶连续可微，若矿是( 1 1 ) 的严格局部最优解，则 v ，( 矿) = o 且u t v 2 ，( 矿) t 正 o ，讹舻 其中，v 2 ，( z ) 表示，( z ) 的h 嘲i 觚，阵 易知当目标函数，是凸函数时，局部最优解也是全局最优解但是事先知道目标 函数为凸函数的情况很少，而且在一般情况下找到全局最优解非常困难所以在非 线性优化里通常认为局部最优解即为所求的解，而在实际的算法中，我们通常是找 到满足局部最优解的必要条件的点，因此我们列出上述的必要条件 牛顿法是求解上述优化问题( 1 1 ) 的古老而有效的方法，该算法成功地利用了h e 踌i a n 矩阵提供的曲率信息，即在找到最优点时需要较少的迭代次数和函数值计算次 数牛顿法的基本思想是在目标函数，( z ) 的极小点矿的近似点z 奄处将，( z ) 二阶泰勒 展开，即 ，( 。知+ s ) g ( 知( s ) = ，( z 七) + v ，( z 知) t 5 + 去，v 2 ，( z 知) s ( 1 2 ) 其中，s = z 一茁七，g ( 蠡) ( s ) 为，( z ) 的二次近似将上式右边极小化，便得 z 七十1 = z 七一【v 2 ，( z 知) 】一1 v ，( z 知) ， ( 1 3 ) 这就是牛顿法迭代公式古典的牛顿法具有如下的迭代形式 z 知+ l = z 七十九，后= 0 ，1 ，( 1 4 ) 2 河南大学硕士学位论文 令夕( z 七) = v ，( z 膏) 和g ( z 七) = v 2 ，( z 知) 分别表示函数，( 功在点z 七的梯度和h e 8 s i a n 矩阵 根据( 1 4 ) 则( 1 3 ) 式也可写成 d k = 一g ( z 知) 一1 9 ( z 七) ( 1 5 ) 当g ( z 七) 稀疏时，牛顿法需要较少的存储量，因而，牛顿法可用于求解当g ( z 知) 稀疏时 的优化问题【6 】然而，牛顿法要求计算目标函数的二阶导数，并且当迭代点远离问 题( 1 1 ) 的解时，( z ) 的h e s s i 觚矩阵可能不正定甚至奇异，此时( 1 2 ) 式可能无解，从而 导致牛顿法失败【6 ，7 】 拟牛顿算法是牛顿法的一种推广它在牛顿法的基础上，随着计算机技术的发 展而产生的一种新型算法牛顿法的优点是成功地利用了h e 龉i 觚矩阵提供的曲率信 息，但另一方面，计算h 嘲i a n 矩阵工作量大，并且有的很难计算，甚至不好求出，而 以拟牛顿方程为基础来构造算法的拟牛顿算法克服了牛顿法的不足它利用目标函 数，( z ) 一阶导数9 ( z ) 的信息，构造出目标函数的曲率近似而不需要明显形成h 嘲i a n 矩 阵同时具有收敛速度快的优点其基本思想是在牛顿法的子问题( 1 5 ) 中用g ( z 七) 的某 个近似矩阵圾取代g ( z 知) 拟牛顿法的一般格式为： 其中也是在点z 七处的牛顿方向： z 七+ l 。z 七十口七如( 1 6 ) 毗= 一五百1 9 ( z 七) ( 1 7 ) 其中a 七是步长，通常由某种线性搜索确定仇是g ( z 知) 的近似，它满足下面的拟牛顿 方程： b 七+ 1 8 蠢= 掀( 1 8 ) 善乓中弧= 9 ( z 奄+ 1 ) 一9 ( z 奄) 8 七= z 奄+ l z 七 拟牛顿矩阵鼠+ 1 的不同的校正公式导致不同的拟牛顿法著名的拟牛顿校正 公式有b r o y d e n 秩一校正公式( 砒) 【4 】，对称秩一校正公式( s r l ) 【4 】，d f p 校正公式【8 】， 3 河南大学硕士学位论文 b f g s 校正公式【9 】 p s b 校正公式【7 】，它们分别由下面这些公式定义： 略，= 风十皆 嘴= 风+ 虹杀案意丛 群= 仇+ 虻业嗡掣一镨赫 砰s = 圾一鬻+ 糕 嘴= 圾+ 虹型掣一锴蹦善 容易看到，d f p ，p s b ，b f i g s ，s r l 校正公式都是对称的，而b 嘲，d e nr l 校正公式 不是对称的如果醒砚 o ，则d f p 和b f g s 公式保持迭代矩阵风的对称正定性，而 其他几种方法不具有这种性质b f g s 公式是颇受欢迎的拟牛顿公式，它具有d f p 校 正所具有的各种性质，大量的数值结果表明b f g s 方法是求解无约束问题的拟牛顿方 法中的最有效的方法之一，它由b r o y d 铋f 1 0 】，f l e t i c h e r f l l 】，g o l d 蛐【1 2 】和s 妇【1 3 】所 提出求解问题( 1 1 ) 的b f g s 方法的算法步骤如下： b f g s 算法 步o 选择初始点z o 舻，初始对称正定矩阵风舻n ，计算梯度夕( z o ) ，令七= ：o 步1 如果夕0 七) = o ，则算法终止否则，令如= 一刀f 1 夕( z 南) 步2 对函数，( z ) 在点z 南处沿着方向如进行某种线性搜索，获得步长a 七，然后令 z 七+ 1 = z 七十n 七d 知计算夕( z 知+ 1 ) 步3 由如下公式计算b 七+ 1 = 风一镗+ 舞 8 上，k s k”s k 喜乓中s 知= z 知+ 1 一z 知，暑_ | b = 9 ( z 知+ 1 ) 一夕( z 知) 步4 令k = k + l ，转步1 b f g s 方法中矩阵风+ 1 满足拟牛顿条件( 1 8 ) 式众所周知，如果凤是正定的，则也 是，在z 七处的一个下降方向计算步长q 知所使用的线搜索通常有如下几种方式 河南大学硕士学位论文 精确线搜索：即鲰满足 口七2a r g 嘞，( z 七十n 也) 此种搜索由于计算量大，所以在实际中很少采用一般采用以下非精确线搜索： w b l f e 线搜索：即a 七同时满足下面的两个不等式 ( 1 9 ) ! ，( 巩佃础) 八) + 叽w o ( 1 1 0 ) 【v ，( 霉k 十q 知d 七) t 以c 您v ，( z 知) r d k 其中伊1 ，c r 2 为常数，满足o 仃l 口l 眈 1 a r m 硒。线搜索：给定6 ( o ，1 ) ，求q 七= m a x ，歹= o ，l ，2 ，】满足 其中p ( o ，1 ) ，( s 知十q 七靠) ，( z 七) + 6 a 知蠢如，( 1 1 1 ) 1 2b f g s 算法 由于b f g s 方法具有较好的数值效果和快速的收敛性，它已成为工程师和数学 家解决最优化问题的一类受欢迎的方法b f g s 方法已有较完善的局部收敛理论【3 ， 9 】其全局收敛性的研究也取得了重要成果，对于求解一致凸目标函数的极小化 问题，p o w e u 【1 4 】证明了b r o y d e n 族( 包含b f g s 方法) 中的d f p 方法当采用精确线搜索 时会终止于唯一的极小值点或者其迭代序列收敛于极值点使用非精确线搜索时， b ”d 和n o d e d a l 【1 5 】证明了b f g s 方法在a r m i j o 线性搜索下求解凸极小化问题的全局 收敛性b y o d ，n o c e d 越和y u a n 【1 6 】证明了除d f p 方法外的b r o y d e n 族方法在w b l f b 线搜 索下求解凸极小化问题的全局收敛性 d a i 【l7 】构造了一个反例已经证明了使用非精确线搜索的b f g s 算法求解非凸极 小化问题时不具有全局收敛性m a u s c a r e n h 嬲【1 8 】证明即使采取精确线搜索b f g s 算法 也不具有全局收敛性然而来自工程中的许多实际问题往往是非凸的研究求解非 凸的优化问题的拟牛顿算法的全局收敛性具有现实的理论意义和实际意义于是在 5 河南大学硕士学位论文 一个较长时间内，人们试图使用较强的附加条件或修正b f g s 方法的结构等手段来 研究b f g s 方法在求解非凸问题时是否具有全局收敛性y u a n 【1 9 】通过修改近似目标 函数的二次模型的匹配条件提出了一个改正的b f g s 算法，并证明了它的全局收敛 性与局部超线性收敛性l i 和f u k 瑚h i 毗在文献【2 0 】和【2 l 】中通过修正b f g s 校正公式 分别提出了修正的b f g s ( m b f g s ) 方法和保守b f g s ( c b f g s ) 方法，并且证明了这两 种方法在使用非精确的w | 0 型线性搜索或舢m i j o 线性搜索时即使求解无约束非凸 最优化问题也是全局收敛的但前者破坏了b f g 8 算法的仿射不变性质，而后者仅部 分地保持这一性质【6 】 1 3 非单调算法 前面都是关于单调b f g s 算法求解无约束优化问题( 1 1 ) 的工作，所谓的单调方法 就是算法产生的函数值序列单调递减，即使得 ，( z 七+ 1 ) o ，6 ，p ( o ，1 ) 及非负整数m ，寻 找步长因子q l | b = m 蹦 a 矿，q p l ，) 使得 ，( z 知十，a 也) 。渤助，( z j b 一歹) + 占矿a 靠如 6 河南大学硕士学位论文 当m = o 时，上丽的非单调的线性搜索变为标准的a 栅唧。型线性搜索非单调技 术的一个好处就是不要求函数值在每次迭代严格减小，从而使步长因子的选择更具 有弹性，即使得步长q 知尽可能的大p a n i e r 和t i t 8 在文献【2 5 】中证明了非单调搜索技术 能避免m 盯a t l 效应大量的数值试验结果表明，非单调搜索比单调搜索表现要好得 多，数值计算也比较稳定【2 6 ，2 7 ，2 8 】总之，非单调算法的特点就是，在算法中并不要 求( 1 1 2 ) 在每一步都得到满足，往往是对于迭代给出一个更宽松的条件，但仍能保证 算法的收敛性 g r i p p o ，l a m p a r i e l l o 和l u c i d i 在文献【2 4 】中也将非单调搜索技术应用到n 唧t l d n 法， 并在假设水平集有界，充分下降条件成立的条件下证明了w t o n 法的全局收敛性 其后，很多人将非单调搜索技术用于求解最优化问题的其它方法l i u 等人提出了一 种非单调的强w b l f b 线性搜索技术【2 9 1 寻找步长因子q 七使得满足 施七+ q 七呶) 。辫他七一歹) + 6 l 口七露故 = i 耀9 ( z 蠹十口知d 知) is 一盯霹9 其中o 6 口 1 文献f 2 9 】同时也证明了p r p 和h s 方法对凸目标函数在上面的非单 调强w b l f b 线性搜索下的全局收敛性最近，h a n 和l i u 在文献【3 0 】中提出了如下的非单 调w b l f 色型线性搜索：寻找步长因子q 七使得它满足 ，( z 七十a 七也) 。要墓，( z 七一j ) 十l q 知靠d 七 怕( z 七+ 口七如) 2 嬲 q ，1 ( 毗j | 如i j p ) 卵毗 其中q ( o ，1 ) ，e 2 ( o ，1 ) ，p ( 一o o ，1 ) h a n 和l i u 并证明了标准的b f g s 方法在上面的 非单调w | o l f e 线性搜索下对凸目标函数全局收敛【3 0 】随后，l i u ，和w e i 【3 1 】在参考 文献1 3 0 】基础上给出了一种修正的b f g s 方法在此非单调的w o 线性搜索下的全局 收敛性。然而，他们的证明都较强地依赖于搜索中的曲率条件和目标函数的凸性 对于非凸函数的非单调线搜索的研究也有一些d a i 在文献f 3 2 l 中讨论了非单调 共扼梯度法，并在【3 3 】中研究了最初的非单调搜索格式，沿着不同行，对于一般的非 7 河南大学硕士学位论文 凸函数分析了非单调线搜索的方法，并对目标函数一致凸时，探测了非单调线搜索 和r 线性收敛性的关系z h a n g 和h a g e r 推广了d 越的工作【3 4 】，提出了一种新的非单调 线搜索的格式选出步长a _ i c = 瓯，h ，其中h 是使得不等式 ，( z 知+ q 七d k ) ( 九+ 鲁忸知9 知d 知 9 ( z 七十q 七d 知) d 七9 ( z 知) d 七 成立的最小非负整数，瓯是初始的试探步长，这里o p l r 他们证明了一 般方法在非单调搜索下的全局收敛性，并对强凸目标函数证明了形戋性收敛速度 8 河南大学硕士学位论文 1 4 本文主要工作和创新点 本文的主要工作是对上述内容做进一步的研究，主要工作如下： 本文将利用l i - f u k u b h i m a 提出的新的拟牛顿方程，使得由此产生的b f g s 型公式 自动保持正定性在此基础上，选择在更弱的非单调的条件下，用于求解非凸极小化 问题时理论上具有全局收敛性和局部超线性收敛性、且数值上具有表现更好的拟牛 顿方法 创新点：方法的全局收敛性所需的假设条件比已有的一般非单调方法的假设 条件较弱 9 河南大学硕士学位论文 1 5 本文所用的记号 实变量 目标函数 目标函数的维数 全体实数组成的集合 全体n 维实向量组成的集合 目标函数，在点z 的梯度 目标函数，的l 五嘲i a n 矩阵 目标函数，的h 嘲i a n 矩阵逆近似 非奇异方阵a 的逆 矩阵a 的转置 矩阵a 的行列式 矩阵a 的迹 矩阵的n o b e m 岫范数 向量的欧氏范数 1 0 双胁依绝船黼晰肤一从州删 第二章非单调m b f g s 算法全局收敛性分析 2 1引言 考虑下面的无约束优化问题： i i l i n ，( z ) ，z 蹰礼( 2 1 ) 求解( 2 1 ) 的单调方法每次均要求函数值下降，即使得，( z 七) ，( z 知一1 ) 成立非单调 方法则不一定要求，( z 知) o ，则存在一个正常数m 使得? 蜒m s 融一“。 ( 2 9 ) 证明：易知序列【z _ i c cc 0 ，对于任意的常数c ，都有0 虻0 c 0 船1 1 根据“的定义，得 s 蚕坑0 l l 夕鼍0 p i i s 七0 2 e p i i s 七1 1 2 ( 2 1 0 ) 1 3 河南大学硕士学位论文 糕器瑙丽3 历可而刮 其中m = 岳证明完毕 下面的一个引理出自参考文献【1 5 】中的引理2 1 引理2 4 2 令序列 z 七 由算法2 3 j 生成对于讹，如果有不等式0 鲰0 成立， e o ，则存在正常量岛，歹= l ，2 ，3 ，使得对于v ，不等式 i i 鼠s t 0 风慷0 ，愚1 1 2 8 毋s i 风0 s 1 1 2 ( 2 1 1 ) 至少成立啤2 】次，其中七 l ，2 ，七 引理2 4 3 定义 他剥2 。蹋哟m 一扎七一m ( 七) 忌 ( 2 1 2 ) 如果，( z 七+ 1 ) ，( z ( 知) ) ，七= o ，l ，对于v o ，则序列，( z ，i ( 七) ) 羊调递减的，其 中z 七c o 证明：从，( z 知+ 1 ) ，( z j l ( j b ) ) ，得 m _ i ( 知+ 1 ) ) 2 。g 当蕊1 ) m m j ) m 缸 。g 虽助m 七一j ) ，他m ) 一 0 。白兰瀚( 动) ，( ( 砷一j ) + 6 瓯( 最的如( 目 = ，( z ( ( 知) ) ) + 妊 ( 后) 蠕詹) d ( 七) 之 ，( z ，l ( 七) ) 十艿a ，l ( 七) 最知) d ( 七) ( 2 1 3 ) 由中值定理和假设2 4 1 有 ，( z ( 知) 十a ，i ( 七) d ( 七) ) =，( z ( 知) ) 十& 伪) 9 ( z ( 詹) ) t d ，l ( 知) + a ( 七) 匆( z ，i ( 奄) + 侈a ( 七) d _ i l ( 七) ) 一9 ( z ( 后) ) t 】如( 知) ，( z 是( 知) ) + a 九( 奄) 9 ( z h ( 砷) t d m k ) 十( a ( ) ) 2 工i i d i l ( 如) 1 1 2 ， 其中p ( o ，1 ) 把上式带入到( 2 。1 3 ) 式，得 a _ i l ( 砷l l | d j l ( 知) 6 2 一( 1 6 ) 9 反七) d _ i l ( 奄) = ( 1 一j ) 嚷知) 玩( 知) 如( 蠹) ( 1 6 ) 仍0 d ( 知) 一 观察最后一个不等式，我们发现它符合引理2 4 2 的形式，表明 a ( 知) ( ( 1 6 ) l ) 尾 所以 q ，l ( 的= 鑫 ( 的p 学= a 引理2 4 5 令序列【z 知) 由算法2 只j 生成对于v 七，如果都有0 鲰0 e 成立，e o ， 则存在一个正常量m i ，使得 州b ) o ，使得对于任意的七1 ，我们有下 面的不等式成立 町沙 ( 2 1 5 ) 引理2 4 7 令序列 z 知) 由算法2 只j 生成对于讹，我们推断下面的不等式 篆一。忠磊椰删h o o ( 2 1 6 ) 威立 证明：令m = 一6 a 知卵如根据引理2 4 3 得 这就说明了 ，( z 1 c + 1 ) ，( z ( 七) ) 一j ， ，( z 七十2 ) ，( z j l ( 奄+ 1 ) ) 一j + 1 ，( 2 ( ) j 9 南+ 1 ， ，( z 七十m ( 知) + 1 ) ，( z ( 知+ m ( 知) ) ) 一p 知+ m ( 七) ，( z ( 七) ) 一p 知+ 仇( 知) ， ，( z j l ( 知+ m ( 七) + 1 ) ) 2 。! ! 萎冀舢，( z 知+ 仇( 知) + l j ) m ( 七) ) 一。爨( 七) 几+ m ( 七) 寸= o ，l 一 1 6 河南大学硕士学位论文 在此，分别选择七= o ，m ( 七) 十l ，( 他一1 ) ( m ( 七) + 1 ) ，得 m ( m ( 埘十1 ) ) 一m j l ( o ) ) 一。忠( 耐( 七) 和 ，( z ，l ( 2 m ( 知) + 2 ) ) 一，( z _ i i ( m ( 知) + 1 ) ) 一o ! ；恕( 七) p 2 m ( 知) 一j ， ，( z ( n m ( 七) + n ) 一，( 。 ( ( n 一1 ) ( m ( 七) + 1 ) ) ) 一o ! ；熙( 七) p h m ( 七) + n l j 对上面n 个不等式进行叠加，得 m m 卅劫叫q 。) ) 一o o ， 。，映。、p 知棚( 知) 一j + o o ， 备。g 蛩风圳动叫 ( 一毋s r ) t 了 = 孕酬2 嘶簖 f j ” _ 三嘶器 f j i 广一” a 三器 r 了” 因此，对于任意的e o ，都存在一个整数伯 o ，使得对于任意的正整数口，我们有 叭，：曼，t 器心忙羔，r 器虬 上面不等式左面的式子是根据几何不等式的性质得到的，因此 c 忙嚣，乳嚣了糕) 1 q ( nq r ) v q 鲁( 餐誓) v q f = r 0 + l ，j 1 r = r o + l ，r 了 事r 黑歹糕 口一一s ：上) f s r 事r 羔了糕 口。! 一s ：上，r s f 丝掣舰 口 再令g _ o o ，我们就产生了矛盾，根据引理2 4 6 可知，存在一个正常量，使得上面不 等式的左面大于等于这个正常量因此我们得到( 2 1 8 ) 式 1 8 河南大学硕士学位论文 2 5非单调改进的m b f g s 算法 在文献删中，z h a n g 和h a g e r 提出了一种新的非单调线搜索的格式，我们应用这 种非单调线搜索的格式给出下面的非单调改进的m b f g s 算法 算法2 5 1 ( 非单调改进的m 日f 琊算法) 步o 给定初始点z o 舻，对称正定矩阵玩，参数o 叩蒯n 锄m 1 ， o p l o 令c ，o = ，( z o ) ，q o = l ，七：= o 步1 如果0 鲰0 = o ，则算法终止，得问题的解z 七否则转步力 步2 给定z 七，风，解线性方程组俾砂计算线性搜索的方向毗 步3 选出步长q 七= 瓯r h ，其中h 是使得不等式 ，( z 七+ q 七d 七) ( x + 口口后9 也， 成立的最小非负整数，哦是初始的试探步长 步4 令z 七+ 1 = z 七十a 七毗根据下面的日阳嘶爹正公式修正风 晰= 仇一鬻+ 鹾s 乏上，七8 奄 s ；暑，孟 其中8 七= z 七+ 1 一z 七，虻由俾砂定义 步5 选定孤【叩嘶n ，协一】，令q 知+ l = 孤瓴十l ，且仇+ l = 饥仇十，( z 七十1 ) ) q 七+ 1 步6 令七：= 七十1 转步j 传统的非单调线搜索方法中没有明确的规则来确定 知的大小，而在很多情况下 算法的数值表现却对参数朋| 0 大小的依赖性很强进而非单调改进的m b f g s 算法，考 虑了怎样更合理地选取参考值的迭代序列，( z r ( 柚) ：= 仇即：对于充分大的七，不等 式满足 s 仇5a 七，其中九= 冬1 ，这个不等式左边的不等号保证了如果搜 索方向是下降方向，则线性搜索最终会成功；右边的不等号保证了算法的全局收敛 这种算法的优点在于解决了传统非单调算法在迭代过程中造成的大量浪费即当 第七个迭代步的参考值，( ( 七) ) = m a ) c 0 o ，对于任意的z u ( 矿) 有下面的 不等式 0 夕( z ) 0 = i l 夕( z ) 一夕( 。+ ) l l m o z z + | i ( 3 2 ) 和 d r g ( z ) d m o d 0 2 ， d 瓣n ( 3 3 ) 2 n 河南大学硕士学位论文 成立特殊的，当z = 瓢时，3 2 和3 3 对于任意充分大的k 都成立我们注意到 8 蚕弧= s 看( 鲰+ l 一鲰) = 8 吾g p l ) 钆m 0 船l | 2 ( 3 4 ) 其中l = z 七十氏船，碗( o ，1 ) 引理3 2 1 在假设3 2 研口幺彳2 成立的条件下，令序列f z 七) 由算法幺l j 生成若z 知 不是稳定点，有i k 0 印成立这时如果我们用钆定义为s 七和风s 七之间的夹角，即， c o s 以= 高一赢 慨5 ， 则存在一个常数n 1 o 使得 0 1 0 肌0 s 以l l s 七| 1 ( 3 6 ) 证明：由假设a 和不等式( 2 7 ) ，我们得到 秒：s 蚕c 0 鲰i i i i s 七0 2 c l | 8 知0 ( 一旅s 七) d 印( 一9 蚕s 七) = c ( 一靠s 知) ，( 3 7 ) 这里c = 侥o 由假设3 2 1 ，我们知道存在一个正常量舰，使得 l i g ( z ) 0 尬( 3 8 ) 假设2 4 2 隐含存在一个正常量 幻，使得| l 夕( z ) 0 毛根据式子( 3 4 ) 、( 3 7 ) 和( 3 8 ) ，我 们得到 尬0 钆1 1 2 0 g 0 1 ) 钆i | i i 观l l = i i 鲰+ 1 一鲰i s 南0 统8 蚕c ( 一s ) = c 0 鲰i l i i 乳i i c d s 巩， 其中s l = z 詹+ 瓦钆，以( o ，1 ) 则( 3 6 ) 成立 引理3 2 2 在假设阻j 和f 矽成立的条件下，令序列t z 七) 是由算法2 3 j 生成，则有 不等式 慨一矿i i ， ( 3 9 ) 七= 0 2 l 河南大学硕士学位论文 成立而且如果我们定义= 仇口z | | z 七一z + 肌8 z 蚪l z 蠡旷 ，则有不等式 ， 七= 0 和 i l 9 9 9_ o 9 9 咖o e + 0 6 3 1 8 7 9 l 0 5 o 6 5 8 3 3 0 b 帖 d i x m a a n al 2 l7 50 0 3 lo 1 舢o e + 0 1o 1 2 7 8 e - 0 口9 4 2 5 7 e - 5 2 23 80 7 9 7 o 1 0 州瑚b + o l0 2 0 0 5 0 4 e - o 2 8 6 l i l e - l 咖 2 56 73 7 8 lo 1 0 0 0 e + 0 lo 2 7 2 6 6 s e - o 4 9 7 7 1 2 e - d i x m a a n bl 3 81 0 0 7 8o 1 o e + o lo 1 3 9 7 l l e - 0 5o 2 3 2 2 3 3 l 蕾0 5 5 5 33 d 22 9 6 9o 1 0 翻0 b + 0 10 1 7 8 1 8 吲b - 0 50 2 4 6 5 4 4 e - 0 5 l o 1 82 22 7 0 30 1 o b + 0 l0 1 8 口0 9 0 e - 0 50 9 8 1 7 4 5 e - d i x m a a n c1 2 62 6 8o 0 7 8o 1 0 e + o l0 枷1 5 4 e - o 8 2 8 5 8 8 e - 5 1 6 65 口8 t0 1 o e + o lo 2 8 翻瑚l 0 50 5 6 “9 5 e - 0 5 l 咖 5 32 4 l1 3 9 5 3o 1 咖e + 0 10 5 0 8 瑚e 0 60 1 3 1 2 1 6 e - 0 5 d m a a n el 14口865o 4 8 40 1 0 0 哦腿+ 0 lb 4 4 s l l 5 b 0 5o 8 8 2 7 1 0 m 5 5 5 7 21 9 9 7 4 9 4 3 80 1 0 0 咖e + 0 10 7 1 0 3 7 6 l k 0 5o 9 8 2 0 5 0 l 0 5 i 咖1 6 3 93 2 5 83 8 2 5 1 6o 1 0 b + o lo 9 1 7 0 2 t l 0 50 9