# 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
def logsumexp(M, A, x, b):
k = int(A.shape[0])
u = M.variable(k)
M.constraint(Expr.sum(u), Domain.equalsTo(1.0))
M.constraint(Expr.hstack(u,
Expr.constTerm(k, 1.0),
Expr.add(Expr.mul(A, x), b)), Domain.inPExpCone())

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).

def max_volume_box(Aw, Af, alpha, beta, gamma, delta):
with Model('max_vol_box') as M:
xyz = M.variable(3)
M.objective('Objective', ObjectiveSense.Maximize, Expr.sum(xyz))

logsumexp(M, array([[1,1,0],[1,0,1]]), xyz, array([log(2.0/Aw), log(2.0/Aw)]))

M.constraint(Expr.dot([0, 1, 1], xyz), Domain.lessThan(log(Af)))
M.constraint(Expr.dot([1,-1, 0], xyz), Domain.inRange(log(alpha),log(beta)))
M.constraint(Expr.dot([0,-1, 1], xyz), Domain.inRange(log(gamma),log(delta)))

M.setLogHandler(sys.stdout)
M.solve()

return exp(xyz.level())

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