Writing a Linear program as a semi definite program

[DKOli]

I am comparing LP's and SDP's and have come across a lot of papers where they show all of the differences, but I am trying to put an lp is sdp form. The reason being I have solved an advanced sdp using an online solver and can solve basic/advanced lps on my pc, but I now want to take a lp and show that it can be solved using sdp (as lp is just a special case of sdp).

Start with the simple LP: min: 3x + 4y ;

Constraints: 3x - 4y <= 12;
x + 2y >= 4;
y >= 0;
x >= 1

How would this look as an sdp in the form:

min 3x + 4y
x=f1x + f2y -f0
x>=0

f0, f1, f2 = ?,?,?

---
Also how would I reverse engineer an sdp into an lp:

Example:

min 10x1+20x2

st X=F1x1+F2x2-F0

X >= 0

F0=[1 0 0 0
0 2 0 0
0 0 3 0
0 0 0 4]

F1=[1 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0]

F2=[0 0 0 0
0 1 0 0
0 0 5 2
0 0 2 6]

What would my constraints for the lp be? (I know there may not be feasible solution for this sdp in lp form).

Thanks in advance, Oli

 

[Stephen Tashi]

Start with the simple LP: min: 3x + 4y ;

Constraints: 3x - 4y <= 12;
x + 2y >= 4;
y >= 0;
x >= 1

I'm not an expert on this, but I can't resist trying.

Trying to fit the form given in the current Wikipedia article http:\\en.wikipedia.org/wiki/Semidefinite_programming:

X = \begin{pmatrix} x&amp;0&amp;0&amp;0 \\ 0&amp;y&amp;0&amp;0 \\ 0&amp;0&amp;s&amp;0 \\ 0&amp;0&amp;0&amp;t \end{pmatrix}

C = \begin{pmatrix} 3&amp;0&amp;0&amp;0 \\ 0&amp;4&amp;0&amp;0 \\ 0&amp;0&amp;0&amp;0 \\ 0&amp;0&amp;0&amp;0 \end{pmatrix}

A_1 = \begin{pmatrix} 1&amp;0&amp;0&amp;0 \\ 0&amp;2&amp;0&amp;0 \\ 0&amp;0&amp;1&amp;0 \\ 0&amp;0&amp;0&amp;0 \end{pmatrix}

b_1 = 4

A_2 = \begin{pmatrix} 1&amp;0&amp;0&amp;0 \\ 0&amp;0&amp;0&amp;0 \\ 0&amp;0&amp;0&amp;0 \\ 0&amp;0&amp;0&amp;1 \end{pmatrix}

b_2 = 1

 

[lofberg]

As Stephen writes, LP to SDP is trivial, just put the constraints on the diagonal (here done in primal space, an alternative is to parameterize the dual SDP). The SDP to LP is typically impossible, unless the SDP constraint is diagonal (or can be transformed to diagonal). If it would be posssible generically, we would never use semidefinite programming. You particular example is most likely not possible, due to the 2x2 block. Basically, you have to be able to perform a simultaneuous diagonalization of all Fi.

BTW, the SDP model by Stephen is not correct. For instance, the number 12 has disappeared and there should be negative terms in data

Here is a dual parameterization

max -3x-4y

s.t diagonal(12-3x+4y,-4+x+2y,y,x-1) positive semidefinite

i.e. in standard form

max b'*z

s.t C-A1*z(1)-A2*z(2) positive semidefinite

where C = diagonal(12,-4,0,-1)
A1 = diagonal(-3,1,0,1)
A2 = diagonal(4,2,1,0)

In practice, you never do this manually, you use a modelling tool such as YALMIP.

cheers
johan

 

[Stephen Tashi]

BTW, the SDP model by Stephen is not correct. For instance, the number 12 has disappeared and there should be negative terms in data

Oh, I see. To follow what the Wikipedia calls the primal, I should have done a minimization and I forgot all about the very first constraint. I'd need yet another slack variable, say u.

 

[DKOli]

So my primal should be:
min 3x + 4y

x=A1 x + A2 y - c >= 0

c= diag(-12, 4, 0, 1)

A1= diag(-3, 1, 0, 1)

A2= diag(4, 2, 1, 0)

I confirmed this with my lecturer. I then showed him the dual you gave but he said it was wrong. Didnt really go into it much but he said to start the objective function should still be 3x + 4y even if its max.

He wasnt sure of the form you used and said just simply do the dual of the lp and then transform it into an sdp because that's easier. You end up with z1,z2,z3,z4 but can cancel z3 and z4 as they are simply diag(1 0) and diag(0 1) but I am not actually solving the dual and there are so many different ways to write it so I didnt bother.

 

[Stephen Tashi]

DKOli,

Tell me the definition of a Semi-Definite Program that your class uses. I'm trying to relate how you do things to the definition given in the Wikipedia article.

 

[DKOli]

Im in a rush and don't want to fool about with symbols.

Google semi definite programs and look at a few of the papers.

its the one that uses f(x)>=0 where fx= f0 + sum(xiFi)

in relation to mine, the Fi's are Ai's and f0 is the b's.

Its so i could solve the simple sdp using sdpa online solver.

Heres the quick guide:
File Format:

The file consists of six sections:

1. Comments. The file can begin with arbitrarily many lines of comments.
Each line of comments must begin with '"' or '*'.

2. The first line after the comments contains m, the number of constraint
matrices. Additional text on this line after m is ignored.

3. The second line after the comments contains nblocks, the number of
blocks in the block diagonal structure of the matrices. Additional text
on this line after nblocks is ignored.

4. The third line after the comments contains a vector of numbers that
give the sizes of the individual blocks. The special characters
',', '(', ')', '{', and '}' can be used as punctuation and are ignored.
Negative numbers may be used to indicate that a block is actually a diagonal
submatrix. Thus a block size of "-5" indicates a 5 by 5 block in which
only the diagonal elements are nonzero.

5. The fourth line after the comments contains the objective function
vector c.

6. The remaining lines of the file contain entries in the constraint
matrices, with one entry per line. The format for each line is

<matno> <blkno> <i> <j> <entry>

Here <matno> is the number of the matrix to which this entry belongs,
<blkno> specifies the block within this matrix, <i> and <j> specify a
location within the block, and <entry> gives the value of the entry in
the matrix. Note that since all matrices are assumed to be symmetric,
only entries in the upper triangle of a matrix are given.

Example:

min 10x1+20x2

st X=F1x1+F2x2-F0

X >= 0

where


F0=[1 0 0 0
0 2 0 0
0 0 3 0
0 0 0 4]

F1=[1 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0]

F2=[0 0 0 0
0 1 0 0
0 0 5 2
0 0 2 6]


In SDPA sparse format, this problem can be written as:

"A sample problem.
2 =mdim
2 =nblocks
{2, 2}
10.0 20.0
0 1 1 1 1.0
0 1 2 2 2.0
0 2 1 1 3.0
0 2 2 2 4.0
1 1 1 1 1.0
1 1 2 2 1.0
2 1 2 2 1.0
2 2 1 1 5.0
2 2 1 2 2.0
2 2 2 2 6.0

for mine it became:

2
2
2 2
3.0 4.0
0 1 1 1 -12.0
0 1 2 2 4.0
0 2 2 2 1.0
1 1 1 1 -3.0
1 1 2 2 1.0
1 2 2 2 1.0
2 1 1 1 4.0
2 1 2 2 2.0
2 2 1 1 1.0