（应用数学专业论文）求非线性规划全局最优解的填充函数法.pdf

摘要 求解一般函数的全局最优解问题是热点课题之一，对全局最优化问题有两个 困难需要解决：一是如何从一个局部极小解出发找到更好的局部极小解，另一个 是全局最优解的判定问题。填充函数法是解决第一个困难的实用方法之一。但由 于填充函数是目标函数的复合函数，且目标函数本身可能很复杂，所以构造的填 充函数形式也可能很复杂，再就是参数过多，难以调节还有早期的填充函数法是 沿线方向的搜索方法，使得在实际计算时工作量很大。构造形式简单且参数较少 的填充函数并使其具有好的性质，以便节约许多冗长的计算步骤及调整参数的时 间，是理论及实际工作者继续研究填充函数的目的。 本论文便是在这种指导思想下，针对以上谈及的问题研究。主要工作概述如 下： 第一章介绍主要的几种全局最优化问题和算法，以及他们的特点。这包括： 填充函数法、区间方法、打洞函数法、积分水平集法，从算法的思想到相关理论 给出了一些深入浅出的说明。 第二章对一般无约束连续全局最优化问题，在无李普希兹连续条件下，提出 了一个新的简单单参数填充函数，针对这个填充函数设计了算法，对该算法进行 数值实验，并将算法的结果与文献 3 1 作了对比，结果表明，该算法是有效的并 且有所改进。 第三章对一般无约束连续全局最优化问题，在李普希兹连续条件下，提出了 一个有别于第二章的新的单参数填充函数，针对这个填充函数设计了算法，对这 个算法进行数值实验并和第二章的算法结果进行比较，结果表明，该算法是有效 的并且有所改进。 第四章对一般r n 空间中带有简单箱子约束全局最优化问题，在无强制性条件 下，提出一个新的单参数填充函数，针对该填充函数设计了一个算法，对算法进 行数值实验并和第三章的算法进行比较，结果表明，该算法是有效的并且有所改 进。 关键词：非线性规划全局最优化填充函数填充函数方法局部极小点 全局极小点 a b s t r a c t t of i n dt h ee f f e c t i v em e t h o d sf o r f i n d i n gt h eg l o b a lo p t i m a ls o l u t i o n so fag e n e r a l m u l t i 。m i n i m i z e r sf u n c t i o ni so n eo ft h eh o tt o p i c s t h e r ea r et w od i f f i c u l t i e si ng l o b a l o p t i m i z a t i o n ：o n ei sh o wt ol e a v ef r o mal o c a lm i n i m i z e rt oas m a l l e ro n ea n dt h eo t h e r i sh o wt o j u d g et h ec u r r e n tm i n i m i z e ri sg l o b a l t h ef i l l e df u n c t i o na l g o r i t h m i n t r o d u c e di so n eo ft h ew e l l - k n o w na n dp r a c t i c a lm e t h o d sf o rs e t t l i n g t h ef i r s t d i f f i c u l t y i nr e c e n ty e a r s ，m a n yk i n d so ff i l l e df u n c t i o n sw i t hp a r a m e t e r sh a v eb e e n p r e s e n t e d h o w e v e r , t h o s ep a r a m e t e r sa r et o oh a r dt o a d ju s t a n di ti sm o s t p r o b a b l e t h a tg l o b a lo p t i m i z e r sa r el o s to rf a k eb e t t e rm i n i m i z e r sa r ef o u n d t h e r e f o r e f u r t h e rr e s e a r c hi sw o r t h yo fc o n t i n u i n go nh o w w ec a nc o n s t r u c tf i l l e df u n c t i o n sw i t h s i m p l ef o r m s b e t t e rp r o p e r t i e sa n da l g o r i t h m sa r em o r ee f f i c i e n t t h em a i nw o r ks u m m a r i z e da sf o l l o w s ： i nc h a p t e ro n e ，s o m em e t h o d sf o r g l o b a lo p t i m i z a t i o np r o b l e m sa r eb r i e f l y p r e s e n t e d i n c l u d i n gt h en e wf i l l e df u n c t i o nm e t h o d s ，t h ei n t e r v a la l g o r i t h m ，t h e m o d i f i e dt u n n e l i n gm e t h o d sa n dt h e i n t e g r a lf u n c t i o nm e t h o d s ；a n ds oo n i nc h a p t e rt w o ，an e wf i l l e df u n c t i o nw i t ho n ep a r a m e t e ri ss u g g e s t e df o rf i n d i n ga g l o b a lm i n i m u mp o i n tf o rag e n e r a lc l a s so fn o n l i n e a rp r o g r a m m i n gp r o b l e m sw i t ha c l o s e db o u n d e dd o m a i n w i t h o u tt h e l i p s c h i t zc o n t i n u o u sc o n d i t i o n ，an e wa l g o r i t h mi s p r e s e n t e da c c o r d i n gt ot h et h e o r e t i c a la n a l y s i s t h ei m p l e m e n t a t i o no ft h ea l g o r i t h m so n s e v e r a lt e s tp r o b l e m si sr e p o r t e dw i t hs a t i s f a c t o r yn u m e r i c a lr e s u l t s i nc h a p t e rt h r e e ，an o v e lf i l l e df u n c t i o nw i t ho n ep a r a m e t e ri s s u g g e s t e di nt h i s p a p e rf o rf i n d i n gag l o b a lm i n i m u mp o i n tf o rag e n e r a lc l a s so fn o n l i n e a rp r o g r a m m i n g p r o b l e mw i t hac l o s e db o u n d e dd o m a i n t h ei m p l e m e n t a t i o no ft h ea l g o r i t h m so n s e v e r a lt e s tp r o b l e m si sr e p o r t e dw i t hs a t i s f a c t o r yn u m e r i c a lr e s u l t s i nc h a p t e r f o u r ，an e w a u x i l i a r yf u n c t i o nw i t ho n ep a r a m e t e rw i t hb o xc o n s n a i n e d o nr ”f o re s c a p i n gt h ec u r r e n tl o c a lm i n i m u mp o i n to fg l o b a l o p t i m i z a t i o np r o b l e mi s p r o p o s e d u n d e r s o m em i l d a s s u m p t i o n s ，w ep r o v ei ti saf i l l e df u n c t i o n an e w a l g o r i t h mi sp r e s e n t e da c c o r d i n gt ot h et h e o r e t i ca n a l y s i s a n ds o m en 啪e r i c a lr e s u l t s d e m o n s t r a t et h ee f f i c i e n c yo ft h i sglo b a lm e t h o df o ru n c o n s t r a i n e d g lo b a lo p t i m i z a t i o n k e y w o r d s ：n o n l i n e a rp r o g r a m m i n g g l o b a lo p t i m i z a t i o n f i l l e df u n c t i o n f i l l e df u n c t i o nm e t h o d l o c a lm i n i m i z e s g l o b a lm i n i m i z e s 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：堡：芏! 蠢 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：熊二垒盔 导师签名：幽纽玺 日期兰! 互：；：兰墨 日期趟：2 ：盈 第一章绪论 第一章绪论 本章主要介绍了全局最优化问题的概况及基本知识。首先介绍了非线性优、 化问题全局最优化的确定型算法，接着重点简述了近几年备受关注的非线性优化 问题全局最优解的填充函数法的研究现状和意义，最后列出了本文的内容提要和 章节安排。 1 1 引言 自二十世纪七十年代以来，非线性科学一直是各学科普遍关注的热点研究领 域。作为非线性科学研究中的一个非常活跃的数学分支全局优化的理论和算 法，自其诞生之日起便受到广泛的关注，全局最优化问题多种多样，它广泛应用 于工农业、国防、金融、化工、能源、通讯等领域，而且与几何、代数、概率以 及计算机科学、系统科学、自动化等有密切联系，互相促进。其应用几乎涉及自 然科学和社会科学的各个领域。已成为研究与解决自然科学与工程中许多复杂问 题的一个强有力工具，但要真正解决这类问题，特别是从工程设计中抽象出的非 线性程度较高、优化变量个数较多的全局优化问题，其困难程度特别大。因此本 文主要讨论非线性规划中的全局最优化问题。 1 2 全局最优化概述 最优化是一门应用性很强的学科。简单地讲，它是研究某些用数学公式定义 的问题，并求出其最优解，即对于给出的实际问题，从众多方案中选出最优方案。 具体来说，讨论决策问题的最佳选择之特性，构造寻求最优解的计算方法，研究 这些计算方法的理论性质及其实现。 虽然最优化可以追溯到古老的极值问题，然而它成为一门独立的学科是在上 世纪4 0 年代末，在1 9 4 7 年d a n t z i g 提出求解一般线性规划问题的单纯形法口吒 之后，现在解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、 几何规划、整数规划等等各种最优化问题的理论研究发展迅速，新的方法不断涌 现。15 1 ，实际应用同益广泛。最优化理论和方法在自然科学、经济计划、工程设计、 生产管理、交通运输、国防等重要领域，已受到政府部门、科研机构和产业部门 的高度重视，成为- - j 7 十分活跃的学科。伴随着计算机的高速发展和优化计算方 法的进步，规模越来越大的优化问题得到解决。 最优化问题的一般表达形式为 求非线性规划全局最优解的填充函数法 烹翟( 1 - x 1 ) s 1 x 其中，x r ”是决策变量，几) 为目标函数，xcr ”为约束集或可行域。特别地， 如果约束集x ：r 一，则最优化问题( 1 - 1 ) 称为无约束最优化问题： m i n 。厂( x ) ( 卜2 ) 约束最优化问题通常写为： m i n ，( x ) j f g f ( x ) = o ，e ( 1 3 ) g f ( x ) 0 i ， 这里e 和1 分别是等式约束的指标集和不等式约束的指标集，g i g ) 是约束函数。 当目标函数和约束函数均为线性函数时，问题( 卜3 ) 称为线性规划。当目标函数 和约束函数中至少有一个是变量x 的非线性函数时，问题( 1 - 3 ) 称为非线性规划。 此外，根据决策变量、目标函数和要求的不同，最优化还分成了整数规划、动态 规划、网络规划、非光滑规划、随机规划、几何规划、多目标规划等分支。 本论文主要研究求解无约束非线性规划中全局优化问题( 1 - 2 ) 的理论和方法。 从形式上已经区别了无约束最优化问题和有约束最优化问题，下面将给出解 的精确定义以区分全局极小点和局部极小点。 定义1 1 设x x ，如果 ( x ) f ( x ) v x x ( 1 4 ) 成立，则称x 是问题( 卜1 ) 的全局极小点。如果对所有x x 和工x ，厂( 工) f ( x + ) 成立，则称x 为( 1 - 1 ) 的严格全局极小点。 定义1 2 设x 宰x ，如果对某一6 o 和x 奉的邻域d 幸，6 ) ，有 ( 工) f ( x ) ，v x 彳厂、o ( x + ，6 ) ( 1 5 ) 成立，称x + 是问题( 卜1 ) 的局部极小点。如果对所有工x 和v x x n d ( x ，6 ) ， 厂( x ) f ( x ) 成立，则称x 为( 卜1 ) 的严格局部极小点。优化理论发展至今，求解 目标函数局部极小点的方法已十分成熟，常用的有最速下降法、牛顿法、信赖域 法、共扼梯度法、拟牛顿法等这些算法在长期实践中不断地被检验并完善，局部 优化之所以较早地被人们重视和研究，有两个主要原因：第一，获取局部信息不 是非常困难。第二，局部最优性条件可以依赖在x 点处的目标函数和约束函数被 定量表示。相比之下，全局信息不容易获取。实际计算中，由于x 中有无限个点， 根据( 1 - 4 ) 式判别某点是否为全局极小点一般是不可能的，所以至今建立全局最优 第一章绪论 3 性等价条件仍是一个急需攻克的难题。 缺乏全局最优性条件，从某种意义上说阻碍了算法的发展。由于缺少终止判 别准则，计算效率会大大降低，但并不影响算法自身的发展和研究。对于具有特 殊结构的全局最优化，如：非凸二次规划、一般凹规划、网络规划以及l i p s c h i t z 和d c 规划，均已形成了一些行之有效的算法。如：割平面法、内逼近法、外逼 近法、分枝定界法等。特别地，当厂( x ) 是凸函数，可行域x 是凸集时，问题( 卜3 ) 被称为凸规划问题，对于凸规划而言，每一个厂( x ) 的局部极小即是全局极小。对 于无约束全局优化问题而言，是在约束集x ：r ”的情况下对目标函数进行全局最 小化。方法可分成两大类：随机性方法和确定性方法，其中，随机方有：m o n t e c a r l o 法、模拟退火方法和遗传方法。确定性方法则主要包含分枝定界法、区间算法、 积分水平集法、打洞函数法和填充函数法。 1 3 几个确定性算法介绍 本节将逐一介绍：区间方法、积分水平集法、打洞函数法。 1 区间方法 设r ”是n 维实空间，x 是二维闭子箱，函数：x r 是连续的，那么总极值 问题为 m 硝i nf ( x ) ( 1 6 ) 区间方法是求解问题( 1 - 6 ) 的一种可行的方法。该方法以区间分析为基础利用 分支定界的思想，求出目标函数在x 的总极值和总极值点集x 。 在介绍区间方法之前，先给出一些定义和记号。记，为一个实闭区间k ，6 】其 中t , b r 。对任意a ，b e ，的运算定义为： a 枣b = 口宰bia a ，b 曰) 其中水可以是加、减、乘和除的运算。如果a ，可以写a = t b a ，删】，其中l b a ，删 分别为彳的上下界。闭区间的宽度定义为o j ( x ) = b a ，如果d s r ，那么 ，( d ) = y i y ，y 董d ) 。类似地，可定义船维的区间向量，肌。接下来叙述扩张函数 的定义，设d c _ r 小和厂：d 寸r ，且( ，) = 厂g ) ix y 表示函数厂在y j r ( x ) 的取值范 围，如果函数f ：，( 移) 。，满足 4 求非线性规划全局最优解的填充函数法 形( 】，) f ( y ) ，vj ，( x ) ， 则称f 是的扩张函数。 m o o r e n 6 3 首先发现了区间分析是计算一个函数在x 上、下界的有效工具，它可 用来计算总极值f ，1 9 7 4 年，s k e l b o e n 7 3 把m o o r e 的一部分思想与分支定界原理 结合起来。最后，m o o r e 再次修改，得到了m o o r e s k e l b o e 算法。该算法用于求 ( 卜6 ) 的总极值。算法的主要思想是：先作目标函数，：，斗r 的扩张函数f ： i ( x ) j ，然后利用分支定界的思想，把x 逐步细分，在某个子箱上搜索，最后 找到最优值厂。 m o o r e s k elb o e 算法：1 1 步1 令l ，：= x 。 步2 计算f ( ，) 。 步3 令y ：= m i nf ( y ) 。 步4 令初始集合= ( ( 】，y ) ) 。 步5 选择坐标方向k i lr e ( y ) = ( e ) ，其是与y 的具有最长的棱平行。 步6 用垂直于k 的超平面把y 分成两个子箱，使得y = u 。 步7 计算f ( ) ，f ( v 2 ) 。 步8 对i = 1 , 2 ，令= ，卯( k ) 。 步9 把( y ，】，) 从集合l 中去掉。 步1 0 把( ，v 。) 和( 吃，v ：) 加入到集合l 中去，而且使l 中的对( 1 ，v ，) 从小到大排 列。 步1 1 记集合l 的第一对为( j ，y ) 。 步1 2 若( f ( 匕) ) 厂+ 的解。分母的第1 项为了 避免把前面已得到的，满足厂( x ：) ：( x ；) ：厂( x ；) ：f 的点x ；，江1 2 一，作为本过 程的解。分母的第2 项是为了消除满足v r ( x ) ：0 ，丁( 工) 0 的7 ( x ) 局部极小点x ，这一 第一章绪论 求解途径的主要困难是叩， o ，如 0 很难确定，从而使工作量增大。 y a o 【1 8 】，b a r h e n ，p r o t o p o p e s c u 和r e i s t e r t l9 1 ，c e t i n ，b a r h e n 和b u r d i c k l 2 0 1 对原有的隧道 函数方法作了重要改进，提出了动态隧道算法，这里不再赞述。 本论文研究的重点是填充函数算法。 1 4 填充函数算法的发展 填充函数算法是由西安交通大学的葛仁溥教授等人首先提出的，参见乜卜2 观等。 以后很多学者对此方法又作了许多有益的工作和改进。参见啪心3 1 等。考虑问题 ( 卜2 ) 。 为方便起见，我们记吖刖为问题( 卜2 ) 的局部极小点的集合，g f ，州为问题( 1 2 ) 的全局极小点的集合。 如果我们假设( x ) 在r ”上连续可微且满足强制性条件： 假设1 1 ( x ) 专+ o o ，当i jxi i 专+ o o 则问题( 1 - 2 ) 等价于 ! i m f ( x ) 这是因为由假设1 1 知，一定存在有界闭集x 使得厂( x ) 在r ”上的所有全局极小点 都在x 的内部。 下面介绍几个以前文献中已有的概念： 定义1 3 函数厂( x ) 在一极小值点x ；处的盆谷是指连通域研，具有下列性质： ( 1 ) x i b 卜 ( 2 ) 对于任意一点x 8 ；使得工工：及( 工) f ( x 1 ) ，存在一条从x 到x ：的下降路径。 若工? 是厂( 工) 的局部极大点，则一( 工) 在局部极小点处的盆谷称为( x ) 在局部极大点 x ；的峰。 定义1 4 设工；和x ；是函数厂( 工) 的两个不同的极小点。如果( 工：) ( x ；) ，称在x 2 + 处 的盆谷b ；比x ? 处的盐谷耳低，或称b 汁匕b ；高。 一般使用填充函数方法还要求假设1 2 或假设1 3 。 假设1 2 厂( x ) 只有有限个极小值点。 假设1 3 苁工) 只有有限个极小值。 8 求非线性规划全局最优解的填充函数法 孤立点x ? 处盆谷研的半径定义为： r = i n f f i 工一x j 仁廿? ” ” 如果厂( 工) 在x 处的h e s s i a n 矩阵v 2 f ( x 1 ) 正定，则r 0 。 填充函数算法由两个阶段组成一极小化阶段和填充阶段。这两个阶段交替使用 直到找不到更好的局部极小点。在第一阶段里，可以用经典的极小化算法如拟牛 顿法口4 啪3 ，梯度投影法7 门8 3 和共扼梯度法钔等，寻找目标函数的一个局部极小值点 x i 。然后进入第二阶段，主要思想是以当前极小点x ；为基础定义一个填充函数， 并利用它找到x 工? ，使得 f ( x ) 。 他们注意到这个函数存在如下缺点： 1 算法的成功与否，严重地依赖这两个参数，而且在算法执行之前我们不知道这 两个参数的合适取值，只有多次的实验才有可能找到较好的选择。 2 由于受到指数项e x p ( - 监= 卫) 的影响，当p 太小或忪一x + i i 太大时，p ( x ，x ；) 和 v p ( x ，工；) 变得很小，从而产生假的平稳点。 3 p ( x ，x 1 ) 只在线上存在极小点，因此算法实现很困难。 4 x 为有界闭箱，事实上不是真正无约束全局极小化问题。 为了克服缺陷，葛和秦在乜2 1 给出了七个填充函数： 第一章绪论 9 p ( x , x 沁= 而1e 啾一学) ， g ( x ，工? ，p ) = 一p 2l o g r + ( x ) 卜i i x x ；1 1 2 ， 6 ( x ，工：，p ) = 一p 2l o g ，+ 厂( 工) 卜0 z x ；| i ， q ( x ，i ，a ) = - - i f ( x ) 一f ( x ；) e x p ( a i i x 一芦；i | 2 ) ， q ( x ，x ? ，a ) = - - i f ( x ) - f ( x ；) e x p ( a i i 工一x ；ij ) ， v e ( x ，x ；，彳) = 一v 厂( x ) 一2 a f ( x ) 一( x ：) 】( x x ；) ， v e ( x ，x ；，爿) = 一可( x ) 一彳【o ) 一厂( 工；) 1 百妻 j 至 百。 他们指出后四个函数是较好的填充函数。l i u 在文献 2 8 ( 2 0 0 1 ) 中给出一个 克服以上缺陷的填充函数： 加面意与丽川忙吲i 其中a 充分大。 葛和秦( 1 9 9 0 ) 在文献 2 5 中提出了另一类关于前置点x 。的填充函数，其定义 为 定义1 6 1 _ 若x 工( j p ) ，则在s l = x e x ：( x ) ( 工) 上除了x o s l 是t ( x ，x ) 的极小点外，不 存在其他平稳点。 2 若s 2 = 红x ：，( x ) o ，o 。 ( 3 ) 如果x j 不是全局极小点，p ( x ，x ；) 一定在s ：= 圳厂( x ) 0 和，满足 o r ，。m i a 。x ( ，) ( ( x ；) 一( x ) ) ，厂( x ；) 0 充分小时，下面的几个定理表明函数f ( x ，x ，p ) 是满足定义2 1 的一 个填充函数。 定理2 1 若工( p ) ，则x 是f ( x ，x ，p ) 的一个严格局部极大点。 证明：由x ( p ) 及厂( 工) 的连续知，存在着x + 的一个邻域( x + ，仃) 仃 or 得对于任意的xe ( x ，仃+ ) 且x x ，f ( x ) - f ( x ) 的x 均有 f ( x ，x ，p ) = 一p i i x x + 1 1 2 0 ，有f ( x + ) 厂( x ) 及 f ( x ，x + ，j d ) = 一p | | 工一x | | 2 和v 2 f ( x ，x + ，p ) = 2 p e 这里e 是单位矩阵。因此，v 2 f ( x ，x + ，p ) 负定。从而，工是f ( x ，x ，p ) 上的一个孤立局 部极大点且v f ( x ，x ，p ) o 对所有x j v ( x ，a ) 。定理2 1 表明f ( x ，x ，p ) 满足填充函数的 性质( 1 ) 定理2 2 若x ( 尸) ，则函数在s l ：缸i f ( x ) 厂( z ；) ，x 烈硝 上的梯度不等于零。 证明： 由f ( x + ) f ( x 1 ) 和z i x ，有 第二章一个简单参数的填充函数 1 5 f ( x l ，x ，p ) = 一pi ix l x 1 1 2 ， v f ( x l ，x ，p ) = - 2 p ( x l x ) 0 定理2 3 若x ( p ) ，x l , x 2 x 满足 f c x ) 厂( x 2 ) ，则有 x l 一工1 1 4 1x 2 一x i i 和f ( x ) 厂( 工1 ) ， f ( x 2 ，x ，p ) f ( x l ，x 。，p ) 0 = f ( x + ，工+ ，p ) 证明：显然，由假设条件我们有 f ( x 2 ，x ，p ) 一v ( x l ，z ，p ) = 一p ( 1 lx 2 一x 0 2 一i ix l x i i ) 2 o 存在吨 0 q i d li i - g ，x l d ，x 1 + d x ， x l 一西一z + 0 f ( x ) f ( x l + d l ，x ，p ) f ( x l ，z ，p ) f ( x l d l , x ，p ) o ，令 d l = s 2 斋轰 这罩0 s 2 s l 。则o | l d li i _ t lx l x ij ， 工l d l x i i = ( 1 一s ) l | x l x 1 1 i ix l x + 0 ， ( 4 ) f ( x ) ， 这里s = s 2 1 1 x l x i i 。因此，由定理2 3 ，以下式子成立 f ( x l + d i ，x ，p ) f ( x 1 ，工，p ) f ( x l d l ，工，p ) 0 = f ( x ，x ，p ) 定理2 4 表明，任意1i n t x 且满f ( x 1 ) f ( x + ) ，工l x 的点肯定不是f ( x ，x ，p ) 的一个局部极小点。 定理2 5 若x ( j p ) ，则f ( x ，工，p ) 的任意局部极小点或鞍点都属于 s 2 = x x ：厂( x ) f ( x 。) 。 证明： 由! i mf ( x ) = + ， “j 0 佃 我们有s 2 = 扛x i f ( x ) 0 充分小时， s 2 = 缸x i f ( x ) 1 1 x ：一工i t 考虑情况( 1 ) ，i ix x i i - l lx ；一工i i 并且厂( x ：) 一f ( x ) 厂( x ) 一f ( x ) o 我们有 f ( x ：，z + ，p ) = 一pi ix ：一x 1 1 2 + ( 厂( x ；) 一f ( x + ) ) 3 一p | | x x 1 1 2 + ( 厂( 工) 一f ( x ) ) 3 = f ( x ，x ，p ) | lx ；一x i i 并且( x ：) 一f ( x + ) 厂( 工) 一f ( x 。) 0 充分小，我们同样有 f ( x ：，x ，p ) = 一pi ix ：一x 1 1 2 + ( 厂( j ：) 一f ( x ) ) 3 于是得到， 一p0 工一x 1 1 2 + ( ( 工) 一f ( x ) ) 3 = f ( x ，x ，p ) f ( x ：，x ，p ) j e 第二章一个简单参数的填充函数 令又一集合 由上式得， 占手= 工x ：厂( z ) 厂( z ：) + 占 c i n t x r a i nf ( x ，x ，p ) = m i n f ( x ，x ，j 9 ) x e e i tx e ；e 亍 = f ( 并，x 。，p ) f ( x ：，x ，p ) 其中工ke 0 露= a 显然彳是开集，故并是f g ，x ，p ) 的局部极小点，r i d ( rf ( 2 j ) 厂( 工+ ) 。 定理2 6 表明f ( x ，x ，j d ) 满足填充函数的性质( 3 ) 。定理2 卜2 6 表明f ( x ，x ，p ) 是 一个填充函数。 定理2 7 若x e g ( p ) ，则对于所有的x x ，有f ( x ，x ，p ) o 证明：由于x + g ( j p ) ，则对所有的x x ，我们有( x ) ( x ) 。由定理2 1 对任意的 z x 有f ( t z ，p ) o 。 2 3 算法的解释及算法的实现 在前一节，我们己经分析了填充函数f ( 矗z ，p ) 的一些性质，本节我们进一步 分析填充函数f ( x ，x ，p ) 在数值计算中的另一些性质，从而根据已有的性质，设计 一个效率较高的算法。下面将给出两个搜索方向，以便使用这两个方向，使算法 能跳出原问题当前的局部极小点找到更好的局部极小点。 1 搜索方向 设x 三( p ) ，x ，是当前的迭代点，d ；是当前的迭代方向。类似于n 6 1 ，我们有以 下定理成立： 定理2 8 1 对于给定的常数屯，知满2 = o 0 1 8 求非线性规划全局最优解的填充函数法 ( c ) c o s