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

摘要 最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一 门独立的学科还是在本世纪4 0 年代末，是在1 9 4 7 年d a n t z i n g 提出求解一般线性 规划问题的单纯形算法之后。随着工业革命、信息革命的不断深化，和计算机技 术的巨大发展，至今短短的几十年，它得到了迅猛的发展。现在，解线性规划、非 线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种 最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学等方面 得到了广泛的应用，成为一门十分活跃的学科。 全局最优化是最优化一个重要分支。相对于线性规划等分支，它在理论和算 法上远没有那么成熟、完善，大多数的全局最优化算法缺少终止准则。但是现实 社会对它有更多更迫切的要求，使得全局最优化工作者利用不同的数学理论和工 具，提出了各式各样的算法，从理论到算法，都具有强大的生命力，而且需要进 一步完善、深化。例如，在函数变换的基础上，提出了填充函数法；在非线性方 程理论的基础上，提出了打洞函数法：在微分方程动力系统的基础上，提出了动 力打洞算法；在积分原理的基础上，提出了积分水平集算法；在组合理论的基础 上提出了分支定界算法，在随机和启发式基础上提出了模拟退火法、遗传算法等 等。 全局最优化算法，从算法的构造上大体可以分为确定型算法和随机型算法， 例如，填充函数法、打洞函数法属于确定型算法：模拟退火法、遗传算法属于随 机型算法。我们在这篇文章中仅仅考虑非线性规划的全局最优化确定型算法、非 线性整数规划的全局最优化确定型算法和非线性混合整数规划的全局最优化确 定型算法。这篇文章的主要目的就是，在研究已有确定型算法的基础上，尝试提 出一些改进和创新。力图在算法效果方面有所提高，在理论方面有所深化。其内 容详细情况如下： 在第一章中，我们介绍了几种常见的全局最优化算法，以及他们的特点。这 包括：填充函数法、打洞函数法、分支定界算法和积分水平集算法。每一个算法 i 都有各自的优缺点。首先，我们从算法思想到相关理论都给出一些深入浅出的说 明，在此基础上，分析了各自的优点和缺点，为我们进一步的推广和构造新的算 法，提供一些指导思想和思路。 在第二章中，在研究填充函数和打洞函数的基础上，为克服打洞函数算法的 一些缺点，在本章的第三节中，提出了修正打洞函数算法。该算法降低了对参数 的依赖，具有较好的可操作性。数值试验显示，该算法是有效和可靠的。 在第三章中我们给出修正打洞算法的数值试验 在第四章中，我们考虑了非凸二次规划问题，在研究分支定界算法的基础上， 给出了一种求解非凸二次规划问题的分支定界算法，并取得了较好的计算效果。 关键词：混合整数规划非线整数性规划非线性规划全局最优解填充函 数打洞函数分支定界积分函数。 i i a b s tr 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 ，m 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 lm 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 n a lc 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 a 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 色a 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 ef i l l e df u n c t i o nm e t h o d s a n dt h et u n n e l l i n gm e t h o d sf o rt h ed i s c r e t eg l 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 di n t e g e rp r o g r a m m i n g t h i sp a p e r m 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 so ng 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 n 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 l yp r e s e n t e d ，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 8 ，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 ， w eg i v eam o d i f i e dt u n n e 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 r g 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 ed i s a d v a n t a g e so f t h et u n n e l i n ga l g o r i t h m i nc h a p t e rt h r e e ，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 mo ns e v e r a lt e s tp r o b l e m s i 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 a lr e s u l t s i nc h a p t e rf o u r ，ab r a n c ha n db o u n da p p r o a c hf o rn o n c o n v e xq u a d r a t i cp r o - g r a z n m i n gw i t hq u a d r a t i cc o n s t r a i n e di si n t r o d u c e d i nt h ep r o p o s e da l g o r i t h m ， w em a k eu s eo ft h el i p s c h i t zc o n d i t i o nt od e t e r m i n el o w e rb o u n d so ff u n c t i o n s o v e re a c hr e c t a n g l e f u r t h e r ，c o n v e r g e n c eo ft h ea l g o r i t h mi sp r o v e d c o m p u t a - t i o n a le x p e r i m e n t sa r er e p o r t e do ns o m eq u a d r a t i cp r o g r a m m i n gp r o b l e m s ，a n d c o m p u t a t i o n a lr e s u l t sc a ns h o wt h a tt h ep r o p o s e da l g o r i t h mi se f l i c i e n t 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 i i i f i m c t i o mb r a n c ha n db o u n d ； m i z a t i o n ；f i l l e df u n c t i o n i v 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 本论文使用授权说明 e l 期：竺鱼兰 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名爰陋日期：全趔 上海大学硕士学位论文 第一章全局最优化问题概述及基础知识 1 1 基础知识 最优化问题是研究最优解的特征和算法的- - f 应用性很强的学科，最优化问 题的一般形式是： r a i n ，( z ) s t z s ( 1 1 1 ) 其中s = z 舻：吼 ) 0 ，t = 1 ，2 ，p ) ，称s 为可行域，( z ) ：舒一r ， 称，0 ) 为目标函数。 因为m a x f ( x ) ：z s 】= 一m i n - - f ( x ) ：z s ) ，所以最大化问题包含在 上面模型中。进而，由于吼( z ) 0 等价于一吼p ) s0 ，仇( z ) = 0 等价于吼( z ) s0 和一吼( z ) 0 ，我们看到( 1 1 1 ) 包含了许多其它类型的约束。 如果可行域是整个几维欧氏空间，那么下列问题称为无约束最优化问题： i l 洫f ( x )( 1 1 2 ) 8 z 彤 如果s 是一个多面体时，称问题( 1 1 1 ) 是线性约束的；此外，若目标函数也是线 性的，该问题称为线性规划问题。当( 1 1 1 ) 中出现的函数至少有一个是：- - = i i e 线性的， 该问题称为非线性规划问题。当目标函数，和每个约束函数吼都是凸的时候， 问题( 1 1 1 ) 称为凸规划问题。有时，当，是凸函数，s 是凸集时，问题( 1 1 1 ) 也 称为凸规划。 在本文中，为了方便统称问题( 1 1 1 ) 和问题( 1 1 2 ) 为原问题。如果不加特别 说明”0 始终表示欧几里得范数；v f ( x ) 表示f ( x ) 在点z 处的梯度；v 2 f ( x ) 表示，( z ) 在点z 处的h e s s e 矩阵。 定义1 1 1 点矿s 称为一个局部极小点，如果存在某个e 0 ，对于所 有满足i i x z + l i 的z s ，有，( 矿) s ，( z ) ，而，( 矿) 称为局部极小值 】 上海大学硕士学位论文 定义1 1 2 矿s 称为一个全局极小点，如果对于所有z s ，有f ( x + ) ，( z ) ，而，( 矿) 称为全局极小值 在无约束全局最优化问题中，凸规划具有很好的性质，也就是当目标函数是 凸的，可行域也是凸的时，凸规划的每个局部极小值就是全局极小值，所以我们 可以应用求局部极小点的方法，求得全局极小点，已有的局部极小化算法对它 都是有效的。而对于非凸的问题，可能存在到很多局部极小点，其函数值不同于 全局极小值，这样就使我们在求解全局最优化问题时面临很多困难，所以我们要 首先研究目标函数在可行域s 上的局部和整体性质。为此，我们首先回顾一些 基本概念，下面的定义和定理在大部分最优化的教材上都有叙述和证明，可以参 考 4 ，1 9 。 定义1 1 3 函数f 在s 上的下确界，记作i n f f ( x ) ：z s ) ，是，在s 上 的最大下界；函数，在s 上的上确界，记作s u p f ( x ) ：z 研，是，在s 上的 最小下界 定义1 1 4 在sc 舻上的一个实值函数，称为李普希兹函数，如果存在 一个常数工= l ( f ，s ) 0 ，使得对于所有z l ，x 2 s ，有 i ，( z 2 ) 一f ( x 1 ) i l 0 2 2 一x l l l ， 其中二称为李普希兹常数 定理1 1 1 设sc 胛是凸的，在包含s 的一个开集上连续可微，并且 在s 上具有有界的梯度，则，在s 上是李普希兹函数，且李普希兹常数 工s u p l w f ( x ) 1 ：z s ) 定义1 1 5 sc 舻称为闭集，如果s 包含所有收敛点列 戤 cs 的极限 点；sc 形称为紧集，如果s 是闭的有界集 由函数在紧集上的连续性，我们可以得到下列著名的魏尔斯特拉斯定理： 定理1 1 2 如果s 是舻中一个非空紧集，0 ) 是s 上的连续函数，那么 ， ) 在s 上至少有一个全局极小( 极大) 点 2 上海大学硕士学位论文 定义1 1 6 集合s p 上定义的实值函数f 在s 上的点z 处称为下半 连续，如果有f ( x ) = l i r ai n f f ( y ) ；f 在s 上的点z 处称为上半连续，如果有 v 工 f ( x ) = l i ms u p ，( y ) 容易看出，函数在z 点处既下半连续，又上半连续，则它在z 点处连续。在 定理1 1 2 中如果将，的连续替换成下半连续( 上半连续) ，那么定理仍然成立。 定义1 1 7 在凸集c 上函数f 的上方图e p i ( f ) 表示为：倒( ，) = ( z ，- ) cxr ：，( z ) ) 。 在极小化问题和凸性的研究中，下半连续的表现形式和重要性与下面的结果 有关： 定t 1 1 1 3 设s 是舻中一个非空闭集，是s 上任意一个函数，则下列 条件是等价的： j 在s 上，是下半连续的 2 对于每个q r ，l ( ，；q ) = z s ：f ( x ) q ) 是闭的 只在舻+ 1 中，上方图卿( ，) 是闭集。 定义1 1 8 定义在舻中的函数f ( x ) 称为强制的，如果有。蟮mf ( x ) = + o o i i x - * o o 对于无约束最优化，其中s = 舻，若，是强制的，则全局极小点的存在性 问题可以借助定理1 1 2 来讨论。 定理1 1 4 若， ) 是强制的，并且连续，则f ( x ) 在舻中至少有一个全局 极小点 下面给出一些关于局部和全局极小点特征的结果。 定义1 1 9 向量d 舻称为点矿处的可行方向，如果存在” 0 ，使得 对于每个0 入”，有矿+ s ( s 是问题的可行域) 令，在点矿的一个邻域内连续可微，并且令d 舻满足d t v f ( x ) 0 ， 其中表示式d t v f ( x ) 是在z + 处沿方向d 的方向导数。对于固定矿和d ，函数 f ( x + x d ) 描述了，沿射线 z = 矿+ 2 d ，入o 的情况。因为 f ( x + 入d ) = ，( z ) + 入d t v f ( = + 口入d ) ， 3 上海大学硕士学位论文 这里0 0 1 是某个确定的数。所以d t v f ( x ) 0 ， 使得对于每个0 入天，有f ( x + 入d ) f ( x + ) 。也就是，可以沿方向d ，使， 局部地下降。所以我们有如下定理： 定理1 1 5 假设函数f ( x ) 在一个包含sct p 的开集内连续可微若矿是 的一个局部极小点( 相对于s ) 则对于每个可行方向d ，都有d t v f ( x ) 0 定义1 1 1 0 点矿s 称为平稳点，如果对于每一个可行方向d ，都有 d t v f ( x ) 0 对于一般问题来说，平稳点并不一定是极小点，但是对于凸规划问题，我们 有下列定理： 定理1 1 6 若，是一个在包含s 的开集内连续可微的凸函数，并且s 是 一个凸集，更i j 矿s 是一个全局极小点，当且仅当矿是一个平稳点 定理1 1 7 凸函数f ：s _ 冗( 其中s 舻是凸的) 的每一个局部极小点 也是全局极小点 定义1 1 1 1 凸集s 边界上的点z 称为一个极点，如果不存在互异的两点 z l ，x 2 s ，使得z = a x l + ( 1 一a ) x 2 ，0 ，( z ；) ，则称在z ；处的盆谷e 比z ；处的盆谷b ：低，或称b ：比e 高 孤立点z ：处盆谷研的半径定义为： r = i n 忙一z 孙 z g b ? ” 如果f ( x ) 在z ：处的h e s s e 矩阵v 2 ，( z ：) 正定，则兄 0 。 在定义1 2 1 和定义1 2 2 的基础上，葛仁溥在文献 1 1 m 给出了一个填充函数 的定义： 定y 1 2 3 函数p ( x ，z ：) 称为f ( x ) 在局部极小点z ；处的填充函数，如果 满足： ( 1 ) z ；是p ( x ，z ；) 的一个严格局部极大点，f ( x ) 在点z i 处的盆谷b ：成为 p ( z ，z ：) 的峰的一部分 ( 2 ) v ( z ，z ：) 在比研高的盆谷里没有平稳点 ( 3 ) 如果存在比b ：低的盆谷e ，则存在b 主使得p ( x ，z ：) 在一和 z ；的连线上存在极小点 由填充函数的定义可以看出，如果当前极小点不是全局极小点的话，通过极 小化填充函数，我们可以跳出原问题当前局部极小点，并到达一个原问题函数值 比当前局部极小值还要小的点。毫无疑问，从该点出发极小化原问题目标函数， 必将导致一个原问题目标函数值更小的局部极小点。 填充函数算法由两个阶段组成：极小化阶段和填充阶段。这两个阶段交替使 用直到找不到更好的局部极小点。在第一阶段里，可以用经典的极小化算法寻找 1 0 上海大学硕士学位论文 目标函数的一个局部极小值点z ：。然后进入第二阶段，在当前极小点z ：处定义 一个填充函数，通过极小化填充函数，找到点一z ：，使得 f ( x 7 ) 0 并且 p ，十、 只 ) = 只0 ：) + 半( z z ：) 2 b ( 正：，z ， 所以，如果z ：不是全局极小点，那么存在一些点满足z ：和b ( z ：，) 0 ，使得r ( ) b ( z ：) 。因此，我们可以通过极小化马( z ；，z ) 找到它的局部极小 点x 2 。如果岛( z i ，x 2 ) 0 ，那么以x 2 为初始点极小化目标函数只0 ) ，必将得 到一个更好的局部极小点。如果易( z ；，z 2 ) 0 ，这个过程被延续： 假设硝 ：，x 2 ) 0 ，构造下列函数： 蹴垆鼍掣群， 并且寻求该函数值小于零的点。假设b ( z ：，x 2 ，z ) 在z 3 处取得最小值。如果 p 3 ( x ；，x 2 ，z 3 ) i 0 ，我们就可以以该点为初始点，极小化函数b ( z ：，z ) ，并得到该 函数的一个更小的极小值，如果b ( z ：，x 2 ，x 3 ) 0 并且胃( z ：，现，z 3 ) 0 ，我 们可以类似的构造只( z ：，x 2 ，x 3 ，z ) ，继续上面的过程。 因为( r 的次数) = ( r 一1 的次数) 一2 ，所以上述过程仅涉及有限多个多项 式函数，而且r + 1 是一个常数。因为r + 1 不能被减少，可推出r 也不能被减 少，因此r l 也不能被减少，最后可推出只不能被减少。所以z ：是全局极小 点。另一方面，如果z ：是只( ) 的局部极小点，因为这n 1 个多项式最多有有 限个的极小点，所以上述过程可以在有限步内，找到点f ，满足b ( ) ，( z ：) ，那么构造打洞函数 m 属) = 旺可乒瑞箍可砑， 这里q 1 是 一x 1 ) t ( z z 1 ) 的强度。目的是使x l 不再是t ( x ，z ；) 的局部 极小点，防止极小化t ( x ，z ；) 时，又得到x l 。然后重新极小化t ( z ，z ：) 。 3 如果， 1 ) 矿= m i n f ( x ) ，令 m ( f ，c ) = 厕1l f ( z ) 咖， 其中 玩= 扛s ：f ( x ) c ) ， 称m ( f ，c ) 是函数，在水平集皿的均值 定义1 2 5 设c 矿= m i n f ( x ) ，令 v l ( f ，c ) = 厕1 厶( m ) 一叨2 p ， 其中皿是水平集如上述定义，称v l ( f ，c ) 是函数f 在水平集凰上的均方差 定理1 2 3 对于问题( p ) ，下面几个性质是等价的： ( j ) 矿使问题( p ) 的全局极小值点，矿= ，( 矿) 为相应的全局极小值 ( 2 ) m ( f ，c ) = 0 ( 3 ) ( ，c ) = 0 在此基础上给出了积分方法的概念性算法，其详细叙述如下： 算法 1 取x o s ，给定一个充分小的正数e ，令c o = ，( 跏) ，月乙= z s ：， ) c d ) ，k = 0 。 1 7 上海大学硕士学位论文 2 若p ( 皿礓) = 0 ，则铅为全局极小值，皿疆为全局极小值点集，转6 。 3 计算均值 c k + l2 志厶他) d u ， 2 硒j 厶。m ， 且令上k + 。= z s ：f ( x ) 仇+ l 。若仇+ l = c k ，则c k + 1 为全局极小 值，+ 。为全局极小值点集，转6 ；否则，转4 。 4 计算方差 y f = 志厶。( m ) 一计咖 5 若y f ，则令k ：= k + 1 ，转2 ；否则，转6 。 6 令广= c k + 1 ，且h = 冠+ ，终止。h + 为，( z ) 在s 中的近似全局极小值 点集，广为相应的近似全局极小值。 如果在上述算法中令= 0 ，则迭代将无限的进行下去，我们可以得到两个 单调下降的点列 ) 和 皿。) 。由于这两个点列均有界，故它们都收敛。令 和 则我们有下述收敛定理。 c = 1 i mc k ， 七- - + h + 如= n 玩，。- - * o o k = l 定理1 2 4 若 ) 为上述算法生成的序列，则c 是问题( p ) 的全局极小 值，日是全局极小值点集 积分型求全局极小值算法在理论上给出了收敛性的证明，并且该算法仅需要 计算目标函数值，故适用于较大范围的全局最优问题。但在一般情况下，水平集 是无法得到的，故原始文献中的实际算法是通过m o n t e c a r l o 随机取点来缩 小搜索范围。在下一章中，我们也给出一个利用积分的算法，并从理论上证明了 算法的收敛性，虽然有些不尽完美，也是对这类算法改进的一个有益尝试。 1 8 上海大学硕士学位论文 第二章无约束全局最优化的变形打洞函数 2 1 引言 在第一章中，我们介绍了与全局最优化问题相关的基础知识和几种常见的确 定性方法，包括分支定界算法、填充函数算法、打洞算法和积分水平集算法，其 中填充函数算法和打洞函数算法是利用函数的局部性质，逐步找到全局最优。算 法思想是首先通过局部极小化算法，找到一个局部极小点，然后进一步找到更好 的解，或者证明当前极小点已经是全局极小点了。为此，这类算法在当前局部极 小点处，构造一个辅助函数，通过极小化辅助函数，为进一步找到原问题的更好 的解创造有利条件( 如果原问题有更好解的话) ，例如，通过极小化辅助函数，找 到一个目标函数值比当前极小值还要小的点，以该点为初始点，应用局部下降算 法必将得到一个比当前极小点更好的一个解。这类方法我们可以通称为辅助函 数法。而对于大部分的分支定界算法，和积分水平集算法，则是一开始就利用目 标函数的整体性质，直接迭代找到原问题的全局最小。 在这一章中，主要考虑如下无约束的全局极小化问题： r a i nf ( x ) s t z 形 ( 2 1 1 ) 在第一章中我们介绍了求全局最优化的打洞函数算法，然而它存在着一些缺 点。在这一节中，我们提出了一类变形打洞函数，试图克服这些缺点。同样，变 形打洞函数法也分为两个阶段：极小化阶段和打洞阶段，在打洞阶段我们首先要 避免极( p o l e ) 的出现，第二要避免找到满足，0 1 ) ，( z ：) 的打洞函数的局部极 小点z 1 ，同时不要使打洞函数变得更平坦，而且不需要解常微分方程，使算法更 简易有效。这样，我们提出的变形打洞函数算法在算法设计和计算效果上都取得 了较大的改进。下面我们将给出详细论述。 1 9 上海大学硕士学位论文 2 2变形打洞函数及其性质 与第2 2 1 节二样，首先，我们给出关于问题( 2 1 1 ) 的如下假设： 假设1 ( x ) 是强制的，也就是当l lz0 一+ o o 时，( x ) _ + 。 假设2 ( x ) 是q 上的连续可微函数，且梯度有界。 假设3 ( x ) 仅有有限个极小值。 同样，我们可以等价的考虑如下问题： r a i n ，( z ) s t z q ， ( 2 2 1 ) 这里qc 形是个紧集。 变形打洞方法同样由两阶段组成： 第一阶段，局部极小化目标函数阶段，同打洞算法； 第二阶段，构造依赖于参数的变形打洞函数t ( x ，矿) ，使得满足 t ( x ，z ) = 0 甘f ( x ) 一，( z ) + r = 0 ( 这里矿为， ) 的当前的局部极小点，o r 型盟二丝：2 1 2 。( 1 + q ( f ( x ) 一，( z ) + r ) 2 ) 2 ( ( 1 + 矿2 ) 三一m z i iz 一知f l y ( z ) ) ， 因此，当q 充分大时，v t i ( z ，矿) 呙 0 ，从而v 乃( z ，矿) 六 上海大学硕士学位论文 ( 2 ) 现在我们考虑乃( z ，矿) 。 因为， ) f ( x ) ，那么 v 乃( z ，z ) = ( f ( x ) 一( x ) + r ) 2一( z - x o ) 丁了i 五万i 丁二丽+ r ) z0z x o1 1 2 0z x o0 1 ，2 ( ，( z ) 一，( z ) - i - r ) v ，( 。)2 q ( f ( x ) 一，( 矿) + r ) 3 里，( z ) 、 广丌i = 写o0 、1 + q c f ( x ) 一f ( x + ) + 7 ) 2 ( 1 + q ( f c x ) 一，( z + ) + r ) 2 ) 2 7 2 ( f ( x ) 一f ( x + ) - t - r ) 2 而j 司r 再瓦而f 页万石汗 ( 一( 1 + 口( ，( z ) 一，( z + ) + r ) 2 ) 鱼生半晶 + 0z c r , o0v ，( z ) ) ， 1 j f 以 v 死( 叩+ ) 呙= 耵i 矿2 ( f 矸( x ) 丽- f 酉( x * ) = 了- l - r 丽) ( 一( 1 + g ( ，( z ) 一，( z ) + r ) 2 ) 鱼羔二掣 + i ix - - x 0i iv f ( z ) 篙知) ，2 ( ( x ) 一，( z 。) + r ) 而j 可r 弄瓦蓐声页方石阿 ( - ( i + c r 2 ) 兰+ 搿怕一跏 i v f ( z ) ) ， 因此，当口充分大时，v 正( z ，矿) 尚 0 充分小 时，则存在正仕，矿) ，乃( z ，矿) 的局部极小点矿i n t f l ，使得 ， ) 一f ( x ) + r 0 证明：因为矿l ( p ) 不是， ) 在q 上全局极小点，那由函数的连续性， 一定存在，扛) ， + ) ，又由于r 的选取满足下列不等式： 0 r m a x ( ( x ) 一，( z ：) ) ， z ：e l ( p ) 。 ，( 重：) 0 ，那么矿是f ( x ) 的全局极小点 由上述定理知，从矿出发求f ( x ) 的局部极小点z ：，一定成立，( z ：) ，( 矿) 的问题，但终止准则仍是一个未解决的 问题。在下一节中，针对这两个变形打洞函数，我们给出了相应的求全局最优问 题的变形打洞函数函数法，同时给出了应用该算法的数值试验的结果。 上海大学硕士学位论文 第三章变形打洞算法 在以往的填充函数法和打洞函数法中，我们仅仅采用一种形式的辅助函数， 通过极小化该函数求得更好的初始点。现在在新提出的变形打洞函数法中，我们 使用两个变形打洞函数，也就是乃( z ，矿) ，易( z ，矿) ，在找到目标函数的局部极 小后，我们构造两个变形打洞函数五( z ，矿) ，正( z ，矿) ，然后任选一个初始点，从 该初始点出发，同时极小化这两个变形打洞函数，这样可以增大发现新初始点的 几率，因此，不失为一种新的思路。下面我们给出该算法的详细描述： 1 初始化 3 1 算法 选取0 0 选取x o 譬q ，并且满足忙一= o l i 1 选取初始点z 2 q 令k = 1 2 主程序 l o 以z 2 为初始点，应用局部下降算法极小化目标函数， ) ，得到问 题( 2 2 j ) 的一个局部解，记为z ：令i = 1 ，r = 1 ，q = 1 0 2 0 如果i ，转到8 0 ；否则，转到3 0 3 0 如果r r o ，终止算法迭代，当前极小点z ：作为问题( 2 2 j ) 的全 局极小点；否则，转到4 0 4 0 如果口q o ，那么，令r = , - 2 ，q = 1 0 ，i = 1 ，转到8 0 ，否则，令 q = l o q ，i = 1 ，转到8 0 2 4 上海大学硕士学位论文 8 0 任选孤q ，如果f ( x k ) ，( z z ) 令k = 后+ i ，z 2 = x k ，并且转 至41 0 ；否贝4 转王49 0 9 0 令 t 1 ( x ，x 加_ 1 1 2 - - 2 0 l l 高器虢黼 t 2 ( x ，加= 南毒啬器黼 并且垢= 垢= 孤，进入内循环 3 内循环 1 0 令m = 0 2 0 应用局部下降算法例如，拟牛顿法、共轭梯度法等等，以编为初始 点极小化打洞函数乃( z ，z ：，q ，r ) ，令姥表示其第仇个迭代点 应用局部下降算法例如，拟牛顿法、共轭梯度法等等，以垢为初始 点极小化打洞函数t 2 ( z ，z ：，q ，r ) ，令镌表示其第m 个迭代点 3 0 如果谤隹q ，并且谚岳q ，那么令i = i + 1 ，转到主程序2 0 ；否则 转到4 0 4 0 如果，( 鳊1 ) ，( z ：) ，并且珐q ，那么令k = k + 1 ，z 2 = 蝓1 ，转 到主程序1 0 ；否则转到5 0 5 0 如果，( 镌) ，0 ：) ，并且镌+ l q ，那么令k = 忌+ 1 ，z 2 = 镌， 转到主程序l o ，否则令m = m + 1 ，并且转到3 0 现在我们来解释一下算法的思想，从总体上说，我们提出的变形打洞函数法 也分为两个阶段，即极小化阶段和变形打洞阶段，在上面的算法中我们将极小 化阶段放在主程序中，将变形打洞阶段放在内循环中。在变