Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Writing a Linear program as a semi definite program

  1. Nov 9, 2011 #1
    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
     
  2. jcsd
  3. Nov 9, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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]
     
  4. Nov 10, 2011 #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 dissapeared 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
     
  5. Nov 10, 2011 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  6. Nov 10, 2011 #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 thats 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 im not actually solving the dual and there are so many different ways to write it so I didnt bother.
     
  7. Nov 11, 2011 #6

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  8. Nov 11, 2011 #7
    Im in a rush and dont wanna 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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Writing a Linear program as a semi definite program
  1. Linear programming (Replies: 1)

Loading...