I've looked into cvxopt and I don't immediately see a way to turn this into problem formulation they support. Is there a free tool I can use to solve SDP below?

Update I got it working following Joachim's suggestion. Needed couple additional details (which are probably obvious to optimization experts), latexized write-up is here

asked 02 Mar '11, 04:01

Yaroslav%20Bulatov's gravatar image

Yaroslav Bul...
4316
accept rate: 0%

edited 03 Mar '11, 11:46


Your problem is specified in the dual form according to CVXOPT's convention.

If you write your problem as

max.    -Tr(Z, e*e')
s.t.    Tr(Z, I) = 1
        Tr(Z, ei*ej') = 0, for all (i,j)in E
        Z >= 0

you are very close to specifying the dual problem in CVXOPT. You only have a single semidefinite variable (N=1). so specify

G^T = [vec(I)^T; vec(e_i1 * e_j1^T)^T; ... ; vec(e_ip * e_jp^T)^T]

in which case you get the problem

max.     -z'*vec(e*e')
s.t.     G^T * z  = (1, 0, ..., 0)^T
         z >= 0.

where z := vec(Z). The later is vectorized form used by most SDP solvers (SeDuMi, SDTP3,...)

You will only be able to solve very moderate size instances using a primal-dual algorithm. If your graph happens to be chordal (or almost chordal), you can solve much larger problems using either a primal or dual method based chordal matrix completion. The following packages implement those ideas and are plugins for CVXOPT:

http://abel.ee.ucla.edu/chompack/

http://abel.ee.ucla.edu/smcp/

link

answered 02 Mar '11, 11:01

Joachim%20Dahl's gravatar image

Joachim Dahl
1163
accept rate: 33%

edited 02 Mar '11, 11:50

thanks, I got it working now

(03 Mar '11, 08:24) Yaroslav Bul...

Wouldn't this work?

dim(s_0) = 0

G_1 = -id
h_1 = 0

(this sets x to the entries of s_1)

c = -e  (e in R^(n^2))

express the two constraints in the matrix A (I suppose E is some fixed set?)

link

answered 02 Mar '11, 07:04

Hans's gravatar image

Hans
1093
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190

Asked: 02 Mar '11, 04:01

Seen: 1,347 times

Last updated: 03 Mar '11, 11:46

OR-Exchange! Your site for questions, answers, and announcements about operations research.