8.5 Second-Order Cone Programming

The function socp() is a simpler interface to conelp() for cone programs with no linear matrix inequality constraints.

socp(c[, Gl, hl[, Gq, hq[, A, b[, solver[, primalstart[, dualstart]]]]]])

Solves the pair of primal and dual second-order cone programs

minimize   cTx                                maximize  - ∑M   hT z - bTy
subject to G x + s = h ,  k = 0,...,M                    ∑M  k=0Tk k   T
           Akx = bk    k                       subject to    k=0G kzk + A y+ c = 0
           s ≽ 0                                        z0 ≽ 0
           s0 ≥ ∥s ∥ ,  k = 1,...,M                      zk0 ≥ ∥zk1∥2, k = 1,...,M.
            k0     k12

The inequalities

s0 ≽ 0,   z0 ≽ 0

are componentwise vector inequalities. In the other inequalities, it is assumed that the variables are partitioned as

                   rk-1                        rk-1
sk = (sk0,sk1) ∈ R×R    ,    zk = (zk0,zk1) ∈ R ×R  ,    k = 1,...,M.

The input argument c is a real single-column dense matrix. The arguments Gl and hl are the coefficient matrix G0 and the righthand side h0 of the componentwise inequalities. Gl is a real dense or sparse matrix; hl is a real single-column dense matrix. The default values for Gl and hl are matrices with zero rows.

The argument Gq is a list of M dense or sparse matrices G1, …, GM. The argument hq is a list of M dense single-column matrices h1, …, hM. The elements of Gq and hq must have at least one row. The default values of Gq and hq are empty lists.

A is dense or sparse matrix and b is a single-column dense matrix. The default values for A and b are matrices with zero rows.

The solver argument is used to choose between two solvers: the CVXOPT conelp() solver (used when solver is absent or equal to None) and the external solver MOSEK (solver=’mosek’); see section 8.8. With the ’mosek’ option the code does not accept problems with equality constraints.

primalstart and dualstart are dictionaries with optional primal, respectively, dual starting points. primalstart has elements ’x’, ’sl’, ’sq’. primalstart[’x’] and primalstart[’sl’] are single-column dense matrices with the initial values of x and s0; primalstart[’sq’] is a list of single-column matrices with the initial values of s1, …, sM. The initial values must satisfy the inequalities in the primal problem strictly, but not necessarily the equality constraints.

dualstart has elements ’y’, ’zl’, ’zq’. dualstart[’y’] and dualstart[’zl’] are single-column dense matrices with the initial values of y and z0. dualstart[’zq’] is a list of single-column matrices with the initial values of z1, …, zM. These values must satisfy the dual inequalities strictly, but not necessarily the equality constraint.

The arguments primalstart and dualstart are ignored when the MOSEK solver is used.

socp() returns a dictionary with keys ’status’, ’x’, ’sl’, ’sq’, ’y’, ’zl’, ’zq’. The meaning is similar to the output of conelp(). The ’sl’ and ’zl’ fields are matrices with the primal slacks and dual variables associated with the componentwise linear inequalities. The ’sq’ and ’zq’ fields are lists with the primal slacks and dual variables associated with the second-order cone inequalities.

As an example, we solve the second-order cone program

minimize   - 2x1 + x2 + 5x3
          ∥∥[                      ]∥∥
subject to ∥∥  - 13x1 + 3x2 + 5x3 - 3 ∥∥ ≤ - 12x1 - 6x2 + 5x3 - 12
          ∥⌊ - 12x1 + 12x2 - 6x3 - 2⌋ ∥2
          ∥∥    - 3x1 + 6x2 + 2x3   ∥∥
          ∥∥⌈   x1 + 9x2 +2x3 + 3 ⌉ ∥∥ ≤ - 3x1 + 6x2 - 10x3 + 27.
          ∥  - x1 - 19x2 + 3x3 - 42 ∥2

>>> from cvxopt.base import matrix  
>>> from cvxopt import solvers  
>>> c = matrix([-2., 1., 5.])  
>>> G = [ matrix( [[12., 13., 12.], [6., -3., -12.], [-5., -5., 6.]] ) ]  
>>> G += [ matrix( [[3., 3., -1., 1.], [-6., -6., -9., 19.], [10., -2., -2., -3.]] ) ]  
>>> h = [ matrix( [-12., -3., -2.] ),  matrix( [27., 0., 3., -42.] ) ]  
>>> sol = solvers.socp(c, Gq = G, hq = h)  
>>> sol[’status’]  
optimal  
>>> print sol[’x’]  
[-5.02e+00]  
[-5.77e+00]  
[-8.52e+00]  
>>> print sol[’zq’][0]  
[ 1.34e+00]  
[-7.63e-02]  
[-1.34e+00]  
>>> print sol[’zq’][1]  
[ 1.02e+00]  
[ 4.02e-01]  
[ 7.80e-01]  
[-5.17e-01]