（运筹学与控制论专业论文）非线性优化问题的精确罚函数算法研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 非线性约束优化问题是最一般形式的非线性规划问题，也是优化研究中的难 点。因此，了解和掌握求解非线性规划问题的方法无疑是非常重要的。近年来， 人们通过对非线性规划问题的研究，提出了解决此类问题的方法：罚函数法( 内点、 外点、混合1 ，可行点法，乘子法，广义简约梯度法以及序列二次规划( s e q u e n t i a l q u a d r a t i cp r o g r a m m i n g 常简写为s q p ) 方法。这几种方法通常存在计算量大、收敛 速度慢以及参数敏感等不足之处。为了解决这些问题，本文在结合现有研究，讨 论了双参数精确罚函数，在此基础上提出了新的解决此类问题的方法：双参数精 确罚函数法。 本文粗略的回顾了非线性约束优化问题的研究发展历史，重点阐述和分析了 罚函数法的发展及其现状；出于后面使用方便，对无约束优化问题的拟牛顿法进 行了必要的阐述。在此基础上，提出了一种新精确罚函数和相关定理，并详细的 论证了用精确罚函数法解决非线性约束优化问题的可行性；在此基础上进一步构 造出一类双参数精确罚函数，讨论了这类双参数精确罚函数的性质，给出了一个 用双参数精确罚函数求解非线性约束优化问题的算法。最后，与无约束优化问题 的解决方法相结合，提出了用布鲁丹族拟牛顿算法来求解这类问题的子算法。最 后通过理论和经验的对比，找到了一种新的行之有效的解决非线性约束优化问题 的算法，通过算例证明，这种方法是行之有效的。与传统的罚函数方法相比，在 解的收敛性上更优。 本文的主要成果是：构造出双参数精确罚函数的非线性约束优化问题 模型，提出了一个拟牛顿算法来求解这个模型。 本文对于一般非线性约束优化问题的求解具有重要的理论意义，同时也给出 了一个新的关于精确罚函数的研究的方向。 关键词：非线性约束优化，精确罚定理、双参数精确罚函数，拟牛顿算法。 重庆大学硕士学位论文 英文摘要 a b s t r a c t n o n l i n e a rc 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 sa r et h em o s tc h a l l e n g e ds u b j e c t si n m a t h e m a t i c a lp r o g r a m m i n g i t sv e r yi m p o r t a n tt os e i z et h em e t h o do fn o n l i n e a r c o n s t r a i n e d o p t i m i z a t i o np r o b l e m s r e c e n t l y , s m d e n th a v e a d v a n c e dm a n yn e w m e t h o d st os o l v ei t ，s u c h 嬲p e n a l t yf u n c t i o n s ，f e a s i b l ep o i n tm e t h o d ，m u l t i p l i e rm e t h o d a n ds 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 h o w e v e r , t h ea m o u n to fc a l c u l a t i o n , t h es p e e d o ft h ec o n v e r g e n c ea n dt h es e n s i t i v i t yo fp a r a m e t e r so ft h e s ea l g o r i t h r n sa r el e s s e n c o u r a g e d i nt h ep r e s e n tp a p e r , w ei n v e s t i g a t e dh o wt oa p p l yt h ea l g o r i t h mt ot h e o p t i m i z a t i o np r o b l e m sw i t he x a c tp e n a l t yf u n c t i o nw i t ht w o p a r a m e t e ra f t e rw ea p p l ya n e wt h e o r e mo f p e n a l t yf u n c t i o n f i r s t l y , w ei n t r o d u c e d t h er e s e a r c hc o n d i t i o no ft h en o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s s e c o n d l y , a f t e ra p p l i e dan e wt h e o r e mo fp e n a l t yf u n c t i o n ，w e d i s c n s s e dt h e p r o p e r t y o ft h e p e n a l t y f u n c t i o nt os o l v en o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s o nt h i sb a s e ，w ec o n s t r u c t e das e r i e so fe x a c tp e n a l t yf u n c t i o n w i t ht w o p a r a m e t e r s ，d i s c u s s e dt h et h e o r e ma n da p p l i e dat h e o r e mo fs o l v i n g n o n l i n e a rc 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 s f i n a l l y , i n t e g r a t e dw i t ht h et h e o r e mo f u n c 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 s ，w ea p p l i e da n e wq u a s in e w t o na l g o r i t h mo fp e n a l t yf u n c t i o nw i t l lt w o p a r a m e t e r c o m p a r et ot h e t r a d i t i o n a la l g o r i t h mt os l a v et h en o n l i n e a rc 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 s ，t h en e w a l g o r i t h mi sm o r ee x c e l l e n ti nt h es p e e do ft h ec o n v e r g e n c ea n dt h ea s t r i n g e n c yo f s o l v e m a i nf r u i ti sb u i l d i n gam o d e lo f n o n l i n e a rc 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 sw i t h e x a c tp e n a l t yf u n c t i o nw i t ht w o p a r a m e t e r s ，a p p l y i n gan e wq u a s in e w t o na l g o r i t h mt o s o l v e t h i st e x th a st h ei m p o r t a n tt h e o r ym e a n i n gf o rt h es o l v et h en o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s k e yw o r d s ：n o n l i n e a rc 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 s ，t h e o r e mo fp e n a l t yf u n c t i o n ， e x a c tp e n a l t yf u n c t i o nw i t ht w o - p a r a m e t e r , q u a s in e w t o na l g o r i t h m 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导f 进行的研究工作及取 得的研究成果。据我所知，除了文中特, n 力1 1 以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：残熟入水众签字日期：2 叼年臼伊日 学位论文版权使用授权书 本学位论文作者完全了解重庆盍堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庆太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、。 ( 请只在上述一个括号内打“”) 学位论文作者签名：磊匦犬术么导师签名：叶钟泉 签字日期：2 叼年f 月，日签字日期：加7 年莎月g 日 重庆大学硕士学位论文i 绪论 1 绪论 1 1 引言 非线性约束优化问题是最一般形式的优化问题。由于实际中所遇到的大多数 优化问题都是带有约束，因此，了解和掌握求解一般非线性优化问题的方法无疑 是非常重要的。从这类问题的提出开始，人们已经提出了多种多样、可用来求解 不同形式非线性约束优化问题的方法：如罚函数法( 包括内点、外点、混合) ，可行 点法，乘子法，广义简约梯度法以及序列二次规划( s 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 常简写为s q p ) 方法等等。本章我们将概略回顾一下非线性规划问题 的研究发展过程，在此基础上重点回顾和介绍罚函数法的研究现状。 1 2 非线性规划问题的研究发展过程 一般的非线性约束优化问题可表示为下面的形式： o 哪 m 。i n 。 厂( 力( 1 1 ) j j c f ( 工) = 0 ，f i = 1 ，2 ，- ，m ( i 2 ) c ，( z ) 0 ， j j = 1 , 2 ，n ( 1 3 ) 其中厂( 曲和q ( 功及c ，( x ) ( 1 i m ，1 j ，1 ) 均是定义在r ”或其某个子域上 的实值函数，r c ，( x ) 及c ，( 工) 中至少有一个是非线性的，m ，n 为有限正整数，有 限集合，和，分别表示等式约束和不等式约束的指标集合。 求解问题( n p l 的算法，按照发展的时间顺序和不同的设计思路，可以大致分为 以下四类。 早期的直接法。包括网格法、随机试验法和复形法。其主要思路是：用求 解无约束优化问题的各种直接方法推广到求解般的非线性约束优化问题。这类方 法对原问题不需要作任何的预处理，在按照某种方式选定了一组测试点或规定了 产生了新的测试点的方法之后，这种方法所需的仅是计算目标和约束的函数值。 因此，这类方法一般都计算简单、直观性强，对问题中的函数无任何特殊的要求， 其缺点是计算量大、算法无好的理论依据，往往只能找到问题的一个较好的可行 解，即使在特殊情况下能保证算法的收敛性，其收敛速度也只能是线性的。所以， 只要不是没有其它的算法可利用，一般不用这类方法。但是，在下面这两种情况 下，这类方法还是很有价值的：一是如果问题中的函数很复杂，性态很差，甚至 难于给出解析表达式；二是对解的精度要求不高。 线性约束问题的算法在非线性约束问题上的推广。包括广义消去法、可行 方向法、广义简约梯度法和投影梯度法等。其主要思路是：对原约束优化问题不 重庆大学硕士学位论文 1 绪论 预先作转换，直接用线性约束问题的算法进行处理。因此，这类方法所产生的迭 代点均是问题的可行点。但是，由于约束函数的非线性性，这些方法的具体实现 要比在线性约束上复杂的多，且有效性也没那么好。以求解等式约束( 1 1 ) 及( 1 2 ) 的广义消去法为例，每次迭代都需要解一个非线性方程组，且简约变量的构成在 每次迭代时都在发生变化。对于其它的方法，为保证迭代点列的可行性，必须确 定出当前迭代点出的可行下降方向，由于约束的非线性性，此时的可行方向不再 是简单的直线，而是曲线形式的可行弧，且非线性约束不允许通过线性搜索来保 持可行性，因为准确的可行弧实际中无法确定，因此要找到问题( n p ) 的可行方向， 需要进行牛顿迭代使其回到可行域。这样，不仅使算法收敛得很慢，迭代点列的 轨迹象滚花边一样在约束区域的边界面上移动，这就导致了这些方法推广到非线 性约束问题时效果很差。总之，这类方法的主要优点是它保持迭代点列的可行性， 并通常可找到问题的局部最优解，其缺点是有关算法的实现往往很复杂、计算量 比较大，且收敛速度通常只能达到线性收敛。故一般而言，对于非线性约束问题， 这类方法不是有效的算法。但有一个例外，即广义简约梯度法，该算法可以降低 问题的维数，在其迭代的后期可用拟牛顿法来加速收敛。 罚函数法。其主要思路是：把非线性约束优化问题转化为无线性优化约束 问题。依据如何将目标函数和约束函数进行组合，人们导出了许多不同形式的罚 函数。由于这些早期方法均需要求解一系列无约束的罚函数极小化问题，故通常 称之为序列无约束极小化方法( s e q u e n t i a lu n c o n s t r a i n e dm i n i m i z a t i o nt e c h n i q u e ) ，简 称s u m t 。依据方法能否保证迭代点列的可行性，可将这些方法分为三类：内点 罚函数法、外点罚函数法以及两者相结合的混合罚函数法。s u m t 类方法的优点 是简单易行，可直接利用无约束优化的算法来求解约束优化问题。在很弱的条件 下即可保证算法的收敛性，且外点罚函数法具有全局收敛性，即它可从任一未必 可行的初始点出发来找到问题的最优解。缺点是这些方法要求解一系列的无约束 优化问题，计算量大且收敛速度慢，更严重的是随着罚参数趋于其极限，这些罚 函数的性态越来越差，这使得很难对其精确求解。为克服这些缺点，人们又提出 另外两种类型的罚函数：一种是精确罚函数，一种是乘子罚函数。精确罚函数的 优点是它的无约束极小点就是原问题的最优解。精确罚函数是在原目标函数上加 一些由约束函数组成的惩罚项而构成的。这类函数通常也含有某个待定的参数， 故实际使用中通常是通过求解若干个由精确罚函数所产生的无约束优化问题，在 确定了参数的适当精确值后，在求一个这样的无约束优化问题的解即可。而乘子 罚函数是在约束问题的拉格朗日函数中增加一个惩罚项而成。其思想是利用约束 问题的近似拉格朗日乘子所提供的信息，在有限次调整罚参数的值后即可使它保 持不变，而在每次迭代中用某一乘子修正公式来对拉格朗日乘子向量进行修正， 2 重庆大学硕士学位论文 1 绪论 通过求解一系列乘子罚函数的无约束极小化问题来找到约束优化问题的最优解， 从而不需要罚因子无限地趋于无穷大或零。由于精确罚函数法和乘子罚函数法相 对于传统罚函数法的上述优点，加上它们问题函数性态的要求也比较低，同时只 要实现方法恰当，就可保证有较好的收敛速度和数值稳定性。因此，这两种方法 一直是求解约束问题( n 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 ) 方法。近年来，为了避免在每个 迭代步直接求解一个乃至多个二次规划子问题，近年来人们发展和研究了基于二 次规划子问题k t 条件导出的线性方程组的序列线性方程组( s e q u e n t i a ls y s t e m so f l i n e a re q u a t i o n s ，简写为s s l e 方法) ，这种方法在求解问题( n p ) 时往往和某种可行 方向法相联系，尽管开始时的标准s q p 方法存在着诸如局部收敛、q p 子问题可能 不可行或无有界解等缺点，但经过人们对其不断进行改进与进一步的发展，现在， s q p 类方法已成为求解非线性约束优化问题的一类最有效的算法。它不仅可以求 解等式约束优化问题，而且很容易处理不等式约束。这类算法不仅具有全局收敛 性，而且具有局部超线性收敛或更强的二次收敛性。 总之，从对求解线性约束优化问题的算法的回顾中我们可以看出：罚函数法 和s q p 法是求解非线性约束优化问题比较好的算法。现在常用的非线性规划算法 大都属于这两类中的某一类。当然，需要注意的是：除了内点罚函数外，这些算 法所产生的迭代点一般不是问题的可行点。由于不能保证迭代点列的可行性，为 了能判断迭代点的好坏，并确保算法的收敛性，以最终求得原约束优化问题的解， 必须建立某种准则来权衡减小目标函数值和满足约束条件这两个互相制约的目 标，这通常是通过定义某个称为效益函数( m e r i tf u n c t i o n ) 的方式来实现的。效益函 数的选择一般应满足这些基本要求：在随着迭代的进行对效益函数不断地极小化 操作后，应最终找到原约束优化问题的一个局部最优解；效益函数在适当的条件 下应能保证算法的全局收敛性；效益函数应容易估值，尽量避免含有参数且应适 当光滑；效益函数不应该影响到算法的收敛速度等。 1 3 罚函数法的研究现状 通过上面的回顾，我们知道罚函数法是解决非线性约束优化问题的一个非常 有效的方法，也是发展非常快和应用最多的一种算法。其核心思想就是找一个容 易求解的替代问题，而这个替代问题的解正好就是原来问题的解。自1 9 4 9 年c o u r a n 重庆大学硕士学位论文 i 绪论 首先提出外点罚函数算法，到现在为止人们已经研究了许多形式的罚函数方 法“” 1 9 - 2 2 】，下面我们简单回顾一下： 1 9 4 9 年c o u r a n 首先提出外点罚函数算法，有效地将带有约束的非线性规划问 题转化为无约束规划问题。对非线性规划问题： ( n p ) r a i n ，( 工) ( 1 4 ) 斑 s q ( 工) = 0 ，i i = 0 , 2 ，m ( 1 5 ) c ，( 石) 0 ，j j = 0 , 2 ，”j ( 1 6 ) 其外点罚函数定义为： ，、4m 卢 p ( 习= m a x 0 ，c 小) + m 划 j = t i = 1 其中，口，口 o 。对应的罚优化问题的( f p ) 为： r a i n f + a p ( x ) j j x r “ 其中口 o 是罚参数。记( f p ) 为p ( x ，口) 一，我们加以分析会知道：对某一充分大的 口，问题p ( x ，口) 的最优解x ( a ) 属于原问题( n p ) 的可行域，则对问题( n _ p ) 任一可行 点工，我们有： 厂( 工( a ) ) = p ( 工( 口) ，口) = m 绑p ( x ，口) p ( x ，口) = ，( 曲 通过这个等式我们发现：只要选取较大的口，就可以通过求解一个无约束优 化问题就可找到约束优化问题的最优解。然而，在实际计算中，确定大小合适的口 比较困难，故通常是选取一个单调增的罚参数序列 吼 ，通过求解一系列的无约 束优化问题来找到约束优化问题的最优解。这就是s u m t 名称的由来。 为保证外点罚函数的收敛性，要求陬寸佃。但是，吼的值很大时，求解罚 函数的无约束极小值往往变得非常困难，原因是罚函数的海森阵会随着a 。不断增 大呈严重的病态特征。为了克服这一病态，我们通常有这两种方法： 一是恰当地选取或确定瓯的变化方式。为了在算法的收敛性和解的精确性之 间取得某种平衡。经验上我们可令= 1 或= m a x ( 1 0 。2 ，l 厂i 1 0 0 ) ，其中厂为约束 极小值的一个估计，然后令吼以某一常数倍c 去增长，c 的通常取法有 6 0 ，4 或 1 0 。 二是考虑到算法的实际执行问题，代之以寻求罚函数的精确无约束极小点， 只满足于找到具有一定精度的近似极小解，且可在适当条件下保证所对应的算法 仍是收敛的。例如( f l e t c h e r , 1 9 9 0 ) 为罚函数提出的终止准则。 为加速罚函数法的收敛，采用所谓的外插技术是很有效的。1 9 9 0 年，f i a c c o 和 m c c o r m i c k 提出：在外点函数法中，给定罚参数a = 二的一个值，就可求得p 二) 4 重庆大学硕士学位论文 1 绪论 的无约束极小点，故该极小点可看作是口或等价的，的函数，记x ( a ) = 工p ) 。当 r 一0 时，z ( 二) 趋向于约束问题的最优解。 由于外点函数法在迭代过程中所产生的近似最优解往往只是近似地满足约束， 一般不可行。对于那些要求严格可行的实际问题，这样的结果无法接受。于是， 在1 9 5 5 年f r i s h 和1 9 5 5 年c a r r o l l 提出了内点罚函数法：考虑非线性规划问题( p ) m 。i n 厂( 工) s a t c ，( 曲0 ，j ，= 1 2 ，m j 注意到任何一个( n p ) 都能转化为( p ) 的形式，其内点罚函数对应的罚优化问题 为： m i n f ( x ) + t b ( x ) s t 工r 4 其中，t 是罚参数，b ( x ) 是关于c i ( x ) 的一个函数，通常取曰( 工) = ! i _ 或 b ( 工) = l i l k ，( 工) i ，若取前者，则称相应的内点罚函数为分( 倒) 数罚函窥箬取后 者相应1 霸内点罚函数为对数罚函数。 对于内点罚函数法，同样有外点函数法所遇到的病态特征，对应的处理方法 也跟外点函数法差不多。需要特别说明的是，内点罚函数法还有两个新问题： 一是初始点的选取。内点罚函数法要求初始点位于可行域的内部。除特殊情 况外，一般很难确定。故与外点函数法不同，其初始点是用一迭代过程来找到的。 二是涉及极小b ( x ，t 。) 的线性搜索，由于内点罚函数不是处处有定义或不一定 存在全局最小，故无约束优化中通常的线性搜索方法不再适用。因此，必须对通 常用的线性搜索方法进行修正，如利用内点罚函数变化奇异性的有关性息来设计 特定的线性搜索过程，或对步长进行适当的控制以免跑出可行域( 见f l e t c h e ra n d m c c a n n ，1 9 6 9 、l a s d o n ，f o xa n dr a t n e r , 1 9 7 3 等) 。总之，不同于外点函数法，内点 罚函数的极小运算通常不是在整个r ”中进行的。 由于内点罚函数法不能处理等式约束，且寻求初始可行内点的计算工作量往 往太大。因此，在实际中，为了求解一般的非线性约束优化问题( n p ) ，人们往往 将内点罚函数和外点罚函数法结合起来使用，这就是我们下面讲的混合罚函数法。 对于( n p ) 我们定义： v ( x , r k ，t i ) = p 时对应的罚优化问题的最优解就 是原问题的最优解。这样，我们只需求解一个罚优化问题就可得到原问题的最优 解。也正因为如此，精确罚函数成为人们解决非线性约束规划问题的重要方法， 并开展了许多研究，如1 9 7 9 年，h a n 和m a n g s r i a n 在文 4 q h 讨论了精确罚函数， 1 9 8 1 年r o s e n b e r g 和l a s s e r r e 分别在文 5 和文【6 】中给出了一个精确罚函数的全局 收敛性算法，1 9 8 2 年c l a r k e 在文【9 】中讨论了精确罚函数的镇定性和稳定性条件， 1 9 8 4 年r o s e n b e r g 也在文 1 0 e e 讨论了精确罚函数的镇定性和稳定性条件，其中镇 定性和稳定性条件又是判断精确性的充分必要条件，但对于复杂问题则无法验证。 d i p p l l o 和g r i p p o 在文 7 - 8 研究了精确罚函数的算法。1 9 9 5 年m o n g e a u 和s a r t e n a e r 在文 1 l 】中对精确罚函数的自动减小问题进行了研究，1 9 9 0 年k o m e r 和f r a n k 研 究了二次规划的精确罚函数的数值算法【1 ”，1 9 8 6 年b e n t a l 和t e b o u l l e 讨论了随机 规划的罚函数问题 1 3 - 1 4 1 1 9 - 2 2 】。1 9 9 5 年韦增欣在文 1 5 研究了一族精确罚函数的存 在性及控制参数的下界。1 9 9 6 年林亮在文【1 6 仲讨论了一种精确罚函数的存在性， 王万量在文 1 7 仲研究了l 1 精确罚函数的存在性，林波艇和张可村研究了用l 1 精确罚函数作线性搜索函数的一种修正约束变尺度算法【1 ”，刘昌文在文【1 9 】讨论了 二次规划的精确罚函数法，1 9 9 7 年张连生在文 2 1 1 d o 给出了全局精确罚函数的一个 充要条件。1 9 9 8 年林蔚在文 2 2 1 中讨论了双层多目标规划的精确罚函数法 1 4 无约束优化问题的发展现状 对无约束优化问题： m i n 厂( 曲 求解的方法主要有最速下降法、牛顿法及其改进和拟牛顿法。这些方法各有 特色，适应面也不尽相同，但它们都是求解无约束优化问题的的最基本、最重要 的算法，无约束优化问题的许多其他求解方法乃至一些无约束优化问题的求解方 法都是以它们为基础发展而来的。下面我们概略地介绍一下这三种方法。 最速下降法是求解无约束优化问题的最简单的方法，设目标函数f ( x ) 连续可 6 重庆大学硕士学位论文 l 绪论 微，且w ( 工) 0 ，将f ( x ) 在x 泰勒展开就得到： 厂( 工耻+ 1 ) = ，( x 似) + c # 可y ( x 耻1 ) 7d 忙+ d ( 0 耐似1 1 ) 上式中，一+ 1 = 工+ 吼，d = x “一v f ( x ”) ，d ”是搜索方向，具体的它是函 数f ( x ) 在点x 处的负梯度方向，即有d = 一v f ( x ) ；是步长由线性搜索策 略确定。这就是最速下降法的基本思想。 最速下降法具有计算工作量小，存储量小，对初始点无特别要求的优点，但 由于d 忙是函数f ( x ) 在点x 似处的负梯度方向，这仅仅是函数的局部性质，对整个 过程而言不一定是最快的。而实际上，在迭代开始的最初几步，f ( x 1 下降的幅度 比较大，但在以后的迭代中，尤其是随着x 仙越来越接近极小点，f ( x ) 下降的越来 越慢，因而，k 耻 的收敛速度较慢。因此，最速下降法比较适用与计算的开始阶 段。至于最速下降法的收敛速度，明显的，由文 2 3 】中定理3 2 7 知这种算法至少 有线性收敛速度。 由于最速下降法只比较适用与计算的开始阶段；而且随着工耻越来越接近极小 点，厂( 工) 下降的越来越慢，因而，扛忙 的收敛速度较慢。为了克服这些缺点，人 们又提出了牛顿法。其基本思想是：在目标函数的极小点工+ 的近似点x 仕附近将 f ( x ) 二阶泰勒展开，用展开的二次函数去逼近f ( x ) ，将这个二次函数的极小点作 为x + 的一个新的近似点x 恤“，用一系列二次函数的极小点b 耻“ 去逼近厂( 工) 的极 小点x 。具体的就是： 设目标函数厂( z ) 二阶连续可微，x 忙是x + 的一个近似点，由泰勒公式有 1 ，( 工) q k ( x ) = ，( 工似) + v f ( x 耻) ，( 工一x 忙) + 去( x x 仕) ，v 2 ，( 工仙) ( 工一工耻) 令 上 v q t ( 功= 0 ，解出工= 工“就是二次函数吼( x ) 的极小点。即 x “1 = x n v 2 f ( x ) 一1 1 盯( x ) ( 1 7 ) 我们将上面得到的x 忙“作为x 的一个新的近似点。 给定石。的初始近似点x 0 后，迭代点列 x 仙 由上面的式子产生，这个式子就 是牛顿迭代公式，相应的算法称为牛顿法。我们由文 2 3 1 中定理3 2 8 知道牛顿法 是局部收敛的，且具有二阶收敛速度。 由于目标函数的极小点x + 是待求的，我们很难检验给定的点工( o 是否靠近x ， 因此，不能保证d 耻是下降方向及扛忙 的收敛性。为了克服这一不足，在牛顿迭 代公式( 即上面的( 1 7 ) 式) 中引进阻尼因子( 即步长) 口。，则迭代公式为： 石+ 1 = 工+ 瑾i d = x 一口t v 2 f ( x ”) 一1 v f ( x )( 1 8 ) 其中，口。由线性搜索策略确定。相对于牛顿法，f l q ( 1 8 ) 式确定的牛顿法称为阻尼 牛顿法。由文【2 3 仲的定理3 2 9 知阻尼牛顿法具有全局收敛性。 阻尼牛顿法克服了牛顿法要求初始点x ( o 充分靠近f ( x ) 的缺点，但只有目标函 7 重庆大学硕士学位论文 1 绪论 数，( 曲的海森阵v 2 f ( x ) 处处正定时，该算法才具有全局收敛性。如果v 2 f ( x ) 不 处处正定，当初始点远离局部极小点时，v 2 f ( x 似) 可能不是正定的，这时v 2 f ( x 似) 可能奇异也可能非奇异。若奇异，求搜索方向的方程组可能无解，或者，虽然有 解，但求出的下降方向不能使迭代过程进行下去；若非奇异，但不正定，则求出 的可能不是下降方向，导致f ( x 耻“) f ( x 啦) 。为了克服这些缺点，人们对阻尼牛 顿法提出了若干改进方法，带保护措施的阻尼牛顿法就是其中最简单的一种。 带保护措施的阻尼牛顿法的主要思想是对下降方向进行修正，即： 设v 。( x ”) 0 若v 2 ( j ) 正定，则d 。= 一v 2 f ( x ) 1 1 w ( x 1 ) 是下降方向。 如果v 2 ( x ) 不正定，但可逆，且v f ( x ) 7 v 2 f ( x ) 1 v f ( x ) 0 时，b + l 才有正定性，而这 个条件很难保证，即使( y “一b 。j ) 7 6 0 ，但若它很小，导致在计算过程中的 数值不稳定，这使得对称秩1 校正公式在实际应用中很受限制。 对称秩2 校正公式。其产生的主要目的就是克服对称秩1 校正公式在迭代 过程中不能保证迭代矩阵的正定性的缺点。 在这里我们不再叙述其推导过程( 详见文 2 3 中定理3 3 2 ) ，只给出具体形式： 占_ 2b k + 南妙”) 一b ) v r + v ( y 忙l b k 8 似) 叫 一芷三型翌型。r ( v 7 6 。) 2 在上面的式子中，取不同v 的，便得到不同的校正公式： 1 ) 令，= y “一b t 6 “，则得对称秩1 校正公式； 9 重庆大学硕士学位论文 1 绪论 2 ) 令1 ，= 6 ”，则得p s b ( 鲍威尔对称布鲁丹公式) ： t2 毋+ 赤抄) ) - 印忙7 椰耻( y t k ) _ ”) 叫 一! ! ! ! = 皇皇生! ：! ：鱼! ：6 t t ，6 t ”r ( 占16 ) 2 3 ) 令v = 葡1 ( y f k j + r h 酽) ，其= ( 篙舞丸艄 b f g s ( b r o y d e n f l e t c h e r g o l d f a r b s h a n n o ) 公式： ”峨+ 筹一筹 4 ) 令v = y “，则得d f p ( d a v i d o n f l e t c h e r p o w e l l ) 公式： ”玩+ 苦爷一生筹篙薯妒圹矿桫垆7 肌排南一斋岛 注意到国咿占= 0 ，故对上式子含7 的项前乘以非负常数庐，便得到一个依 赖于参数的一族校正公式口厶，b 厶满足拟牛顿条件且保持对称性。曰厶表示如 下： 口 + t = b k4 苦等一旦筹瑞孚堋8c ”r b k s k ) 炉 上式称为布鲁丹族拟牛顿校正公式。 在上式中，令= 1 ，即得d 即校正公式。令妒= 0 ，即得b f g s 校正公式，对 比3 ) 和4 ) 我们发现： 乓d + l f p 一一d t b + 1 f g $ + 妒( 6 b i 占”) c o ”矿 即，布鲁丹族拟牛顿校正公式与d f p 校正公式相差一个秩1 矩阵 ( 矿b t j ”) c o ”圹。 由文 2 3 】中定理3 3 4 我们可知，布鲁丹族拟牛顿校正公式磁。是正定的。 若记h k = b i 一，通过文 2 3 1 定理3 3 6 我们发现日厶也是正定的。而且我 们发现关于h k 的布鲁丹族拟牛顿法的优点是，直接由公式d = 一h 。g 幢确定搜 索方向，从而避免了求解关于d 的线性方程组，减少了运算量。在迭代过程中若 由精确线性搜索确定步长，则由b 。是正定的知h k 也是正定的。 在布鲁丹族拟牛顿校正公式中，d f p 校正公式和b f g s 校正公式是两个最著 名的公式。大量的数值试验表明b f g s 校正公式的数值稳定性要优于d f p 校正公 式，而且它与低精度的线性搜索方法相结合使用，能收到较好的计算结果。 我们知道，拟牛顿法具有二次终止性。对于一般的非二次函数拟牛顿法的收 1 0 重庆大学硕士学位论文 1 绪论 敛性和收敛速度，以鲍威尔教授为首的许多科学家在这方面做了大量的研究，取 得了丰硕的成果。最具有代表性的成果是，鲍威尔( p o w e l l ，1 9 7 1 ) 证明了目标函 数， ( x ) 是二阶连续可微的一致凸函数时，采用精确线性搜索的肌p 方法的全局收 敛性及厂( x ) 的海森阵满足利普希茨条件时的超线性收敛性。稍后( 1 9 7 2 ) ，他又在 f ( x ) 为凸函数的较弱假定下，证明了嬲p 算法的全局收敛性。鲍威尔( p o w e l l ， 1 9 7 6 ) 又证明了目标函数厂( 曲是二阶连续可微且有下界的凸函数时，采用沃尔夫准 则的b f g s 方法的全局收敛性和一致凸且海森阵满足利普希茨条件时的超线性收 敛性。伯德，诺赛德尔，袁( b y r d ，n o c e d a l a n d y u a n ，1 9 8 7 ) 将鲍威尔的结果推广 到除了所p 方法以外的所有限制的布鲁丹族算法，证明了对二阶连续可微且有下 界的凸函数，线性搜索采用沃尔夫准则的限制布鲁丹族算法的全局收敛性和f ( x ) 是一致凸函数且海森阵为霍德尔连续条件下的局部超线性收敛性。伯德，诺赛德 尔和刘( b y r d ，n o c e d a l a n dl i u ，1 9 9 0 ) 将超线性收敛的特征条件换成一个等价条 件，给出了一个超线性收敛性定理。 1 5 本文研究内容 研究了一种新的罚函数的精确罚定理，在此基础上构造出一类精确罚函数。 与传统的精确罚函数相比，它多了一个目标罚参数。这种罚函数具有很好的精确 性和可微性。 接着，本文将通过对双参数罚函数的研究，并通过相应的计算来说明这种方 法的优越性。我们的研究主要集中在以下几个方面： 回顾了非线性约束优化问题的研究历史，重点论述了罚函数的研究现状； 同时，为了论述方便，对无约束优化问题的研究也加以回顾。 讨论了一种新的精确罚函数和精确罚定理。 结合非线性约束优化问题，构造了一族双参数精确罚函数，证明了精确罚 定理以及初步给出了双参数精确罚函数算法。 研究了用拟牛顿算法来求解由双参数精确罚函数结合原非线性约束优化 问题所产生的罚优化问题。 下面介绍本文后面各章节的安排： 第2 章提出一种新的罚函数的精确罚定理。并针对这个定理，通过算例来验 证。 第3 章提出了一类新的精确罚函数。对精确罚定理以及双参数精确罚函数的 算法进行了讨论。 第4 章讨论了拟牛顿算法的原理，在此基础上提出了用双参数精确罚函数的 拟牛顿算法作为子算法来求解一般的非线性约束优化问题。 重庆大学硕士学位论文 1 绪论 接下来，我们将本文所做的一些工作进行了总结，并且展望了未来的工作。 最后是参考文献、攻读硕士学位期间公开发表的论文、参加的科研项目以及 致谢。 1 2 重庆大学硕士学位论文2 一种新的精确罚函数 2 一种新的精确罚函数 对非线性约束优化问题( n p ) ，罚函数法是最有效的解决解决方法之一。但罚 函数法的天生的病态性质1 决定了其应用上的局限性。本章我们将提出一种新的 罚函数，并给出了相应的精确罚定理，以解决罚函数的病态性质 2 1 精确罚函数的构造 罚函数方法是解决约束优化问题的主要工具，其解决思路是寻找一个容易求 解的替代问题，而在满足一定的条件下，这个替代问题的解正好是原问题的解。 这样求解问题就变得相对简单。因为罚函数方法可以有效地将带有约束的非线性 优化问题转化为无约束优化问题，所以它在解决约束优化问题方面具有重要作用。 在构造这种罚函数前，我们先明确一下精确罚函数的概念：精确罚函数应满 足的条件是，对于某个罚参数对应的p 的无约束罚优化问题的最优解也是原问题 的最优解。 对非线性约束约束问题( n p ) ： m 洲i n 厂( 工) s t c ；( x ) = 0 ， 。j ( x ) 0 ， v 工r “ i ，= 0 , 2 ，m ) ，j = 0 , 2 ，n ) 其中，厂，c f ，c ，：r “一r 1u “) ， 可行集合z = p 掣f q = o ，f ，；勺( 工) so ，) 。 若令 妒( y ) = m a x 9 ( o ，y )n( 2 1 ) 于是妒( _ ) ，) 对于y 有连续的一阶导数。当y - - 0 时，( y ) = , a y 9 - 1 ；当y ，( 工) 。 对于问题( n p ) ，我们研究下面的罚函数： f ，u ) = ( 厂( 曲一“) + s ( 力( 2 3 ) 易知：f ( x ，u ) - 0 。 1 3 重庆大学硕士学位论文 2 种新的精确罚函数 考虑新的罚函数对应的无约束优化问题： ( p ) r a i nf ( “) 5 工r 4 设其最优解为。则对任意的x ，“，我们有o f ( 式，“) s f ( 工，“) ，且f ( ，“) = o 的充要条件是厂( ) “且s ( ) = o 。 2 2 精确罚函数的- 眭质定理 下面我们给出这种罚函数的性质定理。 定理2 2 1如果x 是问题( n p ) 的最优解k u = 厂( x + ) ，则z + 是罚问题( p ) 的最 优解且fo ，“) = 0 。 证明：因为x 是问题( n p ) 的最优解k u = ，( 石) ，则 f ( 工，“) = 妒( 厂 ) 一“) + s ( x ) = ( ，( x + ) 一f ( x + ) ) + s ( 工+ ) = ( 0 ) + s ( x ) = 0 又因为对任何的工r “，有f ( x ，“) o 。所以，z 是罚问题( p ) 的最优解。 定理2 2 2 设工是问题( n p ) 的最优解，对某个“，z 是罚问题( p ) 的可行解， 并且f ( x ，“) 0 ，如果f ( x ) u ，那么z 是问题( n p ) 的最优解。 证明：根据定理假设，我们有 妒( 厂( ) “) 妒( 厂( z ) - - u ) ，v 工r ”( 2 4 ) 因为f ( x ) “和z 是罚问题( p ) 的可行解。所以 f ( g ) - u ，( ) - f ( x ) 2 0 假设存在x x ，使得f ( x ) 一u 0 ，则有f ( x ) ojf ( x ) 一u ojf ( x ) u 于是 “ ( 功 m 好f ( x ) = 叩 ( 2 ) 综上( 1 ) 和( 2 ) 我们就有( a ) 的成立。 ( b ) 如果p u ，那么u 0 。 则对给定的p 及q ，我们定义下面的双参数精确罚函数： f ( 工，p ， f ) 2 q ( ，( 工) 一 f ) + p 2 ：p ( c t ( x ) ) i e l 其中，p 0 为罚参数，m