# 6.6 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

(6.14)$\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

(6.15)$\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.

## 6.6.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$$:

(6.16)$\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 (6.16) becomes

(6.17)$\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 (6.15). It can be written as:

(6.18)$\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. The explicit representation of affine conic constraints (ACC, see Sec. 6.2 (From Linear to Conic Optimization)) in this case is:

$\begin{split}\left[\begin{array}{ccccc}0&0&0&1&0\\0&0&0&0&0\\1&1&0&0&0\\0&0&0&0&1\\0&0&0&0&0\\1&0&1&0&0\end{array}\right] \left[\begin{array}{c}x\\y\\z\\u_1\\u_2\end{array}\right] + \left[\begin{array}{c}0\\1\\ \log(2/A_{\mathrm{wall}})\\0\\1\\ \log(2/A_{\mathrm{wall}})\end{array}\right] \in \EXP\times\EXP.\end{split}$

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

[r,res] = mosekopt('symbcon');

% Input data
Awall = 200;
Afloor = 50;
alpha = 2;
beta = 10;
gamma = 2;
delta = 10;

% Objective
prob = [];
prob.c = [1, 1, 1, 0, 0]';

% Linear constraints:
% [ 0  0  0  1  1 ]                    == 1
% [ 0  1  1  0  0 ]                    <= log(Afloor)
% [ 1 -1  0  0  0 ]                    in [log(alpha), log(beta)]
% [ 0 -1  1  0  0 ]                    in [log(gamma), log(delta)]
%
prob.a = [ 0  0  0  1  1;
0  1  1  0  0;
1 -1  0  0  0;
0 -1  1  0  0 ];

prob.blc = [ 1; -inf;        log(alpha); log(gamma) ];
prob.buc = [ 1; log(Afloor); log(beta);  log(delta) ];

prob.blx = [ -inf; -inf; -inf; -inf; -inf];
prob.bux = [ inf; inf; inf; inf; inf];

% The affine conic part FX+g \in Kexp x Kexp
%   x  y  z  u  v
% [ 0  0  0  1  0 ]    0
% [ 0  0  0  0  0 ] +  1               in Kexp
% [ 1  1  0  0  0 ]    log(2/Awall)
%
% [ 0  0  0  0  1 ]    0
% [ 0  0  0  0  0 ] +  1               in Kexp
% [ 1  0  1  0  0 ]    log(2/Awall)
%
%
prob.f = sparse([0 0 0 1 0;
0 0 0 0 0;
1 1 0 0 0;
0 0 0 0 1;
0 0 0 0 0;
1 0 1 0 0]);

prob.g = [ 0; 1; log(2/Awall); 0; 1; log(2/Awall)];

prob.accs = [ res.symbcon.MSK_DOMAIN_PRIMAL_EXP_CONE, 3, res.symbcon.MSK_DOMAIN_PRIMAL_EXP_CONE, 3 ];

% Optimize and print results
[r,res]=mosekopt('maximize',prob);
exp(res.sol.itr.xx(1:3))