«
»

Second Order Cone Programming with CVXOPT

CVXOPT is a convex optimization package for Python that includes a Second Order Cone Programming (SOCP) solver.  The SOCP solver takes a set of matrices that describe the SOCP problem, but these matrices are different than the matrices usually used to express the SOCP problem.  This post walks through the simple algebra steps to find relationship between the two formulations of the SOCP problem.

The SOCP problem as described in Wikipedia or the excellent free book Convex Optimization by Boyd and Vandenberghe includes the constraint:

\| A x + b \|_2 \leq c^T x + d

We can rewrite this to be:

\begin{bmatrix} c^T \\ A \end{bmatrix} + \begin{bmatrix} d \\ b \end{bmatrix} = \begin{bmatrix} s_0 \\ s_1 \end{bmatrix}, \qquad s_0 \geq \| s_1 \|_2

Now to rearrange into the format expected by the CVXOPT solver:

- \begin{bmatrix} c^T \\ A \end{bmatrix} + \begin{bmatrix} s_0 \\ s_1 \end{bmatrix} = \begin{bmatrix} d \\ b \end{bmatrix}

And then see the relationship between the two formulations of the SOCP problem are equivalent:

G= \begin{bmatrix} -c^T \\ -A \end{bmatrix} and h = \begin{bmatrix}d \\ b \end{bmatrix}

Tags: , ,

This entry was posted on December 18, 2010 at 8:05 pm and is filed under research. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

One Response to “Second Order Cone Programming with CVXOPT”

  1. steve Says:
    October 14, 2014 at 6:15 am | Reply

    Thanks for this note. I think you are missing an x in the 1st and second equations: e.g. the matrix [ c^T ; A ] should be multiplied by x for this to make sense

Leave a comment