8.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∑- 12
K = l+     rk +    tk.
        k=0     k=0

The columns of G and h are vectors in

                         2         2
Rl × Rr0 × ⋅⋅⋅× RrM -1 × Rt0 × ⋅⋅⋅× RtN-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 8.7.

coneqp() returns a dictionary with 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’
The ’x’, ’s’, ’y’, ’z’ entries are None.

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 base, solvers  
>>> from cvxopt.base import matrix  
>>> 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]