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

上海大学硕士学位论文 摘要 约束非线性规划问题是最优化领域中重要的研究课题，许多实际问题都可以 化为约束非线性规划问题。它有很多实际的应用价值：在应用数学方面，可以应 用到约束拟合和优化控制等领域；在物理学方面，可以应用到光学和流体力学等 方面；此外还可以应用到化学、工程学、计算机科学等学科。由此可见它的重要 性。到了二十世纪七十年代后期，序列二次规划( s q p ) 已成为解非线性最优化 问题的一种最常见、最有效的方法。在1 9 9 8 年，f l e t c h e r 提出了一种新的思想， 即把滤子( f i l t e r ) 和信赖域s q p 相结合，这样就不需要选取罚因子。 在s q p 滤子方法中，用含非线性互补函数( n c p 函数) 等式来表示k k t 条件 中的互补性质，这样将会影响算法的收敛性质和计算效果。之前的滤子通常是数 对组成：即一个是目标函数，另个是约束违反度函数。在本文里将构造出一种 新的滤子，把n c p 函数范数代替约束违反度函数，使得到的点列在趋于可行域的 同时趋于满足互补性条件，增加了一个新的目标，即拉格朗日函数范数，使滤子 中元素由一个数对变为了一个三维的点。而滤子的进入条件也将有所改变。此外， 还将对于滤子中点的个数加以限制，以使新的点更容易取得，减少恢复性阶段的 使用。由此可以得到一个新的s q p 滤子算法。本文将会给出这种算法的全局收敛 性证明和部分数值结果。 对于一个有约束的非线性规划问题，滤子结合逐步二次规划的方法在许多方 面有其优势。因此，如果能很好地对它进行改进，使它在收敛速度，应用范围， 计算存储量等各方面更完善，这样的算法就具有实际意义了。 本文结构安排如下：第一章，我们将给出相关背景和研究现状；第二章给出 一些数学概念和结论，包括信赖域方法、最优性条件和s q p 方法等；第三章中给 出了具体的滤子构造和收敛性证明：该算法的算例和数值结果将在随后的第四章 给出。 关键词：逐步二次规划，滤子， 非线性互补。 上海大学硕士学位论文 a b s t i 认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 gp r o b l e m ( n l p ) i sa ni m p o r t a n tr e s e a r c h t o p i ci no 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 趾b es u m m a r i z e d 鼬t h e c 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 gp r o b l e m s i th a sm a n yp r a c t i c a la p p l i e dm e r i t s ：i n a p p l i e dm a t h , w ec a l la p p l y i tt ot h ef i e l d so fc o n s t r a i n e ds i m u l a t i o na n do p t i m i z a t i o n c o n t r o l ；i np h y s i c s ，i tc a nb ea p p l i e dt oo p t i c sa n dh y d r o d y n a m i c s ；i ta l s oc a nb ea p p l i e d t ot h ef i e l d so fc h e m i s t r y 、e n g i n e e r i n g 、c o m p u t e rs c i e n c ea n ds oo n f r o mt h e s ew ec a l l s e et h ei m p o r t a n c eo fi t u pt ol a t e r19 7 0 s ，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 ) i s o n eo ft h em o s tf a m i l i a ra n de f f e c t i v em e t h o d st os o l v en o n l i n e a rp r o g r a m m i n g p r o b l e m s i n19 9 8 ，r f l e t c h e ra n ds l e y f f e rp r o p o s e dan e wt h o u g h t ，t h a ti st o c o m b i n et h ef i l t e ra n dt r u s tr e g i o ns q p , a n dn e e dn o tt oc h o o s et h ep e n a l t yf a c t o r s i nt h i sp a p e r , w ew i l lc h a n g et h ec o n s t r u c t i o no ft h ef i l t e r t h ed i m e n s i o no ft h e p o i n ti nt h ef i l t e rw i l lb ec h a n g e df r o mt w ot ot h r e e i tw i l lb ee a s i e rf o r t h en e wp o i n t t oe n t e rt h ef i l t e r w ec a nr e d u c et h ep o s s i b i l i t yo fu s i n gr e s t o r a t i o np h a s ea n dc u td o w n t h ed e g r e eo f t h ec i r c l ei nt h ec o u r s eo fs o c n e v e r t h e l e s s ，t h ec h a n g eo f f i l t e rw i l la l s o r e s u l ti naf e wp r o b l e m s f o re x a m p l e ，a f t e rr e l e a s i n gt h ec o n d i t i o n ，i tw o u l de n l a r g e t h eq u a n t i t yo ft h ep o i n t si nt h ef i l t e r , w h i c hr e n d e rt h em e m o r yo ft h ec o m p u t e r o v e r l a r g ei nt h ep r o c e s so p e r a t i o n h e n c e ，w ec o u l dr e s t r i c tt h eu n i t so ft h ep o i n t si nt h e f i l t e r t h i st e x tw i l lc o m et ot h ec o n c l u s i o no ft h eg l o b a lc o n v e r g e n tp r o o fo ft h i s a l g o r i t h ma n ds o m en u m e r i c a lr e s u l t s i nt h ef i r s tc h a p t e r , w ew i l lg i v et h eb a c kg r o u n d i nt h es e c o n dc h a p t e r , w ew i l l g i v es o m er e l a t i v ec o n c e p t sa n dc o n c l u s i o n s ，i n c l u d i n gt r u s tr e g i o na l g o r i t h m ，s q p a l g o r i t h ma n do p t i m i z a t i o nc o n d i t i o n i nc h a p t e rt h r e e ，o n en e w m e t h o do fc o n s t r u c t i n g f i l t e ri si n t r o d u c e d t h en u m e r i c a lr e s u l t so ft h ea l g o r i t h mw i l lb eg i v e ni nt h ef o u r t h c h a p t e r k e y w o r d s ： s q p ,f i l t e r , n c pf u n c t i o n 一v 1 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研 究工作，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已发表或撰写过的研究成果参与同一工作的其他同 志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名： 磐力 日期：妒乒多 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定， 即：学校有权保留论文及送交论文复印件，允许论文被查阅 和借阅；学校可以公布论文的全部或部分内容 ( 保密的论文解密后应遵守此规定) 签名： 菇力导师签名：蝌日期：细a 占帕 上海大学硕士学位论文 第一章引言 1 1 研究背景 当今世界，随着科学技术的飞速发展，运筹学不论在人们的日常生活中，还 是在各行各业中都有广泛地应用。其中，最优化方法作为运筹学中最重要的部分 之一，其作用同样是不可或缺的。在现实生活中，人们碰到的很多涉及到最优化 的问题都是非线性的，而且是在一定约束条件下的。这样的问题可写成( n l p ) m i n 厂( 力 ( 1 1 1 ) s 1 h ( 曲= 0 ， g ( 曲0 ( 1 1 2 ) ( 1 1 3 ) 这里， ：r ”。月，x e r ”，日( 工) = ( 扛( 功，吃( 力，一( 功) ：彤一只p ， g ( 力= ( g ( 力，( n ，晶( 力) ：足”一r ”。 本文所讨论的就是一种改进后的解决约束非线性规划问题的一种有效方法。 1 2 相关问题的研究现状 在约束非线性规划中，滤子的概念最早是由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 方法不论是l s q p ( 线搜索s q p 方法) 还是t s q p ( 信赖域s o p 方法) ， 都需要选择某一合适的罚函数作为价值函数。使用罚函数法会在选择罚参数时仍 然碰到许多困难，通常罚因子需要有界，这个界值很难确定，界太小会使迭代步 迭代至不可行点；界太大会削弱了目标函数对迭代步的影响，从而导致当可行域 边界是曲边时，收敛的速度变的很慢。为了避免罚参数带来的困难，在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 ) 。这种思 上海大学硕士学位论文 想是把目标函数和约束违反度函数分开处理，如果某个迭代步使得要么目标函数 下降，要么约束违反度函数下降，那么就接受这一步，并放入滤子里。最近一些 年，实践中证明s q p 滤子方法在解决变量或约束条件较多的规划问题时是非常有 效的。但是，随着问题规模的变大，s o p 滤子方法的运算量会变得非常大。因此， 对于这一类算法的改进在近些年比较受关注。与之相关的文章也层出不穷，如 1 2 、 2 0 、 2 1 、 2 3 、 4 2 、 4 3 等。 1 3 本文的工作 我们知道，对于k k t 条件中的互补性质，可以用含非线性互补函数( n c p 函数) 等式来表示，这种方法能够被应用到s q p 滤子方法中来。改变滤子的构造 将会影响算法的收敛性质和计算效果。之前的滤子通常是数对组成：即一个是目 标函数，另一个是约束违反度函数，我们若把它看作一个多目标规划，则有两个 目标。在本文里将构造出一种新的滤子，把n c p 函数范数代替约束违反度函数， 使得到的点列在趋于可行域的同时趋于满足互补性条件，增加了一个新的目标， 即拉格朗日函数范数，使滤子中元素由一个数对变为了一个三维的点。而滤子的 进入条件也将有所改变。此外，还将对于滤子中点的个数加以限制，以使新的点 更容易取得，减少恢复性阶段的使用。 在此基础上给出一个新的s q p 滤子算法，讨论算法的收敛性和收敛率，并用 数值例子说明算法的有效性。 上海大学硕士学位论文 第二章数学工具和方法 本文讨论的是关于解约束非线性规划问题的方法。其中用到了信赖域、逐步 二次规划、滤子等概念。下面介绍下这几种工具和方法。 2 i 约束非线性规划的概念 在约束非线性优化问题中，厂( 力及q ( 功( i = l ，m ) 都是定义在r 4 上的实值 连续函数，且至少有一个是非线性的。m 是一正整数，他是介于0 和m 之间的整 数。f ( x ) 被称为目标函数，c f ( 功( i = 1 ，m ) 被称为约束函数。 ( 1 1 2 ) 和( 1 1 3 ) 称为约束条件。满足约束条件的点称为可行点，所有可行 点的集合称为可行域，记为d 。 显然 d = x l h i ( x ) = o , i = l ，p ；髟( 工) 0 = 1 ，小) 。 ( 2 1 1 ) 利用( 2 1 1 ) ，可将问题( 1 1 1 ) ( 1 1 3 ) 写成如下形式： m 瑚i n 厂( 工) ( 2 1 2 ) 当p = m = 0 时，问题( 1 1 1 ) ( 1 1 3 ) 是无约束优化问题，否则是约束优化问 题。在约束优化问题中，如果只有等式约束，即p 0 ，m = 0 ，则称为等式约束优 化问题。另一种特殊情况是所有的约束函数都是线性函数，这时称问题( 1 1 1 ) ( 1 1 3 ) 是线性约束优化问题。 定义2 1 1 设x 。d ，如果对某一万 0 有 ( 功f ( x ) ，x dc 3 b ( x , 回 x ) ， ( 2 1 3 ) 则称x 是问题( 1 1 1 ) ( 1 1 3 ) 的局部极小值，其中 曰( z ，万) = 叫l k 一工+ 9 ：s 万) 。 ( 2 1 4 ) 如果( 2 1 3 ) 式对严格不等号“ 成立，则称石是局部严格极小值。 定义2 1 2 设x + d ，如果 上海大学硕士学位论文 f ( x ) f ( x ) ，x e d z 。) ， ( 2 1 5 ) 则称x 是问题( 1 1 1 ) ( 1 1 3 ) 的全局极小值。如果( 2 1 5 ) 式对严格不等 号“ 成立，则称x 是全局严格极小值。全局极小值也被称为总体极小值。从 定义可知，全局( 严格) 极小值必定是局部( 严格) 极小值 定义2 1 3 对任何工足4 ，称集合 彳( 力= e u i ( x ) ( 2 1 6 ) 是在z 点的积极集合，其中e = 1 ，2 ，p ) ，1 = 1 9o , ，m ) 以及 ，( z ) = u i 白( x ) = o j f ，) 。 ( 2 1 7 ) 我们称岛( 功( ，彳( x ) ) 是在x 点的积极约束，称g ，( x ) ( 仨么( x ) ) 是在工点的非 积极约束。对于给定的石。e d ，在一般情况下，集合d n 曰( x ，万) 扛) 中有无穷 多个点。所以，通过验证( 2 1 3 ) 来判断工是否是优化问题( 1 1 1 ) ( 1 1 3 ) 的解几乎是不可能的。最优性条件就是在一定条件下和( 2 1 3 ) 等价的条件，这 些条件仅依赖于目标函数和约束函数在x 。点的性质。 i 2 2 2 信赖域方法佰颗域万法 信赖域方法是一种新的保证算法总体收敛的方法，它不仅可以用来代替一维 搜索，而且也可以解决h e s s e 矩阵不正定和为鞍点等困难。这种方法首先选择 一个缩短了的步长，然后利用挖维二次模型选择搜索方向。即先确定一个步长上 界吃，并由此定义吒的邻域q 。， q 。- - x l l l x x , l l o ，嗄一o ) ( 2 3 1 ) 为d 在x 处的序列可行方向集合；如果d y ，则称d 是d 在工+ 处的序列可行 方向。 定义2 3 2 设x d ，称集合 甲= d p r v 以( x ) = 0 ，f e ；d r ) o ，j 如) ( 2 3 2 ) 为d 在x 处的线性化可行方向集合；如果d 、王，则称d 是d 在x 处的线性化 可行方向。 引理2 3 1 如果所有的约束函数都在石e d 处可微，则有互、王，。 但是反过来，一般不成立甲y 。因此，要使甲= 缈，需对约束附加条 件，称任何一个保证甲= 吵成立的条件为约束规格( c o n s t r a i n tq u a l i f i c a t i o n ) 。 定义2 3 3 厂( 曲在工处的下降方向集合为 d = p 矿v f ( x + ) 0 ( 2 3 3 ) 定理2 3 1 如果z 为问题( 1 1 1 ) ( 1 1 3 ) 的局部极小点，则 缈r 、d = ( 2 3 4 ) 定理2 3 1 表示，在最优解处不存在下降可行方向。这在直观上是显然的， 但极小点的这一特征是很难检验的。为了得到更好的最优性条件，需要对问题作 一些假定。如果在j 点处 上海大学硕士学位论文 y nd = 甲nd ( 2 3 5 ) 成立，则称问题( 1 1 1 ) ( 1 1 3 ) 满足正规性假定。显然，在约束规范下正规性 假定( 2 3 5 ) 恒成立，但正规性假定比约束规格要弱一些。 定理2 3 2 ( k u h n - - t u c k e r 必要条件) 设工为问题( 1 1 1 ) ( 1 1 3 ) 的一个局 部最优解，厂( 石) ，鸟( x ) ( f z e ) 和g ，( x ) ( 歹，) 在x 的某个邻域内一阶连续可微，又 设正规性假定( 2 3 5 ) 成立，则必存在向量国= ( 西，) t = ( 耳，以) r 使 得2 w ( ，) + 羔西v 吃( ，) + 羔巧( ，) ：o ( 2 3 6 ) i = 1 j = l 彳0 , i i ( 2 3 7 ) g g ，o ) = o , i 6 1 ( 2 3 8 ) 成立。条件( 2 3 6 ) ( 2 3 8 ) 称为k u l m - - t u c k e r 条件，满足该条件的点x 称为 k u h n - - t u c k e r 点( 简称k t 条件与k t 点) ，而( ，国，) r 称为k t 对，它是一个 n + p + m 维向量。 因此，在正规性假定下，最优解必定为k t 点。若正规性假定不成立，则局 部极小点不一定是k t 点。 又因为k a r u s h ( 1 9 3 9 ) 也类似地考虑了约束优化的最优性条件，所以也有 人将上述定理称为k a r u s h - - k u h n - - t u c k c r 定理，把k t 点称为k k t 点。 与( 2 3 6 ) 式有密切关系的一个函数是 p 肘 l ( x ，彩，名) = ( z ) + o a t h 心) + 2 y g ( z ) ， ( 2 3 9 ) i = l = l 它被称为问题( 1 1 1 ) ( 1 1 3 ) 的l a g r a n g e 函数，于是k k t 条件的第一式可以 写成： v ，( x ，缈，五) - - 0 ， ( 2 3 1 0 ) 而向量缈，五称为l a g r a n g e 乘子。 条件巧g ，( x ) = o ( ，) 称为互补松弛条件，它表明，t ；- 与g ，( 工) 不能同时不 6 上海大学硕士学位论文 等于0 ，或者等价地，非积极约束的l a g r a n g e 乘子为0 。但是笱与毋( 石) 有可能 同时为0 ，即积极约束的l a g r a n g e 乘子可能为0 ，如果所有积极约束的l a g r a n g e 乘子均不为0 ，则称严格互补松弛条件成立。在一些算法的理论分析中，常常需 要作这样的假定。 m a n g a s a r i a n 和f r o m o w i t z ( 1 9 6 7 ) 提出另一个约束规格条件( 简称m f c q ) ： v h , ( x ) o e ) 线性无关， ( 2 3 1 1 ) s pv f ( x ) 0 ， v d g ， ( 2 3 2 0 ) 则x 为问题( 1 1 1 ) ( 1 1 3 ) 的一个局部严格极小点。 2 4s q p 和滤子的相关概念 由于q p ( 二次规划) 问题的成功解决，就想到在当前迭代点x 。处，利用目 标函数的二次近似和约束函数的线性近似构成一个二次规划。通过求解这个二次 规划得到下一个迭代点以+ 。这种将求解非线性规划问题转化为求解一系列q p 子问题的方法，称为s 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 最早 由h a n 在1 9 7 6 年提出，随后由p o w e l l 发展的w h p 算法可谓是最早的s q p 算法 了。从此，s q p 方法就发展并流行了起来。 上海大学硕士学位论文 s q p 主要有两类：基于线性搜索的l s q p 和基于信赖域框架的t s q p 。 l s q p 通过求解( 1 1 1 ) ( 1 1 3 ) 的二次规划子问题： m i 玎町( t ) r d + 三d r 取d s t 曩( ) + v 红( 吒) r d = oo = l ，p ) g j ( x k ) + ( ) r d o ( = 1 ，m ) ( 2 4 1 ) ( 2 4 2 ) ( 2 4 3 ) 其中b i r “4 为l a 笋柚g e 函数的h e s s e 阵近似。记( 1 1 1 ) ( 1 1 3 ) 的解为以， 逐步二次规划以畋作搜索方向，记q ，五为对应的l a g r a n g e 乘子。 d 。的一个很好的性质是：它是许多罚函数( 价值函数) 的下降方向。如对 于厶精确罚函数 p ( 工，仃) ：( 功+ 研圭限( 工) f + 芝i g ，( z ) 一i 】 ( 2 4 4 ) i = l s = l 其中g s ( x ) 一= m a ) 【 o ，毋o ) ) ，d 。就是上述罚函数在巩处的下降方向。 下面是h a n ( 1 9 7 6 ) 年提出的逐步二次规划算法。 s t e p l ：给出r ”， 盯 0 ， 万 0 ，骂r ”“，占1 ，k - - 1 。 s t e p 2 ：求解( 1 1 1 ) ( 1 1 3 ) ，得出喀如果i i 以1 1 - 0 ， 从而不能直接利用b f g s 方法。p o w e l l 建议： 上海大学硕士学位论文 一f 以 y t s k 10 2 s t b k s k 败2 t 幺儿+ ( 1 一幺) 最瓯 其他 其中 幺= 卷 则 嘶鬻s l + 再yb k s ks ； t s q p 与l s q p 稍有不同，就是限制了d 。的范数不能超过其每步给定的信赖 域半径r k ，该子问题如下： m i n v 厂( ) r d + 去d r 壤d ( 2 4 5 ) s t 红( ) + v v ( ) d = oo = l ，p ) ( 2 4 6 ) g j ( x k ) + v g r ( x k ) d 0 ( _ = 1 ，1 ) ( 2 4 7 ) 0 d i l ( 2 4 8 ) 下面是s q p 的收敛性定理。 定理2 4 1 假定厂( 力，吃( 功与g j ( x ) 连续可微，存在常数m ，m 0 使得 m l l d l l ：d r b , a _ u l l d l l 三对一切七和d 彤都成立。如果五电盯对一切七都成 立，则算法产生的点列 五) 的任何聚点都是( n l p ) 的k k t 点。 利用二次规划子问题的解畋作为搜索方向在一定条件下，比如 鼠) 正定， 乘子有界，a 。= 1 是一个超线性收敛步。需要注意的是：s q p 与线搜索或信赖域 结合在一定条件下才会全局收敛。 s q p 方法虽具有全局收敛性，但是不论l s q p 还是t s q p 都需要选择某一合 适的罚函数作为价值函数。罚函数法的使用会因为罚因子的选取给运算带来许多 困难，通常要求罚因子有界，这个界值很难确定。界太小会使得迭代点迭代至不 可行点；界太大会削弱目标函数f ( x ) 对迭代步的影响，从而导致当可行域边界 是曲边时，收敛的速度变得很慢。为了克服因罚因子的选取所带来的困难， 上海大学硕士学位论文 f l e t c h e r 和l e 妒陆等人提出了滤子的概念，结合滤子的s q p 方法也应运而生。 下一章将详细介绍滤子的概念，并提出一种新的滤子s q p 算法并给出它的全局 收敛性证明。 接下来讨论与二次规划子问题有关的m a r o t o s 效应及二阶校正步( s o c ) 问 题。 所谓m a r a t o s 效应是指：不管x k 离，多么接近，吼= 1 都不可能成立，从而 破坏了算法的超线性收敛性。目前己知m a r a t o s 效应是由于价值函数的非光滑引 起的。 克 艮m a r a t o s 效应的方法是引进一个二阶校正步( s o t ) ，二阶校正步是下述 问题 的解： m i n g k l r d + 盈d ( 2 4 9 ) s t 鸭( 吒) + v 鸟( ) r d = o ( f = 1 ，p ) ( 2 4 1 0 ) 白( 气) + v g , ( 气) r d o ( 歹= 1 ，m ) ( 2 4 1 1 ) 其中： 磊= 盯( ) + 三喜( q v 吃( ) 一v 曩( + 畋) 】+ 三芸( 五( 气) 一踞，( 五+ 畋) 】 q ，五是二次规划( 2 4 1 ) ( 2 4 3 ) 的l a g ：r a n g e 乘子。记( 2 4 9 ) ( 2 4 1 1 ) 的 解为d 。，在一定条件下可以证明下列超线性收敛结果： jo， 且当充分接近x 时，新点气+ 噍+ d k 可以被价值函数接受。 还可以用下面问题求解一个二阶校正步： m i n v f ( x k ) r j + 耖鼠d s t 曩( + 畋) + v 矽( ) ( d 一畋) = o i e 毋( 气+ 畋) + v g ；( 吒) 似一喀) o 歹j ( 2 4 1 2 ) ( 2 4 1 3 ) ( 2 4 1 4 ) 上海大学硕士学位论文 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 。这种 带滤子的t s q p 不需要用罚函数作为价值函数，这样可以避免由于罚参数选择而带 来的困难。滤子思想类似于多目标优化的思想，即允许一个迭代步被滤子接受当 且仅当目标函数值下降或约束违反度函数值下降。考虑非线性规划形式如下： r a i n 厂( x ) s f c ，( 曲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 在 3 1 中给出 了滤子t s q p 的的全局收敛性的证明，但对 1 9 中的算法有所改进，它证明了两类 信赖域的滤子s q p 算法，第一类算法是把每个迭代步分解成两步，且p n o r m a l 步 与t a n g e n t i a l 步之和；即把求解信赖域子问题 m i n v f ( x , ) r d + 昙d7 反d ( 2 4 15 ) s j c a x ) + 4 ( 工) r d = 0 ( 2 4 1 6 ) c ，( x ) + 4 ( 功，d 0 ( 2 4 1 7 ) i l d f 肾a 。 ( 2 4 1 8 ) ( 其中以为当前迭代点，a 。为第七步迭代时的信赖域半径) 分为两步来做，设么为 ( 2 4 1 5 ) 一( 2 4 1 8 ) 的解，把喀分解为吐= n k + ，其中满足以下式子： s t c a x ) + 4 ( 功r = 0 和 q ( 曲+ 4 ( 力r 俾0 i | l 区a 。 忆临a t s 0 t a x ) + 4 ( 功r d = 0 c ，( 工) + 4 ( x ) ，d o 上海大学硕士学位论文 事实上，是使+ 满足信赖域子问题的约束条件：气使为了使目标函数充分 下降。 3 1 这篇文章中证明了满足条件的体和气是可以找到的。第二类算法就直 接求解( 2 4 1 5 ) 一( 2 4 1 8 ) 得到畋。 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 函数 l ( x ，y ) = ( 工) + y r c ( 功 ( 其中y = ( 儿r ，乃r ) r ”，乃0 ) 来代替 3 1 中的厂( 力，用 o ( x ，y ) 爿ic ( x ) 1 1 2 2 + i ic j + ( z ) 1 1 2 2 + ( 乃r q + ( 工) ) 2 来代替 3 1 中的 ( c ( x ) ) ，即用( o ( x ，y ) ，( 工，y ) ) 来代替而构成滤子。伴随这个主要 的修改，对 3 1 中滤子t s o p 算法的其它地方也做了相应的修改。 4 2 证明了这种 修改的算法的全局收敛性，并且这个修改的滤子t s q p 算法不需要计算二阶校正步 ( s o c ) 也可避免m a r a t o s 效应，具有超线性收敛性，全局收敛性的证明的技巧与 2 0 中类似。2 0 0 3 年，s u l b r i c h 和m u l b r i c h 在 4 3 中提出了一种非单调的滤子t s q p 算法，与 4 2 中类同的使用( o ( x ，y ) ，l ( x ，少) ) 做为滤子的元素，求解等式约束非线 性规划问题： m i l l j r ( 工) ( 2 4 1 9 ) s f c a x ) = o ( 2 4 2 0 ) 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 9 3 是滤子信赖域s q p 方法。事实上，滤子也可以 和l i n e s e a r c h ( 线性搜索技术) 相结合来求解一个非线性规划问题。 以上无论是传统的s q p 还是滤子s q p 在求解非线性规划问题时，每次迭代都需 要求解一个或几个二次规划( q p ) 子问题。当疗( z 的维数) 增加时，整个算法在迭 代过程的计算量的增加非常快。为了解决这一问题，有人提出了用线性规划( l p ) 来代替二次规划( q p ) ，而对与同样维数的x ，l p 的计算量较q p 的计算量小的 1 3 上海大学硕士学位论文 多。 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 在 2 3 中提出了一种s l p 滤子算 法并证明了其收敛性，即带滤子的序列线性规划，可以避免使用罚函数。 2 3 中也是考虑非线性规划问题( 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 q p ，即 每次求解一个线性规划( l p ) ，设为当前迭代点， m i nw c x a r d ( 2 4 2 1 ) s