（应用数学专业论文）非线性约束条件下sqp算法的研究.pdf

摘要 本文用序列二次规划算法解决非线性约束最优化问题。 在第一章中，对具有一般约束的非线性规划构造出新的具有超线性收敛性的s o p 算法每次送代只需求解一个二次规划予问题并自动修币可行方向以避免m a r o t o s 效应， 在较弱的条件下保持了算法的全局收敛性。在第二章中针对非线性不等式约束最优化 问题，提出了一个新的可行序列等式约束二次规划算法。在每次迭代中，该算法只需 求解三个相圆规模旦仅含等式约束的二次翘划，减小了计算的工作量。在一定条件下 得到了算法的全局收敛性和超线性收敛性。在第三章中提出了一种将滤子方法应用线 搜索罚函数方法：如果罚函数在试探点不能充分地下降，就用滤子方法来放宽接受条 件。也就是说，如果约束违反度能够非单调地下降，那么也接受该试探点。这样使得 接受一个试探点的条件简单一些。该方法总结了滤予方法和价值函数方法各盘的优点， 并把它们有机地结合起来，提出一种线搜索的滤子方法，给出了其全局收敛性证明。 与以前的滤子方法不同，此方法不需要可行的恢复阶段。 关键词：约束最优化；s o p 算法；全局收敛性；滤子 a b s t r a c t t h i st h e s i ss o l v e sn o n l i n e a ro p t i m i z a t i o nu s i n gs q pm e t h o d i nt h ef i r s tc h a p t e r , i n t r o d u c e san e ws o pa l g o r i t h mf o rn o n l i n e a ro p t i m i z a t i o nw i t he q u a l i t ya n di n e q u a l i t y c o n s t r a i n t w en e e do n l ys o l v i n go n e q u a d r a t i cs u b p r o b l e ma te a c hi t e r a t i o na n dm o d i f yt h e f e a s i b l ed i r e c t i o na n da u t o m a t i c a l l yi no r d e rt oa v o i dt h em a r o t o se f f e c t t h em e t h o dc o u l d r e t a i nt h eg l o b a lc o n v e r g e n c eu n d e rt h ew e a kc o n d i t i o n i nt h es e c o n dc h a p t e r , af e a s i b l e s e q u e n t i a le q u a l i t yc o n s t r a i n e dq u a d r a t i cp r o g r a m m i n ga l g o r i t h mi sp r o p o s e dt os o l v et h e n o n l i n e a 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 n p e rs i n g l ei t e r a t i o n ，i ti s o n l yn e c e s s a r yt o s o l v et h r e e e q u a l i t y c o n s t r a i n e dq u a d r a t i cp r o g r a m m i n g sw i t ht h es a m es c a l e s ot h e c o m p u t a t i o n a le f f o r t i sr e d u c e d 。i nt h et h i r dc h a p t e r , i n t r o d u c e san e wa l g o r i t h mf o r n o n l i n e a ro p t i m i z a t i o nw h i c ha p p l i e sf i l t e rt e c h n i q u e st ot h et r a d i t i o n a ll i n es e a r c hp e n a l t y f u n c t i o nm e t h o d u n l i k ef o r m a lf i l t e rm e t h o d s ，d on o tn e e dr e s t o r a t i o np h a s eh e r e a n d u n d e rr e a s o n a b l ea s s u m p t i o n s ，g l o b a lc o n v e r g e n c ei sg i v e n k e y w o r d s ：n o n l i n e a ro p t i m i z a t i o n ；s q pm e t h o d ；g l o b a lc o n v e r g e n c e ； f i l t e r ； 学覆论文独翎性声明 学位论文独创性声明 本人声明，所呈交熊学位论文系本人在导师指导下独立完成的研究成果。文 中依法引用他人的成果，均己做出明确标注或得到许可。论文内容未包含法律意 义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论 文或成采。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 獭高 嗣期泖暮年囱7 墨 拳德论文采识产衩投属声臻 学位论文知识产权权属声明 零久在导师撵导下掰完成的学位论文及相关的职务撵晶，知识产权归属学 校。学校享有以任何方式发表、复制、公丌阅览、借阅以及申请专利等权利。本 人离校嚣发表或使用学位论文或与该论文直接相关豹学术论文或戒果对，署名单 盏镶然为青蓦大学。 本学位论文属于： 绦密 不僚密 年鬃塞羼送期予本声明。 ( 请在以上方框内打“4 ”) 日期。辟钢7 日 曩期：渺挣月7 基 引言 引言 最优化理论及方法是一个具有广泛应用背景的研究领域。它研究诸如从众多 的方案中选出最优方案等问题，常见的各种模型如线性规划，二次规划，非线性 规划，多目标规划等。最优化理论及方法已经在经济计划，工程设计，生产管理， 交通运输等领域得到了广泛的应用，吸引了很多学者的研究。 一般非线性约束的数学规划问题是： 其中x e r ”是决策变量，b ) 是目标函数，g ，b ) 是约束函数。 在求解上述问题的诸多算法中序y , j - 次规划( s o p ) 是最有效的一类方法之 一。由于它具有超线性收敛速度，对它的研究一直是非线性规划的一个热点，许 多学者对它进行了研究和改进。 s o p 方法的思想源于w i l s o n ( 1 9 6 3 ) ，他证明了当k ，“) 充分靠近k ，h ) 时 该算法收敛且具有二阶收敛速度。在1 9 7 6 年s p h a n 将拟牛顿法的思想引入 w i l s o n 的算法中给出了一个约束变尺度算法。1 9 7 7 年，他又进一步引入了效益 函数的概念，使用一类精确罚函数作为效益函数以确定步长。从而证明了算法的 全局收敛性。1 9 8 7 年p a n i e r 和t i t s 给出了s q p 可行下降算法。后来国内外诸 多学者对这个算法进行了改进，其中高自友、吴方、等人的改进颇有成效。九十 年代一些学者开展了序列方程组算法的研究。其主要思想是：将序列二次规划方 法中的一个或多个二次子规划用一个或多个具有相同系数矩阵的线性方程组代 替。 关于s o p 方法的一个重要的研究工作是其超线性收敛性的问题，早期 s p h a n 、p o w e l l 等都在较强的条件下( 二阶导数矩阵正定) 证明了超线性收 敛性。而具有广泛影响的工作属于b o g g s 、t o l l e 和w a n g 三人，他们从考虑等 式约束开始将解无约束问题的结果加以推广，在一些假定条件下得到了s q p 算法 的一个著名充要条件： ! 璁咝铲= 。 h m 峪。0 聆 乙 、，j 川肘 l h 仙协 = = ， ， ， o 0 = 、， r r 砖- i 厂g g 暑 六 m 青岛大学硕+ 学位论文 这个结果对s q p 算法极为重要，其后各种约束s o p 算法的超线性收敛性基本 上都是借助这个条件建立起来的，后来许多学者对此结果进行了改进，期望在减 弱假设条件下仍能得到这个充要条件。 自从w i l s o n ( 1 9 6 3 ) 关于序y , j - - 次规划( s q p ) 的工作问世以来，以及h a n ( 1 9 7 7 ) 和p o w e l l ( 1 9 7 8 ) 对这一工作成功改进以后，s q p 方法得到了广泛和深 入的研究。二次规划去构造非线性规划的求解算法的工作有很多新的进展。早期 的大多数s q p 算法有两个不足：一是为了获得搜索方向，在每一步迭代需要求解 多个二次规划子问题，计算量很大。二是算法终止时所得的点是不可行的。此后 有很多作者在理论和应用上对s q p 算法进行改进，使其逐步完善。 由于序n - 次规划法一般都具有良好的超线性收敛性，因而此类算法在非线 性规划求解中占有非常重要的位置。从实际数值效果来看，s q p 算法对于约束下 的最优化问题是非常有效的。但是由于s q p 类算法在实际运算上由于机器终止时 所得到的点一般都是不可行的。而实际与工程设计等实际问题相关的优化问题， 受客观环境的制约，往往要求问题的解是可行的。这是一般s q p 算法的严重的不 足之处。为了克服上述s q p 算法的不足之处，1 9 8 7 年p a n i e r 和t i t s 在 1 2 中 给出一个对序列二次规划方法的修正算法，从而可保证算法的迭代点总是在可行 域内进行。但 1 2 中仍存在以下两点不足：一是算法每步迭代需要求三个不同的 二次子规划，而且有时还要求一个“一阶”方向。此后又有很多作者在理论和应 用上对s q p 算法进行改进。 z h u 和z h a n g ( 见文献 1 1 ) 对具有不等式约束的非线性规划构造出新的超 线性收敛的s q p 算法每次迭代只需解一个二次规划子问题并自动修正可行方向 以避免m a r a t o s 效应，并在较弱条件下保持算法的整体收敛性。在第一章中，我 们将z h u 和z h a n g ( 见文献 1 1 ) 的工作，推广到更一般具有等式约束和具有不 等式约束的非线性规划。 在第二章中，对传统s q p 算法进行改进，提出了一个可行序列等式约束二次 规划算法。该算法每步迭代只需求解三个相同的仅含等式约束的二次规划子问题 以得搜索方向。从而减少了算法的计算工作量，而且在算法的迭代中较成功地解 决了因二次规划仅含等式约束而引起近似乘子不具有非负性的缺点。在适当的条 件下，证明该算法全局收敛，而且具有超线性收敛速度。 在第三章中，提出了一种将滤子方法应用线搜索罚函数方法：如果罚函数在 试探点不能充分地下降，就用滤子方法来放宽接受条件。也就是说，如果约束违 反度能够非单调地下降，那么也接受该试探点。这样使得接受一个试探点的条件 简单一些。该方法总结了滤子方法和价值函数方法各自的优点，并把它们有机地 结合起来，提出一种线搜索的滤子方法，给出了其全局收敛性证明。与文献 1 9 - 2 0 2 引言 不同的是，该方法不需要可性行恢复阶段，也不需要具有复杂参数的“开关条件”， 如果采用二阶校正步，可以证明其局部收敛性。 3 青岛人学硕士学位论文 第一章非线性约束条件下的s q p 可行方法 1 1 约束最优化问题 非线性约束的数学规划问题是指： r a i n1 ( x ) s j g ( z ) so ，j e i ； 1 2 ，m ( 1 1 ) g ，( x ) - - 0 ，je j - - m + 1 ，m + 2 ，1 ) 其中x e r “是决策变量，b ) 是目标函数，g j ( x ) 是约束函数。目标函数和 约束函数都是实值连续函数，且至少有一个是非线性的。约束g ( 工) s o ， j ，= 1 , 2 ，朋) 中的每一个称为不等式约束。约束g ( z ) = 0 ， j e j = m + l 优+ 2 ，_ ，1 ) 中的每一个称为等式约束。 如果目标函数是二次函数，约束函数为线性函数的非线性规划问题成为二次 规划问题。 由于二次规划具有较好的可解性，是最接近于线性规划的非线性规划，序列 二次规划算法就是通过求解二次规划来获得搜索方向。 定义1 1 满足所有约束条件的点称为问题( 1 1 ) 的可行点，所有可行点所组 成的集合称为可行域。我们记可行域为x = x e r ”ig ( x ) so ，j ，) ， 求解非线性规划问题( 1 1 ) 就是在可行域x 上寻求一点x 使得目标函数值 达到最小。 其他情况：求目标函数的最大值或约束函数大于零的情况，都可以通过取其 相反数化为上述一般形式。 下面我们来介绍非线性规划的k k t 点。 定义1 2 如果x x ，且存在a = ( 对，疋，硝) 尺”，使得 v f ( x ) + 艺一小) = 0 一0 ，一g ，( x ) = 0 ，j = 1 , 2 ，m 成立，则称石是问题( 1 1 ) 的k k t 点。相应的a = ( 一，巧，硝) 尺称为问题 ( 1 1 ) 的k k t 乘子。 4 第一章非线性约束条什下的s q p 可行方法 定义1 - 3 对于无约束优化问题，如果x 是稳定点，而且二阶充分条件 v 2 厂f 戈) 正定成立，只要t x ，d 。是一超线性收敛步，则对所有充分大的k ， 都有厂( 毛+ d k ) 厂( x k ) 。从而可知，在无约束情形超线性收敛步都是可以接受 的。但这一点在约束优化时却不成立，此现象称为m a r o t o s 效应。 由于序n - - 次规划法一般都具有良好的超线性收敛性，因而此类算法在非线 性规划求解中占有非常重要的位置。从实际数值效果来看，s o p 算法对于约束下 的最优化问题是非常有效的。但是由于s q p 类算法在实际运算上由于机器终止时 所得到的点一般都是不可行的。而实际与工程设计等实际问题相关的优化问题， 受客观环境的制约，往往要求问题的解是可行的。这是一般s q p 算法的严重的不 足之处。 为了克服上述s o p 算法的不足之处，1 9 8 7 年p a n i e r 和t i t s 在 1 2 中给出 一个对序n - 次规划方法的修正算法，从而可保证算法的迭代点总是在可行域内 进行。但 1 2 中仍存在以下两点不足：_ 是算法每步迭代需要求三个不同的二次 子规划，而且有时还要求一个“一阶 方向。此后又有很多作者在理论和应用上 对s q p 算法进行改进。z h u 和z h a n g ( 见文献 1 1 ) 对具有不等式约束的非线性 规划构造出新的超线性收敛的s o p 算法每次迭代只需解一个二次规划子问题并 自动修正可行方向以避免m a r a t o s 效应，并在较弱条件下保持算法的整体收敛 性。我们将g h u 和z h a n g ( 见文献 1 1 ) 的工作，推广到更一般具有等式约束和 具有不等式约束的非线性规划。 1 2 算法的描述 为方便起见，我们引入如f 记号 ，( 石) = ，ig ，( z ) = 0 ) j ( x ) - - i ( x ) u j 给出如下三个假设条件： a 1x 囝： a 2 厂和g ，是二次连续可微函数； a 3 对任意点x ，向一( v g ，( x ) ，j e i ( 石) ) 线性无关。 假设对于每个迭代点x e x 和对称矩阵曰，我们考虑如下的二次规划子问题 5 青岛人学硕士学位论文 m i nz + i d r b d 2 豇厂( 工) 2d 2 ，a ( 0 ，三) ，z ( 2 ，3 ) 戈= 1 步骤l 计算近似积极约束集。 1 1 令i = 0 ，q = o 1 2 d e t ( a l ，4 ，；) 苫气，l k = 厶4 = 4 ，= f ，转步骤2 ，否则进入 1 3 ， 其中，厶。= _ 川一。sg j ( 以) s0 ) ，4 ，= ( ，( 吒) ，t ，) 1 3 令f ：f + 1 ，；昙气h ，转入1 2 。 步骤2 计算搜索方向 2 1 计算 最- - ( a 。丁4 ) ，心= ( v y k , - j 厶) = 一b k v f ( x , ) 既蝣融) = f g _ 芝) 2 2 对以，求解如下带有扰动项的等式约束二次规划 1 0 蔓三童非线性规划一个可行序列等式约束二二次规划算法 m i n w ( 以) 丁d + 丢d r 日。d 豇p ；+ ，( 戈) r d = o ，_ 厶 设其解为稚，以为相应的k 灯乘子，如d ：；0 ，停 2 3 求解可行下降方向噍 2 3 1 求解如下等式约束二次规划 m i nv r ( ) rd + 委d r h 。d 趾g ，( 吒) + ，( z ) rd = 一j r ，je l k 设其k 一丁点对为“：，九) 。如町( 吒) r 钟 忙。l i ，令五= 0 。 步骤3 线搜索 计算 1 ，云1 ，三， 中满足以下各式 厂( 吒+ 耐。+ f 2 五) s ，( ) + 口f w ( ) r d k ， g j b k + m k + t 2 a 弋s o ，j i 的最大值t 。 ( 2 2 ) 青岛人学硕十学位论文 步骤4 令讫+ 。= x k + t k d 。+ t k 2 j d k ，通过拟牛顿公式来修正正定矩阵 风+ 1 ，k = 七+ 1 返回步骤1 。 2 2 全局收敛性 首先讨论算法的是定性，即算法的每步均口 执行。 a 3 算法产生的点列 ) 有界，巩一致正定，即存在62 口 o ，使得 v k ，y 尺“，有口y 2 s y 2 饥y by2 ，v k ，y e r “。 由于算法属于可行方向法，即保证故e x ，v k ，故易知二次规划总有解。事 实上，每次迭代中d ；0 都是( 2 2 ) 的可行点，故由a 3 可知凸二次规划总有解。 引理2 1 设( d ：，巩) 为二次规划2 3 的解，如果d ：= 0 ，贝, l jx k 为问题( 2 2 ) 的食k 灯点；如果d ：0 ，则步骤2 中的方向畋为问题( 2 1 ) 的一个可争下 降方向。 证明首先，根据k k t 点的定义，由问题( 2 2 ) 易知 v r 厂( 屯) + 月l d ：+ 4 以= 0 p ；+ v g ( 吒) rd ：；o ，_ 厶 如d ：= 0 ，则w ( 稚) + 4 以= o ，p ；= o ，_ 厶，从而由p k 的定义及k x ，v k 知 g ( 以) - - 0 ，v ；o ，_ 厶，且死；一( ，4 ) 以w ( ) - - - - v k ， 即v 厂( 吒) 彳以= o ，g ( 吒) = o ，石；苫o ，_ 厶 令石；0 ，je l 丘，易知上式表明为问题( 2 1 ) 的一个k t 点。 如果d ：一0 ，易知d ：一0 ，则 w ( 吒) 丁d s 一芋1 6 o , g ( 屯) d = 一i ” o , j i ( x k ) cl , 否则，如果以= 一气d ：，则由不是问题( 2 1 ) 的一个k k t 点知 w ( 吒) rd = 一乙w ( 以) rd ：s 一2 o 1 2 第二章非线性规划一个可行序列等式约束二次规划算法 ( ) rd s 一气2 o ，j e i ( x k ) c - - l k 即d 。为问题1 1 的一个可行下降方向。 引理2 2 对任何迭代指标k ，如果不是问题1 1 的一个k k t 点，则步骤 3 中的线搜索总可执行。 证明上述结论表明算法是良定的。由引理2 1 及算法的结构可知，如果算法有 限步终止于讫则是问题1 1 的一个斌r 点。下面设算法产生无穷点列 ) ， 由假设a 3 中 & ，h k 的有界性，集合丘c _ l 的有界性以及k 的定义，可假设存在 一无穷子集k ，使得 耽一工+ ，y 。呻y ，p 。呻，h 。一日，一暑l ，k k(23p p l)kk 一工，u 呻y ，t 呻，i 一爿， 暑 ， l j x k ) 的有界性可知 d ：，d 。，巩，九) 是有界的，故一定存在收敛子列。不妨 假设对无穷子集k 本身，有 。d ：呻d ；，d ：呻d ? ，d 呻d + ，i r k 一万，九呻a ， 足k( 2 4 ) 定理2 1 算法或者有限步终止于问题( 2 1 ) 的k k t 点_ ，或者产生无穷 点列 屯) ，使得其任一极限点x 必为问题( 2 1 ) 的k k t 点。 证明定理的前半部分由算法的构造，及引理1 知显然成立。下设算法产生 无穷点列 ) ，x + 为其任一给定聚点，不妨设2 3 和2 4 成立。首先证明 d ：呻o ，七k 。反设d ：d o 每o , k k 。易矢3 11 ( x + ) l 且d e t ( t 彳) 2 歹，其中 4 = ( w ，( x ) ，) ，故以下二次规划 m i nv 厂( z 。) r d + 昙d 丁日+ d 儿g ，( z 。) + ( 石) rd = 一d ov , 有解，_ r o t ? 0 为其唯一解。易知下式成立 w ( 工) 一d 0 , v g 小) 一d o ，尼k 1 3 青岛大学硕十学位论文 另外，由于 ，( 吒) ) 单调下降，故由 ) 。瓢一z 及厂的连续性有 厂( 吒) 呻，( z + ) ，k 呻筐 从而可知 o = l 。i 酬m ( f ( 吒“) 一厂( 吒) ) 5l 。i 瓢m a t 。w ( 以) r 以s 寻口t w ( x + ) r d + 0 ，使 g 如( x ) 一6 o ，l 厶。根据一x ，d ：_ o ，七一。及g 的连续性，知当七充 分大时 1 4 咖啪卜：憾t k 芸 嚣 tk 葛1k g+vgd v k 二。0 i 。( 吒)如( 吒) 2 ：s 一寺6 o ， 抽芑 矛盾。故厶暑t ( x ) 证咋- - , u 王。首先由的定义可知 呻一b + w ( z ) ；一( 彳4 ) 。1 彳v ，( z ) 另外，由于x 为问题( 2 1 ) 的一个k t 点，且厶置l 。，故 从而 ( 石) + 彳。h 王 收一“，。 = o ，即h i= 一( 彳4 ) 。1 a r v f ( x ) 证以呻比王。由2 3 式知w ( 以) + 日。d ：+ 4 矿= 0 ，从而 万f = 二( 衙4 ) 以鬈( w ( ) + h 。d ：) - 一( 彳4 ) 1a ：v 1 ( x ) = “王 证毕。 为使步长最终为1 ，进一步假设 a 4 对称矩阵序列 h 。) 满足 其中 p k ( 以一v 2 l ( x k ，九) ) 以卜。( i ) p k = l 一4 ( 4 ) q 鬈 v ：( 讫川删玳) + 荟对v 2 9 ) 引理2 4 当七充分大时，气暑1 。 证明只需证 ，( 讫+ d 。+ 五) s 厂( 吒) + 口w ( 吒) r d 。， g x k + d 。+ 五) s0 ， 对于2 5 式，当，硭，时，由g ( x 。) 0 ，d 。 0 ，d t 呻0 及 g ，( 石+ ) 0 ，d 。呻o ，d k 一0 连续知2 5 成立；当，。时 g 如+ 噍。以) = g j ( x i + d k ) + 地) r 五+ 。1 2 ) 1 5 ( 2 5 ) ( 2 6 ) 青岛人学硕+ 学位论文 从而可知 所以 = g ，( 噍+ 以) + w ，( ) r 玩+ d “以旷) 马g i i x 。了a k= - d1 7 - g ( 以+ 以) ，j e i g ，( 吒+ d k + 玩) = 一| | 以+ d ( 1 l 以1 1 3 ) ， 由于f ( 2 ，3 ) ，删yj e i ，2 6 式也成立。 对于2 5 式。记 有 s 垒厂( 吒+ d 。+ 五) 一厂( ) 一口w ( 晚) rd 。 = w ( 以) rd 。+ 五) + v 2 ，( 鼍) r 畋一a w ( 屯) r 以 w ( x ) * d , - - a 善o k d k - 荟对v g ) r 噍 ( 2 7 ) + 。 w ( 屯) r ( 以+ 五) 刊r h k d k - 荟对w ) r ( 以+ 五) + d ( i | w ) g ，( 吒) + ) r 以= 。( 1 2 ) ，j e i 另外，由2 7 知 g ，( 吒) + ，( 吒) r ( 以+ 五) + 2 d 善v 2 9 j ( x k ) d 。+ 。d 。1 1 2 ) = 。d 。i 门，j j r 即 一彰吲以) r ( ”五) 2 荟( 咖i 1d 侄g ( ) 卜 所以 + 。( 1 2 ) s ；a - 1 ) 衫巩以+ 1 v 。( ，批+ 荟( 1 一a ) 对g ) + d ( | 1 w ) 记p = e 一4 ( 4 ) 。1 彳，4 = ( ( _ ) ，j e i ) ，则以一以。 令 则 d 。= p d 。+ y ，y = 彳( 彳4 ) 。彳噍，g ( ) = ( g ( 吒) ，je i ) 1 6 第二章北线性规划个可行序列等式约束二次规划算法 y = 4 ( 彳4 ) 。1 ( 4 4 ) r d 。+ 4 ( 彳4 ) 州t 矾 ，。( i ) 一4 ( 彳4 ) 一g ( 以) + 。( 1 2 ) 易知恻l = o ( d 。眦0 y 0 = d ( 忙。i i ) + d ( 1 l g ( 黾) l i ) ，故 ss a ( 口一丢) i l d t i l 2 + 三( d j p + y r ) ( v 三( 吒，九) 一日t ) d t + 荟( 1 一a ) 矽g ) + d ( | l 哪) = 一口( 三一口) i i d t2 1 0 ( o d t1 1 2 ) + 荟( 1 一a ) a ，k g ，( 吒) + 。( 1 | g ( k ) o ) 。 即2 5 式成立。 综上知本命题成立。 根据引理2 4 可知有以下收敛定理。 定理2 2 算法是超线性收敛的，即i i + 。一一0 = d ( 0 吒一以1 1 ) 。 1 7 第三章一个改进的s q p 滤子算法 第三章一个改进的s q p 滤子算法 价值函数法是传统的解决非线性优化问题的方法。通常，这个价值函数由罚 函数来定义。该方法要求价值函数在每一个试探点都要单调下降，但是，这个条 件往往在每一步较难实现。最近，f l e t c h e r 和l e y f f e r 1 9 2 0 提出了一种叫做 滤子的新方法。在该方法中，如果目标函数或者约束违反度能在试探点非单调地 下降，那么就接受这个点为迭代点。事实上，这个方法目的是放宽接受条件，使 得试探点能够较容易被接受。特别值得注意的是，滤子算法的数值结果非常好， 所以研究人员将它与很多方法相结合。例如w a h c h t e r 和b i o g l e r 2 1 - 2 2 提出 的线搜索滤子方法；m u l b r i c h ，s u l b r i c h 和v i c e n t e 1 8 提出的内点滤子 法；f l e t c h e r 和l e y f f e r 2 3 提出的用于解决非光滑优化问题的捆集滤子法， 还有a u d e t 和d e n n i s 2 4 提出将滤子用于解决无需求导优化问题的模式搜索 法等。但上述有关滤子的文章都用到了一个可行性恢复阶段以减少约束违反度， 使得算法的运算量大大增加。 本章提出了一种将滤子方法应用线搜索罚函数方法：如果罚函数在试探点不 能充分地下降，就用滤子方法来放宽接受条件。也就是说，如果约束违反度能够 非单调地下降，那么也接受该试探点。这样使得接受一个试探点的条件简单一些。 该方法总结了滤子方法和价值函数方法各自的优点，并把它们有机地结合起来， 提出一种线搜索的滤子方法，给出了其全局收敛性证明。与文献 1 9 - 2 0 不同的 是，该方法不需要可性行恢复阶段，也不需要具有复杂参数的“开关条件”，如 果采用二阶校正步，可以证明其局部收敛性。 3 1 滤子 本文将使用的约束违反度和价值函数定义如= g ) 2 弘怫，毫：i l a x h g ) ) 中( x ) = 厂( z ) + p h ( x ) 定义3 1 数对 瓴) ，瓴) ) 控制另一个数对伪“) ，中“) ) 当且仅当 j l l 瓴) sh ( x t )且中( 杖) s “) 。 定义3 2 滤子是一列互不控制的数对。若数对q ( 吒) ，中( 五) ) 不被该滤子中 任何一个数对控制，则称( j i l 瓴) ，中瓴) ) 被该滤子接受。 1 8 青岛人学硕士学位论文 记五= - ( k ) l ( h ( x a m ( x 伪在当前滤子中) 一个试探点z “被此滤子接受 当且仅当h ( x ) o ，使得 ( ) 一( + a d ) 苫一a 叩( v 瓴) 噍一p h 魄) ) 对于a 。 口芑嘶和所有的k i 成立。 定理3 1 如果假设a 卜a 3 成立，则内循环有限步终止。 证明分两种情况。 ( a ) 一町瓴) 以 0 ，使得对所有充分大的七有i k 忙，。 由假设a ( 3 ) ，我们有 坻一a _ 九l s 百a d k1 2 s 警 由于d 。是子问题q p ( x ，h ) 的解 w g 。) + h 。d 。+ 4 九= 0 ，a 。= 陬g 。lj 。) v r 厂g 吒) r d 。= 一d ：h 。d 。一d r a 。九 青岛大学硕十学位论文 t d 二日。d 。一( a k 尸g k ) s d 二h 。d 。+ a k 忆h ( x 。) g d ；1 4 t d t + 九，l ( 黾) 5 一d l l 4 t d i 由算法的结构可知，吒不被加入到滤子中 矛盾，所以x 是一个k 研点。 若只有有限迭代步被加入到滤子中，则存在一个充分大的指标j 0 ，使得 当k 时，所有迭代不均满足巾( 吒+ a d 。) sm 魄) + a a ( v f ( x k ) d 。一p ( 吒) ) 由定理1 2 2 3o f 1 7 可知 故) 的任何聚点都是k 灯点。 2 1 结论 结论暑蜀 己 本文主要针对序列二次规划算法进行研究。序列二次规划算法的主要算法因 素有两个，其一是搜索方向的选取，其二是搜索步长的选取。本文分别从这两方 面进行研究，并且引入了滤子的概念，进一步优化了算法，在此基础上证明了算 法的全局收敛性。 第一章中，将z h u 和z h a n g ( 见文献 1 1 ) 3 2 作，推广到觅一般具有等式约 束和具有不等式约束的非线性规划。z h u 和z h a n g ( 见文献 11 对具有不等式 约束的非线性规划构造出薪的超线性收敛的s o p 算法每次迭代只需解一个二次 规划子问题并自动修征可行方向以避免m a r o t o s 效应，并在较弱条件下保持算法 的全局收敛性。 第二章中，针对非线性不等式约束问题，提高了一个新的可行序列等式约束 二次规划算法。在每次迭代中，该算法只需求解三个相同规模且仅含等式约束的 二次规划，减小了计算工作量。 第三章中，提出了一种线搜索罚函数方法，将滤子方法与其结合。与以前的 滤子方法不同，此方法不需要可行的谈复阶段。在一定条 牛下它可得到全溺收敛 性。 总之，本文用序列二次规划方法解决非线性约束优化问题，所得结论推广了 前人的成果。其中有些问题还需进一步讨论，如第一章和第三章中算法蠢朝算法 c 的超线性收敛性闻题，第二章中如何进一步降低该算法b 的计算量，是待研究 的工作。 参考文献 1m a s a of u k u s h i m a as u c c e s s i v ep r o g r a m m i n ga l g o r i t h mw i t hg l o b a la n d s u p e r l i n e a r l yc o n v e r g e n c ep r o p e r t i e s j m a t h e m a t i c a l p r o g r a m m i n g ，1 9 8 6 ，( 3 5 ) ：2 5 3 2 6 4 2p a n t e r ，t i t s as u p e r l i n e a r l yc o n v e r g e n tf e a s i b l em e t h o d f o rt h es o l u t i o no f 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 l a mjc o n t r o la n d o p t i m i z a t i o n ，1 9 8 7 ，2 5 ( 4 ) ；9 3 4 9 5 0 3j b j i a n p h t a u at w o s t e ps u p e r li n e a r l yc o n v e r g e n tf e a s i b l em e t h o df o r n o n li n e a rp r o g r a m m i n gp r o b l e m s c h e n g d uu n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y p r e s s 1 9 9 2 ，4 6 1 4 6 7 4m j d ，p o w e l l af a s ta l g o r i t h mf o rn o n li n e a r l yc o n s t r a i n e do p t i m i z a t i o n c a c u l a t i o n s j n u m e r i c a la n a l y s i sd u n d e e ，1 9 7 7 ，( 3 ) ：1 4 4 1 5 7 5z y g a o w uf as q pf e a s i b l e m e t h o df o rn o n l i n e a rc o n s t r a i n t s a c t am a t h e m a t i c a s i n c a ( s e ra ) 1 9 9 71 8 ( 4 ) ：5 7 9 5 9 0 6m js b a z a r a a ，j j g o o d e ，a na l g o r i t h mf o rs o l v i n g1i n e a r l yc o n s t r a i n tm i n i m a x p r o b l e m s ，e u r o p e a nj o p e r r e s i i ( 1 9 8 2 ) 1 5 8 1 6 6 7j b i r g e ，l q i ，z w e i ，av a r i a n to f t h et o p k i s v e i n o t tm e t h o df o rs o l v i n g 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 ，a p p l m a t h o p t i m 4 1 ( 2 0 0 0 ) 3 0 9 3 3 0 8j v b u r k e ，as e q u e n t i a lq u a d r a t i cp r o g r a m m i n gm e t h o df o rp o t e n t i a l l yi n f e a s i b l e m a t h e m a ti c a lp r o g r a m s ，j m a t h a n a l a p p l 1 3