（计算数学专业论文）两类全局优化问题的一种新的分支减小定界算法.pdf

l l 摘要 分支定界算法是全局优化主要算法之一，被广泛地应用于整数规划和非线性规划等优 化模型中，近年来一直是最优化领域的研究热点在过去的几年里，人们一直在寻找求解 效率高，迭代次数少，运行时间短的新方法，以便求解实际生产中大规模优化问题本文 是在已有理论的基础上，针对符号几何规划问题和非线性比式和问题，提出一种新的有效 方法一分支减小定界算法，主要内容如下： 第一章，概述全局优化常用的算法，及本文所研究问题的背景与现状，并简单介绍本 文所做的工作 第二章，给出用新的分支减小定界算法求解符号几何规划问题的主要步骤这一章是 利用线性化方法和线性下估计函数，确定原问题的松弛线性规划，然后把可行域逐渐剖分 加细，同时相应的构造出使目标函数值单调增加的下界序列和单调减小的上界序列，当上 界和下界相等或它们的差值满足误差要求时，得到问题的近似最优解特别的，在减小部 分，两个减小操作能够删掉一大部分不存在最优解的区域并证明了算法能收敛到原问题 的全局最优解，最后的数值结果表明提出的算法是可行和有效的 第三章，针对非线性比式和问题，首先引进p 个变量和p 个约束，这比其他方法引进 的个数都少，把原问题转化为一个等价的规划问题，再由指数变换及线性下估计函数得到 另一个等价规划问题，利用新的分支减小定界算法求解这个等价问题，在求解问题之前， 首先调用这个算法求解引进变量的上界和下界，得到的所有引进变量的上下界比其他方法 好得多，数值结果也充分表明该方法在迭代次数，运行时间方面较其他方法有明显的改进 关键词：全局优化，符号几何规划，非线性比式和，减小操作，分支减小定界 i i a b s t r a c t t h eb 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 ，h a s b e e nw i l d l ya p p l i e di ni n t e g e rp r o g r a m m i n ga n dn o n - l i n e a rp r o g r a m m i n g ，a n dw h i c hh a s b e e nt h eh o tt o p i co fr e s e a r c hi nt h eo p t i m i z a t i o nf i l e d si nr e c e n ty e a r s d u r i n gt h ep a s t d e c a d e s ，i no r d e rt os o l v et h el a r g es c a l eo p t i m i z a t i o np r o b l e m si np r a t i c a lp r o d u c t i o n ， p e o p l eh a v eb e e nl o o k i n gf o rt h en e wa l g o r i t h m ：c o m p u t a t i o n a le f f i c i e n t yo ft h ea l g o r i t h m i sh i g h e r ，s o m em e t h o d sm a yp r o v i d ea nf e a s i b a ls o l u t i o n ，t h ec p ut i m ei ss h o r t e r ，a n d t h en u m b e ro ft h en o d ei ss m a l l e r i nt h i sp a p e r ，w ep r o p o s ean e we f f e c t i v em e t h o d ( b r a n c h - r e d u c e - a n d - b o u n da l g o r i t h m ) 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 r s o m e s p e c i f i co p t i m a lp r o b l e m s m a i nc o n t e n t sa r ea sf o l l o w s ： i nc h a p t e r1 ，ab r i e fi n t r o d u c t i o ni sg i v e nt ot h ec o m m o n l yu s e do p t i m i z a t i o nm e t h o d s a 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 r i nc h a p t e r2 ，an e wb r a n c h r e d u c e - a n d b o u n da l g o r i t h mi sg i v e nt os o l v es i g n o m i a l g e o m e t r i cp r o g r a m m i n g ( s g p ) f i r s ta 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 mi sc o n - s t r u c t e db ye 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 f ( s g p ) p r o b l e m ，a n dt h e ns e v e r a lb a s i co p - e r a t i o n st h a tc a l lb 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 et w or e d u c t i o no p e r a t i o n sc a n c 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 m o r e o v e r ，b yu s i n gt h el i n e a r i z a t i o nm e t h o d ，( s g p ) p r o b l e mi sr e d u c e dt oas e q u e n c eo f l i n e a rp r o g r a m s ，a n dt h ep r o p o s e da l g o r i t h mi sp r o v e nt h a ti ti sc o n v e r g e n tt ot h eg l o b a l i i i k e yw o r d s ：g l o b a lo p t i m i z a t i o n ，s i g n o m i a lg e o m e t r i cp r o g r a m m i n g ，r e d u c t i o no p - e r a t i o n s ，n o n l i n e a rs u mo fr a t i o s ，b r a n c h - r e d u c e - a n d - b o u n d i v 摘要 a b s t r a c t 目录 i i i i 第一章绪论 1 1 1 全局优化算法概述 1 1 2 本文所研究问题的背景和现状 4 第二章符号几何规划问题的全局优化算法 9 2 1 引言 9 2 2 等价问题 9 2 3 关键的算法过程 1 3 2 3 1 下界 1 3 2 3 2减小操作 1 6 2 4 算法及收敛性 2 2 2 5 数值结果 2 4 第三章非线性比式和问题的全局优化算法 2 9 3 1 引言 2 9 3 2 等价单调转化 3 0 3 3 基本操作。 3 4 3 3 1剖分规则。 3 4 3 3 2 下界 3 5 v 3 3 3减小操作 3 8 3 3 4 引进变量的上下界 3 8 3 4 算法及收敛性 3 8 3 5 数值实验 4 0 结论 参考文献 致谢 攻读硕士学位期间写作或接受的论文 独创性声明 v i 4 5 4 7 5 5 5 7 5 9 1 1 全局优化算法概述 第一章绪论 近年来随着信息技术的飞速发展，全局优化在经济模型、金融、网络、图像处理、核 能和机械设计、化学工程设计和分子生物学等众多领域的应用越来越广泛，使得在科学、 经济和工程中的许多进展都依赖于计算相应优化问题全局最优解的数值技术，因此全局最 优化理论和方法值得深入研究 全局优化问题的数学模型为： m i n ，( z ) ， s t g i ( x ) 0 ，i = 1 ，2 ，m ， ( z ) = 0 ，j = 1 ，f ， 其中，函数f ：留_ 冗称为目标函数，z 朋称为决策变量，( x ) = 0 ，j = 1 ，2 ，f 称 为等式约束，g i ( x ) 0 ，i = 1 ，2 ，m 称为不等式约束( 当存在i ，使得g i ( x ) 0 时，两端 同时乘以一1 ，即可转化为“”的形式) ，q = z 印ig i ( x ) 0 ，i = 1 ，2 ，m ；( z ) = o ，j = 1 ，2 ，f ) r n 称为可行域，可行域中的点称为问题的可行解，若存在x + q ，且 对一切z q ，都有，( z + ) ，( z ) ，则称x + 为问题的全局最优解 有时也将上述最优化问题写成下面的向量形式： i n f ，( z ) ， s t x q 抽象出的优化模型，可以分为如下几类：线性规划、二次规划、整数规划、几何规划、 多目标规划，此外，还有动态规划、不可微规划、参数规划和随机规划等现有的求解这些 问题的方法依据它们的收敛性质分为两大类，确定性方法和随机性方法确定性方法如： 区间方法、分支定界方法、填充函数方法、罚函数方法、外逼近( 内逼近) 方法、对偶方 法等等；随机性方法如：遗传算法、模拟退火算法、随机搜索方法、随机函数方法等等 下面简单介绍几种常见的全局优化算法： 1 两类全局优化问题的一种新的分支减小定界算法 ( 1 ) 分支定界方法 分支定界方法考虑的问题是： m l n 厂( z ) x e s 。、 其中sc 舻，s 为紧集，函数厂：毋一冗在s 上连续 分支定界方法是一种较为常见的全局优化方法，被广泛的应用在整数规划、非线性规 划等优化模型中，近年来一直是最优化领域的研究热点基本思想是通过把可行域逐渐剖 分加细，同时相应的构造出目标函数值单调减小的上界序列和单调增加的下界序列，当上 界和下界相等或者上界与下界的差满足误差要求时，迭代终止，得到全局最优解；否则迭 代继续进行下去其主要步骤为：分支、定界和剪枝，不同的分支定界方法在于这三种基 本运算的不同处理手段 ( 2 ) d c 规划 在优化中存在一大类函数都可以看作是d c 的，d c 规划是指具有如下形式的问 题： m i n s o ( z ) 一夕0 ( z ) ， s t 五( z ) 一g i ( x ) 0 ，i = 1 ，2 ，m ， z d 其中d 是r n 中的紧凸集，五，g i ，i = 0 ，1 ，m 是钟中的凸函数，通常我们称表示 为两个凸函数差的函数为d c 函数任一d c 规划问题都可以通过凹极小化算法求解 凹函数有很好的组合性质，即如果它有解，那么解一定出现在可行域的极点中，为了求解 凹极小化问题，人们已经提出了一些算法，这些算法多以分支定界技巧、割平面方法、最 优性条件和整数规划方法等为基础 ( 3 ) 区间方法 区间方法考虑的问题是 m i n f ( x ) x e s 其中s 是扎维闭区间，：r n _ r 在x 上连续区间全局优化的基本思想是将分枝定 2 第一章绪论 界方法和m o o r e - s k e l b o e 算法【1 相结合突出优点是能在给定精度内求出问题的全部全 局极小点这类方法的基本步骤有：定界、分支、终止、删除和分裂，其中包括区间分裂 规则、删除规则及区间选择规则，不同的区间算法在于这几种规则的不同处理手段上不 同类型的全局优化区间方法可参考文献 2 ， 3 】， 4 】，【5 】等 ( 4 ) 填充函数法 填充函数法考虑的问题是 m i nf ( x ) z r ” 填充函数法由r g e 最先提出，他在文献 6 ， 7 】中构造了求解上式问题的填充函数算法 这类方法包括极小化和填充两个阶段，关键是如何构造出更好的填充函数，其基本思想 是：首先利用局部极小点的方法求得f ( x ) 在可行域中的一个极小点z ：，然后构造填充 函数，设法找f ( x ) 的另一个比z i 低的局部极小点z ；，即z i z ；且满足，( z ；) ，( z i ) 重复上述过程，直到找到f ( x ) 的全局极小点有关填充函数的具体构造可参看 文献 6 7 ，【8 】， 9 ，【1 0 】， 1 1 】， 1 2 】等另外，张连生、李端和n g 等人对填充函数的定义进行 了很大的改进，给出了一些性质比较好的填充函数【1 3 并且张连生、李端等人 1 4 】把改 进后的填充函数用于求解非线性规划，建立了一个用填充函数直接求解非线性整数规划的 近似算法，为求解非线性整数规划提供了一个有效的途经 ( 5 ) 离散最优化 在很多实际应用中，有许多问题都可归结为离散优化问题求解这类问题的方法主要 有组合化方法和连续化方法离散最优化和连续最优化之间存在一定的联系其中一个问 题是混合整数规划和线性互补问题的等价性问题，还有一个就是极小极大问题，经典的极 小极大理论最初是由y o nn e u m a n n 结合对偶理论和鞍点知识提出的，最近连续的极小极 大理论已经被应用于s t e i n e r 树、网络流、组合分组测试等问题中，最突出的是应用新的 连续极小极大方法解决了s t e i n e r 树问题 1 5 】 ( 6 ) 单调优化算法 有些优化问题的数学模型关于部分变量或者全部变量是单调的，例如广义几何规划， 3 两类全局优化问题的一种新的分支减小定界算法 多乘积规划等非线性优化问题都可以转化为单调优化问题来求解例如可以转化为如下的 单调优化形式： m l n 厂( z ) ， s t 五( z ) 一g i ( x ) 0 ，i = 1 ，2 ，m ， 其中函数，( z ) ，五( z ) ，矶( z ) ，i = 1 ，2 ，m ，都是殿上的增函数，有关这类问题的求解算 法可以参看文献 5 】和 7 2 】 ( 7 ) 随机函数方法 随机函数方法虽然不能有效的求解传统的全局优化问题，但是能够成功的应用于目标 函数的估计代价较高的全局优化问题在这个方法中，相关的随机函数有如下形式： r ( x 1 ，z 2 ) = e x p ( 一d ( x 1 ，z 2 ) ) ， 其中d 是一个距离函数，d 函数的选取是不唯一的 综上所述，近年来研究者在现有算法的基础上对不同的模型提出了更多新的有效算 法，但是有些还存在一定的局限性由于这些问题的复杂性，要想设计出更快速有效的全 局优化方法，特别是快速高效地求解大规模优化问题，还需科学工作者不懈的努力 1 2 本文所研究问题的背景和现状 其中 4 在第二章中，考虑如下符号几何规划( s g p ) 问题： 即i m i n c o ( y ) 一， y = 可r ? 10 鲥犰聍 0 ，那 么( s g p ) 减小为一类多项式几何规划( p g p ) ，它是( s g p ) 问题的理论基础 ( s g p ) 问题最初是在三十多年前由d u f f i n 等人 1 6 - 1 8 】提出的后来又被其它学者 研究其特有的结构性质以及较好的理论基础，引起了广泛的应用和一些有用结果的产生 f 1 9 - 2 1 ，尤其在生产规划、选址、分布情况、风险管理问题，在不同的化学过程设计和工 程设计等问题 1 9 ，2 1 2 6 】尽管( s g p ) 是一类特殊的非线性规划，正如文献 2 7 ，2 8 】所指出 的，许多非线性规划可以被转化为几何规划，并且这些几何规划需要通过一些简单的变量 变换又可以转化为简单的线性规划形式因此，给出好的( s g p ) 算法是很有必要的 求解( s g p ) 问题的局部优化方法一般包括三类第一，通过多项式逐次逼近，称为 “缩合，参看文献【2 9 】第二，p a s s y 和w i l d e 3 0 发展了一种弱对偶，称为“伪对偶”，以适 应此类非线性优化第三，适应一般的非线性规划方法【3 1 】尽管求解( s g p ) 问题的局部 优化方法很多，但基于( s g p ) 问题结构特性的全局优化算法确是很少的( s g p ) 问题的 特殊例子，例如“在圣m ( 秒) 里是正整数或者实数，已经被一些作者考虑 2 4 ，3 2 ，3 3 ，3 4 ，3 5 对于每一个抗是实的，m a r a n a s 和f l o u d a s 3 4 】提出一个基于( s g p ) 特性的指数变量 变换凸松弛全局最优算法( c r a ) ；s h e n 和z h a n g 3 6 提出了一个基于( s g p ) 特性的指 数变量变换和在一些超平面区域的切超曲面、凸包络近似、线性松弛和分支定界的全局最 优算法最近，s h e n 等人【3 7 给出( s g p ) 问题的一个鲁棒算法；w a n g 等人【3 8 】对于 求解( s g p ) 问题给出一种广义算法；q u 等人【3 9 】针对( s g p ) 问题提出一种利用线性松 弛的全局最优算法 在本章里，我们假定( s g p ) 问题是可行的本章针对( s g p ) 问题，通过利用减小运算 和通过在剖分子集上求解一系列线性规划问题，给出了一种新的全局最优算法，提出的方 法是基于( s g p ) 问题特性的一种简单转化这样原问题( s g p ) 等价的转化为一个单调优 化问题( p ) ，即，在问题( p ) 里，目标函数是递增的，所有的约束函数可以记为两个递增函 数的差这个方法和其他方法的对比给出如下：第一，提出的线性松弛是基于单调优化问 题( p ) ，这应用了更多( s g p ) 问题的结构特性，参看文献 3 4 ，3 6 】并且最重要的是提出的 减小运算能够删掉一大部分不存在( s g p ) 问题最优解的区域这个过程比文献 3 6 ，4 7 ，4 8 】 5 两类全局优化问题的一种新的分支减小定界算法 中的方法更有效第二，本章讨论的问题概括了文献 2 4 ，3 2 ，3 3 ，3 5 】中的，具有一般性并 且，我们的方法在计算上比利用凸松弛的文献 3 4 】更简便，因为主要工作是求解线性规 划和严格单调函数的单变量在区间 o ，1 ) 的零点，这可以通过现存的方法求解非常有效， 例如，通过单纯形方法和二等分搜索方法第三，数值结果以及和其他方法的对比说明了 提出算法的潜在优势 在第三章中，我们考虑如下问题： 其中 ( p ) ： m l n s t g o ( y ) ( ) = c j j = l 0 ，m = 1 ，2 ，m o ， y y = y l o 鲥y i 计 o 。，i = 1 ，n o m = 1 ，m o 并且勺，弓t ，萄t ，而t ，7 例，锄m 诱坑都是任意实数 分式规划是非线性优化中的一个重要分支，比式和的优化问题是一类特殊的分式规 化问题，人们对这类问题的研究已有三十年的历史，尤其是最近十多年，这个问题在实际 当中的应用非常广泛，运输方案、经济效益、金融投资等，因此受到了极大的关注并且 因为这类问题拥有许多不是全局最优的局部最优解，所以求解起来比较困难在这些应 用中，目标函数中的比式和数一般不超过4 或5 从研究的角度来看，这些问题构成了 重大理论和计算方面的挑战即使在最简单的例子，即比式都是线性的，虽然他们都有各 自的属性，但他们的和既不是拟凸的，也不是拟凹的，因此，他们一般都具有多个局部最 优解而不是全局最优解在分式规划，大多数理论和算法都是有关比式和问题的，因为它 们都是全局优化问题 5 0 一5 1 】到目前为止，线陛( 或二次，多项式) 分式函数的全局优 化问题，引起了众多研究人员的兴趣，并且已经给出了许多求解这类问题的算法，例如， f a l l 【，k u n o ，q u e s a d a 和s h e n 等人 5 2 5 5 】给出一些求解带线性约束的线性比式和问题的全 局最优算法，f r e u n d 和j a r r e 5 6 1 提出了求解带凸约束的凸比凹比式和问题的内点方法， 6 p 2l= “ 铲 加甜 哟 易脚 i | 白 奶 “ 痧 加n 甜 一 己汹 = “ 一； 弘 伽：l 霞僦 = ym9 第一章绪论 g o t o h 和k o n n o 5 7 给出一种定义在多面体上的凸比凸二次分式规划形式的极大化问题 的有效算法，b e n s o n 5 8 6 0 】给出凹比凸比式和问题的三个分支定界算法，y a n g 6 1 】等人 给出了比式和问题的一种锥分算法，最近，s h e n 等人【6 2 6 9 针对不同的在非凸可行集上 的非凸优化问题，利用不同的线性松弛规划给出几个分支定界算法，q u 7 0 】等人基于矩 形分割和拉格朗日松弛，提出一种新的求解非凸二次约束集上的二次比式和问题的分支定 界算法，f a n g 7 1 】等人对一个二次函数与两个二次函数的比的和的极小化问题提出一种 典范对偶方法由于上述问题中每一分式项前带有实系数，且分子分母都是广义多项式， 所以使得求解更加困难，对研究者来说具有更强的理论和计算挑战性，这可能也是今后的 一个研究方向 7 两类全局优化问题的一种新的分支减小定界算法 8 2 1引言 第二章符号几何规划问题的全局优化算法 符号几何规划( s g p ) 问题可以写成如下的非线性优化问题： f lm i n 西o ( 可) ( s g p ) ： 8 t 西m ( ) 0 ，m = 1 ，m o ， i iy v 其中 ( 剪) = 如t 玑，仇= 0 ，1 ， t = lt = 1 y = 可r ? 10 鲥y i 聍 0 ，我们要找( p ) 的个可行解z q 使得r ( z ) u b s 所以，我们找的x 被限定在集合日aa ，6 】中，这里 h ：= zr ( z ) u b 一，f m ( z ) 0 ，m = 1 ，m ) ( 2 7 ) 减小规则a 的目的是用一个较小的矩形 a 7 ，6 ， c a ，b 】来替代矩形 a ，6 】，并且在 a ，卅 中不失z h a a ，6 】中任一点，即使得h a a 7 ，6 ，】= h a a ，6 】满足这个条件的矩形a 7 ，6 ，】 被定义为r e d a ，6 】， z ，= u b g 为了说明r e d ，a ，6 】= 【a 7 ，b i 】是由下面的规则减小得到的，我们首先定义如下的函数 1 6 第二章符号几何规划问题的全局优化算法 定义1 给定两个盒子 a ，6 】和 a ，6 ，】，满足 a 7 ，卅【a ，6 】，i = 1 ，n ，m = 1 ，m ， 函数妒( q ) ，螺( o r ) 和编( 0 1 ) ： 0 ，1 】_ r 被定义为 婊( 0 1 ) = 露( 6 一o l ( b i a i ) e ) 一聪( 口) ， 怯( o l ) = 聪( 0 7 + q ( 玩一n ：) e i ) 一焉( 6 ) ， 惦( 0 1 ) = f o ( a 7 + o l ( b i n ：) e ) 一， 其中e i 是舻的第i 个单位向量，即这个向量满足对v j i ，e i = 1 ，弓= 0 ，而e 册是 分量全为1 的向量，则e = ：1 ，并且函数昂( z ) ，聪( z ) 和焉( z ) 分别在( 2 1 ) ，( 2 3 ) 和( 2 4 ) 式给出 从函数焉( z ) ，聪( z ) a n d 昂( z ) 的性质很明显看出，函数垆( 口) ，坛( q ) 和惦( q ) 在 区间 0 , 1 】或者是连续的，或者是严格单调的利用函数妒囊( q ) ，螺( a ) 和瑞( q ) ，r e d n ，6 】 由如下定理给出 定理3 ( i ) 如果晶( 口) z ，或存在m 1 ，m ，聪( n ) 一( 6 ) 0 ，那么 r e d “o ，6 = a 7 ，b 7 】= d ( i i ) 如果娲( o ) 并且对任意m 1 ，m ，聪( n ) 一蠕( 6 ) 0 ，那么r e d ，【n ，6 】= a 7 ，6 ， ，其中 a t = 6 一m = 粤lm q 袅】( 玩飞) e i 一 、 6 ，= “噼， 熊i m = o1m 一n 减 一 ，、 并且 q l 2 妒。口，：。，喜二，1 。 熊： 1 当螂1 ) ，那么对每个 z a ，6 】，昂( z ) f o ( a ) 1 2 如果存在m 1 ，m ) 使得聪( n ) 一( 6 ) 0 ，那 1 7 两类全局优化问题的一种新的分支减小定界算法 a ，6 ，r ( z ) = 磁( z ) 一f c ，( x ) 碟( n ) 一f c , ( b ) 0 这两种情况都有 意点z 【a ，b 满足 r ( z ) ，葛( z ) 一j = ( z ) 0 ，m = 1 ，m ， 我们要说明z a 7 ，”令 乜m i ，= m i n ( ( 卫im = 1 ，m 】，藤，= m i n f l im = 0 ，1 ，m ) 首先，我们先说明z a 7 如果z 兰a 7 ，那么存在指标i 使得 x i a ：= b i q 2 ，( b i 一口t ) ，i e ，x i = b i o e ( b i a 1 ) w i t hq l ， q 1 ( 2 8 ) 我们考虑下面两种情况： 情况1 ：如果o m i ，= 1 ，那么从( 2 8 ) 式，有x i a ：= b i 一位纛，( 玩一a i ) = a i ，这与 z a ，6 】即既a i 矛盾 情况2 ：如果0 a m i ， 1 ，函数妒，( q ) 随着单变量q 在区间【o ，1 】是严格递减的 如果函数妒幺，( q ) 在单变量q 不是严格递减的，我们得到妒，( q ) 在区间 0 , 1 】一定是连续 的在这种情况下，我们有 垆，( 1 ) = 妒，( o ) = f g ( b ) 一只+ ，( o ) 0 由q i ，的定义有q ，= 1 ，这与0 q l ， 1 矛盾 因为函数妒纛，( q ) 严格递减的，从( 2 8 ) 式和q 象，的定义 ( 6 一( b i x i ) e i ) 一砧( n ) = ( 6 一a ( b i a i ) e ) 一砧( o ) = 妒毛，( q ) 妒，( 口麓，) = 0 ， 因此， 岛( 6 一( b i x i ) e 。) 砖( o ) 另外，对于n 维变量z ，z b 一( b i x i ) e ，且( z ) 是一个递增函数，我们有 f m l ( z ) ，( 6 一( b i x i ) e 。) 6 ，= + 藤，( b i n ：) ，( 2 9 ) 即，存在q 使得 x i = a ：+ o l ( b i 一口：) ，熊” 6 ，= a ：+ ( b i o ：) = b i ，这与 z a 7 ，6 ，即x i b i 矛盾 情况2 ：如果0 熊， 豫，( 熊，) = 0 ( 2 1 2 ) 假定( 2 一1 1 ) 式成立，我们可以从( 2 1 0 ) 式得到 f o ( a 7 + ( x i o ：) e ) =