（运筹学与控制论专业论文）积分总极值方法在有界可测函数上的推广.pdf

上海大学硕士学位论文 摘要 求全局最优化问题的方法在科学技术、工程设计、经济管理等方面 有着很广泛的应用，本文主要研究讨论以积分水平计算法为主的确定性 全局最优化算法。 1 9 7 8 年，郑权等提出了积分型求总极值的方法，来解决求解全局 最优解的问题。1 9 9 9 年，邬冬华等对原郑权的方法作了一些改进，提 出了修正的积分型求总极值方法。然而这些积分总极值方法还仅限于定 义域为闭集的连续函数。 本文利用本质下确界的概念，以及勒贝格积分的特性，将积分总极 值方法推广到了有界可测函数上，提出了针对有界可测函数的理论算法 和实现算法，并给出了其最优性条件和收敛性证明。在第一章中，我们 简单介绍了全局最优化问题的一些基本知识。在第二章中，我们简单介 绍了几个确定性全局最优化的算法，并且对积分水平集算法的历史、发 展和基本知识进行了详细的介绍。第三、第四章中，我们则将积分水平 集算法推广到了有界可测函数上，提出了相应的理论算法和实现算法， 并给出了其最优性条件和收敛性证明。 关键词：全局最优化，积分水平集，一致分布佳点集，最优性条件， 收敛性 v 上海大学硕士学位论文 a b s t r a c t t h e r ea l em a n y a p p l i c a t i o n so ft h en o n l i n e a rg l o b a lo p t i m i z a t i o ni nt h e f i e l do fs c i e n c ea n dt e c h n o l o g y , o p t i m a ld e s i g no fe n g i n e e r i n g , e c o n o m i c m a n a g e m e n ta n ds t ) o n i nt h i st h e s i s , w ec o n s i d e rs o m ed e t e r m i n i s t i c m e t h o d s ，e s p e c i a l l yt h ei n t e g r a l l e v e l s e t m e t h o d , f o rs o l v i n gg l o b a l o p t i m i z a t i o np r o b l e m s i n1 9 7 8 z h e n gp r o p o s e da ni n t e g r a l l e v e ls e tm e t h o dt os o l v eg l o b a l o p t i m i z a t i o np r o b l e m s i n1 9 9 9 ，w ui m p r o v e di t , a n dp r e s e n t e dam o d i f i e d i n t e g r a l l e v e ls e tm e t h o d b u tt h e s ei n t e g r a l - l e v e ls e tm e t h o d sh a v eo n l yb e e n u s e di nc o n t i n u o u sf u n c t i o n sw i t hc l o s e dd o m a i n i nt h i st h e s i s , w ee x t e n dt h e i n t e g r a l - l e v e l s e tm e t h o d 幻b o u n d e d m e 船u r a b l ef u n c t i o n s ，b yi n t r o d u c i n gt h ec o n c e p to ft h ee s s e n t i a li n f i m u m a n dt h ep r o p e r t yo fl e b e s g i l ei n t e g r a l w ep r o p o s ea ni n t e g r a | l e v e ls e t c o n c e p t u a la l g o r i t h ma n da ni m p l e m e n t a la p p r o a c hf o rb o u n d e dm e a s u r a b l e f u n c t i o n s ，a n da l s og a i n e di t so p t i m a l i t yc o n d i t i o na n dp r o v e dt h a tt h i s a p p r o a c hi sc o n v e r g e n t f i r s t ，i nc h a p t e r1 ，ab r i e f i n t r o d u c t i o ni sg i v e nt ot h e b a s i ck n o w l e d g eo fg l o b a lo p t i m i z a t i o n a n dt h e n , i nc h a p t e r2 ，w es i m p l y i n t r o d u c es e v e r a ld e t e r m i n i s t i ca l g o r i t h m sf o rs o l v i n gg l o b a lo p t i m i z a t i o n p r o b l e m s ，a n dad e t a i l e di n t r o d u c t i o ni sg i v e nt ot h eh i s t o r y , d e v e l o p m e n ta n d b a s i ck n o w l e d g eo f m ei n t e g r a l - l e v e ls e tm e t h o d f i n a l l y ，i nc h a p t e r3a n d4 w ep r o p o s ea ni n t e g r a l l e v e ls e tc o n c e p t u a la l g o r i t h ma n da ni m p l e m e n t a l a p p r o a c hf o rb o u n d e dm e a s u r a b l ef u n c t i o n s ，a n da l s og a i n e di t so p t i m a l i t y c o n d i t i o na n d p r o v e dt h a tt h i sa p p r o a c hi sc o n v e r g e n t k e y w o r d s ：g l o b a lo p t i m i z a t i o n , i n t e g r a l - l e v e ls e t , g o o dp o i n t s e to f u n i f o r md i s t r i b u t i o n , o p t i m a l i t yc o n d i t i o n , c o n v e r g e n c e v i 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：盘垄半日期： l i 上海大学硕士学位论文 1 1 引言 第一章绪论 最优化方法是近代应用数学的一个新的分支，广泛应用于工程技术、科学 研究和经济管理等诸多领域。它主要研究在一定的限制条件下，对若干可供选 择的决策方案做出最满意的决策，去完成所要完成的任务。它的主要内容就是 寻求最满意的决策的方法，建立这些方法所依据的理论以及如何在计算机上实 现这些方法。 一般来说，对于一个优化问题( p ) r f f l n f ( x ) s 1 x s 其中s c r ”厂( 曲：r ”一r 1 。 全局最小点x + 是指：对所有s 域上的点x ，均有，( 矿) f ( x ) 。 局部最小点工是指：存在6 o ，对所有满足肛一x 1 i f ( x l 。) ，存在一条从x 到_ 的下降路径。 若善。是厂( 石) 的局部极大点，则一，( 功在局部极小点而+ 处的盆谷称为 f ( x ) 在局部极大点的峰。 定义2 1 1 2 设而和屯是函数厂( x ) 的两个不同的极小。如果 f ( x 。) 厂( 也+ ) ，则称在屯+ 处的盆谷最比而+ 处的盆谷b i + 低，或称马+ 比 4 上海大学硕士学位论文 易高。 在定义2 1 1 1 和定义2 1 1 2 的基础上，葛仁淳教授在文献嗍中给出了 一个填充函数的定义 定义2 1 1 3 函数p g ，_ ) 称为厂( x ) 在局部极小点而处的填充函数，如 果满足： ( 1 ) x 1 是p g ，而) 的一个严格局部极大点，( x ) 在点毛处的盆谷马成为 p ( x ，x 1 ) 的峰的一部分； ( 2 ) p g ，x l ) 在比置高的盆谷里没有平稳点。 ( 3 ) 如果存在比蜀低的盆谷如，i t j 存在x b 2 使得p b ，而) 在一和x 1 的连线上存在极小点。 由填充函数的定义可以看出，如果当前极小点不是全局极小点的话，通过 极小化填充函数，我们可以跳出原问题当前局部极小点，并达到一个原问题函 数值比当前局部极小值还要小的点。毫无疑问，从该点出发极小化原问题目标 函数，必将导致一个原问题目标函数更小的局部极小点。 填充函数算法由两个阶段组成：极小化阶段和填充阶段。这两个阶段交替 使用知道找不到更好的局部极小点。在第一阶段里，可以用经典的极小化算法 寻找目标函数的一个局部极小值点而。然后进入第二阶段，在当前极小点一+ 处定义一个填充函数，通过极小化填充函数，找到点一五，使得 f ( x ) 厂的解。分母的 第一项是为了避免把前面己得到的，满足厂( _ ) = f ( x 2 + ) 一一+ ) = 厂+ 的点 x t + ，i = 1 ，2 ，f 作为本过程的解。分母的第二项是为了消除满足v t ( x ) = o ， t ( x ) 0 的t ( x ) 的局部极小点x 。隧道函数的参数的选取详见l e v y 和m o n t a l v o 的文【3 2 】。 隧道函数方法有如下的性质： 性质2 i 2 1 在极小化过程中，若取r 为初始点，则一定能找到点满 足厂( 工。) ，( x ? ) 。 性质2 1 2 2 在“凿隧道”过程中，若取置为初始点，则一定能找到点 一0 。满足， ) ，( x ? ) ，也t 。 由以上两条性质可得： 性质2 1 2 3 若算法无限进行下去，则有 厂( + ) f ( x 2 + ) 2 2 f ( x o - i + ) f ( + ) 其中是f ( x ) 的总极值点，t x ，+ ，i ，。 隧道函数方法的难点是参数玎和九的选取，以及算法的终止准则。 7 上海大学硕士学位论文 2 1 3 模拟退火算法 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐 冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒 子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最 小。根据m e t r o p o l i s 准则，粒子在温度t 时趋于平衡的概率为p 哆圩) ，其中e 为温度r 时的内能，e 为其改变量，k 为b o l t z m a n n 常数。用固体退火模拟组 合优化问题，将内能e 模拟为目标函数值厂，温度r 演化成控制参数t ，即得到 解组合优化问题的模拟退火算法：由初始解i 和控制参数初值t 开始，对当前解 重复“产生新解一计算目标函数差一接受或舍弃”的迭代，并逐步衰减f 值，算 法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种 启发式随机搜索过程。退火过程由冷却进度表( c o o l i n gs c h e d u l e ) 控制，包括 控制参数的初值t 及其衰减因子址、每个t 值时的迭代次数三和停止条件s 。 模拟退火的基本算法为： 步1初始化：初始温度丁( 充分大) ，初始解状态s ( 是算法迭代的起 点) ，每个丁值的迭代次数三。 步2 对k = 1 ，2 ，l ，做第3 步至第6 步： 步3产生新解。 步4计算增量a t = c ( s ) 一c ( s ) ，其中c ( s ) 为评价函数。 步5若a t 0 则接受作为新的当前解； 否则，以概率口。接受作为新的当前解。 步6如果满足终止条件则输出当前解作为最优解，结束程序。( 终止 条件通常取为连续若干个新解都没有被接受时终止算法) 步7r 逐渐减少，且r 寸0 ，然后转步2 。 算法完毕。 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后 上海大学硕士学位论文 续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产 生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产 生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一 定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分 产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言， 这是计算目标函数差的最快方法。 第三步是判断新解是否被接受，判断的依据是一个接受准则，最常用的接受 准则是m e t r o p o l i s 准则：若缸 0 则接受作为新的当前解s ，否则以概率 ， p 。圻接受作为新的当前解s 。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对 应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前 解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时， 则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态s ( 是算法迭代的 起点) 无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 9 上海大学硕士学位论文 2 2 积分总极值算法 2 2 1 积分总极值算法介绍 全局最优化问题是运筹学这门学科的一个重要研究分支之一，一直受到数 学规划领域内众多研究学者的广泛关注。现代科学、经济和工程的许多最新发 展有赖于相应优化问题的全局最优解的计算技术。全局优化问题已广泛涉及到 各个不同的领域，其中包括经济模型、金融、网络与运输、数字集成设计、图 象处理、化学工程设计与控制、分子生物学、环境工程及军事科学等等。由此 可见，对全局优化问题的研究具有重要的现实意义。到目前为止，对于一些具 有特殊结构的全局优化问题，已发展起了许多理论和方法成功的予以解决。但 由于问题有“全局性”的要求，对于一般的全局优化问题算法研究中仍然存在 着一定的困难。我们可以求出一个全局优化问题的局部极小点，但还没有一个 有效的全局评判准则来判断一个局部极值点就是全局极值点。如何在搜索过程 中从一个局部极值点跳出，找到下一个更好的局部极值点，直到全局最优点， 这也是全局优化问题研究的课题之一。 郑权教授在1 9 7 8 年时提出了积分一水平集算法。4 圳，并给出用m o n t e c a r l o 取点的实现途径。这个算法是利用积分中值定理来实现的。在每一步迭代中， 先求出函数值小于q 的点集王，通过在片。上求积分中值，便可得到一个新的 函数值c k + l ，至此一步迭代结束。该算法具有很好的收敛准则，序列 “) 最终趋 向于全局最小点。可以说这个算法的思想成功的解决了寻找全局最优点的难题。 事实上，如填充函数、隧道函数的方法，都是在找到一个局部最小点后，再跳 向一个更小的局部最小点，而如何寻找下一个局部最小点、如何确定找到的局 部最小点就是全局最小点，都是非常难解决的问题。积分一水平集算法巧妙的抛 开了局部极小点的困扰，利用积分的全局性，直接构造一个以全局极小值为极 限的序列，从而求解总极值问题。 但积分一水平集算法也存在一些缺陷：在一般情况下，水平集凰是很难求出 1 0 上海大学硕士学位论文 的。事实上，求解水平集日。的难度和求解总极值的难度是等价的。所以在实现 算法过程中，在郑教授的文中只能通 x ：立m o n t e - c a r l o 取点求得近似水平集，其实 现算法的收敛性问题至今没有解决。 针对郑教授的积分一水平集算法，在一般情况下，水平集不易求得而造成难 以求出水平的困难，为了减少已有算法的计算量和提高已有实现算法的计算效 率等目标，邬冬华教授对原始的积分一水平集算法提出了改进，得到了一种修正 的积分一水平集算法“”。该方法保持原有算法的优点，避免原算法可能会产生丢 失总极值的缺陷，提高了修正积分水平集算法的计算效率，且讨论了算法在概 率意义下的收敛性，给出了数值结果。 下面我们将对积分水平集算法作详细的介绍。 2 2 2 积分一水平集算法的基本概念 郑权教授在1 9 7 8 年时提出了积分一水平集算法”4 “，它所研究的对象为： 令【，是一个拓扑空间，s 是u 的子集，是定义在u 上的实值函数。积分 水平集算法想要解决的问题就是如何寻找t ，在s 上的全局最小值 矿= i j ( u ) ”曲 和全局最优点集 h + = 打s l ，( 甜) = c + 在郑权等人的积分一水平集方法中，对问题做了如下的假设： ( a ) ：，是下半连续函数( 1 0 w e rs e m ic o n t i n u o u s ) ，s 是闭集，并且存 在一个实数b 使得集合h b = 扣s i j ( u ) s6 ) 为非空紧集； ( r ) ：j 在s 上是上丰满函数( u p p e rr o b u s tf u n c t i o n ) ； ( m ) ：( u ，n ，肋是q 一测度空间( o - m e a s u r es p a c e ) 。 定义2 2 2 1 称函数，：u r 在点下半连续，如果对于所有a o 使得v “b ，7 ) ，有旯s ，( “) 。 定义2 2 2 2 称函数，是下半连续函数，如果它在u 中的任意一点都是下 上海大学硕士学位论文 半连续的。 性质2 2 2 1 函数，在甜。点是下半连续的，当且仅当以。) l i m i n f j ( u ) 性质2 2 2 2 对函数j 以下三个命题等价： 1 ，是下半连续的； 2 ，的上图像是闭的； 3 所有关于，的水平集s ，叩) = = 函【，l ，( ) ，7 ) 都是闭的。 定义2 2 2 3u 是一个拓扑空间，d 是【，的子空间，集合d c u 被称作 是丰满的，当且仅当c l d = c l i n t d 定义2 2 2 4 点1 , 1 c l d 在d 上被称为丰满点，如果对于任意点甜的领域 n ( u ) ，成3 立n ( u ) l l i n t d 矿。集合d 是丰满集当且仅当d 中的任意点在d 都上 丰满的。 定义2 2 2 5 定义在拓扑空间u 上的函数，是上丰满函数，如果集合 c = 函l t ，( “) c ) ，对于任意实数c 都是丰满的。 定义2 2 2 6 令u 是h a u s d o r f f 空间，q 是u 子集上盯一域，是q 上的 测度。三元量p ，q ) 被称为是个q 一测度空间，当且仅当 1 u 中任何的开集都是可测的； 2 任意非空开集g c u 的都是正的：a ( g ) 0 。则该修正的积分水平集算法的理论算法主 要步骤如下： 步1 f f 双x o d ，给定一个充分小的正数占，令岛= ，( ) ， z 乙= 叫x d ，厂( 力c o ) ，_ | = 0 。 步2 若( 以) = o ，则q 为总极值，以为总极值点集，转步6 。 步3 作函数厶o ) ，满足： 圳= x 羔毒 计算均值q “2 i 吉了j l 矗 ) 舭，且令 h c 。= 如睢d ，f s c k 0 若吒。= q ，则，为总极值，以。为总极值点集，转步6 ； 否则，转下一步。 步4 计算均方差圪“5 i 为了j z ( 矗( 一气) 2 舡 步5 若l 占，则令l i = | + l ，转步3 5 1 4 上海大学硕士学位论文 否则，转步6 。 步6 令广= q “，且日= + ，终止日为( x ) 在d 中的近似总极 值点集，为相应的近似总极值。 那么通过算法求得的序列慨) 是否是收敛的；若确是收敛，其极限是否就 是函数，( x ) 在d 上的全局最小值呢? 这就需要就对算法的最优性条件进行讨 论。 定义2 2 3 1 设q 广= n f m f ( x ) ，定义肘皈) = 云i _ l 厶( x ) 础，其中 删= x 芝毒，州枷矧。 性质2 2 3 1 设 ，则m 魄) s 咯。 性质2 2 3 2 若 q 单调下降且趋向于c ，c ，则 h c 2 舰以2 0 以，且憋忆) 2 慨) 。 性质2 2 3 3 若叙 单调下降且趋向于c ，c z f + ，则舰吖k ) = 时伉) a 定理2 2 - 3 1 若由算法产生的序列瓴 ，集列 如 满足c = 舰q ， 皿2 憋则有 ( c 为问题( d 的全局最小值； ( 6 ) 以为问题( p ) 的全局最小点集。 定理2 2 3 1 若 ) 单调下降且趋向于c ，则有! i m v t = 0 。 f 这些性质、定理证明了通过修正的积分水平集算法得到的结果，就是我们 要求的全局最小值和全局最小点集。 基于这个理论算法，邬冬华教授弓i a 3 数论的知识，利用构造数论的一致 分布点集的方法，提出了修正的积分水平集算法的实现算法。 设厂= r a 。i n 厂( 功，且厂= 卿厶( x ) 令毛= q + 一q ) t ，i = l 2 卅。 而f = 纯，) q ，故不妨设d = q 。则该修正的积分水平集算法的实现算法 可表示如下： 步1 取而g ，给定一个充分小正数万，令磊= 厂瓴) ， k = 翻聋q ，( 力磊 ，七= 0 ，l o = 0 。 步2 做函数矗 ( 力满足 厶炒懈 x e g h h k k x h 弧 利用致分布数值积分计算水平 c k + i “= 士艺矗 ( p c s ) ) 且 ，2 l k i k + l ；l j , 1 - i k + l 为整数序列，当j i 一佃时，_ 忡。 取近似离散水平集为 j 气。 。；纠x = p ( ，) g ，厂( p ( s ) ) s 屯。，i k 。，s = 1 ，2 ，i k + 。； x 月i ，厂( x ) 蟊“，l k “j 及水平集为 + 。= 4 z g ，厂b ) s 色。l k + 。) 。 其中p ( j ) ，s = l ，2 ，i k 。) 为佳点集。 步3计算均方差 = 士芝魄以( p c s ) ) c k + l ，“) 2 步4 若圪+ 占，则令后- | i + l ，转步2 ；否则，转步5 。 步5 若“肘0 卅) 艿，则算法有限步终止，转步6 ；否则，取 。= 阻0 卅) 占】+ 1 ，转步1 ，其中m 0 卅) 是函数i 厂( x ) l 在q 上的一个正上界。 上海大学硕士学位论文 步6 令，= 屯。，l k + ，及詹= 也以。，1 2 1 ：是f ( x ) c f f ：g , , 中的近似总极 值点集，厂+ 是近似总极值。 在郑权提出的实现算法中，采用的是m o n t e - c a r l o 随即投点产生近似水平 集，然后作包含近似水平集的一个新的最小有界闭箱d 1c d ，从而产生迭代过 程。此实现算法的一个明显弱点是：在遗弃的区域d 、d i 上可能丢掉了d 上的 总极值及总极值点。另外，m o n t e - c a r l o 方法的平均收敛速度为d f 行一1 ，且是 在概率意义下的。而修正的积分水平集法，利用数论方法计算，其收敛速度为 d 【刀。1 ”) 。尽管为了保持原实现算法的良好性质，在每一步迭代中把d 分划成 2 n + 1 个子箱，增加了一些工作量，但能保证总极值不被丢失，且每步对个子箱 采用不同的策略，在算法中所构造的中心子箱d 中尽可能多取一些一支分布 点，从而使水平更快地下降。依照这种修正的实现算法，在文献“2 1 中己证明其 实收敛的。并且数值试验的结果也表明，该实现算法优于“”中相应的结果。 1 7 上海大学硕士学位论文 第三章积分总极值方法在有界可测函数上的推广 ( 理论算法) 3 1 研究背景和基本概念的引入 令u 是一个拓扑空间，s 是u 的子集，j 是定义在u 上的实值函数。本论 文讨论的问题是如何寻找- ，在s 上的全局最小值 矿= i 蟑，( 甜) 和全局最优点集 日+ = 扣s i ， ) = 矿) 在郑权等人的积分水平集方法“”“2 1 中，对问题做了如下的假设： ( a ) ：j 是下半连续函数( 1 0 w e rs e m ic o n t i n u o u s ) ，s 是闭集，并且存 在一个实数b 使得集合见= 伽e s i ，( “) s6 为非空紧集； ( r ) ：j 在s 上是上丰满函数( u p p e rr o b u s tf u n c t i o n ) , ( m ) ：( u ，q ，) 是q 一测度空间( q - m e a s u r es p a c e ) 。 而事实上，对于“，是下半连续函数”，以及“s 是闭集”等这些条件似乎 有些苛刻。因为在实际的生产和生活中，我们知道待求极值的函数是非连续的 情况比比皆是，而且其定义域也并非一定是闭集。因此，我们需要重新定义全 局最小值的概念。 i 一1x = 0 例如函数彻2 x ；e o “喃如b 如右图所示 从理论上说，厂( 并) 的全局最小值是一1 。但是事实上这个最小值是个相当不稳定 的状态，由于自变量x 所属的区间是连续的，因此只要x 在0 点附近有一个微小 的扰动，则f ( x ) 立即就会远离一1 。这也就是说，f ( x ) 的全局最小值是一1 是没 1 8 上海大学硕士学位论文 有实际意义的。另一方面，引入勒贝格测度我们知道，事实i - _ f c x ) 在【p l ，p ：】是 几乎处处大于零的，或者说对t p 。，p 2 】，厂( 力2 0 的概率为1 。因此，可以 说0 才是，( x ) 在【p 。，p ：】上有意义的“全局最小值”，我们称之为本质下确界， ( 当然，这里的本质下确界是达不到的) 。用测度的语言来说，令集合 e o = 戈【a ，p 2 i 厂( z ) o ， e = 缸瞻，见】| f ( x ) 0 。 由上例我们可以得出结论：在自变量x 连续，而函数值f ( x ) 非连续的条件 下，我们考察其全局最小值，就相当于是求其本质下确界。 定义3 1 1 设函数厂( x ) ：r “一r 1 是在有界可测集s 上的有界可测函数， 若对于实数c ，记e = 仁sj f ( x ) c ，且满足( e ) = o ，矿= s u p c ，则称c 为f ( x ) 在有界可测集s 上的本质下确界。 注：此处的测度指的是勒贝格测度。 事实上，通过这样的定义之后，我们可以看到：若厂( 功为连续函数，则如 此定义的本质下确界c 就是全局最小值；如果( x ) 不连续，则有可能全局最小 值是达不到的或是存在于孤立点上，那么上述定义所得的结果，也能保证f ( x ) 在其定义域s 上，几乎处处大于其本质下确界c ，即( 易) = o ，其中 以= 缸s f f ( x ) c ，令丘= x s l f ( x ) 0 根据定义3 1 1 ，用反证法易证。 虽然，本质下确界的引入可以很好的解决不连续函数可能不存在全局最优 值的问题，但是本质下确界也常常是达不到的，从而使得我们即使求出了本质 下确界，也难以得到问题对应的解集。为了解决这一问题，我们还需引入另一 个概念“近似全局最小解集”。 举一个简单的例子：有甲、乙两家工厂都在生产完全相同的一种商品，每 家工厂的产量都足够满足社会的需求( 假设社会需求是个定值疗) ，且其生产成 本都为常数c 。乙厂已将这种商品的售价定在某一定值( 根据国家的价格规 定，售价只能在一定的范围内波动：p l y o p 2 ) ，那么甲厂的订价x 应为多少 ( p 。x p 2 ) ，才能获得最大的利润。( 假设社会需求的分配原则如下：顾客 在商品完全相同的条件下，都会买价格较低的商品；若两者价格相同，则社会 需求将平均分配到两家工厂。) 在这个例子中，实际上就是要求解一个单变量函数f ( x ) 的最大值。假设价 格x 是连续的，则函数，( 功可以被具体的写出： ，( x ) = 0 y o 0 ，故卢( j ) 0 。 通过这样的定义之后，我们可以看到：若厂( 功为连续函数，那么只要让 占一0 ，则如此定义的近似全局最小值孑将会无限的逼近本质下确界c ( 此时 的本质下确界就是真正的全局最小值) ，而近似全局最小解集也会无限的逼近真 正的全局最小解集；如果，( x ) 不连续，那么上述定义所得的结果，也能保i t t f ( x ) 在非近似全局最小解集，即s j 上，几乎处处大于近似全局最小值f + ，并且 只要让占_ 0 ，近似全局最小值f 也将会无限的逼近本质下确界c 。 3 2 理论算法及其收敛性 至此，我们先结合文献【12 ，1 4 1 ，给出对于有界可测函数的积分水平集总极值 算法，然后再参考文献u 3 , 1 4 1 ，对该算法的最优性条件进行分析。 步0取s ，令c o = f ( x o ) ，并给定正数j 和a 。 步1 令日。= 】1 x s ，厂( x ) c o 。 步2 u ( h 。o ) 0 ，则令| j = 0 ，转下一步； 否则，使c o = + 旯，转步1 。 2 1 上海大学硕士学位论文 步3 计算函数矿瓴) 。i b l q k 一，( 瑚咖 步4着v ( c ) o 。用反证法，若 c o 0 矛盾。故可知c 0 c 证毕。_ 进一步，如= c + ，则算法第3 步中有矿( ) = o ，算法终止。这是因为， 附志t 删和：也些等善坐竺 根据定义( e 一) = o 且在砟一髟上( x ) = c + ，又因( 髟) 0 ，于是矿( 白) = o 。 性质3 2 2 令 c a 是由本文所提出的算法产生的序列，则对v k 有 气c 证明：用数学归纳法证明：若 c 则+ l2 c + ；若= c + 则序列终止。 由性质3 2 1 及其后续分析可知，若c o = f 则序列终止，故只需考虑c o c 的情况。 对任意一个c 雎 c + ，根据引理3 有( ) o 。由算法中q 的递推公式， 有 上海大学硕士学位论文 = 丽b t m ，咖2 面b t c + 咖= 号篡笋= 一即“ 特别的，当c 。= c + 时， l ( h c 一砟) = o 。这是因为如果 i z ( h c 一也) 0 ， 则有2 南t ，咖2 南( t 也f ( x ) d g + t ，( x ) 咖) 2 志( k 也厂( x ) 咖+ 一( 彤) ) 南( t 也c + 咖+ 一( 以) ) ：! ：竺! 生二堡生! ：竺! 生! ( ) 即c 。“ c + 与已知的“= c + 矛盾。 因此( 以一砟) = 0 ，i 故g ( h ，) = ( 以) 0 ，于是算法第3 步中有 v ( c m “) = v ( c + ) = 0 ，算法终止。 至此，结论证毕。一 推论3 2 1 令 c k 是由本文所提出的算法产生的序列，若对某一个有 靠= c ，则有( 以) 0 2 乏v ( c + ) = o ，算法终止。并且当k c + 。 此推论在性质3 2 2 的后边部分证明中，已经得到证明。 性质3 2 ，3 令h 是由本文所提出的算法产生的序列，则序列瓴 是单调 递减的，且是有界的。即序列 吒 是有极限的。且有! 鳃q2 万c ，其中c + 为 厂( 功在s 上的本质下确界。 证明：性质3 2 2 已经证明了对v 七有气c + ，下面我们来证明对v 七有 c k + 1 c 。时，根据引理3 有( 吒) 卢( & ) o 。又根据e 的定义 上海大学硕士学位论文 可知，在上厂( 功 。于是 = 志t ，o ) 咖= 南 1 一，厂o ) 础+ k 厂( x ) 咖 2 南k 砂+ k m ，叫 c ，有q + l c + 。 性质3 2 4 令h ) 是由本文所提出的算法产生的序列，即 吒) 是一单调下 降的序列，并且! 骢q2 万c + ，其中c + 为，( z ) 在s 上的本质下确界。则有 憋以2 q 以5 珥和熙( 以) 2 ( ) 。 证明：先证 鳃以= n 以= 珥。 o ”i “4 设x 以。，则有，( x ) s q 。 亭，则存在某个常数e ，满足 石 0 k 时，恒有q c + ，则根据引理3 1 3 可得 ( 瓯) 0 。 因此，下面只需证明若存在某一个c 。= c ，那么结论也成立。事实上，由 推论1 可知此时有p ( 曰) = 声( 髟) o 。并且由于矿( ) = 矿p + ) = o ，算法将终 止。 至此，结论得证。 定理3 2 1 证明了本文算法的可行性。即本算法中的计算公式是可以计算 的，不会因分母为零而产生算法无法继续的情况出现。 性质3 2 5 令 以) 是由本文所提出的算法产生的序列，即 c 。 是一单调下 降的序列，并且! 鳃q = e - c ，其中f + 为厂( x ) 在s 上的本质下确界。若万 c + ， 则有粤矿( q ) = 矿( 万) ，其中矿( c ) = j 高万t k 一厂( 纠和 证明：要证明。l i + m 。_ v ( c d = v ( c - - ) ，只需证明p 他) 一y p ) i 5 已o o 即可。而 l v ( c 。) 一矿( 万) i = k k 删劫一志l f 一删叫。b 上海大学硕士学位论文 由于h ) 是一单调下降的序列，故q 万 c + 。于是由引理3 可知b c 且( 上) 乒( 也) o 现在看一下积分： t t & 一，c 瑚咖一j 南l - f 一，c 瑚劫i k k 一厂c 瑚和一志t b 一厂c 瑚咖i + b b t k 一，c 瑚和一面b t h 一，c 堋叫 + k 南t h 一，c 堋和一面b t 眵一厂c 堋叫 = i i 七i l + l 因为( x ) 在s 上有界，而序列瓴) 又单调有界，所以q 一厂 ) 在皿。上有 界，即存在曰使得i 以一厂( x ) l _ c + ，其中c + 为厂 ) 在s 上的本质下确界。如果 c - - c * , 则有c 1 l 嗵t c 以= o 其中以c ) 2 页匆- l p 一八曲】咖 正f llo n o 证明：由性质3 2 2 有吒2c + 。若存在某一个c 。= f ，则由推论3 2 1 可知，此时有矿( ) = v ( c ) = o ，算法将终止。故结论成立。 因此，下面只需证明对v | i 有q c + 时结论也成立。 由引理3 1 3 有_ f ( ) o 。现在看一下积分： ) 2 志t k f ( x ) d t t + t k 一，c 力，咖一面b k 旷c 瑚叫 kp 。，和i = 1 l + j 2 对厶，同性质3 2 4 的l ，有 南t 卜m ) h c - f ( x ) l d l t 2 南l 瓴坳= c k - - c 马。 又由于在上矿厂( x ) c i ，因此 南南 上海大学硕士学位论文 l2 南l 旷( 力。坳 i b t 瓴一c + ) 咖= c k - - c 屿。 从而，可得矿( 气) 玛o e p 。l i _ + m 。_ v ( c k ) = o 结论证毕。一 定理3 2 2 设函数，( x ) ：r “_ r 1 是在有界可测集s 上的有界可测函数。 再令奴) 是由本文所提出的算法产生的序列，即概) 是一单调下降的序列，并 且憋c t = c 。则以下两个命题等价： 1 c 是函数( 工) 在s 上的本质下确界。 2 磐附沪。，其中瞰) = 志t p f ( x ) l d l t 。 证明：先证1 j 2 ：该结论由性质3 2 6 可得。 再i y 2 等1 ：设l i m 矿( 吒) = 0 ，但c + 不是厂( x ) 在s 上的本质下确界，则其 c - f 本质下确界为孑( 根据性质3 2 3 可知f 0 ，则有 ( 上q ) 0 ，( 皿) 0 ，而且根据性质3 2 5 有1 i m 矿( q ) = 矿( 矿) 。接着需 一， 要证明矿( c ) 0 与条件相矛盾。 瞰+ ) 2 志l ( 瑚和 = 志l ，p + ( 瑚础+ 南j 0 【c + ( 纠咖 志小l 删和搿口l ( m ”。 定理证毕。 定理3 2 3 设娩) 是由本文所提出的算法产生的序列，则 q 一定收敛到 厂( x ) 在s 上的本质下确界c + ，即鲤q = c + 。 上海大学硕士学位论文 证明：由于函数f ( x ) 在有界可测集s 上是有界可测函数，故f ( x ) 在s 上可 积。于是根据算法中v ( c d 的定义以及q + 的定义，有： ) 2 志t 【气卅x 脚 2 页b t q 咖一页b t ，( x ) 咖2q 一 由性质3 2 3 有 吼) 单调且有极限万，即；i m c i = 亭，于是可知 l 砸k q + 1 ) = o ，故l 迪矿瓴) = 0 。再根据定理3 2 2 的等价性，可得虿= c + ， 即l i i i l c k = c 。算法的收敛性证毕。 定理3 2 3 和定理3 2 2 的结论证明了本文算法的