# 7.5 Geometric Programming¶

Geometric programs (GP) are a particular class of optimization problems which can be expressed in special polynomial form as positive sums of generalized monomials. More precisely, a geometric problem in canonical form is

(7.8)$\begin{split}\begin{array}{lll} \minimize & f_0(x) & \\ \st & f_i(x) \leq 1, &i=1,\ldots,m, \\ & x_j>0, &j=1,\ldots,n, \end{array}\end{split}$

where each $$f_0,\ldots,f_m$$ is a posynomial, that is a function of the form

$f(x) = \sum_k c_kx_1^{\alpha_{k1}}x_2^{\alpha_{k2}}\cdots x_n^{\alpha_{kn}}$

with arbitrary real $$\alpha_{ki}$$ and $$c_k>0$$. The standard way to formulate GPs in convex form is to introduce a variable substitution

$x_i=\exp(y_i).$

Under this substitution all constraints in a GP can be reduced to the form

(7.9)$\log(\sum_k\exp(a_k^Ty+b_k)) \leq 0$

involving a log-sum-exp bound. Moreover, constraints involving only a single monomial in $$x$$ can be even more simply written as a linear inequality:

$a_k^Ty+b_k\leq 0$

We refer to the MOSEK Modeling Cookbook and to [BKVH07] for more details on this reformulation. A geometric problem formulated in convex form can be entered into MOSEK with the help of exponential cones.

## 7.5.1 Example GP1¶

The following problem comes from [BKVH07]. Consider maximizing the volume of a $$h\times w\times d$$ box subject to upper bounds on the area of the floor and of the walls and bounds on the ratios $$h/w$$ and $$d/w$$:

(7.10)$\begin{split}\begin{array}{rrl} \maximize & hwd & \\ \st & 2(hw + hd) & \leq A_{\mathrm{wall}}, \\ & wd & \leq A_{\mathrm{floor}}, \\ & \alpha & \leq h/w \leq \beta, \\ & \gamma & \leq d/w \leq \delta. \end{array}\end{split}$

The decision variables in the problem are $$h,w,d$$. We make a substitution

$h = \exp(x), w = \exp(y), d = \exp(z)$

after which (7.10) becomes

(7.11)$\begin{split}\begin{array}{rll} \maximize & x+y+z \\ \st & \log(\exp(x+y+\log(2/A_{\mathrm{wall}}))+\exp(x+z+\log(2/A_{\mathrm{wall}}))) \leq 0, \\ & y+z \leq \log(A_{\mathrm{floor}}), \\ & \log(\alpha) \leq x-y \leq \log(\beta), \\ & \log(\gamma) \leq z-y \leq \log(\delta). \end{array}\end{split}$

Next, we demonstrate how to implement a log-sum-exp constraint (7.9). It can be written as:

(7.12)$\begin{split}\begin{array}{l} u_k\geq \exp(a_k^Ty+b_k),\quad (\mathrm{equiv.}\ (u_k,1,a_k^Ty+b_k)\in\EXP),\\ \sum_k u_k = 1. \end{array}\end{split}$

This presentation requires one extra variable $$u_k$$ for each monomial appearing in the original posynomial constraint.

// Models log(sum(exp(Ax+b))) <= 0.
// Each row of [A b] describes one of the exp-terms
public static void logsumexp(Model      M,
double[,]  A,
Variable   x,
double[]   b)
{
int k = A.GetLength(0);
Variable u = M.Variable(k);
M.Constraint(Expr.Sum(u), Domain.EqualsTo(1.0));
M.Constraint(Expr.Hstack(u,
Expr.ConstTerm(k, 1.0),
}

We can now use this function to assemble all constraints in the model. The linear part of the problem is entered as in Sec. 7.1 (Linear Optimization).

public static double[] max_volume_box(double Aw, double Af,
double alpha, double beta, double gamma, double delta)
{
using (Model M = new Model("max_vol_box"))
{
Variable xyz = M.Variable(3);
M.Objective("Objective", ObjectiveSense.Maximize, Expr.Sum(xyz));

logsumexp(M,
new double[,] {{1,1,0}, {1,0,1}},
xyz,
new double[] {System.Math.Log(2.0/Aw), System.Math.Log(2.0/Aw)});

M.Constraint(Expr.Dot(new double[] {0,1,1}, xyz), Domain.LessThan(System.Math.Log(Af)));
M.Constraint(Expr.Dot(new double[] {1,-1,0}, xyz), Domain.InRange(System.Math.Log(alpha),System.Math.Log(beta)));
M.Constraint(Expr.Dot(new double[] {0,-1,1}, xyz), Domain.InRange(System.Math.Log(gamma),System.Math.Log(delta)));

M.SetLogHandler(Console.Out);
M.Solve();

double[] xyzVal = xyz.Level();
double[] hwdVal = new double[3];
for(int i=0; i<3; i++) hwdVal[i] = System.Math.Exp(xyzVal[i]);

return hwdVal;
}
}

Given sample data we obtain the solution $$h,w,d$$ as follows: