（运筹学与控制论专业论文）求总极值的积分方法的一些研究.pdf

摘要 通常一个求总檄值的问题可以表述为：对于给定的一个r l 维空间的紧致集dcr “， 及给定| 勺避续l 拍数，：几”- r ，寻找某一点z + d ，使得刘于一切的z d ，满 足，( j 。) f ( x ) ，洲求下述问题的解： , q l o bl n 氓，( ，) r _ 【1 ， 或考虑求解更般问题的解： 9 必m ) 其中s = 叫小( _ ：) s0 ，i = 1 ，2 ，r ) 是竹维欧氏空问的约束集，肌( 。) ，i = 1 ，2 ，巩为 连续函数。 求总极值题的方法存军事、科学技术、工程设计、自动控制、经济管理等领域 有着广泛的应用。 本文列强s 权、张连生等教授有关积分型的求总极值方法的研究工作作了更细微的 研究。郑权等r 1 9 7 8 1 3 捉的积分水平集求个用优化方法，其j ：要特点是具有判别全 局解的收敛准则，且仅需假定目标及约束函数为连续的，足现有少量较具特色的求全 局优化n q 力浊之。但其+ 艾现算法f j c 提f b , j t ! ：c 念r i ：赞：泄i 不投，实现算法征删沦 上易丢弃全j 斛。1 9 9 5 年0 k 连生教授等捉j 。离敝均饿一水、l ，集卯：法，井证明了其钟j 上 的收敛性。在此基础上，邬冬华等给：基j 二郑权的概念性算法，构造! j 概念性算法较 为吻合n 勺实现翁：法，并辅以数论方法进 j ：数值汁算，得到了实现算法的收敛性。在郧 权、张连生关j 不连续罚函数的工作基础上，我们构造了一个简单的函数用于实现从 有约束到无约束的转化，并给出了棚应f 向收敛俐：征明。我们还构造了水平值函数，使 得种f 关的积分型最优化力浊等价于求一个非线性方程的根，并结合数论中的一致分礼 给出相应的概念算法和实现算法，证明厂实现算法的收敛性。出于构造实现算法过程 中利用数论中致分布代错i v l o n t e c a i l o 随机投点，位实现算法变为1 确定性方法儿 提高实现算法的收敛速度。我们还列非线一2 补问题迎过引进| i ：线性互补函数将其转 化成无约束最优化问题结合积分方法给出了算法。本文共有五章组成。在第一章中， 对于全局优化问题研究的意义、以及目前流行的方法作了简单的介绍。第：章引入了 我们谢：i ! i ：| 中需要的数论t 1 1 的主要结果。第三章巾，对于集约束优化问题构造转化 函 数，给出相应的概念算法及其全局收敛性m ：l 明。在第四章，引进了水平值函数，讨论 其性质并结合二分法和弦截法给r 两种算法，h j 数沦中一致分稚佳点结合水平值函 数给出了实现算法，并证明了其全局收敛f ，j ：。列非线性互补问题转化为无约束最优化 问题结合积分方法进行了研究。第五搴给：i r 数值例子浣明了找们算法的有效性。 关键训总极值，全局优化，埔部优化，m o l 岫一c a t l o 方法，积分方法， 罚雨数，幸 ；_ 了约束，集约束，一致分钿佳点集，积分水平集水平值函 数，最优准则，收敛性，非线性互补问题。 i i a b s t r a c t t h eg l o b a io p t i m i z a t i o ni ) i _ o b l e mc a i lb es t a t e d3 , sf o l l o w s ： g i v e nnn f ) e ， l , p t y c o m p a c ts e td ( ：r “n f n ( ：订n t ”ot i sf u n c t i o n ，：a + r 7 c ? 、 acr “i s “s u i t a b l es e tc o n t a i n i n gd ，f i n da tl e a s tonep o i n tx ds u c ht h a t ，( z ) 至 ，( z ) ，如ra l lz di e g l o bn 舢l i n ，( ) o rw e ( o l l s i d p it t l el l l o r eg e n e r a l l vc a s e sa sf o l l o w s ： w h , e r es = f z l , i ( z ) s0 ，z = ，2 形c o n t i n u o u sf i m c t i o n s 9 l o br a i n 幻 r i s 口e o n s t r a i n t e ds e ti n 舻玑( m ) ，i = 1 ，2 ，r t h m ca i em a n ya p p l i c a t i o n so fn 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 ef i e l do fm i l i t m i h e s s ，s c i e n c ea i l 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 li n g ，a u t o m a ，t i cc o n t r o l ，e c o n o m y ( m a n a g e m e n ta 1 1 ( 1 s oo n i nt h i sd i s s e l t a t i o n w em a k eaf l l r t h ml c s e a l c hf o l t h ei n t e g r a lm e t h o df o rt h eg l o b a l o p t i m i z a t i o n0 1 1t h eb a s i so fm rz h e n ga n dm iz h a n g t h ei n l ，e g r a lm e t h o di sp l ( ) _ p o s e db ym rz l ”gi n1 9 7 8 i ti so l l oo fs o l l t i m f l w el i l t - l h ( ) ( 1f o rt i r eg h , b a lo p t i m i z a t i ( m s i n c e “h a , shg k d ) a ic g i i v 、lg e l w , ec i 吖i ( ma n dt m l y ”q u i r et h e ( o t l ( ，i n u i t yo ft h ef n t i o nw h i 一i 】i sav e r yw e a kc o n d i t i o nf 1 ) rt h eg 1 0 1 ) a lo p t i i n i z a t i o ni ) r o b l e m s h o w e v e r ，w e f o u n dm rz h e n g sc o n c e p l ，1 l a ia l g o r i t h ma n dh i si m p l e m e n t a b l ea l g o r i t h ma r ed i s a c c m d a l i tt h a t7 1 7 ( 1 0 l l sh i si m l ) l e m e n t a b l ei sm a y b el o s et h eg l o b a lo p t i m u mt h e o r e t i c a l l y a d i s c r e t el l l e a l lw d u e l e v e ls e ta l g o r i t h mw i - l , p r o p o s e db ym rz h a n ga n dt h ec o l l v e l l g e m l ! w a s1 ) o v e d 0 1 1t h eb a s i s ( ) ft h ew o r km e n l i o n e da b o w ，m rw up r o p o s e dac o n c e p t u a l a l g o r i t h mb a s eo nm rz h e n g s a n dc o n s t r u c ta ni m p l e m e n t a b l ea l g o r i t h mw h i c ha r e a ( ：一 c o r d a n l ，e o n l p a r a t i v e l yo nt h eb a s i so ft h er e s e a r c h ( ) rm rz h e n ga l l dm rz h a n ga b o u t 1 1 1 d i s c o n t i n u o u sr o b u s tp e n a l t yf i m c t i o n ，w ec o n s t r u c t e da s i m p l ef u n c t i o nt oa c h i e v et h e t r a n s f b r mf r o mt h ec o n s t r a i n e do p t i m i z a t i o nt ot h eu n c o n s t r a i n e do p t i m i z a t i o n ，a l , dw e g a v et h eg l o b a lc o n v e r g e n c eo ft h ec o r r e s p o n d i n ga l g o li t h m m o r e o v e r ，w ea l s oi n t r o d u c ( ，d al e v e l v a h l ef u n c t i o nt oc o n s t r u c tt h ee q u i v a l e n c eb e t w e e nt h eu n c o n s t r a i n e do p t i u f i z a t i o na u dan o n l i n e a re q u a l i l y b ys t u d y h l gt h ef u n c t ，i l m 8p r o p m t i e s ，w eg a v et h et e w q v a l u ee s t i u l a t ea l g o r i t h ma n dt i l eir n p l e n m n t a t i ( i la l g o r i t h mb ym e a u so ft i l eu n i f o li l l d i s t r i l u i t | o no ft h eg o o dp o i n ts e ta e l dw 【，a l s og a v e l t 、c o n v e r g e u c ep r o o fi l lt h ep l o c e s s o ft h ei m p h ! n m n t a b l ea l g m i t h m 、w el i s et h eu n i f o l l 】1d i s t r i b u t i ( ) e li nn m n b e et h e o r yi u s t e a do fm o n t e c a r l o n e o m dw h i c hl l l a k f ! st h ei n q ) l e l n e l , t a b i eag o r i t h mi sd e t e r n f i n i s l - a n de f f e c t | w ! w ea l s ( ) r e s e ae t h e ( 1t h ei l ( ) i i i i i i c ；l i ( ：t ) 1 1 1 1 ) 1 e u l e l l , a l i t yp l o b l e mw i t hi n t e g l a l m e t h o d t h ep a p e ri s o r g a n i z e da , sf o l l o w s ：i nc h a l ) t e r1 , ab r i e fi n t r o d u c t i o ni sg i v e ni ；0t i l e s i g n i f i c a n c ea e l ( it i l ep o p u l a rm e t h o d st ot h eg l o b a lo p t i m i z a t i o np r o b l e m s i ne h a p l ，e r 2 ，w ei n t r o d u c es o g l em a i l lc o n c l u s i o n si nn 1 l l i l l e it h e o r yw h i c hi sa p p l i e di nt h ep r o o f o ft h el a t e rc h a l ) t e ri nc h a p t e r3 ，f o rt h ec 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 u w ec o n s t n l c t e d at r a ，u s f o ih lf u n c t , i o i la n dg a v eac o n c e p ta l g o r i t h n l ，a n dw ep r o v et h ec o n v e r g e n c e i n c h a l ) t e l4 ，w ei n t i o d u c e da ，l e v e l v a l u ef u n c t i o n le l di t , sl i e o p e r t i e s a n dl l r e s e n t e dt w oa l g o r i t h mw i t hb i s e c t i o nm e t h o da n dc u tl i n em e t h o d ，t h e nw ep r o p ( ) s o dt h ei m p l e m e n t a t i o n a l g o r i t h mb yl u e a n so ft h eu l l i f o r md i s t _ 【i l m r | o n ( ) f | h i 、g o o dp o i n ts e ta e , dg a v et h ep r o o o ft h e ( 1 ( ) i l v ! i g e l i c ( w ea l s or r s 1 1 c h c dt i mm m l i n c ；l l ( ：o n l l ) l e l l l e l l l n “i vp r 0 1 ) l e m w i th i n t e g r a lm e t l l o d f i n a 1 l y 、n u m e r i c a le x a m p i e si sg i v e n i l l l l s t r a t et h ee f f e c t i v e n e s so ft l f ， i m p l e m e n t a b l ea l g o r i t h m k e yw o r d s ：g l o b a lo p t i m i z a t i o n ，l o c a lo p t i m i z a t i o n ，i n t e g e ；1 1m e t l m d ，g o o dp o i n t s e to fu n i f o r md i s t t | b u t | o n ，d i s c o n t i n u o sp e n a l t yf u n c i o l l ，m o n t e c a r l om e t h o d ，b o xc o i l s t r a i n s ，s e l ，( ( ) n s l , r a i n s ，l e v e l v a h mt i m e | i o n ，i n | ，e g l ；1 1 一l e v e ls e t ，n o n l i n e a ec o l n p l e l n e e d , a r i ( 、 p r o b l e m 上海大学 6 7 8 1 9 8 本论文经答辩委员会全体委员审查，确认符合上海大学 硕士学位论文质量要求。 主任：麓触乞 j 、酾；2 弘圣j m 久 委员：名荥匿一芝脚犬芬苏梭 3 蚺易 v 兹卜阶髓 “ 蔬仪 l， 导 师：厮斜 答辩日期： h 毕，f 名 7 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅：学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期：删、6 ，f 第一章绪论 在这一章t h 我们主要对于全局优化问题的1 实际背景、意义、研究困难和当前的主要 研究方法给f 简单的介绍。 1 1 全局最优化的实际背景、意义及研究困难 全局最优化理沦的研究i j 标是列于无约束或带约求的非线性函数求其全局最小( 或 最大) 。通常r u + 以表述为：给定一个n 维欧氏空n l j 的非空闭集d ，和一个连续函 数f ：r ”_ r ，寻找一个a ，c + d ，满足厂( r ) ，( r ) ，对所有z d 。即 g l o b 剿似) ( 11 许多在科学，经济和工程| ：的最新进展都依赖r 全局最优化的计算技术，全局最优化 问题的范羽极其j 。泛它们包括经济模型、金融工程、定位与选址、网络运输、数据j 4 和集成r u 路设计、化学：i 一氍设计与控制、分r 生物学等等。 由于存在多个不同于全桶最优值f l f 局部最优值，通常全局最优化问题并不能用传统的 非线性舰划技术得到有效的解决。其主要的难t i 存j i ：现有的卅线性优化方法一般j l 能求出同部最优点，在搜索过程i i 缺乏跳山局部最优点的技巧；此外，还没有一个仃 效的评判准则米判断一个局部最优点是否是全局最优，从而使得那些利用导数、梯j ! ：l ： t 手1 次梯度求，0 琊雎优解的止浊矶以找剑个用j ) 优删。，川此，必j 全0 优化问题的求删 到目前为止仍然是一个非常困难的问题，有很多理论和实践问题亟待解决。 1 2 全局优化问题研究的主要方法 近几十年来，关于全局最优化问题的研究包括凸一次规划、一般凹规划、网络优 化、l i p s c h i t z 丰 j d c 规划等方面都取得了一定的进展，g a l p e r m 和郑权( g a l l ) e r i na n d 3 z h e n g1 9 8 7 ) ，f a l k ( f a l k1 9 7 3 ) 分别提出j 关于仝局解的一个评判准则。同时许多 学者提出了不少求解全局最优化问题的算法，这些锋法一般可分为确定性算法，随机 算法和启发式算法。确定性算法主要包括：外j _ 6 ；i 近，j 法、分支定界法、区间方法、秋 分方法、隧道函数方法和填充函数方法等。随机算法主要包括：二阶段法、随机搜索 方法和随机函数方法。还有一类是近年在： ：程和控制中被广泛应用的现代优化算法， 主要有禁忌搜索、模拟退火、遗传算法、入：r ：神经嘲络等。 1 2 1 外逼近方法 外逼近方法，即用一系列比较简单的松弛集合从可行域的外侧来逼近可行城 的方法，在优化领域特别是组合优化中已经成为一种基本的方法，最l 的文献可见g o i l l e r y ( g0 1 l 】p r y1 9 5 8 ，1 9 6 0 ) c h e n e y 和g o i d s t e i i 】( c j l e ya n dg o h t s t e i n 1 9 5 9 1 及k e l l e y ( k e l l e y1 9 6 0 ) 。外逼近方法的步骤m 常简沽，它已被广泛应川 于凹规划( i h l l f i l i a l l1 9 8 l ，7 f h i e l l ，7 f a i l l 1 1 1 ( 1b a u1 9 8 3 l u y1 9 8 3t h o a i1 9 8 4 ) ，反凸规划 ( t u y1 9 8 7 ) ，l i p s c h i t z i a l l 规划( t h a c ha n dt n y1 9 8 7 ) 和dc 规划( t u y1 9 8 6 ，t h l m 】 1 9 8 8 1 等。 1 2 2 分支定界法 分支定界法( b r a n c ha 1 1 ( 1b o u n da l g o r i t h m ) 是求解瞰优化问题中使用相当广泛的一 种方法，该方法的主要思想是，将一u 行域松弛并刁i 断地划分成小区域，在这些小 区域上确定目标函数值的i 二f 界，从而逐步逼近全局最优值。该方法主要应用r 凹规划，d c 规划年l l l i p s c h i t z i a n 规划。文献参r 见t u y ( t i l yi ( h a c h a i ；l t r o va n du t k i n 1 9 8 7 ) 及h o t s t , 等( i o l s t 1 9 7 6 ，h o r s t1 9 8 6t u yt h i e ua r i dt h a i1 9 8 5 ，t h o a ia l l ( d l y1 9 8 0 ) 。 1 2 3 区州力法 m o o r e ( m o o r e1 9 6 6 ) 首先发现了区间分析( i n t e r v a la n a l y s i s ) 是计算一个函数在子 箱x 上界的极有效的工具，它，l 乎可以计算出总极值f + ；1 9 7 4 年，s k e l b o e ( s k e l b o e t 9 7 4 1 t 2 m o o r e f f , j 一部分魑土想与分支定界原理结合起来；最后，m o o r e ( m o o r e l 9 7 6 ) _ f 次修改，得到了m o o t e s k e l h o e 算法。算法的主要思想是：先作目标函数f ：x r 的 扩张函数f ：j ( j y ) 一 ，；然后利用分支定界的思想把x 逐步细分，在某个子箱f ：搜 索；最后找到最优值i 厂+ 。 4 1 2 4积分方法 积分方法( i n t e g r a 1g l o b a lo p t i m i z a t i o n ) _ f = i 郑权等( 郑权，蒋百川和庄松林1 9 7 8 ，c h e w a n dz h e n g1 9 8 8 ，z h e n ga n dz h u a n 9 1 9 9 5 ) 等提出，其突出的优点足思想简明卣观， 州目标函数和约束函数的限制较小( 只要求函数连续) ，应用范围较广，数值例予说 明该方法是一种较为有效的全局优化方法，我们将仃第三章和第四章对于这一方法给 出集约束算法和水平值估计算法。 1 2 5 隧道甬数法 此力法【| _ 1 1 ，e v y l l m c m t a l v o ( l e v ya l l d m o t l t a l v 0 1 9 8 5 ) 荫先提，该力法要求f ；_ i | 标i ；j 4 数二次连续呵微，且假i 5 2 ，( z ) 的极小点都是孤立极小点，并且足有限个。该方法有两 个过程组成：极小化过程和“凿隧道过程”这两个过程交替进行，从而得到目标函数 的总极他。、) ( 1 9 8 9 ) ，b a r h e n ，p r o t o p o p c u 和r e i s l ；e t 。( 1 9 9 7 ) ，c e t i n ，b a , h e n _ 手l l b u r d i c k f 1 9 9 3 ) x c j 原有的隧道函数法作了重要改进，握出了动态隧道函数法。 1 2 6 填充蛹数方法 填充函数方法( f i l l e df u n c t i o nm e t h o d ) 是g e ( g e1 9 8 3 ，1 9 8 4 ，1 9 9 0 ) 及g e l j q i u ( g ea n dq i , l 1 9 8 7 ) j a ：作的工作。其主要思想是：首先应刖求局部总极值问题的方法，解出，( 叫n j 一个局部校小点j ：通过构造填充函数找到问题的另一 0 部极小点；该点满 足，0 ；) ，( - ：；) ，从丽最终找到函数的全局j 优点。 1 2 7 禁忌搜索算法 禁忌搜索( t a b us e a r c h ) 算法是局部领域搜索算法的推广，是人工智能在组合优化 算法中的一个成功应用。g l o v e r 在1 9 8 6 年首次提出这一概念，进而形成了一套完整算 法。该算法的特点是采用了禁忌技术。所谓禁忌技术就是禁i 上币复前而的工作。为j 回避局部邻域搜索陷入局部最优的不足，禁忌搜索剪。法用一个禁忌表记录下已经到达 过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些 点，以此来跳出局部最优点。 1 2 8 模拟退火算法 模拟退火( s i m u l a t e da n n e a l i n g ) 算法是局部搜索算法的拓展。它不同于局部搜索之 处是以一定的概率选择邻域中费用值人的状态。弹沦_ j 二来说，它是个全局最优孵 法。模拟j 卫火算法最早的思想育m e t _ t ) ( ) l i s ( i1 9 5 3 印提出，n i l k p a t l i c k 在1 9 8 3 _ r 成j 力 将其应用到组合最优化中。模拟退火算法分为叫齐锌法利非时齐算法，理论究表明脱 有的技术尚难以保证模拟退火算法得到全局最优解。 1 2 9 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) 的思想主要基j 二模 r g i 物在自然环境中的遗传和进化过 程而形成的一种自适应全局化概率搜索算法。它最一一出美国密执安火学的h o l l a n d 教 授提出，起源于6 0 年代刈自然和人：i ：自适应系统的研究。7 0 年代d e 1 0 n g 基于遗产算 法的思想在计算机上进行了大量的纯数值函数优化计算试验。存一系列研究工作的然 础上，8 0 年代 4 t g o l d b m g 进行归纳总结，形成了遗传算法的黎确框架。 1 2 1 0 人睡中经网络 人工神经网络( a r t i f i c a ln e u r a ln e t w o r k s ) 的早期工作可以追溯至u 1 9 4 3 年p i t t s 和m c c n l l o ( - h 建立的第一个模型，后被扩展为“女r l ( 1 ) e r c e p t r o n ) 模型。2 0 i ! j ：s e 8 0 年代，h o p f i e h l ：t 舒 人工神经嘲络成功应用在组合优化问题，m c c l e t l a ( 1 和r u i i l e i l l a r t 构造的多层反馈学 习算法成功解决了j 1 _ ：l 隐含层认知刚络的“芹或”问题肢其它的谚 别0 ：d 题，他们的突破 使得人工神经刚络成为新的研究热点。 6 第二章数论中的一些结果 为了证明我们实现算法的收敛性，在这一章，我们将引进一些必要的概念和数论- 1 的一些必要结沦。不失- 般性，我们假设f i 雨所州论的有界闭箱均为单位有界川 箱g 。g 。= 0 ，i h ( 否m i j ，我们总可以作线性变换，把所讨论问题转化为单位有牲 b 箱。) 2 1 相关概念 令 ( 仃) 0 = z 7 z z = 1 u = 。2 z 5 z = 1 0 = z ： z ： ：f 鲁= 1 为g 。的任意分割，设球，) 在g 。卜有定义，| _ i a 。，( 。r ，z z t ，z ，；) = ，( “、，。z 。，w 。) 一_ ，( ：c ，z 麓1 + 。，石。) 1 k ls7 0 越m 。，( ，童乏t ，z 等，) = 几亿，：麓，z 等，z 。) 一，( ，t z l + 1 ， 一，( r ，乏、，z h i k 2 + ，z 。) + ，( m ，z 兰1 + 1 1 1 ：2 礼 7 茁。) ，z ，i ) 露 _ i ，虹，厂( n ，z z l ，z 等，z 职，z 。) = ，( 轧，m 弛，z 等，柳，一。) 一，( 轧“：r 1 ，z 等，办k n , n ，) 一，( ，z 乩，z 等“，_ 船，一。) + h _ 甜+ 1 ，一，z ：，) + + ( 一1 ) 。儿f l ，“，。l，。嚣“，。) + ( 一1 ) m ，一z 。“，l ，跚“，一，。) 1 ：i 如 ， ， 扎 ，z ，m 厂( m ，z 孑，一j 帮) = 厂( z ，z 字，一：i ) 一厂( z + 1 ，珂字，t 2 ) 一，( z ；1 ，z 孑+ 1 ，_ i ；) - i - f ( x i l l + 1 ，z 孑+ 1 ，z i t ) + + ( 一1 ) ”一1 ，( 一i 1 ，z 孑+ 1 ，。罾+ 1 ) + ( 一1 ) “，( z j l + 1 ，m 字11 ，磕+ 1 ) 若变差 + + f 。，( 1 ， 1 1 h k 2 t ) i kj = 0 2 = t 】 “l i + ( 【，1 z “】 ( 2 11 ) ( 2 12 ) 有一与分割( 盯) 无关的上界，则称f ( x ) ) q h a r d y k r a l l s 意义下的囿变函数。k 的上确界 称为厂( z ) 的全变差，记为v ( ，) ，其全体记为鼠。 若设 0sz z 普+ 1 i 1 ， 七= 1 ，2 ，n 8 湖渊 | | ，口 趣 一铲 一一 h 一：j g 一 】 ， 砖 一 一 坯 且存在绝时常数l 使得 ( 2 ) i h 。f ( 1 l ( ：；k l + 1 ，l ，：r ：i ，1 ) isl ( t ? 1 i 曼 ，1 1 z k 1 ，1 ，1 ，t t 。1 2 2 ，】， 一, 1 才7 k ) ( z 1 一e 。z k ：2 ) 1 l ：2 曼， ( m ) l 忆圮，( 1 ，1 ，x “k t l sl ( ：。1 r z l ) ( z 等+ 1 lsk 1 1 ，1 ，r ：等，。乏。，1 ，1 ) 一z 等) ( z 器+ 1 一z 船) 岛2 ：m 礼 则称，( z ) 满足广义局部l i p s c h i t z 条件，此种函数全体 d 1 多, j l 。 定理2 1 1l 。cb 。 证i ! f _ | 若f l 。划 + 胛i 1 1 ) ( 孑+ 1 一孑) ( z 1 一l ) i 2 一 f * ，l + 己 ( 一- 一一- 一 i 曼 l b 女m 兰 i t - 1 = 04 0 2 = 0。 1 2 f ( $ 等州一z 等) ( z 器“一m 船) + + l i 女i + l 1 1 n “l 一1 “2 一l ( z 1 一z 兰等+ 1 一z 謦) sl ( e 7 。1 , + + g ? + + 暖+ ( 鼍) = ( 2 “一1 ) l 故f b 。即得l ，cb 。 “ 。 圳 h n z一 i n、j1 ，2 ) z 嚷一 + 地2 r 爿 ”：h 搿 i ， 茁 正一 了“ # i ， f “ 岭 一 n 删 l 一 ，口 事实上，若，( 茁) 满足 ，( 。：) j l l 百o f ( x ) 1 sl a 2 ，( 岱) i ， 瓯f “ 1in 1si f n f 鑫恤l a ：c i a z 2 0 z 。l 一 则，( 搿) l 。下面讨论的函数均满足j 二述条件。可见仃，。是一类范围很广的函数类a 2 2 数论中的相关结果 令f 为一i 整数，且 r ( ) = ( z f ( ) ，z 2 ( ) ) ，1 1 为g 。中的一点集。对j 二任意7 = ( 1 1 ，y 2 ，) g 。，设f ( 7 ) = 眦( 7 l ，1 。) 表 示局( ) ( 1 a f ) 中适合不等式 0 s ( ：) ，k ，0 曼， 纵 ：) 7 ， 的个数。若 恶l 华小忙m “t ( z z l ) 则称点集毋( ) ( 1 rsf ) 有偏差妒( f ) 。 设仉) 为一整数序列 1 f 1 f 2 一， 对于每一k ，有g 。中彬j - - 4 点集b ，( ；) ( 1s ：f j 与之对应，且有偏差咿( f 。) 。若妒( f s ) = 0 0 ) ，则称点集， 。( 女：) ( f 【 c 4 = r a i n ，( z ) ，令 吲加) = 志厶，( m ) 一) 锄( 3 1 1 0 ) 其中凰是水平集如( 3 1 ，9 ) 所定义，称m ( f ，c ) 足萌数。，在水平集h ：上的均方差。 定理3 1 2 对于问题( p ) ，下面几个俐质是等价的： 1 搿+ 是问题( p ) 的总极值点，c + = ，( + ) 为干日麻的总极值。 2 ，( ，c + ) = 0( 31 1 j 3 ( 3 1 1 2 ) 3 1 3积分力法概念性算法 现将概念性算法表述如h 算法3 1 1 步1j 1 ) c 。l 0 s ，给定一个充分小的i f 数( ，令f | 1 0 = ，( z o ) ，皿。 c o ， = 0 步2 若，t ( ，。) = o ，m 0 为总极值，仉。为总极值点绳转步6 。 步3 计算均值 2 高k 沁h t 且令 啊。一b sm 。) 】 荇。+ 1 = b 则f l 为总极值，h 。为总极值，_ 集，转步6 ；否则，转步4 。 步4 计算均方差 v f 。高厶( m ) 一，tp 1 月“j 儿 z sf ( x ) 曼 f 31 ，1 3 f 3 1 1 ( 3 1 1 5 ) 步5 若v f f ， j ! | j 令 ：= + 1 ，转步2 ：否则j = 步6 。 步6 令+ = = 二“- h 目打+ = ，k 。，终f 【。h + 为( ，：) 1 ，| _ ：s - | 】f 1 0 近似总极值点集，+ 为4 i i i , , 蓝i i j 近似总极f ! 。 3 1 4 收敛世i ： 如果在上述算法中令c = o ，则迭代将无限进h ：| 、去，我们i ，j 以得到两个单调下降的” 刊 ( + t 利( h 。 。i l ij 二这两个序列均铂抖放它们都收敛。令 。k | i m 。c k ( 3 1 ，l o ) 和 h + = 艘，。= n ，。 ( 3 1 e 一 。 m = i 则我们有下m f 的定心! 。 定理3 1 3 微限，是问题( ，) ) 的总极值，f + 是总极值t i 集。 注31 1 杉 分型求总极值算法具有很好的收敛性，i ：且该算法仅需要计算目标函数 值，放适用】二较大范| 1 _ 的总极值问题。但是卉： 般情况下，水i 卜集h 。= 1 i 易求得，敞原女 文献中提供的实现进烈足通过m f ) j c a ) 】i ) 随机墩j j ：墩得近似水平集并缩小搜索m ， 固，往迭代的过程中有可能将总极值点排除出搜索范嗣，从而丢失总极值点。下而我 | 引进修i f 的积分算法。 3 2 集约束的修正积分算法 本节我们首先考忠如下总扳值问题 “m 蚓i n ) ，( ) ( 32 其中d 为，一p 的有界闭衔，f ：冗“- 冗1 、的连续函数，矿为i 厂 ) 在d 上的总极值。 修n ：的求总极他的l 5 _ 分一水、f 集算法，其j ：要的思想是：在第步，当求得均值仇和水 甲集只。后，构造一个新函数 ，) 靴珥， 眦2 1 否则 显然，它与原函数具自相同的总极值。理论一i ：- ，用函数，c ，柬求均值，其积分在闭箱d 上进 行，丽小必在水j f 集1 ：。祚实现算法中，川致分礼f i j 数值积分来逼近均值，并且证明j + 该算法f ) g l l k 敛州：。 3 2 1 最优性条件 我们始终作如“卜i 假i 5 ： 假设1 ，在di 足连续的。 假设2 存在一个实数_ 使得水平集 皿= ：ke i ，( 搿) ，) 和d f f , j 交集非空而紧。 定理a 2 1 在假设l 和似没2 卜，如粜f 1 , ( 1 1 ，) = 0 ，其小h ，= 。：e j l 是b e b e s 9 1 l e 测度，那么，r 一就是，在di ? 的总极值，h 是总极值点集。 证明参见文献 2 1 - 定义3 2 1 设c ， f2 l ，l m l i n ，( z ) ，我们定义 m 卜砸1 再0 由| 1 5 f 3 2 ： dj ( z ) sc d f 3 2 ，1 ) 八q ，、【 其中 性质3 2 1 设0 e ，则 证叫有定义可知 m ( 九) = ，( z o ) u l i - a f 。 下颤我们将证i i 珂j _ 二述算法的收敛性。 在算泄o | 令s = 0 ，则迭代将进行光5 j 多次，川应地榴到曲尢” 列 c ：k ) ， 吐， 及函数列 眠( r ) ，下面讨论它们的一些性质。 定义3 2 2 设“ c ：2 鼍留，( 茁) ， ： 口( ) 一 f 3 2 2 7 o i 0 c ， ，、l e = 、j、j t t ， 口 油益 h m 0 7暇 s ) s 记 忏 f 2 ) 1 i i r o r 矿，则 证叫由定义3 2 2 叫知 志“咖志厶刊胪c t 性质3 2 4 若c k 单凋下降趋于c ，f 三= n l j i j ，( 。j ) 则有 t t o f 3 2 2 s l _ i r a o 。h “= nh “= h c ns ； k l _ + i m o o ( h 。) = f l ( h 。ns ) ( 3 22 9 ) k = o 证i ! j ) f i i “+ ，! 1 1 1 ( t ) f * + l 曼r ，敞h 以，口| 1 1 1 “+ ci l 。j i 足 ? 。i m 。1 1 。= n1 1 “ = 0 又设nh q ，则9 ( z ) sc f l o 若z 隹s ，则c o = 口( $ ) c k c o ， t l l = 0 有v k ，c = c n 。又有： q 2 志r d ( r ) d t 2 志s 响d l 一r s ( ：f ) d t j 2 鬲b i 啪。t ( d s ) + r s 可，。( ：o d l ，+ h 。，( 搿) ( t 一】 2 面b ( ，t ( d ) 叫( 订n ，) ) + 厶。( z ) d f j , k h ，n 。i s , i ，( 一) o 使搿v ：f ( = ：，d ) ，伯r 韵一( 掣) 7 7 ( ) ，敝“： c f 高扣