（运筹学与控制论专业论文）求全局最优化的几种确定性算法.pdf

摘要 最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一 门独立的学科还是在本世纪4 0 年代末，是在1 9 4 7 年d a n t z i n g 提出求解一般线性 规划问题的单纯形算法之后。随着工业革命、信息革命的不断深化，和计算机技 术的巨大发展，至今短短的几十年，它得到了迅猛的发展。现在，解线性规划、 非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各 种最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学等方 面得到了广泛的应用，成为一门十分活跃的学科。 全局最优化是最优化一个重要分支。相对于线性规划等分支，它在理论和算 法上远没有那么成熟、完善，大多数的全局最优化算法缺少终止准则。但是现实 社会对它有更多更迫切的要求，使得全局最优化工作者利用不同的数学理论和工 具，提出了各式各样的算法，从理论到算法，都具有强大的生命力，而且需要进 一步完善、深化。例如，在函数变换的基础上，提出了填充函数法；在非线性方 程理论的基础上，提出了打洞函数法；在微分方程动力系统的基础上，提出了动 力打洞算法；在积分原理的基础上，提出了积分水平集算法；在组合理论的基础 上提出了分支定界算法，在随机和启发式基础上提出了模拟退火法、遗传算法等 等。 全局最优化算法，从算法的构造上大体可以分为确定型算法和随机型算法， 例如，填充函数法、打洞函数法属于确定型算法；模拟退火法、遗传算法属于随 机型算法。我们在这篇文章中仅仅考虑非线性规划的全局最优化确定型算法、非 线性整数规划的全局最优化确定型算法和非线性混合整数规划的全局最优化确 定型算法。这篇文章的主要目的就是，在研究已有确定型算法的基础上，尝试提 出一些改进和创新。力图在算法效果方面有所提高，在理论方面有所深化。其内 容详细情况如下： 在第一章中。我们介绍了几种常见的全局最优化算法，以及他们的特点。这 包括：填充函数法、打洞函数法、分支定界算法和积分水平集算法。每一个算法 i 都有各自的优缺点。首先，我们从算法思想到相关理论都给出一些深入浅出的说 明，在此基础上，分析了各自的优点和缺点，为我们进一步的推广和构造新的算 法，提供一些指导思想和思路。 在第二章中，我们给出三个求解无约束全局最优化问题的算法，在第二节 中，对于一般无约束全局最优化问题，我们给出一个填充函数的薪的定义，它不 同于传统的填充函数定义。在此基础上，提出了一种新的填充函数和相应的算 法，该算法降低了对参数的依赖，具有较好的可操作性。数值试验显示，该算法 是有效和可靠的。 在研究填充函数和打洞函数的基础上，为克服打洞函数算法的一些缺点，在 本章的第三节中。提出了修正打洞函数算法。 我们在本章的第三节中，提出了一种求无约束全局最优化的新的算法即积分 函数算法，并分析了他们的的收敛性。 在第三章中，我们考虑了非线性整数规划中的全局最优问题，在它的第二节 中，我们将填充函数推广到整数规划中，并给出了相应的填充函数算法。在第三 节中，修正打洞函数算法被推广到整数规划中。在第四节中，我们提出了逐次下 降算法，也取得了较好的计算效果。 在第四章中，我们尝试着用已有的算法求解混合整数规划的全局最优问题， 给出一定的策略和理论。在第二节中给出了混合局部极小点的定义和求解混合局 部极小点的算法，在此基础上，在本章的第三节中我们尝试着提出一些求解混合 整数规划的全局最优问题的算法，并进行了一定的理论讨论，为进一步的探索打 下好的基础。 关键词：混合整数规划非线整数性规划非线性规划全局最优解填充函 数打洞函数分支定界积分函数。 i i a b s t r a c t g l o b a lo p t i m i z a t i o np r o b l e m sa b o u n di ne c o n o m i cm o d e l l i n g ，f i n a n c e ，n e t w o r k sa n dt r a n s p o r t a t i o n ，d a t a b a s e s ，c h i pd e s i g n ，i m a g ep r o c e s s i n g ，c h e m i c a le n g i n e e r i n gd e s i g na n dc o n t r o l tm o l e c u l a rb i o l o g y , a n de n v i r o n m e n t a le n g i n e e r i n g ， s i n c et h e r ee x i s tm u l t i p l el o c a lo p t i m at h a td i f f e rf r o mt h eg l o b a ls o l u t i o n 、a n d t h et r a d i t i o n a jm i n i m i z a t i o nt e c h n i q u e sf o rn o n l i n e a rp r o g r a m m i n ga r ed e v i s e d f o ro b t a i n i n gl o c a lo p t i m a ls o l u t i o n ，h o wt oo b t a i nt h eg l o b a l l yo p t i m a ls o l u t i o n s i sv e r yi m p o r t a n tt o p i c d u r i n gt h ep a s tf o u rd e c a d e s ，m a n yn e wt h e o r e t i c a l ，a l g o r i t h m i ca n dc o m p u - t a t i o r l “c o n t r i b u t i o n sh a v eh e l p e dt os o l v eg l o b 8 lo p t i m i z a t i o np r o b l e m sa r i s i n g f r o mi m p o r t a n tp r a c t i c a la p p l i c a t i o n s a m o n gt h ec o n t r i b u t i o nl i s t ，f o rg e n e r a l g l o b a lo p t i m i z a t i o np r o b l e m s ，t h ef i l l e df u n c t i o nm e t h o d s ，t h et u n n e l l i n gm e t h o d s a n dt h eb r a n c ha n db o u n dm e t h o d sa r eo f t e nt a l k e do f i nt h i sp a p e r b a s e do ns o m en e wc o n t r i b u t i o n s w et r yt oi m p r o v eo ns o m e a l g o r i t h m s ，i n c l u d i n gt h ef i l l e df u n c t i o nm e t h o d sa n dt h et u n n e l l i n gm e t h o d s w ea l s ot r yt op r e s e n ts o m en e wm e t h o d sa n de x t e n dt h er u e df u n c t i o nm e t h o d s a n dt h et u n n e u i n gm e t h o d sf o rt h ed i s c r e t ed o b a lo p t i m i z a t i o na n dn o n l i n e a r m i x e dm t e g e rp r o g r a m m i n g t h i sp a p e rm a i n l yc o n s i s t so ff o u rc h a p t e r s i nt h ef i r s tc h a p t e r ，s e v e r a lb a s i sc o n c e p t sa n dc h a r a c t e r s0 1 2g e n e r a l l yn o n l i n - e a rp r o g r a m m i n ga r ei n t r o d u c e d a n ds o m em a i l f l ym e t h o d sf o rg l o b a lo p t i m i z a - t i o np r o b l e m sa r eb r i e f i yp r e s e n t e d ，i n c l u d i n gt h e 蜘e df i l n c t i o nm e t h o d s ，t h e t u n n e l l i n ga l g o r i t h m s t h eb r a n c ha n db o u n dm e t h o d sa n dt h ei n t e g r a lm e t h o d s i nt h es e c o n dc h a p t e r ，f o rg e n e r a lu n c 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 np r o b - l e m s t h r e em e t h o d sa r ep r e s e n t e d ，i n c l u d i n gt h en e wm l e df u n c t i o nm e t h o d ，t h e m o d i f i e dt u n n e l l i n gm e t h o da n dt h ei n t e g r a lf u n c t i o nm e t h o d i ns e c t i o n2 2 n e wd e f i n i t i o no ft h ef i u e df u n c t i o ni sg i v e n i ti sd i f f e r e n t f r o mt h ep r i m a r yd e f i n i t i o nw h i c hw a sg i v e nb yg ei np a p e rf 1 9 b a s e do n t h ed e f i n i t i o n ，an e s tf i l l e df u n c t i o ni sp r o p o s e d ，a n di th a sb e t t e rp r o p e r t i e s a na l g o r i t h mf o ru n c 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 ni sd e v e l o p e df r o mt h en e w f i l l e df u n c t i o n t h ei m p l e m e n t a t i o no ft h ea l g o r i t h m so ns e v e r a lt e s tp r o b l e mi 8 r e p o r t e dw i t hs a t i s f a c t o r yn u m e r i c a lr e s u l t s i ns e c t i o n2 3 ，w eg i v eam o d i f l e dt u n n e l l i n gf u n c t i o n b a s e do nt h ef u n c t i o n ， a na l g o r i t h mf o rg l o b a lo p t i m i z a t i o ni sp r o p o s e d ，t h ea l g o r i t h mo v e r c o m e st h e s e 出s a d v a n t a g e so ft h et u n n e l l i n ga l g o r i t h m t h ei m p l e m e n t a t i o no ft h ea l g o r i t h m o ns e v e r a lt e s tp r o b l e mi sr e p o r t e dw i t hs a t i s f a c t o r yn u m e r i c 8 1r e s u i t s an e wa l g o r i t h mf o rg l o b a lm i n i r a i z a t i o ni si n t r o d u c e di ns e c t i o n2 4 b a s e d o na ni n t e g r a lh m c t i o na n dav e c t o rs e q u e n c e t h ea l g o r i t h mo v e r c o m e st h es h o r t c o m i n g so fs o m eo t h e rm e t h o d s ，w ef u r t h e rp r o v et h a tu n d e rs o m ec o n d i t i o n st h e i i i a l g o r i t h mc a nf i n da ns a p p r o x i m a t eg l o b a lo p t i m a ls o l u t i o na f t e rf i n i t en u m b e r o fi t e r a t i o n s n u m e r i c a lr e s u l t sc l e a r l yi n d i c a r et h ee f f i c i e n c ya n dr e l i a b i l i t yo f t h ep r o p o s e da l g o r i t h m i nc h a p t e rt h r e e ，t h en e wf i l l e df u n c t i o nm e t h o da n dt h em o d i f i e dt u n n e l l i n g m e t h o da x ee x t e n d e dt od i s c r e t eg l o b a lo p t i m i z a t i o np r o b l e m s ，a n dan e wa l - g o r i t h mc a l l e dt h eg r a d u a l l yd e s c e n tm e t h o di si n t r o d u c e df o rd i s c r e t e 出o b a l o p t i m i z a t i o np r o b l e n l s n u m e r i c a lr e s u l t sc l e a r l yi n d i e a t et h ee f f i c i e n c ya n dr e l p a b i l i t yo ft h e s ep r o p o s e da l g o r i t h m s i nc h a p t e rf o u r ，t h eg l o b a l l yc o n v e x i z e df i l l e df u n c t i o ng i y e nb yb yg ei n p a p e r 2 3 i se x t e n d e df o r t h em i x e di n t e g e rn o n l i n e a rp r o g r a m m i n g ( m i n l p ) t h e m i x e dl o c a lm i n i m i z e ro fm i n l pi sd e f i n e da tf i r s t ah 1 i x e dd e s c e n ta l g o r i t h mi s p r o p o s e df o rt h em i x e dl o c a lm l m m i z e r ，a n dak i n do fm i x e df i l l e df u n c t i o n si s c o n s t r u c t e d b a s e do nt h em i x e dd e s c e n ta l g o r i t h ma n dt h ek i n do fm i x e df i l l e d f u n c t i o n s an e wa p p r o a c hf o rm i n l pi sp r o p o s e d k e yw o r d s n o n l i n e a rp r o g r a m m i n g ；d i s c r e t eg l o b a lo p t i m i z a t i o n ；m i x e d i n t e g e rn o n l i n e a rp r o g r a m m i n g ；g l o b a lm i n i m i z e r ；t u n n e l l i n g f u n c t i o n b r a n c ha n db o u n d ；i n t e g r a lf u n c t i o n ；g l o b a lo p t i - m i z a t i o n ；f i l l e df u n c t i o n i v 上海大学博士学位论文 第一章全局最优化问题概述及基础知识 1 1 基础知识 最优化问题是研究最优解的特征和算法的- - r 7 应用性很强的学科，最优化问 题的一般形式是： m i n ，( 茁)( 1 1 1 ) 8 t x s 其中s = 茁形：吼( z ) 0 ，i = 1 ，2 ，p ，称s 为可行域，( x ) ：p r ， 称f ( x ) n 目标函数。 因为m a x f ( x ) ：x 研m l n f ( x ) ：z s ) ，所以最大化问题包含在 上面模型中。进而，由于g d x ) 0 等价于一g i ( x ) s0 ，n ( 。) = 0 等价于g i ( x ) 0 和一g d x ) 0 ，我们看到( 1 1 1 ) 包含了许多其它类型的约束。 如果可行域是整个n 维欧氏空间，那么下列问题称为无约束最优化问题： m i n ，( 茁)( 1 1 2 ) s t o 舻 如果s 是一个多面体对，称问题( 1 1 1 ) 是线性约束的；此外，若目标函数也是线性 的，该问题称为线性规划问题。当( 1 1 1 ) 中出现的函数至少有一个是非线性的， 该问题称为非线性规划问题。当目标函数，和每个约束函数g i 都是凸的时候t 问题( 1 1 ，1 ) 称为凸规f 0 1 f o 题。有时，当，是凸函数，s 是凸集时，问题( 1 1 1 ) 也 称为凸规划。 在本文中，为了方便统称问题( 1 1 1 ) 和问题( 1 1 2 ) 为原问题。如果不加特别 说明”i i 始终表示欧几里得范数；v ，( 茁) 表示f ( x ) 在点石处的梯度；v 2 f ( x ) 表示，( z ) 在点x 处的h e s s e 矩阵。 定义1 1 1 点s 称为一个局部极小点，如果存在某个s 0 ，对于所 有满足忙一矿1 | 的z s ，有，( 矿) ，( z ) ，而，( 矿) 称为局部极小值。 1 上海大学博士学位沦文 定义1 1 2 s 称为一个全局极小点，如果对于所有。s ，有f ( x + ) f ( x ) ，而，( 矿) 称为全局极小值。 在全局最优化问题中。凸规划具有很好的性质，也就是当目标函数是凸的， 可行域也是凸的时，凸规划的每个局部极小值就是全局极小值，所以我们可以应 用求局部极小点的方法，求得全局极小点，已有的局部极小化算法对它都是有效 的。而对于非凸的问题，可能存在到很多局部极小点，其函数值不同于全局极小 值，这样就使我们在求解全局最优化问题时面临很多困难，所以我们要首先研究 目标函数在可行域s 上的局部和整体性质。为此，我们首先回顾一些基本概念， 下面的定义和定理在大部分最优化的教材上都有叙述和证明，可以参考 4 ，3 5 。 定义1 1 3 函数，在s 上的下确界，记作i n f ( f ( x ) ：z s ) ，是，在s 上 的最大下界；函数，在s 上的上确界，记作s u p f ( x ) ：。s ) ，是，在s 上的 最小下界。 定义1 1 4 在sc 研上的一个实值函数，称为李普希兹函数，如果存在 一个常数l = l ( f ，s ) 0 ，使得对于所有x l ，x 2 s ，有 i ，( z 2 ) 一，0 1 ) l 墨三| i z 2 一x l i l ， 其中l 称为李普希嚣常数。 定理1 1 1 设sc 舻是凸的，f 在包含s 的一个开榘上连续可微，并且 在s 上具有有界的梯度，则f 在s 上是李普希兹函数，且李普希兹常数 l s u p l i v ( x ) d i ：z 研 定义1 1 5 sc 郧称为闲集，如果s 包含所有收敛点列 ) cs 的极限 点；s c j p 称为紧集，如果s 是闭的有界集。 由函数在紧集上的连续性我们可以得到下列著名的魏尔斯特拉斯定理： 定理1 1 2 。如果8 是冗n 中一个非空紧集，f ( x ) 是s 上的连续函数，那么 f ( x 1 在s 上至少有一个全局极小( 极大) 点。 定义1 1 6 集合s 冬m 上定义的实值函数，在s 上的点。处称为下 半连续，如果有，( z ) = l i m i n f f ( y ) ；f 在s 上的点舅处称为上半连续，如果有 f ( x ) = l i r as u p ，( p ) 。 f z 2 上海大学博士学位论文 容易看出，函数在x 点处既下半连续，又上半连续，则它在点处连续。在 定理1 1 2 中如果将，的连续替换成下半连续( 上半连续) ，那么定理仍然成立。 定义1 1 7 在凸集c 上函数f 的上方图e 硝( ，) 表示为：e p i ( f ) = ( ( z ，r ) c r ：r ，( z ) 。 在极小化问题和凸性的研究中，下半连续的表现形式和重要性与下面的结果 有关： 定理1 1 3 设s 是舻中一个非空闭集，是s 上任意一个函数，则下列 条件是等价的： j 在s 上，是下半连续的。 2 对于每个a r ，l ( ，；o ) = 如s ：f ( x ) 曼a ) 是闲的。 3 在r “+ 1 中，上方图e p i ( f ) 是闭集。 定义1 1 8 定义在形中的函数，( 嚣) 称为强审1 的，如果有堪m ，( ) = + o o 。 净 f 。 对于无约束最优化，其中s = j p ，若，是强制的，则全局极小点的存在性 问题可以借助定理1 1 2 来讨论。 定理1 1 4 。若，( 。) 是强制酌，并且连续，则，( 。) 在j p 中至少有一个全局 极小点 下面给出一些关于局部和全局极小点特征的结果。 定义1 1 9 向量d 卵称为点矿处的可行方向，如果存在 0 ，使得 对于每个0 a ”，有x + + a d s ( s 是问题的可行域) 。 令，在点矿的一个邻域内连续可微，并且令d j p 满足d r v s ( z ) 0 ， 其中表示式d t v f ( x ) 是在矿处沿方向d 的方向导数。对于固定矿和d ，函数 f ( x + + a d ) 描述了，沿射线忙= 矿+ d ，a o 的情况。因为 ，( 茁+ a d ) = ，( z ) + 入d r w ( x + + 口a d ) ， 这里0 口 1 是某个确定的数。所以d r w ( x + 】 0 ， 使得对于每个0 as _ ，有，( 矿+ a d ) ，( 矿) 。也就是，可以沿方向d ，使， 局部地下降。所以我们有如下定理： 定理1 1 5 假没函数，( z ) 在一个包含sc 舻的开纂内连续可微若矿是 3 上海大学博士学位论文 的一个局部极小点( 相对于s ) ，则对于每个可行方向d i 都有d t v f ( x + ) 0 。 定义1 1 1 0 点x + s 称为平稳点，如果对于每十个可行方向d ，都有 d t v f ( x ) 0 。 i 对于一般问题来说，平稳点并不一定是极小点，但是对于凸规划问题，我们 有下列定理： 定理1 1 6 若，是一个在包含s 的开集内连续可微的凸函数，并且s 是 一个凸集，则x + s 是一个全局极小点，当且仅当矿是 个平稳点。 定理1 1 7 凸函数f ：s r ( 其中s 彤是凸州) 的每一个局部极小点 也是全局极小点。 定义1 1 1 1 凸集s 边界上的点x 称为一个极点，如果不存在互异的两点 x l ，x 2 s ，使得。= 入z l + ( 1 一a ) 茁2 ，0 ，( 。；) ，则称在z ；处的盆谷b ；比z ：处的盆谷b ；低，或称b i 比b ；高 孤立点。i 处盆谷研的半径定义为： r = i n f 忙一。孙 口f 钟“ 如果，( ) 在z j 处的h 髑s e 矩阵v 2 ，( z j ) 正定，则r 0 。 在定义1 2 1 和定义1 2 2 的基础上，葛仁溥在文献【2 1 】中给出了一个填充函数 的定义： 定义1 2 3 函数p ( $ ，z ；) 称为，( z ) 在局部极小点z ：处的填充函数，如果 满足? ( 1 ) 。：是p ( z ，z ：) 的一个严格局部极大点，f ( x ) 在点z i 处的盆谷b ；成为 p ( x ，z i ) 的峰的一部分。 ( 2 ) p ( x ，z ：) 在比b ；高的盆谷里没有平稳点。 ( 3 ) 如果存在比b ；低的盆谷彤，则存在x 7 b ；使得p ( 。，z ；) 在z 和 o ：的连线上存在极小点。 由填充函数的定义可以看出，如果当前极小点不是全局极小点的话，通过极 小化填充函数，我们可以跳出原问题当前局部极小点，并到达一个原问题函数值 比当前局部极小值还要小的点。毫无疑问，从该点出发极小化原问题目标函数， 必将导致一个原问题目标函数值更小的局部极小点。 填充函数算法由两个阶段组成：极小化阶段和填充阶段。这两个阶段交替使 用直到找不到更好的局部极小点。在第一阶段里，可以用经典的极小化算法寻找 目标函数的一个局部极小值点名：。然后进入第二阶段，在当前极小点x i 处定义 一个填充函数，通过极小化填充函数，找到点7 霉j ，使得 ，( 卫) 0 并且 p l ( 盘) ：p l ( $ ：) + p = t t 去l - , t 、( 。一z ：) 2 马( 。+ 1 ，。) ，p l ( 盘) = p l ( $ ：) + - j ? 2 ( 。一z ：) 2 马( z + ，z ) ， 所以，如果$ ：不是全局极小点，那么存在一些点满足。；和p 。( x 7 ，) 0 ，使得p l ( f ) 0 并且 p ( i ，+ 、 p l ( z ) = p l ( $ ：) + 二上；型扛一z ；) 2 尸2 ( z ；，z ) ， 所以，如果z ：不是全局极小点，那么存在一些点满足z ：和p 2 ( z ：，) 0 ，使得p l ( f ) 马( z ：) 。因此，我们可以通过极小化b ( z ：，z ) 找到它的局部极小 使得p l ( f ) 马( z i ) 。因此，我们可以通过极小化玛( z ：，z ) 找到它的局部极小 上海大学博士学位论文 点。2 。如果p 2 ( z ；，z 2 ) 0 ，那么以x 2 为初始点极小化目标函数p 1 缸) ，必将得 到一个更好的局部极小点。如果户2 ( x l ，x 2 ) 20 ，这个过程被延续： 假设男( z i ，z 2 ) 0 ，构造下列函数： 瞩加鼍韶群， 并且寻求该函数值小于零的点。假设马( 。；，x 2 ，z ) 在。3 处取得最小值。如果 p 3 ( z i ，x 2 ，x 3 ) 0 ，我们就可以以该点为初始点，极小化函数p 2 ( x l ，x ) ，并得到该 函数的一个更小的极小值，如果p 3 ( 。：，x 2 ，x 3 ) 0 并且嚣( z ：，x 2 ，x 3 ) 0 ，我 们可以类似的构造只( $ i ，x 2 ，x 3 ，。) ，继续上面的过程。 因为( r 的次数) = ( r l 的次数) 一2 ，所以上述过程仅涉及有限多个多项 式函数，而且r + 。是一个常数。因为r + 1 不能被减少，可推出r 也不能被减 少，因此r 一1 也不能被减少，最后可推出p l 不能被减少。所以茁i 是全局极小 点。另一方面，如果z 是p 1 ( z ) 的局部极小点，因为这钆一1 个多项式最多有有 限个的极小点，所以上述过程可以在有限步内，找到点，满足r ( ) ，( 茁 ) ，那么构造打洞函数 t ( 硼= 两哥肄卷面研 这里q 1 是扛一。1 ) 7 一x 1 ) 的强度。目的是使x l 不再是t ( x ，。；) 的局部 极小点，防止极小化t ( x ，z ：) 时，又得到。1 。然后重新极小化r ( z ，z i ) 。 3 如果f ( x 1 ) 矿= m i n f ( x ) ，令 w ，c ) = 厕1 厶( m ) 一册p ， 其中凰是水平集如上述定义，称v l ( f ，c ) 是函数f 在水平集匝上的均方差。 定理1 2 3 对于问题( p ) ，下面几个性质是等价的： ( ) 矿使问题( p ) 的全局极小值点，c 4 = f ( x + ) 为相应的全局极小值。 ( 2 ) m ( f c 1 = 0 。 ( 鲫( ，c ) = 0 。 在此基础上给出了积分方法的概念性算法，其详细叙述如下： 算法 1 取。o s ，给定一个充分小的正数s ，令c o = f ( x o ) ，凰。= 茹s ：f ( x ) c 0 ，k = 0 。 2 若肛( 也。) = 0 ，则c k 为全局极小值，玩。为全局极小值点集，转6 。 3 计算均值 c k 4 - 1 = 志厶。m m 2 币西止。八叫即 且令c = x s ：f ( x ) c k + l 。若“+ l = c k ，则c k + 1 为全局极小值， 皿。为全局极小值点集，转6 ；否则，转4 。 4 计算方差 y f = 上g ( h o ) o 。( m h 2 舡 5 ，若y f e ，则令舟：= + 1 ，转2 ：否则，转6 。 6 令，+ = c k + 1 ，且h = 风。，终止。日4 为，( 茹) 在s 中的近似全局极小值 点集，广为相应的近似全局极小值。 如果在上述算法中令= 0 ，则迭代将无限的进行下去，我们可以得到两个 单调下降的点列 c k ) 和 风。) 。由于这两个点列均有界，故它们都收敛。令 矿= 1 i r ac k ， 和 h + = 墨恐如= n 匝。，m + 。 上海大学博士学位论文 则我们有下述收敛定理。 定理1 2 4 若 为上述算法生成的序列，则矿是问题( p ) 的全局极小 值，日+ 是全局极小值点集。 积分型求全局极小值算法在理论上给出了收敛性的证明，并且该算法仅需要 计算目标函数值，故适用于较大范围的全局最优问题。但在一般情况下，水平集 是无法得到的，故原始文献中的实际算法是通过m o n t e c a r l o 随机取点来缩 小搜索范围。在下一章中，我们也给出一个利用积分的算法，并从理论上证明了 算法的收敛性，虽然有些不尽完美，也是对这类算法改进的一个有益尝试。 1 8 上海大学博士学位论文 第二章非线性规划的全局最优化算法 2 1引言 在第一章中，我们介绍了与全局最优化问题相关的基础知识和儿种常见的确 定性方法，包括分支定界算法、填充函数算法、打洞算法和积分水平集算法，其 中填充函数算法和打洞函数算法是利用函数的局部性质，逐步找到全局最优。算 法思想是首先通过局部极小化算法，找到一个局部极小点，然后进一步找到更好 的解，或者证明当前极小点已经是全局极小点了。为此。这类算法在当前局部极 小点处，构造一个辅助函数，通过极小化辅助函数，为进一步找到原问题的更好 的解创造有利条件( 如果原问题有更好解的话) ，例如，通过极小化辅助函数， 找到一个目标函数值比当前极小值还要小的点，以该点为初始点，应用局部下降 算法必将得到一个比当前极小点更好的一个解。这类方法我们可以通称为辅助函 数法。而对于大部分的分支定界算法，和积分水平集算法，则是一开始就利用目 标函数的整体性质，直接迭代找到原问题的全局最小。 在这一章中，主要考虑如下无约束的全局极小化问题： m i n ，( z )( 2 1 1 ) s , t z r ” 在下面几节中，我们提出了几种求解上述问题的算法，包括新的填充函数 法、变形打洞函数法和积分函数法。 本章是这样安排的：每一节都独立地给出了一种算法，它包括理论分析、算 法描述和数值结果，为了说明算法的有效性，每一节中我们都给出一个算例的解 的过程的直观图形表示。为了简明起见，所用到的试验函数都集中的放在本章的 附录中。 2 2 无约束全局最优化的填充函数法 在这一节中，我们给出了一个新的填充函数的定义，它有别于葛在文章【2 1 】中 1 9 上海大学博士学位论文 给出的传统定义。基于这个定义，我们构造了一个新的填充函数，给出了一个新 的算法，应用该算法进行了大量的数值试验，实验证明该算法是有效的，同时也 克服了些前面提到的以前的填充函数法的缺点。 2 2 。1 新的填充函数及其性质 首先，我们给出关于问题( 2 1 1 ) 的如下假设： 假设1 ( x ) 是强制的，也就是当| | 。j f 一+ o 。时，( 茁) 一+ 。 由假设l ，我们可推出，一定存在一个紧集qc 舻，它的内部包含了( x ) 的所有全局极小点和函数值小的局部极小点，而且可以认为目标函数在n 的边 界上的函数值大于在其内部的函数值，因此，问题( 2 1 1 ) 等价于下列问题： m i n ( z )( 2 2 1 ) s t o q 假设2 ，( 。) 在q 上是连续可微的，且梯度有界。 由定理1 1 1 ，我们知道，( z ) 也是一个李普希兹函数，且李普希兹常数 l s u p l l v f ( x ) 1 1 ：z q 假设3 ，( 。) 仅有有限个极小值。 假设3 有别于最初葛在1 1 9 】中假设2 ，它不要求有有限个极小点，而是只要 求有有限个极小值，这表示愿问题的局部极小点的个数可以是无限的。 现在我们给出一个填充函数的新的定义，它不同于最初葛在( 1 9 1 中提出的 填充函数的定义( 见定义1 2 3 ) 。定义如下： 定义2 2 1 函数p ( x ，石i ) 称为，( z ) 在局部极小点。 处的填充函数，如果 满足? ( 1 ) 茁：是p ( z ，z ) 的一个严格局部极大点 ( 2 ) p ( z ，z ；) 在s l = 扛i ，( 茁) ，( 。：) ，z q ； ) 上的梯度不等于零。 ( 3 ) 如果。：不是全局极小点，那么p ( x ，t 。1 ) 一定在s 2 = zf ( x ) 0 和r 满足0 0 ) ，使得对于任意z 0 ( 茁 ，6 ) 并且。z ；，我们有，( z ) ，( ；) 。当y ( x ) = ，( z i ) 时，显然有f ( x ，。；，q ，r ) ，( 矿) 上海大学博士学位论文 的情况。 图2 2 ，l ：f ( x ) = x s i n x 和f ( x ，z ；，q ，r ) ，其中q = 0 5 ，r = 0 2 。 渊= 志吲筹一丽， = 南吲塑端紫悉学， s 南吲罴燃i 眈当口2 鲁时删】有蒜黼 万2 q 2 1 ；并且，当 1 同时o 时，不等式e 。 r 毛成立所以我们有 粼f(x*1q 高饮p ( 型t 2 ( f ( x 黼)，。 ，r ) 、口+ 0 。一 l i “、) 一，( ) + r ) 尚m 一罴黼， q r 2 ( f ( x ) 一f ( x * 1 ) + r ) g + 0x z ：0r 2 ( ，( 。) 一，( 。：) + r ) 一2 q 2 ( ，( z ) 一，( 。i ) ) q r 2 ( ， ) 一f ( x * 1 ) + r ) q r 2 ( ，( 茁) 一，( 。i ) + r ) + a 2 2 上海大学博士学位论文 其中 a = , r 2 i | 正z ：l 【( ，( 。) 一，( z i ) + r ) 一2 q 5 ( ，( ) 一，( ：) j 一2 q 2 l i $ 一x ；l l ( f ( x ) 一，( z i ) ) 由假设2 ，并且令o q 0 因为当o g 0 适当的小时，函数f ( 七，x 1 ，口，r ) 在s l = 忙l ，( z ) ，( z ：) ，霉 q z i 上的梯度不等于零。 证明：任取z s 1 ，那么，( 茁) ，( z ；) 和。z i 。我们有 v 肌，味”) t 斋南 一雨南唧( 一蕊矿薪) 2 + 再币词 ， q 2 、v ( x ) t 0 一x 1 ) q 2 戗p ( 一丽万了i 两哥 f = 百丌一顶万了巧矿研 一厕去孺唧( 争志霎 一面了面磊乏三晒= i 孵e x p ( 一) + 2 l 善一面了面磊乏i 晒= i 孵e x p 【一声j + 2 l 令m = 搿忙一蚓| ，取。 g r a i n l ，南 ，那么 v m ，味 ) t 存禹 一击锛唧( 一石q ) + 丽南 2 3 上海大学博士学位论文 因此当0 q 0 适当的小时，数f ( x ，x 1 ，q ，r ) 在s l = 。l ，0 ) ，( z i ) ，z a z 上梯度不等于零。 口 定理2 2 3 如果。i l ( p ) 不是，( 茁) 在q 上的全局极小点，那么在岛= x l f ( x ) 0 的选取，那么一定存在满足f ( x ) 一，( z ：) + r = 0 的点，不妨记作 霹，即有 ，( 硼一f ( z * 1 ) + r = 0 也就是说：f ( 磊，g ：，q ，r ) = 0 。因为在n 上，f 0 ，z ：，q ，r ) 0 ，所以f ( z ，嚣i ，q ，r ) f ( 可，矿，q ，r ) ，因此可是f ( z ，z i ，q ，r ) 在q 上的全局极小点，当然是局部极小 点。口