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

摘要 最优化是一门应用相当广泛的学科，它讨论决策问题的最优选择，构造寻求 最优解的计算方法并研究这些方法的理论性质及实际计算表现。由于社会的进步 和科学技术的发展，最优化问题广泛见于经济计划，工程设计，生产管理，交通运 输，国防军事等重要领域，凶此受到高度重视。伴随着计算机的高速发展和最优化 工作者的努力，最优化的理论分析和计算方法得到了极大提高。 求解一般函数的全局最优解问题是热点课题之一。对全局最优化问题有两个 困难需要解决：一是如何从一个局部极小解出发找到更好的局部极小解，另一个 是全局最优解的判定问题。全局最优化算法，从算法的构造上大体可以分为确定 型算法和随机型算法。其中，填充函数法就是随之出现的一种确定型算法，它是解 决第一个困难的实用方法之一。 填充函数的主要思想是：如果已经找到了一个局部极小矿，但它不是全局最 小，可以在矿处构造一个填充函数使迭代点列离开矿所在的谷域，找到更好的 点( 即处的目标函数值比矿处的目标函数值更小) 。然后以为初始点极小 化原问题找到更优的局部极小点。 填充函数法只需应用成熟的局部极小化算法，因此受到理论以及实际工作者 的欢迎。但是由于填充函数是目标函数的复合函数，且目标函数本身可能很复杂， 所以构造的填充函数形式也可能很复杂。再就是参数过多，难于调节。还有早期提 出的填充函数法是沿着线方向搜索方法，使得在实际计算时工作量很大。构造形 式简单以及较少参数的填充函数并使其具有好的性质，以便节约许多冗长的计算 步骤及调整参数的时间，提高算法的效率，是理论和实际工作者继续研究填充函 数的目的。 本论文的主要工作是：提出一个新的填充函数，在此基础上给出两个求解全局 最优化的算法，力图在算法效果方面有所提高，在理论方面有所深化。其内容详细 情况如下： 本文包含三章章内容，第一章主要介绍了目前国内外主要的几种全局最优化 问题和算法，以及他们的特点。这包括：填充函数法、打洞函数法、分支定界法等。 i 对填充函数法，从算法的思想到相关理论给出了一些深入浅出的说明，在此基础 上，分析了各臼的优缺点，为进一步的推广和构造新的填充函数法，提供一些指导 思想和思路。 第二章，对一般无约束连续全局最优化问题，提出了一个新的简单单参数填 充函数。针对这个填充函数，设计了算法，对该算法进行了有效的数值实验，结果 表明，该算法是有效的。 第三章，在基于上一节填充函数的基础上，利用分值定界算法的思想构造一 个新的求解全局最优化的算法，并对该算法进行了有效的数值实验。 关键词非线性规划全局最优化填充函数填充函数方法局部极小点全 局极小点 a b s t r a c t t h eo p t i m i z a t i o ni saw i d e l yu s e dd i s c i p l i n e ，w h i c hd i s c u s s e st h ec h a r a c t e r so f o p t i m a lc h o i c eo nd e c i s i o np r o b l e m sa n dc o n s t r u c t sc o m p u t i n ga p p r o a c h e st of i n d t h eo p t i m a ls o l u t i o n d u et ot h ea d v a n c e m e n to fs o c i e t ya n dt h ed e v e l o p m e n t o fs c i e n c ea n dt e c h n o l o g y ，t h eo p t i m i z a t i o np r o b l e m sa r eo f t e nd i s c o v e r e di nt h e f i e l do fe c o n o m i cp l a n n i n ga d m i n i s t r a t i o n ，e n g i n e e r i n gd e s i g n ，p r o d u c t i o nm a n a g e - m e n t ，t r a m ct r a n s p o r t a t i o n ，n a t i o n a ld e f e n c ea n ds oo n t h e ya r es oi m p o r t a n t t h a tm e e tw i t hm u c hr e c o g n i t i o n 。w i t ht h es p e e d yd e v e l o p m e n to fc o m p u t e ra n d t h eh a r dw o r ko fs c i e n t i s t s ，t h et h e o r e t i ca n a l y s i sa n dc o m p u t a t i o n a lm e t h o d so i l o p t i m i z a t i o nh a v eb e e nh i g h l yi m p r o v e d t of i n dt h ee f f e c t i v em e t h o d sf o rf 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 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 e o t h e ri sh o wt oj u d g et h a tt h ec u r r e n tm i n i m i z e ri sg l o b a l g l o b a lo p t i m i z a t i o n m e t h o d sc 妇b ec l a s s i f i e di n t ot w og r o u p s ：s t o c h a s t i ca n dd e t e r m i n i s t i cm e t h o d s t h ef i l l e df u n c t i o na l g o r i t h mi n t r o d u c e db yg ea n dq i n ( 1 9 8 7 ) i 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 gt h ef i r s td i f f i c u l t y 。t h em a i ni d e ao ff i l l e d f u n c t i o nm e t h o di s ：i fal o c a lm i n i m i z e r 矿h a sb e e nf o u n d ，w ec a nm a k eaf i l l e d f u n c t i o n s u c ht h a ti t e r a t i v es e q u e n t i a lp o i n t sl e a v et h ev a l l e yi nw h i c hz + l i e st o f i n dab e t t e rp o i n t i nt h el o w e rv a l l e y ( i e ，( ) = 一m i n - f ( z ) ：z s ) ，所以最大化问题包含在上 面模型中。进而，由于阢( z ) 0 等价于一m ( z ) 0 ，吼( z ) = 0 等价于吼( z ) 0 和一夕t ( z ) 0 ，我们看到( 1 1 1 ) 包含了许多其它类型的约束。 如果可行域是整个佗维欧氏空间，那么下列问题称为无约束最优化问题： v a i n ，( z ) s t z 形 ( 1 1 2 ) 如果s 是一个多面体时，称问题( 1 1 1 ) 是线性约束的；此外，若目标函数也是线 性的，该问题称为线性规划问题。当( 1 1 1 ) 中出现的函数至少有一个是非线性的， 该问题称为非线性规划问题。当目标函数，和每个约束函数鳜都是凸的时候，问 题( 1 1 1 ) 称为凸规划问题。当，是凸函数，s 是凸集时，问题( 1 1 1 ) 也称为凸规划。 在本文中，为了方便统称问题( 1 1 1 ) 和问题( 1 1 2 ) 为原问题。如果不加特别说 明l l - l i 始终表示欧几里得范数；v ，0 ) 表示， ) 在点z 处的梯度；v 2 ，( z ) 表示 ，扛) 在点z 处的h e s s e 矩阵。 定义1 1 1 点矿s 称为一个局部极小点，如果存在某个 0 ，对于所有 满足忙一矿0 的z s ，成立， + ) ，扛) ，而，0 ) 称为局部极小值 定义1 1 2 矿s 称为一个全局极，i 、点，如果对于所有z6s ，成立，( 矿) ，( z ) ，而，( 矿) 称为全局极小值 在全局最优化问题中，凸规划具有很好的性质，也就是当目标函数是凸的，可 行域也是凸的时候，凸规划的每个局部极小值就是全局极小值，因此，可以应用求 局部极小点的方法，求得全局极小点，已有的局部极小化算法对它都是有效的。而 对于非凸的问题，可能存在很多局部极小点，其函数值不同于全局极小值，这样就 使得在求解全局最优化问题时面临很多困难，所以首先要研究目标函数在可行域 s 上的局部和整体性质。为此，先回顾一些基本概念，下面的定义和定理在大部分 最优化的教材或文献上都有叙述和证明，可以参考【1 ，2 ，9 ，3 0 ，5 4 。 2 上海大学硕士学位论文 定义1 1 3 函数f 在s 上的下确界，记作i n f ( f ( x ) ：z s ) ，是，在s 上 的最大下界；函数f 在s 上的上确界，记作s u p f ( x ) ：z s ) ，是，在s 上的 最小上界 定义1 1 4 在sc 舻上的一个实值函数f 称为李普希兹函数，如果存在一 个常数l = l ( f ，s ) 0 ，使得对于所有z l ，x 2 s ，有 l ，( z 2 ) 一f ( x 1 ) lsl l l x 2 一z 1 0 ， 其中l 称为李普希兹常数 定理1 1 1 设sc 舻是凸的，在包含s 的一个开集上连续可微，并且在 s 上具有有界的梯度，则，在s 上是李普希兹函数，且李普希兹常数 己s u p l l v f ( x ) l i ：z s ) 定义1 1 5 sc 舻称为闭集，如果s 包含所有收敛点列 ) cs 的极限 点；sc 舻称为紧集，如果s 是闭的有界集 由函数在紧集上的连续性，我们可以得到下列著名的魏尔斯特拉斯定理： 定理1 1 2 如果s 是舻中一个非空紧集，扛) 是s 上的连续函数，那么 f ( x ) 在s 上至少有一个全局极小( 极大) 点 定义1 1 6 集合s 舻上定义的实值函数，在s 上的点z 处称为下半 连续，如果有f ( x ) = l i r a 斌，( 秒) ；f 在s 上的点z 处称为上半连续，如果有 f ( x ) = l i ms u p f ( y ) 容易看出，函数在z 点处既下半连续，又上半连续，则它在z 点处连续。在 定理1 1 2 中如果将，的连续替换成下半连续( 上半连续) ，那么定理仍然成立。 定义1 1 7 在凸集c 上函数f 的上方图倒( ，) 表示为：卿( ，) = ( z ，r ) c r ：r ，( z ) ) 。 在极小化问题和凸性的研究中，下半连续的表现形式和重要性与下面的结果 有关： 3 上海大学硕士学位论文 定理1 1 3 设s 是舻中一个非空闭集，是s 上任意一个函数，则下列条 件是等价的： 1 在s 上，是下半连续的 2 对于每个a r ，三( ，；口) = z s ：f ( x ) q ) 是闭的 3 在舻+ 1 中，上方图, p i ( f ) 是闭集 定义1 1 8 定义在舻中的函数f ( x ) 称为强制的，如果有u mf ( x ) = + 。o i l x l l + 对于无约束最优化，其中s = 舻，若，是强制的，则全局极小点的存在性问 题可以借助定理1 1 2 来讨论。 定理1 1 4 若f ( x ) 是强制的，并且连续，则f ( x ) 在舻中至少有一个全局 极小点 下面给出一些关于局部和全局极小点特征的结果。 。 定义1 1 9 向量d 舻称为点矿s 处的可行方向，如果存在” 0 ，使 得对于每个0 入”，有矿+ , x d s ( s 是问题的可行域) 令，在点矿的一个邻域内连续可微，并且令d 舻满足d t v f ( x ) 0 ， 其中表示式d t y f ( x + ) 是在矿处沿方向d 的方向导数。对于固定矿和d ，函数 f ( x + + a d ) 描述了，沿射线缸= 矿+ a d ，入o ) 的情况。因为 ， + + a d ) 一f ( x ) + , x d t v f ( x + + p a d ) ， 这里0 p 1 是某个确定的数。所以d t v s ( = + ) 0 ，使 得对于每个0 a 页，有f ( x + a d ) f ( x ) 。也就是，可以沿方向d ，使，局部 地下降。所以有如下定理： 定理1 1 5 假设函数f ( x ) 在一个包含sc 舒的开集内连续可微。若矿s 是的一个局部极小点( 相对于s ) 则对于每个可行方向d ，都有d t v f ( x + ) 0 定义1 1 1 0 点z s 称为平稳点，如果对于每一个可行方向d ，都有 d t v f ( x 。) 0 对于一般问题来说，平稳点并不一定是极小点，但是对于凸规划问题，有下列 定理： 4 上海大学硕士学位论文 定理1 1 6 若，是一个在包含s 的开集内连续可微的凸函数，并且s 是一 个凸集，则x + s 是一个全局极小点，当且仅当矿是一个平稳点 定理1 1 7 凸函数，：s _ r ( 其中s 舻是凸的) 的每一个局部极小点 也是全局极小点 定义1 1 1 1 凸集s 边界上的点z 称为一个极点，如果不存在互异的两点 x l ，x 2 s ，使得z = a z l + ( 1 一a ) 观，0 入 玩，i 1 ，2 ，m ) ) = 0 ，即矿d ，则算法终 止：否则转步3 。， 步3 选择j i ( x 詹) ，令最+ l = p kn ( z i 口弘幻) ，计算y ( p k + 1 ) ，转步1 。 外逼近方法的步骤非常简捷，它已被广泛用于凹规划、反凸规划和d g 规划 及单调规划问题，详尽的结果可参见文献【3 l 】。外逼近方法的收敛性已由h o r s t 等人 在文献f 3 2 1 给出。 定理1 2 2 基于上述的外逼近方法，算法具有m 步终止。 1 1 上海大学硕士学位论文 1 2 3 单调规划 在经济、工程及其他一些领域巾的大量数学模型通常都具有某些变量或所有 变量的单调性的性质。在最优设计的相当多数量的文章中，单调性在数值方法的 研究中起着相当重要作用。当单调性与凸性和反凸性结合在一起时，产生了乘积 规划 3 1 1 ，c 一规划【3 7 】等等低维的非凸问题。在过去的十年间，参数方法、对偶基 的补偿方法对求解低维的上述问题的速度是相当快的。 考虑下述问题： m i n f ( x ) l 夕( z ) 1 ( z ) ，x r ：)( 1 2 3 ) 此处，0 ) ，9 ( z ) ，h ( x ) 都是单调增加的( 即当0 z ，f ( x ) ，扛) ，称f ( x ) 为 增加的1 。由考虑的抽象凸性。在某种特殊假设下，此类问题可由广义外逼近方法 来处理。然而，纯单调结构的最重要的优点在于利用全局信息，通过在可行域的限 制区域上的极限的全局搜索，可以用来简化问题。事实上，当( 1 2 3 ) 的目标函数是 单调增加的，若名为可行域已知的可行点，因在z + 殿没更好的可行解，故z 在 z + 僻上为不起作用的。类似地，当函数9 ( z ) ( 相应地h ( x ) ) 是单调增加的，z 为 在z + 解上对于约束夕扛) 1 ( 相应地h ( x ) 1 ) 为不可行点，则整个名+ 霹 可以不予考虑。基于上述观察，外逼近或分支定解等有效方法来可以用求解易处 理的单调规划。 如果存在一单调增加函数9 0 ) ，使得g = z 皿1 9 ( z ) 1 ) ，其形如 g = u 【0 ，习。其中g = u 【o ，z 1 为箱子簇 o ，z l 的和集，z z ，则称g 是正 规的。当z 为有限集时，正规集称为多胞块。正像紧凸集足一簇多胞体的交集， 紧正规集是一簇多胞块的交集。由此，单调系统的解集结构的特征可以被建立起 来，用于单调不等式和单调优化问题的数值分析。更重要的是，多胞块逼近方法 可以推广到求解两个单调增加函数差的优化问题( 亦称为d ，函数的规划问题， 比如问题( 1 2 1 ) ) 。参见文献 6 3 ，6 4 】。由于扎个变量的多项式可表为两个正系数 的多项式之差，即两个殿上的单调增加函数之差，由w e i e r s t r a s s 定理可知，在 【0 ，6 】= 伽舻i o x 吣上的d ，函数在【0 ，6 】上为稠密的，因此，d j 最 优化的适用范围包括多项式规划( 特别是非凸二次规划) 和各类全局和组合优化 问题。虽然如此，但到目前为止，解d ，规划问题仍然是一个较困难的问题，在 】2 上海大学硕士学位论文 理论和算法上都没有d d 规划完备。 1 2 4 填充函数方法 填充函数法是由两安交通大学的葛仁溥教授等人首先提出的，参见【1 4 ，1 5 ，1 6 ， 1 7 ，1 8 】等。以后很多学者对此方法又作了许多有益的工作和改进参见 2 3 ，4 0 ，4 2 ， 7 3 ，7 4 ，8 1 ，8 6 ，8 8 1 等。 考虑闯题( 1 1 2 ) 。为方便起见，记l ( p ) 为问题( 1 1 2 ) 的局部极小点的集 合，c ( p ) 为问题( l 1 2 ) 的全局极小点的集合。 假设f ( x ) 在冗n 上连续可微且满足强制性条件： 假设1 2 1 f ( x ) _ + o o ，当忙0 _ + o o 。 则问题( 1 1 2 ) 等价于 m i n ，( z ) ( p ) iz x 、 、 这是因为由假设1 2 1 知，一定存在有界闭集x 使得f ( x ) 在舻上的所有全局极 小点都在x 的内部。 下面介绍几个以前文献中已有的概念： 定义1 2 1 函数f ( x ) 在一极小值点z ：处的盆谷是指一连通域b ；，具有下 列性质? ( i ) z ：冒i ( i i ) 对于任意一点z 研使得z z i 及f ( x ) ，( z ：) ，存在一条从z 到z i 的下降路径 若z ；是， ) 的局部极大点，则一f ( x ) 在局部极小点z ：处的盆谷称为f ( x ) 在局部极大点z ：的峰 定义1 2 2 设z ：和z ；是函数f ( x ) 的两个不同的极小点如果，( z ：) ，( z ；) ，则称在z ；处的盆谷展比z ；处的盆谷b ；低，或称研比磁高。 一般使用填充函数方法还要求假设1 2 2 或假设1 2 3 。 假设1 2 2 f ( x ) 只有有限个极小值点 假设1 2 3 f ( x ) 只有有限个极小值 1 3 上海大学硕士学位论文 孤立点z ；处盆谷b ；的半径定义为： r = i 。n 。f 。i i x 一= 7 1 1 z g 研 如果f ( x ) 在z ；处的h e s s i a n 矩阵v 2 f ( x 1 ) 正定，则r 0 。 填充函数算法由两个阶段步组成一极小化阶段和填充阶段。这两个阶段交替 使用直到找不到更好的局部极小点。在第一阶段里，可以用经典的极小化算法如 拟牛顿法拟牛顿方法 2 4 ，4 7 ，5 3 】，梯度投影法 7 1 ，硎和共轭梯度法 8 9 】等，寻找目标 函数的一个局部极小值点z ：。然后进入第二阶段，主要思想是以当前极小点x ；为 基础定义一个填充函数，并利用它找到z ：，使得 ，( z ) 0 。 他们注意到这个函数存在如下缺点： 算法的成功与否，严重地依赖这两个参数，而且在算法执行之前我们不知道这 两个参数的合适取值，只有多次的实验才有可能找到较好的选择。 由于受到指数项e x p ( 一j l 兰若监) 的影响，当p 太小或忙一矿i i 太大时，p ( z ，矿) 和v p ( x ，z ，) 变得很小，从而产生假的平稳点。 上海大学硕士学位论文 o p ( x ，矿) 只在线上存在极小点，因此算法实现很困难。 x 为有界闭箱，事实上不是真正无约束全局极小化问题。 为了克服缺陷，葛和秦在 1 5 】给出了七个填充函数： 讯蕊 萨南唧( 一宇) ， a ( x ，z ：，7 ，p ) = 一p 2 l o g r + ， ) 】一i l z z ；1 1 2 ， g ，。：，p ) = - p 2 l o g f r + ，0 ) 1 0 茁一z 钏， q ( z ，z ：，a ) = - f ( x ) 一，( z ：) 】e x p ( a i i x z ：1 1 2 ) ， q ( z ，z ：，a ) = - f ( x ) 一，( z ；) 】e x p ( a h x x ：1 1 ) ， v e ( z ，z ：，a ) = - - v f ( x ) 一2 a f ( x ) 一( x d l ( x z ：) ， v 豆( z ，z + 1 ，a ) = 一v f ( z ) 一a i f ( z ) 一，( z ：) 11 i 量三禹 他们指出后四个函数是较好的填充函数。l i u 在文$ r 4 2 1 ( 2 0 0 1 ) 中给出一个克服以上 缺陷的填充函数： 日( 叩2 币可西1 = 了丽一口l l x - x ；1 1 2 ， 其中a 充分大。 葛和秦( 1 9 9 0 ) 在文f 1 8 】中提出了另一类关于前置点x o 的填充函数，其定义为： 定义1 2 4 1 若矿己( p ) ，则在& = 矗x ：f ( x + ) ， ) 上除了 z o 岛是t ( x ，矿) 的极小点外，不存在其他平稳点 2 若岛= z x ：f ( z ) 0 ，0 ) 】6 上海大学硕士学位论文 ( 3 ) 如果z ；不是全局极小点，那么p ( x ，z ：) 一定在岛= zif ( x ) f ( 2 7 ) ，那么构造打洞函数 一 t ( 纠= 阿研乒铬箍当惭， 这里0 1 1 是 一z 1 ) t ( 2 7 一x 1 ) 的强度。目的是使x l 不再是t ( 2 7 ，矿) 的局部极 小点，防止极小化t ( x ，矿) 时，又得到x l 。然后重新极小化t ( x ，2 7 * ) 。 3 如果f ( 2 7 1 ) f ( 2 7 ) 。这样t ( x ，矿) 会变得十分复杂，且使算法实现十分困难。 3 极的增加会使打洞函数更为平坦，这时求极小点变得困难。同时缺乏全局最优 性准则同样是该算法难以克服的团难。 为了避免求解t ( x ，矿) = 0 ，啪文献 7 5 】中提出了动态打洞算法。定义能 量函数 e ( z ，z + ) = t ( x ，z + ) + k z u ( z ) d z ， 其中，( z ) = f ( x ) 一i ( 2 7 + ) ， 心，= 黔z = 0 1 8 上海大学硕士学位论文 然后求解初始条件为矿+ e 的动态系统： d xa e 一= 一一 d to x ( 1 2 4 ) 这里e 是一个扰动向量。从给定的初始条件，能量沿着动态流递减，当系统( 1 2 4 ) 收敛到平衡状态时，即为完成打洞步骤。( 1 2 4 ) 的平衡点岔在比矿低的盆谷里， 且， ) f ( x ) 。这种方法中，罚参数k 是依赖于问题的，动态系统( 1 2 4 ) 既 是非线性的又带有参数q ，求解也是比较困难的问题。 c e t i n ，b c 等人根据文献【7 5 】的思想，在【6 】给出能量函数： 和动态系统 d x0 e 一= 一一 d t跳 ( 1 2 5 ) 它的特点是系统( 1 2 5 ) 可以完成一个循环的两个步骤一极小化阶段和打洞阶段。 另外还有随机打洞算法，如【4 9 】等。 文$ s 2 1 ，1 9 2 1 也对打洞函数提出了一些改进，提出了变形打洞函数法，其定义 改为： 1 t ( x o ，矿) = 0 当且仅当f ( x o ) 一f ( x ) + r = o ，r 0 为一个很小的数。 2 对任意z 岛= 。x ：，( 茁) f ( x 。) ) ，v t ( x ，矿) 0 3 若岛= z x ：f ( x ) 0 ，x o 簪x ，且对所有z x ，满足忙一x o l i 1 。 针对于函数f ( x ) = x s i n x 和它的一个局部极小点矿= 0 ，下面给出它的修正 打洞函数图像( 见图1 2 2 ) 。 此外，文献i s 2 给出的既是填充函数又是变形打洞函数为 上海大学硕士学位论文 图12 1 ( x ) = x s i n x 和五( z ，矿) ，死( z ，矿) ，其中q = 1 0 0 0 ，7 = 0 0 0 1 。 m ，r ，萨坠筹静帑地 其中，双参数7 0 为较小的正数，p 0 为较大的正数。 t ( z ，矿，) = 硼荔1 邗 再否面丽顶万项萄再鬲高蕊斫丽= 7 虿雨万 ，( z ) 一，鱼) + r 其中，q 2 固定，单参数t 0 为较小的正数。 它们满足条件1 ，2 ，3 。很显然，上述两个函数满足 t ( x o ，z ，p ) = 0 = 争，( z o ) 一( x ) + ，= 0 称它们为变形打洞函数。 其它的变形打洞函数： 乃( z ，矿，r ，力= ( 1 + l l z x o f | 2 ) l n ( 1 + p ( ，( z ) 一( x ) + r ) 2 ) 其中，双参数r 0 是较小的正数，p 0 是较大的正数，x o 岳x 。 死( 叩+ ，r ) = 嚣糍虢等萨 其中，q 3 固定，单参数7 0 是较小的数，x 0 岳x 。 2 0 上海大学硕士学位论文 1 2 6 积分水平集算法 1 9 7 8 年，郑权教授提出了求解函数全局优化的积分水平集算法。积分水平集 算法可以认为是利用了函数的整体性质，来解决全局最优化问题的，它不同于前 面介绍的各种方法。 考虑问题( 1 1 1 ) ，u p r a i nf ( x ) s t z s ， 设x 是n 维欧氏空间，其中f ：x _ r ，s 是x 的一个子集。我们作如下假设： 假设1 2 4 f 在s 上是连续的 假设1 2 5 存在一个实数c 使得水平集 鼠= z 舻：s ( x ) c ) 和s 的交集非空而且紧。 因此上述问题可归结为求c ，使得 c = r e _ i n _ f ( x ) x e s n h c ， 此时，令 h 。= sn 甄0 ， 于是，在假设1 2 4 和假设1 2 5 下，上述问题可以重新叙述为，求c 和日+ 满足 ( p ) 矿= m 剃i n m ) ， h + = z s ：f ( x ) = c ) 在此基础上，给出了问题( p ) 的全局最优化解的条件。 定理1 2 3 在假设_ f 2 彳和假设j 2 5 下，如果p ( 皿) = 0 ，其中鼠= z s ： ，( z ) 0 d ，肛是l e b e s g u e 测度，那么，c 就是，在s 上的全局极小值，皿 是全局极小值点的集合 2 1 上海大学硕士学位论文 定义1 2 7 设c c = n d n ，( z ) ，令 m ( f ，c ) = 而1f u 。f ( z ) 如， 其中 玩= z s ：f ( x ) c ) ， 称m ( f ，c ) 是函数f 在水平集皿的均值 定义1 2 8 设c c + = r a i n ，( z ) ，令 v l ( f , c ) = 瓦1f h ( f ( z ) 一删2 p ， 其中鼠是水