（应用数学专业论文）几何规划算法及其在集成电路设计中的应用.pdf

摘要 摘要 几何规划是一类特殊的非线性规划，也是一种高效的全局优化方法，特别是 许多工程设计中抽象出来的模型都是几何规划的形式，因此它被广泛地应用到 自然科学和社会科学的各个领域，已经成为研究和解决自然科学和工程中许多 复杂问题的一个强有力的工具。在实际应用中还发现，几何规划能用来解决鲁 棒设计问题并快速地扩展设计空间，也就是说，不仅能处理繁多的器件尺寸问 题，而且融合不同的已知设计得出新的电路布局。在当代混合信号集成电路中， 电路设计问题就是要自动设置模拟电路中器件以及晶体管的尺寸，使得电路性 能最优化。为此要在很宽的范围内确定设计参数使得电路性能达到最优。研究 表明，电路性能可以表示为设计参数变量的正项式。因此，电路设计问题可以 转化成几何规划问题。 本文研究采用几何规划方法来优化及自动设置模拟电路中器件与晶体管的 尺寸。创新点是提出了一个基于线性松弛的全局优化算法。该算法的技术线路 是：首先将原几何规划问题转化为一个反向凸规划；其次分别构造出凸约束的 线性下界估计和反向凸约束的线性上界估计；再其次获得原几何规划问题的线 性松弛规划，由此确定原几何规划问题的最小值的下界；最后结合分支定界理 论得出全局优化算法。 本文我们用数学的方法证明了该算法的收敛性。作为应用，文中也给出了 该算法应用于平面螺旋电感器和某些r f 电路的实例。 关键词：几何规划全局优化线性松弛电路设计 a b s t r a c t a bs t r a c t g e o m e t r i cp r o g r a m m i n gi sas p e c i lc l a s so fn o n l i n e a rp r o g r a m m i n g ，a n di ti sa n v e r ye 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 t h e r e f o r e ，i tw a sa p p l i e dw i d e l yt o t h e a r e a si n v o l v i n gn a t u r a ls c i e n c e sa n ds o c i a ls c i e n c e s e s p e c i a l l y , an u m b e ro f p r o b l e m so fe n g i n e e r i n gd e s i g n sf r e q u e n t l ym a yb et r a n s l a t e d i n t ot h eg e o m e t r i c p r o g r a m m i n gp r o l e m ss ot h a tg e o m e t r i cp r o g r a m m i n gi st h ep o w e r f u lt o o lt od e s i g n t h ec i r c u i t a st h ed e v e l o p i n go fg e o m e t r i cp r o g r a m m i n g ，i tm a yb eu s e dt oe a r l yo u t r o b u s td e s i g n sa n dt oe x p a n dt h ed e s i g ns p a c e i no t h e rw o r d s ，i ta l l o w sc i r c u i t d e s i g n e r st od e s i g nr e a l l y , f e ，i n v e s t i g a t et h ed i f f e r e n td e s i g nt r a d e o f f s ，d e s i g nn e w c i r c u i tt o p o l o g i e s ，d e b u g ec i r c u i t sr a t h e rt h a nd e a l i n gw i t ht e d i o u ss i z i n gi s s u e s c u r r e n t l y , i nt h ef i e l do ft h em i x e d - m o d ei n t e g r a t e dc i r c u i t s ，t h ec o m p l e x i t yo ft h e a n a l o gc i r c u i t si st o p1 f o rw h i c h ，aw i d er a n g eo fs p e c i f i c a t i o n sh a v et ob em e ta n d s e n s i t i v i t yt op r o c e s sv a r i a t i o n si sv e r yh i 曲i tw a ss h o w n t h a taw i d ev a r i e t yo f c i r c u i tp e r f o r m a n c em e a s u r e sh a v eas p e c i a lf o r m ，f p ，t h e ya r ep o s y n o m i a lf u n c t i o n s o ft h ed e s i g nv a r i a b l e s a sar e s u l t ，c i r c u i td e s i g np r o b l e m sc a nb ep o s e da sg e o m e t r i c p r o g r a m m i n gp r o b l e m i nt h i sp a p e r , ad e t e r m i n i s t i cg l o b a lo p t i m i z a t i o na l g o r i t h mb a s e do nl i n e a r r e l a x a t i o ni s p r o p o s e df o rl o c a t i n g t h eg l o b a lm i n i m u m m f i r s t l yt h ei n i t i a l n o n c o n v e xp r o b l e mi sr e d u c e dt oat y p i c a lr e v e r s ec o n v e xp r o g r a m m i n g ，a n dt h e na l i n e a rr e l a x a t i o no ft h ep r o b l e mi so b t a i n e db a s e do nb o t ht h ee s t i m a t i o no ft h el i n e a r l o w e rb o u n df o rt h ec o n v e xc o n s t r a i n t sa n dt h ee s t i m a t i o no ft h el i n e a ru p p e rb o u n d f o rt h er e v e r s ec o n v e xc o n s t r a i n t s t h i sr e l a x a t i o np r o g r a m m i n gp r o v i d e st h el o w e r b o u n do ft h es o l u t i o no ft h eo r i g i n a lp r o b l e m t h i sp r o p o s e da l g o r i t h mw i l lo u t p u t t h eg l o b a lm i n i m u mc o n v e r g e n t l y t h en u m e r i c a lr e s u l t ss h o wt h a ta b o v et e c h n i q u e m a yb eu s e dt op r o c e s sm o r 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 ，a n d t h ea p p l i c a t i o n t ot h ep l a n a rs p i r a li n d u c t o r sa n ds o m er a d i of r e q u e n c yc i r c u i ta r ed e s c r i b e di nd e t a i l i i a b s t r a c t k e yw o r d s ：g e o m e t r i cp r o g r a m m i n g ；g l o b a lo p t i m i z a t i o n ；l i n e a r r e l a x a t i o n c i r c u i td e s i g n 1 1 1 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：髟形铹彦l 经指导教师同意，本学位论文属于保密，在 扣飞年，f 只功日 年解密后适用本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： ! 一”一? 一”j 、 ! 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长1 0 年，可少于1 0 年； ；机密2 0 年( 最长2 0 年，- i 少- p2 0 年) ：。一。，+ ，。：一。，。，一。0 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 文焉 矽步年7 月z 7 日 第1 章几何规划概论 第l 章几何规划概论 几何规划( g e o m e t r i cp r o g r a m m i n g ，简称g p ) 是一种具有特定形式的优化 问题，其目标函数与约束函数都有特定的形式要求，即均为变量的正项式函数。 虽然几何规划在上世纪6 0 年代提出之后己被深入研究，但其远不及线性规划被 广泛应用甚至鲜为人知。因此，本章首先给出几何规划的概论，包括简单回顾 几何规划的历史，引述几何规划在工程领域和经济领域的一些应用例子，给出 相应的特殊形式的函数( 单项式与正项式函数) 以及正项几何规划的定义。然 后从定义出发，陈述几何规划与凸规划问题的转换。本章还陈述了几种用于解 正项几何规划问题的方法最后，阐述了广义几何规划及其解法。 1 1 几何规划的研究进展 几何规划的研究始于1 9 6 1 年，由西屋电气公司的一位研究员克拉伦斯齐 纳( c l a r e n c ez e n e r ) 在研究工程中成本最小化问题时提出的。他们发现有一种特 殊形式的问题可以非常容易地解出。恰在此时卡内基梅隆大学的r i c h a r dd u f f m 教授正在研究非线性规划问题的对偶理论。d u f f i n 获悉z e n e r 的工作后，便在对 偶理论基础上为几何规划构建数学架构。于是，d u m n ，p e t e r s o n 与z e n e r 于1 9 6 7 年出版了几何规划的奠基著作几何规划。书中给出了几何规划的基础理论以 及在电气工程中的一些应用( 例如变压器的优化设计) 。之所以采用了“几何规 划”这个称呼，是因为早期的数学理论广泛应用了正数的和与积之间的代数几 何平均不等式。从现在的眼光看，本书在数值解法方面没有多少内容。 到了1 9 6 0 年代末期，对几何规划的研究，已经从理论与应用两方面进行了 大量工作。随后1 9 7 0 年代，z e n e r 出版了几何规划工程应用，b e i g h t l e r 与p h i l l i p s 出版几何规划应用。1 9 7 8 年，优化理论与应用期刊( j o u m a lo fo p t i m i z a t i o n t h e o r ya n d a p p l i c a t i o n s ) 连续做了两期几何规划的专题。1 9 8 0 年e c k e r 的论文【l 】 中，列出了许多几何规划的应用与方法，包括了当时采用的数值解法。 虽然几何规划未被数学学科的规划界痛快接纳【2 】( 只是将几何规划视为一 种新奇的事物) ，但在工程界( 从核工程领域到经济学领域) 却得到了广泛应用， 第1 章几何规划概论 获得了大量研究成果。例如化学工程领域 3 5 】，经济领域 6 1 0 ，电气工程领域 【1 1 1 3 ，环境工程领域【1 4 1 6 】，机械工程领域 1 7 - 1 9 1 ，核i 酬 2 0 2 1 等等。 1 2 几何规划定义 我们首先定义与几何规划相关的一些函数。 1 2 1 单项式函数 设变量一，矗，z 为正实数变量。具有下列形式的函数g ：r “一r g ( x ) = 婶母廿，c o ，r ( 1 1 ) 称为单项式函数。显然，任意正的常量均为单项式：单项式之间进行乘法、 除法运算后仍为单项式；一个单项式的任意幂次仍为单项式。 1 2 2 正项式函数 多个单项式的非负线性组合称为正项式。即 r 厂( x ) = c k x i i 砖h 皆，气o ( 1 2 ) k = l 任意单项式均为正项式。由定义可知，正项式之积、之和仍为正项式；如 果厂为一正项式，g 为一单项式，贝, l j f g 为一正项式；若y 为一非负整数，为 一正项式，则厂为正项式。 1 2 3 逆一正项式函数 正项式函数的倒数 办( z ) 2 夏磊再1 虿 3 ) 称为逆正项式函数。 1 2 4 标准几何规划 几何规划的标准形式是具有如下形式的优化问题 2 第1 章几何规划概论 m i n i m i z e 石( x ) s u b j e c tt o z ( x ) 1 ，i = 1 ，m ， ( 1 4 ) g i ( x ) = l ，皓1 ，p 其中，石为正项式函数，舒为单项式函数，麓为优化变量，薯 0 是一个隐 含约束条件。我们将( 1 4 ) 作为几何规划的标准形式以区别于下面给出的各种 扩展形式。 在标准g p 形式中，目标函数厶( x ) 必须是正项式( 并且必须是最小化r a i n 形式) ；约束函数中的等式必须是单项式等于1 的形式；约束函数中的不等式必 须为正项式小于等于1 的形式。 对于使用者来说，g p 最重要的一点就是可以高效地获得全局解。通过简单 的技巧与转换，我们可以将大量的优化问题转换为g p 形式进行解决。我们首先 看一些情形( 包括约束函数) ： 如果厂为一正项式，g 为一单项式，则约束函数中的不等式( x ) g ( x ) 可以 表示为厂( 石) g ( x ) 1 ，可以作为g p 的标准形式处理( f i g 为正项式) 。特别地， 若约束条件形式为厂( x ) a ，其中为正项式，a 为常数日 0 ，则其可以处理为 g p 的标准形式f ( x ) a l 。 如果h 为一逆正项式，g 为一单项式，则约束函数中的不等式h ( x ) g ( x ) 可 转换为正项式约束1 ( 办( x ) g ( x ) ) l 。 同理，若g l 与9 2 均为单项式，则约束函数g l ( x ) = 9 2 ( x ) 可记为 g l ( x ) 9 2 ( z ) = 1 ( g l 9 2 仍为单项式) 。 考虑下面的优化问题 m a x i m i z e x ：2 x 3 s u b j e c tt o x 1 1 x 2 - n 工3 3 2 3 3 + 1 恐 ( 1 5 ) l 工2 3 五= 4 1 压万 显然这不是g p 的标准形式，通过上面给出的方法将其转化为g p 标准形式 3 第1 章几何规划概论 m i n i m z e i o ( x ) = 百1 巧1 x 3 s u b j e c tt o 石( x ) = 3 3 可1 霹3 + 百1 霹3 巧1 1 左( x ) = x , - 1 l ( 1 6 ) 石( x ) = o 2 3 ) 而1 铂( x ) = ( v 4 1 ) f5 o = 1 此问题的优化值是( 1 5 ) 的优化值的倒数。 1 2 5 正项式几何规划与广义几何规划 几何规划的一般形式为： i m i n 五( x ) ( g g p ) ： s 1 g 。( x ) 吒，m = 1 ，p ； ( 1 7 ) 【 x o ，x r 一 其中a m = + 1 或- 1 。显然该问题是一个关于变量x 的具有非凸可行域的非线 性优化问题。几何规划可分为正项式几何规划和广义几何规划两类，若( x ) 中 c k 0 ，x 0 ，则称瓯( x ) 为关于变量x 的正项式函数，若对于所有的 m = o ，l ，p ，有c k 0 且瓯= + l ，则称( g g p ) 问题是一个正项式几何规划，若 存在 0 ，l7 v - - 4 ， f = l ，m ( 1 1 0 ) 丑0 ， i = l ，m 4 v + 心，鸬= o 其中v j = ( _ 1 ，h ，2 h ，与1 ，q 是第i 个约束的第j 项的系数，矩阵 = q l ，q 2 ，口j ，局 r 局，其列向量q ，对应第f 个约束的第，项的指数。 许多算法都是基于对偶规划来求解原正项几何规划问题，但是由于目标函 数在自变量取值为0 的点处不可微，因此所有基于对偶的方法最终都将面临这 个问题，就使基于对偶的方法存在很大的数值困难。 灵敏度理论 在灵敏度分析中，主要是考虑g p 约束条件中微小的变化如何影响最终的优 化值。 考虑如下优化问题 m i n i m i z e f o ( x ) s u b j e c tt o z ( x ) p 嘶，江1 ，m ， ( 1 1 1 ) 红( x ) = p 畸，f - 1 ，p 其中，；为正项式函数，h ，为单项式，x ，为优化变量，嘶与，为常量。当u ，= 0 ，q = 0 时，此式就简化为g p 标准式( 1 4 ) 。称( 1 1 1 ) 为扰动g p 标准式( 因为约束 被改变或干扰了) 。记p ( u ，v ) 为干扰g p 的优化值，则p ( o ，0 ) 为标准g p ( 1 4 ) 的优化值。这里主要研究u ，1 ，取较小值时的情况，此时矿与e 坼接近1 。 如果u i 0 ，则干扰问题的第f 个约束不等式为，( x ) e 虬是松弛的( r e l a x e d ) ( 与标准问题中的f ( 工) 1 对比而言) 。相反，如果u i 0 ，则干扰问题的第f 个 约束不等式松弛了1 0 0 ( e + 一1 1 个百分点；如果u ， 0 问题( g g e l ) 的最优值即为原广义几何规划( g g p ) 的最优值。 ( 2 ) 若( g g p ) 的最优值为负，则( g g 尸) 问题等价于如下问题： 9 第1 章几何规划概论 ( g g p 2 ) ： r a i n x o 豇x o c o ( x ) - 1 q ( x ) 吒，掰= l ，p x r n + i , x 0 问题( g g p 2 ) 的最优值的负倒数即为问题( g g p ) 的最优值。 另一种方法是在( g g e ) 的目标函数中加上一个较大的常数，保证其最优值为 正，再采用结论( 1 ) 中的方法，将目标函数转化为单变量函数，这种方法的缺陷是需 要事先估计出原问题最优值的个粗略的下界。 下面考虑约束函数，例如考虑这样一个约束： 瓯( x ) = 啊( x ) 一缟( x ) 1 ( 1 1 4 ) 其中啊( x ) 红( z ) 均为正项式函数。则x 满足( 1 1 4 ) 当n 仅当存在变量s 0 使得 ( x ，s ) 满足下面不等式： 啊( x ) s h 2 ( x ) + l ( 1 1 5 ) 不等式( 1 1 5 ) 显然等价于下面两个不等式 栩( z ) 1 ( 1 1 6 ) l s - i 红( z ) + s q 1 ( 1 1 6 ) q b 的第一个不等式为正项式约束，第二个不等式为反向正项式约束，即为规 划( 尺尸尸) 中的约束形式，详见文献 3 1 】 在1 3 中，我们说明了一个正项式几何规划等价于一个凸规划问题，但对于广 义几何规划问题，则没有相应的结论，主要是由于这些反向正项约束产生非凸可 行域，一般来说广义几何规划的局部最小点不是它的全局极小点，为了减少反向 凸约束所产生的求解难度，我们也可以把( r 即) 问题进一步转化为只含有一个反 向约束的反向正项几何规划。考虑如下s 个反向正约束： g j ( x ) l ，= 1 ，s ( 1 1 7 ) 其中g j ( x ) 均为正项式。上面的系统等价于如下不等式：g ( x ) l ，其中 g ( x ) = m i n g l ( x ) ，9 2 ( x ) ，g ，( x ) ) 1 0 第1 章几何规划概论 另外g ( x ) 也可以表示为如下形式：g ( x ) = p ( x ) = g ( x ) ，其中 p ( x ) = g l ( x ) + 9 2 ( x ) + + g ，( x ) g ( x ) = m a ) 【 衙g j ( x ) ：r = 1 ，2 ，s 引入一个新的变量，则我们可以改写( 1 1 7 ) 为： i t - l p ( x ) l l ，一1 + f 一；i ，g ( x ) l ：r = ：1 ，2 ，s 显然上式中第一个约束为反向正项约束，其余的约束为正项式约束。因此任 何广义几何规划可以转化为一个有且仅有一个反向正项约束的反向正项几何规 划问题。做指数变量替换后有等价于仅有一个反向凸约束的凸规划问题。这种 形式的问题性质比较好，研究起来比较方便，但是目前这方面的研究比较少。 广义几何规划求解方法可分为以下三类 对偶法 类似于正项式几何规划问题，广义几何规划问题也存在具有线性约束的对偶 问题，但其目标函数取对数之后不是凸函数。正项几何规划的对偶理论并不能 平移到广义几何规划中，我们称广义几何规划的对偶为“伪对偶”。由于对伪对偶 的研究比较困难，因此对于广义几何规划的求解，采用对偶法的算法很少，主要的 算法见文献 3 2 3 3 】 压缩法 由于广义几何规划的伪对偶研究起来很困难，所以大多数的算法都是直接考 虑其原问题，如正项式压缩逼近法，双压缩线性逼近法等， 正项式压缩逼近法是通过一列正项式规划去逼近原广义几何规划。由文献 3 1 的讨论知，规划问题( g g p ) 可以写为如下等价形式： ( q g g p ) ： m l n x o 豇y m ( x ) = 丽q m ( x ) l ，肼= l ，p x r n + l , x 0 其中瓯( x ) 和己( 工) 均为正项式，令 第1 章几何规划概论 己( 石) = f e ( 。l ，( x ) = t e 【, n l c t 兀_ 矽，姨( x ) 也具有同样形式。 下面简要描述正项式压缩逼近算法： 步1 ：将所求的规划问题转化为( q g g p ) 的形式 步2 ：给定可行点叠，在该点处计算权重向量s ，由这些权重向量压缩正项式 【引，得单项式函数【x ，川，从而得到压缩正项式几何规划。 步3 ：求积压缩正项式几何规划问题，记其最优解为x 。 步4 ：若x = i ，则算法终止，x 即为所求问题的最优解；否则，令叠= x + ，转步2 另外一种压缩法为双压缩线性逼近算法。该算法实际上是上述正项式压缩 逼近算法和1 3 3 中求解正项式几何规划的压缩法的一个巧妙结合，这里就不在 详细描述。 另一类求解方法是利用最新的优化技巧，并充分利用广义几何规划的特点来 设计算法，如文献【3 4 】针对混合约束广义几何规划问题，构造了一列二次规划算法， 并证明了算法的全局收敛性和局部二阶收敛速度；文献 3 5 1 针对广义几何规划问 题，利用约束变尺度法，提出了一种有效算法，并证明了算法的全局收敛性和局部 二阶收敛速度；文献 3 6 】利用无约束广义几何规划的特点，构造出一种有效的压缩 信赖域算法，并证明其全局收敛性和局部二阶收敛速度；文献【3 7 】利用有效集策略 及信赖域思想，结合具有约束的广义几何规划的特征，构造出一种具有全局收敛 性的有效算法。 1 5 本文的主要工作 本文的主要工作集中叙述在第二章，提出了一种基于线性松弛的确定型全 局优化算法，该算法首先将原问题转化为一个反向凸规划，再分别构造出凸约 束的线性下界估计和反向凸约束的线性上界估计，从而获得原问题的线性松弛 规划，由该松弛规划来确定原规划问题最小值的下界，然后结合分支定界理论 提出一种全局优化算法，并从理论上证明了算法的收敛性。为了显示算法的实 用性，我们以平面螺旋电感器和视频电路为例，展示了如何建立几何规划形式 螺旋电感器模型的过程。 第2 章广义几何规划的全局优化方法 第2 章广义几何规划的全局优化方法 本章针对具有不等式约束的广义几何规划问题，讨论了求解其全局最优解 的两种方法，一种是m a r a n a s 与f l o u d a s 3 8 提出的基于凸松弛的全局优化算法， 另一种是本文提出的基于线性松弛的全局优化算法，我们提出的新算法是通过 一种新的方法获得原规划的线性松弛规划，从而可以确定原规划问题最小值的 下界，基于分支定界理论，通过对线性松弛规划的序列修正，最终用序列线性 规划的最优解逼近原广义几何规划的最优解，并给出了该全局优化算法的收敛 性证明。数值实验验证了算法的有效性和可行性，与m a r a n a s 3 8 的方法进行对 比，数值结果表明了该算法的优越性。 2 1 基于凸松弛的全局优化算法 针对第一章中提出的的( g g p ) 问题，根据目标函数及约束函数中系数的正 负，重新组合，可得到如下形式的广义几何规划： ( e g g p ) ： m i n 风( x ) = n o ( x ) 一h o ( x ) s 7 三乙( x ) = z 酷( x ) 一三( x ) s o ，m = 1 ，p x 0 ，x r ” 其中 碟( x ) = 州+ 兀二中，m = o ，p 钣( x ) = 槲一兀二咿，m = o ，p 这里，咖r 表示以( x ) 中的所有系数为正的正项之和，【。r 表示峨( x ) 中的所有系数为负的正项之和。 在规划( e g g p ) 中，令置= e x p z , ，i = 1 ，n ，并赋予变量上下界约束，则规划 ( e g g p ) 问题转化为： 第2 章广义几何规划的全局优化方法 其中 m i n f o ( z ) = 嚣( z ) 一f o - ( z ) j f 吒( z ) = 露( z ) 一巧( z ) o ，m = l ，p 才刁，i = l ，2 ，拧 焉( z ) = f e 【。】+ c 。，e x p z ：! = 。，。乏) ，m = o ，p 巧( z ) = z t 。i m - e x p 三。“刁) ，m = o ，p 由于一个以e 为底，以线性函数为指数的函数为凸函数，所以上述( d c ) 规 划中目标函数和约束函数均为凸函数之差的形式。因为z ? = h l ( # ) ，所以我们假 设( e g g p ) 中的变量置的下界是严格正的。 下面介绍一个松弛凸规划的构造方法，该松弛凸规划的最优值是原( d c ) 规 划问题最优值的一个下界。其主要思想是用一个线性函数一c ( z ) 去下估每一个 凹函数一c ( z ) 。这个线性函数的构造方法是用线性函数下估每一项 一e x p 二。“五) 。通过上述构造方法，我们可以得到下面形式的松弛凸规划问 题： lr a i nf o 一( z ) = g ( z ) 一厶( z ) ( 畏) ： s j 巴”( z ) = 露( z ) 一乞( z ) o ，m = 1 ，p 【z 互，i = 1 ，2 ，刀 其中c ( z ) 与( d c ) 中的相同，厶( z ) 形式如下： 乞( z ) = 气， 以，+ 既，( 厶。弓) 川= o ，p f ( 圳| - i = 1 日： 4 ：型! 鲨! 丝! 二鐾! 兰丛墨2 ” 圪一瑶 = e x p l ( y ：( ) - 歹e x j _ p ( y 竺) 瑶= 二。m i n ( l , 。考，。) 瑶= ：。m a x ( r 。，。孝，。z y ) 1 4 第2 章广义几何规划的全局优化方法 规划( r ) 的最优值是( d c ) 规划的最优值的下界，且( r ) 为凸规划，可采用成 熟的凸规划的软件或求解方法来求解。 基于上述讨论，文献 3 8 1 d p 提出一种基于分支定界理论的松弛凸规划逼近算 法，通过在不断被分割的超多面体上求解序列松弛凸规划问题，最终逼近( 勿c ) 问题的最优解，并给出了算法的收敛性证明，文献中还根据几何规划特点提出 一些特殊的处理技巧，加快了收敛速度，且使得算法更加稳定，有关算法详细 内容见文献 3 8 1 ，这里就不再详细描述。 类似于构造凹函数一乞( z ) 的线性下估的方法，我们同样可以构造出凸函数 露0 ) 的线性下估艺( z ) ，从而问题( 尺) 又可松弛为： ( 三r ) ： r a i n 厶( z ) = e ( z ) 一c o ( z ) j ， 厶( z ) = 乞( z ) 一乞( z ) 5o ，m = 1 ，p 考互 z u ，i = l ，2 ，疗 显然问题( l r ) 是规划规划问题( d c ) 的线性松弛规划，该规划的最优值提供 了规划( d c ) 的最优值的一个下界。同样的，基于分支定界理论，也可以确定一 个基于线性松弛的确定型全局优化算法，这里就不再详细给出。 2 2 基于线性松弛的全局优化算法 本节针对广义几何规划( g g p ) 问题，提出了一种新的基于线性松弛的确定 型全局优化算法。我们首先通过指数变量替换，将原来的非凸规划转换为反向 凸规划，然后采用一种新的方法获得该反向凸规划的线性松弛规划，通过所构 造的线性松弛规划来确定原规划问题最小值的下界，最后采用分支定界理论和 方法确立了该全局优化算法，并证明了算法的收敛性。数值实验表明该算法是 有效可行的。 本节考虑如下形式的广义几何规划问题： j m i ng o ( x ) ( g g p ) ： s 1 瓯( x ) 瓯，m = 1 ，2 ，p ； 【x g i o = x ：0 五芹 o ，= + l 或- 1 ， 第2 章广义几何规划的全局优化方法 瓯= + l 或- l ，。为任意的实常指数。该问题只是在1 4 节中给出的( g g p ) 划 问题中增加变量x 的上下界约束后所得的规划形式。通常规划问( g g p ) 是一个具有非凸可行域的非线性优化问题，若对于所有的t = l ，乙， m = 0 ，l ，p ，瓦，= + l 且屯= + 1 ，贝j j ( g g p ) 问题是一个正项几何规划，由于 正项几何规划经过转化后等价于一个凸规划问题，其局部最优解即为全局 最优解，因此我们这里考虑存在负系数的广义几何规划问题的全局优化方 法。 反向凸规划的构造 由1 4 中的讨论知，任意的几何规划问题( g g p ) 都可以等价的转化为目标函 数为单变量的反向正项几何规划( r p p ) ，因此，针对( g g p 7 ) 问题，我们可以得 到如下正项几何规划： ( 尼即) ： r a i n x o s 1 g 卅o ) l ，m = o ，l ，历 g 。( 工) l ，m = p + l ，g ； x q o = x ：o # 带 0 及任意非负权重 向量g ，其分量之和为1 ，则有如下不等式： 一 毋 ( ) 兀( 等) 定义当t = d 时，( 哆乞) 岛= l 。考虑如下正项式函数 ( x ) = ( x ) = ，兀矿 ffi 给定向量厶d 且= l ， f 则压缩正项式磊 ) 被定义为： 毛( x ) = 瓦兀母 j 其中瓦= i - ，( 薏) 且瓦，= ，显然压缩正项式磊( x ) 是单项正项式。根 据上述讨论，我们可以得到( r c p ) 中的凸约束函数厶( z ) ( 其中 m = 0 ，l ，p ，乙= l n x , ) 的压缩函数为： 厶( z ) = 瓦e x p ( f , ，刁) ( 2 1 ) 其中瓦及死，如前面的定义。我们选择任意的权重向量d ， 有分量之和均为1 ，用压缩函数代替原凸约束函数得： 厶( z ) 1 ，m = 0 ，1 ，p ， 且显然对于任意的m = 0 ，1 ，p ，有下面的不等式成立： 厶( z ) 厶( z ) 1 7 且每个向量的所 ( 2 2 ) 第2 章广义几何规划的全局优化方法 因此用压缩约束( 2 2 ) 替代原凸约束后，( r c p ) 的可行域扩大，并包含原问题 的可行域。不等式约束( 2 2 ) 两边同时取对数后可以转化为等价的线性约束的 形式： 厶( z ) = l i l 瓦+ 死。z ，o ，m = o ，p 其次考虑针对反向凸约束的线性松弛构造方法，对于反向凸约束，我们将 用线性函数厶( z ) 去上估反向凸函数厶( z ) ，其中m = p + l ，q ，文献【3 8 】中给出 了用一个线性函数下估一个凹函数的方法，这里采用的方法与其类似，详细过 程不再描述，只给出结论。上估线性函数为： 兀” l ( z ) = ， 1 ，m = o ，p 计算新的权重值虿： 瓦：墚户l ，一，巧 一丽一刮7 然后按2 2 3 中描述的方法根据上述权重值压缩函数z ( z ) ，得到一个新的压 缩单项式，从而给线性松弛规划( 三即) 增加一个新的约束。用( l r p ) 乘1z ( z ) 分 别表示增加线性约束后的新的线性松弛规划和压缩单项式函数，根据2 2 3 中的 讨论知： z ( z ) = 巧e x p ( 。y l l i z i ) 其中巧= 1 - i 。( 气瓦) 勖且万。= ，儿，毛 显然下式成立 ( z ( 三( q 揶= 彳( 三( q 揶) ) 并且因为f , f f , ( f 2 小) 1 因此点三( q 揶) 不满足新增加的如下约束： z ( z ) l 由算术几何平均不等式知 z ( z ) z ( z ) 因为新增加的单项式约束z ( z ) 1 ，因此若z 是( 尺c p ) 的可行点，则必定也 是( 三r 尸) 的可行点，y i _ i h - j 题( l r p ) 的可行域显然不包括点三( q 邢) ，因此这个界 紧技术逐渐切割掉不包含原问题可行点的区域，加