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

摘要 信赖域算法是求解最优化问题的一类有效算法，该类算法的基本思想是：通 过一系列信赖域子问题的最优值逼近最优化同题的解信赖域算法的一个显著优 点是其稳定的数值性能，并适合于求解病态最优化问题在一定条件下，信赖域 算法具有全局收敛性和超线性收敛性但是传统的信赖域算法也有其局限性，当 信赖域子问题的h e s s i a n 矩阵不正定时，在数值计算上存在一定困难，而且很难 保证其具有超线性收敛速度 w uq j ( 2 0 0 4 ) 提出了修正的b f g s 公式，并将其应用于一般无约束优化问 题的信赖域算法中，得到了无约束优化同题的一种修正的b f g s 信赖域算法，该 算法可保证迭代矩阵的正定性，并在一定条件下，证明了其收敛性 本文将无约束问题的修正b f g s 信赖域算法成功地应用于约束优化问题 对于不等式约束优化问题，通过修正b f g s 公式构造了新的信赖域子问题，从而 得到不等式约束优化同题的修正b f g s 信赖域算法，并在一定条件下证明其可行 性对于般约束优化问题，先通过罚函数法将其转化为无约束优化问题，再利用 无约束问题的修正b f g s 信赖域算法，进而得到一般约束优化问题的修正b f g s 信赖域算法，并证明该方法具有全局收敛性数值实验亦表明，该算法是有效的 关键词：无约束优化；非线性约束优化；信赖域方法；b f g s 信赖域方法；全局 收敛性；收敛速度 a b s t r a c t t r u s tr e g i o nm e t h o d sa r ee f f i c i e n tf o rs o l v i n gn n c o n s t r a i n to p t i m i z a t i o np r o b - l e m s t h eb a s i ci d e ao ft h e s em e t h o d si st oa p p r o x i m a t et h eo p t i m i z a t i o np r o b l e m b yas e q u e n c eo fq u a d r a t i cm i n i m i z a t i o np r o b l e m ss u b j e c tt os o n i ct r u s tr e g i o n a na t t r a c t i v ep r o p e r t yo ft r u s tr e g i o nm e t h o d sl i e si nt h e i rm m a e r i e a ls t a b i l i t ya n d r o b u s t n e s s t h e yc a nb ea p p l i e dt os o l v ei l l - e o n d i t i o n e dp r o b l e m s u n d e rc e r t a i n c o n d i t i o n s ，t r u s tr e g i o nm e t h o d sa r eg l o b a l l ya n ds u p e rl i n e a r l yc o n v e r g e n t h o w - e v e r ，t h et r a d i t i o n a lt r u s tr e g i o nm e t h o d sm a yh a v el i m i t st h eh e s s i a nm a t r i xo f t h et r u s tr e g i o ns u b p r o b l e mm a yn o tb ep o s i t i v ed e f i n i t ei nt h i se a s e ，t h et n l s t r e g i o ns u b p r o b l e mi sr e l a t i v e l yd i f f i c u l tt os o l v e ，t h es u p e rc o n v e r g e n c er a t ei sh a r d t or e t a i n w uq j ( 2 0 0 4 ) p r o p o s e dam o d i f i e db f g sn p d a t ef o r m u l a ，w h i c hw a sa p p l i e d t oag e n e r a ln o n l i n e a ru n c o n s t r a i n to p t i m i z a t i o np r o b l e m h e n c e ，h eo b t a i n e da m o d i f i e db f g st r u s tr e g i o nm e t h o df o rn 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 m n t h i s m e t h o dh a st h ep r o p e r t yt h a tt h eg e n e r a t e dm a t r i x e sa r ep o s i t i v ed e f i n i t e u n d e r c e r t a i nc o n d i t i o n s ，t h em e t h o di sf e a s i b l e i nt h i sp a p e r ，w es u c c e e dt og e n e r a l i z et h em o d i f i e db f g su p d a t ef o r m u l at o 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 m f o ri n 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 np r o b - l e m ，w el l s et h em o d i f i e db f g su p d a t ef o r m u l ac o n s t r u c tan e wt r u s tr e g i o n s u b - p r o b l e m ，a n dt h e no b t a i nam o d i f i e db f g su p d a t et r u s tr e g i o na l g o r i t h mf o r i n 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 np r o b l e m u n d e rc e r t a i nc o n d i t i o n s ，w ep r o v e t h em e t h o di sf e a s i b l e f o rg e n e r a ln o n l i n e a rc 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 m ，w e l l s ep e n a l t yf l m c t i o nm a k et h ec 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 mt ou n 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 ，a n dt h e nw ea p p l yt h em o d i f i e db f g su p d a t ef o r m u l ai n t oi t h e n c e ，w eo b t a i nab f c su p d a t et r u s tr e g i o na l g o r i t h mf o rg e n e r a ln o n l i n - e a rc 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 mt h es a m ea sc h a p t e rt h r e e w ep r o v et h e m e t h o di sf e a s i b l ea n di t sg l o b a lc o n v e r g e n c e a tl a s t b yn u m e r i c a lr e s u l t s 口e g i v e nw h i c hs h o wt h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d k e y w o r d s ：u n c o n s t r a i n e do p t i m i z a t i o n ；n o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n ； t r u s tr e g i o nm e t h o d ；b f g st r u s tr e g i o nm e t h o d ；g l o b a lc o n v e r g e n c e 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：关啦杨日期：弘少年土月封日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名：关名z 掐 导师签名：黟乏弓炙 日期：7 年上月3j 日 日期： 2 耐年f 月日 第一章绪论 1 1 最优化问题算法概述 最优化理论与方法是一门应用性很强的学科。它是用来研究某些数学问题的 最优化解随着计算机的高速发展和优化计算方法的进步，规模越来越大的优化 问题也可以进行求解最优化在航空航天，生命科学水利科学地球科学工 程技术等自然学科领域和经济金融等社会科学领域也发挥着越来越重要的作用 非线性最优化是2 0 世纪5 0 年代发展起来的，它讨论非线性决策问题的最佳 选择，构造寻求最佳解的计算方法。研究这些计算方法的理论性质及实际计算表 现随着电子计算机的发展和应用，非线性最优化理论和方法有了很大的发展 目前，它已成为运筹学的个重要分支，并且在自然科学，工程技术，经济管理， 系统工程，特别优化设 p 等诸多领域得到广泛的应用，成为一门十分活跃的学 科 最优化问题的般形式为t m i n ，( z ) ，z f ，( 1 1 1 ) 其中z j p 为决策变量，f ( x ) 为目标函数，fcj p 为约束集或可行域如果 f = 形，则上述问题称为无约束优化同题；否则称为约束优化问题，通常记为 m i l l ( = ) ，。f ， s t 皿( 茁) 0 ，l = 1 ，2 ，仇，( 1 1 2 ) 吻如) = 0 ，j = 1 ，2 ，l ， 这里卯( $ ) ，0 = 1 ，2 ，m ) ；h j ( z ) ，o = 1 ，2 ，1 ) 均是约束函数 对于上述优化问题，已经提出了很多有效的数值计算方法，如线搜索类型的 方法和信赖域方法等线搜索类型的方法，即每次迭代时产生个搜索方向，然 后在搜索方向上进行精确的或不精确的一维搜索，以得到下个迭代点信赖域 方法是一类很新的方法，它和线搜索法并列为目前求解非线性规划的两类主要的 数值方法信赖域方法的思想新颖，算法可靠，具有很强的收敛性，它不仅能很 快的解决良态同题，而且也能有效的求解病态的优化问题因而对信赖域方法的 研究是近2 0 年来非线性规划领域的一个重要的研究方向，是当今寻求如何构造 新的优化计算方法的重要途径因此，非线性规划信赖域方法对许多学科的研究 都有重大的意义下面我们将详细介绍信赖域算法的基本思想及其有关性质 1 2 非线性约束优化问题的信赖域算法 1 2 信赖域算法 信赖域算法的起源可以追溯到解非线性方程组 f ( x 、= 0 的l e v e n b e r g - m a r q u a d t 方法，该算法中，迭代点列 “) 的产生方式为 x k + l = 瓤+ 以， 其中，以是下面的线性方程组的解 ( a ( z ) r a ( x k ) + k ，) d + a ( x k ) t f ( w k ) = 0 ， ( 1 2 1 ) 这里，是单位矩阵，a ( x ) 是，( z ) 的j a c o b i 矩阵的转置，k 0 是参数，若k = 0 ， 相应的算法即为众所周知的g a u s s - n e w t o n 法，因此，l e v e n b e r g o m a r q u a d t 方法 可看作是g a u s s - n e w t o n 法的一种修正形式，参数k 0 的作用是为了克服当 f ( x ) 病态时，g a u s s - n e w t o n 法在计算上的困难 直接计算可得到l e v e n b e r g - m a r q u a d t 方法中呶的表达式如下 d k = 一( a ( z ) r a ( x k ) + a k l ) 一1 a ( 瓢) t f ( x k ) ( 1 2 2 ) 容易看出，由( 1 2 2 ) 定义的d 七是问题 曲l i f ( 孤臻赞) 忾 ( 1 s t 悯i 以 ”。1 的解，等价地，$ l 是下面最优化问题的解 酬陟s t ，志a ( ：稳拶2 m z 忙一瓢0 以 、7 由于约束条件忪一靠s 磊的存在，我们将l e v e n b e r g - m a r q u a d t 方法视为信赖 域法约束区域 d 彤i i l d l i 奴) 称为信赖域，表示，( z ) 的线性近似，( 瓢) + a ( x k ) ( x z 女) 可以信赖的区域，参数如 0 称为信赖域半径问题( 1 2 3 ) 和 ( 1 2 4 ) 称为信赖域子问题 求解无约束优化问题( i i 1 ) 的信赖域算法可看成是上面的算法的推广求解 无约束问题( 1 1 1 ) 的信赖域算法的迭代过程如下 g l = 瓢+ 以 硬士学位论文 3 其中也是下面最优化问题的解 m i n 讯( ) = d r b k d + v f ( z k ) t d 8 t i i d i 以 其中凤酽“，等价地，。k + i 是下面最优化问题的解 曲饥z 2 虹0 嘲i i x - x k l 0 ，使得 肛一2 1 0 0 ，则矩阵b k + l 也是对称正定的 证明用归纳法证明 z t b k z 0 ，v z 0 由条件知，玩是正定的今假定对于某个数k 0 ，结论成立，并记风= l l t 为风的c h o l e s k y 分解设 则 m 2 l t z ，l = l r s k ， ，b k + 1 z = z t ( b k + = z t ( b k = f m r m 一 由c a u c h y 不等式知 e r t t m 一( 鼎) 2 0 ， - - = t - - - 又由于题设y t s k 0 ，故( 2 1 2 ) 最后个等式中第二项非负，从而 ，b k z 0 ， 1 0 ( 2 1 2 ) ( 2 1 3 ) 硬士学位论文 1 1 由于o 0 ，在( 2 1 3 ) 中等式成立当且仅当仇与竹平行，即当且仅当2 与8 k 平 行面当。与靠平行时，便有o = p 以，卢0 ，这时 篮：俨订船 o ， 班乳 即，当z 与8 k 平行时。( 2 1 2 ) 最后个等式中第二项严格大于零于是对任 意z 0 ，总有 氐+ l z 0 成立口 修正公式( 2 1 1 ) 使矩阵反保持正定是非常重要的，若风正定，则日标函 数，( 功的局部二次模型就是严格凸的，有唯一的局部极小点，算法产生的搜索 方向以就是，( z ) 在瓢处的下降方向我们知道，矩阵风正定的充要条件是 程乳 0 ，显然，若，( z ) 是一致凸函数，则总有硬乳 0 ，而与线搜索无关；对 于非凸函数，( z ) ，则当采用精确线搜索时，卵8 k 0 也成立此时，相应的拟 n e w t o n 方向是函数，( z ) 在靠处的下降方向在拟n e w t o n 算法中修正公式采 用b f g s 公式，岛+ l 由( 2 1 1 ) 确定，则相应的算法称为b f g s 算法 2 2 算法 b f g s 修正公式的改进 用虻代替( 2 1 1 ) 中的即城21 | 潞弧，我们得到一个关于城的修正 钆，= 玩+ 蓑一警 ( 2 z 1 1 ) 我们将公式( 2 2 1 ) 与一般的信赖域算法( 1 2 1 ) 相结合。得到一种修正的 b f g s 信赖域算法该算法能保证矩阵风艇定的 算法2 2 1 ( 修正的b f g s 信赖域算法) 步0 给定常数d 0 ，7 ( 0 ，j ) ，初始点x 0 ，初始信赖城半径6 0 ( 0 ，1 ) ，令 七= o ： 步1 求解子问题( 1 2 5 ) 得解呶j 步2 计算比值“i 步了 “= m 。怎埘z 黑：= 三群乏：三+ 。豁； 1 2 非线性约束优化问题的信赖域算法 步4r 若 i b 2 j ，若n 亿则令$ 1 = + 也，否则令钆+ l - - - - x k ，利 用修正公式( 2 2 1 ) 产生且饥1 ，令以+ 1 ：= 以，：= 七+ 1 ，转步1 由上面的算法可以得到下面的性质 性质2 2 2 若矩阵k 是正定的，则算法2 2 j 产生的校正矩阵f k + 1 是正定的 证明当月k 正定时，有 舻乳= ( 畿矿靠= 错 = i s b k s k + o ( 1 l s k l l 2 ) i l 佻+ o ( 1 ) l l l s , k l l 2 o 其中乳= 戤+ l 一钆，讥= 雏 l g k 饥是鼠最小特征值，所以玩+ 1 是正定 的口 2 3 收敛性 为了建立算法2 2 1 的全局收敛性和收敛速度，我们需要下面的假设条件 ( a ) ，( z ) 在三( 知) 是二次连续可微的且存在m 0 ，使得l i b k l l 0 使得矿铲，( 。) t m l l t l l 2 , 地l ( x o ) ，t j p 其中l ( x o ) 为定义的水平集l ( 铷) = 扣j p ：l ( x ) ，( 知) 引理2 3 1 若( b ) 是合理的，则水平集l ( z o ) 是有界闭凸集【1 1 】 引理2 3 2 若l ( z o ) 是有界闭凸集，则 瓢) 存在聚点，设霉k 一矿，令矽= v 2 ，( 矿) ，则可推得伊是正定的 定理2 3 3 由假设条件( a ) 、( b ) 及引理, 2 0 2 0 i 和引理2 袅2 可知，算法9 2 1 产 生一个满足一阶和二阶必要条件的聚点矿 证明由算法产生的序列中存在一个子序列，满足下列情况之一 ( 1 ) n o ( g l b 表示以的总体最小界) 取矿为上述子序列的任一聚点 硬士学位论文 首先讨论情形( 1 ) 假设9 ) 0 ，对任何x k ，考虑最速下降步。可有 时堕i i g 。l l , m 卅妣+ 案， ( 2 3 1 ) 其中，p 是搜索步长 g 看b k g k 。，则当= 美警岳时，愀( 稆雏) 取得极小值，记为 = 蕊i l g k l l ； 由于s = 一疏对于信赖域子问题( 1 2 5 ) 是可行的，所以 锹= f k 一讯( 8 ) 一饥( 8 ) ( 2 3 2 ) 因为以一o ，屿班一他铲 o ，所以对充分大的可得 讯旦笋垒= ；以。鲰怯 ( 2 3 3 ) 若鳍玩靠 0 ，从( 2 3 2 ) 中第三个等式也可直接得出似氏i 0 2 因 此，当0 轧0 0 时， 烘s 兰丽2 i i g 。1 忙川。训， ( 2 3 4 ) 饥 ；以i i 鲰0 2 2 ” 再由泰勒展开式，有 所以得到 = 仇- f d ( 0 钆旧) “= 瓮叱“。瓦。1 ， 1 4 非线性约束优化问题的信赖域算法 这与“ o 2 5 矛盾，所以g ( z ) = 0 成立 若矿是半正定的，再讨论情形( 2 ) ，注意到 f k 一，( 矿) a f k 又f l 一，( ) 为常数，所以有 0 2 5 帆 量i 因此可得到仇一0 文中定义 妒+ 0 ) = ，0 ) + s r g ( = ) + s r b 。8 设满足0 0 ，故这时约 束川l 髭是无效约束，其对应的拉格朗日乘子为零，从而约束问题 m i n 妒* ( s ) ， s t 的一阶必要条件为9 ( 矿) = 0 ，二阶必要条件为伊半正定，证毕 口 第三章非线性不等式约束优化问题的修正b f g s 信赖域 算法 考虑如下约束优化问题 3 1 引言 m i n ，( 。) ， s t g ( z ) 0 ， ( 3 1 1 ) 其中z j 只，：舻一r ，g ：j p 一舻均是光滑函数，记f 为问题( 3 1 1 ) 的可 行集 令鼠是个对称矩阵，z 是一可行点，逐二次规划法是解下列予问题的搜 索方向 m d i n 妒0 + d ) = ，( 动+ v ， ) t d + d r b k d ( 3 1 2 ) s t 9 0 ) + v g ( x ) d 0 、 其中v g ( z ) = ( v g i ( 霉) ，1 ( 。) ，v 目h ( z ) ) 7 取是目标函数在$ 处的近似h e s s i a n 矩阵，我们用第二章中的修正b f g s 公式( 2 2 1 ) 来求解下个风+ 1 即，为了保证矩阵风的正定性，取 = 凤+ 籍一警 其中虻= 离弧， 函数妒扛+ d ) 是，在当前点z 处的二次模型我们增加下面的个信赖域 保证算法的凸性和收敛性 l i d l i 玩( 3 1 3 ) 其中6 是信赖域半径 当迭代点z 不是原同题( 3 1 1 ) 的可行点时，由于对无论多小的j ，子问题 ( 3 1 2 ) 的结果都是不可行的，因此，我们不能简单的对问题( 3 1 2 ) 加个限制条 件( 3 1 3 ) 本章中我们给出了个可行的信赖域算法，这种算法能够使得所有的迭代点 瓢都是可行的我们通过求解子问题( 3 1 2 ) 和( 3 1 3 ) 求解可行点巩f 处的 1 6非线性约束优化问题的信赖域算法 搜索步d 2 ，我们通过求解下面的子问题得到试探步嘏的下个试探步以 1 + m g n 1 1 d i l l , s t g ；( x kv g , ( x k ) r d ；- 4 1 1 ；，川b ( 3 1 4 ) 1 + = ，i 厶， 其中厶= i l g , ( x k ) 一割d 2 悒) ，1 口 叩则，。 + l = “+ 比，否则z i + l = ； 步8 由b f g s 校正公式( 2 2 1 ) 来计算上k + 1 k ；女+ 1 ，转步j 下面我们证明算法是可行的 引理3 2 2 如果蠼= 0 ，则z 是问题( 3 1 1 ) 的k k t 点 硬士学位论文 1 7 对于任一可行点善，我们定义有效集j ( 如下 ，( z ) = 0 = 1 2 ，m i m ( z ) = o ) 我们定义水平集l ( z o ) 如下 l ( x o ) = z i z f 邑，( $ ) ，( 1 0 ) ) 为了得到理想的结果，我们给出下面两个假设 假设3 2 3 v 吼( z ) ，l j ) ) 是线性的，并且与所有的霉l ( z o ) 无关 假设3 2 4 水平集l ( z o ) 是有界的，并且问题( 3 1 1 ) 中的函敷f , g 在l ( x o ) 的 一个开邻域n ( l ( x o ) 1 内是二次连续可徽的 注意到，l ( x o ) 显然是个闭集，因此如果假设3 2 4 成立，它也是个紧 集故，必存在正常数1 ，杨，l 一3 使得 m x l l v g ( = ) l l ，i i v z c x ) + i i - ，i i v f c x ) l i 肠 l i v 2 f ( x ) l is ，岔工( 知) ， 其中v g ( x ) v g ( x ) + = k ，k 是个恒等矩阵 引理3 2 5 算法曼2 j 是可行的 证明我们只要证明当以足够小时“ 叼和钆+ 也是可行的 在假设3 2 3 和3 2 4 的条件下，当以足够小时，子问题( 3 1 4 ) 是可行的， 并且 i i 也一耀0 = i i 硪i i 气t | | 鲤n( 3 2 2 ) 当鲰( 。) 叩如果也= 罐+ 雌，则有 l f ( x k ) 一f ( z k + d k ) 一妒( 巩) + 妒( z k + d k ) i = i v f ( m k ) t d k o 5 d ：v 2 ( z k + o k d k ) d k + v f ( z k ) t 破+ o 5 d 学最d 2 i = i ( - - v f ( x k ) 一v 2 ，( z i + o k d k ) d k ) t d ：一o 5 d l t v a f ( w k + o k d k ) d l o 5 d f k ( v * a f ( x k + o k d k ) 一玩) d 2 i _ o ( 氏一o ) ， ( 3 2 3 ) 因此，由( 3 2 1 ) ，( 3 2 2 ) ，( 3 2 3 ) 可知。当蟊足够小时，住 叩口 3 3 收敛性 本节我们将证明问题( 3 1 1 ) 的k k t 点的收敛性我们要证明两个方面的内 容，第一、如果算法不是有限终止的，则必有一个极限点是满足k k t 条件的 第二，在风的强假设条件下，可得到所有的极限点都满足k k t 条件 设d ( x ，n 是下列子问题的解 n l i n v f ( x ) t d ， d 8 t 口( z ) + v g ( x ) d 0 ， ( 3 3 1 ) i i d l l 2 下， 其中z f ，r 0 下面的两个引理对信赖域算法的收敛性起着关键的作用 引理3 3 1 令g ( x ，r ) 是问题( 3 3 1 ) 的价值函数，对任意的z f ，有g ( x ，1 ) 0 ，g ( z ，1 ) = 0 的充要条件是$ 是问题的( 3 1 1 ) 的k k t 点当矿满足假设只2 另 但矿不是k k t 点时，则必存在正敷冗和e ，使得对任意的z z | i | z 一矿8 r n f ，有g ( z ，1 ) 引理3 3 2 问题( 3 1 2 ) 和( 3 1 3 ) 的解d 2 满足下列关系式 妒( ) 一妒( + 避) 0 5 9 ( x k ，1 ) m i n 1 ，以，g ( x k ，1 ) 矿2 0 风0 - 1 ) ， ( 3 3 2 ) 其中g ( x k ，1 ) 是问题( 3 3 1 ) 在$ = x k ，r = l 时的价值函数 由( 3 2 2 ) 和( 3 2 3 ) ，我们有如下引理 引理3 3 3 如果假设3 9 3 和只幺；成立，则必存在正常数肠，使得 i ，( 孤+ 靠) 一妒( $ i + 程) i ( j i c , 1 1 4 1 1 ”1 + o 5 0 k i 川i 乳 ( 3 3 3 ) 硬士学位论文 1 9 引理3 3 4 如果假设3 2 3 和s 2 4 成立。且g ( z ，1 ) 0 ， 以m i n 1 ，9 ( 孤，1 ) 矿2 可瓦* 万，。7 的( 瓤，1 ) 互j ：南 ， ( 3 3 4 ) 则r k 叩且乳l 以 证明根据( 3 3 4 ) 可得1 1 4 1js1 ，因此由( 3 2 1 ) ，( 3 3 2 ) 和( 3 3 3 ) 知 i “一1 is 0 5 m i n l ，妣1 ) 矿2 南，。7 5 9 ( x k ，1 ) 赤，( 3 删 假设3 3 6 存在正常数以和观，使得 0 最l i 盯l + a 2 k ，k = 0 ，1 ，2 ， 为了证明算法3 2 1 的全局收敛性，我们介绍下面的引理 ( 3 3 7 ) 引理3 3 7 假设序列 以) 和 帆) 能够对所有的k 有以磊成立，其 中k 是正整数，t 是正常数，令j c k k + 1 ，k + 2 使 以+ l 而氏，七j | | c ； 如+ l n 氏，蔽孔； + l 尥，后k ； 薹叫壶) o o ， 其中，n 是满足0 1 n 的常数 荟曲瓦1 o o ( 3 3 8 ) ( 3 3 9 ) ( 3 3 1 0 ) ( 3 3 1 1 ) ( 3 3 1 2 ) 2 0 非线性约束优化问题的信赖域算法 定理3 3 8 在假设3 2 8 - 3 3 6 的条件下，算法只幺j 或者终止于k k t 点，或者 至少有一个极限点是问题( 3 1 1 ) 的k k t 点 证明根据引理3 2 2 ，如果算法3 2 ，1 终止于迭代点乳，则瓢是问题( 3 1 1 ) 的 k k t 点 如果算法3 2 1 产生一个无穷序列 z k ) ，则由引理3 3 1 ，存在0 7 ，根据( 3 3 2 ) 可得 f ( x k ) 一，( $ t + 1 ) ，7 ( 妒( z 女) 一i p ( z + d 2 ) ) 2 ，7 0 s g ( x k ，z ) m i n 1 ，氏，g ( x k ，z ) $ - ：f l b k l l - 1 0 5 ，7 6r a i n 1 ，氏，e 弘2 垅。1 ) 20 5 班m i n 6 k ，醯- 2 钌1 ) 20 s r m i n 1 ，弘2 ) m i n 以，j l 行1 ) ， 其中e 弘2 行1 0 使得 脚l i r a x k 5 霉勘( 瓢，1 ) 岛p ( 3 3 1 4 ) 硬士学位论文 2 1 为了方便起见，令= o 5 r a i n 1 ，矿2 i 南，0 7 5 5 獗：再1 石) 因此，由( 3 3 6 ) 和假设3 3 9 ，可得 6 k 0 5 r a i n 1 ，矿2 击0 7 5 5 互万1 万) = 肠 o 七只 ( 3 3 1 5 ) 类似地，令= o m i n l ，j 岛，弘2 盯一1 ) ，由( 3 3 2 ) 可得 妒0 i ) 一妒( 瓢+ d 2 ) 0 5 e r a i n 1 ，肠，e 矿2 0 - - 1 ，；肠 0 知p ( 3 3 1 6 ) 因为f ( x ) 在l ( x o ) 内是有界的，所以在p 内没有无穷迭代点换句话说，必存 在正整数硒，使得对所有的k 凰，有 + 1 = z ，以+ 1 = 氏，k p 根据定理3 3 8 ，存在成功的无限迭代点，记 ( k ) 是k p 后的第个成功迭 代，则对所有的k p ，( 如( i ) ) ，( 戤( i ) 一1 ) = ，( 瓢) ，