（运筹学与控制论专业论文）从随机到确定性的积分型全局优化方法.pdf

摘要 全局最优化问题是运筹学这门学科中的很重要的组成部分，一直受到数学规划 领域内诸多研究学者的广泛关注。全局优化的应用涉及科学技术、军事、工程设计、 自动控制、经济管理等现实世界中的方方面面，有着广泛的应用背景，由此可见， 对全局优化问题的研究具有重要的现实意义。但是由于问题有“全局性”的要求， 使得在求解全局优化问题的算法研究中存在着一定的难度。我们可以求出一个全局 优化问题的局部极小点，但还没有一个有效的全局评判准则来判断一个局部极值点 就是全局极值点。如何在搜索过程中从一个局部极值点跳出，找到下一个更好的局 部极值点，直到求出全局最优点，这也正是全局优化问题所研究的课题之一。 本文作者对郑权、张连生等教授提出的积分型算法作了一系列学习和研究，为 了达到提高已有实现算法的易操作性、易实现性以及算法的计算效率等目标，对实 现算法进行了进一步的改进从而提出了从随机到确定性的积分型全局优化方法， 该方法保持原有方法的优点，避免原算法会产生丢失总极值的缺陷，提高了修正积 分水平集算法的计算效率。且给出该算法的收敛性的证明及算法实现的数值结果， 数值结果表明了该算法是有效的。同时，还对带有约束的全局优化问题作了进一步 研究，应用从随机到确定性的积分型全局优化方法构造了实现算法，证明了实现算 法的收敛性 本文共分三章，第一章主要介绍全局最优化问题的研究现状与应用背景，简要 介绍了部分全局最优化方法。第二章对于郑权等教授提出的积分型全局优化方法给 出简明、系统的介绍，包括问题的提出、问题的实质以及近年来对于该问题的诸多 改进情况。最后一章分五个小节介绍了从随机到确定性的积分型全局优化方法 关键词全局优化；积分一水平集i 从随机到确定性；m o n t e c a r l o 随机投点；一致 分布佳点集 a b s t r a c t s i n c et h eg l o b a lo p t i n l i z a t i o np r o b l e mi sav e r yi m p o r t a n tp a r to fo p e r a t i o nr e s e a r c h g r e a ta t t e n t i o ni sp a i dt o i t b yn l a n yi n v e s t i g a t o r si n t h ef i e l do fm a t h e m a t i c a l p l o g l a m m i n ga t a l lt i m e s t h eg l o b a lo p t i n l i z a t i o nc a nb ea p p l i e di nt h ef i e l do fs c i e n c ea n dt e c h n o l o g y ，m i l i t a r ya f f a i r s ，d e s i g no fe n g i n e e r i n 9 1a u t o m a t i cc o n t r o l ，e c o n o m i c i l l a n a g e n l e n ta n ds oo nw i t hac o m p r e h e n s i v ea p p l i e dp r o s p e c t t h e r e f o r ei t i so fg r e a t i m p o r t a n c et os t u d yt i l eg l o b a lo p t , i m i z & t , i o np r o b l e n l b e c a u s eo ft h er e q u e s to ft h e g l o b a l p r o p e l t i e s ，i t , i sd i f f i c u l tt os t u d yt i l ea l g c n i t l n u st os o l v et i l eg l o b a lo p t i m i z a t i o np r o b l e m w ec a nf i n dal o c a lo p t i m ap o i n tb u tc a n tt e l lw h e t h e rt h a t p o i n ti s ag l o b a lo p t i m a p o i n tw i t h o u t a ne f f e c t i v eg l o b a lc r i t e r i o n i ti so n eo ft h et a s k so ft h eg l o b a lo p t i m i z a t i o n p r o b l e mr e s e a r c ht of i n dab e t t e ll o c a lo p t i m ap o i n tf r o mt h ea n t e r i o ro n ed u r i n gt h e s e a r c h i n gp r o c e s s ，a n df i n a l l yw o r ko u tt h eg l o b a lo p t i m ap o i n t i l lo r d e rt oi m p r o v et h ec a p a b i l i t i e so ft h eo p e r a t i o na n di m p l e m e n t a t i o n ，a n dt h e c a l c u l a t i o ne f f i c i e n c yo ft h ea l g o r i t h m ，t i l ea u t h o rm a k e ss o n i cb e t t e r m e n ta f t e ras e r i e so f s t u d ya n dw o r ko nt h ei n t e g r a lg l o b a lo p t i n l i z a t i o nm e t h o dw h i c hp r o p o s e db yp r o z h e n g a n dz h a n gt h ea u t h o rb r i n g sf o r w a ldam e t h o dn a m e da sa n i n t e g r a lg l o b a lo p t i n l i z a t i o n n l e t h o df r o mr a n d o l nt od e t e r n l i n i s t i cw h i c hr e l n a i n st h eg o o dq u a l i t i e so ft h eo r i g i n a la 1 g o r i t l u n w i l ln o th s et t i 。g h b a lo p t i n m n la n da l s ( ) h a sab e t t e ec a l e u l a t i o ne f f i c i e n c yt h a n t i l en l o d i f i e di n t e r g r a l l e v e ls e t a l g o r i t h m h it h i sd i s s e r t a t i o n ，w eg i v et h ea t t e s to ft i l e c o n v e l g e n c eo fo t u a l g o r i t t n na n dt h en n m b e r i c a lr e s u l t so ft h ei m p l e m e n t a b l ea p p r o a c h a n dt i l en u l n b e r i c a lr e s u l t ss h o wt h a to u la l g o r i t h mi sm o r ee f f e c t i v e w ea l s od of u r t h e r r e s e a r c ho nt h ee o n s t ia i n e do p t i m i z a t i o np r o b l e m a p p l yo u ra l g o r i t h mt oc o n s t r u c ta l l i m p l e m e n t a b l ea p p r o a c h a n dp r o v et h a tt i r ei m p l e m e n t a b l ea p p r o a c hi sc o n v e r g e n t t h ed i s s e r t a t i o nc o n s i s t so ft h l e ec h a p t e r sh ic h a p t e r o n e ，w ei n t r o d u c et h ea c t u a l i t ya n d t i l ea p p t i c a t i o n so ft h eg l o b a lo p t i m i z a t i o np r o b l e m c h i e f l y , p i e s e n tt i l ea l g o r i t h m s o fg l o b a l o p t i n f i z a t i o nt r i e f i y i nc h a t l t e rt w o 。w eg i v eas y s t e m i ci n t r o d u c t i o no ft h e i n t e g r a lg l o b a lo p t i n l i z a t i o nm e t h o d ，i n c l u d i n gt h ep r e s e n t a t i o na n dt i me s s e n t i a l so ft h e p t o b l e m a sw e l la st i l ei n l i ) l o v e l l l e n to i lt h i sm e t l l o di nr e c e l l ty e a l st h e r e i ef i v ep a r t s i l lt i l e l a s t e h a p t e lt h ea u t h o ig i v e si l s aw h o l ei t l t to d , l c t i o no ft i l e i n t e g r a lg l o b a lo p t i i i m i z a t i o nm e t h o df r o mr a n d o mt od e t mm l n i s t i c k e yw 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 ，f l o mr a n d o mt od e t e r m i n i s t i c ，m o n t e c a r l op o i l l t ；s ，g o o dp o i n ts e to ft m i f o ti l ld i s t r i b u t i o n 上海大学 本论文经答辩委员会全体委员审查，确认 符合上海大学硕士学位论文质量要求。 答辩委员会签名： 主任：泓鸳主任：例瞅 委员：劣矗甚 戮 t 诹 导师： 答辩日期： 甄扣妥 一中rt ，叼 职孜堤， j 。e 麓警 单袈 阼二 一一弛 7 工叫髻 k 仃汤。，断柏。， 原创性7 声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期：鱼一车j 第一章概述全局最优化问题 在本章中，首先我们给出全局优化问题在实际生活中的应用，在了解全局优化 问题的研究意义的同时，我们将对到目前为止在全局优化问题的研究发展中较为成 熟的方法作简单介绍，并对作者所做的主要工作作了简介。 1 1 全局最优化的应用 我们都知道运筹学是一门应用性很强的学科，它广泛应用于许多科学技术领域 并为管理者解决实际中所提出的诸多决策问题，为决策者选择最优决策提供定量依 据。 全局最优化问题是运筹学这门学科很重要的组成部分，当今社会大量的社会科 学和自然科学中出现的问题都可以归结为求一全局优化问题的解。也就是说在科学 技术，工程设计，经济管理等方面遇到的一些需要决策和分析的问题都可以从中抽 象出全局优化的数学模型并加以求解。 通常一个全局优化问题可以表述为：给定一个n 维欧氏空间的非空闭集d ， 及一个连续函数，：r ”- r ，寻找一个点z 4 d ，满足，( z 8 ) ，( 。) ，对所有 m d 。即 咖6 嬲，( 。) 。 我们来看下面这样一个问题 例题( 生产运输计划) 某种产品由r 个工厂生产，每个厂的生产成本各不相同， 用仇( z ) ，i = l ，2 ，表示第i 个厂生产f 单位产品的成本；需要该产品的部门有m 个，每个部门的需求量分别是d ，= 1 ，2 ，n ；从第i 个工厂把产品运到第，个 部门的单价为c 。i = 1 2 、r j = 1 ，2 ，m ，此外，如果某个部门j 收到的产品 量为f ，而且t d 。，则需要支付缺货费用，用 ，( t ) ，【o ，由) 表示，它是一非负 单调递减函数。问如何制定计划，使得总费用最少? 这是在经济活动中常见的，需要生产组织者给予决策的问题，问题的常见性表 明它是经济活动中普遍存在的。如何较好地锯决这个问题，使生产厂家按照合理的 生产计划，达到总费用最少的目的呢? 为了帮助决策者傲到最大程度地减少成本的 目的，我们可以将这样的一个实际问题，抽象概括归结为如下一个全局优化问题： m i n ：l 凳1e i j z i 3 + 釜l 吼( 叭) 十筘1 ( 勺) s t 凳l 。u = y i ( i = 1 ，2 一，r ) 暑lz u = 勺( j = 1 ，2 ，m ) 。玎，y 勺0 ，v z ，j 通过已有的相关的求懈全局优化问题的工具软件，我们可以给出这个问题的答案， 将它应用到实践，指导生产，便可以帮助生产组织者完成节省成本，最终是使利润 值增大的目的 前面所提到的在生产运输计划中的应用只是全局优化应用范畴中的一个案例， 全局优化广泛地应用于科学技术、军事、工程设计、智能控制、经济管理等现实世 界中的方方面面。由此可见，全局优化问题的现实意义还是很重要的自然地，求 解全局优化问题就成了人们关注和有着广阔前景的领域。但是由于问题对于“全局 性”的要求，使得在求解全局优化问题的算法研究中存在着一定的难度虽然非线 性规划在解决局部极值上是非常成功和有效的，但并不能成功的解决全局最优化问 题。根据条件我们可以求出一个全局优化问题的局部极小点，但还没有一个有效的 全局评判准则来判断一个局部极值点就是全局极值点。如何在搜索过程中从一个局 部极值点跳出，跳到下一个更好的局部极值点，直到找到全局最优点，这正是全局 优化所关注研究的课题之一。 5 1 2 全局优化问题研究的主要方法 全局优化算法总的来说可以分为两大类：一类是确定性算法，另一类是随机算 法和启发式算法。目前，确定性算法研究的比较多的是具有特殊结构的全局优化问 题。如在dc 规划和单调规划方面取得比较成功的探索，dc 规划和单调规划也 是当今研究全局优化确定性算法的主流方向之一。与此同时，二次规划与多项式规 划在近几年由于其广泛的应用背景也得到了广泛的重视并取得了一系列成果当目 标与约束函数均为非凸函数时，一般的数学规划的全局优化问题仍然是全局优化中 最具挑战性的课题。随机算法适用于确定性算法无法应用的全局优化问题。这些方 法一般仅需非常弱的假设，而且至少能够提供概率收敛的框架。随机算法主要分成 三类：二阶段法，随机搜索方法，随机函数方法。启发式算法通常是通过模拟生物 进化，人工智能，数学与物理科学，神经系统和统计力学等概念，以直观为基础构 造的。主要包括禁忌搜索，模拟退火，遗传算法，人工神经网络等。 2 下面我们对其中部分算法做简要的介绍 1 特殊结构的全局最优化问题和算法 *d c 规划 当优化问题中的目标函数和约束函数都可以表示成两个凸函数之差时，我们称 这类规划问题为d c 规划问题。下面是d c 规划中的一些性质： - 任意一个定义在月“的紧凸集上的二次可微函数为d c 函数 任意一个定义在r n 上的二阶连续可微函数为d c 函数。 设，l ( 。) ，一，m ( 。) 为是d c 函数，则函数翟l 九 ( z ) ，( 凡r ) ，n 2 1 五( z ) ， m a x l m ( 。) 以及m i n l ： 。 ( z ) 均为dc 函数。 利用上述性质，每一连续规划问题可以化成一个带线性目标函数及不多于一个 凸和一个反凸约束的d c 规划问题，详细内容可见文献 1 d c 规划问题可用外逼近方法来解。外逼近方法最早应用于解凸规划问题，后 来被成功地应用于凹规划，反凸规划及dc 规划问题等，文献参见( 阮 3 4 卧 6 ) 。在优化领域特别是组合优化中，已经成为一种基本的方法。外逼近方法的主 要思想是通过建立一系列的凸多面体p 1 ， p n 不断逼近可行域s ，使得用问 题m i n ( x ) iz p k ) 的解逼近于m i n f ( x ) lz s ) 的解。 * 单调全局最优化 单调优化是具有特殊结构的一类全局优化问题，在经济、工程及其他一些领域 中大量数学模型通常都具有某些变量或所有变量的单调性的性质。在最优设计的相 当多数量的文章中，单凋性在数值方法的研究中起着相当重要的作用。当单调性与 凸性和反凸性结合在一起时，产生了乘积规划 7 ，c 一规划 8 等等低维的非凸问 题。 下面我们考虑这样的问题： l n i n ( ，( z ) ig ( z ) 1s ( z ) ：z r ；) ， ，( 1 2 ，1 ) 此处，( z ) ，g ( z ) ， ( z ) 都是单调增加的。此类问题在某种特殊假设下，可由广义 外逼近方法来处理。然而，纯单调结构的最重要的优点在于利用全局信息，通过在 可行域的限制区域上的极限的全局搜索，可以用来简化问题。事实上，当f l21 ) 的 目标函数是单谣增加的，若z 为可行域已知的可行点，因在z + 螂没更好的可行 解，故z 在z + 月；上为不起作用的。类似地， _ 4 _ f f q 数9 ( z ) ( 相应地h ( x ) 1 ) 为不 可行点，则整个z + _ r ：可以不予考虑。基于上述观察，外逼近或分支定界等有效方 法可以用来求解易处理的单调规划 * 二次规划和多项式规划 当优化问题中的函数都是二次函数时，此类问题我们称为二次规划问题。有一 部分的非凸二次规划可以通过真正有效的算法求解，这其中对较弱的非凸性的乘积 规划相当有效此外，用这些方法求在椭球上的不定二次规划也可找到局部的非全 局的最优解非凸二次规划是一非常困难的问题，就目前情况而言，求解此问题的 最有效的方法为分支定界方法。分支定界法是求解最优化问题中使用的较为广泛的 一种方法，较多的用来解组合最优化和整数规划问题。该方法的主要思想是在任何 给定的细分集m 上计算下界； 厂玉im i n o ( z ) i ( z ) 0 ，( i = 1 ，- ，m ) ，z m n x ) ，( 1 2 2 ) 因此可通过( 1 2 2 ) 子问题松弛求解，从而找到函数的总极值。该方法主要应用于凹 规划，d c 规划和l i p s c h i t z i a n 规划。文献参见( m 1 0 h 2 】， 1 t ， 1 2 ) 。 由于多项式可以表示成为两正系数多项式之差，故多项式规划为一di ( d i f f e r e n c e o ft w oi n c r e s s i n gf u n c t i o n s ) 最优化问题，则多项武规划可由解单调规划的多面体块 逼近方法求解。 2 一般形式的全局最优化问题和算法 对于一般形式的全局优化问题，常见的算法有积分水平集方法、填充函数法 随机算法和启发式算法。 * 积分水平集方法 此方法由郑权等提出，文献参见( 【1 3 【14 ) ，其突出的优点是思想简明直观， 对目标函数和约束函数的限制较小( 只要求函数连续) ，应用范围较广，数值例子说 明该方法是一种较为有效的全局优化方法，我们将在第二章给出较为细致的介绍。 4 * 填充函数方法 该方法是g e ( 15 】t 1 6 1 f 1 7 1 ) 及g e 和q i u ( f 1 8 】) 所作的工作其主要思想 是：首先应用求局部总极值问题的方法，解出，( z ) 的一个局部极小点。i ；通过构 造填充函数找到问题的另一局部极小点。；，该点满足，( z ；) ，( z i ) ，从而最终找 到函数的全局最优点。 t 禁忌搜索算法 禁忌搜索( t a b us e a r c h ) 算法是局部领域搜索算法的推广( 1 9 ) ，是人工智能 在组合优化算法中的一个成功应用。g l o v e r 2 0 】在1 9 8 6 年首次提出这一概念，进而 形成了一套完整算法，详见( 2 1 】， 2 2 ) 。该算法的特点是采用了禁忌技术。所谓禁 忌技术就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的不足，禁 忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用 禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。 + 模拟退火算法 模拟退火( s i m u l a t e da n n e a l i n g ) 算法是局部搜索算法的拓展( 1 9 ) 。它不 同于局部搜索之处是以一定的概率选择邻域中费用值大的状态理论上来说，它 是一个全局最优算法。模拟退火算法最早的思想有m e t r o p o l i s 2 3 在1 9 5 3 年提出， k i r k p a t r i c k 2 4 在1 9 8 3 年成功将其应用到组合最优化中。 * 遗传算法 遗传算法( 【1 9 ) 是模拟生物在自然环境中的遗传和进化过程而形成的一种自 适应全局化概率搜索算法。它最早有美国密执安大学的h o l l a n d 教授提出f 2 5 1 ，起源 于6 0 年代对自然和人工自适应系统的研究。7 0 年代d e3 0 n g 基于遗产算法的思想 在计算机上进行了大量的纯数值函数优化计算试验。在一系列研究工作的基础上， 8 0 年代由o o l d b e l g 进行归纳营、结，形成了遗传算法的基础框架。 * 人工神经网络 人工神经网络( 1 9 】) 的早期工作可以追溯到1 9 4 3 年m c c u l l o c h 和p i t t s 2 6 建立 的第一个模型，后被扩展为“认知( p e r c e p t l o n ) ”模型。2 0 世纪8 0 年代，h o p f i e l d 2 7 5 2 8 将人工神经网络成功应用在组合优化问题， m c c l e l l a n d 和r u m e l h a r t 2 9 构造 的多层反馈学习算法成功解决了单隐含层认知网络的“异或”问题及其它的识别问 题，他们的突破使得人工神经网络成为新的研究热点。 5 1 3 本文主要工作 作者通过对由郑权、张连生等教授提出的积分型算法的一系列学习和研究，为 了提高已有的实现算法的易操作性、易实现性以及算法的计算效率的目标，对实现 算法进行了进一步的改进，从而提出了从随机到确定性的积分型全局优化方法，该 方法保持原有方法的优势，避免会产生丢失总极值的缺陷，提高了修正积分水平集 算法的计算效率。且在文中作者给出从随机到确定性的积分型全局优化方法的收敛 性的证明与算法实现的数值结果，数值结果表明该算法是有效的。同时，还对带有 约束的全局优化问题作了进一步研究，应用从随机到确定性的积分型全局优化方法 构造了实现算法，证明了该实现算法的收敛性。 6 第二章积分型方法求全局优化问题 在第一章里，我们提到了积分方法，其突出的优点是思想简明直观，对目标函 数和约束函数的限制较小( 只要求函数连续) ，应用范围较广。在本章里我们对积 分方法作进一步介绍，介绍其概念算法及其算法的主要思想，同时介绍一些学者对 于积分型方法的有关改进工作。 l2 ，1 积分型方法的提出 我们考虑的全局最优化问题如下： ( p )c + = m 唼，( 。) r l j ( 2 ，11 ) 其中dcr “是有界闭箱，：r “_ r 1 上的连续函数，c + 为f ( x ) 在d 中的总极 值。 1 9 7 8 年郑权教授等发表了题为“一个求总极值的方法”的论文( 1 3 ) 。文章提 出了求总极值的积分一水平集方法，给出了求解全局优化问题的一种新的思路。 首先我们给出积分一水平集方法的主要步骤： 步1 取跏d ，给定一个充分小的正数e ，令c o = f ( x o ) ，h c 。= 。dlf ( x ) 。0 1 ，= 0 且令 步2 若肛( 风。) = 0 ，则c k 为总极值，凰。为总极值点集，转步6 ；否则转步3 。 步3 计算均值 2丽1ck+ik 沁脚 2 i ；_ i 百：1 | h7 j 3 j d “ h e 。+ ，= ( z d 【，( z ) c k + 1 ) 步4 计算均方差 = 志厶。( m h 咖 步5 若v f e 则令k ：= k + 1 ，转步3 ；否则，转步6 步6 令，4 = c _ - l ，且h 8 = 日。终止。+ 为，( z ) 在d 中的近似总极值点 集，+ 为相应的近似总极值。 对于算法中提到的相关符号表示，参考定义2 2 1 。 2 2 积分型方法的主要思想 从上述的积分一水平集方法的步骤，我们可以大致了解该算法的思路。通过对 文献( 1 3 ，f 1 4 ) 的阅读与学习，我们认识到：积分一水平集方法其实质是实分析 中积分中值定理的应用。为了说明这一思想，我们首先回顾一下积分中值定理及其 几何意义。 定理2 21 设函数，( z ) 在【n b 】上连续( 不妨设，( z ) o ) ，则在h b 】中至少存 在一点，使得 i f f ( z ) d r = ，( ) - ( b - a ) 积分中值定理的几何意义可以简述为： 的面积来求得曲边梯形a b e f 的面积。 可以通过计算一个以。6 为边的长方形a b c d 如图( 2 21 ) 。 图( 2 2 1 ) ：积分中值定理的几何意义 不难知道，亡i 它f ( x ) d x 为函数在区间 a i6 】上的积分平均值。此处 8 +l|10llil4 胀) = 再1 办批 其中n 曲f ( z ) ，( ) c + = m i n ，( z ) ，令 m ( f ，c ) = 志厶。m ) 咖 称m ( ，c ) 是函数，在水平集h 。的均值。 令 川“) = 志i f o m ) 叫2 如 称h ( ，c ) 是函数，在水平集玩上的均方差。其中 皿= z dif ( x ) c ) 为函数，关于c 的水平集。 从图( 2 2 1 ) 可知： 1 水平集 日，( ) = ( 。i ，( ) s ，( ) ，z 【0 ，翻) 亍 t ；t ，叫u 晤，( u u ，卅 2 ，令p ( 嘶( f ) ) = ( 1 一n ) + ( 一f ) + ( 6 一u ) ，其中肛( 日玳) ) 为h s ( f ) 所包含的任 何长度。 i 面我们利用积分中值定理及水平集的基本概念来阐述郑权教授求最大值和最 小值的积分一水平集方法的思想本质。 若设h e 。= ( zi ，( z ) c 。 n ，6 】) ，由郑权教授的方法构造一个迭代序列： c k + l 2 高厶。f ( z ) d x2 币丽厶。 由于z 鼠时，( 。) 茎c 故 c 曼志厶c k d x。曼砸可k f 2 2 1 1 ( 2 2 2 ) 即h ) 为单调下降序列。此外，由闭区间连续函数的性质可知：，( z ) 在 。b 上一 定有最大值肘和最小值m ，即，ns ，( z ) m 。于是 一志n r a d x _ 志厶。m ，a 。s 志厶。m a z = 旭。s ， 所以 ) 为单调有界数列，故h ) 必收敛，不妨设收敛于c 8 。 由( 2 21 ) 及连续函数的介值定理可知：对每一。+ l 一定存在靠+ 1 ( n ，b ) ， 使得，( “+ j ) = c + ，且，( f = + ) = c 女+ 1 _ c + ( _ 。) 。但是此处的 & ) 未必趋 于f 9 ，然而由 “ 的有界性可知：必有( 靠) 的子序列 矗。) ，当_ 。时， 。- ，f + ( n ，6 ) 。即当女_ 时，矗。+ 使得 且聪。 通过上面的介绍我们可以了解到，求解最小、最大值的积分水平集方法的实质 就是利用积分中值定理确定一个水平集，然后构造一不超过该水平值的水平集合， 在该水平集上再求均值。由于此水平集所包含区域要小于原先给定的区域，且在这 样的区域上的函数值不超过上一个均值，因此在新的水平集上的均值变小，以至于 最终逼近区间上的最小值同时我“ 给出几个主要定理： 定理2 2 2 设函数，( z ) 在k6 上连续，h 。= z l f ( z ) sc ，。hh i 0 ，若 肛( 凰) = 0 ，则c 为，( 。) 在h 嘲上的最小值，相应的点集凰为，( z ) 在h 胡上的 最小值点集。 定理22 3 设函数，( c ) 在k 剀上连续， c ) 是由( 221 ) 构造的序列，则 1 ) - c + _ “ 2 ) 如5 里凰 _ l i r a 。且t 。l i m 2 3 积分型方法的一些进展 1 0 郑权教授提出的积分型全局优化方法具有很好的收敛准则，且仅需计算目标函 数值，故适用于较大范围的总极值问题，但由于水平集h c 。不易求得，原始文献 ( 1 3 、 1 4 1 ) 中采用了m o n t e 。c a r l o 随机投点取得近似水平集并缩小搜索范围实现 其概念算法，很大程度上容易丢失总体极值。 在此基础上，1 9 9 6 年张连生等提出了离散均值- 水平集方法参见文献( f 3 0 1 ) ， 主要的思想是利用多点搜索途径，在好点的邻域中多投点，在坏点的邻域少投点， 从而提高了计算效率，同时给出了算法的终止准则，证明了该算法的收敛性。 为了避免郑权教授的求总体极值的积分一水平集方法与其实现算法的不一致 性。邬冬华等利用数论中一致分布替代m o n t e c a r l o 随机投点构造实现算法，给出 了一种修正的求总极值的积分水平集算法，并给出了该修正方法收敛性证明。参 见文献( 【3 1 1 ，【3 2 j ，【3 3 ) 。 第三章从随机到确定性的积分型全局优化方法 在本章中我们将主要介绍从随机到确定性的积分型全局优化方法，给出具体的 实现算法以及算法收敛性的证明，最后给出算法实现的数值结果。 53 1 背景知识 为了证明我们实现算法的收敛性，在这一节，我们先引进一些概念和数论中一 些结论。不失一般性，我们假设下面所讨论的有界闭箱均为单位有界闭箱g g ： 0 1 卜。 1 相关概念 定义31 1 令( 口) z ：- 上j 2 0 = z ! ? i 。：；= 1 为g n 的任意分割，设，( 叭。) 在g 。上有定义，且 “( 一h 。k “l _ f “) = 热h ，：a ，) 一，( 玑c z - “函；) l 曼 ：l n 忆。，( 钆z 麓1 ，z 等，z 。) = ，( 钆。z _ ，。等z 。) 一，( 钆。z ，“，z 等，。) 一( 饥，z h _ 鼍“，+ ( z i ，+ 1 ，z 等“，一。) 1 七1 七。 礼 1 2 趣m a ，* m ，( 钆，。z 1 ，z 麓2 ，z 静，z n ) 2 m ”_ 神h z 静，z “) 一m ，柚麓1 “，z 等，z 静，训 一m m 一“一z 等“z 柳，) + m ”，省“，z 等“，。翟，。) + + ( 一1 ) ”1 ，( z ，、。麓，。等+ 。，z 麓+ 1 ，。) + ( 一1 ) ”f ( x l ，z 麓1 ，z 等，一船“，z 。) 1 h 七2 k 。 r l 若变差 f l l 2 1 k = il 2 0 。2 = 0 + k 1 - - k 萎21 洲 l k l b ! n 2 。l = 0 i k 2 = o “一i + m l 、， 1 l s n i k ，= o z 等+ 1 ) 磅+ 1 ) 亨二耋爹掣) 无关的上界，则称，( z j 为h a r d y k r a u s 意义下的围变函数。的 上确界称为，( 。) 的全变差，记为矿( ，) ，其全体记为b 。 若设 0 兰。? f “茎1 且存在绝对常数l 使得 1 3 n 0 z n o ，l 一 坤2 2 孝 z l (i f + ，) 一 n 1 十 一 m 2 2 z i ，m ；| ， 一 十 = 世2 ， + 十 q 2 地2 t 茁 p ，z 一，j n n 一 一 十 十 篇 z _ 霎船 z h z ”一 峥妒旷旷 一 娃k i 娃o ( 1 ) m ，1 ：。z r 一1 ，1 ) 1 茎l ( z z l “一谢) i k l 茎n ( 2 ) i 也，( 1 1 , x 琶，i ，1 ，。忿1 ，1 ) 】 l ( z 1 r z 一) ( z 等一) 1 l 2 7 。 ( m ) i 趣胁，。，( 1 ，1 ，。z 1 ，1 ，l ，。等，z 麓，1 ， 三( z 乏1 “一搿) ( 蜚+ 1 一z 等) 扛鼢“一z 等) 1 k l ：2 m ” l ( x 1 1 + 1 一z i l l ) ( z 芋+ 1 一z 孑) ，( 。：。+ l t 帑) 则称j ，( z ) 满足广义局部l i p s c h i t z 条件，此种函数全体记为l 定理31 1l 。cb 证明：若f l 。，则 + 。j 一沁l ( 一等+ z 跚z 。i k i , 州一z 等) ( 。静+ 1 一i k 。z ) s 上( 哪+ + e ? 十+ 暖+ 锈) = ( 2 “一1 ) 三 故f 且，即得l 。cb 。 事实上，若，( z ) 满足 1 4 h n z一 + h ” o 比2 z一 ”2 zz z l + 一 h 一一 旷旷 l o 旷旷 k啪 外 l 0 一 产 卸 h 川旷铲虾蜓 l l 笪盟【 l i d _ ，l 矿，i ，r 瓦瓦l “ 1tn l z i n 鑫iox i 1 a z 2 a o n 一 则，( 。) l 。，下面讨论的函数均满足上述条件。可见b 。是一类范围很广的函数类。 2 数论中的相关结果 下面介绍数论中的相关结论。令1 为一正整数，且 为g 。中的一点集 p f ( m ) = ( z l ( ) ，。5 ( ) ，：( k j ) ，1 k f 定义3 1 2 对于任意7 = ( 7 1 忱，) g 。，设n l ( 1 ) = nl ( 1 ，一， 。) 表示 p t ( k ) ( 1 k 茎f ) 中适合不等式 的个数。若 0 z i ( 矗) 1 1 、，0 z ：( 纠 m 。 s u pi 掣一川i ：妒( 2 ) 1 7j ： ， 1 g 。 则称点集最( k ) ( 1s 51 ) 有偏差妒( f ) ( 3 4 ， ? 】) 定义3 l3 设似) 为一整数序列 对于每一) ，有e ，。中的一个点集竹。( ) ( 】 ：茎f ，) 与之对应，且有偏差p ( k ) 。 1 5 若( 以) = o ( 1 ) ，则称点集只。( 纠( 1 f 1 z 2 ) 为一致分布且有偏差妒( b ) ( 3 4 ) 。 定义3 14 设7 g 若形如 的点集存在偏差 p ( 女) = 7 l 女 ， 女 ) ，女= 1 ：2 ，t ，# ，( 31 1 ) 妒( f ) = c ( 1 ，d ) f 一1 + 6 ( 3 12 ) 则称点集( 3 1 1 ) 为佳点集，即所得点集列的最佳分布点集列，而7 称为佳点( f 3 4 1 ) 。 定理3 12 使点集( 3 1 1 ) 存在偏差( 3 1 2 ) 的点7 g 。的l e b e s g u e 测度为l 。 证明：参见文献( 3 4 】) 。 定理3 13 设p f ( 纠( 1 f ) 为存在偏差妒( f j 的点集，若，b 。，则 i 1 ，( 日( i v ( ，) 妒( f ) 。 = j 其中t 3 n 为h a r d y k r a u s 意义下的有界变差函数集，v ( ，) 为 ( x ) 在g 。上的有界全 变差。 证明：参见文献( 3 4 】) 。 推论31 1 条件如上述定理相同，对于任意小的正数d 当z _ o 。，妒( 。) _ + 0 即 r1 f g 。“叫嘶”三们( m ( h 毗 注：关于一致分布佳点集列的具体构造请参考文献( 3 4 】) 。 32 从随机到确定性的积分型全局优化方法 随着计算机技术的飞速发展，算法在计算机上的易操作性及易实现性，也成为 一种算法是否优越的评价准则。出于此方面的考虑，作者提出了一种从随机到确定 1 6 性的积分型全局优化方法。 我们的方法是积分型全局优化方法中的m o n t e c a r l o 随机投点与确定性的数论 方法相结合。在数论一致分布计算以前，先用m o n t e c a r l o 随机投点计算，当函数 值f ( x ) 充分下降后，再用确定性的数论方法计算并实现终止。既提高了修正算法的 计算效率，又保证了算法的收敛性。 算法的主要思想是：在第k 步，当求得均值c 和水平集峨。之后，构造一个 新函数： ，。f c ， z d h c 。 户jm ) 。 显然，它与原目标函数具有相同的总极值，用函数厶( z ) 来求均值，其积分区域是在 闭箱_ d 上，而无需在水平集上求均值，避免了求水平集上的积分时也。的求解，并 保证了不丢失总极值。在实现算法中，利用多种数学工具中常用的调用m o n t e c a r l o 随机函数选取随机点，使用了随机方法避免了在修正算法中初值由构造佳点集再进 行数值计算这种方法的繁杂性。将初值c o 尽量优化，使f ( x ) 充分下降后，再使用 数论一致分布的确定性方法求解、验证，找出全局最优值f ( x 4 ) 及最优解z + 。这种 从随机到确定性的积分型全局优化方法，既不会产生丢失总极值的情况，又提高了 修正积分水平集算法的计算效率，后面我们还将给出算法收敛性的证明。 在给出具体算法之前我们给出如下假设： 假设1 f 在d 上是连续的。 假设2 存在一个实数c ，使得水平集 h e = t r “l ，( 卫) 茎c 与d 的交集非空而且为紧。 定理3 2 1 在假设l 和假设2 的条件下，如果i z ( h 。) = 0 ，且h 。d ，其中 皿= z dj ，( m ) c ，“为l e b e s g u e 测度，那么c 为，( z ) 在d 上的总极 值，h 。为总极值点集。 1 概念算法及收敛性 概念算法32 1 步1 ：给定一充分小的正数e ，取x 0 d 。令c d = f ( x o ) ，h c 。= ( 。d l f ( x ) 。o j ：= 0 。 步2 ：若“( 爿0 ) = o ，那么c j 是全局最优值，h q 为全局最优值点集，转步6 否则转