（应用数学专业论文）有界变量约束非线性优化问题的仿射共轭梯度路径法及其应用.pdf

中文摘要 摘要 本文主要讨论利用仿射内点离散共轭梯度路径解含有有界变量约束的非线性优化问 题，以及对于解无约束非线性方程组的应用。 共轭梯度法是最优化中常用的方法之一，它具有运算简便、只需一阶信 息，以及存储空间小等优点，共轭梯度法己成为求解大规模问题的一种主要方 法。b u l t e 挑与a l 在【1 】中构造了无约束最优化问题的共轭梯度路径，其基本思想是将 标准共轭方向法应用于无约束优化目标函数，的局部二次近似模型，得到一组共轭方向 序列，共轭梯度路径定义为该共轭方向序列的线性组合，该路径关于共轭梯度路径中的 参数r 连续。然而连续的共轭梯度路径需要先构成整个共轭梯度路径，再进行搜索，以使 计算工作量增加，同时，也可能导致构造路径的困难。本文将避免此困难，减少计算步 骤，使用离散化路径来解有界约束的非线性优化问题。理论上只需构造部分共轭梯度法 解每次迭代的近似二次模型，从而提高了算法的运行效率。特别对于解大规模的优化问 题，具有相对优越性。 c o l e m 觚和l i 在【3 】中对有界变量约束非线性问题提出“双信赖域”方法，构造一个仿 射变换矩阵克服了有界约束带来的困难。本文将借鉴其思想，通过引进一个仿射变换矩 阵，将有界约束优化问题转化为无约束优化问题，进而得到相应无约束问题的牛顿迭代 格式，通过构造预条件离散的共轭梯度路径解二次模型获得预选迭代方向，结合内点回 代线搜索获得下一步的迭代。在合理的假设条件下，算法具有整体收敛性和局部超线性 收敛速率。数值结果表明算法的可行性和有效性。 帆g a 与r h e i n b o l d t 在f 1 3 】对多元非线性方程组的迭代解法做了较系统地介绍。本文建 立了非线性方程组的价值函数，并考虑其在每个迭代点的近似线性模型，利用第二章算 法设计的基本思想对无约束非线性方程组加以分析应用，结合非单调线搜索技术提出了 相应的共轭梯度路径算法，在合理的假设条件下，算法具有整体收敛性和局部超线性收 敛速率。数值结果表明算法的可行性和有效性。 关键词：共轭梯度；预条件；仿射变换；线搜索；非线性方程组；非单调技术；整体收 敛性；局部收敛性。 第1 页 英文摘要 a b s t r a c t bt 1 1 i sp a p e r w ep r 叩o s ean e wa p p r o a c ho f 缅n es c a l i n gi n t c r i o rd i s c r e t ec o n j u g a t eg m d i e n t p a t i lf ；d rs o l v i n gb o u n d c o n s t r a i n e dn o n l i n e a r0 p t i i i l i z a t i o n ，觚di t sa p p l i c a t i o n st 0u n c o n s 缸试n e d n o n l i 鹏缸s y s 锄i l s c o n j u g a t eg r a d i e n tm e n l o d ，w 1 l i c hc 强b ee 懿i l yc o m p u t e da n dm e r e l yr e q u i r e st h ef i 飓to r d e ri n f o m a t i o nw i t i ls m a l ls t o r a g e ，i so i 屺0 f 吐l em o s tp o p u l 盯m e m o df b rs o l v i n gl a 略e a l e o p n i i i i z a t i p r o b l e m s b u l t e 孤强d a l 【1 】f ；删ac o n j u g 眦删i e n tp 础o fl l i l c o n s 删 o p t i i i l i z 撕o n r 1 1 l ep a t l li sd e 矗n e d 舔l i 北缸c o m b i n a i i o no fas e q 眦n c eo fc o n j u g a t e 拙e c t i o n s w h i c ha 陀0 _ b t a i 】呛db ya p p l y i i 培s t 如d a mc o n j u g a t ed i r e c t i o nm e m o dt 0a p 班血a t eq u a d 【m t i c m o d e l0 f 眦c o n s t r a i n e d0 p t i n l i z a t i o n ，1 1 l i sp a mi sc o n t i n u sw i mr e s p e c tt 0t h ep 础m l e t e rr i n l ec o n j u g a t eg r a d i e n tp a t l l b u tt h ec o n t i i m o u sg r a d i 髓tp a mn e e d st 0f 嘶nt h ec n 血ep a t l l i i r s t ，锄dt 置l e nt 0 a r c h ，w l l i d hw i ui i l c r e a 舱t l l et o t a lc o m p u t a t i o na n dm a y r e s l l l ti nt i l em m c l l l 哆 0 fc o n s 仇l c t i l l gt l l ep a 1 i nt l l i sp a p e r ，d i s c r e t ep a t l lw mb e 惦e df 0 rs o l v i n gb 0 帅dc o n s 缸撒d n o n l i n e a ro p t i m i z a t i t 0a v o i dt l l ed i 伍c l l l t y 锄dr e d u c et l l ec o m p u 僦o n t h e o r e t i c a l l y w e0 1 1 l y n d st 0c o n s 伽1 c tp a no fn l ec o n j u g a t eg r a d i e n tp a mt 0s o l v et h ea p 讲幽a t eq u 砌眦f h n c t i o n a te v e 哆i t e r a t i o ns u c ht h a tt h ee 伍c i e n c yo ft h ea l g 嘶t h mi sg r e a t l yi m p r o v e d i th 邪r e l a t i v es u - 耐嘶哆e s p e c i a l l yt 0t h el 嘴es c a l e0 p t i m i z a l i p m b l e m c o l e m 蛆锄dl i 【3 】p r o p o dt h ed o l l _ b l e - t r i l s tr e 酉o nm e t l l o df b rt h en o n l i i l e a rm i n i m i z a d 伽 s u b j e c tt 0b o 吼d s ，如do v e o m et h ed i 伍c m 哆i i n p o s e db yt l l eb 吼m dc o n s n 面n t sv i ac o n s t n l c t _ i n g 锄a 伍n es c a l i n gm a t r i x f b l l o w i n gt l l i si d e a 卸a 伍s c a l i n gm a n 奴i si n 劬c e d i n0 r d e r t 0 缸蛆s f 咖lt h eb o u n dc o n s 砌n e d0 p t i i i l i z a t i o nt 0u n c o n s t m i n 酣0 p t i i i l i z a 廿o n ，c o n s e q u e n yw e g e tt i l en e 讯i 讼撕衄0 f t l l i su n c o n s 昀j j l e d 咖b l e m w | eg e t 龇i t e r a t i v ed i i 优t i o nb y l v i n gq u a d r a l i cm o d e lv i ac o 璐t r i l c t i n gp r e c 伽d i t i o n e dc o 面u g a t eg r a d i e n tp a t l l c 伽n b i n i n gi n t e r j 衙 b a c l 【扛粥t i n gh 鹏s e a r c h ，w e0 b t a i nm en 既ti 衙a t i o n g 1 0 b a lc 0 肼e 唱e n c e 粕dk a ls u p e r l i r 圮盯 c o n v e r g e n c er a t e0 ft h ep r o p o s e d 如嘶n 皿a r ee s t a b i l i s h e d s 0 玎1 e 飑a 鼬l ec o n d i t i o n s 0 r t e g aa n dr h e i n b o l d ti n l d u c c dt l l ei t e f a l i v e 烈砸o fn 池盯e q u 撕o n s i ns e v e r a lv a f i a b l e si n 【1 3 】s y s t e m a t i c a l l y h lt i l i sp a p e r w ec o n s m l c tt 1 1 em 耐tf u n c n o n0 fn o n l i n e a re q l l a t i o 螨， 锄dc o n s i d e rt h ea 讲舶强i m a t el i 缸n 川e lo fe a c hi t e r a t i v e 砸n t a c c o r d i i l gt ot l l ei d e ao ft h e a j g 嘶t l l md e s i 印e di nc h a p 衙2 ，w ec o n s i d e ri t sa p p l i c a t i o n 的n o n l i n e a re q u a t i s ，柚d 哪 n l ec o i l j u g a t eg r a d i e n tp a m a l g o r i t h mc o i n b i l l i n gt l l en o m i l o n o t o n el i n e a r c ht e c h n i q u e g 1 0 b a l c o m 伦r g e n c ea n d1 0 c a ls u p e r l i 鹏a rc o m r e ：r g e n c er a t e0 ft i l ep r o p o s e da l g o r i m ma r ee s t a b i i s h e do n s o m e 陀淞o m 山l ec o n d i t i 伽s n u m e r i c a le x p e r i m e n t ss h o wt l l ee 压t i v e n e s s0 fm ea l g o r i m m 第1 i 页 英文摘要 k e yw b r d s ：c o n j u g a t eg r a d i e n t ；p r e c o n d i t i o n ；a f j f i n es c a l i n g ；l i 舱s e a r c h ：n o l l l i n e a re q u 撕o n s ； n o 衄o n o t o n e 妣h i l i q u e ；g l o b a lc o m 吲曙e n c e ；1 0 c a lc o n v e 略e n c em t e 第页 主要符号对照表 渺 渺m l i i i ，0 i i z 4 ( z ) 9 ( z ) v 2 ，( z ： d ( z ) 主要符号对照表 n 维实向量空间 7 l m 维实矩阵 1 1 2e u c l i d 范数 o o 范数 约束优化问题在可行点z 处的等式约束指标集 入，p ，i ， l ( z ，p ，王，) f ( z ) p ( z ) q i n t ( q ) z 缸 z 矿 ，z ； 肌 q 知 几 约束优化问题在可行点z 处的不等式约束指标集 约束优化问题在可行点z 处的有效集 ，在z 处的梯度，即v ， ) ，在z 处的h e s 阵 尺度矩阵 l a 伊锄g e 乘子 约束优化问题的i 嗣g 均n g e 函数 非线性映射号妒一驴 j 嬲0 b i 锄矩阵 可行集 严格可行集 有界约束下界，上界向量 非线性方程组的精确解或极小化问题的k - k - t 点 向量z 的第t 个分量 第七步迭代点及其迭代点的第t 个分量 第七步搜索方向 第七步线性搜索因子 残量序列 第七步仿射矩阵 第1 v 页 致谢及声明 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研 究成果论文中除了特别加以标注和致谢的地方外，不包含其他 人或机构已经发表或撰写过的研究成果其他同志对本研究的 启发和所做的贡献均已在论文中做了明确的声明并表示了谢 = 亡匕 思 作者签名： 谳窀 第3 7 页 日期：川心哆 致谢及声明 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规 定，即：学校有权保留送交论文的复印件，允许论文被查阅和借 阅；学校可以公布论文的全部或部分内容，可以采用影印、缩 印或其它手段保存论文保密的论文在解密后遵守此规定 作者獬：嘶刷磁各 第3 8 页 日期：枷哆 第一章最优化理论基础 第一章最优化理论基础 1 1 最优化问题简介 最优化问题是在许多可行方案( 决策) 中挑选最优的方案( 决策) 。最优化理论与方法是 研究如何从实际问题的众多方案中选取最优方案的一门学科。近年来，随着电子计算机 的普及以及优化计算方法的迅速发展，它在工农业生产、交通运输、金融、管理、通讯 等众多领域的实际应用日益广泛。为应用最优化技术确定最优的方案，需要针对具体的 实际问题建立相应的最优化模型，再根据模型的具体形式和特性来选择适当的最优化方 法去求解。 最优化问题的数学模型一般形式为： m i n ，( z ) 8 t c ( z ) = 0 ，l ， q ( z ) 0 ，t z ， 其中，：渺_ 验1 ，c ：舻一跪1 ，z 舻称为决策变量，( z ) 称为目标函数，c ) 是约 束函数，和z 分别是等式约束的指标集 l ，2 ，m ) 和不等式约束的指标集 m + 1 ，m + 2 ，计。定义集合q 为 q 些 zic ( z ) = 0 ，i ；q ( z ) o ，i z ， ( 1 1 2 ) 则称q 为可行域。若z q ，则称为可行点或可行解。当要求不等式约束等号不满足时， 可行域成为”严格可行域”，即( 1 1 1 ) 的严格可行域为： i n t ( q ) 墼 zic ( z ) = o ， g ；q ( z ) o ，i z ) ( 1 1 3 ) 对于一个可行点z ，所有的等式约束都被认为是有效约束。考虑不等式约束c ( z ) o ，如果有q p ) = o ，就称约束q ( z ) o 在点z 是有效约束或起作用约束；如果有c ( z ) 0 ，就称不等式约束c ( z ) 0 在点z 是无效约束或不起作用约束。如果所有的不等式约束 都是不起作用约束，就称。是可行域的内点。 若模型( 1 1 1 ) 中不含约束条件，即q = 舻，称模型( 1 1 1 ) 为无约束优化问题。若模 型( 1 1 1 ) 中含有约束条件，即称模型( 1 1 1 ) 为约束优化问题。 若模型( 1 1 1 ) 的目标函数， ) 和约束函数q ( z ) “= 1 ，2 ，p ) 均为线性函数时，则称模 型为线性规划。当目标函数和约束函数中至少有一个是变量z 的非线性函数时，模型称为 非线性规划。 第l 页 1 2 最优牲条传 1 2 最优性条件 最优性条件是指最优化问题的最优解所必须满足的条件。常用的是一阶必要条件和 二阶必要条件。最优性条件不仅对于最优化理论的研究具有重要意义，而且对最优化算 法的设计和终止条件的确定起重要作用。 定义1 2 1 设甄q ，4 ( 甄) 是起作用约束集，如果或者所有的 c 。) ，i 4 ( 以) ) 都 是z 的线性函数，或者 v q ( 巩) ，t 4 ( z 。) ) 线性无关，则称问题( 1 1 1 ) 具有线性无关约束 品性。 为了更方便地讨论约束优化问题的局部极小点的最优性条件，我们引入约束优化问 题( 1 1 1 ) 的拉格朗日函数： ， l ( z ，入) = ，( z ) 一九c ( z ) ， ( 1 2 1 ) t = 1 其中a 称为拉格朗日乘子。 下面我们先给出最优解的一阶必要性条件。 定理1 2 1 ( 【2 5 】) 设文q 是问题( 1 1 1 ) 的局部最优解，若在文点线性无关约束品性成立， 则存在向量k = ( a ：，埋) t ，使得 v 霉l ( 氟，九) = o ， ( 1 - 2 2 ) k20 ，i 五 ( 1 2 3 ) k c ( 文) = o ，i z ( 1 2 4 ) 定理1 2 1 通常被称为k a n l s h k u l l n - 1 k k e r ( 简称k - k - r i ) 定理，( 1 2 2 ) 一( 1 2 4 ) 称为问 题( 1 1 1 ) 的一阶必要性条件或k - k t 条件。满足此条件的点称为k l l t l n ，n l c b r 点或k k - t 点。( 1 2 4 ) 式称为互补松驰条件。如果对任意i z ，砖和q 0 。) 中有且只有一个取零值， 则称为严格互补松驰条件成立。 由定理1 2 1 可知，无约束最优化问题的一阶必要性条件可描述为 v ，( 文) = o 下面我们给出最优解的二阶必要条件定理。 定理1 2 2( 【2 5 】) 诳。q 是最优化问题( 1 1 1 ) 的最优解，且函数，( z ) 与q ( z ) ，t = l ，2 ，p 二阶连续可微又设定理1 2 1 中的约束规范条件在点文成立，从而存在拉格朗 日乘子向量九使k - k _ t 条件成立如果严格互补松弛条件在z 。成立，则： s t v ：2 三( z 。，a 。) s o 对一切满足 s t v 白( z 。) = o ，t 4 ( z 。) 第2 页 第一章最优化理论基础 的方向s 均成立 最后，给出最优解的二阶充分条件定理。 定理1 2 3 ( 【2 5 】煅最优化问题( 1 1 1 ) 的函数，( 。) 与c ( z ) ，z = 1 ，2 ，7 n 均二阶连续可 微，在可行点以处定理1 2 - 1 的约束规范条件成立，若存在拉格朗日乘子向量凡使k - t t 绦件和严格互补松弛条件成立，且对所有满足 s t v c i ( z 。) = o ， a ( z 。) 的非零向量s 有 s t v 乙l ( 双，九) s o ， 则z 。是问题( 1 1 1 ) 的一个严格局部最优解 1 3 最优化方法的结构 求解问题( 1 1 1 ) 通常是通过求其k k - t 点的途径得到它的最优解。一般采用的是迭 代法。其基本思想为：给定一个初始点z o 舻，按照某一迭代规则产生一个迭代序 列_ z l | b ) ，使得当 ) 是有限点列时，其最后一个点是k k t 点；当 瓢是无限点列时，它 的任意一个聚点是k - k t 点。 最优化问题求解的基本迭代格式如下： 算法1 3 1 ( 最优化方法的基本迭代格式) 1 给定初始点z o ，七卜0 2 按某一规则确定搜索方向m 3 确定步长q 七使目标函数有某种意义下的下降 4 取下一个迭代点z 詹+ 1 = 瓢+ a 印七 5 判别z 七+ 1 是否满足终止准则若满足，则停止迭代，z 七+ 1 是近似局部最优解；否 则，七卜后+ 1 转第2 步 在以上迭代格式中，关键的两步是构造搜索方向m 和确定步长q 七。不同的构造方 向孤和确定步长q 七构成了不同的算法。线搜索策略和信赖域策略是保证最优化方法整体 收敛的两类技术。一个好的算法应具备的典型特征是：迭代点能稳定地接近局部极小 值点z 。的邻域，然后迅速收敛于文。因此，评价算法优劣的标准之一是由它产生的迭代 序列 瓢) 的收敛速度。设序列 ) 在某种范数意义下收敛于文，即 。l i ml l z 七一氟0 = o ( 1 3 1 ) 若存在实数q 0 及一个迭代次数七无关的常数g 0 ，使得 熙锹钆 ( 1 3 2 ) 南一o ol i z 七一z l l a 。 第3 页 1 4 预条件共轭梯度法 则称算法产生的迭代序列 飘 具有q q 阶收敛速率。特别地， ( 1 ) 当a = 1 ，l 口 o 时，迭代点列 z 知) 叫做具有q - 线性收敛速率： ( 2 ) 当1 o 时，迭代点列 瓢) 叫做具有q 一二阶收敛速率。 另一种收敛速度是冗一收敛速度( 根收敛速度) ，即设 如果冗1 = 0 ，则称是b 超线性收敛于双；如果0 冗1 1 ，则称孤是冗线性收敛 于双；如果r l = 1 ，则称是r 次线性收敛于孔。 类似地，如果疡= o ，则称是冗超平方收敛于文；如果0 o ，预条件矩阵m ，锄= 日知+ 6 ，解m 珈= 卯得殉， 令伽= 一珈，七：= o 。 步2 如果鲰s ，停止。 步3 计算 钒2 蒜， z 七+ 12z 七+ 口脚， g k + l = g k + q k h p k ， 解m 可= 鲰+ l 得纨+ 1 ， 反= 警，鳙娠 孤+ l = 一纵+ l + 岛挑， 步4 令七：= 七+ 1 ，转步2 。 如果m = j ，则预条件共轭梯度算法就是标准的共轭梯度算法。 1 5 非线性方程组背景介绍 熙_ 蓊 1 5 非线性方程组背景介绍 其中 g = 1 ，2 ，礼) 是定义在n 维e u c l i d 空间渺中开域d 上的实值函数。若用向量记号， 令 砟，皑卜 f ( z ) = 0 这里f 表示定义在舻中开域d 上的非线性向量函数，记为 f ：dc 驴- 咿 0 = ( 1 5 1 ) 若存在z 。d ，使f 0 。) = 0 ，则双成为方程组( 1 5 1 ) 的解。非线性方程组的迭代解 法就是研究寻找方程组( 1 5 。1 ) 的解文的方法及有关理论。 非线性方程组问题早在七十年代便在理论上和数值解法上有了大量的研究， 在吼e g a 与i 池e i n b o l d t 的书【1 3 】中，已做了较系统地介绍。但是，由于非线性方程组求 解问题无论在理论上还是解法上都不如线性方程组成熟和有效。因此，对非线性方程组 解的存在性及寻找有效的数值方法均存在很多问题，需要进一步解决与研究。 一般地，解非线性方程组的迭代法有牛顿法、牛顿型迭代、割线法、拟牛顿 法、l e v e n b e r g m a r q u a r d t 方法等，详见( 【1 3 】，【2 6 】) 。 全文分为四章。第一章简要介绍了最优化的一些基本概念。第二章研究了有界约束 的非线性优化问题仿射共轭梯度路径解法，给出了相应的算法并且在合理的假设条件 下，证明的算法的整体收敛性和局部超线性收敛速率，相应的数值结果表明了算法的有 效性。第三章借鉴上一章中算法设计的基本思想，结合非单调线搜索技术，对无约束非 线性方程组设计了相应的算法并给出了相关的收敛性证明，数值结果表明了算法的可行 性和有效性。最后，第四章对本文的工作进行了总结并提出了进一步的研究方向。 第6 页 第二章有界约束非线性优化问题的仿射共轭梯度路经法 第二章有界约束非线性优化问题的仿射 共轭梯度路径法 2 1引言 本章研究含有界变量约束的非线性优化问题 m i i l ，( z ) ，z q( 2 1 1 ) 这里，：舻_ 虢是光滑的非线性函数，可行集q 些 z 舻| f z 牡) ，并假设非空。其 中l ( 跄u 一o o ) n ，t ( 蹰u + o o ) n 。记，和分别为扎维向量z ，z 和t 的第 个分 量，满足f 。严格内点可行集i n t ( q ) 些和舻i f z u 。 文献【3 】中提出用双信赖域仿射内点法解问题( 2 1 1 ) ，而文献【2 1 】中使用共轭梯度法解 信赖域子问题获得连续路径，结合线搜索的方法解问题( 2 1 1 ) 。然而连续的共轭梯度路 径需要先构成整个共轭梯度路径，再进行搜索，以使计算工作量增加，同时，也可能 导致构造路径的困难。本文将避免此困难，减少计算步骤，使用离散化路径来解决问 题( 2 1 1 ) 。理论上只需构造部分共轭梯度法解决每次迭代的近似二次模型，从而提高了算 法的运行效率。特别对于解大规模的优化问题。具有相对优越性。 问题( 2 1 1 ) 的拉格朗日函数为： c ( z ，p ，) = ，( z ) 一，( z z ) 一尸( u z ) ， ( 2 1 2 ) 其中拉格朗日乘子p ，舻。对于文是局部最优解的一阶必要条件为：存在以，以渺， 使得以下方程成立： i 乳一p 。+ 以= o ，p 。，玖o ， 解( f 一乳) = o ，巧( t 一以) = o ， i - f 双饥 o ，当= f 时， = o ，当驴 z ： 时， o ， 当z ：= 时。 ( 2 1 3 ) ( 2 1 4 ) 并称z 。为问题( 2 1 1 ) 的稳定点，其中矿( z ) 为目标函数的梯度夕( z ) 磐v ，( z ) 的第i 个分量。 第7 页 现在定义向量函数( z ) ：舻_ 舻，其第i 个分量定义如下： i 一，当( z ) o 。选取一个对称矩阵风= v 2 ，( z o ) ，初始可行点跏【f ，】舻，令七= o ，转主步。 主步： 1 计算 = ，( 钆) ，鲰= v ，( 孤) ，风，仇，瓯，风，尥= d 蚕仇= d 2 a 2 如果0 矾0 s ，则停止计算，作为最优解；否则转下一步。 3 置铷= 0 ，r o = 鲰，地即= r o ，而= 一s o = 一嵋1 鲰，置i 卜0 。 4 检验 露风也 o ， d i l n 0 ， 若( 2 2 1 ) 和( 2 2 2 ) 式都满足，转下一步，否则转步6 。 5 计算 、 呓s 2 币丽 + l = 仇+ 九盔， 瞻l = n + 九风也， 氛+ l = n + l ， 屈+ 1 ：毕， n 1s 反+ l = 一s 件1 + 屈+ 1 画 检验 ，( z 七) 一，( z 七+ 钉+ 1 ) 【，( z 七) 一妒知( 忱+ 1 ) 】 若( 2 2 3 ) 式满足，置i 卜t + l ，转步4 ，否则转下一步。 6 置伽卜而，矶= 仇。( 这里m 为搜索方向) 。 7 选取口= l ，u ，u 2 ，直到下式成立 ，( z 七+ q m ) ，( z 七) + p 嘲， 并且+ 咖p ，叫 记第一个满足上式的q 的值记为q 七。 第9 页 ( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) ( 2 2 5 ) 2 3 算法的理论分析 8 令 址 淼，嚣吼艇( f ，吼 其中口知( 仇，1 1 ，0 o ， 所以( 2 3 4 ) 式成立。 瞬1 吩+ 1 = ( 一易+ l + 传+ 1 呜) t + 1 = 一曩1 + l = 一咯l 蜂1 勺+ 1 从而( 2 3 5 ) 式成立。 以下三个引理说明共轭梯度路径的单调递增性，二次函数的单调下降性以及相应的 充分下降条件。 引理2 2 r j j 设是由算法第5 步产生的迭代点列，则 i i 帆 o ，所以 从而 i = oi = o j l歹一l 哆尥吗= ( 九哦) t 尥略= 九毋由 o ， i = 0= o i + l i = 咯。尥+ l = ( + 呜) t 尥( + 奶) = 吃m 姻 + 2 入5 吃m k 屯+ 遐电m 姐 l l 仨，因为当巧o 时，哆彤= 巧岈1 吩 o ，巧凰西 o ，而 = 2 ，手嘭+ 哆朋i 1 勺= 2 孝由一巧吩= 碍喀+ 巧( 砌一吩) 第1 2 页 ( 2 3 6 ) ( 2 3 7 ) 第二章有界约束非线性优化问题的仿射共轭梯度路径法 j 一1 = 哥而+ 巧( 内一内一九日k 也) = 碍d j = 一霹慨呜 o ， i = o 由引理3 1 中预条件共轭梯度的性质可得 ( 吻+ 。) 一侬( ) = 鲧( + ，一) + 丢咯。风阱。一丢t 8 r 凰 所以( 2 3 7 ) 式成立。 沁最d j +吉( 九也) t 凰九哦一喜( 九吨) t 风九d 1 ，j 1 j l，一i 。t = o讧0。i = o讧o 1 = b 最d + 毛碍d j h k d j = 禹蠢略+ 三描 = 掣铲姐2 瓣瓦r u 引理2 3 r j 臃关于歹单调下降，即 夕蚕+ l 夕吾，o 歹n 七一1 夕毒+ l 绒，usjsn 七一1 但，靠m 满足充分下降方向，即有下式成立 9 如南s 一8 玑0 2m i n 1 ，知) ( 2 3 8 ) ( 2 3 9 ) 证明 f ，j j 夕吾+ 1 一鲧= 鳍( + 1 一) = 鳍而= s 2 l 磊嘞= 一瑶慨略 o ，所以 翻f + l o ，则 由( 1 ) 知 综上所述 函膏= 靠伽= 靠南= 一靠岈1 鲰= 一0 玑| 1 2 - 靠口= 知露幽= 一知| i 玑1 1 2 锨= 靠吻 露秽，= 一划训2 ，鲧m = 鳙吻 o ，则 一班( 口。) = 一知靠d ；0 一丢入3 舔风而= 知( 靠蜂1 鲰一三鳍峰1 鲰) = 三知靠蜂1 9 知= 鲁l l 矾1 1 2 再利用( ) 的单调下降性可得： 一溉) 一慨( t ) = 鲁i l 巩1 1 2 综上所述，( 2 3 1 0 ) 式成立。 2 4 整体收敛性与局部收敛速率 本节将分析算法的整体收敛性，需作如下假设： 定义2 1如果对于z q 的每个分量，有下式成立 夕。( z ) = 0 = 争r o ，使得对于所有的忌有 i i 矾f i s ，( 2 - 4 4 ) 而 ，( z 知+ 口知p 七) ，( z 膏) + 胆知蘸_ 七，( z 知) 一雕七| i 玑1 1 2m i n l ，k ) ( 2 4 5 ) 由于 ，( ) ) 单调下降有下界，故，( ) 收敛。由上式可得， 。l i mq 豇i l 玩1 1 2 血n 1 ，知) = 0 由假设知，存在翻 o ，使得0 巧10 恸，从而 l 一碍s o 一 鳍蟾1 鲰 、 i | 矾f 1 2 、 1 2 蕊2 雨晤喊斫丽2 丽孤菰瓣2 而 由( 2 4 4 ) 和( 2 4 6 ) 有 h m 舭= 0 露+ 如果口奄由( 2 2 4 ) 决定，则 ，( 钆+ 詈矶) 一，( 瓢) p 詈夕勋七， 因 ( 2 4 6 ) ( 2 4 7 ) ( 2 4 8 ) ( 2 4 9 ) ，+ 詈p 七) 一，( 孤) = 詈嘲+ 詈z 1 b ( + 亡詈矶) 一夕( ) 】南蹴 詈勘+ 鲁( 詈) 2 | i 矶1 1 2 ， ( 2 4 1 0 ) 其中岛为9 ( z ) 在( z o ) 中的l i p c l l i t z 常数。 由以上两不等式得 q 七膂坐迎紫趔 亿4 m ， 第1 5 页 2 4 整体t 故敛性与局部收敛速率 上式取极限，则有熙i i 矾1 1 2m i n 1 ，) = o ，矛盾。 如果讯由边界约束( 2 2 5 ) 决定，设双是孤的一个收敛点，则存在一个子集x 1c 七) ， 满足 魏x 。a ：= o ，壤x 。孤2 ( 2 a 1 2 ) 故存在某一个指标歹，满足m a x 尹，手) = o 。因此，由注释( 1 ) 对q z 的定义知，可以 找到一个子集x 2cx l 使得 j i 哩m a x 孥，掣) ：o ， ( 2 4 1 3 ) 七。堍x 。一守，守划， ( 2 4 j 3 ) 不失一般性，假设一= o 。 ( a ) 若玩 崭等北叫反纯颤阢iz 吼i 么 ( b ) 若反 o ，由最优性条件( 2 1 3 ) 和以的非退化性假设可得，以 o ，鲥 o ，当南充 分大时，由观的连续性知：鳃 ；建 o ，由( z ) 的定义，取( ) = 一，从而 一t 等，等，= 争= 器， 亿4 朋， 颤蹶颤阢l 由假设a 4 知 锗巩揣争羔， 综合( 口) ，( 6 ) 知 h 壤妇叫午，争) _ 0 奄_ o 。，七x 2 、 疵 。 疵 。 不成立，从而q ：不趋向于0 。 当一p = 0 时，同理可证口；不趋向于o 。 综上所述，假设( 2 4 4 ) 不成立，定理4 1 成立。 定理2 2 若假设a 1 - a 4 满足，令 z 七) cq 是由算法产生的迭代序列。则 。l i m | i 玑j | = o 一+ o o ( 2 4 1 6 ) ( 2 4 1 7 ) ( 2 4 1 8 ) 证明 假设存在9 1 ( o ，1 ) 和 玑) 的一个子序列 弘) ，满足对所有的，i = 1 ，2 ，都有 i l 孔i i 1 ， ( 2 4 1 9 ) 定理2 1 保证了存在 玑) 的另一个子序列 孔 ，满足对任意的e 2 ( o ，1 ) ，使得 i i 玩0 s 2 ，七 如 ( 2 4 2 0 ) 第1 6 页 第二章有界约束非线性优化问题的仿射共轭梯度路径法 以及 i 民0 o ( 2 4 2 6 ) l 9 鸭 从而有h mq 知 0 ，如果瓯由( 2 2 5 ) 决定，显然也有。h ma 七 0 。从而与( 2 4 2 5 ) 式矛盾。 所以假设不成立，定理2 2 成立。 上述获得了算法的整体收敛性，下面讨论算法的局部收敛速率，然而需要进一步合 理的假设条件 假设a 5 问题( 2 1 1 ) 的解甄满足强二阶充分条件，即存在，7 0 ，使得 胛。p 训p i l 2 坳渺 ( 2 4 2 7 ) 假设a 6 当h mi 阮0 = o 时，有 u ml i 霄七一d i l v 2 d i li i = o ( 2 4 2 8 ) 定理2 3如果风正定，假设条件a 1 a 6 成立，设序列 孤) cq 是由算法产生的迭代序 列，氟为序列 z 七) 的极限点，则序列 ) 超线性收敛于双，即 熙锗- o ( 2 4 2 9 ) 第1 7 页 o = 磨 口 触 m 憎h 扣 2 4 整体收敛性与局部收敛速率 证明 先证当七充分大时，由算法第5 步产生的巧= d 七吻必满足( 2 2 3 ) ，从而牛顿步瓦= 一瓦1 玑被接受。 由二次模型( 2 1 1 1 ) 可知，乃= v 纸( 巧) = 矾+ 瓦乃，从而由( 2 3 1 ) 得 j 一1 o ：一( f j 、z 一， t = 0 由假设a 5 ，当后充分大时，有 九盔) = 巧= 巧巧= 醒砖+ 豸百巧， 圳巧0 2 谬霄奄码= 一醒巧i l 玑”i l 巧1 1 结合定理2 2 可得，i l 乃o 掣_ o ，1 1 o 托| i 弓0 一o ，( 后_ o o ) 。 由假设a 6 可得 妒七( ) 一，( z 七+ ) l = ( 2 4 3 0 ) ( 2 4 31 ) + 靠吻+ 丢巧风吻一( + 靠+ 丢哆v 2 + 。( o | 1 2 ) ) l 三哆( 风一v 2 ) + 。( o 1 1 2 ) i = l 三哆( 瓦一d i l v 2 d i l ) 巧+ 。( 1 i 1 1 2 ) l = o ( 1 l - j i l 2 ) ， ( 2 4 3 2 ) 由注释( 2 ) 知，吩= v ( 吻) = 鲰+ 凰，从而一鲰= 一巧+ 玩。又由假设a 5 ，引 理2 1 可知，当后充分大时，有 因为 所以 ，( ) 一慨( )= 一鲧吩一三巧凰 = 一弓；+ 吒h 列t 一书h 州t j l 一学( 九盔) + 1 tr r 互丐爿膏 = 丢哆凤= 三豸瓦巧罢l l - j l l 2 ( 2 4 3 3 ) ，( z 七) 一，( z 七+ ) ，( z 七) 一妒知( 叼) 一i 妒膏(