（应用数学专业论文）线性约束优化的仿射内点预条件共轭梯度路径法.pdf

y 9 3 1 6 0 5 j 中文摘要 摘要 本文主要讨论利用仿射投影既约预条件共轭梯度路径内点方法解带线性等式约束和 有界变量约束的最优化问题。 共轭梯度法是最优化中最常用的方法之一，它具有算法简便、不需要矩阵存储等优 点，十分适合于大规模优化问题。无约束优化问题的共轭梯度路径构造的思想启迪我们 用其来解带线性等式约束和有界变量约束的优化问题。基于广义消去法，本文中原问题 可转化为等式约束矩阵的零空间中的一个无约束优化问题。将共轭方向法应用于零空间 中的近似二次模型，得到一组共轭方向序列，共轭方向序列生成了共轭梯度路径。共轭 梯度路径类似于信赖域的一些重要性质，将对算法整体收敛性的证明起重要的作用。本 文通过一个增广系统解既约预条件方程，克服了既约矩阵不保持原矩阵的充分稀疏。在 信赖域子问题中产生可行方向满足严格可行性将导致计算的困难，使用严格可行的信赖 域子问题可能要重复解多次才能接受步长，因此完成一次迭代的计算可能是昂贵和困难 的。为了克服这一困难，本文通过引进一个仿射变换矩阵，构造仿射投影既约预条件共 轭梯度路径来搜索获得迭代方向。当搜索方向不被接受时，采用回代线搜索技术得到可 接受步长，从而定义新的迭代点。由此得到的算法不仅具有整体收敛性，而且保持快速 的局部超线性收敛速率。 全文共分五章。第一章简单地介绍最优化的一些基本理论和概念。第二章构造仿射 投影既约预条件共轭梯度路径，并给出其基本性质，在此基础上，结合既约预条件技 术、共轭梯度路径搜索策略、内点仿射变换和回代线搜索技术等技巧提供了算法。第三 章基于仿射共轭梯度路径的良好性质，在合理的假设条件下，证明了算法不仅具有整体 收敛性，而且具有快速的局部超线性收敛速率。第四章给出了具体的数值试验结果，表 明了算法的可行性和有效性。最后，第五章对本文工作进行总结，同时提出了进一步的 研究方向。 关键词：仿射投影：既约预条件；内点法；共轭梯度路径；整体收敛性；局部收敛速率 第1 页 英文摘要 a b s t r a c t i nt h i st h e s i s ，w ep r o p o s ea l la f f i n es c a l i n gp r o j e c t e di n t e r i o rm e t h o dv i ar e d u c e dp r e c o n d i - t i o n a lc o n j u g a t eg r a d i e n tp a t hf o r t h el i n e a re q u a l i t yo p t i m i z a t i o ns u b j e c tt ob o u n d so nv a r i a b l e s c o n j u g a t eg r a d i e n tm e t h o d ，w h i c hc a l lb ee a s i l yc o m p u t e da n dr e q u i r e sn om a t r i xs t o r a g e ， i so n eo ft h em o s tp o p u l a ra n du s e f u lm e t h o df o rs o l v i n gl a r g es c a l eo p t i m i z a t i o np r o b l e m s t h e i d e ao fc o n j u g a t eg r a d i e n tp a t hi nu n c o n s t r a i n e do p t i m i z a t i o ni r r a d i a t e su st ou s et h i sm e t h o df o r s o l v i n gt h el i n e a re q u a l i t yo p t i m i z a t i o ns u b j e c tt ob o u n d so nv a r i a b l e s b yu s i n gt h eg e n e r a l i z e d e l i m i n a t i o nm e t h o d ，t h es u b p r o b l e mi se q u i v a l e n tt oa nu 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 mi nt h e n u l ls p a c e t h ep a t hi sd e f i n e da sl i n e a rc o m b i n a t i o no fas e q u e n c eo fc o n j u g a t ed i r e c t i o n sw h i c h a r eo b t a i n e db ya p p l y i n gc o n j u g a t ed i r e c t i o nm e t h o dt ot h ea p p r o x i m a t eq u a d r a t i cf u n c t i o ni nt h e u u us p a c e t h ep r o p e r t i e so ft h ep a t hw h i c ha r es i m i l a rt ot h et r u s tr e g i o um e t h o da r ei m p o r t a n t t ot h ep r o o fo ft h eg l o b a lc o n v e r g e n c eo ft h ep r o p o s e da l g o r i t h m i ti su n l i k e l yt h a tt h er e d u c e d m a t r i xw i l lb es u f f i c i e n t l y s p a r s e ，s ow ed e v e l o pp r e c o n d i t i o n e r sb a s e do na l le x t e n d e ds y s t e m i ti s p o s s i b l et h et r u s tr e g i o ns u b g l r o b l e mw i t ht h es t r i c t l yf e a s i b l ec o n s t r a i n tn e e d st ob er e s o l v e dm a n y t i m e sb e f o r eo b t a i n i n ga l la c c e p t a b l es t r i c ti n t e r i o rf e a s i b l es t e p ，a n dh e n c et h et o t a lc o m p u t a t i o n f o r c o m p l e t i n g o n e i t e r a t i o n m i g h t b e e x p e n s i v e a n dd i 伍c u l t i n o r d e r t o o v e r c o m e t h e d i f f i c u l t i e s w ei n t r o d u c ea l la f f i n es c a l i n gm a t r i x ，a n df o r mt h ea f l i n es c a l i n gr e d u c e dp r e c o n d i t i o n a lc o n j u g a t e g r a d i e n tp a t ht oo b t a i nan e wa c c e p t e ds t e p w eu s et h el i n es e a r c hm e t h o db ye m p l o y i n gt h e b a c k t r a c k i n gs t e p sa ta r tu n s u c c e s s f u lt r i a ls t e pt oo b t a i nan e wi t e r a t i v ep o i n t t h ep r o p o s e d a l g o r i t h mn o to n l yh a sg l o b a lc o n v e r g e n c eb u ta l s ol o c a lc o n v e r g e n c er a t e t h et h e s i sc o n s i s t so ff i v ep a r t s i nc h a p t e r1 。w es u m m a r i z et h eb a s i cc o n c e p t sa n dt h e o t i e so fo p t i m i z a t i o nt e c h n i q u e i nc h a p t e r2 ，b a s e do nt h es t r u c t u r ea n dp r o p e r t i e so ft h e , f f f i n e s c a l i n gr e d u c e dp r e c o n d i t i o n a lc o n j u g a t eg r a d i e n tp a t h ，w ed e s c r i b et h ea l g o r i t h mw h i c hc o m - b i n e s t h e t e c h n i q u e so f r e d u c e d p r e c o n d i t i o n a l t e c h n o l o g y , c o n j u g a t e g r a d i e n t p a t h ，i n t e r i o r p o i n t ， a n dl i n e a rb a c k t r a c k i n gs e a r c hs t r a t e g y i nc h a p t e r3 ，b a s e do nt h eg o o dp r o p e r t i e so ft h ec o n - j u g a t eg r a d i e n tp a t h ，g l o b a lc o n v e r g e n c ea n dl o c a lc o n v e r g e n c er a t eo ft h ep r o p o s e dm e t h o da r e e s t a b l i s h e du n d e rs o m er e a s o n a b l ec o n d i t i o n s i nc h a p t e r4 ，n u m e r i c a lr e s u l t si n d i c a t et h a tt h e a l g o r i t h mi su s e f u la n de f f e c t i v ei np r a c t i c e f i n a l l y ，c h a p t e r5c o n c l u d e st h em a i nr e s u l t so ft h i s t h e s i sa n dp r o p o s e ss o m ef u r t h e rr e s e a r c hd i r e c t i o n sa b o u t0 1 1 1 w o r k k e y w o r d s ：a f l i n es c a l i n g ；r e d u c e dp r e c o n d i t i o n a l ；i n t e r i o rp o i n tm e t h o d ；c o n j u g a t e g r a d i e n t p a t h ；g l o b a lc o n v e r g e n c e ；l o c a lc o n v e r g e n c er a t e 第1 i 页 符号说明 为了避免符号混淆，对本文中的符号做以下说明 g p n 维实向量空间 犯“ m n 维实矩阵 队”| 1 2e u c l i d 范数 ”i i 。一范数 z 他维决策变量 f目标函数 c ( z )约束函数 n 可行集 i n t ( f 1 )严格可行集 g ( z ) ，在2 处的梯度，f l 口v f ( x ) v 2 f ( x ) f 在z 处的h e s s e 阵 7 ，卢，j l a g r a n g e 乘子 l ( x ，7 ，“p ) 约束优化闷题的l a g r a 【l l g c 函数 ，在当前迭代点z t 处的函数值 4 ( z ) 约束优化问题在可行点z 处的有效约束集合 仇( p ) 目标函数在z 放b 的局部二次近似 k 信赖域半径 c ( z o ) = z g p if ( x ) f ( x o ) ) 水平集 磁 约束优化问题的仿射预条件共轭梯度路径 m 第k 次迭代步 成 零空间中第k 次迭代步 ( m ，v 2 ，七，巩，仇，a ，磊， t k ，螈等表示相应的函数在z k 处的值，这里就不一一详述 了。) 第页 第一章最优化基础 第一章最优化基础 1 1 最优化问题的数学模型与分类 最优化问题就是在有限种或无限种可行方案( 决策) 中挑选最优的方案( 决策) 。随着科 学技术的飞速发展，最优化理论与方法在工农业生产、交通运输、金融、管理、通信等 众多领域的应用越来越广泛。为应用最优化技术确定最优的方案，需要针对具体的实际 问题建立相应的最优化模型，再根据模型的具体形式和特性选择适当的最优化方法求 解。 最优化问题的数学模型一般形式为： m i n f ( x ) s t c i ( ) = o ，i = 1 ，2 ，一，m ， c i ( 曲o ，t = 矗- i - 1 ，m ，( 1 1 1 ) 其中，：舻一跄1 ，q ：渺一骑1 0 = 1 ，2 ，m ) 。，( 。) 和c i ( 。) 都是定义在咿上的实 值连续函数。z 妒称为优化变量或决策变量，( z ) 称为目标函数，臼( z ) 称为约束函 数。q ( z ) 0 = 1 ，2 ，m ) 为等式约束，c i ( z ) 0 = m + 1 ，m ) 为不等式约束。定义集 合q 为 q d = e f z lc i ( 。) = 0 ，i = 1 ，2 ，一，m ；q ( 。) 0 ，i = m + 1 ，一，m ) ， ( 1 1 2 ) 称n 为约束集合、约束区域或可行域。若o q ，则称z 为可行点或可行解。 若模型( 1 1 1 ) 中不含约束条件，即q = 舻，称模型( 1 1 1 ) 为无约束优化问题，无约束 优化问题是在空间舻上寻求使目标函数，( $ ) 达到极小或最小的点z + 。 若模型( 1 1 1 ) 中含有约束条件，则称模型( 1 1 1 ) 为约束优化问题，约束问题是在约束 集q 上寻求使目标函数，( z ) 达到极小或最小的点o 。 若模型( 1 1 1 ) 的目标函数，( 。) 和约束函数g ( 。) “= 1 ，2 ，m ) 都是线性函数。则称模 型( 】1 1 ) 为线性规划。若，( z ) 和q ( 。) a = i ，2 ，仇) 中至少有一个是非线性函数则称模 型( 1 1 1 ) 为非线性规划。特别的，当目标函数， ) 是二次函数，q ( z ) “= 1 ，2 ，m ) 都 是线性函数时，则称模型( 1 1 1 ) 为二次规划。 1 2 最优性条件 最优性条件，是指最优化问题( 1 1 1 ) 的最优解( 局部的或全局的) 所满足的必要条件和 充分条件。下面在目标函数和约束函数一阶或二阶连续可微的前提下，给出最优化问 第1 页 题( 1 1 1 ) 的最优性条件。最优性条件不仅对于最优化理论研究具有重要意义，而且也是构 造求解最优化问题新算法的理论基础。 记 e = ( 1 ，2 ，m 。) ， z = ( m 。+ 1 ，一，m ) ， 工0 ) = ( l q 扣) o ，i z 定义1 2 1 对任何z 妒，称集合 ( i2 1 ) ( 1 2 2 ) 4 ( z ) = u i r ( x ) ( 1 2 4 ) 是在。点处的有效约柬集合( 或积极约束集合) 。 下面给出最优解的一阶必要性条件，又称k u h n t u c k e r 条件。 定理1 2 2 ( 库恩一塔克一阶必要条件) 设丑q 是最优化问题( 1 1 1 ) 的一个局部最优 解，( z ) ，q ( z ) ，i = t ，2 ，m 在“的一个邻域内连续可微如果对所有的等式约束 和在巩的有效不等式约束，或者都是z 的线性函数。或者它们在点。的梯度向量线性无 关，则存在向量= ( t ，骨，竹) 7 使成立 w ( z 。) 一t v g ( “) = 0 ，( 1 2 5 ) t 0 、i = “- t - 1 t q ( 。) = 0 ，i = m 7 + 1 ( 1 2 6 ) ( 1 2 7 ) 定理1 2 2 中关于约束函数的条件称为约束规范有许多不同的约束规范条件和表现 形式t 但最常见也是最方便使用的还是上述定理中所给出的约束规范条件。 式( 1 _ 2 5 ) ，( 1 2 6 ) 和( 】2 7 ) 称为库恩* 塔克条件，满足库恩一塔克条件的点为库恩一塔 克点( 简称k - t 条件- 与k - t 点) ，( 127 ) 式称为互补松弛( c o m p l e m e n t a r i t y ) 条件。如果对任 意的i = 打t 7 + l 、 ，m q ( 耳) 和以中有且仅有个取零值则称严格互补松弛性条件成 立。 下面给出最优解的二阶必要条件。 定理1 2 3 设o n 是最优化问题( 1 i 1 ) 的最优解，且函敷，( z ) 与q ( ? ) ，i = 1 ，2 ，m 二阶连续可微又设定理l2 2 中的约束规范务件在点z ，成立，从而存在扭格朗日乘手向 量使k i u m - 1 、i c k e r 条件成立如果严格互补松弛条件在成立，别 对一切满足 p 7 v 弘( ，7 ) p o p 审q ( “) = 0 ，t ( z 。 第2 页 第一章最优化基础 的方向p 均成立。 下面的定理给出了最优解的二阶充分条件。 定理1 。2 4 设最优化问题( 1 i 1 ) 的函数，( z ) 与q ( z ) ，i = 1 ，2 ，m 均二阶连续可微，在 可行点z 。处定理1 2 2 的约束规范条件成立，若存在拉格朗日乘子向量仉使k u h n m c k e r 条 件和严格互补松弛条件成立，且对所有满足 p t v c 4 ( x + ) = 0 ，i 4 ( z 。) 的非零向量p 有 p 7 v 。2 。l ( x ，仉扫 0 则。是问题( 1 1 1 ) 的一个严格局部最优解。 1 3 最优化方法概述 求解问题( 1 1 1 ) 通常是通过求其k - t 点的途径得到它的最优解。一般采用的是迭代 法。其基本思想为：给定初始点，按照某一规则产生一个迭代序列扣t ，使得当 z t ) 是有限点列时，它的最后一个点是k - t 点；当 o k ) 是无限点列时，它的任意一个聚点就 是k - t 点。 最优化问题求解的基本迭代格式如下： 算法1 3 1 ( 最优化方法的基本迭代格式) 1 给定初始点o o ，k = 0 。 2 按某一规则构造搜索方向p k 。 3 确定步长o k ( 对于某些算法a b ；1 ) 。 4 取下一个迭代点z k + 1 = x k + w k p k 。 5 判别。k + l 是否满足某种终止准则。若满足，停止迭代过程，z k + l 是近似局部最优 解。否则，七# k + 1 转第2 步。 在以上迭代格式中，关键的两步是构造搜索方向巩和确定步长a k 。不同的构造方 向如与和确定步长o 构成了不同的算法。其中线搜索策略和信赖域策略是保证最优化方 法整体收敛的两类技术。线搜索策略把求多变量函数的极小化问题转化成求一系列单变 量函数极小化的子问题。信赖域策略是在迭代的每一步求解一个具有信赖域约束的子问 题。所谓“信赖域”是当前迭代点o 的一个领域，在这个领域内子问题充分逼近于原问 题。信赖域半径的大小根据每次迭代结果逐步调节。一般地，如果当前迭代模型较好的 逼近原问题，则信赖域半径可扩大，否则信赖域半径应缩小。 对于求解最优化问题的一个数值方法，评价这个方法优劣的标准之一是由它产生的 迭代序列 z k ) 的收敛速度。设序列 巩 收敛于乳，用误差函数 e ( 。) = i l o 一z 第3 页 1 4 预条件共轭梯度法 来度量收敛速度。 如果存在常数a 和r 使得下式成立 熙帮北 ( 1 3 1 ) 就说序列 孤) 以g 为因子r 阶收敛于文。 当r = 1 ，0 c 0 ，预条件矩阵m ，+ g o = h x o + b ，解m y = g o 得珈 令d o = 一珈，_ j c ：= 0 。 步2 如果| | 鲰| iss ，停止。 步3 计算 解m y = 9 + l 得g k + 1 ， 步4 令k ：= k + l ，转步2 a t = 蒜， x k + l = $ k + o ：k p l c ， g k + l = g k + 。k h p k 反= 紫， 口：1 肛 p k + l = 一v t + l + 玩p k ( 1 t 4 4 ) ( 1 4 5 ) ( 1 4 6 ) ( 1 4 7 ) ( 1 4 8 ) 如果令m = i ，则预条件共轭梯度算法1 4 1 就是标准的共轭梯度算法。由预条件共 轭梯度法得到的方向序列也具有和标准的共轭梯度法相对应的方向共轭性、梯度直交 性、下降性等性质，具体形式将在下一章中具体描述。 第5 页 第二章仿射预条件共轭梯度路径内点法 2 1 引言 本章分析与提供了仿射投影既约预条件共轭梯度路径内点算法解下面带有线性等式 约束和有界变量约束的最优化问题： m i nf ( x ) s t a z = b f z t 正 ( 2 ，l 1 ) 其中f ：舻一瓣是光滑的非线性函数，矩阵a 跣“，向量b 妒，决策变量 z 舻，向量l ，u 渺u o 。) ) n ，且满足f u ( 即向量f 的每一个分量小于u 中的相应 分量) 。定义qd = e f x a x = b ，l z u l 表示问题( 2 1 1 ) 的可行集，用i n t ( f 2 ) r l = e t z l a z = b ，2 o 札1 表示问题( 2 1 1 ) 的“严格可行集”。 c o l e m a n 和l i 在【2 】中提出了双信赖域内点算法解只带有界变量约束的优化问题。 然而由于有界约束的存在，造成信赖域子问题保持内点可行性计算困难。对于具有严格 可行约束的信赖域子问题，在每一次迭代往往需要重复多次求解该子问题才能获得可接 受的严格可行步。为了克服这一困难，本文通过构造共轭梯度路径来搜索方向。b u l t e a u 和v i a l 在【1 】中提出了无约束优化问题的三条弧线路径，即共轭梯度路径、最优化路径和 修正梯度路径。朱德通教授【1 2 】成功地将最优化路径和修正梯度路径与非单调信赖域方法 相结合解决了无约束优化问题。最优路径和修正梯度路径都使用精确或非精确h e s s i a n 矩 阵的特征值和特征向量表示出来。然而对称矩阵特征系统的计算通常比较消耗时间，而 共轭梯度路径不需要计算特征系统。本文将共轭梯度路径结合内点回代线搜索技术解同 时含有线性等式约束和有界变量约束的最优化问题。由于共轭梯度路径是一组共轭方向 序列的线性组合，基于共轭方向序列的共轭性质，共轭梯度路径也具有一些重要的性 质。c o l e m a n 和v e r m a 在【3 中提出了既约预条件共轭梯度法解线性等式约束的二次规划 问题，通过一个增广系统解既约预条件方程克服了既约矩阵不保持原矩阵的充分稀疏。 基于最优性条件，问题( 2 1 1 ) 可以转化为含线性等式约束的二次规划子问题。利用广义 消去法，等式约束的二次规划子问题转化为等式约束矩阵零空间中的一个无约束优化问 题。通过在线性等式约束矩阵的零空间中构造仿射投影既约预条件共轭梯度路径解二次 模型获得迭代方向，当搜索方向不被接受时，利用回代线搜索技术得到可接受步长，使 产生的迭代步既落在严格可行域内，又保证目标函数值充分下降。由此得到的算法不仅 具有整体收敛性，而且保持快速的局部超线性收敛速率。 第6 页 第二章仿射预条件共轭梯度路径内点法 2 2 仿射预条件共轭梯度路径的构造与性质 本节考虑仿射预条件共轭梯度路径的构造，主要涉及仿射矩阵变换的选择和目标函 数的近似二次模型的建立。问题( 2 1 1 ) 的最优性条件启发选择仿射矩阵。基本思想概括如 下。 设问题( 2 1 1 ) 的拉格朗日函数为： l ( z ，y ，p ，) = ，( z ) + 7 t ( a x b ) 一，( z z ) 一r ( t 上一。) ， 其中拉格朗日乘子7 妒，p ，p 舻。对于z 是局部最优解得一阶最优性必要条件为存 在仉g p ，肌舻和n g p ，使得下面方程成立： g 。+ a t 仉一以+ = 0 ， m 0 ，0 ， a x 。= b ，z o su ，( 2 2 1 ) p ：“一z 。) = 0 ，口( u 一甄) = 0 ， 这里g 型f v i ( x 。) 。假设可行性成立，。为局部最优解的一阶必要性条件可以等价于： f ( g + + a r o ) = 0 ，若f 。： 。= 藏 2 2 1 8 ) 其中q 表示鼠相异特征值的个数。当矗+ l = o 或者最+ 1 0 ( 血+ 1 o ) 但强l 鼠d i + l o 时，上述过程终止。 仿射预条件共轭梯度路径k ( r ) 构造如下； 和 其中d 和九由( 2 2 1 6 ) 和( 2 2 1 8 ) 给出。当i = 1 时， 对于既约预条件方程( 2 2 1 5 ) 。线性系统传统的预条件策略依赖于矩阵_ c - i = 玩( 日 + 瓯) z 手。然而尽管矩阵f k + 瓯很稀疏，在实际应用中既约矩阵鼠也不一定能保持其充分 稀疏。类似于文【3 】，本文下面采用增广系统求解( 2 2 1 5 ) 。 因为a ) 是行满秩的，z ) 的行向量形成零空间( a ( z ) ) 的一组正交基，取 磊( 。) ：一 矗互娩1 r r 【 n m j r 2 2 2 1 ) 其中r 是置换矩阵，氐r = ( 五扎a 2 ) ，a k 。是非奇异的。为了简单起见，本文中假 设r = 厶。为了求解( 2 2 1 5 ) 式中的墨+ 1 ，定义如下增广系统 第9 页 坶2 口“ 如p+如 一 面 汀 。 | i pr 22 犯 、，、， “触 一 r o ，【 强m r i nm | | p 0 | | 州 令 1，j o _l i l 1，j “ “e 1j 霹o ，巩a -。l 2 2 仿射预条件共轭梯厦路径的构造与性质 其中鼠是f k + g 的稀疏对称正定近似，盈= ( a 五船) ，其中 l 是五k 1 的非奇异近 似，a 2 是a k 2 的近似，以及 = 同时在( 2 2 2 2 ) q b s ，+ 。= 嚣爵+ l ，其中磊的行向量形成零空间( 氖) 的一组基，即 磊= 一髦艘r 仁z ， 易见通过方程( 2 2 2 2 ) 求解s 等价于求解如下方程： ( 磊矾嚣) n ，= 磊， 显然逆矩阵( 磊鼠餐) 一1 可看成是凰的近似逆。 因为磊是矩阵氩的零空间的一组基所构成的矩阵，所以j + 1 = ( 0 ，厶一。) s t + l ，n n g 以不必求解2 k 。对于方程( 2 2 2 2 ) 中增广矩阵矾 叫凳警 亿z 笛， 利用m a n a b 来求解( 见【3 】) 。 2 2 2 仿射预条件共轭梯度路径的性质 下面给出仿射预条件共轭梯度路径的一些性质，并加以证明。 引理2 2 1 设d 是由( 2 2 1 6 ) 得到的方向序列，则对l i ，j z g + 1 t j 结论成立 碍由= 0 ， a 喝= 0 。 m f l = 0 ， 氐= 一m _ 1 氐 a t m d j 0 ， 1 j 0 对于e = 1 ，2 ，f 成立，于是( 2 2 3 0 ) 得证。口 引理2 2 2 设迭代步联( f ) = 聪( r ) 是由仿射预条件共轭梯友路径得到的，则满足以下性 质： 1 对于叮- ( 0 ，+ 。) ，路径的范数函数l l r ( 1 - ) 0 帆是单调递增的，这里”i i m 为椭球范 数，0 。| | “= ( 。7 。 靠。) ，、z g p 。 2 当r ( 0 ，+ 。) 时，二次近似函数( r ( r ) ) 沿着仿射预条件共轭梯度路径是单调递减 的。 3 如果凰是正定的，则 。l i m 。r e r ) = 一露1 彘 证明：为7 方便起见，将第k 次迭代省略。 i _ 一l ( 1 ) 由共轭梯度路径的定义，当 j = l ( i q ) 时， l - 1l - 1 如( r ) 2 m i n m a x o ，r 一) ) = m i n r 一) = 九 j = l ，= l 第1 2 页 r 2 2 3 7 ) 一 b 皿 即 时 0 一 0b 。州 r 同 一r = 、，b 赳 一 ra ，【 nm | | 、，- 州 一 r 宅苫m一 ，【 n皿 = 汀 瓠 b o 和 靠正定，可知业d t ! 0 。因为l i p ( r ) 1 1 m 。在r + 上连 续，所以i | p ( t ) i i m , 萄- ( 0 ，+ 。o ) 上单调递增，从而证得( 1 ) 成立。 ( 2 ) 当如 r 口) 时， 鲣d t 型地+ 驴) r 掣 第1 3 页 有时 曲 一 ob 。触 一 r( 岸 当以所 mb 岸 一 汀 + 出 同 1 1 帕 = r 血b m p + 出b 皿 r 武b 坶 一 p + 白b 博 = d峨 r ； 钮 勘 烈 一 盯 + 由峨印 m 勘 “皿 一 狮 + 嘞b 问 媳 亏 = d r 画 触 一 p + 由b “皿 巩 + 钆 = 2 2 仿射预条件共轭梯度路径的构造与性质 由矗= 氟， 凡的定义以及( 2 2 1 8 ) ，( 2 2 2 4 ) 承1 ( 2 2 3 1 ) ，有 d 于( p ( r ) ) d 下 = d 订+ ( r 一a j ) d t f t k d , j = l 曼最n + ) 、涟羁k 氐 = f 1 + = f 1 + 武m f t = 好( f 。一曩) = ( 一f 一凰由) j = l = 0 所以当r ( 0 ，+ o 。) 时，张( r ( r ) ) 沿着仿射预条件共轭梯度路径是单调递减的a ( 3 ) 如果凰正定，则上述采用精确搜索的共轭梯度法在口步后终止，元+ 1 = 0 ，因为 凰+ 1 + 饥= + 1 = o ，所以+ l = 一霞1 氩，又a 卅l = 巧f t l 瓯j q + 1 石，所以a 叶l = 0 ，从而 有i i mt q + l ( r ) = 0 ，利用( 2 2 3 9 ) 和( 2 2 1 4 ) 可得 l i r a 聪( 7 ) 即( 2 ，2 3 7 ) 式成立。口 ( 2 2 3 7 ) 意味着当凰在零空间上正定时，迭代步变为牛顿步或拟牛顿步，从而使得算 法可能具有较快的收敛速率。 引理2 2 3 设醒( r ) = 聪( r ) 是由仿射预条件共轭梯度路径得到的，则 1 目标函数的既约梯度靠和仿射预条件共轭梯度路径产生的迭代步露( r ) 的关系函 数吼( r ) 譬鲤愆( r ) 在t ( 0 ，+ 。) 上是单调递减的。 2 当o r 0 ，使得0 靠1 1 戈，从而有 吾】；( r ) = 口l 事k = 9 吾p k ( r ) 一三 f k | | 2 ( 2 2 4 1 ) 证明：( 1 ) 由引理2 1 中的( 2 2 3 8 ) 有 吐 矾 好b “州 一 r + 血 靠 = a 一 砖 触 一r k 垮霹 一 | | + i | 由b 。硝 d r 垮b 弹 一 p + 由 鳍 页 b m 博第 = 力 p 尸 瓠 = p 垂 第二章仿射预条件共轭梯度路径内点法 上式关于7 - 求导，并利用d 1 = 一 行1 蟊和( 2 2 3 0 ) n n 皇掣：粕：一a m d , 1 时 蛋t ( r ) = 口吾菇( r ) = 鳍( r d z ) = 一r 口 何1 饥一三- i l o k i l 2 由于吼( t ) 在7 ( 1 ，+ o 。) 上是单调递减的，所以 吼( r ) 0 。选取一个对称矩阵b 0 选取初始可行点z o q 舻，再令女= 0 ，转主步。 主步： 1 计算 = f ( x ) ，g k ；v ，k = v 2 ，d ， ) ，髭，a k = a d 9 1 ，弧= d i l 9 k ，仉 ) = 一【氐0 ) 盈 ) 7 】- 1 氩( 。) 甄( 写) ，分解盈，得到磊，计算日，再，氟。 2 如果l | 敛| 1 e ，则停止计算，作为最优解；否则转下一步。 3 构造仿射预条件共轭梯度路径r i ( r ) ，令多z ( 丁) = 聪( r ) ，则p a ( r ) = d i l 耀砩( r ) 。 取r = 0 0 ，“一，u 一( n - 1 ) ，一，直至下式成立 r1 ，( z k ) 一，( 。 + p t ( t ) ) ，( z k ) 一9 k ( 多( r ) ) i ，f ( 0 ，1 ) ( 2 3 1 ) lj 记满足上式的第一个r 的值为，即获得迭代方向步矶( ) 。 4 选取a k = 1 ，曰，2 ，直到下列不等式成立 f o r k + 口即h ) ) ，( ) + p 口 甄t m ( ) 并且+ a k p k ( t k ) q ， 第1 5 页 ( 2 3 2 ) ( 2 3 3 ) 2 3 算法 5 令 忙 戮孺最怕咖h 培i n t m 卜 s 川 其中巩( 仇，1 ，0 0 ，使得| l v 2 a i is ) ( ，和| i 肌+ a 7 讥1 l 。sx g 。 假设a 2 ：0 吼0 是上有界的，即对任意的瓢c ( x o ) ，存在 0 ，使得i l 风f | 。 假设a 3 ：l i v k h ) i i 是上有界的，即对任意的，存在蜘 0 ，使得忪k ) | i 洳。 假设a 4 ：存在某个正常数戈 0 ，使得l 雠( n ) | i 戈亿| l 氟 由假设a o 可知，存在 0 ，使得l i d ；1 i i ! x d 。 3 1 整体弱收敛性 下面的引理表明在第k 步迭代中，预计下降量 一( 恁h ) ) 满足“足够”下降量， 这对算法整体收敛性的证明具有重要的作用。 引理3 1 1 在第步迭代中，令醒( r ) = 联( r ) 是由仿射预条件共轭梯度路径得到的，则预 计下降量，( z t ) 一( 壤( r ) ) 满足充分下降条件，即 m 女) 一吼( 菇( r ) ) 割姗- ( 3 1 1 ) 其中趸是| i a 靠| j 的上界。 证明：当o a 1 时，由于陬( 聪( t ) ) 在r ( a 1 ，+ 。o ) 时是单调递城的，从巾 m k ) 一讯( r ) m ) 一仇( 西t 2 ( 3 l 3 ) n ( 3 1 2 ) 和( 3 1 3 ) 可得，引理3 1 1 结论成立。口 下面的引理证明了算法第三步在有限步内终止，即经过有限步的缩小r ，使( 2 3 1 ) 成 立。 引理3 1 2 在算法的第3 步中，若| | 甄j | 0 ，则 摧丽生x s x a ) x ( 3 1 4 ) “，x ( x 五十 证明：由( 2 3 2 ) 可得 f ( x k )