（计算数学专业论文）几类特殊非凸规划问题的分支定界算法.pdf

摘要 全局优化研究的是多变量非线性函数在某个约束区域上全局最优点的特征和计算方 法全局优化问题已广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领 域分支定界算法是全局优化主要算法之一，近年来一直是最优化领域的研究热点，人们 一直在寻找求解的新途径和新方法本文在已有理论基础上，针对几类特殊的非凸规划问 题，分别给出求其全局最优解的分支定界算法主要内容如下： 首先，针对凸约束域上凹比凸比式和问题给出一锥形分支定界方法首先，通过引入 变量，将原问题转化为等价的非凸规划问题然后对等价问题构造分支定界算法，其中利 用凹包络构造松弛凸规划问题，从而将估计上界问题转化为一系列凸规划问题，这些凸规 划易于求解而且规模不变，更容易编程实现和应用到实际问题中；分支采用锥分并且给出 一紧缩上界的过程最后，理论分析和数值实验表明所提出的算法是可行有效的，且数值 结果与现有方法相比，迭代次数和运行时间都有显著改进 其次，针对带自由变量的广义几何规划问题给出基于分支定界过程的凸化方法首先 利用等价转换将原问题中的自由变量转化为正变量，再通过凸化方案建立了松弛凸规划 通过逐次的可行域的细分及求解一系列松弛凸规划，从理论上证明了算法收敛到原问题的 全局最优解最后，数值结果表明了算法的可行性该算法和其它算法相比可处理含有更 多变量的符号项 最后，针对凸约束域上线性比式和问题给出了一全局优化算法该算法通过引入新 的变量，将原问题转化为等价的规划问题，再利用等价问题和凸化技术，建立了松弛凸规 划通过对可行域的逐次细分及一系列松弛凸规划的求解，从理论上证明了算法收敛到原 问题的全局最优解最后数值例子表明本文算法是可行有效的 关键词：全局优化，分支定界，比式和，凹包络，广义几何规划，线性比式和 a b s t r a c t g l o b a lo p t i m i z a t i o nm e t h o d sr e s e a r c ht h ec h a r a c t e ra n dt h ec o m p u t a t i o n a lm e t h o do f t 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 ns o m er e g i o n t h eg l o b a lo p t i m i z a t i o n p r o b l e m sh a v eb e e nv e r ye x t e n s i v ei ne c o n o m i cp l a n ，e n g i n e e r i n gd e s i g n ，p r o d u c t i o nm a n - a g e m e n t ，t r a n s p o r t a t i o n ，n a t i o n a ld e f e n s e ，a n ds oo n t h eb r a n c ha n db o u n da l g o r i t h mi s o n eo ft h ef r e q u e n t l y - u s e da n de f f i c i e n tg l o b a lo p t i m i z a t i o nm e t h o d s ，a n di th a sb e e nah o t t o p i co fr e s e a r c hi nt h eg l o b a lo p t i m i z a t i o nf i e l d si nr e c e n ty e a r s t h eb r a n c ha n db o u n d a l g o r i t h m sa r ep r o p o s e db a s e do ns o m ek n o w nt h e o r i e sf o rg l o b a l l ys o l v i n gs e v e r a lc l a s s e s o 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 r e s p e c t i v e l y m a i nc o n t e n t sa r ea u sf o l l o w s ： f i r s t l y , ac o n i c a lb r a n c h - - a n d - - b o u n da l g o r i t h mi sp r o p o s e df o rt h es u mo fc o n c a v e - c o n v e xr a t i o sp r o b l e mo v e rac o n v e xs e t f i r s t ，t h ep r i m a lp r o b l e mi se q u i v a l e n t l yr e f o r - m u l a t e di n t oan o n c o n v e xo p t i m i z a t i o np r o b l e mb yi n t r o d u c i n gn e wv a r i a b l e s n e x t ，a b r a n c ha n db o u n da l g o r i t h mi sc o n s t r u c t e df o rs o l v i n gt h ee q u i v a l e n tp r o b l e m b yu s i n g c o n c a v ee n v e l o p e ，as e q u e n c eo fr e l a x a t i o nc o n v e xp r o g r a m m i n gp r o b l e m sa r ec o n s t r u c t e d f o rs u p p l y i n gt h eu p p e rb o u n d si nt h ep r e s e n t e da l g o r i t h m t h e n ，t h ek e yp r o b l e m so f e s t i m a t i n gu p p e rb o u n d sa r ee q u i v a l e n tt ot h es e q u e n c eo fr e l a x a t i o nc o n v e xp r o g r a m m i n g p r o b l e m sw h i c hd on o tc h a n g ei ns c a l ea n dc a nb es o l v e de f f i c i e n t l y s o ，t h ep r e s e n t e d a l g o r i t h mm a yb ec o d e da n da p p l i e dt op r a c t i c a lp r o b l e m sm o r ee a s i l y i na d d i t i o n ，t h e c o n i c a lp a r t i t i o ni su t i l i z e df o rt h ep a r t i t i o no ft h ep r e s e n t e db r a n c ha n db o u n da l g o r i t h m ， a n dap r o c e d u r ef o rt i g h t e n i n gt h eu p p e rb o u n di sd e v e l o p e d o u ra l g o r i t h mh a sl e s sv a r i a b l e sa n dc o n s t r a i n t si nt h ec o m p u t a t i o np r o c e d u r ef o ro b t a i n i n gu p p e rb o u n d s s ow e c a ni m p r o v el a r g e l yt h ec o n v e r g e n c eo ft h ea l g o r i t h m n u m e r i c a le x p e r i m e n t ss h o wt h a t t h ec o m p u t a t i o n a le f f i c e n c yc a nb ei m p r o v e do b v i o u s l yb yu s i n gt h i st e c h n i q u e ，t h a ti s ，t h e n u m b e ro fi t e r a t i o n ，a n dt h ee x e c u t i o nt i m eo ft h ea l g o r i t h mc a nb er e d u c e ds i g n i f i c a n t l y s e c o n d l y , ac o n v e x i f i c a t i o nm e t h o db a s e do nab r a n c ha n db o u n ds c h e m ei sp r e s e n t e d f o rt h 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 gw i t hf r e ev a r i a b l e s b yu t i l i z i n ge q u i v a l e n t t r a n s f o r m a t i o n ，f r e ev a r i a b l e si nt h ep r i m a lp r o b l e ma r ef i r s tt r a n s f o r m e di n t op o s i t i v e i i i v a r i a b l e s ，t h e n ，b yc o n v e x i f i c a t i o ns t r a t e g i e s ，t h er e l a x a t i o nc o n v e xp r o g r a m m i n gp r o b l e m i se s t a b l i s h e d t h ep r o p o s e db r a n c ha n db o u n da l g o r i t h mi sc o n v e r g e n tt ot h eg l o b a l m i n i m u mo ft h ep r i m a lp r o b l e mt h r o u g ht h es u c c e s s i v er e f i n e m e n to ft h er e l a x a t i o nc o n v e x p r o g r a m m i n gp r o b l e ma n dt h es o l u t i o n so fas e r i e so ft h er e l a x a t i o np r o b l e m s a n df i n a l l y ， t h en u m e r i c a le x a m p l e sa r eg i v e nt oi l l u s t r a t et h ef e a s i b i l i t ya n de f f i c i e n c yo ft h ep r o p o s e d a l g o r i t h m c o m p a r e dw i t ho t h e rm e t h o d s ，t h ep r o p o s e dm e t h o dc a nh a n d l es i g n o m i a l t e r m sw i t hm o r ev a r i a b l e s f i n a l l y , ag l o b a lo p t i m i z a t i o na l g o r i t h mi sp r o p o s e df o rs u mo fl i n e a rr a t i o sp r o b l e m o v e rac o n v e xs e t b yu t i l i z i n gt h ee q u i v a l e n tp r o b l e ma n dc o n v e xt e c h n i q u e ，ar e l a x - a t i o nc o n v e xp r o g r a m m i n gp r o b l e mt h e ni so b t a i n e d ，t h r o u g ht h es u c c e s s i v er e f i n e m e n t o ft h ef e a s i b l er e g i o no ft h er e l a x e dc o n v e xp r o g r a m m i n ga n dt h es o l u t i o n so fas e r i e so f t h er e l a x e dc o n v e xp r o g r a m m i n g s ，a n df r o mt h e o r yt h ep r o o fw h i c ht h ep r o p o s e db r a n c h a n fb o u n da l g o r i t h mi sc o n v e r g e n tt ot h eg l o b a lm a x i m u mi sg i v e n f i n a l l y , t h en u m e r - i c a le x a m p l e sa r eg i v e nt oi l l u s t r a t et h ef e a s i b i l i t ya n de f f i c i e n c yo ft h e p r o p o s e da l g o r i t h m k e y w o r d s ：g l o b a lo p t i m i z a t i o n ，b r a n c ha n db o u n d ，s u mo fr a t i o s ，c o n c a v ee n v e l o p e ， g 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 ，s l l mo fl i n e a rr a t i o s i v 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写的研究成果，也不包含为获得河南师范大学或其他教育机构的学位或证书所使用 过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名： 关于论文使用授权的说明 本人完全了解河南师范大学有关保留、使用学位论文的规定，即：有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅本人授权河南师范大 学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文( 保密的学位论文在解密后适用本授权书) 签名： 堇呼圭d 导师签名： 6 3 1 1 全局优化算法概述 第一章绪论 近年来随着科学技术，特别是信息技术的飞速发展，全局优化在经济建模、固定费用、 金融、网络和运输、数据库和芯片设计、图像处理、核能和机械设计、化学工程设计和控 制、分子生物学以及环境工程等众多领域中的应用越来越广泛，使得在科学、经济和工程 中的许多进展都依赖于计算相应优化问题的全局最优解的数值技术，因此全局优化理论和 方法值得深入研究 全局优化研究的是多变量非线性函数在某个约束区域上的全局最优解的特性和构造 寻求全局最优解的计算方法，以及求解方法的理论性质和计算表现由于多个局部最优解 的存在，并且它们不同于问题的全局最优解，人们无法借助于传统的非线性规划技术求解 这些问题，使得全局优化的研究极具挑战性然而，自从2 0 世纪7 0 年代中后期以来，全 局优化在许多方面得到了飞速的发展，许多新的全局优化理论及算法被相继提出并得到广 泛的应用目前全局优化已成为最优化学科领域中一个独立的学科分支，成为人们研究实 际问题时进行建模和分析的重要手段之一 现有的求解全局优化问题的方法依据它们的收敛性分为两大类，即确定性方法和随机 性方法前者充分利用问题的凸性、单调性、等度连续性、l i p s c h i t z 常数、水平集等全 局性的解析性质产生一确定的有限或无限点序列使其收敛于全局最优解，具有较高的计算 效率这类方法依据某一确定性策略搜索局部极小，并试图跳跃已获得的局部极小而达到 某个全局最优点，包括分支定界方法 1 - 6 1 、区间方法 7 - m l 、填充函数法1 1 1 - 1 3 1 、罚函数 法f 1 4 j 、积分一水平集法【1 5 ，16 1 、外逼近方法【、割平面方法【1 】等对于随机性方法，例 如遗传算法【1 7 1 8 1 、随机函数法【1 9 】、模拟退火算法1 2 0 j 等，这类方法不依赖于问题本身陛 质，利用概率机制而非确定的点列来描述迭代过程它对目标函数性质要求低，从而具有 应用广泛、容易实现、稳定性好等突出特点 下面简单概述一些确定性和随机性全局优化方法及其研究进展 1 确定性算法 ( 1 ) 分支定界方法 1 几类特殊非凸规划问题的分支定界算法 分支定界方法是全局优化的主要算法之一，它已被广泛应用在整数规划、非凸规划等 各种困难的优化问题，近年来一直是最优化领域的研究热点，人们一直在寻找求解的新途 径和新方法 分支定界方法所考虑的全局优化问题是 0 ，d i ( x ) 0 c a m b i n i 等【3 6 1 ，f a l k 和p a l o c s a y 3 7 1 ，k o n n o 和k u n o 3 8 1 ，k u n o 39 1 ，r i t t e r 4 0 1 ，s h e n 和 w a n g 4 1 】等许多研究员都研究了问题( p ) 但是，大部分研究都局限于线性的情况，即带 有线性约束的线性比式和问题另外，为全局地求解非线性比式和问题( p ) ，q u e s a d a 和 g r o s s m a n n 4 2 】在分支定界过程中把估计函数应用到包括问题( p ) 的一类问题；d u r 等【4 3 】 把问题转化为一类可通过分支定界技术求解的参数非线性规划；f r e u n d 和j a r r e 对问 题( p ) 提出一内点方法；最近，b e n s o n 4 5 , 4 6 】对问题( p ) 通过利用相应的凸松弛规划问题 提出了两类分支定界方法；y a n g 等【4 7 】把锥分和外逼近应用到d c 比式和问题 本文提出一通过在剖分集上求解一系列凸松弛规划问题得到问题( p ) 的全局最优解 的新的分支定界方法然而，为产生每个子问题的凸松弛规划问题并保证全局最优解的收 敛性，特殊的方案被采用在本方法中， ( i ) 问题( p ) 的等价问题( p ( a o ) ) 被考虑，其中o 是r 2 p 中的锥 ( i i ) 基于问题( p ( a o ) ) 的目标函数在梯形上的凹包络，问题( p ( a o ) ) 的一个新的凸松 5 几类特殊非凸规划问题的分支定界算法 弛规划问题( 尸( o ) ) 被提出由于在( p ( o ) ) 中有n + p 个变量而b e n s o n 在文献 4 5 】中 采用n + 印个变量，且( p ( a o ) ) 中约束的数目比文献【4 5 】中少2 p 个，所以该松弛比文献 4 5 中计算更简便 ( i i i ) 定上界的子问题仅仅是在某些约束的系数和某些变量的界上不同而在算法过程 中规模没有变大的凸规划问题 ( i v ) 虽然分支定界过程主要在印维空间中进行，但分支发生在p 维而不是几或劬 维空间在许多实际应用中，p 远远小于礼，因此该特征可有效的缩短搜索步长 ( v ) 提高求解过程的紧界方法被提出，基于该方法一个新的分支定界方法被提出 本文给出求解问题( p ) 的锥形分支定界方法通过引入变量，将原问题转化为等价 的非凸规划问题然后对等价问题构造分支定界算法，其中利用凹包络构造松弛凸规划问 题，从而将估计上界问题转化为一系列凸规划问题，这些凸规划易于求解而且规模不变， 更容易编程实现和应用到实际问题中；分支采用锥分并且给出一紧缩上界的过程最后， 理论分析和数值实验表明所提出的算法是可行有效的，且数值结果与现有方法相比，迭代 次数和运行时间都有显著改进 在第三章，针对带自由变量的广义几何规划问题给出基于分支定界过程的凸化方法 该问题的数学模型为 ( f g g p ) ：1 毗m i n 嚣组川， iz q 。： z ：z ：z z ，i ： 1 ，n ) ) ， 其中，q ( z ) = ea j t 兀z y “，q 歹t r ，t j z + ，i j t n ，当1 i p 时x i 0 且 t = l i e i j t “冗；当p + 1 i n 时x i r 且“z ( z 为整数集) ，j = 0 ，m 广义几何规划问题( g g p ) 是一类特殊的非凸非线性规划问题，它已广泛应用于产品 计划、任务管理、化学过程设计等实际问题中由于( g g p ) 问题在它的原始和对偶表示 式中均出现非凸项以及存在多个局部极小和可能出现的非凸可行域，使得求解起来十分困 难目前求解( g g p ) 的局部优化方法有多种，如被叫做浓缩的正项式的逐次逼近，称为 伪凸的弱对偶形式，和采用的一般的非线性规划方法【4 8 】，而求解( g g p ) 全局解的方法还 很少文献 4 9 ，5 0 ，5 1 】基于( g g p ) 的指数变换、凸松弛和分支定界提出求解( g g p ) 问题 的一个全局优化方法最近，许多全局优化方法被提出( 如文献【5 2 】，【5 3 】，【5 4 等) 但已有 6 第一章绪论 方法大多只适用于处理带有严格正变量的( g g p ) 问题虽然正变量被不断地用来表示工 程和科学系统，但我们在管理问题和系统行为中常常用到非正变量，例如，投资决策、压 力、温度、电流、速率和加速度等因此研究带有自由变量的广义几何规划问题( f g g p ) 非常重要文献 5 5 】基于凸松弛给出了符号项中最多含三个变量的( f g g p ) 问题的全局 优化算法 本文提出一全局优化算法首先利用等价转换把( f g g p ) 中的自由变量转化为正变 量，再通过凸化方案，建立了松弛凸规划问题( r c p ) 该方法比 5 5 中可处理含有更多变 量的符号项数值计算表明提出的方法是可行和有效的 在第四章，针对凸约束域上线性比式和问题给出一新的分支定界方法考虑如下线性 比式和问题： ( p ) ：m a xf ( x ) = 。籍 其中p 2 ，x 是形中的非空紧凸集，d j 舻，伤r ，j = 1 ，2 ，p ，且对 比x ，有n t x + a j 0 ，霹z + 伤 0 ，j = 1 ，2 ，p 问题( p ) 能广泛应用于经济、交通等领域，其模型还包括其它的比式和优化问题，如 文献 5 6 】给出了如何把一类凹比凸比式和问题转化为问题( p ) 的方法虽然问题( p ) 的 目标函数中每一个比式都是线性的，但它们有限个的和不一定是拟凸或拟凹的，所以问题 ( p ) 可能存在多个不是全局最优的局部解，使得求解十分困难目前，求解线性比式和问 题的方法有多种( 如文献【5 7 ， 5 8 】， 5 9 】) 本文给出了一个在凸约束域上求解问题( p ) 的新的分支定界方法首先把问题( p ) 转 化为等价问题( q ) ，然后利用凸化技术建立问题( q ) 的松弛凸规划( r c p ) ，通过对( r c p ) 可行域的细分以及一系列( r c p ) 的求解过程，从理论上证明了算法收敛到问题( p ) 的全 局最优解应用本文方法进行计算，结果表明该方法是可行有效的 7 几类特殊非凸规划问题的分支定界算法 1 3 基本理论和知识 最优化问题的一般形式为： f l m i n f ( x ) ( p ) ： s t g i ( x ) 0 ，i = 1 ，m ， l i( z ) = 0 ，j = 1 ，z ， 其中，函数f ：r n _ r 称为目标函数，d = z r n ig i ( x ) 0 ，i = 1 ，m ；h j ( x ) = 0 ，j = 1 ，f ) 称为可行域，d 中的任意点称为可行点；b ( z ) = o ( j = 1 ，2 ) 称为等式约束；g i ( x ) o ( i = 1 ，m ) 称为不等式约束 若d = r 佗，即z 是自由变量，则称问题( p ) 为无约束优化问题；否则，dc 黔，称 问题( p ) 为约束优化问题 定义1 3 1 点x + d 称为一个局部极小点，如果存在某个e 0 ，对于所有满足 忙一z 。l i e 的z d ，有f ( x 4 ) ，( z ) ，而f ( x + ) 称为局部极小值 定义1 3 2 点z + d 称为一个全局最小点，如果对于所有x d ，有f ( x + ) ，( z ) ， 而f ( x + ) 称为全局最小值 由函数在紧集上的连续性，我们可以得到下面著名的魏尔斯特拉斯定理： 定理1 3 1 ( w e i e r s t r a s s 定理) 【1 】若d 酞n 是一非空紧集，( z ) 是d 上的连续 函数，则f ( x ) 在d 上至少有一个全局最小( 最大) 点 若函数在z 点处既下半连续，又上半连续，则它在z 点处连续在定理1 3 1 中如果 将，的连续性替换成下半连续性( 上半连续性) ，那么定理仍然成立 定理1 3 2 f 1 】舻的一个集合是凸的，当且仅当它包含它的元素的所有凸组合 定义1 3 3 函数f ：d _ r ，其中d 是册中一个凸集，称为凸的，如果对于任 意z l ，x 2 d 和0 入1 ，有 f ( a x l + ( 1 一a ) x 2 ) a f ( x 1 ) + ( 1 一a ) f ( x a ) 定理1 3 3 【1 】紧的凸集d r n 上的凹函数f ：d _ r 可以在d 的某个极点取到 它的全局最小值 从实践和理论两个方面来看，函数逼近是数学规划中的一个基本问题，在非凸优化 中，函数的凸包络是一个重要的逼近工具 8 第一章绪论 定义1 3 4 假设d 是r ”中一个非空紧凸集，f 是定义在d 上的一个实值函数 则f ( z ) 在d 上的凸包络是指满足如下性质的函数f ( z ) ： ( 1 ) f ( x ) 在d 上是凸的 ( 2 ) 对于所有z d ，f ( z ) 厂( z ) ( 3 ) 若h ( x ) 是任意一个定义在d 上的凸函数，并且对于所有的z d ，有h ( x ) 厂( z ) ， 则对于所有的z d ，有 ( z ) f ( z ) 根据上述定义，函数的凸包络实际上是该函数在d 上最佳一致的凸下方估计每个 具有凸可行域的非凸优化问题，都相伴着一个具有相同最优值的凸规划问题然而，在通 常情况下，找到一个函数的凸包络同计算它的全局最小点一样困难但是对于某些特殊情 况，其中凸包络可以用给定的函数和凸集明确描述出来 定义1 3 5 满足最+ 1cr 的一个n 维多胞形无穷序列rc 酞n 称为穷举的，是 指存在一个点8 ，使得 o o 。l i mr = f1p k = s ) 5 一“ 五：i 定义1 3 6 令pc 舻是一个满足i n t p 仍的多面体，是一个有限指标集满 足i n t 只d ( i i ) 的p 的一组子多面体 只：i ) 称为p 的一个( 多面体) 剖分，是 指p = u 只，并且对于所有的i ，j i ，i j ，i n t 只ni n t 弓= 仍 9 第二章非线性比式和问题的锥形分支定界方法 2 1引言 目前分式规划是非线性优化领域中发展成熟的学科之一凸集上函数多个比值和的优 化问题是一类特殊的分式规划问题近3 0 多年来它引起研究员的广泛关注在过去十年 中，对这些问题的研究兴趣特别强这一方面是因为源于工程、经济、管理和其它学科的 许多问题都可写为比式和问题【3 2 】，例如，运输问题【3 3 】，铺序生产问题【3 4 】，政券问题【3 5 】，等 等另一方面是因为，这类问题对研究员在理论和计算方面具有极大的挑战性即使在线 性比式这种最简单的情况下，虽然每一项既是拟凸又是拟凹的，但它们的和一般来说既非 拟凸又非拟凹的因此，问题具有多个不是全局最优的局部最优解 本文针对凸集上p 个比值和的优化问题提出一有效和可信赖的全局优化算法，问题 如下： ( p ) 口= m a x ( z ) = p 瑞 ，、 1 2 1 s t z x 其中p 2 ，对每个i = 1 ，2 ，p ，：即_ 兄是有限凹函数，d i ：r n r 是有限凸函 数，且x 是一紧凸集( 可能是空集) 假定对每个i = 1 ，2 ，p ，n x ) 和d i ( x ) 在x 上满 足：n i ( z ) 0 ，d i ( x ) 0 c a m b i n i 等【3 6 】，f a l k 和p a l o c s a y 3 t l ，k o n n o 和k u n o a s l ，k u n o 3 9 l ，r i t t e r 4 叫，s h e n 和 w a n g 4 1 】等许多研究员都对问题( p ) 进行了研究但是，大部分研究都只局限于线性比式 的情况，即带有线性约束的线性比式和问题另外，为全局地求解非线性比式和问题( p ) ，q u e s a d a 和g r o s s m a n n 4 2 】在分支定界过程中把估计函数应用到包括问题( p ) 的一类 问题；d u r 等【4 3 】把问题转化为一类可通过分支定界技术求解的参数非线性规划问题； f r e u n d 和j a r r e 4 4 】对问题( p ) 提出一内点方法；最近，b e n s o n 4 5 , 4 6 】对问题( p ) 分别通 过利用相应的凸松弛规划问题提出了两类分支定界方法；y a n g 等【4 7 l 把锥分和外逼近应 用到d c 比式和问题 本文提出一通过在剖分集上求解一系列凸松弛规划问题得到问题( p ) 的全局最优解 的新的分支定界方法然而，为产生每个子问题的凸松弛规划问题并保证全局最优解的收 1 1 几类特殊非凸规划问题的分支定界算法 敛性，特殊的方案被采用在本方法中， ( i ) 问题( p ) 的等价问题( p ( a o ) ) 被考虑，其中o 是r 2 p 中的锥 ( i i ) 基于问题( p ( a o ) ) 的目标函数在梯形上的凹包络，问题( p ( a o ) ) 的一个新的凸松 弛规划问题( p ( z a o ) ) 被给出由于在问题( p ( a o ) ) 中有n + p 个变量而b e n s o n 在文献 4 5 】中采用t t + 3 p 个变量，且问题( p ( o ) ) 中约束的数目比文献 4 5 】中少2 p 个，所以该 松弛比文献 4 5 中方法计算效果更有效 ( i i i ) 定上界的子问题仅仅是在某些约束的系数和某些变量的界上不同而在算法过程 中规模没有变大的凸规划问题 ( i v ) 虽然分支定界过程主要在助维空间中进行，但分支过程发生在p 维而不是n 维 或2 p 维空间由于在许多实际应用中，p 远远小于n ，所以该特征可有效的缩短搜索步 长 ( v ) 我们给出了提高求解过程的一个紧界方案，基于该方案一个新的基于分支定界过 程的凸化方法被提出 2 2 等价问题 为全局地求解问题( p ) ，我们把它转化为等价的非凸规划问题( p ( a o ) ) 为此，包含x 的单纯形s 可通过求解n + 1 个凸规划问题构造如下1 1 1 ： 其中 s 的顶点集是 其中 s = z r n i x r ，r = 1 ， y s = 昭，昭，培) ， 昭= ( 7 1 ，一，) ，w = ( ，y 1 一，一1 ，a ，+ 1 1 一，) 且o l ，= 7 一竹，r = 1 ，n 因此利用单纯形s 并求解一系列凸规划问题，对每个 f r 1 2 、，7 0 ， o u , o = 羔黼 0 为方便，引入变量t = ( t l ，t p ) r p 和8 = ( 8 1 ，8 p ) r p 并对每个i 定义 q ，f ia n da o ， q = ( 亡，8 ) r 2 p l 屯= 礼i ( z ) ，8 i = d i ( x ) ，i = 1 ，2 ，p ，z x ) ， f t = ( ( 如，8 i ) r 2 i 如t i + 8 i u t ) ， a o = ( 如，s t ) r 2 il o s i t i u , o s t ) 令 f = r 1 l ， 0 = a 2x x a o 则问题( p ) 可转化为如下等价的非凸规划问题( p ( a o ) ) ： iv ( a o ) = ( p ( a o ) ) 7 p m a x 荟基 s t ( t ，8 ) qn fna o 定理2 2 1 如果( x + ，t + ，8 ) 是问题( p ( a o ) ) 的一个全局最优解，那么t ；= n i ( x + ) ，8 i = d i ( x + ) ，i = 1 ，2 ，p ，且x + 是问题( p ) 的一个全局最优解反之，如果z 4 是问题( p ) 的一 个全局最优解，那么( z + ，t + ，s + ) 时问题( p ( a o ) ) 的一个全局最优解，其中t ；= n i ( x + ) ，s ；= d i ( x + ) ，i = 1 ，2 ，p 证明定理的证明可直接由问题( p ) 和问题( p ( a o ) ) 的定义得到，故省略 口 由定理2 2 1 ，求解问题( p ) 就转化为求解它的等价问题( p ( a o ) ) 显然，在实际生活中，当采用该算法求解问题( p ( a o ) ) 时寻找紧的初始的界如，u t ，凹 和四是非常重要的为得到更紧的和可行的界，在某些情况下，我们采取一些措施例如， 1 3 在线性比式和的情况下，我们假定在问题( p ) 中对每个i = 1 ，2 ，p ，n i ( x ) = n t x + 凡? 和吨( z ) = 露z + d ? 且x = z r 扎i a z 6 ) 首先，给出如下线性规划： ( p l ) n t y 4 - n o z m l n - - i - n t z s t a y 一6 z 0 ， 毋秒+ 田z = 1 若假定z 。是问题m i n 趔d i ( x ) l a x 6 ) 的可行解，即a x 。b ，且令 显然， 且 x o 。，0 y o 。d ix o + z 5 a 可。一b z o = 避可o - 4 - 武= d ix o + 田 a x o b d t x o - 4 - 田 d i f f x o + 田 d l i f ix - 4 - 田 粕删z 。= 糍善0 = = 1 l t i ( x o ) d i ( x o ) m i n 糕鲥捌n ( p m ， 其中m i n ( p l ) 表示问题( p l ) 的最优值 因此对每个i = 1 ，2 ，p 都可得到较好的下界口 相似地，我们构造下面的线性规划来得到较好的上界四： ( p u ) m a xn t y + n o z s t a y b z 0 ， 巧妙+ 田z = 1 假定z o 是问题m a x 糍i a z 6 ) 的可行解且令 1 4 y o = 5 x o 截x o + 掣 ，0 一 毋如+ 田 第二章非线性比式和问题的锥形分支定界方法 类似地， ( 珈，z 。) 是( p u ) 的可行解且嘎t 蜘+ 几? z 。= 磊碧因此 m a x 端恤 0 ， 0 四= m a x n 秒+ n o z l a y b z 0 ，西可+ 田z = 1 ) 0 2 3 凸松弛规划问题 求解问题( p ( a o ) ) 的主要过程是为得到问题( p ( a o ) ) 的上界而对问题( p ( a o ) ) 和它 的子问题的凸松弛规划问题的构造该凸松弛规划问题可通过问题( p ( a o ) ) 的目标函数 在相对应的梯形上的凹包络得到 2 3 1 构造凹包络 为构造凸松弛规划问题，给出如下的凹包络的定义 定义2 3 1 【1 】令m r g 是一紧凸集，并令，：m _ r 在m 上上半连续那么， 当以下条件满足时 ( i ) ，m ( z ) 是m 上的凹函数， ( i i ) 对所有z m ，m ( z ) ，( z ) ， ( i i i ) 不存在满足( i ) 和( i i ) 且对某个牙m 有u ( 2 ) i m ( 牙) 的函数u ( z ) 则称 ，m ：m _ 兄是函数t 厂在集合m 上的凹包络 由凹包络的定义可得到下面的定理 定理2 3 1 考虑梯形m = ( z 1 ，z 2 ) r 2 i f z 1 + x 2 “，l x 2 x l u x 2 ，其中 0 2 u ，0 l u 对任意的( z 1 ，x 2 ) r 2 ( x 2 o ) ，定义函数，( z l ，x 2 ) = 爨，则函数 f ( x 1 ，z 2 ) 在m 上的凹包络厂m ( x 1 ，x 2 ) 为 轧蚴= m i n 罕一半半x 2 + l , 等一半计吣 1 5 几类特殊非凸规划问题的分支定界算法 并记 证明对每个( x l ，x 2 ) m ，令 g l ( z 1 ，x 2 ) 9 2 ( z l ，x 2 ) 旦产z 1 一丛与业z 2 + l ， 等z ，一蹬半z z + 矿 ，m ( z l ，z 2 ) = m i n 9 1 ( z 1 ，z 2 ) ，9 2 ( z 1 ，x 2 ) ) 由函数9 l ( x l ，x 2 ) 和9 2 ( x 1 ，z 2 ) 在凸集m 上是线性函数，可以推出函数厂膨在集合m 上 是凹函数 对每个( x l ，x 2 ) m ，由0 l x 2 z 1su x 2 ，0 0 ，得 同理可证 故有， g l ( x l ，x 2 ) 9 2 ( z l ，x 2 ) f ( x l ，z 2 ) ，( z 1 ，z 2 ) ， ，m ( z 1 ，z 2 ) ( x l ，z 2 ) ，v ( x 1 ，z 2 ) m 现在假设函数w ( x l ，x 2 ) 是满足对v ( x ，x 2 ) m 都有w ( x l ，x 2 ) f ( x l ，x 2 ) 且对某个 ( 牙1 ，牙2 ) m 有 1 6 u ( 孟1 ，互2 ) m i n g l ( ：z 1 ，牙2 ) ，9 2 ( 牙1 ，牙2 ) 】 我们知道m 的四个顶点分别为 a = ( 而lu ，而1 钆) ，b = ( 丽u u ， u + 1 u ) ， 第二章非线性比式和问题的锥形分支定界方法 c = ( u + l而1f ) d _ ( 南l 雨1 f ) 则由( 牙l ，牙2 ) m ，有点( 牙1 ，牙2 ) 属于 a ，b ，c ) 的凸包或 a ，c ，d ) 的凸包或同时属于上 述两个凸包下面我们利用反证法证明点( 牙1 ，牙2 ) 属于 a ，b ，c ) 组成的凸包对于( 牙1 ，牙2 ) 属于 a ，ed ) 的凸包的证明可类似得到假设点( 牙。，牙2 ) 属于 a ，b ，c ) 组成的凸包 我们选取和为1 的三个非负实数0