（运筹学与控制论专业论文）一种具有全局收敛性的ncp函数滤子算法.pdf

上海大学硕士学位论文 摘要 约束非线性规划问题是最优化领域中重要的研究课题，许多实际问题都可以 归结为约束非线性规划问题。自从二十世纪七十年代后期，序列二次规划( s q p ) 已 成为解非线性最优化问题的一种最常见、最有效的方法。滤子s q p 最初是由 f l e t c h e r 在 1 9 中提出的，是与信赖域相结合的一种算法。 在 4 2 中u l b r i c h 介绍了一种利用乘子函数来构造滤子的一个分量的方法， 从而不用二次矫正步的就克服m a r a t o s 效应，而且证明了这种方法具有局部超线 性收敛性。基于 4 2 中想法我们在本论文巾我们构造了增广的拉格朗日函数 易( 力来代替【1 9 】中的以习，也同样达到不用二次矫正步就避免了m a r a t o s 效应， 而且结合n c p 函数来构造了滤子的另一个分量以力。从而我们将【1 9 】巾滤子的两 个分量给替换得到新的算法。这种算法具有全局收敛性。 本文在前言中介绍了课题的研究背景和研究现状以及本文在论文中所做的工 作；第二章介绍了约束非线性规划的一些基本的原理和结论，包括基本迭代公式， 最优性条件和收敛速度，以及滤予方法的产生和发展等方面的内容：第三章给出 了算法中滤予的构造，介绍了非线性互补函数( n c p ) 的定义和性质，鉴于在k - k - t 点处的非线性互补条件，我们对于每个迭代点可以构造出一个新的违反约束度， 这样就得到了一种新的滤予，于是通过把n c p 函数放入滤子中我们构造出了一种 新的滤子s q p 算法。该算法的特征是用到了多目标优化里控制的思想：一个迭代 点被接受当且仅当该点是否被滤子接受。在二次子问题不可行时，该算法需要可 行性恢复阶段( 首次在 1 9 中被提出) 。我们证明了在假设条件下，这种新的滤 子s q p 算法具有全局收敛性和超线性收敛性。第四章是关于此算法的数值分析， v 上海大学硕士学位论文 我们通过编程实验算例得出了比较满意的数值结果，显示该算法是解决约束非线 性规划的一种有效算法，而且比原来算法更有效。第五章为本文的结论与展望。 关键词：n c p 函数滤子逐步二次规划全局收敛性 上海大学硕士学位论文 a b s t r a c t t h ec o n s t r 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 ht o p i ci n n 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 ob et h ec 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 s t 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 ht r u s tr e g i o n t e c h n i cw a si n i t i a l l yp r o p o s e db yf i s c h e ri n 【19 i n 【4 2 ，u l b f i c hi n t r o d u c eam e t h o dw i t hm u l t i p l i e r sf u n c t i o n ，a v o i d e dt os u f f e rf r o mm a r a t o s ，a n d p r o v e dt h a tt h i sa l g o r i t h mh a st h es u p e r l i n e a rl o c a lc o n v e r g e n c e o nt h eb a s i so f 【4 2 ，w ec o n d u c t a u g m e n t e dl a g r a n g i a nf u n c t i o n ( 力i n s t e a d i n go f 八力a n dp ( x ) w i t hn c pf u n c t i o n t h i s n e wa l g o r i t h ma l s oa v o i d st os u f f e rf r o mm a r a t o sa n dn u m e r i c a lt e s t sw h i c ha l ep r e s e n t e dc o n f i r m t h er o b u s t n e s so f t h i sa p p r o a c h 。f i n a l l yw ep r o v et h en e wa 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 ， f i s t l yt h eh i s t o r yo ft h i sp a p e ra n dt h eg e n e r a la s p e c to ft h es t u d ya r ei n t r o d u c e d s e c o n d l yw e i n t r o d u c es o m eb a s i ct h e o r i c e sa n dc o n c l u s i o n so fn l pp r o b l e m si nc h a p e r l ，i n c l u d i n gt h e i 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 t c h a p e r3p r o p o s e st h ec o n s t r u c t i o no 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 f a n o n l i n e rc o m p l e m e n tp 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 pc o n d i t i o na tak k - tp o i n t ，w e c o u l dc 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 r a t i v ep o i n tg e tan e wf i l t e r t h u san e wf i l t e r s 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 r ec h a r a c t e r r i z e db yt h e i rn s eo ft h ed o m i n a n c ec o n c e p t o 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 yp a r a m e t e rw h o s ea d j u s t m e n tc a nb e p 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 【19 1 ) i sn e e d e db yt h em e t h o di nt h i sp a p e r a m e c h a n i s mf o rp r o v i n gg l o b a lc 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 pf u n c t i o ni sd e s c r i b e d f o rc o n s t r a i n e dn 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 e r4 , n u m e r i c a lt e s t s a r ep r e s e n t e dt oc o n f i r mt h er o b u d t n e s sa n de f f i c i e n c yo ft 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 d e n c o u r a g i n gf i l t e rs t u d ya r ep r o v i d e d i nc h a p t e r5 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 v i l - 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研 究工作，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已发表或撰写过的研究成果参与同一工作的其他同 志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名：夏苫埘 日期： 。咿莎加 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定， 即：学校有权保留论文及送交论文复印件，允许论文被查阅 和借阅；学校可以公布论文的全部或部分内容 ( 保密的论文解密后应遵守此规定) 躲复陟叶新虢殷吼小l 口 上海大学硕士学位论文 第一章前言 1 1 研究背景与现状 约束非线性规划问题是最优化领域中重要的研究课题，许多实际问题都可以 归结为约束非线性规划问题。它有很多实际的应用价值：在应用数学方面，可以 应用到约束拟合和优化控制领域；在物理学方面，可以应用到光学和流体力学等 方面：此外还可以应用到化学、工程学、计算机科学等学科。由此可见它的重要 性。 到了二十世纪其实年代后期，序列二次规划( s o p ) 已成为解非线性最优化 问题的一种最常见、最有效的方法。我们知道s o p 方法具有类似牛顿法的快速收 敛性。但传统的s o p 方法都存在价值函数如何选取的问题，而多数罚函数含有罚 因子， 5 1 3 1 5 1 6 1 7 1 8 2 4 2 5 2 6 2 7 2 8 3 4 4 0 都是研究罚函 数的。罚因子的选取一直是s o p 方法的一个难点，选的过大或过小都会对算法产 生不良的影响。f l e t c h e r 在文 1 9 中提出了一种新的思想克服了以上困难，即 把滤子和信赖域s o p 相结合，不需要选取罚因子。一个重要的概念就是如果试探 点能降低目标函数或约束违反度函数的值，那么该点就被算法接受，而不象价值 函数那样将两者结合。在1 9 9 8 年，针对滤子信赖域的s o p 算法，f l e t c h e r 等人 给出的运算结果令人鼓舞的。紧随气候，f l e t c h e r 等人又给出相关算法的全局 收敛性的证明。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 在 2 1 对 1 0 算法进 行了改进，给出两种算法路子s o p 算法并证明了他们的全局收敛性。在1 9 9 9 年 r f l e t c h e r ，s g o u l d 和p l t o i n t 在 2 3 中提出了一种序列二次规划( s l p ) 算 法并证明了其全局收敛性，该算法也避免了使用罚函数。随后由s u l b r i c h 在 4 2 对乜d 中的滤子的做了改进后克不用二次矫正步同样避免了m a r a t o s 效应， 并证明了这种算法具有超线性局部收敛性。 1 2 本文的主要工作 本文从最优化条件出发( 即k t t 条件) ，构造非线性互补( n c p ) 函数，用一 个等式来表示k k t 条件中的互补性质，把这种方法应用到s o p 滤子中去，具体做 法是在滤子对中把n c p 函数范数代替约束违反度函数，这样在迭代点逼近可行域 的同时能使互补条件得到满足。为了避免二次矫正步，我们做的另一个工作是在 上海大学硕士学位论文 滤子对中用增广的拉格朗日函数代替目标函数。在此基础上给出一个新的n c p 函数滤子算法，给出和证明了算法的收敛性和收敛速度并用数值例子说明算法的 有效性。 第二章介绍 2 1 最优化方法中常用的数学基础知识 这一节我们将介绍一些在最优化方法中经常被用到的数学基础知识。 定义2 1 1 映射l i | i ：一月被称为上的半范数当且仅当它满足下面的条件 1 1 1 4 1 - 0 ，v x e ： 2 8 纠1 i 叫0 爿l ，v # e 刀，z ； 3 忙+ 川1 1 4 1 + i n i ，v x , j , e 另外，如果该映射还满足 = o x - - 0 ， 则称i i | l 为上的范数。 令x - - - - ( 玉，毛，而) ，一些常用的向量范数有 1 1 4 1 。= m a x h ，( 乞) ； 4 1 。= m ( ) ； 卅i ：( 兰# ) ，( ) ； = l 这些都是名范数的特例。一般的，对于1 尸 o 如果彳0 ，并且0 叫i = o ，其中秒表示所有元素都为零的矩阵 2 。0 刮i = l 圳卅i ，对于任意f 月： 0 彳+ 纠l 0 硎+ 0 卅i 此外，令彳”，我们还可以这样定义矩阵范数 悱赠蝌 这里恫i 是某一向量范数。 定义2 1 2设：一詹，i 若在点i 处对于自变量 x - - - - - ( 而，吒，而) 厂的各分量的偏导数 掣( 川，2 ，功 o x ， 都存在，则称函数在点i 处一阶可导，并且称向量 耽为：、o f 3 ( x ) ，掣，掣) 厂 嘶 是在点i 处一阶导数或梯度。 定义2 1 3 设：一爿，i 和血记吠l | 纠i ) 为i f 纠i 的高阶无穷小。 如果存在口，使得 ( a 一( 为= 血+ 训纠i ) ， 则称函数在点i 处可微，并称 搿国= 0 缸 是在在点i 处的微分。 下面的定理给出了微分和梯度之间的关系。 定理2 】1设：专詹，j 若在点j 处可微，则在点i 处的梯度 v f ( h 存在，并且有 上海大学硕士学位论文 识习= 叭矽血 我们再给出r l 元函数的二阶导数即h e s s e 矩阵概念。 定义2 1 4设：f 专一，i 若在点i 处对于自变量 z = ( 玉，屯，艺) ，的各分量的二阶偏导数 丝盟( ：l ，2 ，功 o x , c l x j 、。 。7 都存在，则称函数在点i 处二阶可导，并且称矩阵 a 2 以习= a 2 八习a 2 ( 为 a 2 ( 为 如2如熟础 a 2 八习a 2 ( 为a 2 以为 挑鸥2挑 a 2 以为a 2 ( 为 a 2 ( 为 a x p ) c 、宅x p h 宅x j 是在点j 处的二阶导数或h e s s e 矩阵。 定义2 1 5设乃：寸刀，；记履力= ( 属( 力，忍( 力，么( 力) ，如果 勿( ，= l ，2 ，功在点j 处对于自变量z = ( 而，而，磊) 7 的各分量的偏导数 掣( ：1 ，2 ，功 a x ? v 都存在，则称向量函数h 在点处是一阶可导的，并且称矩阵 v 脓，钗力= 粥( 曲 豇 鸽( 力 挑 ( 力 阮 鸥( 力 o , a 力魄( 力坛( 砷 挑 上海大学硕士学位论文 是乃在点i 处的一阶导数或j a c o b i 矩阵，简记做 v 履习= v 。履为 我们给出刀元函数在一点处的t a y l o r 展式。它在非线性规划的理论和方法研 究中都有重要的应用。 定理2 i 2 设：寸一，i 若在点；的某邻域具有一i 阶连续偏导数， 则在点i 处有二阶t a y l o r 式： 以a 叫= 以为+ 耿为，缸+ 吾越，v 2 s ( x + o 断) a x ，o 9 1 2 2 约束非线性规划的概念和基本迭代格式 约束非线性优化问题是指 卿以力 ( 2 2 1 ) s t 乞( 砷= 0 ，= l ，犯： ( 2 2 2 ) 哆( 力0 ，= 仍+ 1 ，m ， ( 2 2 3 ) 其中，以力及q ( 力( ，= l ，朋) 都是定义在g - 上的实值连续函数，且至少有一个 是非线性的。朋是一正整数，饬是介于0 和历之间的整数。( 力被称为目标函 数，乞( 力( ，= 1 ，历) 被称为约束函数。s t 是英文s u b j e c tt o ( 满足于) 的缩写 定义2 2 1z g - 被称为问题( 2 2 1 ) 一2 2 3 ) 的可行点当且仪当( 2 2 2 ) 一 ( 2 2 3 ) 成立。所有的可行点组成的集合被称为可行域。 我们称( 2 2 2 ) 一( 2 2 3 ) 为约束条件。根据定义可知，可行点就是满足所有 约束条件的点。我们可以把可行域记为刃： 刃= 石i 弓( 力= 0 ，= 1 ，仫： q ( 力0 ， ，= 睨+ 1 ，m 上海大学硕士学位论文 由可行域的定义知，求解约束优化问题( 2 2 1 ) 一( 2 2 3 ) 就是在可行域刃上寻求 一点j 使得目标函数以力达到最小。 最优化方法通常采用迭代方法求它的最优解，其基本思想是：给定一个初始 点而j ，按照某一迭代规则产生一个点列 ) ，使得当 五 是有穷点列时，其 最后一个点是最优化模型的最优解。当 五) 是无穷点列时，它有极限点，且其极 限点是最优化模型问题的最优解。 一般地，设为第后次迭代点，砟为第后次搜索方向，a t 为第后次步长因子， 则第后次迭代为 x k + l = + 口量幺 从这个迭代格式可以看出，不同的步长因子和不同的搜索方向以构成了不同 的方法。此时搜索方向是在五处的下降方向，即吃满足 v f ( x k ) ，砟 0 是用户可接受的，则称这样的一维搜索为近似一维搜索，或者不精确一维搜索，或 者可接受一维搜索。删o ( 1 9 6 6 ) 和g o l d s t e i n ( 1 9 6 5 ) 分别提出了不精确一维搜 索过程。设 = a 0 i ( 五+ a 砟) 以以) ) 是一个区间，为了避免口太小或者太靠近区间的端点，a r m i j o g o l d s t e i n 不精 确线性搜索准则即满足下面的关系式 ( 五+ 口量) 以) + ( 1 一p ) ( v ( x a ) 厂口正反， ( 2 2 4 ) ( 五+ a t 以) ( 诈) + p ( v ( x a ) 厂吒砟， ( 2 2 5 ) 其中0 0 ，v x ed f i s ( x ，6 ) 有( 力( ，) 成立，则称，是问题( 2 2 i ) - ( 2 2 3 ) 的局部极小点。如果对于一切z d f i b ( x ，6 ) r x ，有( 力 以，) 成立，则称，是局部严格极小点。其中联，6 ) 是以，为中心以6 为半径的广义 球： 夙，6 ) = 川卜刘：6 全局极小点也常称为总体极小点。显然，全局( 严格) 极小点也是局部极小 点。 一个好的算法应具备的典型特征为：迭代点能稳定地接近局部极小点， 一8 - 上海大学硕士学位论文 的邻域，然后迅速收敛于，当给定的某种收敛准则满足时，迭代即终止。一般 的，我们要证明迭代点列 以 的聚点( 即子序列的极限点) 为一局部极小点。一 般情况下，直接利用定义2 3 2 去判断一给定点，是否为局部解很难做到。一个 很显然的困难是刀n 顶，6 ) 中通常有可行域刃中的无穷多个点，从而直接验证 定义2 3 2 的条件是不可能的。因此，有必要给出只依赖在，点处的目标函数和 约束函数的信息，且与定义2 3 2 的条件等价的条件。这样的条件我们称其为最 优性条件。 下面我们将以非线性规划问题( 2 2 1 ) 一( 2 2 3 ) 为例，给出相关的约束规划 一些结果，对于只有等式约束或者只有不等式约束的非线性规划问题也有类似的 理论结果。 定义2 3 3 ( l i c q ) 给定点，和积极约束集以，) ，以功= z u i e l 乞( 力= 0 ) ，如 果积极约束梯度集 v 乞( ，) ，以，) ) 是线性无关的，我们称约束规范条件在 ，点是线性无关的，记为l i c q 定理1 3 1 ( 一阶必要条件) 假设，是问题( 2 2 1 ) 一( 2 2 3 ) 的局部极小点，且在 ，点l i c q 条件成立， 则存在一个l a g r a n g e 乘子a ，a = ( 九) 座刖f ， f = l ， ，= 仍+ l ，柳，在( ，a ) 满足如下条件： v j z ( ，a ) = 耽，) + v 乞( ，) = o ， ( 2 3 1 ) # j q ( ，) = 0 ，f ， c ( ，) 0 ，i ， 0 ，r q ( ，) = o ，i ( 2 3 2 ) 、( 2 3 3 ) ( 2 3 4 ) 证明参见 1 2 3 8 。条件( 2 3 1 ) 一( 2 3 4 ) 就是著名的k k t 条件。 定义1 3 4 ( 严格互补条件) 给定问题( 2 2 1 ) - ( 2 2 3 ) 的局部极小点，及在这一 最小点处的l a g r a n g e 乘子为a 满足k k t 条件，即满足( 2 & 1 ) 一( 2 3 4 ) 。 上海大学硕士学位论文 如果对任意，a 与乞( ，) 中恰有一个为0 ，则称严格互补条件成立。 定义2 3 1 5 ( m f c q )给定点，( ) 及和积极约束集以，) ， 以力= 万u i 弓( 曲= 0 ) ，如果存在一个向量满足： v c , ( 1 ) r c o 0 ，j ( x ) a v e ( ，) ，= o ， ，z 且等式约束梯度 v e ( ，) ，毋是线性无关的，称为m a n g a s a r i a n f r o m o v i t z 约束 规范条件成立。 定理2 3 2假设，为( 2 2 i ) - ( 2 2 3 ) 的局部极小点，且在，点m f c q 条件成 立，则在，点的l a g r a n g e 乘子a 的集合k ( a ) 是非空有界的。 定理证明参见 9 和 1 1 。 定义2 3 6 ( s m f c q )给定点，( ) 及在这一点的l a g r a n g c 乘子r ；如果 有v e ( ，) ，z u 是线性无关的，而且存在一个向量z 撇v c a ，) z o ) ， 髟= ，i = o ) ，是九的第，个元素，则称在，处满足s m f c q 条件。 定理2 3 3假设非线性规划问题( 2 2 1 ) - ( 2 2 3 ) 在点，满足k k t 条件且 k - k - t 乘子为；l = ( 以，) 厂则在，点s m f c q 条件成立当且仅当k k t 乘了九是唯 一的。 定理证明参见 8 定理2 3 4 ( 二阶必要条件之一) 假设，为( 2 2 1 ) 一( 2 2 。3 ) 的局部最优点且满足l i c q 条件，设a 为l a g r a n g e 乘 子并满足k k t 条件( 2 3 1 ) 一( 2 3 4 ) ，则有 ，v ? 以，允。砌o ，对任意只旯) 其中 上海大学硕士学位论文 只九) = lv q ( ，) 厂c o = 0 ，句n 国lv e ( ，) ，缈= 0 ，钗，) n 厶九 o i n 国iv q ( ，) ，之0 ，4 ，) n a = 0 ) v g z x i ，a ) 为l a g r a n g e 函数在，点的二阶胁矩阵。 定理2 3 5 ( 一i 阶必要条件之二) 假设，是( 2 2 1 ) - ( 2 2 3 ) 的局部最小点，设 i ，f 在，点均是两次连续可微的，且假设s m f c q 在，点成立，a 为( 2 2 1 ) - ( 2 2 3 ) 在，点的乘子，则有 i v j z ( g ，a ) z o ，对任意z 只允) ， 其中只a ) 定义同上。 定理2 3 6 ( 二阶充分条件) 假设对某个可行点，( ) ，存在l a g r a n g e 乘子 a 满足k k t 条件( 2 3 1 ) 一( 2 3 4 ) 。又设 ，v 2 z ( ，允) 0 ，对任意只a ) ，0 3 0 ， 则，是( 2 2 1 ) 一( 2 2 3 ) 的局部最小点。 收敛速度也是衡量最优化方法有效性的重要方面。设算法产生的迭代点列 而) 在某种范数意义下收敛，即 l i m i i 五一，i i = o 下面我们给出几个常用的收敛速度的定义。 定义2 1 4 如果存在实数口l 及一个与迭代轮数后无关的常数矿 0 ，使得迭代 点列 满足下面的关系式，则称 砟) 具有夕一口收敛速度。 熘1 醇i l x x + 玎l - z i i = q 特别地， ( 1 ) 当a = 1 ，1 q o ，迭代点列 叫做具有夕一线性收敛速度； 上海大学硕士学位论文 ( 2 ) 当l 口 o 或口= 1 ，q = o 时，迭代点列 ) 叫做具有超p 一线性收敛速 度； ( 3 ) 当口= 2 时，迭代点列 ) 叫做具有夕一二阶收敛速度。 一般认为，具有超线性收敛速度和二阶收敛速度的方法是快速的。 另外一种收敛速度是月一收敛速度( 根收敛速度) ，设 土 乃= 烛s u p l l x k 一，i i ， ( a ) ，= 1 如果属= 0 ，则称五是r 一超线性收敛于，；如果0 坞 1 ，则称 是r 一线性收敛于， ( b ) 尸= 2 如果是= 0 ，则称是启一超平方收敛于，：如果o 忍 1 ，则称 以是月一平方收敛于，；如果驾l ，则称是启一次平方收敛于， 2 4 滤子方法的产生和发展 首先给出本节用到的部分记号： 勺( 力= ( q ( 砷，( 力) ，乃( 力= ( + ( 力，乞( 力) ， “砖= ( 乞( 砖，t a x ) ) ， 以( 力= ( q ( 力，( 力) = y e s - ( x ) ， 4 ( 曲= ( 卅( 力，( 力) = v c a x ) ， 钗力：( 以( 力，4 ( 力) ，f ： l ，) ，： 。，功，仅勺( 功) ：壹i 乞( 力i ， 履o ( 力) = m a x ( o ，乞( 力 ，仅d 力) = 履吃( 力) + 仅o ( 力) ，彳= 【砟) ，q = “五) ， 4 = 钗五) ( 力，乞( 功( ，f ud 都是_ 刀上的两次连续可微函数。 在约束非线性规划中，滤子的概念最早是由f l e t c h e r 和l e y f f e r 提出( 见 1 9 ) ，在 1 9 中它的主要目的是运用序列二次规划( s o p ) 时不再使用罚函数作为 价值函数，而是考虑滤子能否接受。 序列二次规划( s o p ) 对于求解非线性约束问题 上海大学硕士学位论文 r a i n 以力 s 2 乞( 力= 0 ， ( 2 4 1 ) ( 2 4 2 ) 乃( 力0 ( 2 4 3 ) 是非常有效的，它是通过每次求解一个二次子规划来寻找试探步，从而使用迭代 的方法迭代到满足给定精度的最优点。序列二次规划( s q p ) 是目前解决约束优化 最常用的、也是非常流行方法之一。该方法具有许多良好的性质，比如具有全局 收敛性、收敛速度快且稳定等性质。s o p 最早是由w i l s o n 提出。随后由h a n 和 p o w e l l 发展的w h p 算法可谓是最早的s q p 算法了。此后，s o p 就发展并流行了起来 3 6 3 7 就是这方面的成果。s q p 发展至今已不再是一个具体的算法，而是一个 概念性的方法。 在2 2 我们知道最优化的迭代方法具有最基本的两类：线性搜索和信赖域。 我们记基于线性搜索框架的s q 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 m m i n g ) ，这类方法是通过求解二次子问题 m i n 扩叭而) + 丢屏 。旺白( 力+ 4 ( 力厂d = o 白( 力+ 4 ( 力7 0 ( 其中犀”l a g r a n g e 函数的胁矩阵的近似。4 为第后次迭代点) 来得到 试探步盔，再选取合适的罚函数作为价值函数( 如厶罚函数) ，然后进行线性搜 索找到下一个点如。得到新的二次子问题，如此迭代下去直至收敛。 对于基于信赖域框架的另一类s q 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 m m i n g ) ，此类方法只是限制了反的某一范数不能 超过其每步给定的信赖域半径t ，该二次子问题如下： m i n d r v f ( x k ) + - 1r i b # s j c e q n + 4 文叠r a = 0 。 0 ( 力+ 4 ( 习厂0 ， 上海大学硕士学位论文 d l l _ a - ， ( 其中为第量步迭代时的信赖域半径，同样，忍”l a g r a n g e 函数的 h e s s e 矩阵的近似) 。 s q p 方法中可能会有拒绝能够取得进展的迭代过程的情况产生，于是妨碍了 s q p 方法的快速收敛性，这种现象称之为m a r a t o s 效应( 参见 3 5 ) ，这时我们可以 采用w a t c h d o g 技术或二阶校正步( s o c ) 来避免它( 参见 9 3 ) 。 然而传统的s q p 方法不论是l s q p 还是t s q p ，都需要选择某一合适的罚函数作 为价值函数。使用罚函数法会在选择罚参数时仍然碰到许多困难，通常罚因子需 要有界，这个界值很难确定，界太小会使迭代步迭代至( 2 4 1 ) 一( 2 4 3 ) 的不可 行点：界太大会削弱了目标函数对迭代步的影响，从而导致当( 2 4 1 ) 一( 2 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 9 ) 这种带滤子的t s q p 不需要用罚函数作为价值函数，这样可以避免由于罚参数选择 而带来的困难。滤子思想类似于多目标优化的思想，即允许一个迭代步被滤子接 受当且仅当目标函数值下降或约束违反度函数值下降。 1 9 中考虑非线性规划形 式如下： m i n ( 砷 s j c a x ) 0 这篇文章给出了详细的算法过程以及非常好的算法数值执行结果，表明这种滤子 t s q p 是一种非常有效的算法，但它没有给出全局收敛性的证明。1 9 9 9 年，r o g e r f l e t c h e r 、n i c h o l a si m g o u l d 、s v e nl e f f e r 和p h i l i p p e l t o i n t 在 2 0 中给出 了滤子t s q p 的的全局收敛性的证明，但对 2 0 中的算法有所改进，它证明了两类 信赖域的滤子s q p 算法，第一类算法是把每个迭代步分解成两步，即n o r m a l 步 与t a n g e n ti a l 步之和；即把求解信赖域子问题 1 m i nv ( 以) 7 办i 1 口, t 屏 ( 2 4 4 ) 二 础t a x ) + 4 ( 力，= 0 ( 2 4 5 ) t a x ) + a a x ) ，0 ( 2 4 6 ) 上海大学硕士学位论文 0 d l l _ a j ( 2 4 7 ) ( 其中五为当前迭代点，为第石步迭代时的信赖域半径) 分为两步来做，设反 为( 2 4 4 ) 一( 2 4 7 ) 的解，把砟分解为喀= 砟+ 厶，其中满足以下式子： 和 s t ( 力+ 4 ( 力厂= 0 c j 七a f 蝌终0 临a - s t t a x ) + 以( 曲，= 0 t a x ) + 4 ( 砷，0 事实上，佟是使+ 体满足信赖域子问题的约束条件；乓使为了使目标函数充分 下降。 2 1 这篇文章中证明了满足条件的和磊是可以找到的。第二类算法就直 接求解( 2 4 4 ) 一( 2 4 7 ) 得到( 这样的要求更强) 。 2 0 中证明了这两种算法 都是全局收敛的。2 0 0 2 年，s t e f a nu l b r i c h 在 4 2 中提出了一种修改的滤子t s q p ， 4 2 中考虑用修改的滤子t s q p 来求解非线性规划问题( 2 4 1 ) 一( 2 4 3 ) 。考虑用 l a g r a n g e 函数 z ( 五力= j r ( 力+ “力 ( 其中少= ，乃厂) r m ，乃o ) 来代替 1 9 中的( 砷，用 9 ( 五力= i i 如( 力1 1 2 2 + 1 1 ( 力1 1 2 2 + ( 砷) 2 来代替 1 9 中的反d 力) ，即用( p ( 五力，z 力) 来代替而构成滤子。伴随这个主要 的修改，对 1 9 中滤子t s q p 算法的其它地方也做了相应的修改。 4 2 证明了这种 修改的算法的全局收敛性，并且这个修改的滤子t s q p 算法不需要计算二阶校正步 ( s o c ) 也可避免m a r a t o s 效应，具有超线性收敛性，全局收敛性的证明的技巧与 1 7 中类似。2 0 0 3 年，s u l b r i c h 和m i j l b r i c h 在 2 3 中提出了一种非单调的滤子 上海大学硕士学位论文 t s q p 算法，与 4 2 中类同的使用( a ( 五力，z ( 力) 做为滤子的元素，其中口( 五力 是用乘子函数构造的。可以参见 3 0 3 2 求解等式约束非线性规划问题： i i l i n 以力 ( 2 4 8 ) s t 白( 力= 0 ( 2 4 9 ) 4 3 中证明了该修改非单调滤子算法在一定的条件下有如下结论： ( 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 6 - 1 8 2 2 2 7 3 3 3 4 4 2 4 3 4 4 均是滤 子信赖域s q p 方法。事实上，滤子也可以和l i n e s e a r c h ( 线性搜索技术) 相结合 来求解一个非线性规划问题。 以上无论是传统的s o p 还是滤子s q p 在求解非线性规划问题时，每次迭代都需 要求解一个或几个二次规划( q p ) 子问题。当刀( j 的维数) 增加时，整个算法在迭 代过程的计算量的增加非常快。为了解决这一问题，有人提出了用线性规划 ( l p ) 来代替二次规划( q p ) ，而对与同样维数的石，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 滤子算 法并证明了其收敛性，即带滤子的序列线性规划，可以避免使用罚函数。 2 0 中也是考虑非线性规划问题( n l p ) ( 2 4 1 ) 一( 2 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 ) ，设而为当前迭代点， m i n 耽五) 7 d ( 2 4 1 0 ) s t 乃( 力+ 4 ( 砷厂0 ( 2 4 1 1 ) i | d l l _ 七 ( 2 4 1 2 ) 2 0 这篇文章只是证明了迭代点列在定条件下收敛到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 和r f l e t c h e r 在 1 2 中提出了s l p 滤子算法并采 e q p 迭代步来求解不等式约束的非线性规划( 2 4 8 ) 一( 2 4 8 ) 。事实上， 7 中 是考虑每次采用线性规划( l p ) 来预估积极约束集，每次预估的集合彬称之为工 作集，然后根据这个工作集来形求解等式约束二次规划子问题( e q p ) ，其具体做 法如下，先求解( 2 4 1 0 ) 一( 2 4 1 2 ) 得缸，令形= ，i v 乞( 力，如+ q ( 力= 0 ) ，然后 求解如下等式约束的二次子规划( e q p ) ： 1 r a i n 职) ，d + 寺d s , d 二 础q ( 力+ q ( 力7 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 步，测