（运筹学与控制论专业论文）求解约束全局最优化问题的填充函数法.pdf

中文摘要 全局最优化所研究的是非线性函数在某个区域上的全局最优解的特征和计算 方法在几十年的发展历程中，产生了许多诸如切峰函数法，隧道法以及本文研 究的填充函数法等等新的算法现在全局最优化已发展成为最优化学科领域中一 个独立的学科分支 填充函数法由极小化和填充两个阶段组成，首先在极小化阶段可以用经典的 局部极小化算法寻找目标函数的一个局部极小解，然后进入填充阶段，以之前得 到的局部极小解为基础构造一个辅助函数即所谓的填充函数，通过对该填充函数 的求解来寻找原问题的更好的局部极小解，从而开始新一轮的极小化过程两个阶 段交替进行直到找不到更好的局部极小解，那么最后的局部极小解被看作是函数 的近似全局极小解研究填充函数法的目的在于构造形式简单以及较少参数的填 充函数并使其具有好的性质，以便节约许多冗长的计算步骤及调整参数的时间， 提高算法的效率由此可见，填充函数法的关键之一就在于能否找到一个性能优 越的辅助函数 到目前为止，大多数填充函数都是用来求解无约束最优化问题和箱式约束优 化问题的本文则针对具有一般约束的优化问题，提出了一个新的填充函数并设 计了相应的算法在适当的假设条件下，证明了所提函数的填充性质我们也对 所提算法进行了初步的数值试验，数值结果表明所提算法是可行的 关键词：约束全局优化；填充函数；非线性规划；全局最小解 a b s t r a c t t h ec o n t e n to fg l o b a lo p t i m i z a t i o ni st os t u d yt h ef e a t u r eo ft h eo p t i m a l s o l u t i o n sa n dt h ec o m p u t a t i o n a lm e t h o do ft h en o n h n e a rf u n c t i o n d u r i n gt h e s e y e a r s ，m a n yn e wa l g o r i t h m sh a v eb e e np r o p o s e d ，s u c ha st h ec u t p e a k m e t h o d ， t h et u n n e l i n gm e t h o da n dt h ef i l l e df u n c t i o nm e t h o d ( f f m ) n o w i th a sb e e nd e v e l o p e di n t oa ni n d e p e n d e n tb r a n c hi nt h eo p t i m i z a t i o nf i e l d t h ef f mi sc o m p o s e do ft w op h a s e s ，w h i c ha r et h em i n i m i z ep h a s ea n dt h e f i l l e dp h a s e i nt h em i n i m i z ep h a s ew ew i l lf i n dal o c a lm i n i m u mo ft h eo r i g i n a l p r o b l e mb yu s i n gs o m ec l a s s i c a ll o c a lm i n i m i z a t i o na l g o r i t h m ，a n dt h e n a na u x i l i a r yf u n c t i o nw h i c hi sc a l l e dt h ef i l l e df u n c t i o nw i l lb ec o n s t r u c t e db yu s i n g t h a tl o c a lm i i l i m u l n s oi nt h ef i l l e dp h a s ea n o t h e rb e t t e rl o c a lm i n i m u mo ft h e o r i g i n a lp r o b l e mc a nb ef o u n db yu s i n gt h a t 觚e df u n c t i o n t h e s et w op h a s e sr u n b yt u r n sa n dw i l ln o ts t o pu n t i ln ob e t t e rl o c a lm i n i m u mc a nb ef o u n da n y m o r e i nt h ee n dt h el a s tl o c a lm i n i m u mi sr e g a r d e da st h ea p p r o x i m a t eg l o b a lm i n i m u m o ft h eo r i g i n a lp r o b l e m t h ep u r p o s eo fr e s e a r c h i n gf f mi st oc o n s t r u c ta nf i l l e d f u n c t i o nw h i c hh a ss i m p l ef o r ma n df e wp a r a m e t e r s ，s ot h a tw ec a nr e d u c et h e c o m p u t a t i o n a ls t e p sa n ds a v em a n yt i m e s ot oc o n s t r u c tas u p e r i o ra u x i l i a r y f u n c t i o ni so n eo ft h ec r u c i a lo ft h ef f m u pt on o w ，t h em o s tf i l l e df u n c t i o n s a r eu s e dt os o l v et h eu n c o n s t r a i n e d o p t i m i z a t i o no rt h eb o x 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 t h i sp a p e ri sa i m e da t t h eg e n e r a lc 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 w ep r o p o s ean e w 丘u e df u n c t i o n a n dd e s i g naa l g o r i t h mf o rs o l v i n gt h ep r o b l e mc o n c e r n e d w es h o wt h e 皿e d p r o p e r t i e so ft h ep r o p o s e df u n c t i o nu n d e rs u i t a b l ea s s u m p t i o n s w ea l s or e p o r t t h ep r e l i m i n a r yn u m e r i c a lr e s u l t so ft h ea l g o r i t h m ，a n dt h en u m e r i c a lr e s u l t ss h o w t h a tt h ep r o p o s e da l g o r i t h mi sp r o m i s i n g k e yw o r d s ：c o n s t r a i n e dg 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 o n ；n o n l i n e a rp r o - g r a m m i n g ；t h eg l o b a lm i n i m i z e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证 书丽使用过的材料与我一同工作的周志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意 学位论文储孙始一交签字啉啼歹月乃日 学位论文版权使用授权书 本学位论文作者完全了解天津大学有关保留、使用学位论文的规定 特授权天津大学 可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校 向国家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名= 亨扬易波， 签字e l 期：阳谚年月o 日签字期：加年彳月 日 日 导师签名： 蝴 签字日期：五赢净6 月t b 第一章全局最优化问题概述 第一章全局最优化问题概述 全局优化研究的是无约束或有约束的非线性函数在某个区域上全局最 优解的特征和计算方法全局最优化问题通常可以表述为：给定1 1 维欧氏 空间中的一个非空闭集d 和一个连续可微函数f ：辩一跪，寻找点x d ， 使得f ( x ) f ( x ) 对所有的8 d 成立 客观世界中的很多实际问题都可以抽象成全局优化的数学模型全局 优化的应用涉及科学技术，军事，工程设计，智能控制，经济管理等现实世 界中的方方面面，有着广泛的应用背景然而由于问题全局性的要求，使得 在求解全局优化问题的算法研究中存在着相当的难度，其主要的难点是： 现有的非线性优化方法一般只能求出局部最优解，并且还缺乏有效的判别 准则来判断一个局部最优解是否是全局最优解，从而使得那些利用导数， 梯度和次梯度求局部最优解的方法难以找到全局最优解因此，关于全局 优化问题的求解到目前为止仍然是一个非常困难的问题，有很多理论和实 践问题亟待解决 1 1 最优化问题的一般特性 1 1 1 最优化问题的模型与分类 最优化问题的一般形式是 m i no rm a x ，( z ) ，s t 8 s ， 其中s ( 可行域或容许域) 是舻中的一个集合，通常记为 s = z 跄ng i ( x ) 0 ，i = 1 ，m ；，b ( z ) = o ，j = 1 ，f ) s 中的任意点称为可行点；，( z ) ( 目标函数) 为定义在s 上的实值函数也 1 第一章全局最优化问题概述 即： f 俐佗m ) ， s t 吼( z ) 0 ，i = 1 ，仇， ( 1 1 ) l i( z ) = 0 ，j = 1 ，1 下面介绍最优化问题的简单分类 ( 1 ) 根据可行域划分若s = 舻，即z 是自由变量，则称问题( 1 1 ) 为 无约束优化问题；否则sc 渺，称问题( 1 1 ) 为约束优化问题 ( 2 ) 根据函数的性质划分若目标函数和约束函数都是线性的，则称 问题( 1 1 ) 为线性规划；若目标函数和约束函数中至少有一个是非线性的， 则称问题( 1 1 ) 为非线性规划进一步，若目标函数是二次的，约束是线性 的，则称问题( 1 1 ) 为二次规划；若目标函数是凸的，可行域是非空凸集， 则称问题( 1 1 ) 为凸规划 ( 3 ) 根据可行域的性质划分若可行域内的点是有限的，则称问题 ( 1 1 ) 为离散最优化问题；若可行域内含有无穷多个不可数的点，且可行域 内的点可以连续变化，则称问题( 1 1 ) 为连续最优化问题对于离散优化问 题，若变量均为整数则称其为整数规划问题；若部分变量为整数，而另一部 分变量连续变化，则称其为混合整数规划问题 ( 4 ) 根据函数的可微性质划分若目标函数及约束函数都是连续可微 的，则称问题( 1 1 ) 为光滑优化问题；若目标函数及约束函数中至少有一个 是不连续可微的，则称问题( 1 1 ) 为非光滑优化问题 ( 5 ) 根据函数的向量性质划分若目标函数为向量函数时，则称问题 ( 1 1 ) 为多目标规划问题；若目标函数为数量函数时，则称问题( 1 1 ) 为单目 标规划问题 ( 6 ) 根据规划问题有关信息的确定性划分若目标函数及约束函数具 有随机性，也就是问题的表述形式随时间的变化而变化，具有不确定性，这 样的优化问题称为随机规划；相应地，另外一类即目标函数和可行域都是 确定的，这样的规划问题称为确定性规划问题 - 2 第一章全局最优化问题概述 1 1 2 相关概念与定理 对于最优化问题 m i no rm a x ，( z ) ，s t 8 s ， 令表示欧几里得范数点矿s 称为一个相对极小考, ( r e l a t i v em i n i m u m ) ，或 者局部极小 , ( 1 0 c a lm i n i m u m ) ，如果存在某个 0 ，对所有满足l | x 一矿i l 的z s ，有，0 ) ，( z ) 我们说矿是一个全局极小 , ( g l o b a lm i n i m u m ) ，如 果对于所有的z s ，有( x ) ，( z ) 矿是局部极小点是指在s 的以矿为中心的某个领域内，f ( x ) 在矿处 取到最小值而矿是全局极小点是指在整个可行域s 上，f ( x ) 在矿处取到 最小值局部极小点不一定是全局极小点，但全局极小点一定是局部极小 点当f ( x ) 是凸函数，s 是凸集时，每个局部极小点一定是全局极小点 对于一些广义凸的目标函数，这个性质仍然成立；但对拟凸函数，它不再成 立对于非凸的非线性规划问题，可能会遇到许多局部极小点，其函数值不 同于全局极小值 一般来说，最优化问题的( 全局或局部) 最优解是指( 全局或局部) 极 小值解需要说明的是，在问题( 1 1 ) 中，存在任意阶连续可微的函数，有 最小值但不一定有最小解考虑函数f ( x ) = ( x l x 2 1 ) 2 + ( x x ) 2 ，其最优值为 0 ，但无最优解因此，问题( 1 1 ) 有时也写成下面的形式： i n f ( x ) s t z s 另外，当问题( 1 1 ) 中的可行域s 无界或非闭，以及函数不连续时，其 全局极小值也不一定存在例如，在跪内考虑下面4 个例子： ( 1 ) f i x ) = z ，s = 跪； ( 2 ) ( x ) = e 一善，s = 睨+ = zlz 0 ，z 驼) ； ( 3 ) ，( z ) = z ，s = ( 0 ，1 ) ； 3 第一章全局最优化问题概述 ( 4 ) f ( x ) ： 1 2 ，z = 0 s ： 0 ，1 1z ， z ( 0 ，1 】， 由于不同的原因，上述4 个例子的全局极小值都不存在对于例( 1 ) ，有 i n f f ( x ) ：z s ) = 一o 。；对于例( 2 ) ，有i n f f ( x ) ：z s ) = 0 ，但是无法在s 上 取到例( 3 ) ，( 4 ) 与例( 2 ) 类似 函数，在s 上的下确界i n f ，( z ) ：z s ) 是，在s 上的最大下界若， 在s 上不是下有界，则记i n f f ( x ) ：z s 】- = 一o o 若i n f f ( x ) ：z s ) 是有 限的，则i n f f ( x ) ：z s = 血n ，( z ) ：z s ) 的充要条件是在某点矿s 取 到此下确界( 对于s u p 和m a x 情况类似) 下面是几个最优化问题中常用到的相关定理： 定理1 1( 魏尔斯特拉斯，w e i e r s t r a s s ) 如果s 是咿中一个非空紧集， ( x ) 是s 上的连续函数，那么，( z ) 在s 上至少有一个全局极小点( 极大点) 定理1 2若f ( x ) 是强制的，并且连续，则( x ) 在舻中至少有一个全 局极小点 定义在咿中的函数f ( x ) 称为强制的，是指 l 出m ) = + 。 定义1 1如果存在” 0 ，使得对于每个0 r a n d o m ( o ，1 ) 时，则x i ：= 巧；重复步2 步3t k + 1 ：= d t 。；七：= k + 1 ；若满足停止条件，则终止计算；否则，回到 第2 步 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自 适应全局化概率搜索算法该算法最早由美国密执安大学的h o l l a n d 教授提 出，起源于6 0 年代对自然和人工自适应系统的研究7 0 年代d ej o n g 基于 遗产算法的思想在计算机上进行了大量的纯数值函数优化计算试验8 0 年 代，g o l d b e r g 在一系列研究工作的基础上进行归纳总结，形成了遗传算法 的基础框架 人工神经网络的最早可以追溯到1 9 4 3 年，m c c u u o c h 和p i t t s 建立了第 一个模型，后被扩展为“认知”( c p e r c e p t r o n ) 模型2 0 世纪8 0 年代，h o p f i e l d 将人工神经网络成功地应用于组合优化问题m c c l e l l a n d 和r u m e l h a r t 构造 的多层反馈学习算法成功地解决了单隐含层认知网络的。异或”问题及其 它的识别问题，他们的突破使得人工神经网络成为新的研究热点 8 第二章填充函数法 第二章填充函数法 填充函数法 3 8 】是确定性全局优化算法中的一种这一类算法的思想 是通过构造一个辅助函数，使得算法能够从目标函数的当前局部极小点找 到另一个更优的( 目标函数值更小的) 局部极小点填充函数法最早是由r g e ( 葛仁溥) ( 【1 】， 2 ， 3 】， 4 】) 提出，用来求解无约束的连续全局优化问题 2 1 填充函数法的基本思想与相关概念 填充函数法是由r g e 2 首先提出的，以后很多学者对此方法又做了 许多有益的工作和改进这类方法一般都假设，( z ) 在舻上连续可微且满 足强制性条件 珊冀m ) = + o 。 此时填充函数法所考虑的问题 ( p 1 z m 妒i n m ) z ，r 就退化为，( z ) 在某个有界闭集x 上的全局优化问题 填充函数法由两个阶段组成：极小化和填充这两个阶段交替进行直 到找不到更好的局部极小点它的基本思想为：首先在极小化阶段，使用 任意一种经典的局部优化方法找到目标函数f ( x ) 的一个局部极小点z 1 ， 然后转入填充阶段，以当前的极小点x 1 为基础构造一个称为填充函数的辅 助函数p 0 ) ，使得它有极大点x l ，而且在任何比z 1 所在的谷域高的谷域中 没有极小点或鞍点，但在某个比z 1 所在的谷域低的谷域中有一个极小点或 鞍点虿，然后以- z 作为初始点去极小化厂( z ) ，并找到f ( x ) 的一个新的极小点 x 2 ，使得f ( x 2 ) ( x 1 ) 用x 2 代替x l ，重复上述过程，直到找到f ( x ) 的全局 极小点 下面介绍填充函数法所用到的几个概念： 定义2 1称是函数f ( x ) 在一极小点x 处的一个谷域，是指b 是一 连通区域，且满足以下性质： 9 第二章填充函数法 ( i ) 矿b ； ( i i ) 对任意一点z b ，使得x x + 及f ( x ) ，( 矿) ，存在一条从x 到矿 的下降路径 若矿是f ( x ) 的局部极大点，则一，( z ) 在局部极小点x 处的谷域称为 f ( x ) 在局部极大点x + 处的山域 定义2 2 设x ：和z ；是函数f ( x ) 的两个不同的局部极小点，如果 ，( z ：) ，( z ；) ，则称在z ；处的谷域彩比x ：处的谷域研低，或称研比展 高 2 2求解连续优化问题的填充函数 上世纪八十年代初，r g e 首次提出了填充函数的概念，那以后在众 多学者的潜心研究下，这类方法得到了较快较好的发展填充函数的形式 和性质都有了很大的改进和提高为了更直观的了解填充函数及其发展， 本节介绍了几类颇有代表性的求解连续优化问题的填充函数 2 2 1 求解无约束优化问题的填充函数 填充函数法的关键是在填充阶段中如何构造填充函数，在不同的文章 中对填充函数的定义也有所不同 设x ：是f ( x ) 的一个局部极小点，填充函数的定义如下： 定义2 3 称函数p ( z ，x 1 ) 为f ( x ) 在局部极小点z ；的填充函数，是指 p ( x ，x 1 ) 满足： ( i ) z ：是p ( z ，z ：) 的一个局部极大点，( z ) 在点z ：处的谷域研成为 p ( z ，x 1 ) 的山域的一部分 ( i i ) p ( z ，z ：) 在比研高的谷域里没有稳定点 ( i i i ) 如果存在比研低的谷域彩，则存在z 研，使得p ( z ，z ：) 在z 和 x ：的连线上有极小点 1 0 第二章填充函数法 很显然，对同样的函数f ( x ) 及同样的局部极小点z ：，填充函数是不唯 一的以下便是r g e 2 】等给出的一个含有两个参数的填充函数 即属1 萨高唧( 一掣) ( 2 ) 其算法如下： 算法2 1 s t e p1 选 o ，l 0 ，使1 0 和p 2 不太大，同时使再为较小 s t e p3 构造填充函数( 2 1 ) 用b f g s 方法求其极小，初始点选为 z l = z ：+ 匏1 ，6 0 ， 其中6 可选参 s t e p4 若p ( x ，z i ，7 ，p ) 的极小化序列超出x ，则依次选 甄= z ：+ 如，i = 2 ，6 0 ， 如果由s t e p3 和s t e p4 中的两个式子表示的所有的x i 都用过了，且所有 的极小化序列都超出x ，则转到s t e p1 0 s t e p5 若在极小化p ( x ，x l ，7 ，j d ) 过程中，下列条件之一在x k 成立，则 x | | c 兮z 否则继续极小化p ( x ，z ；，y ，p ) ( 1 ) ( z 七一z ：) t v p ( x 詹，z ：，7 ，p ) o ； ( 2 ) ， 女) 0 ， 同时，妒( t ) 必须满足如下性质中的一部分： ( 1 ) 妒( ) 0 ，v t 【0 ，+ o 。) ；妒( t ) 0 ，v t - t l ，o ) ，其中t l o ； ( 2 ) l i m t 。+ 妒( t ) = 0 ，l i m + t 妒= o ； ( 3 a ) 妒( o ) = 0 ，l i m t + 妒 ) = b o ； ( 3 b ) 妒( 0 ) = 0 ，l i m t + 妒 ) o ； ( 4 ) l i m t 一妒 ) = 一。； ( 5 ) h m + o o 铲( t ) = 0 假设x 0 咿是给定的点，z ；是，( z ) 的一个局部极小点，矿是f ( x ) 的全局最优点，7 1 ，p 0 填充函数可构造如下： 其中 ( ”，j d ) = 叩( 扣z z 。1 1 2 ) 妒( ，y ( m ) 一m ：) ) + 纠) ， ( i ) 叼( ) 满足上述性质( 1 ) 和( 2 ) ； ( i i ) 妒( ) 满足上述性质( 1 ) ，( 2 ) 和( 3 a ) ； ( i i i ) p 满足0 p ，( z ：) 一f ( x ) 1 4 第二章填充函数法 v ( x , 7 , p ) = 叩( 三i ix - 知喃+ 妒( 7 m z ) 一m ；) ) + p 】) ， 其中 ( i ) 叩( ) 满足上述性质( 1 ) 和( 2 ) ； ( i i ) 妒( t ) 满足上述性质( 1 ) ，( 2 ) ，( 3 b ) ，( 4 ) 和( 5 ) ； ( i i i ) p 满足0 p ，( z ：) 内没有稳定点； ( 3 ) f ( z ) 在区域岛= z 咿：f ( x ) ， i ) ) 内没有稳定点； ( 3 ) f ) 在区域& = z x ：f ( x ) 0 x i = i ； 掣 0 铲让t ； d z 。 百o f ( x ) = o ，i ，：如 0 是一个较小的参 数，v ( t ) 是一个连续可微的单变量函数满足： c ( o ) = 0 ，g 亿) a 0 对于所有的t 0 h ( t ) 也是一个连续可微的单变量函数满足以下三条性质t ( 1 ) h 他) 0 ，h ( t ) 单调递增， ( 2 ) h 也) 和t h 他) 单调趋于0 ， ( 3 ) h ( o ) = 0 ，t i m t - - - , + h ( t ) = b 0 下面就是两个成功的例子： 1 f ，a ，允) 2 矿i 赤a r c t a n ( a ，o ) 一， ：) + 纠) ； 1 f ( z ，a ，危) 2i i 赤t a n h ( a i f ( z ) 一，( z ；) + 叫) 2 3 求解离散优化问题的填充函数 填充函数算法是求解连续总体优化问题的一类有效算法但是在( 3 0 】， 【3 9 】) 文献中就给出了对于求离散问题的填充函数法这一节主要介绍一种 适于直接求解整数规划问题的填充函数算法( 【1 5 】， 3 3 ， 3 5 0 该方法通过寻 找填充函数的离散局部极小解，而找到比整数规划问题的当前离散局部极 小解好的解该类算法丰富了填充函数法的内容，且为整数规划的求解提 供了一类新算法 对于一般形式的整数规划问题 ( p ) r a i n ，( z ) ， 8 t 2 xni n ： 其中x = z 舻：a z b 是顶点为整点的有界闭箱，p 是驼n 中的整点 的集合，虽然在计算机科学和经济管理等学科中有广泛的应用，但由于缺 乏必要的分析和代数工具，使得求解极为困难在给出具体的填充函数算 法之前先介绍一些必要的相关概念 1 8 第二章填充函数法 定义2 7对任一整点z i n ，整点的集合n ( x ) 冬i n 称为z 的领域若 n ( x ) 满足 。，z + c i ，z e ，i = 1 ，n ) c ( z ) ， 其中e 是第i 个分量为1 ，其余分量为0 的n 维向量 显然，整点x 的最为简单的一个领域是n ( x ) = z ，x + e i ，x - e i ，i = 1 ，佗) 有了上述整点的领域的概念，下面给出问题( p ) 的离散局部和全局极 小解的定义 定义2 8整点x 0 xni n 称为问题( p ) 的离散局部极小解，如果 比n ( x o ) nx ，有f ( x ) f ( x o ) 定义2 9整点x 0 xni n 称为问题( p ) 的离散全局极小解，如果 比xni “，有f ( x ) f ( x o ) 显然，上述定义隐含着如下结论： 定理2 3问题( p ) 的离散全局极小解必是问题( p ) 的离散局部极小 解 下面给出寻找整数规划的离散局部解的邻域搜索算法，该算法与组合 优化中通常的邻域搜索算法无本质的区别 算法2 2 ( 邻域搜索) s t e p1 任取一初始整点x 0 xni n s t e p2 若问题z o 是问题( p ) 的离散局部极小解，停止；否则，检查z o 的邻域，找到一整点z n ( x o ) nx 使得f ( x ) 0 满足上述条件的函数妒( ) 有很多，如可取妒( ) = a r c t a n t ，则b = 吾或 取妒( t ) = 耳l _ 蕊e - 2 t ，则b = 1 以上几节只是分类概述了几个有一定代表性的填充函数在这么多年 的发展历程中所出现的填充函数可谓多种多样，但是由于篇幅有限不能在 此做更多的介绍不得不承认填充函数法是一个非常巧妙的方法，虽然构 造这样一个函数并不需要多么高深的数学知识，但是想要找到一个性能优 越的填充函数却不是件易事下面例举几篇从2 0 0 1 年到2 0 0 6 年之内的相关 参考文献( 8 】，【9 1 ，【1 0 1 ， 1 2 ，【1 3 ，【1 9 ，【2 0 ， 2 2 ， 3 2 ， 3 4 ，【3 6 ) ，拜读期间受益 非浅 第三章一类新的填充函数 第三章一类新的填充函数 在前面的章节里，我们介绍了多种针对不同优化问题所提出的填充函 数除了用来解决连续的全局优化问题外，还有的用来求解离散的全局优 化问题但无论是连续的还是离散的，都局限于求解无约束或箱式约束问 题，还没有见到对带有一般约束的非线性规划问题做相关讨论本文将讨 论使用填充函数法求解带一般约束的全局优化问题 3 1 1 构造新填充函数 3 1 新填充函数 在由r g e 首先提出的填充函数法中，假设f ( x ) 在咿上连续可微且 满足强制性条件 磊m ) = + o 。 并且存在一个有界闭区域qc 咿包含了，( z ) 所有的全局极小解除此之 外还假设局部极小解的个数为有限个( 每个极小解都是孤立的) 本文就要求解的问题( p ) 给了出以下三条个假设。 ( 1 ) ，0 ) 是连续的； ( 2 ) 厂( z ) 有有限个局部极小值； ( 3 ) s 是连续区域 在第二条假设中，仅管f ( x ) 有有限个局部极小值，但是却可能拥有无限个 局部极小解 定义3 1 假设z ：是，( z ) 的当前局部极小解，l ( x ，x l ，e ) 被称为f ( x ) 在点z ；处的填充函数，如果它满足以下的性质： ( 1 ) x ：是l ( x ，z ：，e ) 的最大解，并且，( z ) 的整个谷域研成为l ( z ，x 1 ，e ) 的山域的一部分；( 谷域和山域的定义请看：定义2 1 ) ( 2 ) l ( x ，z ：，e ) 在比研高的谷域没有稳定点； 2 1 第三章一类新的填充函数 ( 3 ) 如果f ( x ) 在x + 存在一个比研低的谷域j e i + ，那么在b 中存在一个 点z 7 使l ( x ，z ：，e ) 在。；和矿的连线上取得最小( 矿是x 的某个领域中 的任意一点) 注意到定义中的第三条与当年r g e 首次提出的填充函数的概念有所 不同，与z ：相连的不是一个点而是x 的某个领域中的每个点 下面就是本文所构造的填充函数： l ( x ，z ：，e ) = ( 一l lz z ：1 2 ) n ( 1 + c s i g n f ( x ) 一，( z ；) 】) ， 其中： s i g n ( t ) = 一，雳 z ：是问题f ( x ) 的当前局部极小解，s 是一个大于0 小于1 的正常数 考虑下面的一般约束优化问题： 羔：l 罢 其中f ( x ) 是连续可微函数， s = z 蛇nfg i ( x ) 0 ，i = 1 ，仇；，b ( z ) = o ，j = l ，f ) 假设z ；是问题( p ) 的当前局部极小解，在解决问题( p ) 之前我们可以通过 任何一种局极小化方法，极小化厂( 。) 以得到的f ( x ) 一个局部极小解 3 1 2 填充函数的证明与相关定理 引理3 1 l ( x ，x 。1 ，e ) 在z ；点连续 证明：既然x ：是问题f ( x ) 的当前局部极小解，那么当z 无限接近于z ： 时，由f 的连续性可知。f ( x ) 无限接近于，( z ：) 因此， l i m i 三( z ，拼1 ，e ) 2 墨( 一忪一z ：惭佗( 1 悃夕讥i f ( z ) 一m 跏 2 2 第三章一类新的填充函数 = 0 = l ( z ：，z ；，e ) ， 即可证得l ( x ，z ：，e ) 在x ；点连续 证毕 定理3 1 点z ；是l ( x ，z ：，e ) 的局部最大解，l ( x ，x ：，e ) 的山域包含，( z ) 的整个谷域 证明：因为x ：是问题， ) 的当前局部极小解，所以存在这样一个邻 域：( z ：，7 - ) ( 其中丁 o ) ，使得对于所有的x ( z ；，丁) 都有f ( z ) ，( z ：) 成 立因此。 l ( z ，z ：，e ) = ( 一i lz x ：1 1 2 ) f 礼( 1 + s i 9 礼【，( z ) 一，( z ：) 】) = - - i n ( 1 + ) ( i ix x 川2 ) 0 = l ( z ：，z ：，e ) 于是便证明了点z ；是l ( x ，z ：，e ) 的局部最大解 从上面的定理很容易看到，对于除x ；以外的研中的任何一点z ，都有 ，( z ) ，( z ：) 及l ( x ，z ：，e ) l ( z ：，z ：，e ) 成立也就是说f ( x ) 的整个谷域成为 l ( x ，x 1 ，e ) 的山域的一部分 证毕 。 定理3 2 假定x ：是当前的局部极小点，那么对于任意满足，( z ) ，( z ：) 和x x ：的点x ，一定有v l ( x ，茁：，e ) 0 成立 证明：由条件厂( z ) 厂( z ：) 可知 l ( z ，z ；，e ) = 一i n ( 1 + e ) ( i lz x ；1 1 2 ) ， 那么 v l ( x ，z ：，e ) = - 2 i n ( 1 + ) 一x 1 ) 0 证毕 在填充函数的方法中，我们最小化填充函数是为了找到一个点z 使得 ，( z ) ，( z ：) 或者得到f ( z ) 更小的最小解在最小化，( z ) ，( z ：) 的过程 2 3 第三章一类新的填充函数 中，只要f ( x ) 不比厂( z ；) 小，搜索过程就不会停止，上述定理就表明：当 f ( x ) ，( z ；) 时l ( x ，z ；，e ) 没有稳定点 近一步可以注意到，沿着方向d = z z ：，有 v l ( x ，x l ，e ) t d = 一2 1 n ( 1 + g ) f iz z ：1 1 2 ，( z ：) ；要么f ( x o ) ，( z ：) 所以 l ( x o ，z ：，e ) = 一i n ( 1 + e ) ( 0z o z ：f 1 2 ) ， 或者 l ( x o ，z ：，e ) = 一i n ( 1 一) i