（运筹学与控制论专业论文）不等式约束问题的修正的sqp方法.pdf

摘要 摘要 本文提出并分析两种解不等式约束最优化问题的修正的s q p 方法，第一种 算法为序列罚函数法，在此方法中将不等式约束问题转化为无约束问题进行求 解，并且算法在经过充分的迭代后，相当于标准的s q p 算法。第二种算法是在 第一种算法的基础上提出的一种稳定的s q p 方法，在此法中每次只须求解一个 线性规划和一个二次规划，在这两种修正的s q p 方法中罚函数我们使用的是厶 罚函数。与传统的s q p 方法相比较，这两种修正的s q p 方法能够克服传统的s q p 方法中的子问题不相容的缺点，并且初始点可任意选取，在适当的条件下证明了 两个算法的全局线性收敛性和局部超线性收敛性，数值实验表明，本文中的两个 算法是切实可行的。 本文是按如下方式组织的：第一章为绪论部分；第二章给出并讨论基于s q p 法的序列罚函数法的算法及其收敛性分析；第三章给出并讨论一种稳定s q p f 方 法的算法及其收敛性分析；第四章给出l a g r a n g e h e s s i a n 矩阵的修正公式；第 五章给出本文两个算法的数值实验及其运算结果；最后是附录内容，给出本文所 用数值实验例子。 关键词：不等式约束优化问题；s q p 法；l 1 精确罚函数；全局收敛性； 局部超线性收敛性 a bs t r a c t w ep r e s e n ta n da n a l y z et w om o d i f i e ds q pm e t h o d sf o rs o l v i n gn o n l i n e a ri n 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 np r o b l e m s t h ef i r s tm e t h o di sa l ls e q u e n t i a lp a l t ya l g o r i t h m , i nt 1 1 j s m e t h o d ”c o n s t r a i n o do p t i m i z a t i o np r o b l e m si st r a n s f o r m e dt on o n c o n s t r a i n e do p t i m i z a t i o n p r o b l e m s a f t e rs u f f i c i e n t l ym a n yi t e r a t i o n s i ti sp r o v e dt h a tt h ea l g o r i t h mb e h a v e se q u i v a l e n t l yt o t h es t a n d a r ds q pm e t h o d 1 1 s e c o n dm e t h o di sb a s e do nt h ef a s tm e t h o d i ti sar o b u s ts o p m e t h o d i nt h em e t h o dw eo n l ys o l v e sal i n e a rp r o g r a m m i n gs u b p r o b l e ma n daq u a d r a t i c s u b p r o b l e ma te a c hi t e r a t i o n c o m p a r e dw i t ht r a d i t i o n a ls o pm e t h o d , t h et w om o d m e ds o p m e t h o d sc a r lo v e r c o m et h ei n c o n s i s t e n c eo fs u b p r o b l e m si nt h et r a d i t i o n a ls q pm e t h o d t h et w o m e t h o d sc a l ls t a r tf r o ma l la r b i t r a r yi n i t i a lp o i n t m o r e o v e r , o a rm e t h o d si sb a s c d0 1 1l te x a c t p e n a l t yf u n c t i o n u n d e rm i l dc o n d i t i o n s o m eg l o b a lc o n v e r g e n c er e s u l t s 辫p r o v e da n dl o c a l s u p e r l i n e a rc o n v e r g e n c er e s u l t sa r ea l s oo b t a i n e d p r e l j l i l i n a r yn u m e r i c a le x p e r i m e n t ss h o wt h e e f f i c i e n c ya n ds t a b i l i t yo f t h et w om e t h o d s t h i sp a p e ri so r g a n i z e da sf o l l o w s i nc h a p t e r1 , t h eb a c k g r o u n da n dt h em a i nr e s u l t so f t h i s p a p e ra r eg i v e n w ep r e s e n ta ns e q u e n t i a lp e n a l t ya l g o r i t h mf u rn o n l i n e a ri n e q u a l i t yc o e d o p t i m i z a t i o na n dd i s a s st h ec o n v e r g e n c er e s u l t so f t h em e t h o di nc h a p t e r2 i nc h a p e r3 ，w e p r e s e n tam b a s ts q pa l g o d t h mf o rn o n l i n e a ri n e q u a l 耐c o n s l r a i n e do p t i m i z a t i o na n dd i s u s st h e c o n v e r g e n c er e s u l t so f t h em e t h o d t h em o d i f i e df o r m u l ao f l a g r a n g eh e s s i a nm a t r i c si s 舀v e ni n c h a p e r4 i nc h a p e r5 ，p r e l i m i n a r yn u m e r i c a le x p e r i m e n t so f t h et w om e t h o d sa r e 舀v e n a n di nt h e a p p e n d k t h ei n e q u a l i t yc o n s 仃a l n e dp r o b l e m sw es o l v e da r ep r e s e n t k e y w o r d s ：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 ；s q pm e t h o d ；l 【a c t p e n a l i t y f u n c t i o n ；g l o b a lc o n v e r g e n c e ；l o c a ls u p e r l i n e a rc o n v e r g e n c e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：圣i ! 室重 日期：兰盟：f ：! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲孙守霞导师躲瞢文吼如m 占 第1 章绪论 1 1 背景知识及主要结果 第1 章绪论 在非线性约束最优化问题中不等式约束优化问题的数学表达式为： r a i nf 一 ( 1 1 ) s t q ( 的0 ，f i = l ，2 ，研) 这里n f i n 表示求极小，盯= s u b j e c t t o 意思是受限制于，x 是万维向量，其分量 为五，屯，毛，f ( x ) 及q ( 力( f = 1 ，m ) 都是定义在上的是实值连续函数， 且至少有一个是非线性的，m 是一正整数，八功被称为目标函数，q ( 力 ( f = 1 。m ) 被称为约束函数。 非线性约束最优化问题已广泛涉及到许多重要的领域，其中包括经济模型， 金融，网络与运输，数字集成设计，图像处理，化学工程设计与控制，分子生物 学，环境工程及军事科学等等。在过去的几十年间，由于非线性约束最优化在许 多领域的重要应用，其理论和方法己得到了很大的发展。随着最优化理论的广泛 应用，非线性不等式约束优化问题的解法需日趋完善，而此问题一直是非线性约 束最优化问题的一个难点，也是广大研究者正在致力解决的问题之一，此问题的 完善将会使最优化理论得到更广泛的应用。 目前，常用的非线性不等式约束优化问题的解法主要有以下几类方法：一 类是将约束问题转化为一系列无约束问题，通过求解一系列无约束最优化问题， 来得到约束问题的最优解，这类方法称为序列无约束极小化方法。另一类方法是 序列二次规划法( 简记为s q p ) ，序列二次规划法对于非线性约束优化来说是最有 效的方法之一，s q p 方法能够被应用于一维搜索和信赖域方法中，并且它对于大 小问题都是适用的。本文中将要讨论的两种方法都是针对s q p 方法提出来的。 自从w i l s o n ( 1 9 6 3 ) 关于s q p 的工作问世，以及r a n ( 1 9 7 7 ) 和p o w e l l ( 1 9 7 8 ) 对此工作成功地改进后，s o p 方法得到广泛和深入的研究。s q p 方法是一种迭代 法，它通过以下的迭代形式来逼近问题的解 x + 12x k + o l k d k 其中x 。为当前迭代点，口。为步长，d 。为搜索方向。 对于非线性不等式约束优化问题( 1 1 ) 来说通过求解如下形式的子二次规 划 1 n f i n 寺b k d + v f ( x i ) 7 d，1 口、 、， j j q ( 黾) + v q ( 毪) 1ds 0 i = 1 ，m 北京工业大学理学硕士学位论文 以得搜索方向d i 。b k 是l a g r a n 百a n 函数l ( x ，d = 八力+ 兰a f c l ( 功h e s s i a n 矩阵的 近似，a = ( 无，a ：，a ，) 7 是乘子向量的近似。 s q p 算法良好的收敛速度使之成为许多学者研究的热点，但是q p 子问题的 线性约束必须相容对s q p 方法来说是非常严重的限制。在这个算法的结构中， p o w e u 1 在每一次迭代中求解一个修正的予问题 r a i n 去b k d + v f ( x k ) 7 d + 寺3 k ( 1 - p ) 2 占j 鸬q ( 耳) + v q ( 耳) r d o i = 1 ，m 其中心= 仨怒冀 且唧s 1p 。是一个惩罚参数。借助于其他 一些技巧，证明这个修改是非常成功的，但是b u r k e 和h a r t ( 1 9 8 9 ) ，并且b u r k e 提出了一个简单的例子表明这个算法不是最好的。 另一方面，基于信赖域方法，f l e t c h e r ( 1 9 8 1 ) 2 】提出了对于问题( 1 1 ) 的 s t , q e 方法。 r a i n 毒d 7 尉+ v f ( 工) 7 d + 8 , 1 1 0 r “，但是t o n e s 的修正方法却没有给出 一个关于收敛性的证明。 e s p e l l u c c i ( 1 9 9 8 ) 5 对于一般约束问题的子问题的不可行问题提出了一种新 的技巧，把求解s q p 问题转化为求解如下形式的子问题： m i n ，1 _ d 7 b d + v f ( 工) 7 d + 口玩+ b r v + 等酬枞i | 2 + | w ) 2 第1 章绪论 v c i ( 力2d + c i ( u a j j v h ( x ) 1d + ( 曲+ 1 8 = o , v 0 u a 0 其中a = a ( x ，o 3 = p ：q ( 矽田 = d i a g ( ) ，只= l ，如果h i ( 力 o 使得 妒o ；埘) = y ( x ；u o ，v t o ，刃 i 正n - 见参考文献 1 2 1 。 引理2 2v x r 4 ，y 似回是f 上的一个凸函数。 7 ，。 ：耋三些銮兰翌兰翌圭：竺兰三 证明：见参考文献 1 2 】。 2 3 算法模型 算法2 1 步1 给定初值五，墨是一个正定矩阵，q o , o ；，0 一；d ：丑t 巩，令 一一 避骅胁t 闱旷转觊【 一【毪，吼) j 步4 选择口。为序列 1 ，2 ，。 中的最大数且满足 令x + l 。x t b e t t d t ， 中， 1 ( x k + a d k ) 一西卅( x t ) 筇口，i ( x t ；d i ) 修正夙得到曰，k = 4 汁1 ，转步3 。 2 4 算法的全局收敛性 定义2 1，被称为一个可行稳定点或k k t 点如果下列条件被满足： ( i ) ( ，) = o ； ( i i ) 对于所有满足v c , ( x ) 0 的d 都有d 7 w ( 工) o ，i e 厶( x ) 。 定义2 2x 被称为一个不可行稳定点如果下列条件被满足： ( i ) ( ，) o ； ( i i ) m i n l ( c ( x ) + v c ( 工+ ) 锄+ l | 1 = ( ，) 。 由定义可知，一个不可行稳定点是线性约束的1 一范数的最小值。 定义3x 被称为一个奇异稳定点如果下列条件被满足： ( i ) w ( x ) = o ； ( i i ) 存在收敛到，的序列 儿 使得y 魄) o 并且 。1 1 1 1 1 些划坚型里! 螳划：；。 一一1 ” y l y t j 引理2 3 如果x r 1 是一个不可行稳定点或奇异稳定点，则存在则存在 p c 。0 和p 使得下面的一阶必要条件成立： 8 第2 章解不等式约束优化问题的一种序列罚函数法 p 嗣( 功+ p y c 。( 力= 0 n 0 , i = o ，l ，m 证明：见参考文献【8 】中的引理3 4 。 引理2 3 描述了一个不可行稳定点或奇异稳定点的特点。在下面的分析中我 们假设以下条件总是成立。 假设2 1 ( i ) ( 刁，c i ( x ) 为二次连续可微函数，f = 1 ，2 ，m 。 ( i i ) m ，k = 1 , 2 ，为正定矩阵并且存在常数m l o , m 2 o 满足 m 删卜矿b 胡i 0 ；则黾是一个 不可行稳定点，如果妒( 黾) = o ；则黾是一个可行稳定点。 证明：因为算法在第2 步无限次的循环，那么盯i o o 并且以= o ，对于任意 的d r 4 ，我们有 1 ，d 7 尉+ v f ( x ) 7 d + 吒0 ( c b i ) + v c g i ) 切+ i 吼y ( 黾) 两边同时除以盯。并且令k - - - ho o ，我们得到 0 ( c g 。) + v c ( x 。) o ) + 岭妒阮) 因此 m i n i | ( c ( 耳) + v c ( 毪) 勿) + l l 。= 妒( 黾) 所以如果 c ，( 黾) o ；则耳是一个不可行稳定点。 如果y ( 黾) = 0 ，则也是一个可行点，因为反= o 是m i ( 回的最小值点，而 吼( d ) 是关于d 的凸函数，我们知道0 a 吼( o ) ，其中a 巩( 回是吼( d ) 在d 处的 次梯度。即 一w ( 杖) 妒”( h ；o ) 因此我们知道存在p ( x ) r 4 使得 一v f ( x d = a ：v c ( x i ) ( 耳) 姐( 耳) ) 0 f e ， f ( x a a = | | ( c ( x 。) + v c ( x , ) 铆+ l 9 北京工业大学理学硕士学位论文 恤( ) 忆l 因此毪是一个可行稳定点。 引理2 6 算法2 1 不会在第4 步无限次的循环。 证明：用反证法， 假设算法2 1 在第4 步无限次的循环，则对于v 睇( o ，1 ) 我们有 ，如k + a d d m ，b 0 a p e ，k ( x k ；d d 即 业塑鼍掣 p o 毗d k ) 口 ” 令口斗o 得到 g ：d j + 盯i ( x i ；d t ) 曰，i ( x i ；d ) 由引理2 1 知矿( x ；d i ) i c ，b i ；d t ) ，所以有 ( 1 一d o 。t ( x k ；d k ) o ，( o ，去) 即 日，i ( x k ；d k ) 0 另一方面，算法2 1 到达第4 步那么矾0 ，因此我们有 o o k ( x t ；d t ) 一i 1 口i t 占i d i ；m 。i i d 旷 0 ，则序列b i ) 的任意一个聚点都属于不 可行稳定点集。 证明：我们分两种情况来证明： ( 1 ) 盯。在第2 步一个无限次的迭代中增加。在这种情况下我们能够假设存 在序列 x 。 的子列 轴 使得盯。在点翔处的至少增加一次，因此无= o 是下面子 问题的解 r a i n 去d 7 玩d + v f ( x d 7 d + j l ( c ( x d + v c ( x 。) r d ) + i l 。 即对任意的d e r 4 ，我们有 告d 7 d + v f c x d 7 d + 岭( x d + v c ( x 矗) 切+ 忙少魄) 由假设2 1 ( 1 i d 知道子列 了目) 收敛到，两边同时除以盯。并且令f m 得到 o ) + v c ( x ) 勿) + 忙妒( ，) 这说明x + 是一个不可行稳定点。 ( 2 ) t l r k 只在第2 步有限次的迭代中增加，在这种情况下，我们假设定理的 结论为假，因此存在整数和一个紧集q 对于所有的k k o 使得黾q ，对于所 有的x e q 有( 石) 0 ，并且在q 中没有不可行稳定点，又由不可行稳定点的定 义及q 的紧致性，因此存在常数v 0 及正数万使得对于充分大的数k 有 m i n h ：。，i i c ( n ) + v c q 。) 切+ i i 。妒b t ) 一1 ，工e q 选择d 2 使得忙2 i l 一i i d 强 巩 矛盾。此定理得证。 定理2 3 如果盯i a o 并且陋妒g 。) = o ，则序列饥) 属于奇异稳定点集。 证明：见参考文献【8 】中的引理4 5 。 定理2 4 如果对于充分大的k 有盯。= 盯，那么序列 x 。) 属于稳定点集。 证明：不失一般性，我们假设盯。= 盯，并且对于所有的k p ，上( 黾，d ) 一i 1 口i t b i d 由假设2 1 ( i i ) 我们有 o o i ( x i ；d t ) 一i 1 口1 b d i 一；m l l i d t 旷 o 使 得x c t - w 有l l d , i i ，现在我们首先证明序列舰 远离0 ，实际上，如果q 不远 离0 ，那么我们可以假设珥斗0 ，因此 。酬( 新+ ( q ，) d j o 卅( x f ) + ( q r ) o 鲥( x ；d j ) 即 中“( 船+ ( q r ) d j ) 一m “( x j ) ( q y “q f ；d ，) 令i 寸。，由引理2 1 得到 以( 工，d 一) ( 工；d ) z o o ( x ，d ) 所以 以( ，d ) o 另一方面由d o 得到巳( ，d ) m j p o ，得到矛盾，因此q 远离0 1 2 第2 苹解不等式约果优化问题的一种序列罚函数法 因为序列 o 。( 黾) ) 单调递减并且有界，因此中( 吒+ ) 一m 。( x d j 0 ， 得到瓴，巩) 专o ，又远离0 ，所以气( ，4 ) j o ，又因为 只。( 黾，4 ) 吼( 以) 一y ( ) ，吼( 吃) q ( o ) = o - k ￥, ( x k ) ，所以存在常数0 8 l 使得只。( 黾，反) s 觏矿( x d ，所以有 一 妒“) 专0 即 矿( ，) = o 这证明，是一个可行点另一方面我们有色( 一，珥) 肘。憾酽 1 1 a 1 1 ：i i ( a ) + l i ： ( 2 1 7 ) 其中是矩阵4 的广义逆。 令 云= 七( c ( 黾) + v c ( 耳) 瓴) + i = o ) 引理2 8 如果假设2 2 和假设2 3 的条件都满足，则对于充分大的k ，我们有 1 4 瓴) + v c ( 黾) ) + i | l ：o 证明：如果引理的结论为假，则存在一无穷的数列七芒五。对每一个 七正乏，1 1 五1 1 。= 盯。，很明显，对充分大的数七叠孟，我们有，。( 故) 厶( ，) ，下面令 ( 五l = ( 旯l - ，厶f ) 一 五i = ，。( 耳) 2 , k = 0 _ ，z o ( x ) 、，( x d 则 h 剐i i i i 。 。制i 。爿 因此由( 2 1 5 ) 。( 2 1 7 ) 及假设2 1 ( i i ) 我们得到 i ：29 夥魄) + 4 瓴) 训：州驯： ( 1 ，j ) 1 1 1 叮( 黾) 一4 ( 也) 五+ 彳( x 五一五) i i ： = ( 1 m 2 ) l j 爿+ c l 一五，i l ：十。f - x l l ：， 却卜叱肛) + | | 2 i i 删 卜互k 慨石肛) + | | 2 i i ) + d ( 1 ) 斗h 凡胍石p ) + j | 2 i i ) + d ( 1 ) ( 盯+ 一川l ) o 使得 ， v 七茌k 因此对于任意的七仨云 i i k 。一| | 2 = 恢喀驴( 盯一2 鸩蛎i i ( a ) + p o ( 2 i g ) 因为由无穷多的七仨五，( 2 1 8 ) 和假设2 2 的( i i ) 矛盾，因此引理的结论为真。 此引理说明。对于充分大的k 搜索方r a 是下列子问题的解： m i n j7 b i d + v ，( x t ) 7 d s t c f ( z t ) + v c f ( z t ) 1d 0f = 1 ，m 也就是说，当k 充分大时有算法2 1 产生的搜索方向相当于由标准的s q p 算法产 生的方向。因此，当k 充分大时算法2 1 相当于标准的s q p 算法。 为了证明无约束问题的局部超线性收敛性，还需要假设二阶充分条件成立， 并且l a g r a n g e 函数的h e s s i a n 矩阵在有效约束的梯度的零空间上有很好的近似。 假设2 4 ( i ) 对于所有满足d 7 v q ( ，) s 0 的非零向量d 都有d w d 0 ，i o ( x ) ， 其中 w = v 2 f ( x ) + ( n v 2 c l ( x ) ( i i ) 觏忙( 色一w ) 以i i ：州破 ：= o ，其中p 是4 的切空间上的投影矩阵。 由标准的s q p 的超线性收敛性结论的分析，得到下面的引理。 引理2 9 如果假设2 2 、2 3 、2 4 的条件被满足，则有 熙甓早= 。 由于价值函数的非光滑性，“m a r a t o se f f e c t 有可能发生从而算法达不到超线 性收敛性，为了避免这种情况，m a y n e 和p o l a k ( 1 9 8 2 ) ，c o l e m a n 和 c o n n ( 1 9 8 2 ) f l e t c h e r ( 1 9 8 2 ) 1 4 等提出3 - - 阶导数修正法，对于我们的算法我们求 解下面的线性方程组的最小二乘解。 c f ( x i + d i ) + v c l ( x t ) o = o ，i r ( x d ( 2 1 9 ) 令d 。是此线性方程组的最, j , - - 乘解，如果此线性方程组不相容或者是它的最小 二乘解的范数不小刁：l l d t 我们令巩= o ，当我们得到二阶修正步巩后，在第3 步中的一维搜索由下面的弧形搜索代替： 第3 步选择口。为序列 l ，2 ，中的最大数且满足 e p ，i ( x k + a d k + a 2 d i ) 一o ( x k ) o 满足 m 删卜矿b , t d a m ：例2 ( i i i ) x 。) ， d i ) - 一致有界。 因为对约束函数没有任何限制了，由算法3 1 产生的序列的聚点可能为下列 三种稳定点点中的一种，下面分别给出这三种点的定义。 定义3 1 如果x 是可行的并且存在向量p = ( 尸。p 2 7 ，p 。ye r ”使得 g ( 曲+ 4 ( 力p = o ，p ，0 ，p ，c ，( x ) = 0 ，i = 1 ，2 ，m 。则x 被称为问题( 1 1 ) 的严 格可行稳定点。 定义3 2 如果工是不可行的并且m i n 0 ( c ( 工) + v c ( 功o ) + i = 妒( 力，则工被称为 第3 苹解不等式约束优化问题的一种稳定的s q p 方法 问题( 1 1 ) 的不可行稳定点。 定义3 - 3 如果工是可行的并且存在不可行序列 v i ) 收敛到x 使得 1 i r a 些型坦尘! 塾! 弛：1 一2j t m t v j 则x 被称为问题( 1 1 ) 的奇异稳定点。 以上三个定义和算法3 1 是密切相关的，与l i u 和y u a n ( 2 0 0 0 ) 8 的引理3 4 相似我们能够证明以下引理。此引理描述了不可行稳定点和奇异稳定点的特点。 引理3 1 如果x r 4 是一个不可行稳定点或者是奇异稳定点，则存在 p o o 和p r “使得下面的一阶必要条件成立 p o g ( x ) + p , v c f ( 力= o p ，0 ，i = 0 ，1 ，m 证明：见参考文献【8 】中的引理3 4 。 引理3 2 如果算法3 1 在点瓢处停止计算，那么瓢或者是一个不可行稳 定点或者是一个严格可行稳定点。 证明：( 1 ) 如果算法3 1 在第2 步结束， d k = o , 那么m = ，并 且z j k o 。因为z 0 ，所以x 是一个不可行点，下面我们证明 m i n l | ( c g d + v c ( x 。) o ) + i i ，= 妒( x o 其中5 c ，( 毪) = 瓴) + ( 故) = ( 毪) 。实际上如果上式不成立，则存在d 2 使得 h 。= m i n | l ( c ( 柚+ v c 铉) + | l l i i ( x d 显然。2 r ，；。) 7 是子问题( 3 1 ) 的一个可行解，又根据三i 的定义我们有 矧， 矧| l g 。 这与。叫妁穗 ( 2 ) 如果算法3 1 在第3 步结束，则d 。= o 时子问题( 3 2 ) 的解，因此 满早子阖额( 32 ) 的一阶凶暮条件 2 1 北京工业大学理学硕士学位论文 g , + b k d + a j , p j , 七a l p l 2 0 q ( 耳) + 1 ( 黾) d s 乙 c l p 0 a l ：( x k ) d - 0 户 ( 吒( 黾) + 7 ( ) d z 0 ) = 0 以( 气( 屯) + 屯2 ( 稚) d ) 2 0 p ，0 ，i = 1 ，m 现在我们来证明0 磊l = o ，如果0 磊l 。，由c t ，的证明过程知工t 是不可行的， 因为算法3 1 不会在第3 步结束，那么i l 磊i ( ) = c ，( 黾) ，这说明d = 。不 是子问题( 3 2 ) 的一个可行解，产生矛盾，因此0 磊= 。因此( 3 - 2 ) 的一阶必 要条件变成 g t + a * p = 0 p ，0 c t 0 p c f ( x t ) = 0 ，f - 1 ，m 即x 。是一个严格可行稳定点。 此引理说明经过有限次的迭代后，那么x 。或者是一个不可行点或者是一个 强稳定点。 引理3 3 在第5 步中一维搜索是有定义的。 证明：因为算法3 1 在第4 步结束，因此有 秽卅( x t ；d t ) - d r b t d t p o 撕 口 令口 - h 0 得到 g i t d i + o - k 驴, ( x i ；d i ) 口，i q j ；d t ) 由b u r k e 和h a n ( 1 9 8 6 ) 5 q b 的引理4 1 我们知道y 。( x t ；d i ) y + ( x i ；d i ) ，其中 妒( x 。；d t ) 是i i ( c ( 工t ) ) + i i 。在巩处的方向导数a 所以有( 1 - 励口，。( x t ；d o o ，而 ( o ，尹1 ，产生矛盾。引理得证。 由y 啪( 1 9 9 2 ) 【1 3 】中的引理4 2 知当盯i - - o o 时，脚y q t ) 存在。 m 引理3 4 如果以母且t l i r a c 曲 o ，则存在 瓢) 的一个子列收敛到个不 可行稳定点。 证明：令s 为& 。 的一个聚点集，如果引理不成立，则对于任意的工s ， 有妒( 力o 并且定义3 2 中的等式不成立。因此，存在常数v o 及正数j 使得对 于充分大的数k 有 m i n m ：。一( x t ) + v c g 。) 勿) + l g ( x , o - v = ( ) 一1 ， 选择穰使忙2 0 0 ，使得 m i n m ：。( c ( x i ) + v c ( x 。) o ) + l s 妒( 工i ) - - y = 么( ) 一v 成立，类似于引理3 4 的证明，引理3 5 可得证。 引理3 4 和引理3 5 说明只有当盯。有界时，数列 x 。) 才能收敛到问题( 1 1 ) 的严格可行稳定点。 在以下的讨论中我们假设盯i 是有界的，即盯i 一盯，k = 1 2 。 引理3 6 假设x i _ x ，既专b ，那么z 哼z ，d i 寸d ，其中z ，z 分别是子问 题( 3 1 ) 在孙x 处的解，d i ，d 分别是子问题( 3 2 ) 在( x k , b i ) ，( 工，b ) 处的解。 证明：引理的第一部分能够从线性规划的灵敏性分析中得到。下面我们来证 明引理的第二部分。 假设 d i ) 不收敛到d ，则存在一个子列 d ，) c d 。 收敛到d d ，由第一部 分我们知道z 厶一z ，对于子问题( 3 2 ) 在q ，b ) 处的任何可行解，存在子问题( 3 2 ) 在b ，b 0 处的一个可行解d ，使得d 。- - 9 , d ，因为d ，是子问题( 3 2 ) 在( b b j ) 处的 一个可行解，因此 g ；d ，+ i 1 口，t 口，d ，g ；d 册+ i 1 口。t 曰，d ， 令s 专，m 寸，可得到 g ( 7 d + 丢d 7 云d g ( o + 导d r 由 即d 是子问题( 3 2 ) 在b ) 处的一个解，这与子问题( 3 2 ) 在( x ，b ) 处的解是唯一的 矛盾。 引理3 7 假定盯。= 仃，k = l 2 ，b 。 是由算法产生的无穷序列，并且 x t ：k 茁 是一个收敛子列，那么对于所有的k r ，当k 斗时d t 一0 。 证明：用反证法，假定存在一个无穷子列 x k ：七茁c r ) 和一个正数使得 i i d t 0 r ，v k e r ，又由算法3 1 中的第4 步和假设3 1 ( i i ) 有 2 4 第3 章解不等式约束优化问题的一种稳定的s q p 方法 o c k ( x i ；d ) 一d ：b d i m 刀，v k 0 和d c0 p a n t o j a 和m a y n e ( 1 9 9 1 ) 中的命题3 2 1 1 5 相似我们能够证明存在一个正常 数，使得口i ，v k r 。，又由第5 步知 ，b t + 1 ) 一d ，( x i ) s 口以( x k ；d j ) 谊。卢m 一7 此式表明 ( o 。+ o - e d ，( 工t ) ) s 一口m 刀= 哪 k e e t e r 因此 熙o a ( 南) 一。如o ) 2 舰荟( o 一。一。一) ) 荟( o q 一西如助 s 一口膨，7 = 咱 h 一 这与假设3 1 矛盾，此引理得证。 定理3 1 假定仃t = c r , k = l 2 ， x i ) 是由算法3 1 产生的无穷序列，并且 b 。：_ | d 是一个收敛到x + 的子列，那么x 是一个