（运筹学与控制论专业论文）线性约束优化问题中的可行共轭梯度法.pdf

硕士学位论文 摘要 本文将求解无约束优化问题的非线性共轭梯度法的思想推广应用于求解线性 等式约束优化问题设计相应算法并证明算法的全局收敛性的思想 我们首先结合可行方向法和求解无约束优化问题的非线性共轭梯度法提出一 类求解线性等式约束优化问题的共轭梯度算法我们证明，当用于求解线性等式约 束下二次函数极小值问题时，若采用精确线性搜索，则该算法具有有限终止性而 且，此时f r 型算法，p r p 型算法，c d 型算法和d y 型算法是等价的，该结论 是求解无约束优化问题的子空间扩展定理的一种推广 本文的第二章是在较弱的条件下证明采用精确线性搜索时，f r 型算法用于 求解线性等式约束优化问题时的全局收敛性 本文最后还提出一种求解线性等式约束优化问题修正的f r 型( m f r ) 算法， 并在较弱的条件下，证明采用非精确线性搜索时算法的全局收敛性 本文最后进行数值试验，对所提出的算法进行数值测试i 9 1 4 试问题具有高度非 线性性，问题的规模由2 维至9 0 0 0 维所得结果表明本文提出的算法切实可行，是求 解线性等式约束优化问题的一种有效算法 关键词：线性等式约束问题；共轭梯度法；f r 法；m f r 法；二次终止性；全局收敛 性 硕士学位论文 a b s t r a c t i nt b i sp a p e r ，t h en 1 醒d i n e a rc o n j u g a t eg r a d i e i l tm e t h o df o rs o l v i n g 瑚1 c o n s t r 2 l i 球姐 0 p t i m i z a t i o np r o b l e mi sa p p l i e dt os o h ，eu n e a u fe q u a l 蚵c 0 i l s t r a i n e do p t i 皿z a t i o np r o b - l e m s t h e 酉o b a lc o n v e r g e n c eo ft h e m e t h o d si se s t a b u s h e d ，n u m e r i c a le ) ( p e r i m e n t s 盯ea ：k ；o 酉v e n 砌c hs h a wt h ee m c i e n t0 ft h ep r o p o s e dm e t h o d 8 a t 血s t ，c o m b i i l i n gt h ef e a s i b l e 出r e c t i o nm e t h o d 而t ht h ec o n j u g a t e 铲a l d i e n t m e t h o d ，w ep r o p o s eo fac 1 鹪80 fc o n j u g a t eg r a d i e n tm e t h o df o rs o l 诚n gl i n e a re q u a h t y c o n s t r 咖e dp r o b l e m w h e nt h em e t h d di su s e dt os o l v eal i n e a re q u a l i 匆c o n s t r a i n e d q u a d r a t i cp r o g r 舭m n i n g ，w ep r o v et h a t 虹l ec ( 蝴u g a t eg r a d i e n tm e t h o dw i t h 让l ee x a c t 1 i n es e a r 6 ht e r m i n a t ea tt h es o l u t i o no ft h ep r o b l e mw i t l l i nt h e 矗1 1 i t ei t e r a t i o 璐f i u r t h e rm o r e ，i nt h bc a u s et h ef r _ t y p em e t h o d ，p r p t y p em e t h o d ，c d t y p em e t h o da n d i ) y 咖em e t h o d 甜ee q m 、试e n t t h er e 8 u l ti se x t e 璐i o no ft h es u b s p a u c ee x t e n s i o n t h e o r e mf o rt h ec o n j u g a t eg r a d i e n tm e t h o d si nt h es 0 1 u t i o n0 fu n c o n s t r a j n e do p t i m i z a t i o n p r o b l e m i nd l 印t e r2 ，m l d e rm i l dc o n d i t i o n ，w ep r o v et h e 西o b a l lc o r l v e r g e n c eo ft h ef r - s t y l ei n e t h o dw i t he x 锄tl i n e8 e a r c hf o rs o l v 洫gl i i l e a re q u a l i t yc o 璐t r a i i n e do p t i m i z a t i o n p r o b l e m i nc h a p t e r3 ，w ep r o p o s eam o d m e df r ( m f r ) 8 t y l em e t h o df o rs o l v i n gl i n e 跗 e q u a u t yc 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 ，a n dw ea l s op r o 、陀i t s 舀o b 砒c o n v e r g e n c ei n t h ec 舀s ew h e r ei n e x a c tl i n es e a r c i hi 8u s e d f i i l 缸l y ，w e 百v et h en 眦e r i c a le x p e r i m e n t st oi m 髑t i g a t et h ep e r f o r m 龇1 c eo ft h e p r o p o s e dm e t h o d s t h et e s tp r o b l e m s 甜eh i 曲l yn o n l i n e a r ，a n dt h es c a l eo ft h et e s t p r o b l e 瑚v 哪f r o m2d i m e n s i o nt o9 0 0 0d i m e i l s b n t h er e s 诚so fn 【i l e r i c a le x p e r i m e n t si n d i c a t et h a tt h ep r o p o s e dm e t h o d si nt 址sp a p e ra r ee 任t i v ef o rs o l v i n gt h e 1 i n e a re q u a h t yc o n s t r 面n e dp r o b l e m k e yw 0 r d s ：c o n j u g a t eg r a d i e n tm e t h o d ；l i n e 村e q u a l i t yc o i l s t r a i n e do p t i m i z a t i o n p r o b l e m ；f rm e t h o d ；m f rm e t h o d ；g l o b a lc o n v e r g e n c e i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 醐。叩 6 窍l b ， 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密瓯 ( 请在以上相应方框内打“”) 作者签 导师签 昌篓；葶引昌 硕士学位论文 第1 章绪论 1 1共轭梯度法的背景与主要成果 共轭梯度法最初是针对无约束优化问题中的二次函数极小化问题而提出的一 种算法考察二次函数极小化问题 m i n m ) = 啦+ ， z 舻，( 1 1 ) 其中，q 形黼对称正定，口即先引入向量组共轭的概念 定义1 1 设q 形黼对称正定，d l ，如是印中非零向量若对i ，歹= 1 ，m ，有 吃lq 略= o ，i 歹， 则称向量组d l ，d m 关于矩阵q 相互共轭 求解二次函数极小值问题的共轭方向法的思想是：从某个初始点黝出发，依 次沿关于q 相互共轭的n 个方向也，i = l ，扎进行精确线性搜索，即令 z 南+ 1 = z 知+ q 知毗，七= 0 ，l ，死一1 ， ( 1 2 ) 其中，口角由精确线性搜索产生，即q 知是下面问题的解 ，( z 知+ q 七毗) 2 啦，( + a 甜 采用精确线性搜索的共轭梯度方向法求解严格凸二次函数极小值问题时可经 过有限步达到问题的最优解因此，共轭方向法具有二次终止性 求解一般无约束问题 m i n ，( z ) ， z 兄， ( 1 3 ) 的非线性共轭梯度法是在求解二次函数极小值问题的共轭梯度法的基础上发展起 来的记v ，( z ) 表示，在点z 处的梯度非线性共轭梯度法利用负梯度方向 一v ，( z 知) 与算法的前一个方向的线性组合作为第惫次迭代的搜索方向，且初始 方向为一v ，( 黝) ，即 也= 二； 薹；+ 反比一。，乏三： c 1 4 ， i v ，( z 南) + 反d 知一1 ，忌1 ， 其中，参数阮的确定使得算法用于求解二次函数极小值问题时，比和也一1 关于 q 相互共轭 线性约束优化问题中的可行共轭梯度法 1 9 5 2 年，h e s t e n e s l l 】和s t i e f e l l 2 】在【3 】提出h s 算法，其中参数凤取为 雎避需器群 在此基石出上，h s 算法的计算步骤如f ： 算法1 1 ( 非线性共轭梯度法一h s 算法) 步。取初始点z r n ，如= 一v ，( z o ) ，精度g 0 令后：= o 步1 若l i v ， 知) i l e ，则算法终止，得问题的解z 七否则，转步2 步2 由线性搜索确定步长q 七 步3令z k + 1 = 钆+ a 知毗 步4 由( 1 4 ) 确定毗+ l ，其中，仇= 解s 令忌：= 七+ 1 转步2 除了上面的h s 算法外，还有多种共轭梯度法，著名的有f r ( f l e t c h e r 一e v e s ) f 4 】 法，p i 冲( p o l a r k - r i b i e r e - p o l y a r ) 【5 ，6 1 法，c d ( f l e t c h e r - r e e v e s ) 吲法，d y ( d a l i y - u a n ) 【8 】 法这些算法中隗的选取方式如下： 觑= 雕k 黠， 凤= 俨= 业嵴糍拶， 风= 藤黯， 仇= 卯k 蕊摆 一 若将算法1 1 步4 中的反= 鳍s 分别改为阮= 硝r 、反= 陌r p 、凤= 鳄d 或仇= p ? y ，我们称相应的算法为f r 算法、p r p 算法、c d 算法或d y 算法当 这些算法用于求解凸二次函数极小化问题( 1 1 ) 时，若采取精确线性搜索，f r 算 法、p r p 算法、c d 算法以及d y 算法等价证明可以参考【9 1 中定理5 2 1 定理1 1 设 z 七) 表示由精确线性搜索的h s 算法求解二次函数极小化问题 产生的点列，则向量组 比) 留关于q 相互共轭，而且，对任何庇竹，有 v ，( z ) t 奶= o ，v ，( z 南) t v ，( z j ) = 0 ， 坳 下面的定理称为子空间扩展定理，定理给出了共轭梯度法的一个重要性质 定理1 2 ( 子空间扩展定理) 设严格凸二次函数厂由( 1 1 ) 给出，非零向量组 d 0 ，d 1 ，丸一1 关于矩阵q 相互共轭对任意的z o 舻，设迭代格式 z 凫+ 1 = z 七十口七d ，后= 0 ，l ，佗一1 2 一 硕士学位论文 中的呶由共轭梯度法确定，步长口七由精确线性搜索确定即q 七满足，( 瓢+ q 七以) = 赌，( z 忌+ q 丸) 则z 知+ - 是，在线性流行 = z = 铷+ 屈也i 屈冗， t = o ，1 ，七) t = 0 中的极小值点特别，z n = 矿= 一q - 1 口是问题( 1 1 ) 的唯一极小值点 子空间扩展定理证明了共轭梯度法的一个重要性质，即算法的有限终止性此 外，非线性共轭梯度法的表达式形式简单，易于编程，且只需要计算和存储目标函 数的梯度值与牛顿型算法以= 一凰v ，( z 七) ( 风是，在处的h e s s i a n 逆或其 近似) 相比，共轭梯度法的存储量大大减少，因而更加适用于求解大规模问题 本节我们主要介绍f r 算法、p r p 算法、h s 算法等几种常用的非线性共轭梯 度法的相关研究进展 ( 1 ) f r 算法 z o u t e n d i j k 【1 0 】已经给出了f r 法在精确线性搜索下求解非凸无约束优化问题 的全局收敛性同时，当采取强w r o l f e 线性搜索时，即q k 满足下面两个不等式 ，( z 七+ q 知d 知) ，( z 知) + 6 q k v ，( z k ) t d 知 其中o 6 0 使得 v ，( z ) 一v ，( 可) 0 l | | z 一剪，vz ，! ，( 1 8 ) 由假设容易得到，存在常数饥 0 ，使得 l i v ，( z ) l i 7 1 ，vz q 一7 一 ( 1 9 ) 线性约束优化问题中的可行共轭梯度法 第2 章线性等式约束问题的 f r 法及其性质 本章，我们提出求解问题( 1 6 ) 的一种f r 算法，并证明该算法的两个重要性 质：充分下降性和二次终止性 2 1 算法的描述 考察线性等式约束优化问题( 1 6 ) ，我们将求解无约束最优化问题的f r 共 轭梯度法的思想应用于求解( 1 6 ) 其基本思想如下：在当前迭代点z 南，寻找形 如( 1 4 ) 或( 1 5 ) 的可行下降方向然后，在可行域d 中进行线性搜索，得一新的 可行点，其目标函数值较，( z 七) 小注意到在( 1 4 ) 和( 1 5 ) 中，一v ，( z ) 可能不 是可行方向，为此，我们需寻找某种可行的最速下降方向取代一v 厂( z 南) 类似于 z o u t e n 幽k 算法中方向的确定，我们考察如下问题 s t a d = o ， l d l | 1 ， 其中d = ( 篡) 记问题c 2 的解为五= ( 霎) 哦 ( 驯篓) = 0 ， 即 从而 v ，( z 七) t d ( 2 1 ) = o 的d = ( 2 2 ) = ( v ( 珊瑚，嘲t ，v ( 根堋，硼t ) ( 篓) = v z 譬，( z 譬( z ) ，z ) t d b + v 茹，( z 暑( z ) ，z ) t d f 2 3 1 = v z 量，( z 导( z ) ，z ) 丁( 一日_ 1 ) + v 。，( z 譬 ) ，z ) t 。 = ( v z 0 ，( z 参( z ) ，z ) 一( b 一1 ) t v z 譬，( z 暑( z ) ，z ) ) t d = v f ( z 2 ，) 一8 一 硕十学位论文 又帕u 衄s z 不铽对任= ( 篓) 一忙妯有 v f ( z ) t d 一i i v f ( z 譬) | ii l d l l 一l i v f ( z ) i i 因此，当问题c 2 的可行点d = ( 篓) 满足 一器 时是问题c 2 的解即五= ( 舅) 由下式给出 雄= 一1 罟；，印= 一b 一1 茚 问题( 2 1 ) 给出了一种可行最速下降方向，在此基础上，我们进一步研究求解 线性等式约束优化问题( 1 6 ) 的可行共轭梯度型算法z h o u ，z h a n g 和l i 【1 6 】基于 【广b f g s 法的迭代格式，构造出了一种新的共轭梯度法m p r p 法，其迭代格式如 下： ， 比= 二孑； 三：；+ 阼艘d 知一。一巩纨一，蹇三呈： c 2 4 ， l v 厂( z 知) + 阼艘d 知一1 一巩纨一1 ，七1 ， 、 其中民= 豁，纨一1 = v ，( z 七) 一v ，( z 南一1 ) 从而，我们可以得到 v ，( z 知) t d = 一i | v ，( z 七) l | 2 ， 即m p r p 法能始终保证充分下降性，而且这种充分下降不依赖于任何线性搜索 当我们采取精确线性搜索，即巩= 0 时，m p r p 法的迭代格式就还原到p r p 方法 的迭代格式，此时，m p r p 方法就是我们传统的p r p 方法 令魂= v ，( z 七) t 五，一鲰= 一讯磊由磊和钆的定义，不难发现钆= v i j f ( z j 2 r ) 叭类似于z h o u ，z h a n g 和l i 【1 6 】提出的m p r p 法的迭代格式，我们 提出求解线性等式约束优化问题( 1 6 ) 的一类可行共轭梯度法，其搜索方向比由 d 知= 二塞+ 反比一。一巩u 知，竺三呈： ( 2 5 ) 其中觑是参数，由共轭梯度法给出，可以是鳍s ，雎兄，筇r p ，熙d ，卯y 中的任意 一种，乱七s 是可行方向且满足v ，( z 南) t 越南o ， 戮将风 一9 一 线性约束优化问题中的可行共轭梯度法 注：在( 2 5 ) 中，若取u 磨= 玑一1 ，则( 2 5 ) 的形式与( 1 5 ) 一致，因此，( 2 5 ) 可 作为是( 1 5 ) 的一种推广 容易验证，a 比= 0 对所有的忌都成立，即九是可行方向 2 2 方向的下降性 本节，我们可以证明若z k d 不是问题( 1 6 ) 的k k - t 点，则由( 2 5 ) 确定的 方向毗是问题( 1 6 ) 的一个可行下降方向 k k t 点是约束最优化问题的一个重要概念，其定义由下面给出设函数，心，j e ，吼，z j 连续可微，考察如下一般约束最优化问题 m l n s z ，( z ) 吼 ) o ， 屯( z ) = o ， i j = 1 ，2 ，m 1 ) ， 歹e = m 1 + 1 ，2 ，m ) ( 2 6 ) 下面的定理给出了矿是问题( 2 6 ) 的解得一阶必要条件，或称为k k t 条件 定理2 1 设z + 是二次规划问题局部最优解，若下面的两个条件之一成立： 1 在z + 处的有效约束的梯度线性无关； 2 约束函数均为线性函数， 则存在l a g r a n g e 乘子向量a + 和肛+ ，使得下面的条件成立： lv 霉l ( z ，a + ，p + ) = o ， ；b ( z + ) = o ，j e ， la ；o ，仇( z + ) o ，a ；吼( z + ) = o ， i j 下面，我们将给出由( 2 5 ) 确定的方向也是可行下降方向 定理2 2 设钆d ，则由( 2 5 ) 定义的方向也是线性等式约束优化问题 ( 1 6 ) 在z 膏的可行方向且满足 v 厂( z 知) t 比= 一v 厂( 钆) t 鲰0 而且，v ，( z 七) t 以= o 当且仅当z 七是问题( 1 6 ) 的k k t 点 证明根据( 2 5 ) ，我们有 a d 南= a ( 一9 k + 反d 七一1 一九乱南) =一a 9 岛+ 凤a d 七一l 一巩a u k ( 2 7 ) =0 一1 0 一 硕士学位论文 即以是线性等式约束优化问题( 1 6 ) 在z 七的可行方向又由比的定义，有 呶= 一夕k + 仇d 知一l 一乩钍七 = 一鲰+ 反以一- 一锻凤 等式两边同时乘以v ，( 钆) 有 v ，( z 七) t 比= 一v ，( z 七) t 鲰= 一j iv f ( z j 2 r ) l | 2 o ( 2 8 ) ( 2 7 ) 和( 2 8 ) 表明由( 2 5 ) 定义的搜索方向也是当前迭代点z 克处的可行下降 方向 下面我们将证明：v ，( z 蠡) t 毗= o 的充分必要条件是当前迭代点z 知是线性等 式约束优化问题( 1 6 ) 的k k t 点 先假设当前迭代点z 知是线性等式约束优化问题( 1 6 ) 的k k t 点，则存在 l a g r a n g e 乘子九，t = 1 ，2 ，m ，使得 v ，( 钒) 一九啦= o 在等式的两边同时乘以比，则有 m d j v ，( 瓢) = 入。- 毗= o t = 1 另一方面，若v ，( ) t 毗= o ，则由( 2 8 ) 有 一v ，( z 七) t 鲰= v ，( z 詹) t 如= 0 由一鲰的定义和定理2 2 1 ，存在九，i = 1 ，2 ，m 使得 m v 弛知) 一九啦+ 2 p = 0 = 0 p o ，i | | i 1 ，p ( | | d 1 1 2 1 ) = o ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 在等式c 2 1 1 ，两边同时乘以一肌，且由一鲰= ( 嚣) 我们有 一菇v 厂( z 七) + 凡订锄+ 2 p i i 硭1 1 2 = o ， 进一步我们结合( 2 1 0 ) ，( 2 1 2 ) ，( 2 1 3 ) 可以得到肛= o 从而由( 2 1 1 ) ，我们有 v ，( z 七) 一概= o 又z 知d ，即4 z 七= 6 上面说明，点z 知是线性等式约束优化问题( 1 6 ) 的k k t 点 证毕 一1 1 一 线性约束优化问题中的可行共轭梯度法 2 3共轭性和二次终止性 本节我们进一步研究由( 2 5 ) 产生的方向的重要性质，我们证明，采用精确线 性搜索下的相应算法用于求解线性等式约束二次规划问题时具有有限终止性 考察线性等式约束二次规划问题 m 1 _ ( z i z t q z + q t z ， ( 2 1 4 ) s t a z = 6 其中，q 舻“对称正定，口舻，a = ( o l ，8 2 ，口m ) t 舻煳，6 我们分 别用d 和s 表示线性等式约束二次规划问题( 2 1 4 ) 的可行域和可行方向集，即 d = z 月，i a z = 6 ) ，s = d r ，i a d = o 下面的定理是子空问扩展定理的一种推广，定理展示了由( 2 5 ) 定义的也的 另一个重要性质 定理2 3 设知是线性等式约束二次规划问题( 1 4 ) 的任意可行点且迭代序列 z 知) 是由下列迭代格式产生 z 七十1 = z 知+ q 詹d 七，七= 0 ，l ，2 ， 其中搜索方向毗是由( 2 5 ) 确定的，风= 至号笼蓦e 专耥且搜索步长 q 知由精确线性搜索产生，即口南满足v ，( z 凫+ 钒巩) t 以= o ，则 ( 1 ) 对于任意的七，有下面的等式成立 q 嘭= o ，v ，( z 血) t 办= o ，v 厂( 瓢) t 毋= o ， 七( 2 1 5 ) ( 2 ) 可行点钆是，在线性流形 中的极小值点特别地，z 他一仇是等式约束二次规划问题( 1 4 ) 的唯一极小值点 证明( 1 ) 因为搜索步长。七由精确线性搜索产生，则有 v ，( 矾) t 毗一1 = o 由巩的定义易知，巩= 0 因此，由( 2 5 ) 确定的方向九可等价的表示为 毗= k 乩葚 亿峋 、， r 如也以 ：l + o z i l z酽 z r i nd | | 瓯 硕士学位论文 由反的定义和( 2 1 6 ) 有 d t q 如一，= o 接下来，我们将证明对任意的札都有 d j q 略= o ，v ， k ) t 略= o ，v ，0 毛) t 缈= o ， 忌 当尼= 1 时，很明显 d 丁q d ；0 = o ，v ， 1 ) t d o = o ，v ，( z 1 ) t 夕0 = 一v ，( z 1 ) t 如= o ( 2 1 7 ) 我们假设当礼= 七一1 时，( 2 1 5 ) 是成立的下面，我们将证明当n = 七时，( 2 1 5 ) 仍然是成立的对于任意的歹后一1 ，由假设我们有 v ，( z 七) t 奶 和 则 因为 = 巧( v ，( z 南) 一v ，( z 七一1 ) ) + + 町( v ，( + 2 ) 一v ，( + 1 ) ) + 巧v ，( + 1 ) = d 7 - ( v ，( z t ) 一v ，( z t 1 ) ) 句+ 2 南 = 町q ( 觋一z t t ) 讧0 + 2 七 = 瓴一1 盯q 也一1 i = f + 2 =0 v ，( z 知) t 毋= v 厂( z 忌) t ( 一奶+ 岛奶一1 ) = o v f ( z ) = ( 一召- 1 ) t v 霉譬厂( z 譬( z ) ，z ) + v z ，( z 譬 ) ，z ) = ( ( 一b 1 ) t ，e ) v ，( z k ) ， 鲰= v ，( z ) ， 1 3 一 珊瑚 徘 矿r l|啡卜卜晰町 ) 兰= e e 旷 勒一ve一尝 线性约束优化问题中的可行共轭梯度法 其中 ：( b 二三竺；! ：，t 一1 ) = i 、7 i 对称矩阵由v ，( z 知) t 毋= o ，有 从而，对任意的歹 七一1 ，有 v ，( ) t w v ，( ) = o q 也= ( 一纨+ 厥毗一1 ) t q 力 一舛q 呜+ 凤以一1 q 呜 一壶订( v ，( 巧+ ，) 一v ，( ) ) 一击( 疗v ，( 吩+ - ) 一露v ，( ) ) 一击( v ，( z 奄) t w v ，( 巧+ 1 ) 一v ，( 钆) t w v ，( ) ) 因此也，i = 0 ，1 ，南关于矩阵q 相互共轭 ( 2 ) 上一部分我们己证得搜索方向也，i = o ，1 ，后关于矩阵q 相互共轭，则 也，z = 0 ，1 ，毛线性无关，故有& 一l = 毋 下面，我们只需要证明z 七+ 1 是，在线性流形鼠中的极小值点 由 z 后+ 1 = z 七+ a 七以= 。黝+ 可知，对任何z 鼠，存在屈冗，z = 0 ，1 ，后，使得 由t a y l o r 展开得 ，( z ) = z = z o + s k 厂( z 缸+ ，) + v ，( z 知+ 。) t ( z z 知+ - ) + 丢( z z 知+ 。) t q ( z z 知+ ) ，( z 七+ 1 ) + v ，( z 七+ 1 ) t ( z z 磨+ 1 ) = ， 凫+ 1 ) + ( 觑一q ) v 厂 知+ 1 ) t 也 i = o 而且，当z z 七十l 时，上丽的不等式为严格4 i 等式又由( 2 1 5 ) ，我们有 从而对任何z 鼠有 v ，( z 南+ 1 ) t d t = o ， = o ，1 ，七 厂( z ) ，( z 缸 - 1 ) ， 1 4 一 d口 七渤 也 8 知：l 硕十学位论文 从而定理得证 定理2 3 说明，用于求解线性等式约束= 次规划问题的h s 型算法具有有限终 止性另一方面，( 2 1 5 ) 表明，当用于求解线性等式约束二次规划问题时，h s 型 算法、f r 型算法、p r p 型算法、c d 型算法、d y 型算法是等价的因此，定理2 3 实际上是扩展子空间定理的一种推广 一1 5 线性约束优化问题中的可行共轭梯度法 第3 章采用精确线性搜索的f r 型共轭 梯度法的全局收敛性 。上一章的结论表明，当用于线性等式约束二次规划问题求解时，共轭梯度型 算法具有有限终止性本章，我们研究第2 章中提出的共轭梯度性算法用于求解 一般非线性函数在线性等式约束下的极小值问题的全局收敛性 3 1线性等式约束问题的f r 型算法 考察线性等式约束最优化问题 m i n ，( z ) s 亡a z = 6 ( 3 1 ) 其中，：舻_ r 连续可微，a 冗仇“行满秩6 胛我们分别用d 和s 表示问 题( 3 1 ) 的可行域和可行方向集，即 d = z 月，i a z = 6 ) ，s = d 月，i a d = o ， 矩阵a 分解为a = ( b ，) ，其中男咒m m 非奇异对任意z d ， 则护= b 一1 6 一b 一1 z 显然，问题( 3 1 ) 等价于下面无约束问题 m i n f ( z ) 垒，( z b ，z ) = ，( b 一1 6 一b 一1 z ，z ) ( 3 2 ) 设z 七为当前迭代点，求解下面线性规划 其中d = m i nv ，( z 七) t d s 4 d = 0 记问题( 3 ， 由上一节我们知道问题( 3 ) 的解为 3 3 ) 的解 l l d l i 1 ， 由下式给出 彭= 一斋毙黼，雄= 一b 。霹 一1 6 一 ( 3 3 ) 融 糊护 们厂 我 l z 令 、一、 霹霹印霹 ，i = = 五 五 b d 岔 硕+ 学位论文 令魂= v ，( z 知) t 五= v f ( z ) t ( 裂= 一i | v f ( z ) i i ，一鲰= 一魂五在上面的基础 上，我们类似于求解无约束最优化问题的共轭梯度法，构造方向以如下： 巩： 咄， k 0 ( 3 4 ) i 一鲰+ 阮也一1 ， 七1 ， 由鲰，魂和五的定义易知，玑= ( 一1 ) v f c z 2 ，本章，我们仅考察f r 型 算法，即在( 3 4 ) 中取臃= 差冬，由钆的定义，我们有凤= 书簧嚣 o 七一1 容易看出，由( 3 4 ) 定义的也是钆处的一个可行方向 而且，若采取精确线性搜索，则有 v ，( z 七) t 以= 一v 厂( z 奄) t 9 = 一i f v f ( z ) 1 1 2 ( 3 5 ) 因此，只要z 七不是问题( 3 1 ) 的k k t 点，则i i v f ( z ) | l o ，此时有v ，( z 七) t 毗 0 ，使得 v 厂( z ) 一v 厂( 可) i l l | | z 一可| i ，v z ，可 一1 7 线性约束优化问题中的可行共轭梯度法 迭代序列 z 七) 由采用精确线性搜索的算法3 1 1 产生，则 l i 口i n f v f 扛) i l = o 证明根据迭代格式( 3 4 ) 有 ( 墨) = ( 二霎) + 凤( 豢：) 特别，有 d = 一夕，+ p 南d 墨1 由( 2 3 ) ，夕k 的定义及精确线性搜索条件有 ( 9 ，) t 堪1 = v f ( z 2 ，) t d 也。 = v ，( z 知) t d 七一1 在( 3 7 ) 两端取范数即得 l l 皑1 1 2 = l b 1 1 2 2 仇d 也。+ 磁l l d 怨。1 1 2 = 1 1 9 洲2 + 穰1 i d 乜。1 1 2 = 1 2 + 黠雌，1 1 2 上式两边同时除以i i v f ( z ：2 r ) 1 1 4 ，注意到夕= v f ( z j 2 r ) 可得 f f 礤f f 2 1 。l f d 墨。l f 2 。：- 一= ：= 一+ 一 l l v f ( z 岔) l | 4 l i v f ( z ) f 1 2 。l | v f ( z 怨。) 1 1 4 一 l 。 1 。 f i 雅。1 1 2 一丌弓万瓣十i 可万i 珊十1 可珊 一忐 1 | f 掣1 1 2 2 蚤南+ 赫。台 l v f ( z ，) 1 2 8 v f ( z 分) 1 1 4 。 则 器= 娄赢薪1 i v f 0 ) 1 1 4 一台l l v f ( z ) i i 。 反设( 3 6 ) 不成立，则存在常数 o ，使得 l i v f ( z ) | l ，讹 由此及( 3 8 ) 得 l i d 1 1 2，七 雨研 从而 l i 础1 2 翱v f ( z 洲4 ( 3 6 ) ( 3 7 ) ( 3 8 ) ( 3 9 ) 硕士学位论文 因为也是可行方向，所以 故存在常数c 0 使得 i i 耀| 1 2 c | i 彬1 1 2 箬i i v f ( z ) 1 1 4 由此及( 3 9 ) 可推得 i i 也1 1 2 = i l d 譬1 1 2 + i i d j 2 r i | 2 三 尼i i v f o j 2 r ) 1 1 4 ， 上式等价为 | | v f 0 ) ij 4 2 l i 也1 1 2二( c + 1 ) 七 两边同时取和，则有 譬：慨 ( 3 1 0 ) 缸 恻1 2 ” _ “叫 另一方面，由中值定理，对任何q 0 ，均有 ，( z 七+ q d 七)= ，( z 七) + q v 厂( z 七+ 南q d 南) ld 彪 =，( z 七) + q v ，( z 血) t d 知+ 0 1 【，( z 七十t 知q d 知) 一v ，( z 知) 】t d 膏 ，( z 七) + 口v ，( z 知) t 以+ n | i ，( 钒+ “q 也) 一v ，( z 知) l 也 ，( z 七) + a v ，( z 七) t d 南+ 三q 2 i i d 七1 1 2 ， 其中，如( o ，1 ) 特别，上式对 驴一瑞学 成立，即有 ，( z 七+ a 知d 知) 一，( z 七) a 七v ，( z 知) t 毗+ l a 2l l d 七| | 2 一壶掣 由精确线性搜索条件，步长q 南满足 ，( z 七+ 1 ) = ，( z 知+ a 南畋) ，( z 七+ a 南d 七) ， 从而， 即 m m h 地叫训一壶警， c 警洲叫叫阱，) i ( 3 1 1 ) 一1 9 线件约束优化问题中的可行共轭梯度法 其中c = 壶 又由( 3 5 ) 有 v ，( ) t 比= 一v ，( z 南) t 鲰= 一钰v ，( z 南) t 五= 一= 一l i v f ( z ) 1 1 2 由此及( 3 1 1 ) 得 从而 上式与( 3 1 0 ) 矛盾 因此，( 3