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: , ,

One Response to “Second Order Cone Programming with CVXOPT”

  1. steve Says:

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: