Writing a Linear program as a semi definite program

In summary, the conversation is about the comparison between LPs and SDPs. The person is trying to convert an LP into SDP form, as they have solved an advanced SDP using an online solver and can solve basic and advanced LPs on their computer. They are also trying to reverse engineer an SDP into an LP, but this may not always be possible. Some methods and tools for converting between LPs and SDPs are mentioned,
  • #1
DKOli
8
0
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
 
Mathematics news on Phys.org
  • #2
DKOli said:
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:

[itex] X = \begin{pmatrix} x&0&0&0 \\ 0&y&0&0 \\ 0&0&s&0 \\ 0&0&0&t \end{pmatrix}[/itex]

[itex] C = \begin{pmatrix} 3&0&0&0 \\ 0&4&0&0 \\ 0&0&0&0 \\ 0&0&0&0 \end{pmatrix}[/itex]

[itex] A_1 = \begin{pmatrix} 1&0&0&0 \\ 0&2&0&0 \\ 0&0&1&0 \\ 0&0&0&0 \end{pmatrix}[/itex]

[itex] b_1 = 4 [/itex]

[itex] A_2 = \begin{pmatrix} 1&0&0&0 \\ 0&0&0&0 \\ 0&0&0&0 \\ 0&0&0&1 \end{pmatrix}[/itex]

[itex] b_2 = 1 [/itex]
 
  • #3
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
 
  • #4
lofberg said:
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.
 
  • #5
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.
 
  • #6
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.
 
  • #7
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
 

1. What is a linear program?

A linear program is a mathematical optimization model where the objective is to maximize or minimize a linear function subject to a set of linear constraints. The variables in the linear function and constraints are all continuous and the objective and constraints are all linear functions.

2. What is a semi definite program?

A semi definite program is a mathematical optimization model where the objective is to maximize or minimize a quadratic function subject to a set of linear constraints. The variables in the quadratic function and constraints can be both continuous and discrete, and the objective and constraints can be both linear and quadratic functions.

3. How do you convert a linear program into a semi definite program?

To convert a linear program into a semi definite program, the linear objective function needs to be transformed into a quadratic function by adding slack variables. The constraints also need to be transformed into semi definite constraints by squaring the linear expressions. The resulting semi definite program can then be solved using algorithms specifically designed for semi definite programming.

4. What are the advantages of using a semi definite program over a linear program?

Semi definite programs allow for more flexibility in the objective function and constraints, as they can include both linear and quadratic terms. This can lead to more accurate and efficient solutions for certain types of optimization problems. Additionally, semi definite programs have faster algorithms for solving compared to linear programs.

5. Are there any real-life applications of semi definite programming?

Yes, semi definite programming has various real-life applications in fields such as engineering, economics, and computer science. Some examples include portfolio optimization in finance, sensor network localization in engineering, and graph partitioning in computer science. Semi definite programming is also used in machine learning for solving certain types of optimization problems.

Similar threads

  • General Math
Replies
1
Views
3K
  • Programming and Computer Science
Replies
2
Views
1K
  • General Math
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
465
Replies
4
Views
2K
  • Math POTW for University Students
Replies
1
Views
2K
  • Calculus
Replies
2
Views
1K
Replies
17
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
4K
Back
Top