（计算数学专业论文）几类非凸规划问题的全局最优解方法.pdf

摘要 全局最优化问题是一门研究非线性函数在某个区域上全局最优点的特征和计算方法 的科学，广泛见于金融、网络和交通、化学工程、分子生物学及环境工程等诸多领域由 于全局优化问题具有多极值性，使得传统的非线性规划技术很难用来求解，因此研究此类 问题的求解算法既有重要意义，又极具挑战性随着全局优化方法的广泛应用，其理论和 算法也得到了很大发展，但这些算法也存在许多问题本文将在现有某些算法的理论基础 上，针对几类特殊的全局优化问题，研究新的更有效的方法主要内容如下： 第一章，概括介绍了目前国内外几种主要的求解全局优化问题的确定性方法和随机性 方法，以及它们的研究现状，并对本文所做的工作给予简单介绍 第二章，针对一类非凸规划问题( n p ) ，将由j i a o 提出的全局优化方法与一个合适的 删除技巧相结合，提出了一个新的加速算法这一技术提供了一种可能来割掉当前所考虑 的区域中不包含全局最优解的一大部分，因而可以看作是一种加速策略与参考文献中的 方法相比，数值结果表明：通过采用这一新的删除技巧，在迭代次数，需要的链表长度和 总的运行时间上，计算效率都有明显改进 第三章，针对带离散约束的广义几何规划问题，提出了一个具有一般性的全局求解 方法为了极小化原问题，首先利用问题的特殊结构，构造了一个等价的带有离散约束 的单调优化问题，然后提出了几个容易执行的基本操作来得到全局最优解特别地，减 小和调整操作能割掉最优解不存在的一大部分区域，因此能提高算法的有效性最后，证 明了所提方法能够保证收敛到全局最优解，并用数值试验表明了算法的可行性和有效性 关键词：全局优化，非凸规划，单调优化，离散广义几何规划 i i a b s t r a c t t h er e s c a r c ho fg l o b a lo p t i m i z a t i o nm e t h o d sf o c u s e so nt h ec h a r a c t e r i s t i ca n dc o r n p u t i o n a lm e t h o do ft h eg l o b a lo p t i m a lp o i n to ft h en o n l i n e a rf u n c t i o no v e rs o m ec o n v e xo r n o n c o n v e xa r e a g l o b a lo p t i m i z a t i o np r o b l e m sa r o u n df i n a n c e n e t w o r ka n dt r a n s p o r t a - t i o n ，c h e m i c a le n g i n e e r i n g ，m o l e c u l a rb i o l o g y , e n v i r o n m e n t a le n g i n e e r i n g ，a n ds oo n d u e t om u l t i e x t r e m u mp r o p e r t yo fg l o b a lo p t i m i z a t i o np r o b l e m s ，a l lt h e s ep r o b l e m sc a nn o t b es o l v e de a s i l yb yc l a s s i c a ln o n l i n e a rp r o g r a m m i n gt e c h n i q u e s ，t h e r e f o r e ，s t u d i n gs o l u - t i o n sf o rt h i sk i n do fp r o b l e m sn o tn o l yh a si m p o r t a n ts i g n i f i c a n c e ，b u ta l s oh a sc h a l l e n g e e x t r e m e l y g r e a td e v e l o p m e n th a v eb e e no b t a i n e di nt h et h e o r i c a la n da l g o r i t h ma s p e c t s o fg l o b a lo p t i m i z a t i o nd u et oi m p o r t a n tp r a t i c a la p p l i c a t i o n s ，b u tt h e r eu s u a l l ye x i s ts o m e p r o b l e m sd u r i n gt h e c o u r s eo fa l g o r i t h m s c o m p u t a t i o n w ep r o p o s ean e we f f e c t i v em e t h o d b a s e do nk n o w nt h e o r ya n da l g o r i t h m sf o rs o m es p e c i a lg l o b a lo p t i m a lp r o b l e m s m a i n c o n t e n t sa r ea sf o l l o w s i nc h a p t e r1 ，w ei n t r o d u c eb r i e f l ys e v e r a lm a i n l yd e t e r m i n i s t i ca p p r o a c h e sa n ds t o c h a s - t i ca p p r o a c h e s t h e nw eg i v et h el a t e s tr e s e a r c hd e v e l o p m e n to ft h e s ea p p r o a c h e s ab r i e f i n t r o d u c t i o ni sg i v e na b o u to u rw o r ki nt h i sp a p e ri nt h ee n d i nc h a p t e r2 ，w ec o m b i n et h eg l o b a lo p t i m i z a t i o nm e t h o dp r o p o s e db yj i a ow i t ha s u i t a b l ed e l e t i n gt e c h n i q u et op r o p o s ean e wa c c e l e r a t i n gg l o b a lo p t i m i z a t i o na l g o r i t h m f o rs o l v i n gac l a s so fn o n c o n v e xp r o g r a m m i n gp r o b l e m s ( n p ) t h i st e c h n i q u eo f f e r sa p o s s i b i l i t yt oc u ta w a y al a r g ep a r to ft h ec u r r e n t l yi n v e s t i g a t e dr e g i o ni nw h i c ht h eg l o b a l i i i o p t i m a ls o l u t i o no f ( n p ) d o e sn o te x i s t ，a n dc a nb es e e na sa na c c e l e r a t i n gd e v i c ef o rt h e g l o b a lo p t i m i z a t i o na l g o r i t h mo ft h en o n c o n v e xp r o g r a m m i n gp r o b l e m s c o m p a r e dw i t h t h em e t h o di nt h ea b o v ec i t e dr e f e r e n c e ，n u m e r i c a lr e s u l t ss h o wt h a tt h ec o m p u t a t i o n a l e f f i c i e n c yi so b v i o u s l yi m p r o v e db yu s i n gt h i sn e wt e c h n i q u ei nt h en u m b e ro fi t e r a t i o n s ， t h er e q u i r e dl i s tl e n g t ha n dt h eo v e r a l le x e c u t i o nt i m eo ft h ea l g o r i t h m i nc h a p t e r3 ，w ep r e s e n t sag e n e r a la p p r o a c hf o rg l o b a l l ys o l v i n gg e n e r a l i z e dg e o m c t r i cp r o g r a m m i n g ( g g p ) p r o b l e m sw i t hd i s c r e t ec o n s t r a i n t s f o rm i n i m i z i n gt h ep r o b l e m ， a ne q u i v a l e n tm o n o t o n i co p t i m i z a t i o np r o b l e mw i t hd i s c r e t ec o n s t r a i n t si sc o n s t r u c t e db y e x p l o i t i n gt h es p e c i a ls t r u c t u r eo ft h e ( g g p ) p r o b l e m s ，a n dt h e ns e v e r a lb a s i co p e r a t i o n s t h a tc a nb ee a s i l yi m p l e m e n t e da r ep r o p o s e dt oo b t a i nag l o b a lo p t i m a ls o l u t i o n s p e c i a l l y t h er e d u c t i o na n da d j u s t i n go p e r a t i o n sc a nc u ta w a yal a r g ep a r to ft h er e g i o ni nw h i c h t h eo p t i m a ls o l u t i o nd o e sn o te x i s tt oe n h a n c et h ee f f i c i e n c yo ft h eo p t i m i z a t i o na p p r o a c h i ts h o w st h a tt h ep r o p o s e dm e t h o di sg u a r a n t e e dt oc o n v e r g et oag l o b a lo p t i m u m a n d f i n a l l yt h en u m e r i c a le x p e r i m e n ti sr e p o r t e dt ov i n d i c a t et h ef e a s i b i l i t ya n de f f e c t i v e n e s s o ft h ep r o p o s e dm e t h o d k e yw o r d s ：g l o b a lo p t i m i z a t i o n ，n o n c o n v e xp r o g r a m m i n g ，m o n o t o n i co p t i m i z a t i o n ， d i s c r e t eg e n e r a l i z e dg e o m e t r i cp r o g r a m m i n g i v 摘 要 a b s t r a c t 第一章绪论 目录 1 1 全局优化算法概述 1 1 1 确定性方法 1 1 2 随机陛方法 1 2 本文的研究背景及主要工作 i i i i 1 第二章求一类非凸规划问题全局解的加速方法 9 2 1 引言 9 2 2 删除技巧 9 2 3 算法及其收敛性 1 7 2 3 1 算法步骤 1 7 2 3 2 算法分析 1 8 2 4 数值试验 2 0 第三章求解带离散约束广义几何规划问题全局最优解方法 2 5 3 1 引言， 2 5 3 2 等价单调转化 2 5 3 3 基本操作 2 9 3 3 1 分枝规则 3 0 v 3 3 2 下界。 3 1 3 3 3 减小割 3 4 3 3 4 调整策略 3 8 3 4 算法及收敛性 3 9 3 4 1 算法描述 3 9 3 4 2 收敛性 4 0 3 5 数值试验 4 1 结论 参考文献 致谢 攻读学位期间发表的学术论文目录 独创性声明 v i 9 1 7 9 1 4 5 5 5 6 1 1 全局优化算法概述 第一章绪论 全局优化问题的来源相当广泛，包括经济，金融，网络与运输，数据库与芯片设计， 图像处理，核能与机械制造，化学工程设计与控制，分子生物学以及环境工程等在过去 的几十年里，全局优化的理论与算法都得到了很大发展，尤其是在生产生活中很多具有重 要意义的全局优化问题，例如：非凸规划、二次规划、广义几何规划、单调优问题等，都 有了一些理论及求解算法 现有的全局优化方法依据它们的收敛性质分为随机性方法和确定性方法两大类前者 包含遗传算法【1 】，随机函数法【2 】，模拟退火算法【3 4 】，神经网络算法 5 】等，这类方法 有对目标函数性质要求低、容易实现、稳定性好等突出特点，但效率低、可靠性差、不能 保证产生优化问题的最优解相比之下，确定性方法具有充分利用问题的解析性质产生一 个确定性的有限或无限的点序列并使其收敛于全局最优解通常所指的全局性解析性质包 括凸性、单调性、稠密性、李普希兹常数和水平集等这类方法包括分枝定界方法【6 】、 区间方法 7 8 】、填充函数方法 9 】、割平面方法【1 0 】、顶点枚举方法【1 1 等，这类方 法大多根据所求优化问题目标函数和约束函数的特征而构造相应的算法这类算法通常有 较高的计算效率 考虑如下形式的全局优化问题： m i n i m i z e s u b j e c tt o f ( x ) 吼( z ) 0 ， b ( z ) = 0 ， 其中z = ( x l ，z 2 ，z 。) t r n 函数f ：r n _ r 称为目标函数，q = z 舻ig i ( x ) 0 ，i = 1 ，m ；h j ( x ) = o ，歹= 1 ，f ) 舻称为可行域若存在x + q ，且对一切 z q ，都有，( z + ) ，( z ) ，则称x 。为问题的全局最优解 下面给出目前国内外在确定性方法和随机性方法方面所取得的一些进展 仇 l ， ， b l i i | 1 z 几类非凸规划问题的全局最优解方法 1 1 1 确定性方法 所谓全局优化的确定性算法主要是指利用问题的解析性质产生一确定性的有限或无 限点列使其收敛于全局最优点的算法主要利用的解析性质有凸性和单调性在确定性方 法这一部分，主要有以下几类算法 ( 1 ) 分枝定界方法 分枝定界方法是全局优化主要方法之一，其基本思想是通过把可行域逐渐剖分加细， 同时相应的构造出最优值单调减少的上界序列和单调增加的下界序列，当上界和下界相等 或者上界与下界的差满足误差要求时，迭代终止，得到全局最优解；否则迭代继续进行下 去根据剖分过程和上下界估计过程的选取不同，分枝定界方法大体上可分为两类，一类 是把切甲面过程与分枝定界技术相结合，另一类是使用目标函数逼近( 或下估计) 过程 分枝定界方法被广泛地应用在整数规划、非线性规划等优化模型中，近年来一直是人们研 究的热点，人们一直在寻找求解的新途径 ( 2 ) 区间方法 区间方法考虑的问题是 m i 罂，( z ) ， z x 、 其中x 是n 维区间，f ：r n _ r 区间全局优化的基本思想是将分枝定界方法和m o o r e - s k e l b o e ( 1 2 算法相结合这类算法都包含精确区问计算，且算法的执行效率依赖于区间 扩张的构造方法它的突出优点是能在给定精度内求出问题的全部全局极小点下面从不 同方面概括最近几年区间算法的研究进展就区间扩张构造的方法来说，在文献 1 3 中， y kf a n g ( 2 0 0 3 ) 给出了区间扩张函数的最优中心形式当函数的变量为一维时，文献 1 4 】 给出了一个新的区间扩张函数在文献【1 5 】中， e c a r r i z o s a 等人证明了通过区间平移 能够改进区间扩张函数上下界就区间分裂技术而言，j l l a g o u a n e l l e 和g s o u b r y 【1 6 给出了一个新的区间最优多分裂技术就加速工具而论，r a t z 【1 7 】在1 9 9 9 年利用区间 斜率对一维非光滑函数提出一个区间删除技术申培萍和张可村【1 8 2 0 】分别对一维的 可微函数和n 维的非光滑函数研究了相应的区间剪枝技术在文献【8 】中， m s u n 和 a w j o h n s o n 通过局部抽样给出了一个新的删除技术，再与分枝定界方法相结合给出了 2 第一章绪论 一个新的区间算法 ( 3 ) 填充函数法 填充函数法考虑的问题是 ( p 1 础m i n 。，( z ) z t t r 填充函数法由r g e 最先提出，他在文献【2 1 】中构造了求解问题( p ) 的填充函数算法这 类方法的基本思想是：首先利用局部极小点的方法求得f ( x ) 在可行域中的一个极小点z ：， 然后构造填充函数，设法找f ( x ) 的另一个比z ；低的局部极小点z ；，即z ；x 2 且满足 ，( z ；) 0 上述问题( n p ) 已广泛应用于产品计划，任务管理，化学工程，金融优化等实际问题 中将文献【3 5 】提出的求解一类非凸规划问题全局最优解方法与一个合适的删除技巧相结 合，提出了一个新的加速全局优化算法来求解问题( n p ) 这个技巧可以被看做非凸规划 问题全局优化算法的一种加速策略与参考文献中的方法相比，数值结果表明通过利用新 的删除技巧，算法在迭代次数，最大节点个数以及执行时间等方面的效率都有明显改进 在第三章中，针对带离散约束的广义几何规划问题( d g g p ) ： ( d g g p ) ：1 眦兰舌：，m 乩m 其中 西。( 可) = 玑蛳，m = 0 ，l 1 一，u o ， = 1 = 1 f l o = ( 可砰l0 0 成立，给出如下记号： 隆y j t m = l n x j t , ”墨, 枷嵫m ( 2 - 1 ) 因此，对任意的z q ，由式( 2 - 1 ) 容易导出玛t 。，k t 在q 上的下界和上界，分别记 做弼。，珞和弼。，磁，由下式给出： 和 刊。m 娣m 瑶= 瑗= n = i = 1 礼 = i = 1 m i n c j t m i x _ i ，c j r m i 夏) d j r m a x c j t m i x i ，勺棚瓦】十也m ， 1 t m i n 一j t m l n 叫咖l n 弼。) ， j t m a x 坳m l n 刊t 。，t 。l n ? 吩。 ， 其中勺t 僦代表c j t m 的第i 个分量 1 0 利用( 2 - 1 ) 式，每一个g j ( z ) 0 = 0 ，1 ，m ) 能重新写做 q ( z ) = 乃 t t - - - - 1 乃 l ix ：器= l = l 乃弓t p j t e x p ( e t m 协t 。) = t e x p ( y j t ) ， t = lm = lt = 1 ( 2 - 2 ) ( 2 - 3 ) ( 2 4 ) 一 ，、【，、一， 第二章求一类非凸规划问题全局解的加速方法 首先考虑g j ( z ) ，j o ，1 ，m ) 中的分项 q ( 可) 全t e x p ( t 。协拥) = o t j c e x p ( y j t ) ， 其中t 1 ，殇) 对每一个q t ( 可) ，构造它的仿射下界函数l a s t ( y ) 为了这个目的，考虑函数e x p ( y ) 在区间【y ，y “】和函数l n ( x ) 在区间。，x “1 上的 仿射下界函数，分别记做l ( e x p ( y ) ) 和l ( 1 n ( x ) ) ，以及仿射上界函数，分别记做u ( e ) 【p ( y ) ) 和u ( 1 n ( x ) ) 利用e x p ( y ) 的凸性和l n ( x ) 的凹性，相应的仿射下界函数和仿射上界函数 为： l ( e x p ( y ”= a ( 1 + y h a ) ( 2 - 5 ) 、， 【u ( e x p ( y ) ) = a ( y y ) + e x p ( y ) ， 和 l ( 1 n ( x ”= b ( x x f ) + 1 n ( j x f ) ， ( 2 6 ) 【u ( 1 n ( x ) ) = b x l n b 一1 ， 并且满足 l ( e x p ( y ) ) e x p ( y ) u ( e x p ( y ) ) ，vy 【，y ”】，( 2 - 7 ) 和 l ( 1 n ( x ) ) l n ( x ) u ( 1 n ( x ) ) ， v x 【x ，x “】，( 2 - 8 ) 其中 a = e x p 弋( y 矿q - r e x p ( y t ) ，b = i n ( x 页 ) _ - 可l n ( x 1 ) 以2 可e 可广一，乃2 1 f j f 一 基于上述讨论，用巧t 和如t 代替式( 2 - 5 ) 和( 2 7 ) 中相应的符号y 和a ，可以得到函 数g j t ( ) 在【珞，磁】上的仿射下界函数l g j t ( y ) 如下： 蚴：卜l ( e x p ( v j o ) 礼p o 【a j t u ( e x p ( y j t ) ) ，若t 0 ， 【t a j t ( y j t 一瑶) + e x p ( y j t ) ， 若q j t 0 ， 若t 0 ， 若哟t m o ， l g j t ( x ) = 焉1 l a 3 t l g j t m ( z ) + “e x p ( 瑶) 一a j t 珞】，若t t m 0 和p u b ，那么对任意的茁q 南有l g 3 ( x ) r l 3 u b ，也即 g o ( z ) l g ：( z ) r l ： u b 因此，问题( n p ) 在q 七上不存在最优解 ( i i ) 如果对某个h 1 ，礼) 有入 0 和菇 p 2 ：堕丝盟雩逊幽 o 入z u b r l 3 + m i n a o k 7 l 墨，入： 硝) 由上面的式子可以得出 1 4 n 入z i + 醋= 入x h + i = 1 ，t h 入z t + 醋 u b r l k o + m i n a o h 式，a 虿2 ) + = u b i = 1 ，i a 包z t + 醋 u b 一m i n 【a 磁，入舻k - - i k 】+ 地反 ub i = l ，i h i = l ，i h 十 ：i z入 壹州 魂碓酸七毗 a n mm 十 霉砖岔磕 璺m n 僦。 第二章求一类非凸规划问题全局解的加速方法 这表明 vz q ： 因此，问题( n p ) 在q ：上没有最优解 采用类似的方法，如果对某个h 1 ，他 有a 建，那么也能得到问 题( n p ) 在瞄上没有最优解 口 定理2 3 对任意子矩形q 七= ( q ；) 。x 1cq o ，下述结论成立： ( i ) 如果对某个j 1 ，m ) 有r l ； 岛成立，那么问题( n p ) 在绺上不存在可 行解 ( i i ) 如果对每一个j 1 ，m ) 都有r l ；侍，考虑下面两种情况：若对某个 歹 1 ，m ) 存在指标h 1 ，扎) 使得a 0 和磕 岛，那么对任意z q 七有 因此问题( n p ) 在q 知上没有可行解 ( i i ) 如果对每一个j 1 ，m ) 有r 骘岛，首先考虑第一种情况，若对某个j 1 ，m ) 和h 1 ，佗) 有喙 0 和嚎 一 z 0 g ，j ll，l 岛 蠡， lr = 够 + 、，弓 七一弘 入 誊 七一弘 入mn n 曲 一 够 上 兢 七一弘 入 。!l = z 唠 l 一 z q 几类非凸规划问题的全局最优解方法 此外，根据入氛 0 ，上述公式表明 入孰z 岛一r 骘+ m l - l t k ，凶k ；，啄露) 更进一步，对任意z 磷可以得到 c j ( x ) l 唠( z ) = 入缸+ 劈 乎1 = 磅h x h + 嗨戤+ 劈 = 岛一舢- l k k ，橼k - - 山；k ) + m i n 喙或，喙磁 + 嗨如 i = 1 i = l ，诤，l = 岛一m i n a 兰鸢，入j k 以- - k + 嗨如 i = l ，i i = 1 ，i 反 这意味着问题( n p ) 在q ! 上没有可行解，这证明了第一种情况 第二种情况的证明过程与第一种情况相似，此处省略这就完成了整个证明过程口 根据定理2 2 和定理2 3 ，下面给出一种新的删除技巧来割掉问题( n p ) 的全局最优解 不存在的一些区域令q 七= ( 嘴) 。l 嘴= 隧，- - z ；k 】( i = 1 ，佗) 是q o 的任个子矩形 删除技巧 ( s 1 ) 最优性准则：计算式( 2 1 1 ) 中的r l 3 如果r l 3 u b ，置q 七= 0 ；否则，计 算式( 2 1 2 ) 中的露( i = 1 ，礼) 若对某个h 1 ，礼) 有a 0 和硝 有入 盛，则令猷= j 9 2 置 q 七= ( q ? ) 竹1 ，其中q ? = 嘭，- - z i k 】( i = 1 ，几) ( s 2 ) 可行性准则：对任意的j = 1 ，m ，计算式( 2 1 1 ) 中的冗；如果对某个 歹 1 ，m ) 有r l ； 岛成立，那么置阱= d ；否则，计算式( 2 1 3 ) 中的嗾0 = 1 ，m ，i = 1 ，n ) 若对某个j _ 【1 ，m ) ，h 【1 ，几 有a 氟 0 和嚅 u b ， 或者存在指标j 1 ，m ) 使得r 易 岛，那么将相应的子矩形q 从q 七中剔除，即 瓯：= 瓯q ，然后跳到q 尼中的下一个元素 步4 ：( 定界) 如果q 七仍，对每一个q 哦，求解r l p ( f 2 ) 得到z ( q ) 和l b ( q ) 如果l b ( f 2 ) u b ，置= q 南q ；否则，更新上界u b ，如有必要也更新可行点集f 令矿= a r g m i n g o ( x ) lz f 目前剩余的剖分集q k = ( 阢q ) u 瓯，新的下界 l b ( k ) = m i n l b ( q ) lq q k 步5 ：( 收敛性检测) 置q 七+ 1 = 阢 qj 己b ( q ) 2u b e ，q 钒) 如果q 七+ 1 = d ，终 止算法，u b 为最优值，矿为最优解否则，选取个满足l b ( q 1 ) = a r g m i n l b ( q ) iq 阢+ 1 ) 的节点q 1 作进一步的考虑，令扩“= x ( e k + 1 ) 置k = k + 1 ，返回步1 2 3 2 算法分析 下面给出上述算法的全局收敛性质如果算法不是有限步终止，分枝规则能保证所有 分量的区间收敛到一个点另一方面，应该证明当i q i 一0 时松弛线性规划r l p ( f 1 ) 趋向 到n p ( f 1 ) 定理2 4 对任意的q = 匠，司q o 和y 歹 o ，1 ，m ) ，令q ( z ) 和l 岛( z ) 分 别由问题n p ( f 2 ) 和r l p ( f 1 ) 定义那么，对vz q ， ( z ) 与l g j ( z ) 的差满足 g j ( z ) 一l g j ( z ) _ 0 当i l 虿一xi l _ 0 ， 其中| | z xi i = m a x 夏一x iii = 1 ，佗) ，j = 0 ，1 ，m 1 8 第二章 求一类非凸规划问题全局解的加速方法 证明 对任意的z q = k ，_ 】q o ，令玛c 。，刊t 。和驾k 由式( 2 - 1 ) 和( 2 - 2 ) 定 义对任意j o ，1 ，m ) ，t 1 ，功) 和m 1 ，乃t ) ，令哟m = 弼。一刊。m 因为 ( 夏一亟) ， 所以当i i 虿一星0 _ 0 时，t m _ 0 因此，根据参考文献 3 5 】中的定理1 有 证毕 g ( z ) 一l g j ( x ) 一0 ，当i lz xi l 一0 ，v 歹( o ，1 ，m ) 口 定理2 5 上述算法要么有限步终止，产生问题( n p ) 的一个全局e 近似最优解x + ， 要么沿着分枝定界树的分枝产生一个无穷序列 z 七) ，它的任意个聚点都是全局最优解 证明 如果算法是有限步的假定它终止于第k ( k20 ) 步那么算法终止时有 u b l b ( k ) e 由算法中的步0 和步4 ，能够得到问题( n p ) 的一个可行解x + ，这意味着 g o ( x + ) 一l b ( k ) e 记u 为问题( n p ) 的最优值，那么根据第2 部分的讨论，有 l b ( k ) t ， 因为矿是问题( n p ) 的可行解，所以 g o ( x + ) u 综合以上三个式子，可以得到 u g o ( x ) l b ( k ) + e u + e ， 因此矿是问题( n p ) 在 g o ( x ) t ，+ e 1 9 咖 勺 他烈 = 溉砖 一 仇碌 = 拥 几类非凸规划问题的全局最优解方法 这个意义下的一个全局e 最优解 如果算法无限终止，全局优化方法收敛的一个充分条件是定界操作必须是相容的且选 择操作是界改进的 3 7 】 定界操作称为相容的，如果在每一步中，任意一个未考虑的剖分能得到进一步的修 正，并且任意一个经过修正的剖分元素无穷下降序列满足 。l i m ( u b l b ( k ) ) = 0 ， ( 2 1 5 ) k 其中l b ( k ) 是在第k 次迭代的一个下界， u b 是当前最好的上界下面我们证明( 2 1 5 ) 式成立因为算法采用的对分过程是o t 对分，这一过程是穷举的相应地，由定理2 1 和 v ( r l p ) v ( n p ) ，式( 2 1 5 ) 成立，这表明采用的定界操作是相容的 选择操作称作是界改进的，如果在实际下界能取到的剖分集中至少有一个剖分元素在 经过有限次修正后能再次被选择到显然，采用的选择操作是界改进的，因为取到最小下 界的剖分元素在紧接着的下一次迭代中能得到进一步剖分 总之，我们证明了算法中的定界操作是相容的，选择操作是界改进的因此，根据文 献 3 7 】中的定理3 ，提出的优化算法能收敛到问题( n p ) 的全局极小值 证毕 口 2 4 数值试验 为了测试加速算法的有效性，我们采用v i s u a lf o r t r a n 编程，利用单纯形方法求解松 弛线性规划，置收敛误差为e = 1 0 e - 8 ，测试了以下1