（计算数学专业论文）约束非线性优化问题的信赖域算法.pdf

南京航空航天大学硕士学位论文 摘要 信赖域方法是非线性优化中一类重要的数值计算方法，它具有良好的收敛 性和稳定性，因此在许多领域都有广泛的应用。本文主要研究约束非线性优化 问题的信赖域算法，全文分为三章。 第一章为绪论，简要介绍了信赖域方法的研究和发展情况以及本文主要研 究内容。 第二章对一类特殊的线性不等式约束优化问题提出了一种修正的信赖域算 法。此算法以内点法为基础，在构造子问题时。只考虑一般的不等式约束，而 把非负边界约束化为信赖域约束的一部分，从而得到一个简单易解的子问题。 本文在一定的条件下证明了算法的收敛性，并给出了数值结果。 第三章对一般的非线性约束优化问题提出了几种修正的信赖域算法，这些 算法都是以l 。精确罚函数为价值函数，对是否接受试探步的判别准则进行了修 正。本文证明了修正算法的全局收敛性，并给出了相应的数值结果。 关键词：线性不等式约束，非线性不等式约束，约束优化，信赖域，内点法， 全局收敛性，强收敛性 a b s t r a c t t r u s tr e g i o nm e t h o di sac l a s so fi m p o r t a n tn u m e r i c a la l g o r i t h m sf o r n o n l i n e a r o p t i m i z a t i o n t h e r e a r e s t r o n gc o n v e r g e n c e a n dr e l i a b i l i t y p r o p e r t i e sf o r t h e s ea l g o r i t h m s ，s ot h e ya r ew i d e l yu s e di nm a n yf i e l d s i n t h i st h e s i sw ed i s c u s st r u s tr e g i o na l g o r i t h m sf o rc o n s t r a i n e dn o n l i n e a r o p t i m i z a t i o np r o b l e m sb y t h r e ec h a p t e r s i nc h a p t e ro n e ，w e b r i e f l yi n t r o d u c e st h ed e v e l o p m e n t o ft r u s tr e g i o n m e t h o da n dt h em a i nc o n t e n t so f t h i s p a p e r at r u s t r e g i o na l g o r i t h m f o r s p e c i a l l i n e a r i n e q u a l i t y c o n s t r a i n e d o p t i m i z a t i o np r o b l e m si sp r o p o s e di nc h a p t e rt w o t h i sa l g o r i t h mi s b a s e do nt h ei n t e r i o r - p o i n tm e t h o d i n c o n s t r u c t i n gt h es u b p r o b l e m ，w e m o v et h e n o n n e g a t i v eb o u n d c o n s t r a i n t sf r o mt h eg e n e r a li n e q u a l i t yo n e s i n t ot h et r u s tr e g i o nc o n s t r a i n t s ，a n do b t a i nas o l v e d - e a s i l ys u b p r o b l e m u n d e rv e r ym i l dc o n d i t i o n s ，c o n v e r g e n c er e s u l t sf o rt h ea l g o r i t h ma r e g i v e na n d n u m e r i c a lr e s u l t sa r e r e p o r t e d i nt h el a s tc h a p t e r , w e p r e s e n tt h r e em o d i f i e dt r u s tr e g i o na l g o r i t h m s f o r g e n e r a l n o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s f o r t h e s e a l g o r i t h m s w ec h o o s e l 。e x a c tp e n a l t yf u n c t i o na st h em e r i tf u n c t i o n a n d m o d i f y t h er u l e sf o r a c c e p t i n g t h et r i a ls t e p g l o b a lc o n v e r g e n c ef o rt h e s ea l g o r i t h m sa r ep r o v e da n dn u m e r i c a lr e s u l t sa r er e p o r t e di n t h i sc h a p t e r k e yw o r d s ：l i n e a ri n e q u a l i t yc o n s t r a i n t s ，n o n l i n e a re q u a l i t yc o n s t r a i n t s ， c o n s t r a i n e d o p t i m i z a t i o n ，t r u s tr e g i o n ，i n t e r i o r - p o i n tm e t h o d ，g l o b a l c o n v e r g e n c e ，r o b u s tc o n v e r g e n c e 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。尽我所知，除文中已经注明弓l 用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本 论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 作者签名： 基遘 日 期：墨蛀：2 ：i f 堕塞鉴皇堕墨查堂堡主堂垡堡塞一 _ _ _ _ _ _ 一 第一章绪论 最优化理论与方法是一门应用性很强的学科它研究某些数学问题的最优 解。随着计算机的高速发展和优化计算方法的进步，规模越来越大的优化问题也 可以进行求解。最优化在航空航天、生命科学、水利科学、地球科学、工程技术 等自然科学领域和经济金融等社会科学领域也发挥着越来越重要的作用，它的 研究和发展一直得到广泛的关注。 最优化问题的一般形式为： m i nm ) ( 1 1 ) s t x f ， 其中工彤为决策变量，( x ) 为目标函数，fc 2 ”为约束集或可行域。如果 f = 掣，则上述问题称为无约束优化问题：否则，称为约束优化问题，通常记 为 r a i n ，( z ) s t q ( x ) = 0 ，f e ( 1 2 ) c ，( x ) 0 ，f ， 这里和f 分别是等式约束和不等式约束的指标集，c ( x ) 是约束函数。 对于无约束优化问题，已经提出了很多有效的数值计算方法，如最速下降法、 牛顿法、共轭梯度法、拟牛顿法等。对于约束优化问题，也有不少计算方法，如 二次规划法、罚函数法、序列二次规划法、可行方向法、信赖域法等。 信赖域方法是近二十多年来发展起来的一类重要的数值计算方法，受到了非 线性优化界非常的重视。特别是近几年，一直是非线性优化研究的热点。目前， 信赖域方法已经和传统的线搜索方法并列为非线性规划的两类主要的数值方法。 信赖域方法的研究起始于p o w e i i 的研究工作“”，后来人们发现信赖域方法 的基本技巧在一定意义下等价于求解非线性最小二乘的l e v e n b e r g m a r q u a d t 方 法。信赖域方法的构造和逼近是密切相关的。给出一个当前迭代点而，构造一 个近似于原问题的逼近模型。由于该模型主要是基于原问题在毛的信息，故有 理由认为此模型仅在黾附近可以很好地描述原问题。所以，人们仅在屯附近的 某一邻域内求解逼近模型的最优点。该邻域被称为信赖域，它常是以也为中心 约束非线性优化问题的信赖域算法 的广义球。信赖域的大小通过迭代逐步调节。一般说来，如果当前迭代模型较好 地逼近原问题，则信赖域可扩大，否则信赖域应缩小。 信赖域方法的关键组成部分是如何求得信赖域试探步以及怎样决定试探步 是否可被接受。试探步一般是一子问题的解，所以如何求得信赖域试探步实质上 归结于子问题的构造。决定试探步是否可被接受通常是利用某一价值函数，看试 探步能否使价值函数下降。对于无约束优化问题，价值函数显然就是目标函数。 对于约束优化问题，价值函数常常是一罚函数。 信赖域方法育两个很好的性质。一是它有很好的可靠性和强适性，另一个是 它有很好的收敛性。这也正是它备受关注的主要原因， 对于无约束优化问题和等式约束优化问题，信赖域方法的研究已经比较成 熟，但对于不等式约束优化和一般约束优化问题，信赖域方法还有待于进一步研 究。 对一般线性约束优化问题 1 1 1 i n ，( x ) s t 良= 0 ( 1 3 ) 五5 ， 目前已有的信赖域方法有两类。一类是单调的信赖域方法，它要求每一步迭代都 是下降的，如y u a n 。1 给出了一个一般性的信赖域方法，它是可行点法和信赖域法 的结合。另一类是非单调的信赖域方法，即不要求每一步迭代都是下降的，如葛 恒武和陈中文“5 3 给出的算法，不仅利用了已有点的信息，而且根据子问题可t r 信 赖”的程度自动调节非单调的幅度。 对于些特殊形式的线性约束优化问题，如 m i n f ( x ) s t f x “， ( 1 4 ) 大多数信赖域方法都是与其他技巧相结合。陈中文等利用有效集的技巧构造了 一个信赖域方法- 丽c o l e m a n “1 等利用了内点技术构造了一个信赖域方法并且具 有良好的收敛性。 对于如下线性等式和非负边界约束优化问题 m i n ( 砷 s t c x = d ( 1 5 ) 工0 。 南室塾窒塾墨盔兰堡主兰垡笙塞 一一 一一。 目前都是用内点法构造信赖域子问题，如文献【4 ， 1 2 ， 1 3 。 对于一般非线性约束优化问题( 1 2 ) ，信赖域方法的构造主要取决于试探步 d 。的选取和如何判别矾是否可被接受。与无约束优化一样，以的选取归结为子 问题的构造。约束优化问题的信赖域子问题有好几种形式。第一种形式为 m x t i f n 或d + 毛毋b k d s t 吼q ( 以) + d 7 v c , ( x d = 0 , i e ( 1 6 ) o m , ( x i ) 十d r v c ，( x t ) o ，i ， ：色， 其中只( 0 ，1 ) 。这一问题的详细描述参见b y r d ，s c h n a b e l 与s h u l t z m 3 和v a r d i 嘶3 的论文 另一一种信赖域子问题是 卿咖+ 妒鼠d s t k + 群以) 一蛤氧 ( 1 7 ：s 屯， 其中c 。：c ( t ) ：( c ，( x d ，c 。( 黾) ) 7 ，a k = a ( x k ) = v c ( x d r , 磊0 是参数，上标“一” 表示 玎= v f ，i e ， v , - = m i n o ，h 】，i j 利用此子问题模型的有c e l i s ，d e n i s 和t a p i a m l 以及p o w e l l 和y u a n ”等。y u a n 1 讨论了子问题的性质，还给出了求解子问题的一个对偶算法啪3 。这个子问题还可 化为一个单参数问题，见文献 2 9 。 第三种信赖域子问题是用非光滑精确罚函数导出的，它的形式为 罂静爵d + 圭d 7 反d + 吼j l ( q + 4 d ) 一i i ( 1 8 ) s t i i d 0 t ， f l e t c h e r 啪3 取| | | | 为洲。，而y u a n ”“把| | | i ；推广到了洲。，并给出了如何逐步修改吼 的技巧。在y u a n 的研究工作基础上，张红潮1 对文献 3 0 作了改进，提出了非 单调的信赖域算法，且获得了较好的结果n 计算试探步也可利用约束零空间以及积极集合等技巧，如文献 1 6 ， 1 7 ， 约束非线性优化问题的信赖域算法 3 1 和 3 3 等。另外，利用松弛变量把不等式约束化为等式约束也是一种常见的 方法，如文献 3 7 ， 3 8 和 3 9 等。其中文献 3 7 将目标函数化为障碍函数，再 与内点法结合求解。而文献 3 8 和 3 9 与牛顿法和内点法结合。 上述算法大多是在正则条件的假设下证明算法的全局收敛性的，e 1 一a l e m “” 在无正则条件下证明了d e n n i s ，e 1 一a l e m 和m a c i e l 类信赖域算法是全局收敛的。 张菊亮“”在无正则条件下提出了一个新的信赖域算法并且证明了算法具有全局 收敛性。 在信赖域方法中，判别畋是否可被接受将依赖于某一价值函数只( x ) ，它常 是一精确罚函数。b y r d “”最先利用非光滑精确罚函数构造信赖域方法，而p o w e l l 和y u a n “”是最先利用光滑精确罚函数作为价值函数构造信赖域方法的。 约束优化信赖域方法一般需要构造一个近似价值函数面。( d ) ，使其在i 彳艮 小时满足 中i ( d ) 一m ( o ) = 最( 砟+ 1 ) 一只( 坼) + o ( 1 l d l l ) ， 而且有 p r e d 女= o i ( o ) 一中 ( 矾) 6 瓦m i n a i ，毛删最胭， ( 1 9 ) 其中万是正常数，毛是k - - t 条件的违反度： 气- - l l c ：l l + l l g 。一4 五 五满足( 五) o ，i i ，是在当前迭代点对l a g r a n g e 乘子的估计。然后令 ：业止掣2 ，( 1 1 0 ) p r e a 根据气来判别是否接受试探步瓯。 下面给出一般信赖域算法模型： 算法a 步1 给出_ e r ”，a i o ，占o ，o q c 4 0 ，且钆( o ，1 ) ，因此，坼+ d ( 1 - 6 i ) 屯 0 。这样就保证了每次迭代产 生的点都是可行域的内点，从而满足边界约束条件耳0 ，即子问题( 2 4 ) 是 可行的。 现在我们比较问题( 1 1 1 ) 的两个不同的子问题( 2 3 ) 和( 2 4 ) 。( 2 4 b ) 中 a r ，( 2 4 c ) 中有n 个不等式约束，因此共有m + n 个约束。而( 2 3 b ) 中 五r 1 ”，( 2 3 c ) 也可以化为r t 个线性不等式，因此共有m + 2 n 个约束。因此， 子问题( 2 4 ) 的约束条件要比子问题( 2 3 ) 的约束条件少n 个，从而会减少计算量 和计算时间。当问题的变量个数力较大时，这一效果会更明显。另外，子问题( 2 4 ) 也是一般的二次规划问题，可用现有的二次规划方法来解。 由于予问题( 2 4 ) 的可行集e r ”i 爿( 耳+ d ) 抚一耳d a k x k 总是非空 紧集，所以( 2 4 ) 总存在最优解以。下面引进一些记号： ，= l ，2 ，m ) - a 1 = ( a i ，i ，) ， j 0 0 = j f d x = b 矗。 = j ，i 司( x k + 以) = 6 | ) ， p r e d , = 咄= q k ( 0 ) 一吼( 矾) ， 约束非线性优化问题的信赖域算法 a r e d k = f ( x k ) 一f ( x k - i - d k ) 其中a r e d , 和p r e d k 分别为目标函数在处的实际下降量和预计下降量 在讨论解问题( 1 1 1 ) 的算法前，先给出如下假设和一个引理。 假设2 1 v x f ，向量组( n ，l j ( x ) 线性无关。 引理2 1 a q k 0 总成立。若a q k = 0 ，则鼍为问题( 1 1 1 ) 的k t 点。 引理2 1 的证明可参考文献 2 3 中引理1 的证明。 下面给出求解问题( 1 1 1 ) 的信赖域算法： 算法b 步1 给出可行点一 o ，对称矩阵马r “”，叩( 0 ，1 ) ，( 0 ，1 ) ，k = 1 。 步2 解子问题( 2 4 ) 得或。若a q k = 0 ，停止。 步3 计算= ! 竺! 。如吒 - 8 1 1 v 删陋a ，坦铲 ( 2 5 ) 这里 i i v ，f ( 圳i = l i mp ( x - a v d f ( x ) ) - x 是定义在可行域f 上的投影梯度，其中 p ) = a r g m i n z - y l l ，z 刃， 可行域f 的定义见2 2 节。由文献 3 定理1 3 2 2 的证明知只要d k 是( 2 4 ) 的 解，则( 2 5 ) 一定是满足的。 根据文献 3 ，我们得到以下引理： 引理2 3 x 是问题( 1 1 1 ) 的k - - t 点当且仅当i v ，( x ) l l = o 。 定理2 1 设k 是由算法b 产生的点列，算法b 不会在步2 与步3 之间无 限循环。 证明：若定理不成立，则气 o 。不失 一般性，假设这一不等式对所有充分大的k 都成立。因此由引理2 2 及( 2 5 ) 得 l i m i 吒一1 i = l i m t + i o 一 s l i m 璁糕一o ， 则由此可见，! i r r 2 r t = l ，这与 o ，使得对无穷多的七k ，都有 6 v ，( k ) 4 由假设2 2 知，i i 鼠0 一致有界，从而对无穷多的七k ，有 p r e d , 瓯幽势 瓴m i n t a = 瑟o a , m i n 1 ， 其中m = 1 裂0 最上式的第二个不等号是由于。 o ，使得对无穷多的k ，f 1 吨6 。 q 。由 假设2 2 知，) 有界，因此总存在一个正常数毛，使得对任意的k k ， 8 以屯毛。又由算法b 知序列 五) 单调下降，得l 。i r a ，( 坼) = ，( x ) ，于是在 以上不等式中令七k ，k _ ，有o 七3 q ，产生矛盾，证毕。 定理2 2 设 是由算法b 产生的点列，若假设2 1 ，2 2 成立，则算法b 或有限步终止于( 1 1 1 ) 的k - - t 点，或产生无穷点列饥) ，使得协 的每一个聚 南京航空航天大学硕士学位论文 点x 均是( 1 1 1 ) 的k t 点，即算法是全局收敛的。 证明：若算法终止于毛，则由步2 知，吼= 0 。由引理2 1 知，以为( 1 1 1 ) 的k - t 点。设算法产生无穷点列瓴) ，z 为给定的聚点，则存在无穷下标子列k l ， 使得 m l i r a 2 ，v 女k 1c k 由引理2 4 妣l i m d k 2 0 另方面，指标集 存在一个元素相等的子列 l k 。k 2 k 。即k k ：， i k = ，。对于任意的i ，有 衫x 一b i 。般 赡一6 ，1 = l 惩一口j 破= 0 ， 故，= j ( x 1 。 利用假设2 1 可知，k k ：充分大时，向量组“，f i k 线性无关。因为盔为 问题( 2 4 ) 的最优解，由k - - t 必要条件知，存在乘子群，使得 g k + b 吨+ 矿q = o ，”? o ，v i e ， ( 2 ，6 ) l e ， k 充分大a 由假设2 2 ，! 囊8 且吨0 = 0 a 因此，令七丘，七一，对( 2 6 ) 式两边取极限得 旷+ 矿q = o ，矿0 ，v i e ， f t ， 因为，= j ( x ) ，此即说明工是( 1 1 1 ) 的k t 点。证毕。 为进一步分析算法的强收敛性，我们给出强收敛性的定义和相应的假设。 定义2 1 设x 是赋范线性空间，瓴) c x ，z 。如果f k 一0 _ o ( h 斗m ) ， 就称纯 强收敛于。 假设2 3 设算法产生的点列 吒) 存在聚点x ，使得问题( 1 1 1 ) 在工处二阶 充分条件和互补松弛条件成立，即 v 三三( x ，“) = v 2 f ( x ) 在子空间 y ( x 。) = ( d r ”i d = o s i ，) 上正定，其中“? 0 ，i e j 。= j ( x ) ，“为x 的k t 乘子。 下面的引理来自文献 2 3 中引理4 。 引理2 5 设 是由算法b 产生的点列，若假设2 1 ，2 2 ，2 3 成立，则 l 鳃l l x , r 以恃0 1 1 约束非线性优化问题的信赖域算法 现在我们给出算法b 的强收敛定理。 定理2 3 设 是由算法b 产生的点列，设假设2 1 ，2 2 ，2 3 成立，则 l i m 以= x + ，即算法是强收敛的。 证明：由文献 7 的定理1 2 5 可知，二阶充分性使得x 为( 1 1 1 ) 的k t 点， 进而由定理2 2 可知工为序列( x k ) 的孤立聚点，因此结合引理2 5 。由文献 7 的定理1 1 6 立知! i r a x k = x + 。根据定义2 1 ，算法b 是强收敛的。 2 4 数值实验 在这一节，我们对本章讨论的算法用m a t l a b 编制了程序，并进行了数值实 验a 其中参数选取如下：s = 1 0 - a , r = o 1 ，色= 2 3 。风= 是单位矩阵，且毋根 据b f g s 拟牛顿迭代公式来迭代，即 。卜， 彩咒o 歌2 卜装一鬻，删 其中喀= x k + l 一屯，y k = 既+ ，一，终止条件为a q k 占。另外，我们把算法b 和 y u a n 。1 中的算法1 3 2 1 进行了9 个算例的数值比较试验，算例见附录部分，计 算结果见表l 。表中n 表示问题的变量个数，i t e r 表示迭代步数，r 表示计算时 间( 单位为秒) ，n o r m 表示最优解与近似解之差的欧氏范数。 算例见附录部分。 表l 算法b 与算法1 3 2 1 的数值比较 算法b算法1 3 2 i 问题 n i t e rt ( s )n o r m 1 t e rt ( s )n o r m l21 21 9 6 9o1 32 1 7 2 o 2330 6 5 7o71 。5 1 22 3 6 1 1 0 “ 3310 3 6 0o10 4 6 9o 4320 50lo 5 1 5o 5351 0 4 77 4 1 4 1 0 51 l2 3 7 52 3 1 5 1 0 “ 6340 8 5 9i 1 6 4 1 0 。1 02 0 1 5 2 1 2 5 1 0 4 7441 1 4 l 2 6 4 6 xl o 一851 1 6 61 9 8 2 x l o 一8 852 3 5 2 9 702 35 4 6 90 945工4 2 21 0 2 7 x i 0 一o51 4 2 2o 数值结果表明，本章的算法b 对解这类问题要比y u a n 的算法1 3 2 1 更为有 效。在九个测试例子中，其中一个例子，不管是精度、迭代步数还是计算时间， 算法b 的结果都要比算法1 3 2 i 好的多。在精度相当的情况下，有五个例子的 迭代步数和计算时间，算法b 都要比算法1 3 2 1 少的多，仅有一个例子的迭代 步数稍微多了一点。另外的两个例子，虽然前者的精度比后者低，但计算时间和 迭代步数并不比后者多。从理论分析来看，由于算法b 中信赖域子问题的约束条 件减少，予问题的计算最大大减少，从而整个问题的计算时间和迭代步数大大减 少。因此，算法b 是一个较好的信赖域算法。 约束非线性优化问题的信赖域算法 第三章非线性一般约束优化问题的信赖域算法 在这一章我们给出了非线性一般约束优化问题的三种修正的信赖域算法，这 些算法都是以l 。精确罚函数为价值函数，对是否接受试探步的判别准则进行了 修正。我们证明了修正算法的全局收敛性，并给出了相应的数值结果。 3 1 引言 本章我们主要考虑下列非线性约束优化问题 m i n f ( x ) s t c j ( x ) = 0 ，f - 1 ，2 ，m e ； q ( 工) 0 ，i = m e ，“，肌 ( 3 1 ) ( 3 2 ) ( 3 3 ) 其中f ( x ) 和c ，( x ) “= l ，用) 是定义在r “上的实函数，加m e 为两个非负整数。 信赖域方法的关键就是在当前迭代点附近的某个邻域求解逼近的二次模型， 得到试探步，然后构造价值函数并根据其下降性决定试探步是否可被接受。目前， 对于无约束优化问题，价值函数往往是目标函数，但对于非线性约束优化问题， 价值函数常常是一罚函数。y u a n 。”是以l 。精确罚函数为价值函数求解问题 ( 3 1 ) 一( 3 3 ) 的，本章我们所提出的算法保留了文献 2 1 的这一主要内容，而对 其中的判别准则进行了修正。从而得到了新的信赖域算法。 3 2 算法 首先定义l 。精确罚函数 只( 工) = - ，( 一仃忙一( ) 其中，盯 0 是罚参数，c 。( x ) 定义如下： c i ( 苫) = c ，g ) ，i = 1 , 2 ，m e ； 玎( x ) = m i n 0 ，q ( x ) ) ，i = m e ，m 易见约束( 3 2 ) 一( 3 3 ) 等价于等式忙( x ) l l 。= o ，并且在一定的条件下 小值点恰好是原问题( 3 1 ) 一( 3 3 ) 的解。 y u a n 。“在算法的每一步解如下子问题 r a i n 纯( d ) = g r d + 士d 7 最d + 吼0 ( q + d ) 一9 。 s t 0 d i l s 女 ( 3 4 ) ( 3 4 ) 的极 ( 3 5 ) ( 3 6 ) 南京航空航天大学硕士学位论文 其中，g + = v f ( x 。) ，b 。是( z ) 在屯处的近似h e s s i a n 阵。吼是罚参数，“一”定 义如上。记 最( x ) = 厶( x ) ， 目标函数的实际下降量和预计下降量分别为 a r e a l k = 丘( 气) 一只( 耳+ 矾) ， p r e d k = 吼( o ) 一纯( 以) ， 其中以为( 3 5 ) 一( 3 6 ) 的解。 下面是y u a n “”中给出的信赖域算法： y u a n 算法 步1 给出x ie r “，a i 0 ，b l r “”是对称矩阵，卤 o ，盯l o ，占 0 ，k = 1 ： 步2 解子问题( 3 5 ) 一( 3 6 ) ，得或；如果j k 儿 0 ，转步4 ：否则 + l = i 或9 。4 ，x = 孔，k = k + l ；转步2 。 步4 x = x k 七dk 计算b 。 a “= m a x 2 。，4 l d 。l ，气 o 9 a ，0 1 r k 0 9 ( 3 8 ) m i n a i 4 ，慨k 2 ， o ，仃i o ，s 0 ， k = i ： 步2 解子问题( 3 5 ) 一( 3 6 ) ，得吨；如m l l a , l l 。 0 ，q o ，占 0 ， k = l ： 步2 解子问题( 3 5 ) 一( 3 6 ) ，得吨；如果0 以l l o 9 “i = ，o 1 s 五s 0 9 l m i n a 。4 ，忱l l 2 ，露 o ，则 ) 至少有一个子列收敛到一个不可行稳定点。 证明：假设引理不成立，则存在整数七0 和紧集q ，使得对所有的k ， 坼q 。对所有的x q ，c ( z ) 0 ，并且q 中不存在不可行稳定点。根据不可行 稳定点的定义以及q 的紧性，存在常数 0 ，使得对所有的工n ， p m k i n ；。i i ( c ( z ) + 一( x ) 7 d ) 一i i 。s l l c - ( x ) 0 。一 ( 3 1 7 ) 成立。我们定义向量孑( z ) 为 | | ( c ( x ) + 4 ( x ) 7 虱x ) ) 一卜副r a i n ( ) + 爿( z ) d ) 忆 的解。由以是予问题( 3 5 ) 一( 3 6 ) 的解，并且 烈砌m 口南k 色， 得 似m 卸q 瓴灿n 赢d ， 其中妒( 以) 参见( 3 5 ) 。因此， 烈o ) 叩) 烈o ) 叩仃胁【l 南】) 令呔( c f ) = 壮( x k ) + d ) l ，则由( 3 1 7 ) 得， 纯( o ) 一丸( 讯吒) ) ( 3 1 8 ) 觏2 赢引棚岫姒卿舢黼， 晚 五孑( 坼) + ( 1 一五) o 】( 1 一a ) 氟( o ) + 五纯( 虱吒) ) 】， 即得 纯( o ) 一九( 五虱) ) 五【以( o ) 一噍( 虱) ) 】舡= r a i n 1 ，z 】 ( 3 1 9 ) 又根据 且) 有界，得 g i t “t j i “- 7 最孑= d ( t ) ，( 3 2 0 ) 其中扎虱m i n 【1 】。龇由( 3 5 ) ( 3 1 8 ) ( 3 - 1 9 ) 和( 3 2 0 ) 有下式 州o ) 叩口( x k ) m i n 1 , 赢d = 妒( 0 ) 一妒( 孑) = j 。以( o ) 一g ：d 一士d 1 岛d c k # a d ) = 一0 一 厅7 盈孑+ 吼辘( o ) 一# m i n o ，a ) 孑( 矗) d ( i ) + o k p r a i n 1 ，a 吼弘t ， 其中露是一个正常数。于是， 妒( o ) 一妒( 吐) 吒五氆 ( 3 2 1 ) 由算法c l 步5 知，当吼_ ，有坑_ 0 ，并且 敢( o ) 一吼( 巩) 对无穷多的k 成立。这与( 3 2 1 ) 矛盾，因此引理是正确的。 类似于引理3 2 ，我们可以证明下列引理： 引理3 3 设忸。) 是由算法g 产生的点列，若l i m 吼= m 且! i m l l c ；i l = o ，则 + k 郴 “ k , 4 * d i i i i * 0 札) 至少有一个子列收敛到一个奇异稳定点。 由引理3 2 和引理3 3 可以推出，如果问题( 3 1 ) 一( 3 3 ) 既没有不可行稳定 点，又没有奇异稳定点，则 吼) 有界。下面是 吒) 有界时的收敛结果。 定理3 1 设 ) 是由算法c l 产生的点列，若对所有充分大的k ，c r k = 盯，则 算法c 。产生的序列 x 。l 收敛于k - - t 点。 证明：不失一般性，假设对所有的k ，有 o k = d ，6 k = 6 由算法c i 步5 知 伊( o ) 一妒( 以) 8 a m i n a i ，悔 ( 3 2 2 ) 对所有的k 成立。设孬是 以 的所有聚点i 的集合，且使得c ( i ) = 0 。若定理不 正确，则对任意的i 西，i 不是k - - t 点，从而存在一个常数可 0 使得 m r a i n 矽( d ) s 尹( 0 ) 一可， ( 3 2 3 ) 认d ) = g ( i ) d + 圭- 1 1 昆。， ( 3 2 4 ) 2 1 约束非线性优化问题的信赖域算法 其中万时一个正常数。 我们称满足五o 1 的迭代步为成功的，记k = k l 夏- 0 1 根据再的定义 ( 见( 3 i o ) ) ，我们可以看出若瓦0 1 。必存在k - 【k - m i n l ，k ) + 1 ，明，使得 唯o 1 。若不然，则对于所有的i k - m i n l ，t ) + 1 ，七 ，都有 o i 。又因为 q m 】【o ，l 】，所以 q m l + i ) = o j “r k 。l = 瓦 p a x d - p a x 。+ ，) 】 最( 唧) 一丘( 唯+ 。) 】 o 1 毯 1 e fk a 品 ( 3 2 5 ) 的第一、二个不等号是由于最( z ) 单调递减且有界获得 由于0 1 和( 3 2 4 ) 获得。这表明 a f m 根据文献 1 1 中引理3 2 的证明得 a 。 。 ( 3 2 5 ) 第三个不等号是 ( 3 2 6 ) 又由连续性假设知 最( ) 一p , ( x k + 砬) = 纯( o ) 一g , a a d + o ( t x ) ( 3 2 7 ) ( 3 2 4 ) 和( 3 2 7 ) 表明_ 1 ，由瓦的定义知，耳_ l 。从而对充分大的k ， 。2 ，这与( 3 2 6 ) 矛盾。因此定理成立。 3 5 数值试验 这一节，我们对本章讨论的三种算法利用m a t l a b 来编写程序，对文献 1 0 中的1 2 个问题进行了数值计算，以检验算法的有效性。其中参数选取如下： 占= 1 0 - 6 , 4 = 0 0 1 ，o i = 1 0 ，i = 1 0 ，蜀= ， 南京航空航天大学硕士学位论文 b 。由p o w e ll 的修正公式来确立 轧却舞一鬻， l 仇，仇o 1 嘎吱 “ 【幺仇+ ( 1 一幺) 反以，r h o 1 屏畋。 其中r l , = + ，一g k + ( 4 。一4 ) ，以= t + 。- x k 皖= 0 g d 最以( 反以一彩仉) ， 丑是l a g r a n g e 乘子。 对于算法c 1 ，当( 3 1 0 ) 中参数，取不同的值时，五的计算公式也就不同。为 此，我们作如下讨论。 当，；l 时，算法c l 就等同于y u a n 算法。 当，= 2 时，瓦可以写成如下形式：瓦= 吼+ ( 1 一国) 脚( 0 ，1 ，k 2 ，其 中彳= 。也就时说夏利用了前两步迭代点处的信息。通过数值试验，我们发现c o 的值大于0 8 ，收敛的效果较好。为此，取国为0 9 。 当，= 3 时，五可以写成如下形式：瓦= q + 吐一l + 0 - c o , 一c 0 2 ) r , - 2 ，k 3 ， 其中可= r l , 巧= ，2 + ( 1 一) ，o ) i ，吐( o ，l 】。也就是说瓦利用了前三步迭代点处 的信息。通过数值试验，我们发现丐与o 1 的取值关系不大。当k 3 时，q 较大 时收敛的效果较好。为此，我们取o j , ；0 8 ，c o z = 0 1 。 依次类推，当，逐渐变大，直至对所有的女，都有，k 时，五就可以记成： 瓦= 唯+ ( 1 一曲) 瓦_ l ，( 0 ，1 1 七2 ，其中彳= 。也就时说茸利用了所有迭代点 处的信息。通过数值试验，我们发现o 的值大于0 8 ，收敛的效果较好。为此， 取功为0 9 。 对于算法c 2 ，口越接近于l 。迭代效果越好。有的时候，o f 越大，精度越高， 但迭代也越慢，为此分别取口= 0 8 和口= 0 9 。 对于算法g ，取卢= 0 9 ，此时效果最好。 我们对文献 2 1 中的y u a n 算法( 即，= l 时的情形) 也编了程序，同样测试了 文献 1 0 中的i ；3 题。这里n i n g 分别表示算法的迭代次数和梯度的计算次数，晶 表示算法得到的解与精确解的绝对误差，阀题的序号对应于文献 1 0 中的序号。 试验结果见表2 。 算例见附录部分。 丝塞! ! 垡竺垡些塑望堕堕塑塑墨鳖 问算法g算法c ，算法c 1 题 7 n i n g 岛 口 n i n g 岛 n i n g 岛 l 2 0 1 4 7 0 3 6 1 e 0 0 8 21 3 91 6 0 5 l e - 0 0 7 0 81 6 1 21 4 2 8 l e - 0 0 6 1 2 32 1 1 43 4 3 0 0 e - 0 0 82 4 1 74 2 6 5 6 e 一0 1 2 七2 0 1 53 8 3 0 3 e - 0 0 9 0 ，92 4 1 74 2 6 5 6 e - 0 1 2 l 5 52 ，8 8 6 6 e - 0 1 5 0 8 6 52 8 8 6 6 e - 0 1 5 2 5 52 ，8 8 6 6 e 一0 1 5 2 4 6 52 ，8 8 6 6 e - 0 1 5 35 52 8 8 6 6 e 一0 1 5 o 9 6 52 8 8 6 6 e 一0 1 5 k5 1 52 8 8 6 6 e 一0 1 5 l 6 51 2 6 3 3 e 一0 0 6 26 51 2 6 3 3 e - 0 0 6 o 86 59 9 9 2 0 e - 0 1 6 2 8 1 0