（应用数学专业论文）非线性最优化问题的若干算法研究.pdf

山东科技大学硕士学位论文 摘要 摘要 本文共分三个部分。第一章简要叙述了s q p 算法与s s l e 算法的发展历史和概况， 介绍了近期发展的一些新成果，考察了这些算法全局收敛性与局部超线性收敛性的条件， 讨论了其中存在的问题及解决的方案；同时着重介绍了日前s q p 算法中比较流行的f i l t e r 方法，给出了一些相关的结论和近期的研究进展。第二二章中我们用线性方程组取代二次 规划子问题，每步通过求解两个或三个同系数的线性方程组来获得搜索方向，建立了一 个新的不可行f i l t e r - s s l e 线搜索算法，并在一定条件下证明了该算法具有全局和局部超 线性收敛性。由于在无严格互补松弛条件的情况下建立s s l e 算法的局部超线性收敛性 一卣是非线性约束优化领域的重要研究课题，因此在第三章中我们给出了一个新的不可 行f i l t e r - s s l e 算法。该算法在迭代过程中引入了有效集识别技术，通过该技术，取消了 难以验证的严格互补松弛条件，且在相对大大减弱的条件下便可精确识别k k t 点的有 效甚至强有效约束集。算法每步迭代只需求解一个或二个系数矩阵相同的线性方程组以 得到迭代方向，且方程组只包含工作集中的约束，其规模较原问题大大减小。同时，在 算法中我们采用了f i l t e r 技术，避免了罚函数法中由于问题不同而给罚函数选择带来的困 难，增强了算法的实用性。并且算法不再计算广义投影矩阵，使计算量大大减小。 关键词：非线性规划，相容性，严格互补松弛性，序列二次规划，序列线性方程组， 阶充分条件，全局收敛性，超线性收敛性，f i l t e r 山东科技大学硕士学位论文 a b s t r a c t a b s t r a c t t h ep a p e ri so r g a n i z e da sf o l l o w s ：i nt h ef i r s tc h a p t e r , w eb r i e f l yr e v i e wt h ed e v e l o p i n g h i s t o r yo fs q pm e t h o da n ds s l em e t h o d ，a n di n t r o d u c es o m en e wa c h i e v e m e n t si nt h i sf i e l d i nr e c e n ty e a r s t h e nt h eg l o b a la n dl o c a l l ys u p e r l i n e a rc o n v e r g e n tc o n d i t i o n sa r ec o n s i d e r e d a n dt h ep r o b l e m se x i s t e di nt h e s et y p e so fa l g o r i t h m sa r ep r e s e n t e d a tt h es a m et i m e ，w ea l s o d i s c u s ss o m es o l u t i o n so ft h e s ep r o b l e m s m o r e o v e r , w em a i n l yi n t r o d u c eaf i l t e rm e t h o d ， w h i c hi sm o s tw i d e l yu s e di ns q p t y p em e t h o da n dg i v es o m er e s u l t sa n dn e wa c h i e v e m e n t s i nr e c e n ty e a r s i nt h es e c o n dc h a p t e r , b yc o m b i n i n gt h ef i l t e rm e t h o da n da c t i v e s e ti d e n t i f i c a t i o n t e c h n i q u e ，an e wf i l t e r - s s l ea l g o r i t h mf 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 si s p r o p o s e d t h ea l g o r i t h mn e e d st os o l v eo n l yt w oo rt h r e es y s t e m so fl i n e a re q u a t i o n sw i t ht h e s a l t l ec o e f f i c i e n tm a t r i xa te a c hi t e r a t i o nt og e tt h es e a r c hd i r e c t i o na n di ti sp r o v e dt ob e g l o b a l l ya n ds u p e r l i n e a r l yc o n v e r g e n tu n d e rm i l dc o n d i t i o n s i nt h et h i r l d c h a p t e gw ep r o p o s ean e wi n f e a s i b l es s l ea l g o r i t h mf o rn n t h en e w a l g o r i t h mi sb a s e do nf i l t e rm e t h o da n da ne x t e n d e da c t i v es e ti d e n t i f i c a t i o nt e c h n i q u e a te a c h i t e r a t i o n ，t h em o s tt w ol i n e a re q u m i o n sw i t ht h es a m ec o e f f i c i e n tm a t r i xn e e dt ob es o l v e da n d w h e nt h ei t e r a t e sa r ec l o s et ot h es o l u t i o no n l yo n eo ft h e mi si n v o l v e d m o r e o v e r ，t h e e q u a t i o n si n v o l v eo n l yc o n s t r a i n t si nt h ew o r k i n gs e ta n dt h o s en o ti nt h ew o r k i n gs e ta r e t o t a l l yn e g l e c t e d ，w h i c hr e d u c e st h ep r o b l e ms i z eg r e a t l y ht h en e wa l g o r i t h m ，w ei n c o r p o r a t e t h ef i l t e rm e t h o dw h i c h ，c o m p a r e dw i t ht h ep e n a l t yf u n c t i o nm e t h o d ，a v o i d st h ed i f f i c u l t yi n c h o o s i n gt h ep e n a l t yp a r a m e t e rf o rd i f f e r e n tp r o b l e m sa n dm a k e st h en e wa l g o r i t h mm o r e a p p l i c a b l e i np a r t i c u l a r , i th a sb o t hg l o b a lc o n v e r g e n c ea n dl o c a ls u p e r l i n e a rc o n v e r g e n c e w i t hl e s sc o m p u t a t i o na n dw e a k e ra s s u m p t i o n s k e y w o r d s ：n o n l i n e a rp r o g r a m m i n g ，c o n s i s t e n c e ，s t r i c tc o m p l e m e n t a r i t y , s q p ，s s l e ， s e c o n d o r d e rs u f f i c i e n tc o n d i t i o n s ，g l o b a lc o n v e r g e n c e ，s u p e r l i n e a rc o n v e r g e n c e ，f i l t e r 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交 于其它任何学术机关作鉴定。 硕士生签名 日期 a f f i r m a t l o n 郑当莲 0 6 f e id e c l a r et h a tt h i sd i s s e r t a t i o n ，s u b m i t t e di nf u l f i l l m e n to ft h e r e q u i r e m e n t sf o r t h ea w a r do fm a s t e ro fs c i e n c ei ns h a n d o n gu 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 , i sw h o l l ym yo w nw o r ku n l e s sr e f e r e n c e do fa c k n o w l e d g e t h ed o c u m e n th a sn o t b e e ns u b m i t t e df o rq u a l i f i c a t i o na ta n yo t h e ra c a d e m i ci n s t i t u t e s i g n a t u r e ：郑雪莲 d a t e ：0 5 g 山东科技大学硕士学位论文 非线性最优化问题及其算法概述 1 非线性最优化问题及其算法概述 1 1 最优化问题的概述 1 1 1 最优化问题的概述 最优化是运筹学的一个分支，与其它分支不同，它更侧重于运筹学问题的数值求解。 因为工程设计、国民经济、管理科学中也要用到最优化的模型及求解方法，所以它又以 某种意义超出了运筹学的范畴。在科学技术、生产实践和日常生活中，人们经常遇到大 量的、各式各样的极小化或极大化问题，对于这些问题往往可队通过事物的各种量之间 的规律，描写为多个变量的函数在一定条件下的极值问题，我们称它为最优化问题或数 学规划问题( j ) 。其一般数学模型为： o , r l p ) r a i n ，( z ) s ，f c f ( x ) 茎0 ，i j = 1 ，2 ，州)( 1 1 ) c ix ) = 0 ，i 工= 伽+ 1 ，一，m + p 其中，工= ( x 1t ，) 1 r “，厂( z ) ，c i ( x ) ( i i u l ) 是关于变量工的函数，称集合 x = z r ”b ( x ) o ，i j ；c j o ) = o , i e 是问题( n l p ) 的可行域。如果z 鼻，则称z 是 问题( n l p ) 的可行解。如果对一一切z x ，都有f ( x ) i 厂( ，) ，则称工+ 是问题( n l p ) 的全 局最优解；如果存在z + 的某个邻域m ( z + ) = x ：忙一z f i o 是常数，| j | | 是向 鼍模，使得对一切x x n 虬( x + ) ，( z ) ，( f ) 成立，则x 为。儿p ) 的局部最优解。 若，= = g ，我们称问题( n l p ) 为无约束优化问题：否则，称( n l p ) 为约束优化问题。 若( x ) 与q ( x ) ( f 八j 三) 都是线性函数，我们称问题( n l p ) 为线性规划；反之，若f x ) 与o ( 工) ( i e i u l ) 中至少有一个非线性函数，就称( n l p ) 为非线性规划问题。 在本文中，我们主要讨论非线性规划问题。 1 1 2 非线性优化问题的一般算法概述 对于最优化模型( n l p ) ，通常采用迭代法求它的最优解。迭代方法的基本思想是： 山东科技大学硕士学位论义 非线性最优化问题及其算法概述 从个选定的初始点而出发，按照某一特定的迭代规则产生一个点列 _ ，使得当 气 是有穷点列时，其最后一个点是问题( n l p ) 的最优解；当 以 是无穷点列时，它有极限 点，并且其任一极限点是( l p ) 的最优解。个算法是否收敛通常和初始点x o 的选取有 关，如果只是当初始点充分接近，时，算法产生的序列 以) 才收敛到x + ，则称算法是局 部收敛的；如果对任何初始点x o ，算法产生的序列 t 都收敛到x 。，则称算法是全局收 敛的。 评价一个算法的好坏，最重要的衡量标准之一是它的收敛速度。假设序列 _ 收敛 到x + ，如果存在p ( 0 , 1 】，使 l i m 则称 ) 的收敛速度是线性的；如果户 l i m 。 = d = 0 则称 _ 的收敛速度是超线性的；如果存在一个自然数p ，使得 燃黼- oko 则称 t ) 的收敛速度是p 步，阶超线性的。 1 1 3 一般约束优化问题的最优性条件 这里我们主要给出一般带有等式和不等式约束优化问题的最优性条件。 定理1 1 在问题( n l p ) 中，设x + 是其局部最优解，厂o ) ，q ( x ) ( f 八j l ) 在x 处均 t ，j 微；且向量组 v q ( 工+ ) ，f j ( 工+ ) 线性无关，其中( x ) = f lc l ( 爿+ ) = o ，fe 八一 ，则存 裨：不全为零的常数五( i e 八j ) ，使得 v ，l ( x ，a + 1 = 0 ， c 】( z ) o ，f e ，c ix + ) = o ，f 工， c f ( 工) = o ，( f ，) ，丑o ，( f ) 卅可棚卅习k f 却k 雨 l “东科技大学硕十学位论文非线性最优化问题及其算法溉述 其中( 丘丑) ：厂( 。) 十羔五c f ( 。) 。 定理1 1 中j 所满足的条件称为k k t 条件。 定理1 2 ( 二阶必要条件) 在问题( n l p ) 中，设，( z ) ，c i ( x ) ( i e 八j ) 是二次连续可微函数，x + 是( n l p ) 的个局 部最优解，若向量组 v ( x + ) ，i ，( 工) 线性无关，则存在不全为零的常数一( iei u l ) ， 其中o ( f e ，) ，使得k k t 条件成立；且矩阵v ：( 工，a ) 在子空间 y v c ，( x ) 7 y = o l ，( x ) 上是正半定的。 定理1 3 ( 二阶充分条件) 在问题( n l p ) 中，设厂( x ) ，c i ( x ) ( i 八j ) 是二次连续可微函数，对可行点z + 而言， 若存在耳( i e l u l ) ，使得( j c ，兄+ ) ( n l p ) 猷jk k t 点；并且7 。2 ( * ，a + ) 在予空间 y j v q ( 工) 7 y = 0 ，f e ，( z + ) ) 上正定，则工4 是严格局部极小点。 对照二阶充分条件，我们可以给出对应的强二阶充分条件。 定理1 4 ( 强二阶充分条件) 在问题( n l p ) 中，设厂( x ) ，c ( x ) ( i 八儿) 是二次连续可微函数，对可行点x 而言， 若存在霄( f i u l ) ，使得( z + ，丑+ ) ( n l p ) i j 勺k k t 点；并且v ：c ( x + ，a + ) 在子空间 y v c l ( x + r y = o , i e - ( x 。) u 工) 匕正定，这里，+ ( x + ) = i i o ( x + ) ，再 。) ， ，n ( + ) = i e ic ( x + ) = o ，则工+ 是严格局部极小点。 定义1 1 ( m f c q ) ：称可行点x x 满足m f c q ，如果等式约束梯度 v q ) ，i 上 线 性无关，且存在一个方向d r “，使得：v q ( z ) 7 d 0 ，v i 1 0 ( x ) ；v q ( z ) 7 d = 0 ，v z 。 定义1 2 ( s m f c q ) ：称可行点石x 满足s m f c q ，如果向量组 vc f ( 工) ，i ，+ ( z ) u 工j 线性无关，且存在向量d r ”，使得：v q ( 工) 2d 0 ，v i ，一( j ) ；v c , ( 上) 2d = 0 ，v i ，+ ( ) ； v o ( 上) d = 0 ，v i 。这里，_ ( 工) = ，o ( z ) ，+ ( x ) 。 山东科技太学硕士学位论文 非线牲最优化拇艟置其算往概进 1 2s q p 算法 拟牛顿算法足求解无约束优化问题最有效的算法之，序列二次规划算法 ( s 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 g ，简称s q p ) 是烽拟牛顿算法应用到求解约束优化问题 的推广与发展，由于它保持了拟牛顿算法的超线性收敛速度因而成为求解约束优化的重 要算法类。序列二次规划算法最早甫w i l s o n 于1 9 6 3 年在其博士论文中提出，他证明j 在最优解的邻域内，算法具有二次收敛速度。但是w i l s o n 提出的算法还存在许多问题， 例如由于算法还不大实用，每步中的二次子规划的解可能不存在，二次子规划中的 v 2 ( ，五) 不一定正定等。2 0 世纪7 0 年代，在h a r tsp ，p o w e l l mj d 等大批学者的研 究与改进下，序列二次规划算法获得了新的生命力。他们在w i l s o n 算法的基础上，用一 个对称正定矩阵耳代替v 2 上嘛，丸) ，并引入效益函数进行线性搜索求步长口。，从而建立 了个完整、实用、快速有效的序列二次规划方法，这就是著名的w i l s o n h a n - p o w e l l 方法。下面以h a n 的算法为例说明一下般的s q p 算法的基本步骤： 算法1 ，1 步0 给定初始点，选取初始对称正定矩阵玩，令k = 0 ； 步1 求解( q p ) 得( 癣， ) ， 罂毋w ( ) r d + d r b d ， s l ，v c i ( x 。厂d + c i ( x k ) - o , l ， v q ( 气) 7 d + 0 i ( 也) o ，f 若d 。= 0 ，则停止； 步2 求步长“【o 翻，满足 ( + f k d a ) r a i n ( 心+ 噱) + 毛 其r t 一“) 是一精确罚函数，即 m m 十p ) = ，( ，) + 丑m “( o ，c f ( z ) ) + 丑k ( x ) p 1+ l m _ + p b ) = 厂( x ) + 丑m a x ( o ，c f ( z ) ) + 丑k ( z ) 1l 4 山东科技太学硕士学位论文 e 线性最优化问题及其算法概述 “ 为一非负数列且满足毛 o 为常数) ； 则算法全局收敛。 关于收敛速度问题，b o g g s ，t o l l e 和w a n g 3 3 获得- t 较好的结果。假设 收敛于z h + = + 喀，v 矗( ，) = ( vc l ( j ) ，v + ，( x ) ) 为列满秩的矩阵，及二阶充分条件成 立。令b 是从月“到子空间，( ) = s p v q ( _ ) = o ，扛+ l ，m + p 上的投影矩阵，则 在些假定条件下，得到了算法超线性收敛的个著名的充要条件是： 熙咝掣：。 z ， 我们知道要得到超线性收敛速度，关键之是：当k 充分大以后要有 + ，= + 破， 即步长为1 。但是，m a r a t o s 【3 2 证实，即使v ：( j + ，五+ ) 正定，而且x k 充分靠近z + ，当使 用雌搜索，也有可能r 。 。 步0 选取初始点x 0 盖，和初始正定阵h 。足，0 1 1 0 ，使得 列v y e r “，0 2 v i l 2s y r h 。y _ c r 。l l y l l 2 等条件f 可得下面定理： 定理1 , 6 算法或者有限步终j 七于【n l p ) 的一个k k t 点，或者产生一个无穷点列， 其任一聚点都是( n l p ) 的k k t 点。 另外，若再假定函数，和q ( i 八j ) 至少为二次连续可微，严格互补松弛条件及二 阶充分条件成立，以及h 对称正定且满足： 东科技大学硕十学位论文非线性最优化问题及其算法概述 l i m + o 其中，只= i - q ( r ) 。1 群，r 。= ( v c ；( t ) ，i ，( x + ) u ) ，( 葺五) = 厂( z ) + a i c i ( x ) ， i = 1 则算法具有步超线性收敛性。 目前的大多数s q p 算法或s s l e 算法为了克服m a r a i o s 效应，获得超线性收敛性， 常常需要对问题作一个很难验证的严格互补性假设。b o r m a n s 2 2 和l a u n a y ，f a c c h i n e i 1 8 先后研究了无严格互补松弛条件的超线性收敛的s q p 算法。那么对于s s l e 算法能不能 也去掉这个苛刻的条件呢? f a c c h i n e i 和l u c i d i 1 7 ，简金宝 5 7 ，高自友【5 2 】等在无严格 互补松弛条件f ，分别研究了不等式约束优化和一般约束优化的序列线性方程组方法， 其结果只具有局部收敛性。简金宝【5 6 】把解线性方程组与计算一次广义投影相结合，给 出了一种混合型算法。该算法采用以目标函数为效益函数的阿米久型线搜索计算步长， 且当迭代次数k 充分大以后，直接用拟牛顿法产生步长1 ，其中并不要求l a g r a n g e 函数 的近似海色矩阵正定，在无严格互补松弛假设的较弱条件下，算法具有全局收敛性及超 线性收敛性。探讨新型的线性搜索策略，对此问题作进一步的研究是必要的。 1 4f i l t e r 算法 1 4 1 算法及定义 众所周知，s q p 算法是求解非线性规划问题的最行之有效的算法之一。其基本原理 就是将非线性规划问题转化为二次规划问题，通过求解二次规划子问题得到迭代方向， 然后采用精确罚函数进行线性搜索，得到步长，再进行下一步迭代。这样，非线性规划 问题的求解就转化为一系列二次规划子问题的求解。大多数s q p 方法中的线性搜索均采 用精确罚函数方法，这种方法的优点在于具有全局收敛性在最优点附近有较快的收敛 速度。但是在应用罚函数时，却有许多的困难。例如，采用罚函数会增加目标函数的复 杂性，特别是一些常用的精确罚函数往往是不可微的，因此必须同时使用别的方法( 如 w a t c h d o g 技术) 。另一个问题是需要确定罚函数中的参数，在选择罚参数时通常有一个极 限值，选择的参数太小将会导致获得一个不可行点，甚至导致罚函数无限增长；选择的 参数太大则会抑制目标函数的作用，导致收敛缓慢。适当调节罚参数的大小可以起到一 一 些要翌堡奎兰竺主芏堡丝三 斐垡生壁垡些塑坚墨基塞苎竖堕 定的作用，但是仍会出现一些问题。最近，z o p p k e d o n a l d s o n 4 8 提出了一种不使用罚函 数的线搜索s q p 算法，数值实验结果验证了算法的优越性。这些算法和结果发表后，g i 起r 广泛的兴趣。1 9 9 7 年，r f l e t c h e r 和s l e y f f 等【3 5 提出了用f i l t e r 方法代替传统的罚 函数法，建立了一个新的s q p 信赖域算法并且数值实验也验证了其优越性，现对其算法 简述如卜。 考虑不等式约束优化问题： 髀纂州， s ， 其中，= 1 ，埘 且，g ) 和c f ( x ) 均是二阶连续可微的实值函数。 l 亨歹l j x 由x “= x + d 得到，搜索方向由如下一个q p 子问题来计算： 卿p 土d 7 矿( d + d r g ( ) 一e “2 虬v q ( x ( 砷) d + c j ( - 0 ，ie ， 。p 其中g ”= g ( x 1 ) = v ( x ) ，三( z ，a ) = 厂( z ) 十丑o ( x ) ，是( p ) 的拉格郎日函数， c ( r ) = ( c l ( z ) ，气( 工) ) 1 ，w = v 2 l ( x ，丑) 。 非线性规划问题的求解通常需要满足两个要求：一是求目标函数的极小值，二是使 迭代点列收敛到原问题的可行域内。这两个要求可以表述成如下形式： f 雪，( x ) ， l 卿6 ( c ( z ) ) 这早 ( c ( x ) ) = p o ) i 。= c j ( x ) ，( 工) = m a x ( o ，q ( x ) ) 。这里用范数是为了方便计算， 实阿“i 也可以应用其它的范数。当x = 工时，分别记，( x ) 和 ( c ( j ) ) 为厂“，h 。 定义1 3 ( 支配) 如果迭代点( ”，厂) 满足 ” 且厂厂“，则称点( “，厂) 如喃( 班f 。) 。 定义1 4 ( f i l t e r ) 如果一个点列 ( “，o ) 中任何一点都不能被这个点列中的其它 点所支配，则称点列 ( ”，聊) 组成一b f i l t e r 。 东科技大学硕士学位论文非线性最优化问题及j 算法橇述 记f 扯= 卜k ，( ，f u ) ) 是当前f i h e r 中的元素) 。称“点被础e r 接受”，如果它 所对应的点对( “，) 不被f i l t e r 中的任何点对所支配即对所有的_ ，f “，或者 ( ( 7 ) 或者厂】 厂( 。) ；我们也称“f i l t e r 中包含一个点x ”，如果它所对应的点对 ( ( c 0 ) ) ，g ) ) 进入f i l t e r ，且f i l t e r 中被其支配的其它点对均被移除。在s q p 信赖域方法 中我们就用这个f l t e r 代替线性搜索，来决定步长。 其迭代的基本步骤如下： 算法1 3 步0 给定初始点x ( “，参数p ，令k = 0 ； 步1 若q p 子问题不相容，则进入可行修正步，得到一个新的迭代点x ( “1 ) 使其既能 够被f i l t e r 接受又使q p 子问题相容；否则，转步2 。 步2 求解q p 子问题得搜索方向d ( “，令z m ) = 一) + d i “，若x ) 能够被f i l t e r 接受， 则f i l t e r 中包含该点且f i l t e r 中被该点支配的其它点均被移除，同时增大p ，转步1 ；否 m 0 拒绝该点，令“) ：一“，同时减小p ，转步1 。 注在q p 子问题中，约束条件有时不相容，或者当迭代点连续不能被f i l t e r 接受时，算 法不能实现。针对上述问题，许多学者给出了一些改进办法，这里我们介绍两种主要方 法来避免这些情况的发生，使得到的新迭代点既能够被f i l t e r 接受，又能够使q p 予问题 相容。 1 二阶修正步( s o c ) ： 当x ( “1 ) 不能被f i t l e r 接收时，文献 2 0 引入了个二阶修正步，即求解一个如下形式 的f 问题q p l ， ( q p l ) r a d ；i 月n 。1 2d 7 缈( t ) d + d g ( i ) ， 5 j v c i ( 一) d + c i 似“，) 一vc f ( x 旺) 7 d ” - 0 f ， l l a l l 。 o ，j ，可通过下面的l s l 来确定： r a i n z 7 d 把j s t 0 p d + 4 o ，f ，1 1 1 4 。p 这里n = v c ；( z 。) 。 1 4 2 近期的研究进展 f l e t c h e r 和l e y f f 的文章 3 5 】发表后，引起了人们的广泛兴趣，1 9 9 9 年，f l e t c h e r 和 1 2 生查型苎奎兰堡主兰竺丝苎 ! ! 堡壁墨垡些鲤里墨墨墨堡塑鉴 l e y 研37 在文献【3 5 提出的方法基础上加以推广和改进，得到了求解既含等式又含彳i 等 式约束优化问题的f i l t e r - s q p 算法。 对该算法，文献 3 7 做了如下假设： a 1 由算法产生的序列 x ( k j 和 x ( k ) + d ( j 包含在紧致凸集s 中。 a 2 厂0 ) 和c i g ) 是s 上的二阶连续可微函数，i = 1 ，2 ，m 。 a 3 哦是有界的。 定理1 7 在上述假设条件下，算法产生的点列必满足下列情况之一： ( a ) 对某一个p p 。，由可行修正步得到的迭代点不能既被f i l t e r 接受又使得q p 子n 日题相容o ( b ) 算法能够有限步终止于一个k k t 点； ( c 1 任意聚点都是可行点并且要么是一个k k t 点，要么不满足m f c q 。 随后，s u l b r i c h 4 3 在f i l t e r 方法中用拉格朗日函数代替了目标函数，修正了上述算 法，同样也获得了较好的结果。最近，a h d r e a sw a c h t e r 和t b i e g l e r 在文献【3 5 的基础上， 将f i l t e r 方法运用到有效集s q p 和障碍内点法中，在较弱的假设条件下，保证由算法产 生的迭代点序列的每一个聚点都是可行点，并且至少存在一个聚点是稳定点。 在定条件下证明了算法具有快速的收敛速度。 1 5 论文研究内容及各章主要安排 论文吾革安排如f ： 第一章简要叙述s q p 算法与s s l e 算法的发展历史和概况，介绍近期发展的一些新 成果，考察了这些算法全局收敛性与局部超线性收敛性的条件，讨论其中存在的问题及 解决的方案；并且还着重介绍目前s q p 算法中比较流行的f i l t e r 方法，避免了原有精确 罚函数法中不易选择罚参量的困难，同时介绍了一些相关的结论和近期的研究进展：指 出水迁主要工作。 第二章在文献【5 0 的基础上，用线性方程组取代二次规划予问题，每步通过求解两个 或蔓个系数矩阵相同的线性方程组来获得搜索方向，同时结合f i l t e r 技术，建立了一个求 解不等式约束优化问题的不可行f i l t e r - s s l e 算法。在一定条件下，新算法不仅有局部超 线性收敛性，也有全局收敛性。 l 些查型垫奎兰竺主兰竺堕苎 斐些丝墨垡些塑璧墨苎竺茔塑堕 第三章中，考虑带有不等式和等式的非线性约束优化问题唧) ，参照文献f 1 5 1 ，给 出了一个新的不可行f i l t e r s s l e 算法，该算法在迭代过程中引入k k t 点有效集识别技 术。通过该技术，取消了难以验证的严格互补松弛条件，在相对大大减弱的条件下可精 确识别k k t 点的有效甚至强有效约束集。算法每步迭代只需求解一个或二个系数矩阵 相同的线性方程组以得到迭代方向，且方程组只包含工作集中的约束，其规模较原问题 大大减小。同时，在算法中我们采用了f i l t e r 技术，避免了罚函数法中由于问题不同而给 罚参数选择带来的困难，增强了算法的实用性。并且该算法不再计算广义投影，计算量 小，保持了文献 5 6 1 中算法的良好性质。 4 山东科技入学硕士学位论文 不等式约束优化问题的线搜索f i h e r - s s l e 算法 2 不等式约束优化问题的线搜索f i l t e r - s s l e 算法 2 1 引言 本章考虑形如第一章中( 1 3 ) 所描述的不等式约束优化问题( p ) 。 对t i l t e r - s q p 信赖域算法而言，如果新的迭代点不被f i l t e r 接受，就需要相应减小信 赖域的半径。而如果当前迭代点x k 不是可行点，则减小信赖域半径就会最终导致二次规 划子问题的不可行性，即二次规划子问题的可行域为空。c h o o n g m i n g c h i n 【7 , 8 1 ( 2 0 0 2 年) 将f i l t e r 技术与s q p 方法相结合，给出了一个全局收敛和超线性收敛的线搜索f i l t e r - s q p 算法，简述如下： 序列 _ 由耳+ = + c t d , ( a ( o , q ) 得到，而破由下面的( q p ) 子问题计算： ( q p ) 皿m i n v f ( 雄) r d + j 1 矿嗽 ls 工v c l ( x k ) 1d + ( x k ) 0 ，i ， 若产生的新的迭代点不能被f i l t e r 接受，为了避免产生m a r a t o s 效应，则用一个s o c 步来修正搜索方向d k ： m i nv 厂( 以) 7 ( o + 吨) + 寺( 孑+ 畋) ( i + 吐) d e r ” s t ，v c ，( - ) 7 d + c ，( x 。+ d 。) = 一l l d 。i l ”，i 五( z 。) v 勺( _ ) 7 孑+ c j ( 以+ 以) 一1 1 以犷，i ，e 4 ( 砟) j ( ) 这氅v ( 2 ，3 ) ，j ( 以) = f 4 ( _ ) ：属 0 ，a ( 墨) = i ：v q ( ) 7d 。+ c 。( ) 一o ，这时序 列 而 由x k 。= 鼍+ 口矾+ a 2 玩( a ( o ，l 】) 得到。 文献【8 1 彳导到下面主要结论： 定理2 1 1 假设s m f c q 及二阶充分条件成立，则算法具有二步超线性收敛性。 值得注意的是，上述定理并没有假设严格互补松弛条件成立。 但是利用二次规划予问题来求迭代方向存在两个重要问题，一是二次规划的求解通 坐查型塾查兰堡主堂堡堡苎 至竺垫竺塞垡些塑望塑些望耋旦! 竺! ! ! ! 塞堡 常采用迭代法，计算工作量较大，并且很难利用系数矩阵的稀疏性，对称性等良好性质； ：二是这些二次规划子问题可能无解，虽然可以通过一系列措施来进行调整，但势必会增 加算法的复杂性和计算工作量。与s q p 方法相比，序列线性方程组算法( s s l e ) 具有 计算韪小，稳定性好等特点，并且克服了s q p 方法所固有的相容性问题，较好的解决了 s q p 方法的上述问题。这个算法最初是存1 9 9 4 年由g a o 等 5 1 在文献u 4 的基础上提出 的。自此以后，在这一方面取得了许多成果。1 9 9 7 年，g a o 等【4 7 】利用一个罚函数把这 个算法推广到求解一般约束优化问题上。2 0 0 0 年，在文献 1 4 ，4 7 的基础上，q i 等【3 4 利 用k k t 条件的非光滑方程又给出了一个新型的q p f l e e 算法。但是，所有以上这些算法 都要求初始点是可行，这对于非线性约束( n l p ) i h 题是很费时的。为此，1 9 9 7 年，g a o 等5 0 通过引入g 有效集技术并采用一个特殊形式的效益函数首次给出了一个初始点任 意的s s l e 算法，且在一定条件下，算法具有良好的全局和局部超线性收敛性质。基于 此，并考虑到采用罚函数时遇到的困难，本章中把文献【5 0 中的算法与f i l t e r 技术相结合， 给出了一个初始点任意的线搜索f i l t e p s s l e 算法。从而既克服了s q p 算法所固有的缺陷， 同时又避免了采用罚函数时所遇到的困难。在一定条件下，新算法不仅具有局部超线性 收敛性，而且也是全局收敛的。 2 2 算法及定义 对于任意的j r “，定义其有效约束集如f ： ，( z ) = i e 小( z ) = 甲( 工) 其中甲：r ”一r 定义为：甲( x ) = m a x q ( x ) ，i e l ；0 。i 已c ( x ) = ( c ( x ) ，靠( z ) ) 。 本章始终假设下列条件成立： a 1 ，g ) 和c i b ) ，f 均为二阶连续可微函数。 a 2 对任意的x r ”，向量组 v q ( z ) ，i e ，( x ) ) 是线性无关的。 非线性规划问题( p ) 的求解通常需要满足两个要求：一是求目标函数的极小值，二：是 使迭代点列收敛到原问题的可行域内。为了同时满足这两个要求，我们结合f i l t e r 的概念 将问题( p ) 转化为如下形式： 山乐科技大学硕士学位论文 不等式约束优化问题的线搜索f i l t e r s s l e 算法 m m i n 。，( 工) m m i n 。 ( c ( 工) ) 这哩， ( c ( z ) ) = 肛+ ( 鼻) 其中c + ( z ) = ( c ( 工) ，c ：( x ) ) 7 ，百( x ) = m a x ( o ，q ( x ) ) ，i ，。记 f ”= j 墨 ，( ( c ( 。) ) ，厂( x ，) ) 为当前f i l t e r 中的元素 。 类似于文献 7 ，我们对f i l t e r 定义条件做了略微的修正，若迭代点x 被f i l t e r 接受， 则对所有的j ，满足 ( c ( x ) ) s ( 卜口叩) (