（应用数学专业论文）非线性优化中的滤子方法及非单调方法.pdf

中文摘要 捅要 解非线性规划问题的滤子方法最早是由f l e t c h e r 和l e y f f e r 【3 2 】提出的。由 于其良好的数值例子而受到广泛的重视。以往在处理带约束的优化问题时，都 要用到拉格朗日函数或罚函数。但是，有时会产生一些新问题，如罚参数的处 理。罚参数过大或过小都会引起不好的效果。滤子方法是一种无罚参数的方 法。自从关于滤子的第一篇文章发表以来，已有很多人在做这方面的工作，如 f l e t c h e r ，d e n n i s ，t o i n t ，l e y f f e r 等。关于解非线性规划问题的滤子方法的软件 已经出现，并且该软件和其它软件相比，在解有些问题上很有优势。滤子方 法现在已经和信赖域方法【2 8 】，序列二次规划( s q p ) 方法【3 l 】，序列线性规划 ( s l p ) 方法【1 6 ，2 9 ，内点法【5 ，9 0 ，9 5 ，模式搜索法【2 】结合起来，并且还用来解 决其它类型的问题，如在【3 0 】中，滤子法被用来解非光滑优化问题。 滤子方法借用了多目标优化的思想，将约束优化问题化为双目标优化问 题，即使得目标函数和约束违反度都要减小，但是可以不同时减小，其本质是 一种非单调的方法，有利于得到全局最优点。本学位论文对滤子方法作了深入 研究，通过对其本质的研究，对其进行改进，并提出新的具有良好性质的算 法。 考虑到滤子方法本质上是一种非单调的方法，所以可以设计一种新的非单 调的方法来解约束优化问题。在第二章，提出了一种新的非单调的算法。该算 法既不需用罚函数或拉格朗日函数来检验步长的可接受性，也不需要用到滤子 和可行性恢复阶段。此外，同其它滤子方法相比，本章提出的算法在接受步长 方面，具有较强的灵活性。该算法具有全局收敛性和局部超线性收敛性。晟 后，给出的数值结果表明该算法是有效的。 在第三章，提出了一种求解最大最小值问题的非单调s q p 算法，也是第二 章中提出的算法在实际问题中的应用。该算法具有全局收敛性和局部超线性收 敛性。最后，给出的数值结果表明该算法在解决实际问题中是非常有效的。 目前所提出的滤子方法基本上都是通过s q p 方法得到搜索方向的。 在s q p 方法中，一般用一阶泰勒展开得到约束条件的近似逼近。这对于那 些几乎线性( n l ) 的约束条件来说不失为个好方法，但对于那些高度非线 性( h n ) 的约束条件来说，仅用一阶逼近，就不太合适了。从数值计算的角 度来说，h n 约束条件在每一个迭代点的的约束违反度会有较大的变化幅度， 一t i i 中文摘要 而对于n l 约束条件来说，这种情况一般不会发生。所以，对于h n 约束条件 和n l 约束条件需区别对待。事实卜有许多实际问题同时有h n 和n l 约束条件。 在二维滤子s q p 方法中，尽管将目标函数和约束违反度分别考虑，但是它们将 所有的约束条件放在一起考虑且只有一个约束违反度。未对具有各自不同性质 的h n 和n l 约束条件充分考虑。在第四章，提出了一种三维滤子信赖域算法。 考虑至i j h n 和n l 约束条件各自的性态，将约束条件分为h n 和n l 约束条件两个部 分，将它们相应的约束违反度同时晟小化作为两个日标。这样就得到一个三维 滤子，包括三个分量，即目标函数值、h n 和n l 约束违反度。这样，与二维滤 子丰目比，一个试探点被接受的条件将大大放松。该算法具有全局收敛性和局部 超线性收敛性。最后，给出的数值结果表明该算法是有效的。 另外，还注意l i j s q p 方法本身也有两个不可忽视的缺点，即较大的计算量 和子问题的不相容性。而近年来发展起来的序列线性方程组( s s l e ) 方法可 以避免上述s q p 方法中的不足。s s l e 方法本质上就是用 个或多个具有相蚓 系数矩阵的线性方程组来取代s q p 方法中的一个或多个q p 子问题。在第五章 中，提出了一种新的s s l e 算法。该算法无需解q p 子问题，只需解三个具有相 同系数矩阵的线性方程组。从而，于【3 1 相比，计算量大大减少。通过利用滤 子的技巧，无需罚函数，避免了罚参数的选取。对初始点不作特殊要求，可以 是任意的点。算法中还使用了x 有效集的技巧。只有在x 一有效集中的不等式 约束条件和等式约束条件才被考虑，可以减少算法的讨算量。另外，该算法还 对 3 9 ，4 0 】算法进行改进，克服了在某些特殊情况下其算法不具有下降性的不 足。由此可以看出，本章算法既保持了【3 1 和 3 9 ，4 0 i 中算法好的性质，也具有 其独自的特点。该算法具有全局收敛性和局部超线性收敛性。最后，给出的数 值结果表明该算法是有效的。 关键词：非线性规划，非单调，滤子，多目标规划 英文摘要 a b s t r a c t t h ef i l t e rm e t h o dw a sf i r s t l yp r o p o s e db yf l e t c h e ra n d l e y f e r 【3 2 】f o rs o l v i n gn o n l i n e a rp r o g r a m m i n g ( n l p ) a n df o ri t se x c e l l e n tn u m e r i c a lr e s u l t s ，m a n yr e s e a r c h e r s b e g i ni n t e r e s t e di ni t t h el a g r a n g i a nf u n c t i o no rt h ep e n a l t yf u n c t i o na r ea l w a y su s e d i nt h et r a d i t i o n a lm e t h o df o rs o l v i n gn l p h o w e v e r , t h e r ea l w a y se x i s ts o m ep r o b l e m s ， s u c ha st h ec h o i c eo fa p r o p e rp e n a l t yp a r a m e t e r t h er e s u l tw i l lb eb a di ft h ep e n a l t y p a r a m e t e ri sc h o s e nt o ol a r g eo rt o os m a l l f i l t e rm e t h o di st h ef i r s tp e n a l t y f u n c t i o n f r e em e t h o d a n dn o wm a n yr e s e a r c h e r sb e g i nt od os o m er e s e a r c ho ni t ，s u c ha s f l e t c h e r , d e n n i s ，t o i n t ，l e y f f e r , e t c t h es o f t w a r ef o rs o l v i n gn l ph a sb e e nd e v e l o p e da n di ti sb e t t e rt h a no t h e rs o f t w a r e si ns o l v i n gs o m ep r o b l e m s f i l t e rm e t h o dh a s b e e nu s e dw i t ht h et r u s tr e g i o nm e t h o d 【2 8 ，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 ) m e t h o d 【3 1 ，s e q u e n t i a ll i n e a rp r o g r a m m i n g ( s l p ) m e t h o d 【1 6 ，2 9 ，i n t e r i o rm e t h o d 【5 ，9 0 ，9 5 ，p a t t e r ns e a r c hm e t h o d 【2 】f u r t h e r m o r e ，i ta l s oh a sb e e nu s e df o rs o l v i n g o t h e r p r o b l e m s ，s u c ha sn o n s m o o t ho p t i m i z a t i o np r o b l e m 【3 0 t h ef i l t e rm e t h o du s e st h ed o m i n a n c ec o n c e p to fm u l t i - o b j e c t i v eo p t i m i z a t i o n t 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 mi sc o n s i d e r e dt ob eab i - o b j e c t i v eo p t i m i z a t i o n p r o b l e m ，i e ，m i n i m i z i n gb o t ho ft h eo b j e c t i v ef u n c t i o na n dt h ec o n s t r a i n tv i o l a t i o n i nf a c t ，i ti san o n m o n o t o n em e t h o d ，w h i c hi sb e n e f i c i a lf o rr e c e i v i n gt h eg l o b a lc o n v e r g e n c e t h ep a p e rh a sad e e pr e s e a r c hi ni t w ei m p r o v et h ef i l t e rm e t h o da n d f u r t h e r m o r e ，w cp r o p o s ean e wa l g o r i t h mw h i c ha l s oh a sv e r yg o o dp r o p e r t i e s s i n c ef i l t e rm e t h o di san o n m o n o t o n em e t h o d ，w ec o n s i d e rd e s i g n i n gan e wn o n m o n o t o n em e t h o dt os o l v en l ei nc h a p t e r2 ，w ep r o p o s ean e wn o n m o n o t o n el i n e s e a r c hm e t h o d t h ea l g o r i t h md o e sn o tu s eap e n a l t yf u n c t i o no rl a g r a n g i a nf u n c t i o n t ot e s tt h ea c c e p t a b i l i t yo fs t e p s t h ea l g o r i t h mt h a tw e i n v e s t i g a t eh e r ea l s od o e sn o t u s et h ec o n c e p to ff i l t e ro rt h ef e a s i b i l i t yr e s t o r a t i o np h a s e r a t h e r , t h i ss t r a t e g ya d m i t s af l e x i b i l i t yi na c c e p t i n gs t e p st h a ti sc o m p a r a b l ew i t hf i l t e rm e t h o d s n u m e r i c a lr e s u l t s s h o wt h ee f f i c i e n c yo ft h ea l g o r i t h m i nc h a p t e r3 ，w cp r o p o s ean e wn o n m o n o t o n es q pm e t h o df o rs o l v i n gt h em i n i m a xp r o b l e m s ，w h i c hi sa na p p l i c a t i o no ft h ea l g o r i t h mp r o p o s e di nc h a p t e r2 t h e a l g o r i t h mi sg l o b a l l ya n dl o c a l l yc o n v e r g e n ta n dn u m e r i c a lr e s u l t ss h o wt h ee f f i c i e n c y o ft h ea l g o r i t h mi ns o l v i n gt h ep r a c t i c a lp r o b l e m s 一v 一 英文摘要 a l lt h ep a p e r sm e n t i o n e da r es q pt y p ea l g o r i t h m s i ns q pt y p em e t h o d s ，t h ef i r s t o r d e rt a y l o re x p a n s i o n si su s e dt oa p p r o x i m a t et h ec o n s t r a i n t sw h i c hi sag o o dw a yf o r n lc o n s t r a i n t s ，w h i l ef o rh n c o n s t r a i n t s ，w h i c hi sn o tp r o p e r i nt h ep o i n to fn u m e r i c a l p e r f o r m a n c e ，t h eh nc o n s t r a i n tv i o l a t i o nm a ya l t e rv a s t l yf r o mo n ei t e r a t i o np o i n tt o a n o t h e ro n e ，w h i l ef o rt h en lc o n s t r a i n t s ，t h eo p p o s i t es i t u a t i o nm a y a r i s e t h u s ，f r o m t h ea s p e c to fc o m p u t a t i o n ，w em a ya l l o wt h ed i f f e r e n tf l e x i b i l i t yf o rt h eh nc o n s t r a i n t s a n dt h en lc o n s t r a i n t s ，r e s p e c t i v e l y s t i l li np r a c t i c a ll i f e ，t h e r ea r eal a r g en u m b e ro f p r o b l e m sh a v eb o t ho ft h eh na n dn lc o n s t r a i n t s s oi ti sd e s i r a b l et oc o n s i d e rt h eh n a n dn lc o n s t r a i n t si n d e p e n d e n t l y i nb i d i m e n s i o n a lf i l t e rs q pm e t h o d s ，t h o u g ht h e y c o n s i d e rt h eo b j e c t i v ef u n c t i o na n dt h ec o n s t r a i n tv i o l a t i o nr e s p e c t i v e l y , t h e yc o n s i d e r a l lt h ec o n s t r a i n t st o g e t h e ra n do n l yo n ec o n s t r a i n tv i o l a t i o n t i l e yd on o tp a ya t t e n t i o n t ot h ei n d i v i d u a lb e h a v i o r so ft h eh na n dn lc o n s t r a i n t s i nc h a p t e r4 ，w ep r o p o s e ak i n do ft r i d i m e n s i o n a lt r u s tr e g i o nf i l t e rm e t h o d b e c a u s eb o t ho ft h eh na n dn l c o n s t r a i n t sh a v et h e i ro w nb e h a v i o r s ，w ec o n s i d e rt h eh na n dn lc o n s t r a i n t sa p a r ta n d d e f i n et h ec o n s t r a i n tv i o l a t i o n sr e s p e c t i v e l y t h u st h en e wf i l t e rc o n s i s t st h r e ev a l u e s ： t h ev a l u eo ft h eo b j e c t i v ef u n c t i o n ，t h em e a s u r eo ft h eh na n dn lc o n s t r a i n tv i o l a t i o n s ot h ec o n d i t i o n sf o rat r i a ls t e pt ob ea c c e p t e da r em o r er e l a x e d t h i ss t r a t e g ya d m i t sa f l e x i b i l i t yi na c c e p t i n gt r i a ls t e p sw h i c hi sc o m p a r a b l ew i t hb i - d i m e n s i o n a lf i l t e rm e t h - - o d s t h ea l g o r i t h mi sg l o b a l l ya n dl o c a l l yc o n v e r g e n ta n dn u m e r i c a lr e s u l t ss h o wt h e e f f i c i e n c yo ft h ea l g o r i t h m i ti sn o t e dt h a ts q pt y p ea l g o r i t h m sh a v et w op r o b l e m s ，i e ，t h el a r g ec o m p u t a t i o n a la m o u n ta n dt h ei n c o m p a t i b l ep r o b l e m s e q u e n t i a ls y s t e m so fl i n e a re q u a t i o n s ( s s l e ) m e t h o do rq p f r e em e t h o d ，w h i c ho n l yr e q u i r e sa te a c hi t e r a t i o nt h es o l u t i o n o faf e wl i n e a rs y s t e m su s u a l l yw i t hc o m m o nc o e f f i c i e n tm a t r i c e s ，w e r ed e v e l o p e dt o a d d r e s st h ec o m p u t a t i o ni s s u e si nt r a d i t i o n a ls q pm e t h o d s i nc h a p t e r5 ，w ep r o p o s ea n e ws s l ea l g o r i t h m t h r e el i n e a re q u a t 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 x ，i n s t e a d o ft w oq u a d r a t i cp r o g r a m m i n gs u b p r o b l e m s ，a r es o l v e di ne a c hi t e r a t e t h u s ，t h et o t a l c o m p u t a t i o na m o u n t so ft h en e wa l g o r i t h mi sl e s st h a nt h a to fa l g o r i t h mo f 【3 2 b y u s i n gt h ef i l t e rt e c h n i q u e ，t h ep e n a l t yf u n c t i o ni sn o tu s e dh e r ea n dt h et r o u b l e s o m eo f c h o o s i n gt h es u i t a b l ep e n a l t yp a r a m e t e ri sa v o i d e d t h ea l g o r i t h md o e sn o tn e e ds p e c i a ld e m a n d st ot h ei n i t i a lp o i n t t h ex a c t i v es e tp r o c e d u r ei su s e di nt h ea l g o r i t h m o n l yt h ec o n s t r a i n t si nt h e ) ( 一a c t i v es e ta n dt h ee q u a l i t yc o n s t r a i n t ss e ta r ec o n c e r n e d ， 一v i 英文摘要 w h i c hi sh e l p f u lf o rs i m p l i f y i n gt h ec o m p u t a t i o n a lp r o c e s s t h ea l g o r i t h mh e r ei sa n i m p r o v e m e n tw o r ko f 【3 9 ，4 0 ，w h i c hc a n a v o i dt h es p e c i a lc a s e sw h e r et h ed e c e n tp r o p e r t yo ft h ea l g o r i t h mi n 【4 0 】m a yn o te n s u r e d w ec a ns e e t h a tt h en e wa l g o r i t h mn o t o n l yp r e s e r v e st h ea d v a n t a g e sm e n t i o n e da b o v ef o rt h ea l g o r i t h mo f 【3 2 】a n d 【3 9 ，4 0 1 ， b u ta l s oh a si t so w nf e a t u r e s t h ea l g o r i t h mi sg l o b a l l ya n dl o c a l l yc o n v e r g e n ta n d n u m e r i c a lr e s u l t ss h o wt h ee f f i c i e n c yo ft h ea l g o r i t h m k e yw o r d s ：n o n l i n e a rp r o g r a m m i n g ，n o n - m o n o t o n e ，f i l t e r ，m u l t i o b j i e c t i v e v 一 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：董叁塑 趔墨年月日 i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下 各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学 位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存 论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务； 学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在 不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术 活动。 学位论文作者签名： 益塞塑 2 盟基年月日 第一章引言 第一章引言 1 1 约束非线性规划基本理论 考虑如下形式的非线性约束优化问题( n l p ) ： m l n s t ，( z ) c i ) = 0 ，i = 1 ，2 ，m 。， c f ( z ) 0 ，i = m 。+ 1 ，m ， ( 1 1 ) ( 1 2 ) ( 1 3 ) 其中目标函数，( z ) 和约束函数q ( z ) ，i = 1 ，2 ，仇是光滑的。记e = 1 ，2 ，m 。) ，i = m 。+ 1 ，m ) 。 下面我们以问题( n l p ) 为例，给出相关的约束非线性规划理论，对于仅有 等式约束或者仅有不等式约束的n l p 问题也有类似的理论结果。首先，我们给 出约束优化问题的全局极小点和局部极小点的概念。 定义1 1 ：称z r “为可行点当且仪当( 1 2 一1 3 ) 成立。也就是说可行点是满足 所有约束条件的点。所有可行点组成的集合称为可行域。 记可行域为 d = zq ( z ) = 0 ，i e ，c t ( z ) 0 ，i ，) 由可行域的定义可知，求解约束优化问题就是在可行域d 上寻求一个点z ，使 得目标函数厂( z ) 达到最小。下面给出其解的精确定义。 定义1 2 ：设z + d ，如果，( z ) f ( x + ) ，对v x d 成立，则称z + 是问题 ( n l p ) 的全局极小点。如果对于切x d 且z z + 有f ( x ) ，( z + ) 成立，则 称z + 是全局严格极小点。 定义1 3 ：设z + d ，如果存在某个6 0 ，使得对于v x dnb ( z + ，6 ) ，有 厂( z ) 厂( z + ) 成立，则称z + 是问题( n l p ) 的局部极小点。如果对于一切 z dnb ( x + ，6 ) 且z 矿有i ( x ) f ( x + ) 成立，则称z + 是局部严格极小点。 第一章引言 其中b ( z + ，6 ) 是以x + 为中心，6 为半径的广义球 b ( x + ，6 ) = zi i z z i i ：6 ) 全局极小点也常称为总体极小点。很显然，全局( 严格) 极小点也是局部( 严 格) 极小点。一般情况下，直接利用定义1 3 去判断一给定点z + 是否为局部解 很难做到。一个很显然的困难是dnb ( z ，6 ) 中通常有无穷多个点，从而直接 验证定义1 3 的条件是不可能的。因此，有必要给出只依赖于在x 点处的目标 函数和约束函数的信息，且与定义1 3 等价的条件。我们称这样的条件为最优性 条件。在给出最优性条件之前，先给出以下几个基本概念。 定义在给定点z 处的不等式积极约束集为 j ( x ) = i i i q ( x ) = o ) 定义1 4 ：( l i c q ) 若向量集 v q ( z ) ，i euj ( z ) ) 是线性无关的，则称在z 点处 的线性无关约束规范( l i c q ) 条件成立。 定义问题( n l p ) 的拉格朗同函数为 l ( x ，a ) = m ) + a c ( z ) = m ) + 地( z ) ， t = 1 其中a = ( a 1 ，a 2 ，入m ) t 是拉格朗口乘子，c ( z ) = ( c ( z ) 1 ，c ( z ) 2 ，c ( z ) 。) t 。 定义1 5 ：( 一阶必要条件) 假设x + 是问题( n l p ) 的局部极小点，且在x + 点处的 l i c q 条件成立，则存在一个拉格朗日乘子a + = ( 入：，坨，入) t 使得以下条件 成立： v l ( x + ，入+ ) = v f ( x + ) + 兰1n v q ( z + ) = 0 ， q ( z + ) = 0 ，i e ；q ( z 4 ) 0 ，i i ， 入；0 ，入；c i ( z + ) = 0 ，i i 条件( 1 4 1 6 ) 就是著名的k k t 条件。 下面再给出几个相关的约束规格条件。 一2 一 ( 1 4 ) ( 1 5 ) ( 1 6 ) 第一章引占 定义1 6 ：( 严格互补条件) 点x + 是问题( n l p ) 的局部极小点，a + 是相应的拉格朗 日乘子，即( x + ，a 4 ) 满足k k t 条件( 1 4 1 6 ) 。如果对任意的i i ，a ；q ( z + ) = 0 ，则称互补条件成立，它要求n 与c i ( x ) 中至少有一个为0 。若 ( a ；) 2 + 【c i ( x + ) 】2 0 ，v i ， 则称严格互补条件成立。 定义1 7 ：( m f c q 条件) 给定点x + 和不等式积极约束集j ( z + ) ，如果 ( 1 ) 【v q ( z + ) ，i e ) 线性无关； ( 2 ) 集合s = d 匙“id t v q ( z + ) = 0 ，i e ，d r v c i ( x + ) 0 ，i j ( x + ) ) 非 空， 则称在z 处m a n g a s a r i a n f r o m o v i t z 约束规范( m f c q ) 条件成立。 定义1 8 ：( 二阶必要条件之一) 假设x + 为问题( n l p ) 的局部最优点且满足l i c q 条件，入为相应的拉格朗日乘子，则有 其中 d r y 。l ( x + ，a + ) d 0 ，对vd f ( 入) ， f ( a ) = d i v e l ( z + ) t d = 0 ，i e ) o d lx t c i ( x + ) t d = 0 ，k 0 ，i j ( x + ) ) n 0 ，对v 0 d f ( 入+ ) ， 其中f ( a + ) 定义同定义i 9 ，则z 是问题( n l p ) 的局部严格极小点。 定理1 1 ：假设矿为问题( n l p ) 的局部极小点，且在该点m f c q 条件成立，则 其相应的拉格朗k l 乘子入+ 的集合k ( a + ) 是非空有界的。 定理1 2 ：假设z + 为问题( n l p ) 的k k t 点，a + 为其相应的拉格朗日乘子，则在 z 点处s m f c q 条件成立当且仅当入+ 是唯一的。 下面我们给出几个常用的关于收敛速度的定义。 定义1 1 2 ：如果存在实数o t 0 ，q 0 ，使得迭代点列( z k ) 满足下而的关系式， 则称 z k ) 具有q q 阶收敛速度。 k - i - - m * o o 糕并x 鸹l i z 七一+ 扩 一 ( 1 7 ) 特别地， ( 1 ) 当q = 1 ，q 0 时，称该序列具有q 一线性收敛速度； ( 2 ) 当1 0 时，称该序列具有q 一二阶收敛速度。 1 2 滤子方法 解非线性规划问题的滤子方法最早是由f l e t c h e r 和l e y f e r 【3 2 】提出的。由 于其良好的数值例子而受到广泛的重视。自从第一篇文章发表以来，已有很多 一4 一 笫一章引言 人在做这方面的工作，如f l e t c h e r ，d e n n i s ，t o i n t ，l e y f f e r 等。关于解非线性 规划问题的滤子方法的软件已经出现，并且该软件和其它软件相比，在解有些 问题上很有优势。滤子方法做为一种无罚参数的方法，现在已经和信赖域方 法【2 8 】，序y 0 - - 次规划( s q p ) 方法【3 1 】，序列线性规划( s l p ) 方法【1 6 ，2 9 】，内 点法【5 ，9 0 ，9 5 】，模式搜索法【2 】结合起来，用米解n l p 问题，并且还用米解决其 它类型的问题，如在【3 0 】中，滤子法被用来解非光滑优化问题。本章介绍滤子 方法现有的主要成果。 1 - 2 1 滤子思想的产生 大多数解( n l p ) f 司题的方法是在牛顿法的基础上通过迭代产生点列 z 七】。 假设z 知是当前迭代点，通过对问题( n l p ) 的线性或二次逼近，得到下一个迭代 点z 七+ 1 。如果_ 【z 靠近最优点，那么这个点列是可以收敛的。反之，如果z 七 远离最优点，那么由这种方法产生的点列可能是不收敛的。那么对于后一种情 况，如何确定其收敛性是一类值得研究的问题。 价值函数方法( 特别是罚函数法) 是解决这类问题的传统方法。价值函数 通常是日标函数和约束违反度的一个线性组合。比如说f 1 精确罚函数定义为 p ( x ，7 ) ：= y ( x ) + r h ( x ) ， 其中r 0 是罚参数，其中约束违反度为 t n e m ( z ) ：= m a x q ( z ) ，o ) + i i c , ( z ) l l ， i = 1r n e + 1 ”l l 表示某个范数。当r 充分大时，我们可以通过要求每次迭代过程中，罚函 数都有一个充分的下降来得到全局收敛性。但是，一个合适的罚参数依赖于原 问题的解，一般要求r l i a + 怯其中”是原问题局部最小值z + 对应的拉格朗 日乘子，”1 1 2 表示2 范数。这使得寻找一个合适的罚参数是不太容易的。当罚 参数取得过大时，任何一种单调的算法都会减少牛顿步的步长，最终会减慢其 收敛速度。z o p p k e d o n a l d s o n 【1 0 2 】的博士论文中用大量的算例表明：如果不用 罚函数，s q p 方法效果反而很好。同时，该论文也没有用w a t c h d o g 方法或其它 技巧。但它没有给出全局收敛性证明。 受【1 0 2 的影响，f l e t c h e r 提出了一种不需要罚函数的方法，即滤子方法。 该方法的目的是要尽可能多的接受步长为l 的牛顿步，以达到全局收敛性和较 一5 一 第一章引言 快的收敛速度。 1 2 2 解n l p 问题的滤子方法 滤子方法不需要考虑罚参数的选取，从而避免了罚函数方法中的不足。罚 函数方法是将目标函数和约束违反度放在一起考虑。而滤子方法视其为双目标 优化问题，将它们分别考虑，即使f ( x ) 和h ( x ) 都最小，其中第二个目标更重 要。因为我们必须保证解的可行性，所以必须要求在最优点z + 处，约束违反度 h ( x ) = 0 。借用多目标优化中关于控制的概念，我们给出如下定义。 定义1 1 3 ：一个点z 七控制另外一个点x l 当且仅当，( z 七) ，( 勋) 且h ( x k ) h ( x 1 ) 。 这就是说我们从两个方面( 目标函数值和违反约束度) 来度量一个点的好坏。 定义1 1 4 ：滤子是一列数对 ( ，( z z ) ，h ( z z ) ) ) ，其中各个点之间互不控制。 定义1 1 5 ：记当前滤子为氕一1 。若点z 七不被滤子氕一1 中的任意一点控制，则 ( f ( x k ) ，h ( x k ) ) 被滤子氕一1 接受。若将( f ( x k ) ，h ( x k ) ) 加入到滤子兀一1 中，则需 移去那些被z 知控制的点。 令d k = 【i 0 为常数，则令新的迭代点x 七+ 1 = z 七+ d ，并适当的增加信赖域半 径，更新滤子( 将z 七加到滤子中，并移走滤子中那些被z 南控制的点) 。否 则，若该试探点不被当前滤子接受，就拒绝接受该点成为新的迭代点，并令 z + 1 = z 七，减少信赖域半径后重新解q p 子问题( 1 8 ) 。在f l e t c h e r 和l e y f f e r 【3 1 】 中，只把那些不能使f ( x k ) 下降的点放在滤子中，其它可以被接受的点并不放 进滤子里。 以上是滤子方法的基本思想，然而为保证其收敛性，还需作一些改进。 ( 1 ) 滤子接受条件。为避免得到不可行的极限点，即h ( x + ) 0 ，z 七一 z + ，k _ + ，将滤子接受条件加强，对任意的2 d 七一1 ， h ( x k + 1 ) z h ( x 1 ) 或者f ( x k + 1 ) f ( x 1 ) 一 h ( x k + 1 ) ， ( 1 1 0 ) 其中p ，7 ( 0 ，1 ) 为常数。以后几乎所有分析滤子方法的文章都把( 1 1 0 ) 或类似 条件做为接受滤子的条件并且保证h ( x k ) 一0 ，k _ + o o 。 ( 2 ) 充分下降条件。如果只有条件( 1 1 0 ) 成立，并不能保证可以收敛到一个 稳定点。比如说，如果只有h ( x 七+ 1 ) f l h ( x f ) 成立，那么迭代点列可能只收敛 到任意一个可行点，而不是最优点。所以当约束违反度h ( x ) 充分小时，我们要 求目标函数，( z ) 要有充分的下降。记a q k = 一v ( x k ) r d 一 d t h k d 。 若 a q j c 0 ，( 1 11 ) 其中盯( 0 ，1 ) 是常数。我们称( 1 11 ) 为选择条件，( 1 1 2 ) 为充分下降条件。 ( 3 ) 可行性恢复阶段。若( 1 8 ) 无解或约束条件不相容，则可以用一可行性 恢复阶段来得到一个新的迭代点瓢+ 1 ，使( 1 8 ) 有解并且z 七+ 1 可以被滤子接 受，详细的修复算法见【3 2 】。可行性恢复阶段实质上就是就是降低约束违反度 h ( x ) 的值。 下面我们给出接受滤子的条件。 定义1 1 6 ：一个试探点z 七十d 被滤子接受当且尽当下面两种情况： ( 1 ) z 七+ d 被滤子氕一1 和z 七接受，即对所有的f d k 一1u 忌) ，( 1 1 0 ) 成 一7 一 、j 2il ，七 g 盯 一 、l ， l七 z j ，j 一 、， 七 z ，lf j 求要“um 童( 第一章引言 卫： ( 2 ) 若x q k 0 ，则要求充分下降条件f ( x 知) 一，( z + d ) t t x q k 成立。 基于上述思想，f l e t c h e r 和l e y f e r 【3 1 】给出一种信赖域s q p 滤子方法，算法如 下： a l g o r i t h m1 ：信赖域s q p 滤子方法 步1 给出初始点z o ，令k = 0 ，参数p ，7 ，7 7 ，