几何规划

[外文]：geometric programming

一类特殊的非线性规划。20世纪60年代起，从工程设计费用小化问题的研究中，发展了这类特殊非线性规划的处理方法。这类特殊规划的研究中，几何平均不等式有着根本的作用，因而称之为几何规划。它在化学和机械、土木、电气、核工程以及管理科学等方面有许多应用。

设 与w=（′表示转置）都是T维向量，并且v>0与w≥0，亦即它们的分量分别都为正与非负，则有

式中，而当wt=0时定义为1;又，当且仅当

时，(1)中的等号成立。特别当时，(1)就是熟知的几何平均-算术平均不等式。

以上两个不等式的意义在于把不等式左方若干项的和与右方若干因子的乘积相联系。在许多实际问题中，需要小化的目标函数（例如工程费用）常常可以写成若干项之和，根据广义几何平均不等式，它绝不小于某些因子的乘积。在某些情况下，通过适当选取w1，w2，…，wT，可使这一乘积变成一个与决策变量无关的常数，所选取的wt，即为使目标函数等于这一下界（此时也是小值）的决策变量数值，也就是问题的较优解。这就是早期几何规划的常用方法。

形如

的有正变向量 的函数称为正项式，其中系数ct必须为正，而指数rtn(n=1，2，…，N)可为任意实数。

人们最初研究的几何规划是正项几何规划，即有正变向量 尣>0的、目标函数和约束函数都是正项式的非线性规划

min g0(尣)，s.t.gm(尣)≤1 (m=1，2，…，M)，

尣>0，

式中都是正项式。

一般地，正项式(3)未必是x的凸函数，所以正项几何规划(4)一般不是凸规划，但是通过变换zn=lnxn(n=1，2，…，N)可将 g(尣)化成 z的凸函数。因此尽管正项几何规划不一定是凸规划， 但它具有凸规划所有的优良性质:它的任何局部极小点一定也是它的整体极小点。

记

于是，，由此及(1)可知，对于任何w＝≥0，都有

式中。特别，如果取w使之满足，则由(5)及gm(x)≤1(m =1，2，…，M)，可知

的右方与尣无关，记为d(w)；又，当且仅当

成立时，g0(尣)与d(w)相等。称

max　　　d(w)，

s.t.　　w 00=1，

为正项几何规划(4)的对偶规划。因为lnd(w)是w的凹函数，所以对偶规划(8)的任何局部极大点也是它的整体极大点。由(6)可知， 对于正项几何规划(4)与对偶规划(8)的任何一对可行解x与w，(4)的目标函数值绝不小于(8)的目标函数值，并且当且仅当(7)式成立时，这两个规划的目标函数值才相等，这时x与w分别是(4)与(8)的较优解。

设正项几何规划(4)有满足gm(尣)<1(m=1，2，…，M)的可行解并且有较优解，则对偶规划(8)也有较优解，并且这两个规划的较优值相等。

对偶定理的假设条件之一是(4)有较优解。但是在什么情况下(4)一定有较优解呢？可作如下的回答：

若(4)有可行解而(8)有分量全为正的可行解，则正项几何规划(4)必有较优解。

由于对偶规划只有线性约束条件，特别对于某些特殊情形，例如当出现在各个gm(尣) (m ＝0，1，…，M)中的项数总和正好比变量个数N多1时，对偶规划只有惟一的、可以通过解线性方程组得到的可行解，所以相对而言，对偶规划的求解似乎应当容易些。在实际应用中，以对偶定理为基础，往往先设法求出对偶规划的较优解w*，然后通过求解与(7)等价的、以lnxn为变量的线性方程组

来获得正项几何规划(4)的较优解。因为，所以由(7)或(9)中的第一式可知，实际意味着υ0t(尣)在正项几何规划目标函数g0(x)中所占的较优比例。

近十多年来，除了正项几何规划外，对于容许系数сmt为负的符号几何规划、出现反向约束不等式gm(尣)≥1的反向几何规划以及gm(尣)是两个正项式的商的补几何规划，也有了不少的研究，特别是E.L.彼得森的工作扩大了几何规划的研究范围。

参考书目

R.J.Duffin， E.L.Peterson and C.M.Zener，Geometric Programming-Theory and Application，John Wiley & Sons， New York，1967.

J.G.Ecker， Geometric Programming: Methods. Computa-tion and Application，SIAM Review，22，pp.338～362，1980.

E.L.Peterson， Geometric Programming─a Survey，SIAM Review，18，pp.1～51，1976.