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

          ∑                 [  T    T        T ]T        [  T   T       T  ]T
lse(u) = log  exp(uk),    F =   F0  F 1  ⋅⋅⋅ Fm    ,    g =  g0  g1  ⋅⋅⋅ gm    .
           k

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 means that the algorithm reached the maximum number of iterations before a solution was found. The ’x’, ’snl’, ’sl’, ’y’, ’znl’ and ’zl’ entries are None.

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.base import matrix, log, exp  
from cvxopt import 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’] )