（运筹学与控制论专业论文）一种结合ncp函数的滤子sqp算法的研究.pdf

上海大学硕士学位论文 摘要 约束非线性规划问题是最优化领域中重要的研究课题，许多实际问题都可以 归结为约束非线性规划问题。自从二十世纪七十年代后期，序列二次规划( s q p ) 已 成为解非线性最优化问题的一种最常见、最有效的方法。滤子s o p 最初是由 f l e t c h e r 在 1 中提出的。是与信赖域相结合的一种算法。 传统的s q p 方法需要选择某一合适的罚函数作为价值函数。使用罚函数法会 在选择罚参数时通常罚因子需要有界，这个界值很难确定。为了避免罚参数带来 的困难，在 1 中，这种带滤子的s o p 不需要使用罚函数作为价值函数，而是考虑 滤子能否接受，这样可以避免由于罚参数选择而带来的困难。 本文第一章介绍了约束非线性规划的一些基本的原理和结论，包括基本迭代 公式，最优性条件和收敛速度，以及滤子方法的产生和发展等方面的内容；第二 章给出了算法中滤子的构造，介绍了非线性互补函数( n c p ) 的定义和性质，鉴于 在k - k t 点处的非线性互补条件，我们对于每个迭代点可以构造出一个新的违反 约束度，这样就得到了一种新的滤子，于是通过把n c p 函数放入滤子中我们构造 出了一种新的滤子s q p 算法。该算法的特征是用到了多目标优化里控制的思想： 一个迭代点被接受当且仅当该点是否被滤子接受。在二次子问题不可行时，该算 法需要可行性恢复阶段( 首次在 1 中被提出) 。我们证明了在假设条件下，这种 新的滤子s o p 算法具有全局收敛性和超线性收敛性。第三章是关于此算法的数值 分析，我们通过编程实验算例得出了比较满意的数值结果，显示该算法是解决约 束非线性规划的一种有效算法。第四章为本文的结论与展望。编程我们用到的是 i a t l a b 软件，主要程序具体可见本文的附录。 关键词：n c p 函数滤子逐步二次规划全局收敛性 上海大学硕士学位论文 a b s t r a c t t h ec o n s u a i n e dn o n l i n e a rp r o g r a m m i n g ( n l p ) p r o b l e mi sa ni m p o r t a n tr e s e a r c h t o p i ci nn u m e r i c a lo p t i m i z a t i o nf i e l d s m a n yp r a c t i c a lp r o b l e m sc a nb er e d u c e dt o i t s i n c e1 9 7 0 s ，t h es 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 ) a l g o r i t h mh a sb e c o m ea l l a t t r a c t i v eb a s i ci t e r a t i v em e t h o d a n dt h ef i l t e rs q pm e t h o dw h i c hi n c o r p o r a t e dw i t h t r u s tr e g i o nt e c h n i q u ew a si n i t i a l l yp r o p o s e db yf l e t c h e ri n 【l 】 t r a d i t i o n a ls q pm e t h o d sn e e ds o m ep r o p e rp e 值l t yf u n c t i o nt ob et h em e r i t f u n c t i o n t h em o t i v a t i o ni n 【i 】h a sb e e nt od i s p e n s ew i t ht h ei d e ao f ap e n a l t yf u n c t i o n , w i t hav i e wt op r o v i d i n ga l la l g o r i t h mt h a td o e sn o tr e q u i r ed i f f i c u l td e c i s i o n sf r o mt h e u s t q i nr e g a r dt ot h ec h o i c eo f p e n a l t yp a r a m e t e r s i nt h i sp a p e r , w ef i r s ti n t r o d u c es o m eb a s i ct h e o r i e sa n dc o n c l u s i o n so fn l p p r o b l e m si nc h a p t e r l ，i n c l u d i n gt h ei t e r a t i v ef o r m u l a t i o n ，t h eo p t i m i z a t i o nc o n d i t i o n , t h er a t eo fc o n v e r g e n c ea n dt h ef i l t e rm e t h o d n e x tc h p t c r 2p r o p o s e st h ec o n s t r u c t i o n o ff i l t e ri nt h ea l g o r i t h m , t h ed e f i n i t i o na n dp r o p e r t i e so fan o n l i n e a rc o m p l e m e n t p r o b l e m ( n c p ) f u n c t i o n r e g a r d i n gt ot h en c p c o n d i t i o na tak k - tp o i n t , w ec o u l d c o n s t r u c tan e wc o n s t r a i n tv i o l a t i o ni ne a c hi t e m t i v ep o i mt og e tan e wf i l t e r t h u sa n e wf i l t e rs q pm e t h o di sc o n s t r u c t e d s u c hm e t h o d sa c h a m c t c f i z e db yt h e i rl l s co f t h ed o m i n a n c ec o n c e p to ft h em u l t i - o b j e c t i v eo p t i m i z a t i o n , i n s t e a do fap e n a l t y p a r a m e t e rw h o s ea d j u s l m e n tc a nb ep r o b l e m a t i c r e s t o r a t i o np h a s e ( f i r s t l yp r o p o s e di n 【l 】) i sn e e d e db yt h em e t h o di n t h i s p a p e r am e c h a n i s mf o rp r o v i n gg l o b a l c o n v e r g e n c ei nf i l t e rs q pm e t h o dw i t ht h en c p f u n c t i o ni sd e s c r i b e df o rc o n s t r a i n e d 一- 上海大学硕士学位论文 n o n l i n e a ro p t i m i z a t i o np r o b l e m w ep r o v et h a tt h ea l g o r i t h mh a sg l o b a lc o n v e r g e n c e a n ds u p e r l i n e a rc o n v e r g e n c er a t e su n d e rs o m em i l dc o n d i t i o n s f u r t h e ri nc h a p t e r3 ， n u m e r i c a lt e s t sa r ep r e s e n t e dt oc o n f i r mt h e r o b u s t n e s sa n de f f i c i e n c yo f t h i sa p p r o a c h f i n a l l y , t h ec o n c l u s i o na n de n c o u r a g i n gf u t u r es t u d yf l t r ep r o v i d e di nc h a p t e r4 k e y w o r d s ：n c pf u n c t i o n , f i l t e r ，s q p , g l o b a lc o n v e r g e n c e 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研 究工作，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已发表或撰写过的研究成果参与同一工作的其他同 志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名：仓中 日期：，2 叼、多， 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定， 即：学校有权保留论文及送交论文复印件，允许论文被查阅 和借阅；学校可以公布论文的全部或部分内容 ( 保密的论文解密后应遵守此规定) 签名：冷牛导师签名“习考弘l 日期：2 7 占， 上海大学硕士学位论文 第一章介绍 1 1 最优化方法中常用的数学基础知识 这一节我们将介绍一些在最优化方法中经常被用到的数学基础知识。 定义1 1 1 映射帅：r ”一r 被称为f 上的半范数当且仅当它满足下面的条件 1 1 k l l - - o ，v x e r ”； 2 1 i 叫l = l a l h ，v a e r ，z r ”； 3 1 p + 卅l i 卅i + 0 卅l ，v x ，y r ” 另外，如果该映射还满足 i i , l l = o 铮x = o ， 则称8 为掣上的范数- 令工= ( 而，恐，) 7 r ”，一些常用的向量范数有 0 x l l 。- - , m k , i ，以) ； = i x , i ，“) ； i _ l 0 捌：= ( 杰而2 卢，幔) ； 这些都是l 范数的特例。一般的，对于l p o 如果- o ，并且0 0 珏= o ，其中。表示所有元素都为零的矩阵： 2 1 酬= l d l l 彳9t 对于任意c r ； 3 0 彳+ 硎i i 卅| + 0 叫i 此外，令a 胄”，我们还可以这样定义矩阵范数 = 学槲 这里是某一向量范数 定义1 1 2 i 殳f ：k “一r 1 ，；r 4 若，在点；处对于自变量童= ( 五，恐， 毛) 7 的各分量的偏导数 o f _ ( x ) ( f ：1 ，2 ，功 都存在，则称函数j 厂在点王处一阶可导，并且称向量 v f ( x ) = 掣，百o f ( x ) o x ,，掣7 c 甄识 是在点；处一阶导数或梯度。 定义1 1 3 设：秽- * r 1 ，；和缸r “记o q 酬) 为0 酬i 的高阶无穷小 如果存在口彤，使得 ，西a x ) - f ( x ) = a 7 缸+ d q i 叫d ， 则称函数在点x 处可微，并称 矽( 两= 矿缸 是在，在点；处的微分。 下面的定理给出了微分和梯度之间的关系。 定理1 1 1设，：寸r ，x e 若，在点i 处可微，则，在点i 处的梯度 w ( 刁存在。并且有 上海大学颈士学位论文 ( 习= v f ( 矽缸 我们再给出n 元函数的二阶导数即h e s s e 矩阵概念。 定义1 1 4 设：f _ r 1 ，i 掣若在点；处对于自变量j = ( 为，而，而) 7 的各分量的二阶偏导数 肇婴( ，：l 2 ，帕 o x , 积 都存在，则称函数，在点；处二阶可导。并且称矩阵 a 2 ，( 动= a 2 ，( ；) 觑2 a 2 厂( 西 0 x ：魄 a 2 ，( 西 钆铂 a 2 ( 而 铂 a 2 ，( 两 融2 a 2 ，( 习 阮 是，在点；处的二阶导数或h e s s e 阵。 定义1 1 5设 ：肜斗r 1 ，x e r ”记矗( 砷= ( ( n 吗( 曲，吃( 功) 7 如果啊 ( f = l ，2 ，朋) 在点i 处对于自变量x = ( 五，恐，矗) 的各分量的偏导数 掣c ，：1 ，2 ，功 。 一 都存在，则称向量函数h 在点；处是一阶可导的，并且称矩阵 v | j j ( 工) = a 啊( 曲 戤 型 觑 a g ( x ) 0 x , a ( 砷 孰 盟堂盟 铂饥 是h 在点；处的一阶导数或j a c o b i 矩阵，简记做 盟眠黼一诋；黼一鲜 巡啪一阪； 上海大学硕士学位论文 v h ( x ) = v 。_ i l ( x ) 我们给出n t u 函数在一点处的t a y l o r 展式。它在非线性规划的理论和方法研 究中都有重要的应用。 定理1 1 2 设厂：r ”一r 1 ，；r ”若，在点；的某邻域具有二阶连续偏导数， 则，在点；处有二阶t a y l o r 展式： f ( x + a x ) ：厂( ；) + v f ( x ) r a x + 昙缸r v 2 6 + 0 a x ) a x ，0 0 1 1 2 约束非线性规划的概念和基本迭代格式 约束非线性优化问题是指 卿( x ) ( 1 2 1 ) s t q ( 曲= 0 ，= l ，巩： ( 1 2 2 ) q ( 曲0 ，i = ，吃+ l ，m ， ( 1 2 3 ) 其中，( 工) 及q ( 功( f = l ，m ) 都是定义在掣上的实值连续函数，且至少有一个 是非线性的。m 是一正整数，是介于o 和m 之间的整数。( x ) 被称为目标函 数，q ( 工) ( i = l ，m ) 被称为约束函数。s t 是英文s u b j e c tt o ( 满足于) 的缩写。 定义1 2 1x r “被称为问题( 1 2 1 ) - ( 1 2 3 ) 的可行点当且仅当( 1 2 2 ) 一 ( 1 2 3 ) 成立。所有的可行点组成的集合被称为可行域。 我们称( 1 2 2 ) 一( 1 2 3 ) 为约束条件。根据定义可知，可行点就是满足所有 约束条件的点。我们可以把可行域记为d ： d = 缸iq ( 力= 0 ，f = l ，： q ( x ) 0 ，f = 巩+ l - m * 9 m 由可行域的定义知，求解约束优化问题( 1 2 1 ) - ( 1 2 3 ) 就是在可行域d 上寻求 上海大学硕士学位论文 一点x 使得目标函数y ( x 、达到最小。 最优化方法通常采用迭代方法求它的最优解，其基本思想是：给定一个初始 点x ，按照某一迭代规则产生一个点列 椎 ，使得当 x k ) 是有穷点列时，其 最后一个点是最优化模型的最优解。当 x k ) 是无穷点列时，它有极限点，且其极 限点是最优化模型问题的最优解。 一般地，设为第k 次迭代点，以为第七次搜索方向，吒为第k 次步长因子， 则第七次迭代为 鼍+ i = x j + 以 从这个迭代格式可以看出，不同的步长因子q 和不同的搜索方向t 构成了不同 的方法。此时搜索方向吨是厂在& 处的下降方向，即矾满足 夥( 砟) 7 矾 0 i ，( 气+ 口也) ，( 毛) ) 是一个区间，为了避免口太小或者太靠近区间，的端点，a r m i j o - g o i d s t e i n 不精 确线性搜索准则即满足下面的关系式 ，魄+ q 以) 八靠) + ( 1 一p ) ( 耳) ) 7 吼面， ( 1 2 4 ) 厂( + 吼以) 蔓f ( x k ) + p ( v f ( x k 矿4 ， ( 1 2 5 ) 其中o p - - t r ( v f ( x k ) ) 7 4 ， ( 1 2 6 ) 其中，口e ( p ，1 ) 。在实际中有时仅采用准则( 1 2 6 ) ，并且要求a 不太小，我们把 这种仅利用准则( 1 2 6 ) 的做法叫做简单准则。 信赖域方法是一种新的保证算法总体收敛的方法，它不仅可以用来代替一维 搜索，而且也可以解决h e s s e 矩阵不正定和吒为鞍点等困难。这种方法首先选择 一个缩短了的步长，然后利用胛维二次模型选择搜索方向。即先确定一个步长上 界嚏，并由此定义鼍的邻域瓯， q 。= x ln x x , l l - - h , 假定在这个邻域e e - _ 次模型是目标函数f ( x ) 的一个合适的模拟，然后利用玎维二 上海大学硕士学位论文 次模型确定搜索方向丑，并取k 。= 毛+ 。这种方法既具有牛顿法的快速局部收 敛性，又具有理想的总体收敛性。由于步长受到使t a y l o r 展式有效的信赖域的限 制，故方法又称为限步长方法。 信赖域方法的模型问题是 r a i n q ”( s ) = ，( 砟) + 9 1 7 j + 去j r g ；3 ， 二 s t 0 4 1 - o ，v x d a b ( x ，国有，( 力，( ，) 成立，则称，是问题( 1 2 1 ) 一 ( 1 2 3 ) 的局部极小点。如果对于一切x d a b ( x ，回且x ，有厂( 力 f ( x ) 成 立，则称工是局部严格极小点。其中曰( ，艿) 是以工为中心以万为半径的广义球： 烈，j ) = 卜巩s 田 全局极小点也常称为总体极小点。显然，全局( 严格) 极小点也是局部极小 点。 一个好的算法应具备的典型特征为：迭代点而能稳定地接近局部极小点x 的邻域，然后迅速收敛于，当给定的某种收敛准则满足时，迭代即终止。一般 上海大学硕士学位论文 的，我们要证明迭代点列 气) 的聚点( 即子序列的极限点) 为一局部极小点一 般情况下，直接利用定义1 3 2 去判断一给定点，是否为局部解很难做到。一个 很显然的困难是d n 刀( f ，毋中通常有可行域d 中的无穷多个点，从而直接验证 定义1 3 2 的条件是不可能的。因此，有必要给出只依赖在，点处的目标函数和 约束函数的信息，且与定义1 3 2 的条件等价的条件。这样的条件我们称其为最 优性条件。 下面我们将以非线性规划问题( 1 2 1 ) 一( 1 2 3 ) 为例，给出相关的约束规划 一些结果，对于只有等式约束或者只有不等式约束的非线性规划问题也有类似的 理论结果。 定义1 3 3 ( l i o q ) 给定点x 和积极约束集，( ，) ，( 曲= e u i ij q ( = o ，如 果积极约束梯度集 v q ( ，) ，f ，( ，) 是线性无关的，我们称约束规范条件在， 点是线性无关的，记为l i c q 定理1 3 1 ( 一阶必要条件) 假设，是问题( 1 2 1 ) 一( 1 2 3 ) 的局部极小点，且在 ，点l i c q 条件成立，则存在一个l a g r 柚g e 乘子a ，= ( 乃) 。u f ，e - - 1 ，) ， ，= + 1 ，脾) ，在( x ，) 满足如下条件： v ，工f ，) = v ( x + ) 一五v c i ( x ) = o ， ( 1 3 1 ) 扣l c 0 ) = 0 ，f e e ， ( 1 3 2 ) q ( ，) 兰0 ，f ， ( 1 3 3 ) 五o ，4 + q ( x ) = o ，j ， ( 1 3 ，4 ) 证明参见 4 4 。条件( 1 3 1 ) 一( 1 3 4 ) 就是著名的k - k - t 条件。 定义1 ，3 4 ( 严格互补条件) 给定问题( 1 2 1 ) 一( 1 2 3 ) 的局部极小点z 及在这一 最小点处的l a g r a n g e 乘子为五满足k k - t 条件，即满足( 1 3 1 ) 一( l3 4 ) 。 如果对任意f i ，与q ( x + ) 中恰有一个为o ，则称严格互补条件成立。 上海大学硕士学位论文 定义1 3 5 ( 虾c q ) 给定点，( r 。) 及和积极约束集，o ) ，j ( x ) = e u f i l q ( 的= o ) ，如果存在一个向量国r ”满足： v c , ( x ) 7 毋 0 ，e ，o + ) f l z 、c ? 旗号= 0 i e e 且等式约束梯度 v q ( ，) ，j 毋是线性无关的，称为m a n g a s a r i a n f r o m o v i t z g 勺 规范条件成立。 定理i 3 2 假设，为( 1 2 1 ) - ( 1 2 3 ) 的局部极小点，且在f 点w f c q 条件成 立，则在，点的l a g r a n g e 乘子的集合r ( 五) 是非空有界的。 定理证明参见 1 9 。 定义1 3 6 ( s 盯c q ) 给定点，( r ”) 及在这一点的l a g r a n g e 乘子矿；如果 有v q ( ，) ，i e e u j 是线性无关的，而且存在一个i 甸f z e r ”满r e , ( x + k o ) ， k = f j i 耳= 0 ) ，五是的第i 个元素，则称在工处满足s m f c q 条件。 定理1 3 3假设非线性规划问题( 1 2 1 ) - ( 1 2 3 ) 在点膏+ 满足k - k t 条件且 k - k t 乘子为= ( 以，丑) 7 则在，点s 盯c q 条件成立当且仅当k - k - t 乘子五是唯 一的。 定理证明参见 1 8 定理1 3 4 ( 二阶必要条件之一) 假设，为( 1 2 1 ) 一( 1 2 3 ) 的局部最优点且满足 l i c q 条件，设为l a g r a n g e 乘子并满足k k t 条件( 1 3 1 ) 一( 1 3 4 ) ， 则 有 7 v 。2 三f ，a 弦o ，对任意盘f ( ) 。 其中 ，( 五) = 印i v c , ( x ) 7 国= o , i e e f l 和i v c , ( x ) 7 缈= o ，i e 爿f ) n ，丑 o o 9 上海大学硕士学位论文 国i v e , ( x ) 7 脚2 0 , i 彳o ) n ，五= o ) v 。2 工o ，) 为l a g r a n g e 函数在，点的二阶h e s s e 矩阵。 定理1 3 5 ( 二阶必要条件之二) 假设，是( 1 2 1 ) 一( 1 2 3 ) 的局部最小点，设， c 在r 点均是两次连续可微的，且假设s 师c q 在，点成立，a 为( 1 2 1 ) 一( 1 2 3 ) 在工点的乘子，则有 z 7 v 。2 三( ，名) ：o ，对任意2 f ( a ) ， 其中，( ) 定义同上。 定理1 3 6 ( 二阶充分条件) 假设对某个可行点x ( er ”) ，存在l a g r a n g e 乘子 满足k k t 条件( 1 3 1 ) 一( 1 3 4 ) 。又设 c 0 7 v 盯2 上( f ，a ) 珊0 ，对任意e ，( 五) ，国0 ， 则，是( 1 2 z ) - ( z 2 3 ) 的局部最小点。 收敛速度也是衡量最优化方法有效性的重要方面。设算法产生的迭代点列 ) 在某种范数意义下收敛，即 l i m0 以一，j | = 0 下面我们给出几个常用的收敛速度的定义。 定义1 ，3 7 如果存在实数口1 及一个与迭代轮数i i 无关的常数q 0 ，使得迭代 点列 气) 满足下面的关系式，则称k ) 具有q 一口收敛速度。 i - 弋= p 面 i x k + 可l - x * l l s 垡 特别地， ( 1 ) 当口= 1 ，l q o ，迭代点列k ) 叫做具有q 一线性收敛速度； ( 2 ) 当l 口 o 或a = l ，q = o 时，迭代点列 以 叫做具有超q 一线性收敛速 度； 3 ) 当8 = 2 时，迭代点列 黾 叫做具有q 一二阶收敛速度。 上海大学硕士学位论文 一般认为，具有超线性收敛速度和二阶收敛速度的方法是快速的。 另外一种收敛速度是r 一收敛速度( 根收敛速度) ，设 鬈= 烛s u p l l x , - - x * l l ， ( a ) p = 1 如果墨= 0 ，则称吒是五一超线性收敛于，；如果0 墨 l ，则称吒 是r 一线性收敛于f ( b ) p = 2 如果是= o ，则称毛是r 一超平方收敛于，；如果o 恐 ，j = o l ，朋， ( 气( x ) ) = l q ( 力l ， 卅 _ l l ( q ( x ) ) = m a x o ，q ( 工) ) ， p ( 功) = ( 白( x ) ) + ( q ( 功) ，五- - f ( x , ) ，q = c ( ) ， 4 = 彳( 而) 以工) ，c , ( x x ie u x ) 都是掣寸r 上的两次连续可微函数。 在约束非线性规划中，滤子的概念最早是由f l e t c h e r 和l e y f f e r 提出( 见 1 ) ，在 1 中它的主要目的是运用序列二次规划( s o p ) 时不再使用罚函数作为价 值函数，而是考虑滤予能否接受。 序列二次规划( s q p ) 对于求解非线性约束问题 r a i n ，( ( 1 4 1 ) s j c e 0 ) = 0 ， q ( x ) 茎0 l l ( 1 4 2 ) ( 1 4 3 ) 上海大学硕士学位论文 是非常有效的，它是通过每次求解一个二次子规划来寻找试探步，从而使用迭代 的方法迭代到满足给定精度的最优点。序列二次规划( s q p ) 是目前解决约束优化 最常用的、也是非常流行方法之一。该方法具有许多良好的性质，比如具有全局 收敛性、收敛速度快且稳定等性质。s q p 最早是由h a n 在1 9 7 6 年提出。随后由 p o w e l l 和w i l s o n 发展的w h p 算法可谓是最早的s o p 算法了。此后，s o p 就发展并流 行了起来。s q p 发展至今已不再是一个具体的算法，而是一个概念性的方法。 在1 2 我们知道最优化的迭代方法具有最基本的两类：线性搜索和信赖域。 我们记基于线性搜索框架的s o p 方法为l s q p ( l i n e s e a r c hs e q u e n t i a lq u a d r a t i c p r o g r a 姗i n g ) ，这类方法是通过求解二次子问题 m i n d t v f ( x a + 吉只j “c e 砖+ a e t 醇d = o q o ) + 4 ( 功7 d s o ( 其中毋r 是l a g r a n g e 函数的h e s s e 矩阵的近似。气为第k 次迭代点) 来得到 试探步以，再选取合适的罚函数作为价值函数( 如厶罚函数) ，然后进行线性搜 索找到下一个点以+ 。得到新的二次子问题，如此迭代下去直至收敛。 对于基于信赖域框架的另一类s o p 方法，我们记为t s q p ( t r u s tr e g i o n s e q u e n t i a lq u a d r a t i cp r o g r a i a m i n g ) ，此类方法只是限制了矾的某一范数不能 超过其每步给定的信赖域半径趣，该二次子问题如下： m i nd 7 v f ( x a + 三d 7 乓j s t c a x ) + 以7 d = 0 ， q ( x ) + 4 ) 7 d 0 ， l i 矗l 喀。， ( 其中色为第i 步迭代时的信赖域半径，同样，既r l a g r a n g e 函数的 h e s s e 矩阵的近似) 。 s o p 方法中可能会有拒绝能够取得进展的迭代过程的情况产生，于是妨碍了 上海大学硕士学位论文 s q p 方法的快速收敛性，这种现象称之为m a r a t o s 效应( 参见 3 8 ) ，这时我们可以 采用w a t c h d o g 技术或二阶校正步( s o c ) 来避免它( 参见 1 3 3 ) 。 然而传统的s q p 方法不论是l s q p 还是t s q p ，都需要选择某一合适的罚函数作 为价值函数。使用罚函数法会在选择罚参数时仍然碰到许多困难，通常罚因子需 要有界，这个界值很难确定，界太小会使迭代步迭代至( 1 t1 ) 一( 1 4 3 ) 的不可 行点；界太大会削弱了目标函数对迭代步的影响，从而导致当( 1 4 1 ) 一( i 4 3 ) 的可行域边界是曲边时，收敛的速度变的很慢。为了避免罚参数带来的困难，在 1 9 9 8 年，f l e t c h e r 和l e y f f e r 提出了一种带滤子的t s q p 称为滤子t s q p ( 见 1 3 ) 。 这种带滤子的t s q p 不需要用罚函数作为价值函数，这样可以避免由于罚参数选择 而带来的困难。滤子思想类似于多目标优化的思想，即允许一个迭代步被滤子接 受当且仅当目标函数值下降或约束违反度函数值下降。 1 3 中考虑非线性规划形 式如下： r a i nf ( 功 5 j q ( 功0 这篇文章给出了详细的算法过程以及非常好的算法数值执行结果，表明这种滤子 t s q p 是一种非常有效的算法，但它没有给出全局收敛性的证明。1 9 9 9 年，f l e t c h e r 、g o u l d 、l e f f e r 和t o i n t 在 3 中给出了滤子t s o p 的的全局收敛性的证明，并对 f 1 中的算法有所改进，讨论了两类信赖域的滤子s o p 算法，第一类算法是把每个 迭代步分解成两步，i l l j n o r m a l 步与t a n g e n t i a l 步；即把求解信赖域子问题 m i nv f ( x , ) r d + 昙d r b d( 1 4 4 ) “o ) + 以 ) 7 d = 0 ( 1 4 5 ) q 0 ) + 4 0 ) 7 d s 0 ( 1 4 ，6 ) 0 d 临a 。 ( i 4 7 ) ( 其中为当前迭代点，色为第露步迭代时的信赖域半径) 分为两步来做，设吱为 ( 1 4 4 ) 一( 1 4 7 ) 的解，把巩分解为喀= + ，其中满足以下式子： s j + 以o ) 1 心= 0 上海大学硕士学位论文 和 q ) + 4 0 ) 7 n k 0 i f 仇临t 0 f | i 阵a t 盯( x ) + 4 f ( x ) 7 d = 0 q o ) + 4 0 ) 7 d s 0 事实上，是使+ 满足信赖域子问题的约束条件；气使为了使目标函数充分 下降。【3 这篇文章中证明了满足条件的嗥和是可以找到的。第二类算法就直 接求解( 1 4 4 ) 一( 1 4 7 ) 得到喀( 这样的要求更强) 。 2 中证明了这两种算法 都是全局收敛的。2 0 0 2 年，s t e f a nu l b r i c h 在 4 中提出了一种修改的滤子t s q p ， 4 中考虑用修改的滤子t s q p 来求解非线性规划问题( 1 4 1 ) - ( 1 4 3 ) 。考虑用 l a g r a n g c 函数 l ( x ，力= ，( 力+ 广c ( 曲 ( 其中y = 魄7 ，乃) r ”，乃o ) 来代替 3 中的f ( x ) ，用 口( 】o ) ，) = 0c ( x ) 1 1 2 2 + l lc , + ( x ) 0 2 2 + ( 乃7 q + ( 功) 2 来代替【3 中的矗( c ( x ) ) ，即用( 口( x ，力，三阢力) 来代替而构成滤子。伴随这个主要的 修改，对 3 中滤子t s q p 算法的其它地方也做了相应的修改。 4 证明了这种修改 的算法的全局收敛性，并且这个修改的滤子t s q p 算法不需要计算二阶校正步( s o c ) 也可避射i a r a t o s 效应，具有超线性收敛性，全局收敛性的证明的技巧与【2 中类 似。2 0 0 3 年，s u l b r i c h 和札u l b r i c h 在 5 中提出了一种非单调的滤子t s q p 算法， 与 4 中类同的使用p “力，工o ，瑚做为滤子的元素，求解等式约束非线性规划 问题： r a i n ，( 力 ( 1 4 8 ) “屯( 曲= 0 ( 1 4 9 ) 上海大学硕士学位论文 5 中证明了该修改非单调滤子算法在一定的条件下有如下结论： ( i ) 不用二次矫正步( s o c ) 可得二阶收敛性； ( i i ) 不需要调用可行性恢复阶段( f e a s i b l i t yr e s t o r a t i o np h a s e ) 。 通过上面的介绍，我们知道 1 卜 5 均是滤子信赖域s q p 方法。事实上，滤子 也可以和l i n e s e a r c h ( 线性搜索技术) 相结合来求解一个非线性规划问题。 以上无论是传统的s q p 还是滤子s q p 在求解非线性规划问题时，每次迭代都需 要求解一个或几个二次规划( q p ) 子问题。当疗( 苫的维数) 增加时，整个算法在迭 代过程的计算量的增加非常快。为了解决这一问题，有人提出了用线性规划( l p ) 来代替二次规划( q p ) ，而对与同样维数的x ，l p 的计算量较q p 的计算量小的 多。 1 9 9 9 年，r f e l t c h e r ，s l e y f f e r 和p t o i n t 在 6 中提出了一种s l p 滤子算 法并证明了其收敛性，即带滤子的序列线性规划，可以避免使用罚函数。 6 中也是考虑非线性规划问题( n l p ) ( 1 4 1 ) 一( 1 4 3 ) ，与前面介绍不同的是用序列 线性规划s l p ( 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 o p ，即 每次求解一个线性规划( l p ) ，设为当前迭代点， r a i n v f ( x d 7 d ( 1 4 1 0 ) “q 0 ) + 4 ( x ) 7 d - o ( 1 4 1 1 ) 0 d i 肾a t ( 1 4 1 2 ) 6 这篇文章只是证明了迭代点列在一定条件下收敛到f r i t z - j o h n 点，而不是 k k - t 点。这种算法的优点是每次迭代的计算量较小，只需求解( l p ) 子问题， 而不是( q p ) 子问题，但缺点也是很明显的，一方面，该算法不一定收敛到k - k t 点，另一方面，当最优点不在单纯形上时，迭代速度特别慢。为了克服这些困难， 2 0 0 1 年，c m c h i n 和rf l e t c h e r 在 7 中提出了s l p 滤子算法并采e q p 迭代步来 求解不等式约束的非线性规划( 1 4 8 ) 一( 1 4 8 ) 。事实上， 7 中是考虑每次采用 线性规划( l p ) 来预估积极约束集，每次预估的集合称之为工作集，然后根据 这个工作集来求解等式约束二次规划子问题( e q p ) ，其具体做法如下，先求解 上海大学硕士学位论文 ( 1 4 1 0 ) 一( 1 4 1 2 ) 得d 0 ，令取= t l v c a x ) 7 d 0 + q ( 功= o ) ，然后求解如下等式 约束的二次子规划( e q p ) ： 1 m i n f b jd + 妥d tb k d 二 童工q 0 ) + q ( d 7 d s 0 ， 并用二阶矫正步( s o c ) 和c a u c h y 步作为候补迭代。即如果( e q p ) 不被滤子接 受，则计算s o c 矫正步，并测试s o c 校正步是否被滤子接受，如果s o c 锈正 步也不被接受，则计算c a u c h y 步，测试c a u c h y 步是否被接受。但 7 中仍然没 有证明其迭代点列收敛到k k t 点，只证明了该迭代点列收敛到f r i t z - j o h n 点。 2 0 0 4 年，r i c h a r dh b y r d ，n i c h o l a si 融g o u l d ，j n o c e d a l 和r i c h a r da w a l t z 在 8 中提出了一种s l p 算法，但没有运用滤子。而是采用罚函数作为价值 函数。每次求解一个线性规划子问题( l p ) 来预估积极约束集合，得到工作集畋， 与 7 类似，然后根据这个工作集磁求解等式约束信赖域子问题( e q p ) ，幸运的 是， 8 中证明了该算法收敛到k - k - t 点。 运用滤子思想的算法中，大多都需要一个可行性恢复阶段，即当( q p ) 不相容 时，调用可行性恢复阶段求得一个新的迭代点，使得它可行或接近可行( 判别标 准就是看该点能否被主迭代中滤子接受) 。事实上，这一恢复阶段的算法也是至 关重要的，于是2 0 0 1 年，r f l e t c h e r 和s l e y f f e r 在 9 中提出了一种滤子型求解 非线性等式和不等式的算法。2 0 0 3 年，c 札c h i n 在 1 0 中提出了直接用信赖域方 法求解非线性约束不可行的问题，不需要用滤子。 综上所述。自1 9 9 7 年以来，f l e t c h e r 和l e y f f e r 在 1 中提出了滤子思想之 后，至今滤子方法理论一直是在发展完善之中，并且它被应用到其他方法中产生 了许多新的方法。所以，对于滤子方法的研究是当前优化问题的前沿之一。 上海大学硕士学位论文 第二章结合n c p 函数的滤子s q p 方法 2 1 算法中滤子的构造 本文考虑以下形式的约束非线性规划问题( n l p ) r a i n ，( ， 善r n ， “h 【曲= 0 g ( 工) s 0 这里的厂：彤 r ，日( 功= ( 鱼( 功，吨( 破，( 砌：r “ r 和g ( x ) = ( g l ( 功，9 2 ( 功 ，繇 ) ) ：一r ”是二次连续可微函数。 我们用 d = 缸r ”1 日( 功= 0 ，g ( 功o ) 来表示约束非线性规划问题( n l p ) 的可行域。 f l e t c h e r 和l e y f f e r 运用滤子方法来解决( n l p ) ( 参见 1 ) ，这是一种与传 统的惩罚函数法不同的方法。这种方法的思想非常简单，只要能够使得目标函数 充分下降或者约束违背函数充分下降，则解一个序列的二次规划( q p ) 所得的满足 条件的试验点都可以被接受。另外，f l e t c h e r 和l e y f f e r 给出的数值结果也是 非常令人满意的。滤子方法和它们的收敛性质见 1 3 一 5 。 滤子方法的特征是运用了多目标规划的控制思想，代替了在使用的调节过程 中会出问题的罚参数。在滤子方法 1 - e 5 中，对于每个迭代点以，我们除了得 到一个函数值瓴) ，还得到一个违反约束度量p ( x d ，这里 p ( x ) = p ( g 阮) 日瓴) ) = h ( t ) i + m 强 o 毋瓴) ) f 。l j = i 不难看出，如果p ( x 。) = 0 ，则毛可行域d 在这篇学位论文中，我们将对于每个迭代点屯重新定义一