（应用数学专业论文）有界变量约束非线性方程组的仿射共轭梯度路径法.pdf

卜海! i l j 范人学硕上学位论文中文摘要 摘要 最优化理论与方法是一门应用性很强的学科，它研究如何从某些实际问题的众多可行 方案中找出最优的方案。最优化技术在国防、工农业生产、交通运输、金融、贸易、管 理、科学研究等许多领域中有着广泛的应用。随着计算机的发展，最优化理论和算法在 实际应用中正发挥着越来越大的作用。 共轭梯度法是最优化中常用的方法之一，它具有运算简便、只需一阶信息，以及存储 空间小等优点，共轭梯度法已成为求解大规模问题的一种主要方法。b u l t e a u 与v i a l 在【l 】 中构造了无约束最优化问题的共轭梯度路径，其基本思想是将标准共轭方向法应用于无 约束优化目标函数的局部二次近似模型，使用完全的一组共轭方向序列的线性组合定义 路径。在本文中，引入另一类仿射矩阵，并通过建立合适的二次模型，构建出仿射内点 离散的共轭梯度路径法来求解有界变量约束非线性方程组。此方法只需部分共轭梯度法 解每次迭代的近似二次模型，减少了计算步骤，从而提高了算法的运行效率。在合理的 假设下，证明了算法的整体收敛性和局部超线性收敛速率，数值结果表明了所提供的算 法的有效性和可行性。 本文又提出了不精确牛顿仿射共轭梯度法求解有界变量约束的非线性方程系组问题， 对于非线性方程组的求解，经典的的求解算法是牛顿法，此方法在初始点足够接近解时 具有良好的收敛性，然而在实际计算中对每一步迭代线性方程组的精确运算往往是困难 的，不精确牛顿法通过每步迭代方程组的近似求解，从而在一定程度上克服了这一弱 点。鉴于小精确牛顿法这一特性，将其与仿射内点离散的共轭梯度路径法相结合。通过 预条件共轭梯度法得到一系列共轭方向，然后通过不精确牛顿法来检验来找到一个下降 方向，再结合非单调技术得到下一步迭代公式。通过证明，此方法是可行的。 最后，对本文的工作进行总结，并进一步提出研究方向。 关键词：非线性方程组；仿射变换；共轭梯度法；不精确牛顿法。 一 ：海师范大学硕上学位论文英文摘要 a b s t r a c t o p t i m i z a t i o nt h e r o ya n dm e t h o d ，w h i c hm a k e sr e s e a r c ho nh o wt of i n dt h eo p t i m a ls o l u t i o na m o n gm a n yf e a s i b l ep l a n s ，i sv e r yp o p u l a ra n du s e f u ls u b j e c t o p t i m i z a t i o nt e c h n o l o g yi s w i d e l ya p p l i e di nm a n yf i e l d ss u c ha sd e f e n s e ，i n d u s t r i a la n da g r i c u l t u r a lp r o d u c t i o n ，g a n s p o r t a t i o n ，f i n a n c i a l ，g a d e ，m a n a g e m e n t ，s c i e n t i f i cr e a c h w i t ht h ed e v e l o p m e n to ft h ec o m p u t e r s ， o p t i m i z a t i o nt h e r o ya n dm e t h o di sp l a y i n ga ni n c r e a s i n gr o l ei np r a c t i c a l 叩p l i c a t i o n 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 nb ee a s 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 r s to r d e r i n f o r m a t i o nw i t hs m a l ls t o r a g e ，i so n eo ft h em o s tp o p u l a rm 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 b u r e a ua n dv i a l 【1 】f o r m e dac o n j u g a t eg r a d i e n tp a t ho fu n c o n s t r a i n e do p t i m i z a t i o n 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 gs t a n d a r dc o n j u g a t ed i r e c t i o nm e t h o dt oa p p r o x i m a t eq u a d r a t i cm o d e lo f u n c o n s t r a i n e do p t i m i z a t i o n i nt h et h e s i s ，b ye m p l o y i n gaa f f i n es c a l i n gm a t r i xa n dc o n s t r u c t i n ga s u i t a b l eq u a d r a t i cm o d e l ，w ep r o p o s eaa p p r o a c ho fa f f i n es c a l i n gi n t e r i o rd i s c r e t ec o n j u g a t eg r a - d i e n tp a t hf o rs o l v i n gn o n l i n e a re q u a l i t ys y s t e m ss u b j e c tt ob o u n d so nv a r i a b l e t h i sm e t h o do n l y n e e d st oc o n s t r u c tp a r to ft h ec o n j u g a t eg r a d i e n tp a t ht os o l v et 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 n a te v e r yi t e r a t i o ns u c ht h a tt or e d u c et h ec o m p u t a t i o na n di m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h m g r e a t l y g l o b a lc o n v e r g e n c ea n dl o c a ls u p e rl i n e a rc o n v e r g e n c er a t eo ft h ep r o p o s e da l g o r i t h m a r ee s t a b l i s h e do ns o m er e a s o n a b l ec o n d i t i o n s 伯en u m e r i c a lr e s u l t so ft h ep r o p o s e da l g o r i t h m i n d i c a t et ob ee f f e c t i v e f o rs o l v i n gt h ec o n s t r a i n e dn o n l i n e a re q u a t i o n s ，w ep r o p o s eam e t h o do fi n e x a c tn e w t o n a f f i n es c a l i n gi n t e r i o rd i s c r e t ec o n j u g a t eg r a d i e n tp a t h ac l a s s i c a la l g o r i t h mf o rt h ep r o b l e mi s n e w t o n sm e t h o d t h em e t h o di sa t t r a c t i v eb e c a u s ei tc o n v e r g e sr a p i d l yf o ra n ys u f - f i c i e n d yg o o d i n i t i a lp o i n t h o w e v e r , s o l v i n gas y s t e mo fl i n e a re q u a t i o n se x a c t l ya te a c hs t a g ec a nb ee x p e n s i v e i ft h en u m b e ro fu n k n o w n si sl a r g e b u tt h ed r a w b a c k sc a l lb eo v e r c o m e dt os o m ee x t e n ti fw e s o l v e dl i n e a re q u a t i o n si n e x a c t l ya c c o r d i n gt ot h i sc h a r a c t e r i s t i c ，w ec o m b i n ei tw i t hd i s c r e t e c o n j u g a t eg r a d i e n tp a t h w ec a no b t a i nas e q u e n c eo fc o n j u g a t ed i r e c t i o nb yt h ep r e c o n d i t i o n e d c o n j u g a t eg r a d i e n tm e t h o d c h e c k e db yt h ei n e x a c t n e w t o nm e t h o d ，w ew i l lg e tad e s c e n td i r e c t i o n c o m b i n i n gw i t ht h en o n - m o n o t o n et e c h n i q u e 。w ew i l lf i n da na c c e p t a b l et r i a ls t e pl e n g t h a l o n gt h i sd i r e c t i o nw h i c hi ss t r i c t l yf e a s i b l ea n dm a k e t h eo b j e c t i v ef u n c t i o nd e c r e a s i n g u n d e r s o m er e a s o n a b l ea s s u m p t i o n ，t h ef e a s i b i l i t yo ft h ea l g o r i t h mi sp r o v e d f i n a l l y , t h el a s tc h a p t e rc o n c l u d e st h em a i nr e s u l t so ft h i sp a p e ra n dp r o p o s e ss o m ef u r t h e r r e s e a r c hd i r e c t i o n s i i 卜海师范大学硕士学位论文 英文摘要 k e yw o r d s ： n o n l i n e a re q u a t i o n s ；a f f i n es c a l i n g ；c o n j u g a t eg r a d i e n t ；i n e x a c tn e w t o n i i l 一卜海师范大学硕j j 学位论文主要符号对照表 渺 舻m i i i l ，”1 1 2 1 1 g ( z ) v 2 y ( x ) d ( x ) 入，p ，薹， l ( x ，p ，) f ( x ) f 7 ( z ) q i n t ( f 1 ) i ，u x 矿 z 蠡，z p k c t k r k m k 主要符号对照表 1 1 , 维实向量牢间 1 1 , m 维实矩阵 e u c l i d 范数 o o 范数 ，在z 处的梯度，即v f ( x ) j p 在z 处的h e s s e 阵 尺度矩阵 l a g r a n g e 乘子 约束优化问题的l a g r a n g e 函数 非线性映射咿_ 舻 j a c o b i a n 矩阵 可行集 严格可行集 有界约束下界，上界向量 非线性方程组的精确解 向量z 的第i 个分量 第k 步迭代点及其迭代点的第i 个分量 第k 步搜索方向 第k 步线性搜索因子 残量序列 第k 步仿射矩阵 v i 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别 加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究成果。其他同 志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表示了谢意。 作者签名：日期： 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以 采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此规定。 作者签名： 上海师范大学硕士学位论文第章最优化理论基础 第一章最优化理论基础 1 1 最优化问题简介 最优化是一门应用十分广泛的学科，它研究在有限或无限种可行方案中挑选最优方 案，构造寻求最优解的计算方法。在电子计算机的推动下，最优化理论与方法在经济计 划、工程设计、生产管理、交通运输等方面得到了广泛应用。 最优化问题的数学模型一般形式为： m i nf ( z ) s t c i ( x ) = 0 ，i ， ( 1 1 1 ) q ( z ) 0 ，i z ， 其中f ：舻一跪1 ，q ：舻一驼1 ，x 舻称为决策变量，f ( z ) 称为目标函数，龟( z ) 是约束函数，和z 分别是等式约束的指标集 1 ，2 ，m ) 和不等式约束的指标集 m + 1 ，m + 2 ，p ) 。问题( 1 1 1 ) 的可行域定义为集合： q d = e f zic t ( z ) ：0 ，i ；c i ( z ) 0 ，i z ) ( 1 1 2 ) 当要求不等式约束等号不满足时，可行域成为“严格可行域”，即( 1 1 1 ) 的严格可行域 为： i n t ( q ) d = e f zl 龟( z ) ：0 ，i 占；q ( z ) 0 ，i z ) ( 1 1 3 ) 对于一个可行点x ，所有的等式约束都被认为是有效约束。考虑不等式约束q ( z ) 0 ，如果有q ( z ) = 0 ，就称约束q ( z ) 20 在点z 是有效约束或起作用约束；如果有 龟( o ) 0 ，就称不等式约束龟( z ) 0 在点z 是无效约束或不起作用约束。如果所有的不 等式约束都是不起作用约束，就称x 是可行域的内点。 若模型( 1 1 1 ) 中含有约束条件，即称模型( 1 1 1 ) 为约束优化问题。当约束中只有等 式约束时，则称为等式约束最优化问题；当约束中只有不等式约束时，则称为不等式约 束最优化问题；如果既有等式约束，又有不等式约束，则称为混合约束问题。 若模型( 1 1 1 ) 中不含约束条件，即q = 舻，称模型( 1 1 1 ) 为无约束优化问题，一般 简记为 m i n ，( o ) 第，章最优化理论基础 上海师范大学硕+ 学位论文 1 ，2 最优性条件 最优性条件是指最优化问题( 1 1 1 ) 的最优解( 局部的或全局的) 所必须满足的条件。常 见并常用的是一阶必要条件和二阶必要条件。最优性条件不仅对于最优化理论的研究具 有重要意义，而且对最优化算法的设计和终止条件的确定起重要作用。 定义1 2 1 设z 。q ，4 ( z 。) 是起作用约束集，如果或者所有的 q ( z + ) ，i 4 ( 甄) ) 都是 x 的线性函数，或者 v q ( 飘) ，i 4 ( 文) ) 线性无关，则称问题( 1 1 1 ) 具有线性无关约束 品性。 为了更方便地讨论约束优化问题的局部极小点的最优性条件，我们引入约束优化问题 ( 1 1 1 ) 的拉格朗日函数： p l ( x ，a ) = ，( z ) 一九q ( z ) ， ( 1 2 1 ) i = l 其中a 称为拉格朗日乘子。 首先我们给出最优解的一阶必要性条件，称为k u h n t u c k e r 条件。 定理1 2 1 ( 3 5 1 ) 设z 。q 是问题( 1 1 1 ) 的局部最优解，若在z 。点线性无关约束品性成 立，则存在向量k = ( 入1 一，理) t ，使得 v 茁l ( x 。，九) = 0 ， ( 1 2 2 ) 圮0 ，i z ，( 1 2 3 ) a ：q ( z 。) = 0 ，i z ( 1 2 4 ) 把( 1 2 2 ) 一( 1 2 4 ) 称为问题( 1 1 1 ) 的一阶必要性条件或k k t 条件。满足此条件的 点称为k u h n t u c k e r 点或k k t 点。( 1 2 4 ) 式称为互补松驰条件。如果对任意i z ，定 和龟( z 。) 中有且只有一个取零值，则称为严格互补松驰条件成立。 由定理1 2 1 立即可得无约束最优化问题的一阶必要性条件为 v f ( x 。) = 0 接着我们给出最优解的二阶必要条件。 定理1 2 2 ( 【3 5 】) 设x + q 是最优化问题( 1 1 1 ) 的最优解，且函数，( z ) 与q ( z ) ，i = 1 ，2 ，p 二阶连续可微又设定理1 2 1 中的约束规范条件在点z 。成立，从而存在拉格 朗日乘子向量尢使k - k - t 条件成立。如果严格互补松弛条件在z 。成立，则： s t v ：= l ( x 。，入。) s 0 对一切满足 2 s r v c ( z 。) = 0 ，i 4 ( z 。) 上海师范大学硕十学位论文第一章最优化理论基础 的方向8 均成立 最后，给出最优解的二阶充分条件。 定理1 2 3 ( 【3 5 】) 设最优化问题( 1 1 1 ) 的函数，( z ) 与q ( z ) ，i = 1 ，2 ，仇均二阶连续 可微，在可行点x 。处定理1 2 1 的约束规范条件成立，若存在拉格朗e l 乘子向量入+ 使 k t - t 条件和严格互补松弛条件成立，且对所有满足 的非零向量8 有 s r v c 4 ( z 。) = 0 ，i a ( z + ) s t v z 2 霉l ( x 。，入。) s 0 ， 则z 。是问题( 1 1 1 ) 的一个严格局部最优解。 1 3 最优化方法的结构 通常采用迭代方法求解问题( 1 1 1 ) 的最优解。其基本思想为：给定最优解一个初始 估计点x o 渺，按照某一迭代规则产生一个迭代序列 z ) ，使得当 。惫) 是有限点列 时，其最后一个点是最优化模型问题的最优解：当 z 七) 是无限点列时，它有极限点，且 其极限点是最优化模型问题的最优解。 一般情况下，最优化问题求解的具有以下基本迭代格式： 算法1 3 1 ( 最优化方法的基本迭代格式) 1 给定初始点x o ，k 卜o 。 2 确定搜索方向p 知，即按照一定规则，构造目标函数在x k 点处的下降方向作为搜索方 向。 3 确定步长q 七使目标函数有某种意义下的下降。 4 取下一个迭代点x k + l = z 七+ o r k p k 5 判别x k + 1 是否满足终止准则。若满足，则停止迭代，x k + 1 是近似局部最优解；否 则，k 卜k + 1 转第2 步。 在以上迭代格式中，关键的两步是构造搜索方向m 和确定步长口南。不同的构造方向 p 七和确定步长q 七构成了不同的算法。线搜索策略和信赖域策略是保证最优化方法整体收 敛的两类技术。一个好的算法应具备的典型特征是：迭代点z 七能稳定地接近局部极小值 点z 。的邻域，然后迅速收敛于文。因此，收敛速度也是衡量最优化方法有效性的重要方 面。设序列 z 七) 在某种范数意义下收敛于z 。，即 1 i mi l z 七一x + i i = 0 ( 1 3 1 ) 3 第，+ 章最优化理论基础 上海师范大学硕士学位论文 若存在实数q 0 及一个迭代次数k 无关的常数q 0 ，使得 k l i - - m * o o 鬻_ g ， ( 1 3 2 ) i | z 南一z 。驴 、 则称算法产生的迭代序列( z 七) 具有q q 阶收敛速率。特别地， ( 1 ) 当q = l ，1 q 0 时，迭代点列【瓤) 叫做具有q 线性收敛速率； ( 2 ) 当1 0 时，迭代点列 z 知) 叫做具有q 一二阶收敛速率。 一般来说，具有超线性收敛速度和二阶收敛速度的方法是比较快速的。但是，对任 何一个算法，即使已证得收敛性和收敛速度的理论结果，这也并不代表算法在实际执行 时一定有好的实际计算结果。这主要有两方面原因：一是由于这些结果本身并不能保证 方法一定有好的特性，二是由于它们忽略了计算过程中十分重要的舍入误差的影响。另 外，这些结果通常要对函数，( z ) 加上某些约束，这些约束条件在实际上并不一定能得到 满足。因此，一个最优化方法的开发还有赖于数值实验。这就是说，通过对有代表性的 检验函数进行数值计算( 通常采用m a t l a b 语言进行编程计算) ，一个好的算法应该具有可 以接受的特性。显然，数值实验并不能以严格的数学证明保证算法具有良好的性态。理 想的情况是根据收敛性和收敛速度的理论结果来选择适当的数值实验。 下面的定理给出了算法超线性收敛的一个特征。它对于构造终止迭代所需的收敛准则 是有用的。 定理1 3 1 如果序列 z 詹) q 一超线性收敛到双，那么 k l i - - m * o o 锗“ ( 1 - 3 3 ) l | z 知一z 但反之一般不成立。 算法的另一个重要特征为终止迭代所需要的终止准则。我们有时采用 或 x k + l x k l | e l ( 1 3 4 ) ，( z 七) 一f ( x k + 1 ) e 2( 1 3 5 ) 来作为终止准则。终止准则( 1 3 4 ) 和( 1 3 5 ) 对于一些预计会有较快收敛性的算法是比较 理想的。对于有一阶导数信息的目标函数，且收敛不太快的算法，例如共轭梯度法，可 以采用如下迭代终止准则： 4 v f ( x k ) l i s 3( 1 3 6 ) 上海师范大学硕士学位论文 第一章最优化理论基础 一般地，可取1 = e 2 = 1 0 一，3 = 1 0 。 求解最优化问题，大多数是从构造二次函数模型导出的。这种模型的方法通常是有效 可行的。其主要原因是一般函数在极小点附近常可用二次函数很好地进行近似。所谓二 次终止性是指当算法应用于一个二次函数时，只要经过有限步迭代就能达到函数的极小 点z 。因此，对于一般函数而言，具有二次终止性的算法可望在接近极小点具有很好的 收敛性质。 1 4 预条件共轭梯度法 共轭梯度法是最著名的共轭方向法，它首先由h e s t e n e s 和s t i e f e l ( 1 9 5 2 ) 提出来作为 解线性方程组的方法，由于解线性方程组等价于极小化一个正定二次函数。在这个基础 上，f l e t c h e r 和r e e v e s ( 1 9 6 4 ) 提出了无约束极小化的共轭梯度法。由于共轭梯度法存储量 小，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际 问题中。 对于极小化正定二次函数 1 m i n f ( x ) = 去。t g 茁+ b t x + e ， ( 1 4 1 ) 正 厶 其中g 是n n 对称正定矩阵，b 是佗1 向量。 一般的共轭梯度法中，a 知由精确线性搜索得到， p k + 1 = - g k + 1 + 反p 岛， 仇：鳝募鱼型( c r 。w d e r - w o l f e 公式) 雕( g k + x g k ) ：g ：；6 + 彳l g k + l ( f l e t c h e 卜r e e v e s 公式) g 女g k 另外两个常用的公式为 风：亟逝型 g 五g k ( 1 4 2 ) ( 1 4 3 ) ( 1 4 4 ) ( 1 4 5 ) ( p o l a k - r i b i e r e p o l y a k 公式)( 1 4 6 ) 反：一篮土；里坐( d i x o n 公式) ( 1 4 7 ) 上面的公式虽然看起来比最速下降法稍微复杂一点，但共轭梯度法具有二次终止性， 所以共轭梯度法还是受到大多数关注的方法。 此外共轭梯度法产生的序列 z ) 满足 忪一川g ( 蒜一一蚓i g 4 固 其中a 1 和k 分别是g 的最大和最小特征值，k ( g ) = l i g | 1 2 l i g _ 1 1 1 2 = 鸯1 是矩阵g 的 条件数。 第一章最优化理论基础上海师范大学硕士学位论文 由( 1 4 8 ) 可以看出，共轭梯度法的收敛速度依赖于 石而，而不是k ( g ) ，因此如果能 够采取某种措施改善g 的条件数，就可以加快收敛速度。下面给出了解决这个问题的一 个办法。 设c 是某个非奇异矩阵，令岔= c x ，则二次目标函数( 1 4 1 ) 变成 叫n ，( 仝) = 去岔t ( c t g c 一1 ) 金+ ( c t 6 ) t 圣- t - c ( 1 4 9 ) 茁么 这时，方法的收敛速度依赖于c _ t g c _ 1 的条件数而不是g 的条件数。如果能够选择非 奇异矩阵c 使得c 刁g c _ 1 的条件数明显好于g 的条件数，则收敛速度将明显改善。根 据这个思想，我们定义m = c r c ，并给出下面的预条件共轭梯度法。 算法( 预条件共轭梯度法) 步1 初始步：给定x o ，s 0 ，预条件矩阵m ，令g o = g x o + b ，解m y o = g o 得珈，令 p o = 一珈，k ：= 0 。 步2 如果g k ，停止。 步3 计算 解m y = g k + 1 得玑+ 1 ， 步4 令k ：= k + 1 ，转步2 。 一撩t ， x k + l2x k + q 詹p 七， g k + 1 = 鲰- - t - o l k g m ， 凤= 紫y k ，鳙 p k + 1 = 一纨- t - 1 + 熊p 七， 显然，如果令m = i ，则预条件共轭梯度算法就是标准的共轭梯度算法。 1 5 不精确牛顿法 6 在叙述不精确牛顿法之前，我们先对给出非线性方程组一般定义： r ( x ) = 0 ，( 1 5 1 ) 上海师范大学硕士学位论文第。章最优化理论基础 巾，蜒) 令 f 7 ( z 知) s 知= - - f ( z k ) ( 1 5 5 ) x k + l2z 七+ 8 k( 1 5 6 ) 7 第一章最优化理论基础上海师范大学硕士学位论文 现考虑不精确牛顿法：解 其中 令 f ( x k ) s k = - - f ( x k ) + r k ( 1 5 7 ) 热佻 ( 1 5 8 ) x k + l = x k + 乳( 1 5 9 ) 这里飞= f ( x k ) s k 4 - f ( x k ) 表示残量，讯是一个控制不精确程度的序列。如果讯兰o ，则 不精确牛顿法就是牛顿法。 下面，我们在序列 讯卜一致小于1 的条件下给出不精确牛顿法的局部收敛性。 引理1 5 1 设f ：舻_ 舻在z 。d 连续可微，f ，( z 。) 非奇异，则存在6 0 3 , 0 , e 0 ， 使得当恬一z 。0 6 ，y d 时，f 7 ( 可) 非奇异，且 i i f 7 ( 可) - 10 ，y( 1 5 1 0 ) 此外，f ( 秒) _ 1 在z 。处连续，即 i if ，( 秒) 一f ， + ) _ 10 e( 1 5 1 1 ) 定理1 5 1 设f ：舻_ 舻具有( 1 5 4 ) 式中的三个条件，设 吼) 是一个实数序列满 足0 讯r m 。 0 是两个给定的常量。 定义内点仿射矩阵为 d ( x ) 型f d i a g ( 1 ( z ) ，矽n ( z ) ) ( 2 1 6 ) 则( 2 1 3 ) 式的必要条件是： d ( x ) v f ( x ) = 0 ( 2 1 7 ) 为使解( 2 1 7 ) 式，令矽= d k p ，则p = d - ；1 f ，其中d 詹= d ( x k ) ，在x k 有下面的仿射二次 模型 砜p ) = 丢p t d k l f ( x k ) t f ( x k ) d i l p + f ( z 知) t f 7 ( x k ) d i l f + 互1 f ( 现) t f ( x k ) ( 2 1 8 ) 下面我们将给出求解( 2 1 3 ) 问题的离散的仿射共轭梯度法的算法。 第二章仿射共轭梯度路径法 上海帅范大学硕i ：学位论文 2 2 算法 离散的共轭梯度法所构成的搜索方向p k 仅仅是负梯度方向一鲰与上一次迭代的搜索 方向m 一1 的组合，从而具有存储量少，计算方便的良好性态。 下面从构建仿射共轭路径求解仿射子问题( 2 1 8 ) ，给出完整的算法： 初始步：选定参数p ( 0 ，；) ，( 0 ，1 ) ，u ( 0 ，1 ) ， 0 ，7 = 1 ，初始可行点 x o f ，“】舻，令k = 0 转主步。 主步： 计算f k = f ( x k ) ，冠= f 7 七) ，d k ，m k = d 2 ，g k = 咒t r ，玑= d i l 鲰。 如果i i d ；1 鲰i i e ，则停止计算，z 七作为最优解；否则转下一步。 置v o = 0 ，r o = g k ，m k s o = r o ，解得8 0 ，令- s o = d 0 = 一晖1 9 k ，置i 卜0 。 计算q i = 唬，检验： 嚷t 吼0 d i l r i 0 若( 2 2 1 ) 和( 2 2 2 ) 式都满足，转下一步，否则转步6 。 计算 检验： r i + 1 = r i + 凡( ) t 吼， 尥s 件l = r i + l ， 屈+ 1 ：_ 二r = 1 = ， d i + l = - 8 i + 1 + 展+ 1 也 ( 2 2 1 ) ( 2 2 2 ) ，( z 七) 一( z k + v i + 1 ) ( 厂( z 南) 一m k ( v i + 1 ) 】( 2 2 3 ) 若( 2 2 3 ) 式满足，置i 卜i + 1 ，转步4 ，否则转下一步。 当i = 0 ，p k = d o ；i = 1 ，p k = v l ；i 2 ，p 七= 仇一l 。 l o 也，九垫如时 = = 九 h 上海师范大学硕士学位论文第二章仿射共轭梯度路径法 选取q = 1 ，叫，u 2 ，直到下式成立 ，( z 南+ q m ) ，( z 知) + 胆纸t m ， 并且x k + 慨【1 ，u 】。 记第一个满足上式的o l 的值记为q 七。 令 注释： r i o l k p k ， h k = i 以o e k p k ， 、 当x k + o e k p k ( z ，z t ) 时； 否则， 其中巩( o t ，1 】，0 0 1 0 假设当小于等于j 时( 2 3 1 ) ( 2 3 5 ) 式成立，下证歹+ 1 时也成立。由 印磁彤+ 1 = 砑q + l = 毋( 吩+ t 劬) = 露巧+ a j q ，q j ， 当0 i j 一1 时，由归纳假设知，上式为0 。当i = j 时， 4 d 2 s m = r m = 呓寸 + 入j f 陶= 喝r j + 丽r t s j 哪t j 所以( 2 3 1 ) 式成立。由 = 哆( s j + 略) = 岛哆而一= 0 ， r t d ；2 巧+ 1 = r t d k 2 ( 吩+ t 彩) = r t d ；2 巧+ ( 一也+ 屈哦一1 ) t t 劬， = r t d ；2 巧一瓯t 钐+ 屈衣l 彩， 当0 i 歹一1 时，由归纳假设知，上式为0 。当i = j 时， t d - 2 r j + 1 = - 吒啼j 。j 霹q j “j 罅谭 = 吒啼j 一磊r t s j 蛳t = 吒d i 2 r j 一吒d i 2 r j = 0 1 所以( 2 3 2 ) 式成立。又由 一劬+ = 一( 一勺+ t + 岛+ d j ) = 一( 鱼去 ) t 班2 巧+ - + 岛+ ，谚 = _ 1l t l t 七- 2 吩+ l 一瞬ld i 2 吩+ 1 ) + 岛+ 1 一劬， i 当0 i j 一1 时，由归纳假设知，上式为0 。当i = 歹时， 1 2 盼= 一磊q t q j 研v1 8 j + 1 + 警如- o 上海师范大学硕士学位论文第二章仿射共轭梯度路径法 可得，( 2 3 3 ) 式也成立。由 刃d 2 奶+ = 毋d 2 ( 一句+ + 岛+ - 呜) = 一毋d 2 勺+ ，+ 岛+ ，毋d 2 如= 岛+ - d t id 2 吗， 当0 i j 一1 时，由( 2 3 4 ) 及岛+ 1 0 知，上式大于0 。当i = j 时， 4 d 2 d j + 1 = 岛+ 巧d 2 奶 0 ， 所以( 2 3 4 ) 式成立。因为 略1 吩+ 1 = ( 一勺+ 1 + 岛+ 1 奶) t 巧+ l 从而( 2 3 5 ) 式成立。 口 = 一再1 啊1 = 一r j + x v i 2 啊1 ，2 一丐+ 1 吩+ 12 一 。巧+ 1 ， 以下三个引理说明共轭梯度路径的单调递增性，二次函数的单调下降性以及相应的充 分下降条件。 引理2 3 2 ( 1 ) 设是南算法第5 步产生的迭代点列，则范数单调增 d k v j l l 2 i i d 知+ 12 ，0 歹t t k 一1 ( 2 ) 对于二次函数m 七( p ) = + d p + p t 展t f t p ，有二次目标函数单调减 m 知( 吻+ 1 ) 。1 ，0 j 一1 m k ( v j ) 0 n k 1 m 知( 吻+ ) 0 ，可得 从而 一1 一1 = 伽+ 九也= 九也， i = oi = 0 j - 1j - 1 哆d 2 嘭= ( 九也) t d 2 奶= 九d 孑d 2 略 0 ， i = 0 i = 0 d 忌v j + ll l ；= 略。d 2 v j + i = ( + 奶) t d 2 ( + 奶) = 哆d ；+ 2 哆d 2 而+ 智2 哆上七2 略 ( 2 3 6 ) ( 2 3 7 ) ( 2 3 8 ) 1 3 第二章仿射共轭梯度路径法上海师范大学硕士学位论文 所以( 2 3 6 ) 式成立。 i l 仇幢 ( 2 ) 当巧0 时，有哆s j = 哆d i 2 吩 0 ，醪劬 0 ，则 2 最d j + 吒s j = 嘁d j + 吒d 三2 r j =锄鼍a 一屯下 = 穗a + 吧t o r n j - 1 = 碍如+ 亏( 伯一r o 一九t q i ) = r 手而= 一舔d ；如 0 ， i = 0 由引理3 1 中预条件共轭梯度的性质，可得 m 知( + 1 ) 一m 知( ) = 夕蚕( + 1 一) + 互1 t + 1 r + l 一互1 t r - - 七! t = x j g 吾g j + 吉( 九也) t t e 九吨一去 。i = 0 i = 0 。 = 夕吾奶+ 互1 - - 2 劬t 劬 = 雾飒+ 互1 百( r t s j ) 2 吗s j q 最d j + 吗s 囊 从而( 2 3 7 ) 式成立。 ( 3 ) 由( 2 ) 的证明结论，知 2 醪劬 0 j 一1j - 1 九也) t t 凡哦 i = 0 砜( 巧+ - ) 一而岛( 巧) = 靠( 弓+ 。一弓) + 互1 _ u j t + ，d i l t 巧1