How does CVX transform SDP to a cone progam for solving?

1

I am interested in understanding how an SDP can be equivalently transformed to a cone program to be solved. There is a comment in these slides from Stephen Boyd that says CVX handles the painful process of carrying out this transformation so the user can simply write the SDP program and CVX transforms to be solved.

However, I am curious about how CVX transforms the problem. If possible, is there any literature that describes the process?

2

You can read Michael Grant’s thesis.

1 Like
4

@mcg do you have any comment on this? I am reading your thesis and understand that it was motivated by automating this kind of transformation step. But is there any part you can point me to that shows how to transform an SDP into a cone program? i.e.

A semidefinite program in inequality form is written as

\begin{array}{ll} \text{minimize} & c^Tx \\ \text{subject to} & x_1 A_1 + \cdots + x_n A_n \preceq B \end{array}

rewritten as a conic program

\begin{array}{ll} \text{minimize} & c^Tx \\ \text{subject to} & Fx + g \preceq_K 0 \end{array}

So if we have set up a problem as a semidefinite program with known A_i,B how can we rewrite it in the conic form?

5

For example Mosek has the concept of a semidefinite variable X\succeq 0 and then the above is simply introducing such a variable X together with the linear equalities X=B-\sum_i x_iA_i. Other solvers may have a different interface, but generally you have some sort of SDP cone and a sequence of n^2 affine expressions which you declare as belonging to that cone. (I’m hiding a lot of implementation nonsense, that is just the main point)

6

@Michal_Adamaszek thanks for the reply! However, the implementation nonsense is what I am interested in! If you have time, please do share more

7

By implementation nonsense I meant that CVX can choose to dualize, or that you only need n(n+1)/2 coordinates because of symmetry rather than the full n^2 etc.

Maybe you should do an example. Suppose for the sake of simplicity that the solver allows you to write Fx+g\in S_n where Fx+g is an affine expression of dimension n^2 and S_n is the convex cone consisting of all vectors \mathrm{vec}(X) as X varies over all symmetric PSD matrices of size n\times n. (Here vec means flattening ie. writing an n\times n matrix as a vector of length n^2 say row after row.) Then

\sum_i x_iA_i\preceq B

will be converted to

\mathrm{vec}(B-\sum_i x_iA_i) \in S_n

For example for n=3 the LMI

x\left[\begin{array}{ccc}3&5&0\\5&0&0\\0&0&1\end{array}\right]+y\left[\begin{array}{ccc}-1&0&0\\0&-1&0\\0&0&-1\end{array}\right]\preceq \left[\begin{array}{ccc}9&8&7\\8&5&4\\7&4&1\end{array}\right]

will be converted to

(9+y-3x,\ 8-5x,\ 7,\ 8-5x,\ 5+y,\ 4,\ 7,\ 4,\ 1+y-x)\in S_3

You can always express the last one in the form A\left[\begin{array}{cc}x\\y\end{array}\right]+b\in S_n for suitable A,b if that is what you’re after. (Essentially A,b consist of -\mathrm{vec}(A_i) and \mathrm{vec}(B) in columns).

1 Like