7.6 Semidefinite Programming

The function sdp() is a simple interface to conelp() for cone programs with no second-order cone constraints. It also provides the option of using the DSDP semidefinite programming solver.

sdp(c[, Gl, hl[, Gs, hs[, A, b[, solver[, primalstart[, dualstart]]]]]])

Solves the pair of primal and dual semidefinite programs

minimize   cTx                                          maximize  - hT z - ∑N  tr(h z )- bTy
subject to G x +s  = h                                             T0 0 ∑N  k=1 T  k k      T
           G0x + 0vec(s0) = vec(h ), k = 1,...,N          subject to G0z0 +   k=1 Gk vec(zk) +A  y+ c = 0
           Akx = b     k        k                                  z0 ≽ 0
           s ≽ 0                                                  zk ≽ 0, k = 1,...,N.
           s0≽ 0,  k = 1,...,N
            k

The inequalities

s0 ≽ 0,   z0 ≽ 0

are componentwise vector inequalities. The other inequalities are matrix inequalities (i.e., the require the lefthand sides to be positive semidefinite). We use the notation vec(z) to denote a symmetric matrix z stored in column major order as a column vector.

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.

Gs and hs are lists of length N that specify the linear matrix inequality constraints. Gs is a list of N dense or sparse real matrices G1, …, GM. The columns of these matrices can be interpreted as symmetric matrices stored in column major order, using the BLAS ’L’-type storage (i.e., only the entries corresponding to lower triangular positions are accessed). hs is a list of N dense symmetric matrices h1, …, hN. Only the lower triangular elements of these matrices are accessed. The default values for Gs and hs are empty lists.

A is a 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 DSDP5 (solver=’dsdp’); see section 7.8. With the ’dsdp’ option the code does not accept problems with equality constraints.

The optional argument primalstart is a dictionary with keys ’x’, ’sl’, and ’ss’, used as an optional primal starting point. primalstart[’x’] and primalstart[’sl’] are single-column dense matrices with the initial values of x and s0; primalstart[’ss’] is a list of square matrices with the initial values of s1, …, sN. The initial values must satisfy the inequalities in the primal problem strictly, but not necessarily the equality constraints.

dualstart is a dictionary with keys ’y’, ’zl’, ’zs’, used as an optional dual starting point. dualstart[’y’] and dualstart[’zl’] are single-column dense matrices with the initial values of y and z0. dualstart[’zs’] is a list of square matrices with the initial values of z1, …, zN. These values must satisfy the dual inequalities strictly, but not necessarily the equality constraint.

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

sdp() returns a dictionary that includes entries with keys ’status’, ’x’, ’sl’, ’ss’, ’y’, ’zl’, ’ss’. The ’sl’ and ’zl’ fields are matrices with the primal slacks and dual variables associated with the componentwise linear inequalities. The ’ss’ and ’zs’ fields are lists with the primal slacks and dual variables associated with the second-order cone inequalities. The other entries in the output dictionary have the same meaning as in the output of conelp().

We illustrate the calling sequence with a small example.

minimize   x1 -[ x2 +x3   ]    [           ]     [        ]   [        ]
subject to x1   - 7 - 11  + x2    7   - 18 + x3   - 2 - 8  ≼   33  - 9
            ⌊ - 11   3     ⌋   - 1⌊8   8         ⌋- 8  1⌊       - 9 26  ⌋   ⌊            ⌋
              - 21  - 11 0         0    10   16          - 5   2  - 17       14   9  40
          x1⌈ - 11  10   8 ⌉ + x2⌈ 10  - 10 - 10⌉ + x3⌈   2   - 6  - 7 ⌉ ≼ ⌈ 9  91  10 ⌉
                0    8   5         16  - 10  3           - 17  8   6         40  10  15

>>> from cvxopt import matrix, solvers  
>>> c = matrix([1.,-1.,1.])  
>>> G = [ matrix([[-7., -11., -11., 3.],  
                  [ 7., -18., -18., 8.],  
                  [-2.,  -8.,  -8., 1.]]) ]  
>>> G += [ matrix([[-21., -11.,   0., -11.,  10.,   8.,   0.,   8., 5.],  
                   [  0.,  10.,  16.,  10., -10., -10.,  16., -10., 3.],  
                   [ -5.,   2., -17.,   2.,  -6.,   8., -17.,  -7., 6.]]) ]  
>>> h = [ matrix([[33., -9.], [-9., 26.]]) ]  
>>> h += [ matrix([[14., 9., 40.], [9., 91., 10.], [40., 10., 15.]]) ]  
>>> sol = solvers.sdp(c, Gs=G, hs=h)  
>>> print sol[’x’]  
[-3.68e-01]  
[ 1.90e+00]  
[-8.88e-01]  
>>> print sol[’zs’][0]  
[ 3.96e-03 -4.34e-03]  
[-4.34e-03  4.75e-03]  
>>> print sol[’zs’][1]  
[ 5.58e-02 -2.41e-03  2.42e-02]  
[-2.41e-03  1.04e-04 -1.05e-03]  
[ 2.42e-02 -1.05e-03  1.05e-02]

Only the entries in Gs and hs that correspond to lower triangular entries need to be provided, so in the example h and G may also be defined as follows.

>>> G = [ matrix([[-7., -11., 0., 3.],  
                  [ 7., -18., 0., 8.],  
                  [-2.,  -8., 0., 1.]]) ]  
>>> G += [ matrix([[-21., -11.,   0., 0.,  10.,   8., 0., 0., 5.],  
                   [  0.,  10.,  16., 0., -10., -10., 0., 0., 3.],  
                   [ -5.,   2., -17., 0.,  -6.,   8., 0., 0., 6.]]) ]  
>>> h = [ matrix([[33., -9.], [0., 26.]]) ]  
>>> h += [ matrix([[14., 9., 40.], [0., 91., 10.], [0., 0., 15.]]) ]