8.3 Geometric Programming

gp(K, F, g [, G, h [, A, b]])

Solves a geometric program in convex form

minimize   f0(x) = lse(F0x+ g0)
subject to fi(x) = lse(Fix + gi) ≤ 0, i = 1,...,m
           Gx ≼ h
           Ax = b

where

          ∑                 [                  ]         [                 ]
lse(u) = log  exp(uk),    F =   FT0  F T1  ⋅⋅⋅ FmT  T ,   g =  gT0  gT1  ⋅⋅⋅ gTm  T ,
           k

and the vector inequality denotes componentwise inequality. K is a list of m + 1 positive integers with K[i] equal to the number of rows in Fi. F is a dense or sparse real matrix of size (sum(K),n). g is a dense real matrix with one column and the same number of rows as F. G and A are dense or sparse real matrices. Their default values are sparse matrices with zero rows. h and b are dense real matrices with one column. Their default values are matrices of size (0,1).

gp() returns a dictionary with keys ’status’, ’x’, ’snl’, ’sl’, ’y’, ’znl’ and ’zl’. The possible values of the ’status’ key are:

’optimal’
In this case the ’x’ entry is the primal optimal solution, the ’snl’ and ’sl’ entries are the corresponding slacks in the nonlinear and linear inequality constraints. The ’znl’, ’zl’ and ’y’ entries are the optimal values of the dual variables associated with the nonlinear and linear inequality constraints and the linear equality constraints. These values approximately satisfy
        m
∇f (x)+∑  z   ∇f (x)+GT z+AT  y = 0,   f (x)+s    = 0, k = 1,...,m,    Gx+s   = h,   Ax = b
  0    k=1 nl,k  k        l              k    nl,k                          l

and

                                         T      T
snl ≽ 0,   sl ≽ 0,  znl ≽ 0,   zl ≽ 0,  snlznl + sl zl = 0.

’unknown’
This indicates that the algorithm terminated before a solution was found, due to numerical difficulties or because the maximum number of iterations was reached. The ’x’, ’snl’, ’sl’, ’y’, ’znl’ and ’zl’ contain the iterates when the algorithm terminated.

The other entries in the output dictionary describe the accuracy of the solution, and are taken from the output of cp().

As an example, we solve the small GP of section 2.4 of the paper A Tutorial on Geometric Programming. The posynomial form of the problem is

minimize  w- 1h-1d-1
subject to (2∕Awall)hw+ (2∕Awall)hd ≤ 1
          (1∕Aflr)wd ≤ 1
          αwh -1 ≤ 1
          (1∕β)hw-1 ≤ 1
          γwd -1 ≤ 1
          (1∕δ)dw -1 ≤ 1

with variables h, w, d.

from cvxopt import matrix, log, exp, solvers  
 
Aflr  = 1000.0  
Awall = 100.0  
alpha = 0.5  
beta  = 2.0  
gamma = 0.5  
delta = 2.0  
 
F = matrix( [[-1., 1., 1., 0., -1.,  1.,  0.,  0.],  
             [-1., 1., 0., 1.,  1., -1.,  1., -1.],  
             [-1., 0., 1., 1.,  0.,  0., -1.,  1.]])  
g = log( matrix( [1.0, 2/Awall, 2/Awall, 1/Aflr, alpha, 1/beta, gamma, 1/delta]) )  
K = [1, 2, 1, 1, 1, 1, 1]  
h, w, d = exp( solvers.gp(K, F, g)[’x’] )