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

i 摘要 幽i ii i r l l l lr f l f l l l l l r li l l l l uiflf r r l l l e , , j | l l unip | ii ii l i y 17 3 4 4 8 8 全局优化问题已广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领 域分支定界算法是全局优化主要算法之一，近年来一直是最优化领域的研究热点，人们 也一直在不断改进这一算法本文在原有理论的基础上，针对几类特殊的非凸规划问题， 分别给出求其全局最优解的分支定界算法主要内容如下： 首先，简要介绍几种常见的全局优化算法，及本文所研究问题的研究现状、主要结论 及一些基本概念和性质 第二章，针对一类带有多个反凸约束的特殊的反凸规划问题，通过引入变量，将原问 题等价地转化为线性规划问题然后对等价问题构造分支定界算法，分支采用矩形分割不 但保证其穷举性，而且使得线性规划规模减小通过把可行域逐渐剖分加细，利用区域删 除准则删掉不存在最优解的一大部分区域，加快了算法效率理论分析和数值实验表明 所提出的算法是可行有效的，且数值结果与现有方法相比，表明提出的算法是可行和有效 的 第三章，我们考虑广义凹多乘子函数在紧凸集上的解，这类问题包含多种变形：如广 义规划，双层线性规划，线性0 - 1 规划等对这类问题，我们给出一个统一有效的算法， 在算法中，通过分支定界搜索全局求解一个等价的极小化问题，其主要工作中包含求解一 系列仅目标函数系数不同的凸规划问题因此，为了有效求解这些凸规划问题，一个问题 的最优解可能可以被用作下个问题的一个好的初始解最后给出算法的收敛性和计算注意 事项，以及几个例子的求解 关键词：全局优化，反凸规划，单调最优化，分支定界，多乘积规划 i i a b s t r a c t t h eg l o b a lo p t i m i z a t i o np 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 e b r a n c ha n db o u n da l g o r i t h mi so n eo ft h em a i ng l o b a lo p t i n i z a t i o nm e t h o d s ，a n di th a s b e e nah o tt 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 h a n db o u n da 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 g s e v e r a lc l a s s e 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 ，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 s f o l l o w s ： a tt h ef i r s t ，s e v e r a lm a i ng l o b a lo p t i m i z a t i o na p p r o a c h e sa n dt h el a t e s tr e s e a r c hd e - v e l o p m e n to fp r o b l e m ss t u d i e di nt h i sp a p e ra r es i m p l yp r e s e n t e d ，a n ds o m eb a s i ct h e o r i e s a n dm a i np r o p e r t i e sa r ei n t r o d u c e d i nc h a p t e r2 ，f o ras p e c i a lr e v e r s ec o n v e xp r o g r a m m i n gp r o b l e m sw i t hm o r et h a no n e r e v e r s ec o n v e xc o n s t r a i n t s t h ep r i m a lp r o b l e mi sr e f o r m u l a t e di n t oal i n e a rp r o g r a m m i n g p 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 ，ab 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 d f o rs o l v i n gt h el i n e a rp r o g r a m m i n gp r o b l e m i na d d i t i o n ，t h er e c t a n g l eb i s e c t i o ni su t i l i z e d f 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 d a l g o r i t h m s p e c i a l l y , t h er e g i o nd e l e t i n g p r i n c i p l e 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 ht h eo p t i m a ls o l u t i o nd o e s n 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 t h ea n a l y s i st h e o r y a n dn u m e r i c a le x p e r i m e n ta r er e p o r t e do nt 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 i i i i nc h a p t e r3 ，w ec o n s i d e rt h es o l u t i o no ft h ep r o b l e mo fm a x i m i z i n gag e n e r a l i z e d c o n c a v em u l t i p l i c a t i v ef u n c t i o no v e rac o m p a c tc o n v e xs e t w h i c hc o n t a i n sv a r i o u sv a r i - a n t ss u c ha s ：g e n e r a lq u a d r a t i cp r o g r a m m i n g ，b i l i n e a rp r o g r a m m i n g ，a n dl i n e a rz e r o - o n e p r o g r a m m i n ge t c f o rs u c hp r o b l e m s ，w ep r e s e n ta ne f f i c i e n tu n i f i e da l g o r i t h m i nt h e a l g o r i t h m ，a ne q u i v a l e n tm i n i m i z a t i o np r o b l e mi sg l o b a l l ys o l v e dv i aa b r a n c h a n d - b o u n d s e a r c h t h em a i nw o r ko ft h ea l g o r i t h mi n v o l v e ss o l v i n gas e q u e n c eo fc o n v e xp r o g r a m - m i n gp r o b l e m st h a td i f f e ro n l yi nt h e i ro b j e c t i v ef u n c t i o nc o e f f i c i e n t s t h e r e f o r e ，t os o l v e e f f i c i e n t l yt h e s ec o n v e xp r o g r a m m i n gp r o b l e m s ，a no p t i m a ls o l u t i o nt oo n ep r o b l e m c a n p o t e n t i a l l yb eu s e dt og o o da d v a n t a g ea sas t a r t i n gs o l u t i o n t ot h en e x tp r o b l e m a t l a s t ，c o n v e r g e n c eo ft h ea l g o r i t h mi ss h o w n ，a n dc o m p u t a t i o n a lc o n s i d e r a t i o n s a r eg i v e n s e v e r a ls a m p l ee x a m p l e sa r ea l s os o l v e 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 ，r e v e r s ec 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 ，b r a n c ha n db o u n d ，m u l t i p l i c a t i v ep r o g r a m m i n g i v 摘要 a b s t r a c t 第一章 1 1 1 2 1 3 目录 i i i i 绪论 1 全局优化算法概述1 基本理论和知识 5 本文所研究问题的背景和现状7 第二章 特殊反凸规划问题的分支定界方法 2 1 引言 2 2 等价问题。 2 3 线性松弛过程 2 4 算法过程 2 5 算法及收敛性 2 5 1 算法陈述 2 5 2 收敛性分析 2 , 6 数值结果 第三章 3 1 3 2 3 3 广义凹多乘积规划问题的全局优化3 1 引言3 1 等价转化 3 2 算法过程，3 3 v l 1 2 5 8 4 4 5 6 1 1 l 1 1 2 2 2 2 3 4 算法的收敛性 4 0 3 5 数值实验 4 4 结论 参考文献 致谢 攻读学位期间发表的学术论文目录 独创性声明 v i 7 9 5 7 9 4 4 5 5 5 1 1 全局优化算法概述 第一章绪论 全局优化问题常见于经济建模，固定费用，金融，网络和运输，数据库和芯片设计， 图像处理，核能和机械制造，化学工程设计和控制，分子生物学及环境工程等由于多个 局部最优解的存在，且它们不同于问题的全局最优解，所以人们无法借助于传统的非线性 规划技术求解这些问题然而，2 0 世纪7 0 年代中后期以来，在科学、经济和工程中的许 多进展都依赖于计算相应优化问题全局最优解的数值技术，使得全局优化得到了飞速的发 展，许多新的理论及算法被相继提出并在实际中得到应用，全局优化已发展成为最优化领 域中一个独立的学科分支，成为人们研究实际问题时进行建模和分析的重要手段之一全 局优化理论和方法在诸多领域发挥着越来越重要的作用，因此值得我们深入研究 常见的优化模型有如下几类：线性规划、二次规划、整数规划、几何规划、多目标规 划，此外，还有动态规划、不可微规划、参数规划和随机规划等现有的求解全局优化问 题的方法依据它们的收敛性分为两大类：确定性方法和随机性方法确定性方法如：区间 方法、分支定界方法、填充函数方法、罚函数方法、外逼近( 内逼近) 方法、对偶方法等 等；随机性方法如：遗传算法、模拟退火算法、随机搜索方法、随机函数方法等等前者 充分利用问题的凸性、单调性、等度连续性、l i p s c h i t z 常数、水平集等全局性的解析性 质产生一确定的有限或无限点序列使其收敛于全局最优解，具有较高的计算效率这类方 法依据某一确定性策略搜索局部极小，并试图跳跃已获得的局部极小而达到某个全局最 优点，包括分支定界方法 1 3 】、区间方法 4 】、填充函数法【5 7 】、积分一水平集法 8 9 】、罚函数法【1 0 】、外逼近方法 1 】、割平面方法 1 】等对于随机性方法，例如遗传 算法 1 1 1 2 】、随机函数法【1 3 】、模拟退火算法【1 4 等，这类方法不依赖于问题本身性 质，利用可能性机制而非确定的点列来描述迭代过程它对目标函数性质要求低，从而具 有应用广泛、容易实现、稳定性好等突出特点 下面分别简述几种确定性和随机性全局优化方法及其研究现状 1 特殊非凸规划问题的全局最优化方法 1 确定性算法 ( 1 ) 区间方法 区间方法考虑的问题是 m i ，n ，y ( x ) x e x 其中x 是扎维区间，：舻_ r 在x 上连续区问方法的基本思想是在区间分析的 基础上，由区间算术运算规则用区间变量代替点变量进行区间计算，并将分支定界方法 和m o o r e - s k e l b o e 算法 1 5 相结合突出优点是能在给定精度内求出问题的全部全局极小 点它的一般过程可概括为定界、分枝、终止、删除和分裂五个基本步骤其中包括区间 分裂规则、删除规则及区间选择规则，不同的区间算法在于分裂规则、删除规则和区间选 择规则的不同处理手段上 下面针对不同的规则给出最近几年区间算法的研究发展现状 m o o r e 等首次提出区间全局优化这一概念c s e n d e s 和r a t z 1 6 】在1 9 7 7 年研究了四 种分裂方向的选取规则近年来c a s a i o 、m a r k o t 1 7 1 9 】等提出一个新的多分裂技术 对整个区间算法的执行效率起重要作用的加速工具有c u t o f f 测试、单调性测试凸性测 试和区间n e w t o n 方法等申培萍和张可村【2 0 】分别对一维的可微函数和n 维的非光滑 函数研究了相应的区间剪枝技术r a t z 2 1 在1 9 9 9 年利用区间斜率对一维光滑函数提出 一个区间删除技术m o o r e - s k e l b o e 算法给出了一般的区间选择规则最近c a s a d o 等提 出一新的启发式选取规则 ( 2 ) 分支定界法 分支定界方法考虑的问题是： m i ，n ，y ( x ) x e x 其中xcr n ，x 为紧集，函数，：p _ r 在x 上连续分支定界方法是一种较为常见 的全局优化方法，被广泛的应用在整数规划、非线性规划等优化模型中，近年来一直是最 优化领域的研究热点基本思想是通过把可行域逐渐剖分加细，同时相应的构造出目标函 数值单调减小的上界序列和单调增加的下界序列，当上界和下界相等或者上界与下界的差 2 第一章绪论 满足误差要求时，迭代终止，得到全局最优解；否则迭代继续进行下去分支定界算法实 现的主要步骤包括分支、定界和剪支三个基本操作，三个基本操作的处理手段不同可以得 到不同的分支定界方法 分支操作一般采用矩形分支、单纯形分支和锥形分支矩形分支过程比较简单，容易 实现，但如果算法需要用到其顶点，则不宜采用矩形分支，因为n 维空间中具有非空内部 的矩形有2 礼个顶点，会使问题规模急剧增大，这种情况下采用单纯形分支可控制问题规 模，提高计算效率；在采用矩形分支和单纯形分支时，可能使得某些细分产生的小区域和 问题可行域没有交集，锥形分支可以避免这种情况，但采用锥形分支生成的序列套一般收 敛到射线而不是某个点，从而会造成求解子问题时数值不稳定 定界操作包括定下界和定上界，其中最关键的是定下界，能否构造出单调增加的最优 值下界序列是决定算法成功与否的关键定下界的基本原则是把求下界问题转化为尽可能 简单的易于求解的问题，如线性规划或凸规划问题，具体方法包括对原问题目标函数或可 行域进行线性松弛或凸松弛、求解对偶问题等上界一般是通过可行点处的目标函数值确 定的，最小的目标函数值可以作为最优值一个上界，可行点一般在算法执行过程中被发现 或者通过局部极小化方法得到 剪支主要是删除分支产生的不可能包含最优解的那些小区域，比如在小区域上的下界 大于所发现的最好上界或小区域和问题可行域没有交集剪支可以提高算法效率 分支定界算法的一般步骤为 1 】： 步0 ( 初始化) 选择可行域x 的初始松弛集合d ) x ；初始可行点集合q = d ；上界u b = + o o 令 p = d ) ，计算下界l b ( d ) m i n f ( x ) ，z d ，并令l b = l b ( d ) 在计算l b ( d ) 的 过程中，若有必要，则更新q 和u b 步1( 分割) 将d 分割成有限个子集d i ，i i 满足d = u 吲d i ，i n t d in i n t d j = d ，v i ，j i ，i j ，令p = ( p d ) u u 洲d d 步2 ( 剪枝) 3 特殊非凸规划问题的全局最优化方法 对每个i i ，计算，在子集皿上的下界l b ( d i ) ，使其满足l b ( d i ) i n f f ( d i n d ) 利用在计算l b ( d 。) 的过程中所发现的所有可行点修正集合q ，删除p 中所有不包含最 优解的d ；或玩的一部分，剩余集合不妨记为p 若p = 0 ，置l b = u b ，否则继续 步3 ( 定界) 令l b = m i n l b ( d t ) d l p ，u b = m i n f ( x ) l x q ) 步4 ( 算法终止判断) 若u b = l b ，则终止算法，否则从尸中挑选合适的子集d ，d p ，转入步1 最近，l i n d e r o t h 2 2 1 提出求解非凸二次约束的二次规划问题的分支定界方法该算 法的创新点在于分支是通过剖分可行域为二维的三角形或矩形的笛卡尔积，在该三角形或 矩形上的隐式松弛形式被推出并应用b c n s o n 2 3 】提出单纯形分支定界对偶界算法来求 解线性比式和问题 s h c n 和y u a n 2 4 1 对在多项式约束下的多项式分式函数和的优化问 题也提出一种分支定界方法，等等 在下面第二和第三章中，我们给出两类特殊的优化问题，利用目标函数和约束函数的 特征，讨论了相应分支定界算法的构造及实现过程 ( 3 ) 填充函数法 填充函数法考虑的问题是 m i ny ( x ) z 舻 填充函数法由r c e 2 5 2 6 1 最先提出，他在构造了求解上式问题的填充函数算法这类 方法包括极小化和填充两个阶段，关键是如何构造出更好的填充函数，其基本思想是：首 先利用局部极小点的方法求得f ( x ) 在可行域中的一个极小点z ；，然后构造填充函数，设 法找y ( x ) 的另一个比z i 低的局部极小点z ；，即z ；x ；且满足厂( z ；) 0 ，对于所有满足 忪一z + l i e 的z d ，有f ( x + ) ，( z ) ，相应的f ( x + ) 称为局部极小值 定义1 2 2 点矿d 称为一个全局最小点，如果对于所有z d ，有f ( x + ) ，( z ) ， 相应的f ( x + ) 称为全局最小值 由函数在紧集上的连续性，我们可以得到下面著名的魏尔斯特拉斯定理： 定理1 2 1 ( w e i e r s t r a s s 定理) 1 若d 融是一非空紧集，f ( x ) 是d 上的连续 函数，则f ( x ) 在d 上至少有一个全局最小( 最大) 点 若函数在z 点处既下半连续，又上半连续，则它在z 点处连续在定理1 3 1 中如果 将，的连续性替换成下半连续性( 上半连续性) ，那么定理仍然成立 定义1 2 3 函数f ：d _ r ，其中d 是r “中一个凸集，称为凸的，如果对于任 意：z 1 ，z 2 d 和0 入1 ，有 f ( a x l + ( 1 一a ) z 2 ) a f ( x 1 ) + ( 1 一a ) 厂( z 2 ) 定理1 2 2 f 1 】印的一个集合是凸的，当且仅当它包含它的元素的所有凸组合 定理1 2 3 “1 】紧的凸集d r ”上的凹函数f ：d r 可以在d 的某个极点取 到它的全局最小值 定理1 2 4 “2 】 设d p 为非空凸集， ，是定义在d 上的凸函数，则对任一点 牙i n t d ，都存在r “，使得f ( x ) ，( 牙) + t ( z 一牙) ，比d ，即f 是，在点牙处的 次梯度 这个定理给出了凸函数的一种下方估计 定理1 2 5 【3 】3设d 鼢为非空凸集，厂是定义在d 上的凸函数，且f ( x ) 0 ，比d ，则，2 ( z ) 也是d 上的凸函数 从实践和理论两个方面来看，函数逼近是数学规划中的一个基本问题，在非凸优化 中，函数的凸包络是一个重要的逼近工具 6 第一章绪论 定义1 2 4 设f ：d _ r 是下半连续函数，其中d 是r “中非空凸集则f ( x ) 在s 上的凸包络是指满足如下性质的函数f ( z ) ： ( 1 ) f ( z ) 在d 上是凸的 ( 2 ) 对于所有z d ，f ( x ) ，( z ) ( 3 ) 若h ( x ) 是任意一个定义在d 上的凸函数，并且对于所有的z d ，有h ( x ) ，( z ) ， 则对于所有的x d ，有h ( x ) f ) 根据这个定义，函数的凸包络实际上是该函数在d 上最佳一致的凸下方估计每个 具有凸可行域的非凸优化问题，都相伴着一个具有相同最优值的凸规划问题然而，在通 常情况下，找到一个函数的凸包络同计算它的全局最小点一样困难但是对于某些特殊情 况，其中凸包络可以用给定的函数和凸集明确描述出来 定理1 2 6 3 令d 是由顶点，口1 ，生成的一个单纯形，f ( x ) 是定义在 d 上的凹函数则f ( x ) 在d 上的凸包络是仿射函数2 ( z ) = c r x + b ，它是由线性方程组 f ( v i ) = ，忱+ b ( i = 0 ，1 ，礼) 惟一确定的 定义1 2 5 满足p k + lcp k 的一个n 维多胞形无穷序列rc 瞅称为穷举的，是 指存在一个点8 ，使得 熙r = n r = ” 七= 1 定义1 2 6 函数f ：r 咖_ 乏称为单调递增的，如果对于所有的x 7 ，z 碾加且满 足z z ，即x ：x i ，v i = 1 ，? 2 0 ，都有f ( x 7 ) f ( x ) 成立如果一个函数可以分解为 两个单调递增的函数之差，那么我们称这个函数为d m 函数 1 3 本文所研究问题的背景和现状 在生产生活中的很多问题都可归结为优化问题，而很多典型的优化问题，例如：反凸 规划、二次规划，比式和规划、几何规划、d c 规划、混合整数规划等等，都有了一些求 解算法本文将在近些年新发展的优化理论基础上，针对两类全局优化问题，提出了全局 求解它们的有效算法 7 特殊非凸规划问题的全局最优化方法 在第二章中，考虑如下非凸规划问题： ， l m i nf o ( ) l ( p o ) 2 & l f r o ( y ) 1 ，m = 1 ，印， lf m ( 可) 21 ，仇= p + 1 ，：m ， ly q o = 拶10 0 ，i = 1 ，2 ，p 多乘积规划是非线性优化中的一类常见问题，在实际生产生活中有广泛的应用，如在 微观经济、统计学、金融优化、工程设计等方面都会遇到多乘积规划问题，因此不少学者 开始深入研究这一问题，并提出了一些有效的算法尽管对于特殊形式的问题( g c m p ) 最 优化方法是普遍适用的，但对于本文将要考虑的基于一般形式的( g c m p ) 的全局优化方 8 第一章绪论 法还很少因为这种问题是全局优化问题，具有有许多不是全局最优的局部最优解，所以 求解起来比较困难在本文中我们拟提出一种分支定界算法，首先，在一个比问题的决策 变量的空间维数低的空问使用分支定界过程其次，实现算法所求解的所有子问题都是凸 规划问题，这保证具有一个最优解然后为了加快求解这些凸规划的速度，一个问题的最 优解可以用作下一问题的初始解数值实验表明，对于常见的线性规划，计算结果无论从 计算量还是精度上都有了改进证实所给的算法具有可行性和适用性我们希望这个算法 能够对于全局求解广义凹乘积规划问题提供一个有力的工具 9 特殊非凸规划问题的全局最优化方法 1 0 2 1 引言 第二章特殊反凸规划问题的分支定界方法 本章我们考虑形如下列形式的规划问题； l m i n f o ( y ) ( p 0 ) & l 蹦们g m 叫，印， if m ( y ) 1 ，m = p + 1 ，m ， iy q o = ( y0 鲥y i 聍 o o ，鲥聍，i = 1 ，n o ) ， 其中e ，( ) ：塞。最扩“，m ：0 ，1 ，m ，且如。是正实常系数， 叩m “是任意实常 = 1t = 1 指数一般的称b 。( 可) 为多项式很显然问题( p 0 ) 对应于一个带有非凸目标函数和约束 的非线性最优化问题通过对( p o ) 应用指数变换 y i = e x p 旎，i = 1 ，伽 我们可以得到如下等价的反凸规划问题( r c p ) ： l m i n f o ( z ) ( r c p ) & l m 力 0 ，i = 1 ，n o ， f = i7 0 t i 0 和p 2 岛，那么在x 七上不存在r l p ( x o ) 的可行解，否则，考虑下面两种情况；如 果存在某些指标h 1 ，n ) 和j 1 ，m 】- 满足喙 0 和嚎 u b ，则令x 南= 国；否则计算式( 2 1 0 ) 中的p ；( i = 1 ，n ) 若对h 1 ，佗) 有入 0 及p 岛，令x k = d ；否则计算式( 2 1 1 ) 中的嗾如果对某些歹 1 ，m ) 及h l ，佗) ，入鼽 0 和嚷 0 ，我们要找一个可行解z x 使得 9 ( z ) u b g 所以，我们找的z 被限定在集合厂n 【a ，6 】中，这里 厂= zg ( z ) u b e ，h ( x ) 0 ，m = 1 ，m ) 减小割的目的是用一个小的矩形 a ，6 ，】c 【a ，b 来替代矩形【a ，6 】，而且不失去任何的 点xe 厂n o ，6 】满足这个条件的矩形 a ，6 ，】记为r e d ，a ，6 】，其中= u b 一为了说 ，j l_，1【 i i = 七m 出 鼍 x 第二章特殊反凸规划问题的分支定界方法 明r e d ，【o ，6 】= 【a 7 ，卅是怎样由减小割得到的，定义如下的函数 定义2 4 1 给定两个矩形 a ，6 】和【a 7 ，6 ，】，且【a 7 ，6 ，】 a ，6 ，对i = 1 ，礼，m = 1 ，m ，定义函数妒( q ) ，螺( q ) 和砒( a ) ：f 0 ，1 】一r 为 妒( n ) = q k ( b q ( 玩一a i ) e ) 一p k ( n ) ， 1 蠊( q ) = p k ( a 7 + a ( b i n ：) e ) 一q k ( b ) ， 妒j ( q ) = g ( a 7 + a ( b i o ：) e ) 一， 其中函数夕( z ) ，p k ( x ) 和q k ( x ) 分别由( 2 1 ) ，( 2 3 ) 和( 2 4 ) 式给出， 从函数9 ( z ) ，p k ( x ) 和q k ( x ) 的性质很明显看出，函数妒( a ) ，坛( q ) 和编( a ) 在区间 o ，1 】是连续的，或者是严格单调的因此r e d ，a ，6 】可由如下定理给出 定理2 4 3 ( i ) 对某些仇= 1 ，m ，如果g ( a ) 或p k ( a ) 一q k ( b ) ，那么对每个z 【a ，6 】， g ( x ) g ( a ) 如果存在m 1 ，m 使得p k ( a ) 一q k ( b ) 0 ，那么对每个 z 【a ，6 】，h ( x ) = p k ( x ) 一饥( z ) p k ( a ) 一q k ( b ) 0 在这两种情况下都有：厂n 【a ，6 】= d 2 1 n n = = 0 仇 ；m 赢 螺 l l m l 【 l i i | n n 藤 巨 并 特殊非凸规划问题的全局最优化方法 ( i i ) 给定任意点x a ，6 】满足 9 ( z ) ，p k ( x ) 一q k ( x ) 0 ，m = 1 ，m ， 我们将说明x 【a ，6 ，】令 q 未一m i n a 纛lm = 1 ，m ) ，熊，一m i n 熊lm = 1 ，m ) 首先，我们说明z a 7 否则存在指标i 使得 x t a ：= 玩一q 麓，( 玩一吼) ，也就是说，z t = b i a ( b i 一吼) ，q l ， q 1 ( 2 1 2 ) 考虑f 面两种情况： 情况1 ：如果a 未，= 1 ，那么从( 2 1 2 ) 式，有瓤 n ：= b i a 麓，( 6 t o i ) = a i ，这与 x 【a ，6 】矛盾 情况2 ：如果0 q i ， 1 ，函数妒。i ，( q ) 关于单变量o 在区间【o ，1 是严格递减的从 ( 2 1 4 ) 式和a 袅，的定义 a m ，( 6 一( b t x i ) ) 一p m ，( o ) = q m , ( b o e ( b i a i ) e ) 一p m ，( 口) = 妒，( q ) 妒，( q ，) = 0 ， 因此。 q m ，( 6 一( b i x d e 。) p m ，( n ) 另外，因为q m ，( z ) 是关于佗维变量z 的递增函数，并且x b 一( b i x i ) e ，我们有 q m ，( z ) q m ，( 6 一( b i x d e 。) 6 ，= a ：+ 雕，( b i n ：) ， ( 2 一1 3 ) 第二章特殊反凸规划问题的分支定界方法 即，存在p 使得 x i = a ：+ f l ( b i n ：) ，雕， 6 ：= a ：+ ( b i 一口：) = 玩，这与 z a ，6 】，即z t b i 矛盾 情况2 ：如果0 矽麓，( 雕，) ( 2 1 6 ) 假定( 2 - 1 5 ) 式成立，我们可以从( 2 1 4 ) 式得到 g ( a 7 + ( x i 一) e ) = g ( a 7 + f l ( b 一o ：) ) 由x a 7 + ( x i n ：) e 和夕( z ) 是递增的 g ( x ) g ( a 7 十( 甄一口：) e ) ， 这与g ( x ) 矛盾 如果( 2 - 1 6 ) 式成立，我们从( 2 1 4 ) 式得到 p r o ( d 7 + ( x i o ：) e ) = p r o ( 口7 + z ( b t n ：) e i ) q m ，( 6 ) ， 因为z + ( x t o ：) 和p 。，( z ) 都是增的，则有 p r o , , ( z ) p m ，( n 7 + ( 兢一n ：) e ) q m ，( 6 ) 这与p r o , , ( z ) q m ，( z ) q m , ，( 6 ) 矛盾 从上面的结果，我们有z 6 ，也即z a 7 ，6 ，】 口 特殊非凸规划问题的全局最优化方法 2 5 算法及收敛性 在这一部分，给出求解问题( p ) 的一种分支减小定界( b r b ) 算法，基于上述的线性 松弛方法和新的减小规则，算法需要在) 岛的剖分子集上求解一系列( r l p ) 问题基于 矩形x o 的剖分子矩形，考虑分支定界树的每个节点因此，在算法的任意阶段k ，假设 我们有一个活动节点的集合，定义为五，即，对每个矩形x x o ，vx 五我们要通过 r l p ( x ) 的最优值和晶( n ) ，计算( p 1 ) 的目标函数值的一个下界l b ( x ) ，所以( p 1 ) 在第 七步的最优值的下界为m i n l b ( x ) ，vx 兀】_ 根据标准分支规则，我们选择一个活动 节点，把它划分为两个子矩形对每个新节点，减小它，再根据上述计算下界同时，如 果有必要，更新上界u 仇通过计算任一非提高的节点，我们为下一步提供一个活动节点 的集合，重复这个过程直到收敛点 2 5 1 算法陈述 步o ：选择收敛容许 0 令p o = x o ) ，7 0 = 1 【】如果存在一些可行解是可 用的，把它们增加到集合厂，并且令u b o = m i n ( g ( x ) ix 厂) ，否则，令厂= 仍及 u b o = + 。置k = 0 步1 ：删除每个使得g ( a ) u b k 一或p k ( a ) 一q k ( b ) u b 一，计算出使得g ( a + e ( b o ) ) = u b 一的点仝= a + e ( b a ) 第二章特殊反凸规划问题的分支定界方法 ，否则，令圣= b i v ) 如果芦0 ，定义新的上界矿b k = m i n g ( x ) lz 芦) ，和已知最好的可行点 z + = a r g m i n g ( x ) iz 厂) 置磊= ( 五x 七) u 硝 步4 ：置五+ 1 = 五 xl b ( x ) u b k e ，x 五) 如果瓦+ l = 谚，算法停止：如果u b k = + o 。，这个问题是不可行的，否则，u b k 是最 优值，矿是最优解否则，选择一个活动节点x 抖1 = a r g m i n l b ( x ) ix 五+ 1 做进 一步考虑 步5 ：使用分支规则，把x 七十1 剖分为两个子矩形，且令r + 1