（运筹学与控制论专业论文）积分型总极值方法理论的发展及其并行算法.pdf

摘要 最优化问题从产生到现在，众多的学者和数学家已经提出和总结了许多的最 优化方法。但应该指出，目前大多数的算法求得的都是局部极小点，仅当问题具 有某种凸性时，局部极小点才是全局极小点。一般来说求全局极小点是一个相当 困难的任务，其中的难点又在于最优性条件的给定。 我们讨论如下形式的最优化问题： 设x 是拓扑空间，s 是x 的非空子集，实值函数f ：x - 冗。求全局最优值 c = i n f f ( x ) ，( 0 0 1 ) z v 及其全局最优点集 h = z sif ( x ) = 矿( 0 0 2 ) 我们对讨论的问题作如下基本假设： ( a ) ：函数，是下半连续的，集合s 是闭集，而且存在一个实数b 使得 集合g b = z si ， ) 6 ) 是非空紧集； ( r ) ：函数，在s 上是上丰满的，即对于所有的c ，集合 z s i s ( = ) 0 ，且对于所有的紧集k ，都有p ( k ) 矿= 皿s ，( z ) 。函数，在其水平集日cn s 上 的僻均值： m l ( f ，c ；s ) = 硒b 厶n s r e ( f ( 训咖( 0 - 0 3 ) 函数钉：r 1 一冗1 被称作伊函数，如果它满足下面的条件： 1 ( ) 是非负函数而h v ( y ) = o 当且仅当y = 0 。 1 2 v ( - y ) = u ( 可) 。 3 当秒0 ，函数v 连续严格递增 函数，在其水平集皿n 。9 上的伊方差： 1 ，- 眦c ；s ) 2 南厶n s 钉( m ) 一c ) 舡 ( 咖4 ) 最后给出最优化问题的最优性条件： 在( a ) 、( m ) 、( r ) 的假设成立之下，点矿s 是函数，在集合s 上的全局最小 点且c + = f ( x + ) 是全局最小值当且仅当下面两个条件中的一个成立： i ) 僻均值条件( m - m e a nv a l u ec o n d i t i o n ) 尬( ，矿；s ) = m ( c ) ； i i ) 钞一方差条件v - v a r i a n c ec o n d i t i o n ) ：v l ( f ，矿，s ) = 0 整个论文的结构如下： 第一章，我们简要回顾了全局最优化问题的提出和发展以及目前国内外关于 这个问题的研究工作状况。给出了全局最优解的定义。介绍了郑权教授提出的求 解全局最优解的积分总极值法。 第二章，我们引入了丰满集、丰满函数和q - 测度空间等概念。通过丰满分析， 我们知道，在积分型算法中，目标函数，不一定要是连续的。 第三章，为了能够使积分总极值方法能够更有效地应用在处理最优化问题的 情况，我们引进积分总极值中胁均值和伊方差等概念，发展了积分型总极值的最 优性条件并给出了算法。 第四章，对求解有约束的最优化问题。我们借鉴罚函数的概念，利用不连续 精确罚函数的概念对积分总极值方法进行了推广。给出了处理有约束最优化问 题的积分总极值罚函数最优性条件及其算法。 第五章，我们给出了变测度积分总极值方法。讨论了在无限维空间中，如何 用有限维子空间的全局最优值去逼近无限维空间中的全局最优值。引用t q 一测 度收敛和变测度的概念，定义了在此概念下的册均值和伽方差，并推导出变测度 意义下的最优性条件。同时还给出了算法，并验证了其收敛性。 第六章，给出了变测度的罚函数积分型方法。对于无限维空间中的有约束的 问题，我们引入不连续罚函数的方法，使有约束问题化为无约束问题求解。 i i 第七章，大规模并行计算则成为研究科学与工程技术的一种崭新的手段和方 式。在前面的研究中，我们发现积分水平集算法在应用并行计算得以实现时，对 求解大规模问题具有独特的优势，为此在这一章中我们在这个方面进行一些研究 和探讨。 关键词：全局最优解丰满分析积分型总极值理论m 均值伽方差总极 值的最优性条件积分型总极值算法不连续精确罚函数变测度方法 i i i a b s tr a c t t h ep r o b l e mc o n s i d e r e di nt h i sd i s s e r t a t i o ni sh o wt oc h a r a c t e r i z ea n df i n d t h eg l o b a lm i n i m u mv a l u ea n dg l o b a lm i n i m i z e r so fa no b j e c t i v ef u n c t i o ni n 即 a n df u n c t i o n a ls p a c e l e txb ea t o p o l o g i c a ls p a c ea n df ：x _ r ar e a l - v a l u e df u n c t i o n c o n s i d e r t h ef o l l o w i n gm i n i m i z a t i o np r o b l e m ： c = i ng e n e r a l ，m i n i m i z e r so f ( 0 0 5 ) m a yn o te x i s t u n d e rt h ea s s u m p t i o n ( a ) ：，i sl o w e rs e m ic o n t i n u o u s ，xi si n f - c o m p a c t ( 0 0 5 ) m i n i m i z e r so f ( 0 0 5 ) e x i s t t h ep r o b l e mo fm i n i m i z i n gaf u n c t i o nh a sb e e ni n v e s t i g a t e ds i n c et h es e v e n - t e e n t hc e n t u r yw i t ht h ec o n c e p t so fd e r i v a t i v ea n dl a g r a n g i a nm u l t i p l i e r t h e g r a d i e n t - b a s e da p p r o a c ht oo p t i m i z a t i o ni st h em a i n s t r e a mo ft h a tr e s e a r c h h o w - e v e r ，t h er e q u i r e m e n to fd i f f e r e n t i a b i l i t yr e s t r i c t si t sa p p l i c a t i o nt om a n yp r a c t i c a l p r o b l e m s m o r e o v e r ，i tc a no n l yb eu t i l i z e dt oc h a r a c t e r i z ea n df i n da l o c a ls o l u - t i o no fa g e n e r a lo p t i m i z a t i o np r o b l e m i nt h i sd i s s e r t a t i o n ，w ea p p l yt h ei n t e g r a lg l o b a lo p t i m i z a t i o nt e c h n i q u et oi n - v e s t i g a t eam i n i m i z a t i o np r o b l e mw i t hd i s c o n t i n u o u so b j e c t i v ef u n c t i o n i n t e g r a l g l o b a lo p t i m i z a t i o nt e c h n i q u ei sav e r yp o w e r f u ly e tf l e x i b l et o o lt ot r e a tv a r i o u s o p t i m i z a t i o np r o b l e m s w ef i r s tr e c a l lb a s i cc o n c e p t so fr o b u s ts e t s ，f u n c t i o n sa n dt h ei n t e g r a la p - p r o a c ht og l o b a lm i n i m i z a t i o n w i t ht h ei n t e g r a la p p r o a c ht og l o b a lo p t i m i z a - t i o n s e v e r a ln e wo p t i m a l i t yc o n d i t i o n sf o rg l o b a lm i n i m i z a t i o na r es t u d i e d u 8 - i n gf f - m e a nv a l u ec o n d i t i o no n e c a nd e s i g na l g o r i t h m sf o rf i n d i n gu n c o n s t r a i n e d g l o b a lm i n i m i z e r s w i t hv - v a r i a n c ec o n d i t i o n o n ec a n s e ts t o p p i n gc r i t e r i o n a c l a s so fd i s c o n t i n u o u sp e n a l t yf u n c t i o n si sp r o p o s e dt os o l v ec o n s t r a i n e dm i n i - m i z a t i o np r o b l e m sw i t ht h ei n t e g r a la p p r o a c ht og l o b a lo p t i m i z a t i o n o p t i m a l i t y c o n d i t i o n so fap e n a l i z e dm i n i m i z a t i o np r o b l e ma n dan o ns e q u e n t i a la l g o r i t h m i sp r o p o s e d n e wo p t i m a l i t yc o n d i t i o n so ft h ei n t e g r a lg l o b a lm i n i m i z a t i o na r e a p p l i e dt oc h a r a c t e r i z eg l o b a lm i n i m u mi nf u n c t i o n a ls p a c ea sas e q u e n c eo fa p - p r o x i m a t i n gs o l u t i o n si nf i n i t e - d i m e n s i o n a ls p a c e s av a r i a b l em e a s u r ea l g o r i t h m i su s e dt of i n ds u c hs o l u t i o n s f o rac o n s t r a i n e dp r o b l e m ，ad i s c o n t i n u o u sp e n a l t y m e t h o di sp r o p o s e dt oc o n v e r ti tt ou n c o n s t r a i n e do n e s t h ei n t e g r a la l g o r i t h m c a nb ei m p l e m e n t e db yap r o p e r l yd e s i g n e dm o n t ec a r l om e t h o d n u m e r i c a l e x a m p l e sa r eg i v e nt oi l l u s t r a t et h ee f f e c t i v e n e s so ft h ea l g o r i t h m t h ei n t e g r a lg l o b a lm i n i m i z a t i o na l g o r i t h mi sa l s oi m p l e m e n t e do np a r a l l e l c o m p u t e r ，t h er e s u l t ss h o wt h eg r e a ta d v a n t a g eo ft h ei n t e g r a la p p r o a c h i v 、l， z ，fl，j fn z l k e yw o r d s g l o b a lm i n i m i z a t i o n ，r o b u s ta n a l y s i s ，i n t e g r a lg l o b a lo p t i m i z a - t i o nt e c h n i q u e ，m - m e a nv a l u e ，v - v a r i a n c e ，o p t i m a l i t yc o n d i t i o n s o fg l o b a lm i n i m i z a t i o n ，d i s c o n t i n u o u se x a c tp e n a l t yf u n c t i o n ，v a r i a b l e m e a s u r em e t h o d 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研 究工作。除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已发表和撰写过的研究成果。参与同一工作的其他 同志对本研究所做的任何贡献均已在论文中作了说明并表示 了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定， 即：学校有权保留论文及送交论文复印件，允许论文被查阅 和借阅；学校可以公布论文的全部或部分内容。 签名幽师张丛日期：一 4 上海大学博士学位论文 第一章绪论 近四十多年来，随着工程和科学的进步，人们在全局最优化的理论和算法的 研究方面，倾注了大量心血，也得到了显著的发展。全局最优化理论和算法的应 用涵盖了非常广泛的领域，其中包括经济建模、固定费用问题、金融、运筹学、统 计学、结构优化、网络和运输、数据库和芯片设计、图像处理、核能和机械设计、 化学工程设计和控制、分子生物学以及环境工程，等等。众所周知，在这些领域 中，人们获得了显著的进步。这当中也包括了郑权教授提出的求解全局最优解的 积分总极值法。 1 1 总极值的发展和趋势 历史上最早关于总极值这方面的文献记载是：要求寻找一条已知长度的曲 线的形状，使之与一条已知线段能围绕最大的面积。a r c h i m e d e s 推测这条最优 曲线是一个圆。他的猜测是正确的。一百年以后，大约是公元前1 0 0 年，h e r o no f a l e x a n d r i a 猜测光线是按照最短路线( t h es h o r t e s tp a t h ) 行进的。直至1 j 1 6 5 7 年，f e r m a t 才正确推导出其实光线是按照最短时i 日- ( t h el e a s tt i m e ) 行进的，而不是按照最短 路程行进。 另外一个总极值的基本问题是如何选择函数( 族) ，使之能最小化已知泛函。 在n e w t o n 时代人们就提出了两类在这方面非常具有代表性的问题。第一类问题是 寻找一条曲线，使得旋转这条曲线所产生的立体的旋转体在某一重力场下运动时， 受到的空气阻力最小。第二类问题是最速降线问题( b r a c h i s t o c h r o n e ) 。在这类问题 中，要求寻找连接两个定点a ，b 得一条曲线，使得一个沿着这条曲线滚动的没有摩 擦力的小球能在最短的时间内从a 点到b 点。1 6 9 6 年，j o h nb e r n o u l l i 把这个问题 当作是一种挑战刊登在学报上征询解答。1 7 6 6 年，e u l e r 经过对这类问题的深入研 究，发展了一套系统法则，称为变分法( c a l c u l u so fv a r i a t i o n s ) 。同样在这个时代， 力学中许多规律都以最优化定律和公式的方式被记录下来。l a g r a n g e 和g a u s s 也 都在最优化领域的其他方面都有巨大的贡献。例如1 7 6 0 年，l a g r a n g e 发明了一个 1 上海大学博士学位论文 用来解决最优化问题的方法，那就是l a g r a n g e 乘子。l a g r a n g e 变换提供了人们考 察在预期最优点的函数性质的工具。 在1 8 3 4 年，w r h a m i l t o n 发展了用来描述最优化理论的h a m i l t o n 的函数族， 并且统一了那个时代的光学和力学的知识理论。1 8 7 5 年，j w 。g i b b s 介绍了关于 热力学平衡点的更进一步理论。 总极值问题的提出： 设d 是扎维空间中的一个子集，是一个有下界的函数。我们希望求，在d 上 的总极小值 c = i n f 。f ( x ) z d 及函数，值等于矿的点集： h + = z d ：( x ) = c 注? 如果d 是有界闭集，是下半连续函数，则总极小值点集日+ 非空。 无论从理论上或从实际应用上来说，我们都希望求出，在d 上的总极小如 果我们把函数，在d 中所有的局部极小值点都求出来，比较它们的大小，不就可 以把总极小值点求出来了吗? 但是，一般我们很难求出所有的局部极小值点。而 且，总极小值点还可能在d 的边界上。如果我们用求局部极小值点方法把局部极 小值点一个一个地求出来，也无法判定什么时候算法可以终止( 最优性条件) 。因 此，需要专门讨论求函数的总极小值点的理论和方法。 大部分传统的最优化理论和方法是在梯度( g r a d i e n t - b a s e d ) 的框架上发展起 来的，它们往往只能描述或找出可微目标函数的局部最小值点。自从1 6 3 8 年起，f e r m a t 原理就主导了整个最优化理论的研究。这个被称为最优性条件的法则，被数学 家们一次又一次地引用于各种公式中。例如变分法问题中的e u l e r - l a g r a n g e 方 程，等式约束问题的l a g r a n g e 乘子法则，等式及不等式约束问题的k a r u s h - k u h n - t u c k e r 条件，最优控制中p o n t r y a g i n 最大值原理。在这个最优性条件的基础上， 有很多可以寻找局部最小点的方法和理论。依赖梯度的理论是很直观的。这些依 赖梯度的算法较容易实现，并且它们的迭代经常具有较好的收敛速度，它们曾是 最优化研究的主要方向。然而当我们处理非凸的最优化问题时，全局最优值比局 部最优值显示出更大的吸引力。从而如何解决全局最优值问题变得尤为重要。 2 上海大学博士学位论文 积分总极值方法( i n t e g r a lg l o b a lo p m i t i m i z a t i o nm e t h o d ) 是一个用来寻找 全局最优值的全局最优化方法。它可以被用来处理连续或非连续目标函数的非 凸的最小值问题( 参阅 5 l 】【5 8 】) 积分型总极值方法是一个有效的灵活的工具，可以用来解决不同的最优化 问题。它同样可以解决非连续的目标函数和非凸约束的最优化问题。这个方法在 很多领域中都被证实是有效的，如偏微分方程( p d e ) 的数值解【1 】， 2 】，旅行售货 员问题( t r a v e l l i n gs a l e s m a np o r b l e m ) 【5 s ，最优控制( o p t i m a lc o n t r 0 1 ) 9 0 ，【5 7 】， 统计计算( s t a t i s t i c a lc o m p u t a t i o n ) 6 7 ，光学薄膜最优设计( o p t i m a ld e s i g ni n o p t i c a lt h i nf i l m s ) j 2 5 ，最优外形设计( o p t i m a ls h a p ed e s i g n ) 8 5 ，经济平衡点 的逼近( a p p r o x i m a t i o no fe c o n o m i ce q u i l i b r i a ) 5 6 ，等等。 1 2 求凹函数总极小值的理论和方法 对于凹函数在凸集上的总极小问题，由于它的结构，总极小在凸集的边界上 达到。这类问题有它自己的理论和方法，在这节里我们只作简单的介绍。 1 2 1 下估计逼近 考虑下面的求极小问题： c + m 础a nm ) ， ( 1 2 1 ) 其中尸是彤中的有界多面体，是p 上的连续凹函数。由于( 1 2 1 ) 的极小在p 的 某( 些) 极点上达到，故我们只需在p 的极点中去寻找最p , - i 。虽然p 的极点是有限 个，可以用穷举法，但p 的极点数量会很大，我们希望有比较聪明的方法。 首先我们构造一个，在p 上的下估计函数g g ( x ) ，( z ) ，比p 通常我们取夕为线性函数，从而得到一个线性规划问题： m z i p n 夕( z ) 3 ( 1 2 2 ) ( 1 2 3 ) 上海大学博+ 学位论文 容易用求解线性规划的算法求得( 1 2 3 ) 的解x o ，则我们得n ( 1 2 1 ) 的下估计臼= 9 ( 黝) 和上估计c t = f ( x o ) ： q2 m 触i n9 ( z ) m 础i n ，( z ) c l ( 1 2 4 ) 如果c l = c u ，则跏就是( 1 2 1 ) 的解，c l 就是，在尸上的总极小值。如果c l 0 是一个充分大的实数。应用任何一个极小化方法都有可能找到一个 点满足t ( i ) 0 交替的应用这两个阶段，能够得到一个函数值单调下降的局部极小点序列。 确定打洞函数 最早在文章 3 9 】给出的打洞函数有下列的形式： t ( z ) = 瓜x i 磊i f 丽( x ) - 丽f 二磊砑 ( 1 4 1 ) 上式中的未知点和数由下列过程来确定： 第一步；确定，。一旦一个局部极小点牙被找到，我们希望打动函数可以忽略 掉所有函数值大于当前极小点函数值的局部极小点，那么我们取厂= ，忙) 作为目 前已经得到的最小函数值。 第二步；确定卵和甄，1 = 1 ，l 。这里2 是函数值等于，的局部极小点的个数 进一步，假设z ：1 ，也就是说目前仅找到一个局部极小点牙，函数值为，= f ( x 1 ) 。 打洞函数可以简单的表示为： 啦) = 雨等蓦而， ( 1 4 2 ) 这里z ；牙1 ；e ，并且e 是一个随机向量。通过迭代修正刀1 的值，从入1 = 1 开始， 直到下列条件满足： z ( x ) h x 0 ( 1 4 3 ) 如果对于入l ，( 1 4 3 ) 不满足，令a 1 = 入l4 - 入1 ，直到上述的条件满足。仇按 照下列方法确定： 0 ， i f7 1 + e 2 ， a 1 ， i f7 1 一e 2 ， ( ) h 2 ) 1 + ( 1 一，y ) 2 】，i f1 一e 1 7 1 + e 2 ， 1 1 上海大学博士学位论文 这里，y = 忙一引i ，e 2 是一个事先给定的正数，一般地取e 2 = 1 0 一。这样的调整 是必须的，因为对于一些函数来说，当忙一刮 1 时，方程( 1 4 2 ) 的分母变得很 大，这会使打洞函数变得更平坦而接近于零，影响到打洞算法的收敛。 对于存在多个局部极小点的情况，当黾，i = 1 ，l 一1 已经被发现并且已 经确定了仇，i = 1 ，z l 的值，仂将由上述方法应用于下列函数来进一步的确 定： 啦) = 面万丽箬蒙壬丽， 第三步z m 和知的确定。该【 】知项的目的是为了避免在极 小化打洞函数t ( z ) 时出现不需要的极小点。一旦出现这样的极小点，我们将作如 下的处理：令z 是这个当前点，圣是打洞算法产生的前一个点，那么确定为： = 乏+ 。1 一，z ，i i f fi i i i 盒：e 一- z x 。l l f 干专两? p ( z ，n p ) ， 比b ( x 1 ) ( 1 4 6 ) 卿呆z 1 是征盆，合b 【孟1 ) 甲网凼裂，网一i 、局鄙微小点，那么返葸味看孟1 犋允幽 数p 在这个盆谷中的极大点。p 的梯度是 p 一赢 绷刊， 叫一学 4 如果我们选取p 和r 满足 。 南南 。， 这里 k = i 耐南l 唧卜学】 上海大学博士学位论文 在这种情况下，函数p ( x ，r ，p ) 满足填充函数的定义。然而，我们事先并不知道那 类函数容易满足条件( 1 4 8 ) 。 g e 也提到“在数值试验中，为了保证p ( z ，r ，p ) 在低的盆谷中存在一个平稳 点，尽可能让r + ，( z ) 小，因为这容易使得r + f ( x ) _ 0 + 和r + f ( x ) 。 ( 1 4 9 ) 显然 q ( x l ，a ) = 0 q ( x ，a ) ，f o rf ( x ) f ( x 1 ) o rz b l ( f f ：1 ) 如果 a 耀端， m 4 加， 那么q ( z ，a ) 是一个填充函数，这里 h = m i n f ( 牙i ) 一f ( x 1 ) 】 0 ， 黾，i = 2 ，m 是函数，( z ) 的局部极小点。 作为一个填充函数，q ( x ，a ) 的优点是它仅有一个参数。缺点是参数a 始终要 求是很大的，而当a 很大时，e x p ( a lj x 一孟1 1 1 ) 会使得q ( z ，a ) 和v q ( x ，a ) 变化很 慢。 比较( 1 4 9 ) 和打洞函数，我们能够发现它们的分母是不同的。g e 认为，如 果能够找到一个函数e ( z ， 那么它将是一个更好的填充函数。 1 4 上海大学博士学位论文 1 5 积分型总极值的最优性条件和算法 传统的最优化的理论和方法是建立在梯度的基础上的在建立函数总极小的 最优性条件时，我们不能用梯度为零的条件，因为梯度为零的点可能是极大，可能 是极小，也可能是鞍点。郑权教授引进以积分为基础的总极值的积分型理论和方 法，给出总极小值的最优性条件和算法。 1 5 1 均值和方差最优性条件 引理1 5 1 设，：d = 舻一兄1 是一个连续函数，c o 矿= m i nf i x ) 是一个 给定的常数，则水平集如= z ：f ( x ) c 0 ) 的测度为正( 如) 0 证明：由，的连续性，水平集如包含非空开集 z ：f ( x ) c 。= n l i nf i x ) 我们称 w ，c ) = 志厶m ) 咖 1 1 5 1 ) 为，在水平集皿上的均值，称 ，w ，c ) = 志上。i f ( z ) - c ) 2 咖 1 1 5 2 ) 为，在水平集皿上的方差 由引理可知均值和方差的定义对于c 矿有意义。 1 m ( f ，c ) c ，v c c 2 如果c l c 2 矿，贝l j m ( f ，c 1 ) m i f ，c 2 ) 3 如果仇上c c ，贝j j l i m 。l c m ( ，仇) = m ( f ，c ) 。 当c = 矿时，测度p ( 如) 可能为零。我们用极限过程来拓广均值和方差的定 义： m ( f ，c ) = l i r a m ( f ，q ) e k 工c e l f ，c ) = l j m y ( ) e k l e 上海大学博士学位论文 定理1 5 1 下列的命题是等价的： j 已是总极小值 2 m ( f ，石) = 石阳值条件， 3 v ( f ，动= 0 ( 方麦条件) 证明：我们只证( 1 ) 和( 2 ) 是等价的。设e = c + 是总极小值，则，( z ) 吞，坳对 于c 己 m ( f c ) = 厕1f oi ( 喇弘志厶副p = 已 于是 令cj ，己得 岙m ( i ，c ) c ，v c 吞 己m ( f ，c ) 百 即得( 2 ) 。反之，设( 2 ) 成立：m ( ，己) = 五，但是已 c = m i n ，( z ) 令2 0 = 吞一c + 0 。 我们有 己= m ( ，动= l - - - l - j f ( z ) d p = 志lm m 志k 批 志眦( 皿) 一p ( 如一】+ 丽c * 4 - 7 p ( 如一 = 石一日 。 从而得出矛盾。 1 5 2 均值一方差算法 初始步：取一个实数c 0 c ，定义水平集上k = 【z ：，( z ) c o 。 注：如非空，并且，p ( 如) 0 。 1 6 上海大学博士学位论文 下一步：计算厂在如上的均值和方差 q = w ，c o ) = + 志厶m ) 舡 驴w ，c o ) = 志厶( m ) 一c 0 ) i 咖 注：我们有c 0 c 1 c 。 一般情况：对于k = 2 ，令 c k = m ( 工一1 ) 及= v ( f ，儡一1 ) 注：我们得到两个单调序列： c ；0 c l “+ 1 c _ 舌 如d 皿ld d 如d 如+ 1 ) ) h + ，h k _ 日 定理1 5 2 两个单调序列的极限存在，并且 。l i mc k = c + 及。l i m 如= n 如= h + ( 1 5 3 ) 詹- + 0 0詹+ 证明：从算法的构造 c k = m ( ，鲲一1 ) 上式中令k _ 0 0 得 百= m ( f ，动 因此，云= 矿是总极小值。此外， n 皿。= 疗= 腹= h + f 歹t 1 1 5 1 i 殳f ( x ) = h a ，o t 0 求总极小值和总极小值点集 取c ；0 = 1 ，则如= 【- 1 ，1 】。这时， c - = m ( f 川= 三肛a 如= 击 上海大学博士学位论文 耻驯1 、1 a ，( 击) v a 剐= 2 ( 南) v a 一般地，我们有 = ( 击) 铀= ( 击) 七，忍 耻卜( 击) a ，( 击) v a 卜蛐， p ( g c k ) = 2 ( 击) 纠a 小 从而， c = 1 i m 魄= 0 席 一卧( 击) 口，( 击) 枷h 1 6 积分型算法的m o n t e - c a r l o 实现 1 6 1 简单模型 考虑在佗维空间中的简单模型：求函数具有合箱约束的总极小 卿m ) ，d = z = ( z 1 ，z n ) ia i b i ，i = 1 ，几) ( 1 6 1 ) 我们假设，在d 中有唯一的总极小点d 。令仇是包含凰。nd ，k = 1 ，2 的最小立方体： d k = ( z = ( z 1 ，z n ) la ：z 6 ：，i = 1 ，礼) ，( 1 6 2 ) 其中 口i = = i n f x lz = ( z 1 ，z n ) 五knd ) ， 6 丧= s u p x iz = ( z 1 ，z n ) 日& nd ) 】8 上海大学博士学位论文 所以， c 2 卿m ) - 善m 风i 。n n 。m ) - 舢m i n 。他) ( 1 6 3 ) ( 1 6 4 ) 在均值方差算法的每一迭代步中我们用m ( ，d