（应用数学专业论文）等式约束优化问题的非单调信赖域算法.pdf

太原理工大学硕士研究生学位论文 等式约束优化问题的非单调信赖域算法 摘要 对于一般的约束优化问题，信赖域方法是一种比较有效的方法。本 文就等式约束优化问题，结合当前比较流行的非单调技术，提出了一种 求解等式约束优化的非单调信赖域算法。其非单调程度由算法自适应控 制，计算预测下降量和实际下降量的比值时，采用前跏( 七) 个点的信息， 这不同于以前在计算预测下降量和实际下降量的比值时仅仅采用当前一 个点的信息。我们取增广l a g r a n g e 函数为价值函数。信赖域予闯题与文 献 3 2 中的信赖域子问题是相似的。在求解信赖域子问题时，我们把它 等价的变换为简单易解的无约束优化的信赖域子问题。在没有正则性条 件的假设下我们证明了算法是有定义的，并且通过对不同情况的讨论证 明了算法的全局收敛性。基本的数值试验表明算法是有效的，且说明非 单调信赖域算法比单调信赖域算法有效。本文共分五章： 第一章对信赖域算法及国内外在等式约束优化问题方面的研究现状 作了一个描述。 第二章是预备知识，主要给出了一些重要概念和一些重要定理。 第三章给出了非单调信赖域算法的模型及信赖域子问题的求解。 第四章我们首先证明了算法是有定义的，其次在没有正则性条件的 假设下证明了算法的全局收敛性。 第五章用实例做了数值试验，表明非单调信赖域算法比单调信赖域 太原理工大学硕士研究生学位论文 算法有效。 关键词：信赖域算法，非单调算法，全局收敛，等式约束 盔堡里三2 1 堡主堑塞生堂垡堡壅 n o n m o n o t o n et r u s tr e g i o n a l g o r i t h mf o r e q u a l i t y c o n s t r a i n e do p t i m i z a t i o n a b s t r a c t t r u s tr e g i o nm e t h o di sak i n do fe f f i c i e n ta n dr o b u s tm e t h o dt o s 0 1 v e g e n e r a lc o n s t r a i n e do p t i m i z a t i o n t h i st h e s i sc o m b i n e st h en o 衄o n o t o n e t e c h n i q u ea n dp r o p o s e san o n m o n o t o n et r u s t r e g i o na l g o r i t h mt os 0 1 v e e q u a l i t yc o n s t r a i n e do p t i m i z a t i o n t h en o n m o n o t o n ed e g r e ei sc o n t r o l l e db y a l g o r i t h ms e l f - a d a p t , w h e nw ec a l c u l a t et h er a t i oo f p r e d i c t e dr e d u c t i o na n d a c t u a lr e d u c t i o n ，w ea d o p tt h ei n f o r m a t i o no ft h ef r o n t a l m ( t ) d o t s i ti s d i f f e rf r o mp r e v i o u s l ya d o p t e dt h ei n f o r m a t i o no f t h ef r o n t a lad o tw h e n 、v e c a l c u l a t et h er a t i oo fp r e d i c t e dr e d u c t i o na n da c t u a l r e d u c t i o n t h em e r i t f u n c t i o ni sa u g m e n t e d l a g r a n g ef u n c t i o n t r u s tr e g i o ns u b p r o b l e mi ss i m i l a r t oo n ei n 3 2 】w h e nw es o l v et h et r u s tr e g i o ns u b p r o b l e r r bw e e q u i 训e n t l y t r a n s f o r mi ti n t ou n c o n s t r a i n e dt r u s tr e g i o ns u b p r o b l e m w ep r o v e 廿l a tt 1 1 e a l g o r i t h mi sw e l ld e f i n e da n dt h eg i o b a lc o n v e r g e n c eo fm e t h o di so b t a i l l e d 、) l ，i t i l o u tr e g u l a rc o n d i t i o n s p r e l i m i n a r yn u m e r i c a lr e s u l t ss h o w t h ea l g o 删_ l i i l i se f f e c t i v e ，a n dn o u m o n o t o n et r u s tr e g i o na l g o r i t h mi s m o r ee f f e c t i v et h 姐 i i i 查匾垄三盔堂亟主婴塞皇堂焦堡塞 m o n o t o n et r u s tr e g i o na l g o r i t h m t h e r e a r ef i v ec h a p t e r si nt h i s p a p e r a l t o g e t h e r ： i nc h a p t e r1 ，w ed e s c r i b et r u s tr e g i o na l g o r i t h ma n do v e r v i e wa b o u t e q u a l i t yc o n s t r a i n e do p t i m i z a t i o n i nt h ew o r l d i nc h a p t e r2 ，s o m ei m p o r t a n tc o n c e p t sa n dt h e o r e m sa l eg i v e n i nc h a p t e r3 ，t h em o d e lo nn o n m o n o t o n et r u s tr e g i o na l g o r i t h ma n dt h e m e t h o dh o wt os o l v et r u s tr e g i o ns u b p r o b l e ma r eg i v e n i nc h a p t e r4 ，w ep r o v et h a tt h ea l g o r i t h mi sw e l ld e f i n e da n dt h eg l o b a l c o n v e r g e n c eo f m e t h o d i so b t a i n e dw i t h o u tr e g u l a rc o n d i t i o n s i nc h a p t e r5 ，p r e l i m i n a r yn u m e r i c a lr e s u l t ss h o wt h ea l g o r i t h m i s e f f e c t i v e ，a n dn o n m o n o t o n et r u s tr e g i o nm g o r i t h mi s m o r ee f f e c t i v et h a n m o n o t o n et r u s tr e g i o na l g o r i t h m k e yw o r d s ：t r u s tr e g i o na l g o r i t h m ，n o n m o n o t o n ea l g o r i t h m ，g l o b a l c o n v e r g e n c e ，e q u a l i t yc o n s t r a i n t s 太原理工大学硕士研究生学位论文 符号说明 x ：n 维列向量。 r 一：雄维实向量空间。 w ，g ：目标函数厂( 功的梯度向量，g = v ( x ) = ( 善，拳7 。 v ：( 力：厂的h e s s i a i l 矩阵，其第f 行第，列的元素为蓑筹。 c ( 功：向量约束函数，c ( 力= ( q ，( x ) ) 7 ，其中q ( 力是第f 个约束函数。 4 ( x ) ：以v q ( 功为列的矩阵，彳( x ) = v c = ( v q ， ) ) 。 a r ：矩阵4 的转置。 ( ) + ：矩阵的广义逆。 i i i i ：向量或矩阵的e u c l i d 范数。 ( 鬈) ：鬈的核空间。 v i 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：垒空至日期： 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名： 导师签名： 日期： 日期：2 0 0 6 ! ) - 3 一 蕴 太原理工大学硕士研究生学位论文 第一章绪论 在这一章，我们首先对信赖域方法作了简述，然后给出所研究问题的基本状况及 国内外研究现状，最后给出本文对此问题的研究所得出的结论。 1 1 信赖域方法简介 信赖域方法是非线性最优化的一类重要的数值计算方法。非线性最优化是2 0 世纪 5 0 年代发展起来的。它讨论非线性决策问题的最佳选择之特性，构造寻求最佳解的计 算方法，研究这些计算方法的理论性质及实际计算表现。随着电子计算机的发展和应 用，非线性最优化理论和方法有了很大发展。目前，它已成为运筹学的一个重要分支， 并且在自然科学、工程技术、经济管理、系统工程，特别是“优化设计”等诸多领域 得到广泛的应用，成为一门十分活跃的学科。 非线性优化的传统方法几乎都是线搜索类型的方法“，即每次迭代时产生一搜索 方向，然后在搜索方向上进行精确的或不精确的一维搜索，以得到下一个迭代点。信 赖域方法是一类很新的方法，它和线搜索法并列为目前求解非线性规划的两类主要的 数值方法。信赖域方法思想新颖，算法可靠，具有很强的收敛性“，它不仅能很快地 解决良态问题，而且也能有效地求解病态的优化问题。因而对信赖域方法的研究是近 2 0 年来非线性规划领域的一个重要的研究方向，是当今寻求如何构造新的优化计算方 法的主要途径。 信赖域方法的研究起源于p o w e l l l 9 7 0 年的工作啊，他提出了一个求解无约束优化 问题的算法。该算法在每次迭代时强制性地要求新的迭代点与当前的迭代点之间的距 离不超过某一控制量。引入控制步长是因为传统的线搜索方法常常由于步长过大而导 致算法失败，特别是当问题是病态时尤为如此锄控制步长实质上等价于在以当前迭 代点为中心的一个邻域内对一个近似于原问题的简单模型求极值。这种技巧可理解为 只在一个邻域内对近似模型信赖，所以此邻域被称为信赖域( t r u s tr e g i o n ) 利用这一 技巧的方法也就被称为信赖域法。信赖域的大小通过迭代逐步调节。一般来说，如 太原理工大学硕士研究生学位论文 果在当前迭代模型较好地逼近原问题- 则信赖域司扩大，否则信赖域应缩小后来， 人们发现信赖域方法的基本技巧在一定意义下等价于十分著名的求解非线性最小= 乘问题的l e 伽b e 蟹m a r q u a d t m 方法。对于非线性最小二乘问题： n 。l i 胪n i if ( x ) 1 1 2 ( 1 1 ) f ) = ( 石( 功，厶( x ) ，厶( 砌7 和z ( 力q = l ，2 ，州) 是掣中连续可微的函数，i 表示中的毛范数，g a t l s s 她w t o n 方法是： “= + 以= x k 一( d ( x d t ，( ) ) _ 1 j ( x d 7 f ( x d ( 1 2 ) 其中，( 功是f ( x ) 的j a e o b i 矩阵，且， ) 是列满秩的。不难看, q 4 , g a u s s - n e w t o n 步是 以= 一似) 7 ，瓴) ) 。1 以磁) 7 f 瓴) 是问题： m i if ( x , ) + s ( x , ) a 1 1 2 ( 1 3 ) 的解。显然，( 1 3 ) 是问题( 1 1 ) 在当前迭代点黾的近似。当j a c o b i 矩阵j ( x d 几乎 奇异时，g a u s s - n e w t o n 步吒= 一( 黾) 7 j ( 故) ) 。，( 磁) 7 f ( x k ) 很可能会非常长，从而使 g a _ i l s s - n e w t o n 方法出现数值困难。为克服这种困难，i 自l e v e n b e r g 提出并由m a r q u a d t 重新发现的l e v e n b e r g - m a r q u a d t 方法利用如下步： 以= 一u 魄) 7 j ( x k ) + a k i ) - 1 ，瓴) 7 f 瓴) ( 1 4 ) 其中 o 是一个常数，它每次迭代修正嘲。b m 方法的思想就是通过引入参数五来 克服- ，瓴) 几乎奇异所带来的困难利用恰当的参数五可保证矩阵 反= 纯) 7 ，( 薯) + 五d 正定而且避免出现过大的0 喀l i 。显然，( l4 ) 是阔题： r a i n i i f ( x j ) + j ( x k ) d i l 2 + 训邢 ( 1 5 ) 的解，问题( 1 5 ) 是( 1 3 ) 的修改。其中五l l d l l 2 可看作是罚项从而可阻止0 喀i i 过大 定义： a 4 爿i u 纯，- ，( 黾) + 五d - 1 ，( 毛) 7 f ( 黾) 0 ( 1 6 ) 2 太原理工大学硕士研究生学位论文 则不难证明l e v e n b e r g - m a r q u a d t 步( 1 4 ) 也是如下问题： 翟扫| l f ( 矗) 十j ( ) d “2 ( 1 7 ) s t 0 d 临吼 ( 1 8 ) 的解。约束条件( 1 8 ) 正是一信赖域约束。可见，问题( 1 7 ) 一( i 8 ) 是一信赖域子问 题。因此，从这个意义下传统的l m 方法也是一特殊的信赖域方法，也正由于此，人 们提及信赖域方法的历史总是追溯j ：l j l m 方法。 信赖域方法的关键组成部分是如何求得信赖域试探步以及怎样决定试探步是否 可被接受。试探步一般通过一子问题来求解，所以予问题的构造是求得信赖域试探步 的关键所在。而决定试探步是否可被接受通常是利用某一价值函数，看试探步能否使 价值函数下降。对于无约束优化问题，价值函数显然就是目标函数。对于约束优化问 题，价值函数常常是一罚函数。一。 1 2 国内外研究现状 非单调思想最早由g 嘶印m 于1 9 8 6 年提出，并用在牛顿法上，文 8 利用这种思想 把它用在s q p 方法上，以避免 m a r o t o s ”效应。文【9 予1 9 9 3 年用非单调思想讨论了无 约束信赖域方法。文 1 0 把这种思想用到等式约束优化问题，提出了一种信赖域方法。 非单调算法放松了接受试探步的条件，在迭代点位于某个“峡谷”时，仍能产 生更长，更有效的试探步，且在一定程度上能克服约束优化问题中常产生的“m a r o t o s 效应：因此受到了越来越多的重视卧“” 本文考虑如下等式约束优化问题： 卿，o ) ( 1 9 ) s t c ( 功= 0 ( 1 1 0 ) 其中f ：r ”专r ，c = ( q c 2 ( 办，7 ，q ：f r ( f = 1 ，2 ，哟令 g ( 功= 可y ( 力，爿( 功= v c ( 力，而为了简单方便，我们通常用q ，五，反，4 表示c ( 甄) ， 八黾) ，g 魄) ，彳瓴) 3 太原理工大学硕士研究生学位论文 当给出一个近似解磁时，序列二次规划方法求解( 1 9 ) 一( 1 1 0 ) 是通过下面的子 问题来获得搜索方向以： m i n d + 三d 7 忍d ( 1 1 1 ) s t g + 彳喀= o ( 1 1 2 ) 这里且是l a g r a n g e 函数三 ，五) = 厂( x ) + a 7 c ( x ) 在( ，五) 点的h e s s i a n 矩阵或者是它 的一个近似。 如果我们想构造一个信赖域方法去代替序列二次规划方法，最简单的方法就是在 ( 1 1 2 ) 中增加一个信赖域约束。即在而点通过解下列子问题来得到搜索方向以。 卿咖+ 妒反d ，( 1 1 3 ) s t g + 鬈d = o ( 1 1 4 ) i i r i l l o 为信赖域半径。但是，子问题( 1 1 3 ) 一( 1 1 5 ) 的可行解可能 是空集。正因为这样，许多作者提出了许多办法来克服这一困难，提出很多信赖域子 问题。 v a r d i ( 1 9 8 5 ) 1 5 】和b y r d ，$ c h n a b e 及s h u l t z ( 1 9 8 7 ) t 1 6 1 提出下面的信赖域算法子问题： m i n 爵d + l a m b e d ( 1 1 6 ) s t 鬈d + 口c ：= o ( 1 1 7 ) 0 r i l l 瓯 ( 1 1 8 ) 这里五是第七步迭代的信赖域，半径口的选取使得( 1 1 7 ) 和( 1 i 8 ) 相容且有下 面两个式子成立； 8 瓯s 口l ki i s 盈。 口( o ，1 ) ( 1 1 9 ) 4 太原理工大学硕士研究生学位论文 = “( 毪) = 一4 ( 鬈4 ) - 1 g ( 1 2 0 ) p o w e l l 和y u a n ( 1 9 9 1 ) 1 v 提出下面的子问题： m i n d + 妻d 7 反d ( 1 2 1 ) s t 0 c ：+ 群d | 阵仇，l f d f l 五 ( 1 2 2 ) 这里仇满足： m i n 。岭+ 和临仇 0 是罚因子。他们不需要用二阶校正就避免了“m a r a t o s ”效应。但是子问题 ( 1 2 1 ) 一( 1 2 2 ) 最早由m r c e l i s ，j z d e n n i s 和r a t a p i a ( 1 9 8 5 ) 提出，被称为c d t 子 问题，它的求解是一个“o p e np r o b l e m ( 参见文献 1 8 】和【1 9 】) 。 m e l i a l e m ( 1 9 9 1 ) t 2 0 l 考虑子问题( 1 1 1 ) 一( 1 1 2 ) 和( 1 2 1 ) 一( 1 2 2 ) ，用( 1 2 4 ) 作为价值函数，但仍不能避免c d t 子问题。z h a n g 和z h u ( 1 9 9 0 ) 1 2 1 1 利用投影拟牛顿方 法求解下面子问题： m i n ( z ；& ) r p z + 妻( p z ) r 盈p z ( 1 2 6 ) 二 s t p 。临盈( 1 2 7 ) 这里乏是( 彩) 的正交基矩阵，价值函数为( i 2 4 ) 但是在较强的条件下，他们得 到两步超线性收敛。 上面提到的信赖域方法大部分有一个共同特点，那就是为了保证算法的全局收敛 性，都要求算法的每一步迭代是“成功迭代”，即新的迭代点能保证价值函数比当前 的值严格单调减少然而，在实际计算中发现，对于某些问题这样做并不能保证算法 5 太原理工大学硕士研究生学位论文 是有效的。大多数的信赖域方法的全局收敛性的证明需要假设正则性条件成立，即假 设约束的梯度线性无关。但是在实际问题中特别是大规模问题中，正则性条件难以满 足。因此在无正则条件下提出新的非单调信赖域算法是十分重要而有意义的 e 1 a l e m 噙1 在没有正则性条件下证明 d e n n i s ，e 1 - a l e m 和m a c i e ! s 类信赖域方法是全 局收敛的。 本文提出一类新的求解问题( 1 9 ) 一( 1 1 0 ) 的非单调信赖域算法。其非单调程度 由算法自适应控制，计算预测下降量和实际下降量的比值时，采用前m ( k ) 个点的信 息，这不同于以前在计算预测下降量和实际下降量的比值时，仅仅采用当前一个点的 信息。本文的价值函数采用了增广l a g r a n g e 函数，在没有正则性条件成立下讨论了算 法的收敛性，并对一些例子做了数值试验。 本文的结构安排如下： 在第二章中我们给出了求解等式约束优化用到的一些基本知识，几个重要概念及 一些重要定理。在第三章中我们给出了解决等式约束优化的非单调信赖域算法模型， 并给出了子问题的求解。在第四章中我们在没有正则性条件成立的假设下证明了算法 是有定义的，并且是全局收敛的。在第五章中我们做了一些数值试验，说明算法是有 效的。 6 太原理工大学硕士研究生学位论文 第二章预备知识 本章介绍求解等式约束优化所用到的一些基本知识和一些重要概念，以及后面要 用到的一些重要定理。 2 1 几个重要概念 定义2 1 m 连续函数，：掣寸r 称为在二：连续可微，如果要( 功存在且连续， 观 i = i ，2 ，栉f 在x 处的梯度定义为： v f ( x ) ；洋( 小，要( z ) ) r 嘶 如果厂在开集d e r ”中的每一点连续可微，则称厂在d 中连续可微。 定义2 2 连续可微函数厂：r 一一r 称为在x 处二次连续可微。如果兰姜( 功存 o 蟹c x ， 在且连续，1 i , j 0 ，r h ，玑( o ，1 ) ，o - o 0 ，整常数 m 2 0 ，m ( o ) = 0 ，mo = m ，后_ 0 ； 步1 令= ； 太原理工大学硕士研究生学位论文 步2 计算正，g ，4 ； 步3 解( 3 1 ) 一( 3 2 ) 和( 3 3 ) 一( 3 5 ) 得到唯 ) 和吨( ) 。若u ( 缈) = 0 且巩 ) = 0 或 者唯( 国) = o 且甑t 吃( 出) + 圭喀) 7 b 吨( ) + 巧g o ，停止； 步4 令吒( 出) = 吒。如果 p r e d k ( 甜) i 1 吼 ) ( 1 1 g 1 1 2 一l l g + 以 ) 1 1 2 ) ( 3 1 j ) 不成立，则 o - r a , ) = 咧吒，逊盟掣器蓑鸳稀掣避； 步5 由( 3 8 ) 一( 3 1 4 ) 式计算成( 国) 其中吒由吼( ) 代替。如果成茹) o 使得对所有的七有； i i b 临n 注意到假设条件中并不包含约束条件的梯度线性无关这一假设，而这是一个许多研究 者普遍使用的条件。 引理4 1 如果u ( ) 0 ，则对任意o 国s 有： i i q i l 2 刈q + 鬈川2 ( 1 一o ( 州2 ( 4 1 ) 证明：由于h ( ) o ，对任意o 国有j 三唯( ) 是( 3 1 ) 一( 3 2 ) 的一 个可行解。且 吼饥( 。) ) s 。( o ) ：昙qi i ： 因此 1 6 太原理工大学硕士研究生学位论文 由于 所以 2 m ( k ( ) ) s2 0 i ( 竺一唯( 也k 。) ) r a i n 刮q + 芒钒u | j 2 + 暑忆( 训1 2 s ( 1 一_ 生) i l q1 1 2 + 旦i l c i + 彳唯( 。) 1 1 ： q n mq n “ + 乏忆( 训r = ( 1 一善l - ) i i qi p + ：竺一o g + 鬈1 l ( 国缸) l | ： q。q“ + 丢忆c 国u ) 1 1 2 + 咯一考慨( l j 2 每 - 0 一导) 憾1 1 2 十兰岭1 1 2 吐k hq m + + 专 慨c ) 1 1 2 马l g1 1 2 + 譬忆( q ) 1 1 2 q 血 g + 彳唯( 国) 1 1 2 2 吼瓴( 国) ) 0 g 2 0 q + 群以( 国) 0 2 刮q0 2 0 q + 唯( 国) 1 1 2 习ic ：1 1 2 2 吼吨( ) ( 1 一_ = 兰与唯( ) i l z n k 1 7 太原理工大学硕士研究生学位论文 引理4 1 证毕。 引理4 2 如果假设h 成立，则存在不依赖于迭代步的正常数墨使得： l i c k l l 2 一i i q + 4 v , 。( c o ) 1 1 2 2 墨1 1 4 g l l 2 ( 4 2 ) 证明：如果4 g 1 1 = 0 ，即4 g = o ，因为0 是问题( 3 i ) - - ( 3 2 ) 的可行解，所 以有： 圭l i c k + 鬈唯 ) 酽+ 三。唯( 国) n 2 三| | g 旷 也就是 i i c ：+ 鬈唯( 缈) l l 马i c ： 所以 l i c k 2 0 q + 鬈v i ( c o ) 1 1 2 2 0 = 墨i f 4 g 旷 以下假设i i 以gl p 0 令 自k = 一9 k a s k 其中 尾= 0 4 g l l 2 1 1 4 c i l 2 + 1 1 鬈4 g i l 2 t o ) 0 4 q | i 则龟是问题( 3 1 ) - - ( 3 2 ) 的可行解由问题( 3 1 ) 一( 3 2 ) 可得： 2 0 。( 吒) 爿i c ：+ 彳噍1 1 2 + i i 露i l = ( q + 鬈露) 7 ( g + 鬈露) + 0 五1 1 2 = t i c , | 1 2 - 2 展1 1 4 g i l 2 + 群鬈4 g0 2 + 露l i n g i l 2 ( 1 ) 当a = 丽时， 1 8 太原理工大学硕士研究生学位论文 2 。鹊妒一丽龋愀驯2 + 而1 1 4 q i j 2 + 0 4 4 q | | 2 由假设条件h 知，存在正数6 l 使得i l 鬈i i - 1 1 g0 2 2 0 。也( 口) ) 0 g i l 2 2 0 i ( 吼) k i l 4 q i l 2 综上所述引理4 2 得证。 引理4 3 如果假设h 成立，则存在不依赖于迭代步的正常数鸥使得： i 触反( ) 一p r e 吨( ) l 吒 ) 1 1 吨( 国) 1 1 2 ( 4 3 ) 证明： 如果反( 口) = o ，则 k e a i ( r o ) = p ( 磁，五，o l ( ) ) 一p ( x k + 反( 缈) 五+ 1 ，d l ( ) ) = ，( 以) 一，( 黾+ 反( ”+ 巧( c ( ) 一c ( + 以( 甜) ) ) _ 巧瓴+ 吱( 国) ) + o - d r o ) ( 1 l c ( 而) i | 2 - i i c ( x , ) + d w o ) 1 1 2 ) = - 誓c 瓴) p r e d ( 国) = 一g n r c o ) 一圭( ) 恳以( 功_ 誓( g + 4 以 ) ) 一4 j 以( 硼+ o - r r o ) ( 1 l c ( = , ) 1 1 2 0 c ( 黾) + , l i d , ( t o ) 1 1 2 ) 一 = _ g c ( x , ) 即 l a r e 反( ) 一p 坞喀( 功l - 0 上式成立 太原理工大学硕士研究生学位论文 下面假设4 ( t o ) 0 ，则 la r e d k ( o d ) 一p r e 矾 ) = j ( 五) 一f ( x k + a a c o ) ) + 砑( c ( 吒) 一c 瓴+ 反( 缈) ) ) 巧( t + 以( m ) ) + a , ( r o ) ( 1 l c ( x , ) 1 1 2 一1 1 c ( x , ) + 4 ( c o ) 1 1 2 ) + 爵吨+ 去( 反反( ) + 巧( g + 吐) ) + 巧匝( 缈) ) - 盯, ( c o ) ( 1 l c ( x , ) 1 1 2 一 i c 瓴) + a 4 ( c o ) 1 1 2 ) l q 厂瓴) 一，魄+ 噍( ) ) + 吐+ 去衫 ) 忍喀( 国) l + i 砭。( q + 鬈d i ) 一c ( + 以 ) ) ) i + 文( ) 川c 瓴) + 彳反( 国) i l ：一i i c 瓴+ 反( ) ) 鑫 乌矾 ) 7 ( 盈一俨， ) 噍 ) ) i + i f m f f f v 2 c ( x ) 4 f + 气( ) 川c ( 矗) + a 4 ( c o ) 1 1 2 一c ( 黾+ 4 ( c o ) ) 1 1 2 i q 忍- v 2 厂( 蟊) 川畋0 2 + i i 五。i i i i v c ( ( d i i + 吒( 国) i i i c ( 黾) + 群4 ( c o ) 1 1 2 一l l c ( 稚+ 4 ( r o ) ) 1 1 2 i ( 磊和在鼍和黾+ 以( ) 之间) 由于c ( 功，b ) 二次连续可微，五是有界序列，盈是一致有界的，i i4 ( t o ) i i o j ，而 由问题( 3 1 ) - - ( 3 2 ) 可得： j g + x r 4 ( c o ) 1 1 2 硼g + 鬈唯( 功j 1 2 q l g0 2 综合以上可得：存在正常数m ，j i 如， 毛使得： i a r e 嗄( 功一p 吨 ) i 0 时， 峻糍辫1 1 z ；g , i i t 2 2 ( 互名& ) 1 鼠( 互互) 丽黔姥丽噼酬2 ! ! 垄剑： 2 | j 乙1 1 2 | l b l l 六i i 墨酬2 当( 乙z ；) 7 皿唯( m ) o 使得： p r e 以( 功墨j i 露既1 1 2 一蜀i i q i i + # k ( i i g i l 2 0 q + 4 哦( ) 咖 证明：由于 i i q + 鬈噍( 西h 刮g l i 0 鬈或( 功) 0 o ，则稚是不可行m a y e r - b l i s s 点。 证明：因为也( 功= 0 ，由引理4 2 得4 c i = o 。x 4 ( c o ) = o ，由( 3 2 7 ) 式和。 以( ) = 五u k + ( ) + 4 喙( 功可得零= o 。所以黾是不可行一阶点。 由爵反( ) + 昙以) r 魂嚷( 国) s o ，我们可以推出g o 。即靠是不可行 m a y e r - b l i s s 点。引理4 6 证毕。 由引理4 6 知，如果迭代点五在步3 终止，则耳是稳定点。以下我们假定算法a 不有限步终止，即假定算法产生一个无穷序列 毪) 。下面证明算法a 是有定义的。 定理4 1 算法a 有定义的，即算法a 不会在步3 与步5 之间无限循环。 证明：如果算法a 不在步3 终止，我们有唯( 国) o 或者露0 。假定算法a 在 步3 与步5 中无限循环