（应用数学专业论文）拟牛顿法及其收敛性.pdf

障上学位论文 摘要 本文，我们首先提出一种求解单调非线性方程组的正则化的b f g s 算法和l b f g s 算法，在不假设方程组的j a c o b i a t 矩阵非奇异的条件下得到了这两种方法的 全局收敛性这些方法的一个显著优点是迭代点到解集的距离单调递减此外，本 文算法的全局收敛性证明不需要假设方程可微，因而能够用于求解非光滑的非线性 方程组与g a u s s n e w t o n 型b f g s 算法相比较，本文算法中的迭代矩阵的条件数要 小很多而且，所提出的l b f g s 方法适合大规模非线性方程组的求解我们还对 这两个算法进行了数值实验，结果表明它们非常有效 为了求解大型的一般的非线性方程组，基于l i 和f u k u s h i m a 的g a u s s - n e w t o n 型b f g s 公式，我们在第3 章提出了一种非单调的谱梯度方法并建立了算法的全局 收敛性定理本文的方法是求解无约束最优化问题的谱梯度方法在求解非线性方程 组中的一种推广 其次，我们在第4 章提出一种非单调的a r m i j o 线性搜索技术并证明m b f g s 方 法和c b f g s 方法在此搜索下求解非凸函数极小化问题的全局收敛性在不假设迭 代矩阵序列有界的前提下建立算法的全局收敛性定理数值结果表明，采用非单调 搜索的m b f g s 方法比单调的b f g s 方法的数值效果明显要好 在第5 章，我们提出一种求解无约束优化问题的非单调的b f g s 信赖域方法 并证明该方法求解非凸极小化问题的全局收敛性该算法的优点是信赖域子问题的 目标函数是一个严格凸二次函数，因而信赖域予问题的求解相对容易而且，我们 在不假设迭代矩阵序列有界的前提下建立算法的全局收敛性定理在第6 章，利用 m b f g s 割线条件，我们提出一种求解无约束优化问题的下降的非线性共轭梯度法 并证明该方法求解非凸极小化问题的全局收敛性该方法的一个优点是能产生不依 赖线性搜索的充分下降方向 在第7 章，我们提出一种求解二阶锥互补问题( s o c c p ) 的光滑化的b r o y d e n 方 法利用超平面投影方法的思想，我们还提出一种求解s o c c p 问题的投影牛顿法， 在适当的条件下证明算法的全局收敛性 最后我们研究b r o y d e n 方法求解h i l b e r t 空间中半光滑算子方程的局部收敛性 质通过对广义微分引入n 阶半h s l d e r 连续的概念，在一定条件下，我们证明b r o y d e n 方法具有局部的线性和超线性收敛速度 关键词：拟牛顿法；谱梯度方法；非线性方程组；非线性共轭梯度法；非单调搜索， 信赖域方法；半光滑算子方程；非凸极小化问题 博士学位论文 a b s tr a c t h lt h i sp a p e r w ef i r s tp r o p o s ear e g u l a r i z e db f g sn l e t h o da n dl b f g sm e t h o df o r s o l v i n gm o n o t o n en o n l i n e a re q u a t i o n s u n d e rv e r ym i l dc o n d i t i o n s w es h o wt h a tt h e s e m e t h o d sa r eg l o b a l l yc o n v e r g e n te v e ni ft h ee q u a t i o ni sn o ts m o o t ha n di m si n f i n i t e l y m a n ys o l u t i o n s a na t t r a c t i v ep r o p e r t yo ft h e s em e t h o d si st h a tt h ed i s t a n c eb e t w e e n i t e r a t e sa n dt h es o l u t i o ns e ti sd e c r e a s i n gm o n o t o n i c a l l y c o m p a r e dw i t ht h eg a u s s n e w t o nb a s s e db f g sm e t h o d ，t h ec o n d i t i o nn m n b e ro ft h ei t e r a t i v em a t r i xi sm u c hl e s s i no r d e rt os o l v el a r g e - s c a l en o n l i n e a re q u a t i o n s ，b a s e do nt h eg a u s s n e w t o nb a s e d b f g sm e t h o dp r o p o s e db yl ia n df u k u s h i m a w ed e v e l o pan o m n o n o t o n es p e c t r a lg r a d i e n tm e t h o da n dp r o v ei t sg l o b a lc o n v e r g e n c e t h en l e t h o di sa ne x t e n s i o no ft i l es p e c t r a l g r a d i e n tm e t h o df o rs o l v i n go p t i m i z a t i o np r o b l e m s i nc h a p t e r4 ，w ei 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 ea n dd e v e l o pa n o n m o n o t o n em b f g sm e t h o da n dan o n m o n o t o n ec b f g sm e t h o df o rs o l v i n gu 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 s u n d e rm i l dc o n d i t i o n s ，w ee s t a b l i s ht h eg l o b a le o n v e r g e n c eo ft h ep r o p o s e dm e t h o d s o u rn u m e r i c a le x p e r i m e n t ss h o wt h a tt h en o n m o n o t o n e m b f g s c b f g sm e t h o dp e r f o r m sm u c hb e t t e rt h a nt h em o n o t o n em b f g s c b f g s m e t h o dd o e s i nc h a p t e r5 ，w ed e v e l o pan o n m o n o t o n eb f g st r u s t - r e g i o nm e t h o df o rs o l v i n gu 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 s ag o o dp r o p e r t yo ft h em e t h o di st h a tt h eo b j e c t i v e f u n c t i o no ft h et r u s t r e g i o ns u b p r o b l e mi sas t r i c t l yc o n v e xq u a d r a t i cf l m e t i o n c o n s e q u e n t l y ，i ti sr e l a t i v e l ye a s yt os o l v et i l es u b p r o b l e m w ee s t a b l i s hag l o b a lc o n v e r g e n c e t h e o r e mf o rt h em e t h o dw i t h o u tr e q u i r e m e n to ft h eb o u n d e d n e s so ft h eg e n e r a t e dm a t r i x s e q l l e n c e i nc h a p t e r6 ，w ep r o p o s ean o n l i n e a rc o n j u g a t eg r a d i e n tm e t h o df o rs 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 s t h em e t h o di sd e v e l o p e db a s e do nt h es e c a n te q u a t i o n s a t i s f i e db yt h em b f g sf o r m u l aa na d v a n t a g eo ft h ep r o p o s e dc o n j u g a t em e t h o di st h a t a te a c hi t e r a t i o n ，t h em e t h o dg e n e r a t e sas u f f i c i e n td 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 e f u n c t i o n u n d e rm i l dc o n d i t i o n s ，w eg e tt h eg l o b a lc o n v e r g e n c eo ft h em e t h o d w et h e nc o n s i d e rt h en u m e r i c a lm e t h o df o rs o l v i n gt h es e c o n do r d e rc o n et o m - p l e m e n t a r i t yp r o b l e mf s o c c p ) b a s e do nas e m i s m o o t he q u a t i o nr e f o r m u l a t i o no ft h e s o c c p ，w ep r o p o s eas m o o t h i n gb r o y d e nm e t h o df o rs o l v i n gs o c c p u n d e ra p p r o p r i a t e c 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 eo ft h em e t h o d i na d d i t i o n ，b yt i l eu s eo ft h e h y p e r p l a n ep r o j e e t i o nt e c h n i q u e ，w ea l s op r o p o s eap r o j e c t i o nn e w t o nm e t h o df o rs o l v i n g s o c c pa n de s t a b l i s hi t sg l o b a lc o n v e r g e n c e i i i 博士学位论文 f i n a l l y , w es t u d yl o c a lc o n v e r g e n c ep r o p e r t yo fb r o y d e n sr a n ko n em e t h o df o r s o l v i n gs e m i s m o o t ho p e r a t o re q u a t i o n si nh i l b e r ts p a c e w ei n t r o d u c eac o n c e p to fa o r d e rs e m i - h s l d e re o n t i n u i 毋f o rg e n e r a l i z e dd i f f e r e i l t i a lu n d e ra p p r o p r i a t ec o n d i t i o n s ， w ep r o v et h a tb r o y d e n sr a n ko n em e t h o dp o s s e a s e sl i n e a ra n ds u p e r l i n e a rc o n v e r g e n c e p r o p e r t i e s k e yw o r d s ：q u a s i n e w t o nm e t h o d s ；s p e c t r a lg r a d i e n tm e t h o d s ；n o n l i n e a rc o n j u g a t e g r a d i e n tm e t h o d s ；n o n l i n e a re q u a t i o n s ；n o n l n o n o t o n el i n es e a r c h ；t r u s t r e g i o nm e t h o d s ； s e m i s n l o o t ho p e r a t o re q u a t i o n ；n o n c o n v e xm i n i n f i z a t i o n i v 博士学位论文 r 1 ： r 蔓： r ”： 露翌： r “”： a 一1 ： m i n ( x ，y ) m a x ( x ，y ) ”1 1 ： 盱： p 符号表 实数空间 j s 负数金体 扎维实剜向量空间 n 维菲受实刭向量全俸 n 阶矩阵的集合 瓶阵a 的逆矩阵 经意懿， 存在 ，y 孛漱较小静数 $ ，y 中取较大的数+ 钟中的欧凡服得范散 舻孛浆无穷蕊数。 无穷和 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：，司甲每 日期：年厂月苫日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论 文。 本学位论文属于 1 、保密口，在年解密后试用本授权书。 2 、不保密瓢 ( 请在以上相应方框内打“”) 作者签名忍中学 导师签名2 i 一翼麓 7 一w 剀趴“z 匆毛 日期：o 为缶厂月r 日日期：0 为锋6 月b 日 日期 ) 矗严厂月髟日 卤七 、 c 博士学位论文 第1 章绪论 拟牛顿法是求鼹非线性方程组秘无约裘饯纯阉题瓣一类非常窍效黪方法。本文 主要研究求解非线性方獠组和无约柬优化问题及二阶镶互补问题的拟牛顿法及其收 敛毪，将裂讨论b f g s 方法藉b r o y d e n 方法懿全局枝绶洼及它稍懿数值表现在按 下来的几节中，我们介绍拟牛顿法的一些背景和已有结果 1 1 求解非线性方程组的拟牛顿法 设f ：钟一舻是连续可微映射考虑下面的非线性方程组： f ( x ) = 0 ( 1 1 ) 牛镶法是求辩方程组( 1 1 ) 的缀典的方法之一，葜迭代格式为： j + 1 = 掣b + d ，d k = 一f 7 ( 茹) 一f ( 。) ， 其中f 扛) 楚f 在。女鲶静j a c o b i a n 阵牛顿法游一个显著优点勰是其有局部静越 线性甚至二阶收敛速度队由于牛顿法这一优点，使其成为颇受欢迎的算法之一， 然而，强j a c o b i a n 矩阵f 怡k ) 奇异时，牛顿方向可髓不存在克服牛顿法这一缺陷 鲍一令主要途径楚采曩数牛顿法，其基本懋怒是利用菜令矩薄墩痒鸯f ( x k ) 的透 似取代f 怡k ) 拟牛顿法的一般格式为t x k + 12x k + a k d k 、 d k = 一目i 1 f ( 执) ， ( 12 ) ( 1 3 ) 其中0 1 是步长，通常由菜种线性搜索确定b k 是f ，( x k ) 的近叛，它满足下谢的拟 牛顿方程； z k + 1 s = = 执，( 1 4 ) 其中y k f ( g + 1 ) 一f ( x k ) ，乩= z t + l 一k ，注意到y k f ，( 。k + 1 ) & ，闲此， b k + l 与f ( 茹女+ ，) 淤方起龉很接近揪牛顿矩阵最+ ，的不阑酶校正公式导致不露的拟牛 顿法著名的拟牛顿校正公式有b r o y d e n 秩一校正公式( r 1 ) 吐对称秩一校破公式 f s r l 鲻，d f p 校委公式辩，b f g s 校歪公式1 4 1 ，p s b 校正公式等吐它 | 、j 分鞠壶下 颟这些公式定义： b d f p = 鼠+ 蛀型啭掣一锴瓣 b p s b = 墩+ 虻型笔掣一常域； 皤b f 。g k 耻鬻+ 舞； 撼牛顿法及冀收敛性 磷，= 瓯+ 照型8 t s k b s + l r l = 圾+ ( y k - - 西b 了e 二s k l ) 瑟( y 五k 了- - b - k s k ) r + 容易豢到，d r p , p s b ，b f g s ，s r l 校蚕公式都楚对称静，它们邋台求解对称问 题，碟b r o y d e nr 1 校难公式是不对称的，因此它常被耀来求释器对称闻题，始桑 y 舌s k 0 ，则d f p 和b f g s 公式保持迭代矩睡最的对髂正定性，两其它几秘方法不 具有这种性质p s b 校正公式在非线性最小二聚问题中经常被采用b f g s 公式是 颇受欢迎的拟牛顿公式，它具有d f p 校正所具有的各种性质此外，当采用w o l f e 线性搜索时，b f g s 算法对凸极小仡问题具有全局收敛能质，这个性质对于d f p 方 法是否成立海不清楚大量的数值绪果表龋，b f g s 方法的数值效粜优于其它的拟 牛顿方法 拟牛顿法不罴要昵显计算j a c o b i a n 阵，舞辩曝持牛顿法躲挟速l 芟敛羧凄，舀2 0 世纪6 0 年代b r o y d e a 第一次提出求鳃j 线性方程缎静接牛顿法基唑爨其深邃事 富的理论性和实际计算中的有效性，很快受到最优化工侮者鞠计簿数学家的特别海 睐特别是拟牛顿法的局部收敛性得到了广泛的研究，参见文献 1 ，4 6 1 此外，人 们对拟牛顿法求解无约束问题的全滴收敛性分析进行了相当的努力并且取得了巨大 遴糙，其体参觅文献f 5 2 0 尽管拟牛顿法的局部收敛性结果十分丰寓，但是其求解 线性方程组懿全稀枝敛霞睁结果帮裰步垒局纯方法z 川= x t + “t 蟊需要采用 菜釉搜索计笋步长8 ，但是拢时拟夸壤方商一般不黪是菜个嶷量蕊数静下洚方商， 从丽使得线性搜索难以实理或考说怒缺少一静毒效的线炊搜索。 g r i e w a a k 森1 9 8 6 年研究了鳃非线性方程组的b r o y d e n 秩一方法的全鼹收敛蛙， 并在文献 2 1 1 中提出了一种无导数的线性搜索，同时证明了b r o y d e n 方法在该搜索 下的全局收敛性l i 和f u k u s h i m a 在文献f 2 2 1 中构造了个反例表明g r i e w a m k 猩 文献沼1 1 中的线性援索在计算中可熊会产生桀些困难，即该搜索不是适寇的为克 服挖缺陷，l i 耪f u k u s h i m a 键鑫了一种菲革调搜索技术p 2 2 1 ：求步长o 使得 i i f ( x k + n 如) f 1 1 i f ( m ) 1 1 口，l i n k d d l 。十r m i f ( x k ) l l 其中o 1 0 是常数，佻 c o ；在适当条件下，文献f 2 2 】证明了求解非线性方稷 组的b r o y d e n 方法的全局收敛性 关于b f g s 方法求解非线性方程组的第一个全局收敛性结果属于“和p u k u s h i m a + t 9 9 9 年，他们在文献 23 j 中提出了一种新的近似范数下降的b f g s 方法，称之为 g a t m s n e w t o n 黧b f g s 方溘，萁蓣牛顿方向由下面的方禚决定： 玩d + 蟊一0 ， 其中磊= 塑盟拉生a ，：- 纽i 址! 蚴f7 ( 瓢) f ( 善b ) ，展出下面的b f g s 公式校正 一鼠一鬻+ 蓑， 一2 一 其中s 一。盘+ l 一。，蟊一f ( x k + y k ) 一f ( x k ) ，巍= f ( x k 十1 ) 一p ( x ) 。这静g a u s s - n e w t o n 型b f g s 公式不阕予标准的b f g s 公式，霉管它仍然满足菝牛颧方程 四k + 1 8 k = 靠 注意到擞f ( 女+ 1 ) 2 8 ，因此，鼠+ l p ( + 1 ) 2 。鞠应的方法髂之为g a u s s - n e w t o n 登b f g s 方法。2 0 0 3 年，g u 等入萼 入了一种藏数下降的线穗搜索潮，并静i 耀l i 和f u k u s h i m a 求解无约柬优化问题的c b f g s 和m b f g s 方法的思想 1 4 , 2 5 】，撼出了 求解对称非线性方程组的范数下降的保守的和修厩的g a u s s n e w t o n 型b f g s 方法 著置证骥了这两释r 方法全局收敛。 尽警牛顿法帮掇牛顿法都是饕常有效的算法，但是它髓郡需要计算和移德矩 阵，这难以用于求解大激问题最近。c r u z 和r a y d a n 在文献 2 6 提出了一种求解一 般的非线性方程组的非单调的谱梯度方法并证明了其全局收敛性z h a n g 和z h o u 在文麸 2 7 捷囊了一耱浓惩革调菲线犍方程组静遴梯度投影方浃势建立了全鼹收鼗 性结果，这两种谱梯度方法都适合求大规模问题，察实上，这两种谱梯度方法怒求解 无约束优化问题的谱梯魔方法在非线性方程组中的推广谱梯发方法最早是b m , z i l m 和b o r w e i n 提出来的删，其基本思想是甩一个数檄矩阵k j ( 这飘j 是单位矩阵) 代 替熬孛缓矩簿最，英峰| 是下嚣最，l 、铯阉瑟豹薅： m i n i l b b 一抓叭b e r 不难推得，上面问题的解为 壤：擎+ 3 i 壤 谱梯度方法形式简单，适合隶解大獭问题谱梯发方法引起人们的关注应该归功于 r a y d a n 灏过采用g r i p p o 等人的非翠调线性搜索技术【“，r a y d a n 在文献 3 0 1 中证 鳃菲攀调谱梯度方法蛔垒是收敛镶羚豆辑骰的数德实验也获褥了糠入鲍成凌，大 量的数德结果表鳕这种非单调控索下的谱梯麦方法莓至可以与荚轭梯虔法稽秘：狻， 特别是对大型问题更怒如此近年来，谱梯度方法的研究受到了广泛关注，参见文 献 2 8 ，3 1 3 4 羲嚣讨论懿都是荚予羧牛顿法求释蠢潢菲线瞧方程整懿甚露结果。对羧顿法 求解菲光滑方程组静绥果目前并不多觅，雨显大多数研究集中在局部收敛帔分析 上，参见文献 3 5 4 0 l i 和f a k u s h i m a 提出了一种求解与非线性瓦补问题等价的半 光滑方稷组的光滑化拟牛顿法h “，辩证明了算法的全局收敛性+ 同样，通过光滑化 援拳，毛i 瑟f u k u s l g m a 耱交彀鎏2 】b r o y d e n 方法黎绥炎溪方程缀夔全局牧簸骥续暴 推广到了一般的半光滑方程组口“ 1 2 求解无约束优化问题的拟牛顿法 设歹：r n r 遘绥霹徽，g ( x ) 涛f 在z 点鲶瓣臻囊，褰鼹茏终寒捷纯阙怒 m i n ，( z ) ，v z r ”( 1 5 ) 一3 一 拯牛顿洼及其收敛往 的拟牛顿法的迭代与其求鼹 # 线性方程维静格式撵嬲，廷需要将( 1 4 ) 中y k 豹定义 改为 y k = 尊女+ 1 一g ， 其中热是g ( x k ) 的燕写。 拟牛顿法求解无约束优化问题不仅局部收敛性分析取穆r 事硕的成果h “】，薅 且其全局收敛性分析也取得了巨大进展p o w e l l 和d i x o n 证明了b r o y d e n 族方法 在如下精确搜索下求解凸极小化问题时的全局收敛性 1 1 , 1 7 所谓的精确搜索，即求 m 使得其满足 ，( 嚣女十o 魂) 然r a 。) i u nf ( x k + a 矗) b y r d 等人在文献【8 】8 中证明了除d f p 方法外的b r o y d e n 族方法在w o l f e 线性搜索下 求解凸极小化闽题的全局收敛往这里的w o l f e 搜索，指的怒求使得其满足 ，扛+ 呶) 董，( g ) + 5 a k g 手d k 9 扣k + a k d k ) 玎瓤， 其中0 5 口 1 b y r d 和n o c e d a l 证明了b f g s 方法禚a r m i j o 线性搜索下求解凸 极小纯蔺题的全局牧蒙往戮骈谓的a r m 目。控索，即求位= m a x p j ，j = 0 ，1 ，2 ， 满足 f ( x 十d k ) 篓f ( x 女) + 6 a k g d e ， 其中p f 0 ，1 ) 为常数有关搭牛顿法求解髓萄数板，j 、偬蟊趣魏研究还可参觅文献 臣6 ，1 0 ，1 2 2 0 1 d a i 在文漱潮孛构造了一令爱铡表明b f g s 方法在w 醚线性援褰 下对非凸投小化问题不具有全岗收敛性走了璎究拟牛顿法求鼹非凸闷题的众局收 敛性，“和f u k u s h i m a 在文献f 1 4 ，2 5 1 中修正了标准的b f g s 公式，提出了c b f g s 方法和m b f g s 方法并证明了这两种方法在a r m i j o 和w o l f e 线性搜索下对非凸极小 化问磁全局收敛 前面都是美于单调的拟牛顿法求勰无约束问题( 1 5 ) 的工作，所谓的单调方法就 是箨法产生的添数德序魏单清递减，酃使褥f ( x k ) f ( x k - ) 成立菲单谪方法粥不 一定要求f ( x ) 0 ，6 ，p ( 0 ，1 ) 及非负整数膨，寻找步长因子a = m “ 8 矿，a p l ， 使褥 饱 + 矿d d ) s 。驾巍施州) + 驴n 蠢也 ( 1 6 ) 当m 一0h 寸，上面的j s 单调线性搜索变为标准鲍a r m i j o 线性搜索。非肇谖技 术( 1 6 ) 的一个好处就是不要求函数值减少，从丽使步长因子的选取更具有弹性， 即使得步长n m 尽可能的大此外，p a n i e r 和t i t s 在文献 4 2 】中证明了非单调搜索 技术能避免m a r a t o s 效应大量的数值结果表明，非单调搜索比单调搜索数值表现 。4 博士学能论文 要好得多，特别是非单调方法熊求一些比较困难的问题，此外，其数值计算也比较 稳定，参看文献【3 0 ，4 2 4 7 g r i p p o ，l a m p a r i e l l o 稀l u c i d i 奁文献 2 9 中将非单调搜 索技术应用到n e w t o n 法，并程假设z k 乎集有爨，充分下降条终9 d k 墨一c 1 l 驻8 2 及 l | 1 c 2 l l m ij 成立的条件下证明了n e w t o n 法的全局收敛性其盾，很多人将非单 谖攫索接本麓于求解最谯铯闻黻静葵它方法，d a i 在文献瓣8 串讨沦了菲萃谲共辘 梯度法及文献f 4 9 1 中研究了一般的非单调搜索格式z h a n g 和h a g e r 推广了d a i 的 工作，他们证孵了一般方法在菲荤调搜索下的全局收敛佼，并对强凸目标黼数证 嚷了嚣线性收敛速嶷。l i u 等久提出了一种菲单溺的强w o l f e 线。瞧搜索技术 s o l ：寻 找步长因子o k 使得满足 ，( 茹+ n d k ) 篓。m s ，a ! x 。f ( z - j ) + d 。k g t d k 和 j 4 9 ( x , + a k d k ) l 一a d 吾g k ， 箕中0 5 口 0 使褥 l t p ( x ) 一f ( y ) i l 三i l g 一# 弘魄，y 彬，( 2 ，1 7 ) 则由f 的单调性和l i p s c h i t z 性质，我们有 h 1 f ( x k ) l l s t s k 曼妊8 k ( l + h l l f ( x k ) l l ) s ：。( 2 1 8 ) ( i i i ) 鼠的校正公式不同于l i 和f u k u s h i m a 在文献 2 3 】中的g a u s s - n e w t o n 型b f g s 方法由于文献【2 3 j 中的拟牛顿嫩阵鼠十，“( z e + - ) 2 ，因而其条件数会变得很 大，这可熊影响戮它懿毁值稳定愁，鉴予茂，算法2 , 2 1 申戆b k 瓣性鼹要毙【2 3 】 中鼠的性能好 ( i v ) 线性搜索( 2 1 3 ) 不同于文献【7 6 】中的线性搜索由( i i ) ，容易看到算法是适定的 前面我们提劐，拟牛顿法不适合解大型问题。为了克服逸一困难，n o c e d a l 在 文皴 l 饕牵掇鑫了求瓣无终衷爨傀绽瓣蓬懿黪i 谓静毒限记忆数b f g s 方法，簿髂势 l b f g s 方法大量的数值结果表明l - b f g s 方法对大型问题的求解非常有效( 8 ；，删 这稀有蔽记忆彼术最近叉褥鲴了很大发展，参觅文敞i 1 3 ，8 7 9 1 然而，就我们所 知，对于求鳃大型的 # 线性方程组，旋未有耀应的磅究本帮，我们将撼蹬一种求 解单调非线性方程组的l b f g s 方法，这种方法可以看作是l b f g s 方法与超平面 投影方法稚结食戆产锈。 我们先简单的回顾求解无约束优化问题的l - b f g s 方法； 1 2 ， 博士学位论文 考虑无约束优化问题 m i n ，( 动，z r ”， 其中：彤一r 连续可微记v f ( x ) 为，在z 处的梯度文献 8 6 提出的求解上 面最优化问题的l - b f g s 算法如下： 算法2 2 2 s t e p1 给定z o r “，整数m ，对称正定矩阵b o 令k ：= 0 s t e p2 由鼠d k = 一v f ( x , ) 计算d k ，令2 = z k + o d k ，其中o k 满足某种线性 搜索 s t e p3 令佩= m i n k + 1 ，m ) 选取对称正定矩阵日产和单调增加的整数集l = 协，赫1 ) o ，) 用 蛳，拗) 盏1 校正醪m 次，对j = 0 ，伉l ， 计算 带“趔l 絮筹+ 瓣， 其中8 k = + 1 一，讥= v ( x k + 1 ) 一v ，( z k ) 令b k + 1 = b 护，k ：= + 1 转s t e p 对于s t e p3 中的b 1 0 ，其选取方式很多，例如我们可以选取b ? = b o 我们将 算法2 2 2 的思想应用于求解单调非线性方程组，并结合超平面投影技巧，提出一个 求解( 2 1 ) 的l - b f g s 方法其步骤如下： 算法2 2 3 ( l - b f g s 方法) s t e p0 给定x 0 形，蹩数m 0 和常数p ( 0 ，1 ) ，口( 0 ，1 ) ， 0 选取b o = ， 令：一0 s t e p1 按下式计算d b 鼠d k = 一f ( z ) 如果d = 0 ，则停 s t e p2 求“k = p m 使得m m 是满足下式的最小非负整数m 令z k = x k + o k d k s t e p3 计算 ( 2 1 9 ) f ( x k + 卢”d k ) ，d k ) 口卢“i i d k l l 2( 2 2 0 ) k + 1 = z 堡镫播酬 皿。， 1 3 拟牛顿法及萁收敛性 s t e p4 按下面修正的l b f g s 公式计算b + 1 令戒= m i n k + 1 ，n 。取 群”一b o = f 选取一单谪增加整数集l k = j 一- ，赫一l 0 ， 利用 取：s 郝 蓥1 校正b f r h 次，即对一0 ，觑一l ，校正 材，一p 一鬻十舞，髁器强偿。， 【碟， 否则， 其中船= # 州一k ，= f ( x k + 1 ) 一f ( z ) 令b m 日妒，k ：= k + 1 转s t e pl 洼记2 2 。2 ( i ) 算法2 , 2 。3 与2 , 2 1 的区别在于对圾的修正方姣，既s t e p4 不慝，运避文献 1 5 中描叙的逆校征公式计算h k f ( x k ) ，从而得到d k 因而如果凹：0 ) = ，我们不必赢接 存结程诗算巍及甄 ( i l ) 关于b 的校正，我们利用了l i 和f u k u s h i m a 的保哿的校正准则f w 同样，这 种校正的好处楚髓保证玩对任意的都是对称正定的 汹) 令碟+ 1 一( 彰+ 1 ) ，鲣= l 鳋黝，碟4 = j 一拶瓣f 易褥( 2 2 2 ) 黪遂校正公 式如下： 妒： v k ( o “r ( ”帮+ 帮8 f l s j t z ，如架豁b l 碟， 否爨， 同样，如果fl i p s c h i t z 连续，则容易证明钏取吣和圳医1 雌是有界的也就怒存 在常数弘 0 使得 l l 口i l 肚，i i b ；1 f l 冬“( 2 ，2 3 ) ( i v ) 当m = l 时，l - b f g s 方法变为文献f 9 2 】中的无记忆b f g s 公式 ( v ) 易知算法2 2 。3 是适定憋 2 。3 全局收敛性 本节，我们将证明由上节提出的b f g s 方法和l - b f g s 方法的全局收敛性 枣子l - b f g s 方法的证瑟与b f g s 方法具有许多稠儆之处，因貌，我们灵诞明b f g s 方法的收敛性，对l - b f g s 方法的全局收敛性可类似证嚏 下面的引理来自于文献f 7 i | 理2 3 1 设b * 由b f g s 公式( 2 1 5 ) 得到假设对称磁定如果存在正常数 m m 使得对任意的0 ，歉墨鞋壤濮是 器狐麟鲻陬萨瑗2 魏一 则对任意的k ( 0 ，1 ) ，存在正常数反，恳，岛和段使褥不等式 航“s t | | i i b i s 。f | 曼岛1 1 8 。i | ， 岛峪酽曼s j 鼠觑l b | 1 2 1 4 w f 2 2 4 ( 2 2 5 ) 博士学位论文 对 1 ，2 ，k ) 中至少m 卅个指标成立 对每一个k ，我们定义指标集虬和k 如下： 甄= i ti ( 2 2 5 ) 成立) ， k = u 甄 ( 22 6 ) 由于钆一n k 也，如果用也代替s k ，不等式( 2 2 5 ) 仍然成立此外，由( 2 1 2 ) ，我们有 胁i i d k l i | i f ( x k ) l | 胁i i d k l l ， v k k ， ( 22 7 ) 下面的引理来自文献【7 6 引理2 3 2 设f 单调及t ，y 舒满足f ( g ) ，。一y ) 0 令 z + = z 一帮f ( 。) 则对任意满足f ( 孟) = 0 的牙彤，有 ” i i + 一牙| | 2 | | z 一面i | 2 一i i x + 一z 1 1 2 现在我们给出b f g s 方法即算法2 2 1 的全局收敛性定理 定理2 3 1 假设f 单调且l i p s c h i t z 连续，假设方程组( 2 1 ) 的解集非空， z k ) 由 b f g s 方法产生，则对任意满足f ( i ) = 0 的i ，有 。+ l 一面0 2sl i 。一牙1 1 2 一l i 搿+ l x k i l 2 特别， z *