7.2 Quadratic Cone Programs

coneqp(P, q[, G, h[, dims[, A, b[, initvals[, kktsolver]]]]])

Solves a pair of primal and dual quadratic cone programs

minimize   (1∕2)xTP x+ qTx                  maximize  - (1∕2)(q + GTz + ATy)TP †(q +GT z +AT y)- hTz - bTy
subject to Gx + s = h                      subject to q+ GT z + AT y ∈ range(P )
           Ax = b                                    z ≽ 0.
           s ≽ 0

The primal variables are x and the slack variable s. The dual variables are y and z. The inequalities are interpreted as s ∈ C, z ∈ 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:

C = C0 × C1 × ⋅⋅⋅× CM × CM+1 × ⋅⋅⋅× CM+N

with

                                                                                                     {             }
C0 = {u ∈ Rl | uk ≥ 0, k = 1,...,l}, Ck+1 = {(u0,u1) ∈ R×Rrk -1 | u0 ≥ ∥u1∥2}, k = 0,...,M - 1, Ck+M+1 = vec(u) | u ∈ Stk+ , k = 0,...,N - 1.

In this definition, 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’]:
[r0,,rM-1], a list with the dimensions of the second-order cones (positive integers).
dims[’s’]:
[t0,,tN-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.

P is a square dense or sparse real matrix, representing a positive semidefinite symmetric matrix in ’L’ storage, i.e., only the lower triangular part of P is referenced. q is a real single-column dense matrix.

The arguments 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

       M∑-1    N∑- 1
K = l+     rk +    t2k.
        k=0     k=0

The columns of G and h are vectors in

Rl × Rr0 × ⋅⋅⋅× RrM -1 × Rt20 × ⋅⋅⋅× Rt2N-1,

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 G, h, A and b are matrices with zero rows, meaning that there are no inequality or equality constraints.

initvals is a dictionary with keys ’x’, ’s’, ’y’, ’z’ used as an optional starting point. The vectors initvals[’s’] and initvals[’z’] must be strictly positive with respect to the cone C. If the argument initvals or any the four entries in it are missing, default starting points are used for the corresponding variables.

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

coneqp() returns a dictionary that contains the result and information about the accuracy of the solution. The most important fields have keys ’status’, ’x’, ’s’, ’y’, ’z’. The ’status’ field is a string with possible values ’optimal’ and ’unknown’.

’optimal’
In this case the ’x’, ’s’, ’y’ and ’z’ entries contain primal and dual solutions, which approximately satisfy
Gx+s = h,    Ax = b,    Px+GT z+AT y+c = 0,    s ≽ 0,   z ≽ 0,   sTz = 0.

’unknown’
This indicates that the algorithm terminated early due to numerical difficulties or because the maximum number of iterations was reached. The ’x’, ’s’, ’y’, ’z’ entries contain the iterates when the algorithm terminated.

The other entries in the output dictionary summarize the accuracy with which the optimality conditions are satisfied. The fields ’primal objective’, ’dual objective’, and ’gap’ give the primal objective cTx, the dual objective calculated as

(1∕2)xTPx + qTx+ zT(Gx - h)+ yT(Ax - b)

and the gap sTz. The field ’relative gap’ is the relative gap, defined as

------sTz------                          ----sTz-----
- primal objective if primal objective < 0,   dual objective if dual objective > 0,

and None otherwise. The fields ’primal infeasibility’ and ’dual infeasibility’ are the residuals in the primal and dual equality constraints, defined as

max{∥Gx-+-s--h∥-,-∥Ax---b∥-},    ∥Px-+-GTz-+-ATy-+-q∥,
     max{1,∥h∥}  max{1,∥b∥}           max{1,∥q∥}

respectively.

It is required that the problem is solvable and that

                    ⌊ P ⌋
rank(A) = p,   rank(⌈ G ⌉ ) = n,
                      A

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 a constrained least-squares problem

minimize   ∥Ax - b∥22
subject to x ≽ 0
           ∥x ∥2 ≤ 1

with

    ⌊                  ⌋        ⌊      ⌋
    |   0.3   0.6  - 0.3 |       |   1.5 |
    || - 0.4   1.2   0.0 ||        ||   0.0 ||
A = |⌈ - 0.2  - 1.7  0.6 |⌉,    b = |⌈ - 1.2 |⌉ .
      - 0.4   0.3  - 1.2           - 0.7
        1.3  - 0.3 - 2.0             0.0

>>> from cvxopt import matrix, solvers  
>>> A = matrix([ [ .3, -.4,  -.2,  -.4,  1.3 ],  
                 [ .6, 1.2, -1.7,   .3,  -.3 ],  
                 [-.3,  .0,   .6, -1.2, -2.0 ] ])  
>>> b = matrix([ 1.5, .0, -1.2, -.7, .0])  
>>> m, n = A.size  
>>> I = matrix(0.0, (n,n))  
>>> I[::n+1] = 1.0  
>>> G = matrix([-I, matrix(0.0, (1,n)), I])  
>>> h = matrix(n*[0.0] + [1.0] + n*[0.0])  
>>> dims = {’l’: n, ’q’: [n+1], ’s’: []}  
>>> x = solvers.coneqp(A.T*A, -A.T*b, G, h, dims)[’x’]  
>>> print x  
[ 7.26e-01]  
[ 6.18e-01]  
[ 3.03e-01]