Document Actions

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

$\begin{displaymath} \begin{array}{ll} \mbox{minimize} & c^T x \\ \mbox{subje... ...=0,\ldots,m-1 \\ & G x \preceq h \\ & A x = b. \end{array}\end{displaymath}$

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.

F() returns a tuple (m, x0), where m is the number of nonlinear constraints and x0 is a point in the domain of f. x0 is a dense real matrix of size (n, 1).
F(x), with x a dense real matrix of size (n, 1), returns a tuple (f, Df). f is a dense real matrix of size (m, 1), with f[k] equal to f_k(x). Df is a dense or sparse real matrix of size (m,n) with Df[k,:] equal to the transpose of the gradient $\nabla f_k(x)$ . If x is not in the domain of f, F(x) returns None or a tuple (None,None).
F(x,z), with x a dense real matrix of size (n,1) and z a positive dense real matrix of size (m,1) returns a tuple (f, Df, H). f and Df are defined as above. H is a square dense or sparse real matrix of size (n,n), whose lower triangular part contains the lower triangular part of

$\begin{displaymath} z_0 \nabla^2f_0(x) + z_1 \nabla^2f_1(x) + \cdots + z_{m-1} \nabla^2f_{m-1}(x). \end{displaymath}$

If F is called with two arguments, it can be assumed that x is in the domain of f.

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

cpl() requires that the problem is solvable and that

$\begin{displaymath} \Rank(A) = p, \qquad \Rank\left(\left[\begin{array}{cccccc}... ...cdots \nabla f_{m-1}(x) & G^T \end{array}\right]\right) = n, \end{displaymath}$

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:

$\begin{displaymath} \begin{array}{ll} \mbox{minimize} & W + H \\ \mbox{subjec... ...gamma \leq w_k \leq \gamma h_k, \quad k=1,\ldots,5. \end{array}\end{displaymath}$

This problem has 22 variables

$\begin{displaymath} W, \qquad H, \qquad x\in{\mbox{\bf R}}^5, \qquad y\in{\mbox{... ...}^5, \qquad w\in{\mbox{\bf R}}^5, \qquad h\in{\mbox{\bf R}}^5, \end{displaymath}$

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

$\includegraphics[width=15cm]{figures/floorplan.eps}$

CVXOPT

Sections

Personal tools

Document Actions

9.2 Problems with Linear Objectives