9.2 Problems with Linear Objectives

The following function for problems with a linear objective is simpler to use than cp(). (In fact, cp() converts the problem to one with a linear objective, and then calls cpl().)

cpl(c, F[, G, h[, dims[, A, b[, kktsolver]]]])

Solves a convex optimization problem with a linear objective

minimize  cTx
subject to  fk(x) ≤ 0, k = 0,...,m - 1
          Gx ≼ h
          Ax = b.

c is a real single-column dense matrix.

F is a function that evaluates the nonlinear constraint functions. It must handle the following calling sequences.

The other arguments have the same meaning as in cp().

cpl() requires that the problem is solvable and that

                  ([ ∑m - 1                                       ])
rank(A) = p,   rank     k=0 zk∇2fk(x) AT   ∇f0(x)  ⋅⋅⋅∇fm -1(x)  GT    = n,

for all x and all positive z.

Example: floor planning

This example is the floor planning problem of section 8.8.2 in the book Convex Optimization:

minimize   W + H
subject to A    ∕h - w  ≤ 0,  k = 1,...,5
           xmi≥n,k0, kx ≥ k0,  x  ≥ 0
           x1+ w  + 2ρ ≤ x , 4x + w  + ρ ≤ x , x + w  + ρ ≤ x , x + w  + ρ ≤ x , x + w  ≤ W
           y1≥ 01,  y ≥ 03,  y 2≥ 0 2       3    3   3       5    4   4       5    5   5
           y2+ h + ρ3≤ y,  y5+ h  + ρ ≤ y , y + h + ρ ≤ y,  y + h  ≤ H,  y + h  ≤ H
           h2∕γ ≤2w ≤ γh1,  1k = 11,...,5. 4    3   3      4    4   4        5   5
            k      k    k

This problem has 22 variables

W,    H,     x ∈ R5,   y ∈ R5,    w ∈ R5,   h ∈ R5,

5 nonlinear inequality constraints, and 26 linear inequality constraints. The code belows defines a function floorplan() that solves the problem by calling cp(), then applies it to 4 instances, and creates a figure.

import pylab  
from cvxopt import solvers  
from cvxopt.base import matrix, spmatrix, mul, div  
 
def floorplan(Amin):  
 
    #     minimize    W+H  
    #     subject to  Amink / hk <= wk, k = 1,..., 5  
    #                 x1 >= 0,  x2 >= 0, x4 >= 0  
    #                 x1 + w1 + rho <= x3  
    #                 x2 + w2 + rho <= x3  
    #                 x3 + w3 + rho <= x5  
    #                 x4 + w4 + rho <= x5  
    #                 x5 + w5 <= W  
    #                 y2 >= 0,  y3 >= 0,  y5 >= 0  
    #                 y2 + h2 + rho <= y1  
    #                 y1 + h1 + rho <= y4  
    #                 y3 + h3 + rho <= y4  
    #                 y4 + h4 <= H  
    #                 y5 + h5 <= H  
    #                 hk/gamma <= wk <= gamma*hk,  k = 1, ..., 5  
    #  
    # 22 Variables W, H, x (5), y (5), w (5), h (5).  
    #  
    # W, H:  scalars; bounding box width and height  
    # x, y:  5-vectors; coordinates of bottom left corners of blocks  
    # w, h:  5-vectors; widths and heigths of the 5 blocks  
 
    rho, gamma = 1.0, 5.0   # min spacing, min aspect ratio  
 
    # The objective is to minimize W + H.  There are five nonlinear  
    # constraints  
    #  
    #     -wk + Amink / hk <= 0,  k = 1, ..., 5  
 
    c = matrix(2*[1.0] + 20*[0.0])  
 
    def F(x=None, z=None):  
        if x is None:  return 5, matrix(17*[0.0] + 5*[1.0])  
        if min(x[17:]) <= 0.0:  return None  
        f = -x[12:17] + div(Amin, x[17:])  
        Df = matrix(0.0, (5,22))  
        Df[:,12:17] = spmatrix(-1.0, range(5), range(5))  
        Df[:,17:] = spmatrix(-div(Amin, x[17:]**2), range(5), range(5))  
        if z is None: return f, Df  
        H = spmatrix( 2.0* mul(z, div(Amin, x[17::]**3)), range(17,22), range(17,22) )  
        return f, Df, H  
 
    G = matrix(0.0, (26,22))  
    h = matrix(0.0, (26,1))  
    G[0,2] = -1.0                                       # -x1 <= 0  
    G[1,3] = -1.0                                       # -x2 <= 0  
    G[2,5] = -1.0                                       # -x4 <= 0  
    G[3, [2, 4, 12]], h[3] = [1.0, -1.0, 1.0], -rho     # x1 - x3 + w1 <= -rho  
    G[4, [3, 4, 13]], h[4] = [1.0, -1.0, 1.0], -rho     # x2 - x3 + w2 <= -rho  
    G[5, [4, 6, 14]], h[5] = [1.0, -1.0, 1.0], -rho     # x3 - x5 + w3 <= -rho  
    G[6, [5, 6, 15]], h[6] = [1.0, -1.0, 1.0], -rho     # x4 - x5 + w4 <= -rho  
    G[7, [0, 6, 16]] = -1.0, 1.0, 1.0                   # -W + x5 + w5 <= 0  
    G[8,8] = -1.0                                       # -y2 <= 0  
    G[9,9] = -1.0                                       # -y3 <= 0  
    G[10,11] = -1.0                                     # -y5 <= 0  
    G[11, [7, 8, 18]], h[11] = [-1.0, 1.0, 1.0], -rho   # -y1 + y2 + h2 <= -rho  
    G[12, [7, 10, 17]], h[12] = [1.0, -1.0, 1.0], -rho  #  y1 - y4 + h1 <= -rho  
    G[13, [9, 10, 19]], h[13] = [1.0, -1.0, 1.0], -rho  #  y3 - y4 + h3 <= -rho  
    G[14, [1, 10, 20]] = -1.0, 1.0, 1.0                 # -H + y4 + h4 <= 0  
    G[15, [1, 11, 21]] = -1.0, 1.0, 1.0                 # -H + y5 + h5 <= 0  
    G[16, [12, 17]] = -1.0, 1.0/gamma                   # -w1 + h1/gamma <= 0  
    G[17, [12, 17]] = 1.0, -gamma                       #  w1 - gamma * h1 <= 0  
    G[18, [13, 18]] = -1.0, 1.0/gamma                   # -w2 + h2/gamma <= 0  
    G[19, [13, 18]] = 1.0, -gamma                       #  w2 - gamma * h2 <= 0  
    G[20, [14, 18]] = -1.0, 1.0/gamma                   # -w3 + h3/gamma <= 0  
    G[21, [14, 19]] = 1.0, -gamma                       #  w3 - gamma * h3 <= 0  
    G[22, [15, 19]] = -1.0, 1.0/gamma                   # -w4  + h4/gamma <= 0  
    G[23, [15, 20]] = 1.0, -gamma                       #  w4 - gamma * h4 <= 0  
    G[24, [16, 21]] = -1.0, 1.0/gamma                   # -w5 + h5/gamma <= 0  
    G[25, [16, 21]] = 1.0, -gamma                       #  w5 - gamma * h5 <= 0.0  
 
    # solve and return W, H, x, y, w, h  
    sol = solvers.cpl(c, F, G, h)  
    return  sol[’x’][0], sol[’x’][1], sol[’x’][2:7], sol[’x’][7:12], sol[’x’][12:17], sol[’x’][17:]  
 
pylab.figure(facecolor=’w’)  
pylab.subplot(221)  
Amin = matrix([100., 100., 100., 100., 100.])  
W, H, x, y, w, h =  floorplan(Amin)  
for k in xrange(5):  
    pylab.fill([x[k], x[k], x[k]+w[k], x[k]+w[k]],  
               [y[k], y[k]+h[k], y[k]+h[k], y[k]], facecolor = ’#D0D0D0’)  
    pylab.text(x[k]+.5*w[k], y[k]+.5*h[k], "%d" %(k+1))  
pylab.axis([-1.0, 26, -1.0, 26])  
pylab.xticks([])  
pylab.yticks([])  
 
pylab.subplot(222)  
Amin = matrix([20., 50., 80., 150., 200.])  
W, H, x, y, w, h =  floorplan(Amin)  
for k in xrange(5):  
    pylab.fill([x[k], x[k], x[k]+w[k], x[k]+w[k]],  
               [y[k], y[k]+h[k], y[k]+h[k], y[k]], ’facecolor = #D0D0D0’)  
    pylab.text(x[k]+.5*w[k], y[k]+.5*h[k], "%d" %(k+1))  
pylab.axis([-1.0, 26, -1.0, 26])  
pylab.xticks([])  
pylab.yticks([])  
 
pylab.subplot(223)  
Amin = matrix([180., 80., 80., 80., 80.])  
W, H, x, y, w, h =  floorplan(Amin)  
for k in xrange(5):  
    pylab.fill([x[k], x[k], x[k]+w[k], x[k]+w[k]],  
               [y[k], y[k]+h[k], y[k]+h[k], y[k]], ’facecolor = #D0D0D0’)  
    pylab.text(x[k]+.5*w[k], y[k]+.5*h[k], "%d" %(k+1))  
pylab.axis([-1.0, 26, -1.0, 26])  
pylab.xticks([])  
pylab.yticks([])  
 
pylab.subplot(224)  
Amin = matrix([20., 150., 20., 200., 110.])  
W, H, x, y, w, h =  floorplan(Amin)  
for k in xrange(5):  
    pylab.fill([x[k], x[k], x[k]+w[k], x[k]+w[k]],  
               [y[k], y[k]+h[k], y[k]+h[k], y[k]], ’facecolor = #D0D0D0’)  
    pylab.text(x[k]+.5*w[k], y[k]+.5*h[k], "%d" %(k+1))  
pylab.axis([-1.0, 26, -1.0, 26])  
pylab.xticks([])  
pylab.yticks([])  
 
pylab.show()

PIC