Document Actions

8.1 Linear Cone Programs

conelp(c, G, h[, dims[, A, b[, primalstart[, dualstart[, kktsolver]]]]])

Solves a pair of primal and dual cone programs

$\begin{displaymath} \begin{array}[t]{ll} \mbox{minimize} & c^T x \\ \mbox{su... ...ct to} & G^T z + A^T y + c = 0 \\ & z \succeq 0. \end{array}\end{displaymath}$

(8.1)

The primal variables are x and the slack variable s. The dual variables are y and z. The inequalities are interpreted as $s \in C$ , $z\in C$ , where C is a cone defined as a Cartesian product of a nonnegative orthant, a number of second-order cones, and a number of positive semidefinite cones:

$\begin{displaymath} C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times \cdots \times C_{M+N} \end{displaymath}$

with

$\begin{displaymath} C_0 = \{ u \in {\mbox{\bf R}}^l \;\vert \; u_k \geq 0, \; ... ... u \in {\mbox{\bf S}}^{t_k}_+ \right\}, \quad k=0,\ldots,N-1. \end{displaymath}$

In this definition, $\mathop{\mathbf{vec}}(u)$ denotes a symmetric matrix u stored as a vector in column major order. The structure of C is specified by dims. This argument is a dictionary with three fields.

dims['l']:: l, the dimension of the nonnegative orthant (a nonnegative integer).
dims['q']:: $[r_0, \ldots, r_{M-1}]$ , a list with the dimensions of the second-order cones (positive integers).
dims['s']:: $[t_0, \ldots, t_{N-1}]$ , a list with the dimensions of the positive semidefinite cones (nonnegative integers).

The default value of dims is {'l': G.size[0], 'q': [], 's': []}, i.e., by default the inequality is interpreted as a componentwise vector inequality.

The arguments c, h and b are real single-column dense matrices. G and A are real dense or sparse matrices. The number of rows of G and h is equal to

$\begin{displaymath} K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2. \end{displaymath}$

The columns of G and h are vectors in

$\begin{displaymath} {\mbox{\bf R}}^l \times {\mbox{\bf R}}^{r_0} \times \cdots \... ... R}}^{t_0^2} \times \cdots \times {\mbox{\bf R}}^{t_{N-1}^2}, \end{displaymath}$

where the last N components represent symmetric matrices stored in column major order. The strictly upper triangular entries of these matrices are not accessed (i.e., the symmetric matrices are stored in the 'L'-type column major order used in the blas and lapack modules). The default values for A and b are matrices with zero rows, meaning that there are no equality constraints.

primalstart is a dictionary with keys 'x' and 's', used as an optional primal starting point. primalstart['x'] and primalstart['s'] are real dense matrices of size (n,1) and (K,1), respectively, where n is the length of c. The vector primalstart['s'] must be strictly positive with respect to the cone C.

dualstart is a dictionary with keys 'y' and 'z', used as an optional dual starting point. dualstart['y'] and dualstart['z'] are real dense matrices of size (p,1) and (K,1), respectively, where p is the number of rows in A. The vector dualstart['s'] must be strictly positive with respect to the cone C.

The role of the optional argument kktsolver is explained in section 8.7.

conelp() returns a dictionary with keys 'status', 'x', 's', 'y', 'z'. The 'status' field is a string with possible values 'optimal', 'primal infeasible', 'dual infeasible' and 'unknown'. The meaning of the other fields depends on the value of 'status'.

'optimal'

In this case the 'x', 's', 'y' and 'z' entries contain the primal and dual solutions, which approximately satisfy

$\begin{displaymath} Gx + s = h, \qquad Ax=b, \qquad G^T z + A^T y + c = 0, \qquad s \succeq 0, \qquad z \succeq 0, \qquad s^T z =0. \end{displaymath}$

'primal infeasible'

The 'x' and 's' entries are None, and the 'y', 'z' entries provide an approximate certificate of infeasibility, i.e., vectors that approximately satisfy

$\begin{displaymath} G^T z + A^T y = 0, \qquad h^T z + b^T y = -1, \qquad z \succeq 0. \end{displaymath}$

'dual infeasible'

The 'y' and 'z' entries are None, and the 'x' and 's' entries contain an approximate certificate of dual infeasibility

$\begin{displaymath} Gx + s = 0, \qquad Ax=0, \qquad c^T x = -1, \qquad s \succeq 0. \end{displaymath}$

'unknown'

The 'x', 's', 'y', 'z' entries are None.

It is required that

$\begin{displaymath} \Rank(A) = p, \qquad \Rank(\left[\begin{array}{c} G \\ A \end{array}\right]) = n, \end{displaymath}$

where p is the number or rows of A and n is the number of columns of G and A.

As an example we solve the problem

$\begin{displaymath} \begin{array}{ll} \mbox{minimize} & -6x_1 - 4x_2 - 5x_3 \\ *... ...0 & 99 & 23 \\ -19 & 23 & 10 \end{array}\right]. \end{array} \end{displaymath}$

>>> from cvxopt.base import matrix
>>> from cvxopt import solvers 
>>> c = matrix([-6., -4., -5.])
>>> G = matrix([[ 16., 7.,  24.,  -8.,   8.,  -1.,  0., -1.,  0.,  0.,   7.,  -5.,   1.,  -5.,   1.,  -7.,   1.,   -7.,  -4.], 
                [-14., 2.,   7., -13., -18.,   3.,  0.,  0., -1.,  0.,   3.,  13.,  -6.,  13.,  12., -10.,  -6.,  -10., -28.],
                [  5., 0., -15.,  12.,  -6.,  17.,  0.,  0.,  0., -1.,   9.,   6.,  -6.,   6.,  -7.,  -7.,  -6.,   -7., -11.]])
>>> h = matrix( [ -3., 5.,  12.,  -2., -14., -13., 10.,  0.,  0.,  0.,  68., -30., -19., -30.,  99.,  23., -19.,   23.,  10.] )
>>> dims = {'l': 2, 'q': [4, 4], 's': [3]}
>>> sol = solvers.conelp(c, G, h, dims)
>>> sol['status']
'optimal'
>>> print sol['x']
[-1.22e+00]
[ 9.66e-02]
[ 3.58e+00]
>>> print sol['z']
[ 9.30e-02]
[ 2.04e-08]
[ 2.35e-01]
[ 1.33e-01]
[-4.74e-02]
[ 1.88e-01]
[ 2.79e-08]
[ 1.85e-09]
[-6.32e-10]
[-7.59e-09]
[ 1.26e-01]
[ 8.78e-02]
[-8.67e-02]
[ 8.78e-02]
[ 6.13e-02]
[-6.06e-02]
[-8.67e-02]
[-6.06e-02]
[ 5.98e-02]

Only the entries of G and h defining the lower triangular portions of the coefficients in the linear matrix inequalities are accessed. We obtain the same result if we define G and h as below.

>>> G = matrix([[ 16., 7.,  24.,  -8.,   8.,  -1.,  0., -1.,  0.,  0.,   7.,  -5.,   1.,  0.,   1.,  -7.,  0.,  0.,  -4.], 
                [-14., 2.,   7., -13., -18.,   3.,  0.,  0., -1.,  0.,   3.,  13.,  -6.,  0.,  12., -10.,  0.,  0., -28.],
                [  5., 0., -15.,  12.,  -6.,  17.,  0.,  0.,  0., -1.,   9.,   6.,  -6.,  0.,  -7.,  -7.,  0.,  0., -11.]])
>>> h = matrix( [ -3., 5.,  12.,  -2., -14., -13., 10.,  0.,  0.,  0.,  68., -30., -19.,  0.,  99.,  23.,  0.,  0.,  10.] )

CVXOPT

Sections

Personal tools

Document Actions

8.1 Linear Cone Programs