On the dual form?

[Karl]

Hi, all,

I am trying to use LogdetPPA to solve a large-scale problem. As mentioned by the yalmip Wiki, "Please note that if you intend to solve really large problems via YALMIP, it is crucial that you pose them in the dual form."

 

But I can NOT ensure what form is the dual form referred in the above. Actually, in the Wiki page of semidefinite programming (http://en.wikipedia.org/wiki/Semidefinite_programming), the Dual SDP (D-SDP) is defined by an equivalent form of the default yalmip form (I suppose that the default yalmip form is the first model in this page: http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.AutomaticDualization). Hence it seems that yalmip uses the term "dual form" in a sense different with Wiki? My question is: If I want to use LogdetPPA, whether I need to dualize my model which is oringally represented by a Wiki D-SDP form? Thank a lot for your replying.

[Johan Löfberg]

Dual form means the form in which the constraints most efficiently are defined through an image, i.e.,, the form which you refer to on the Wiki, and as explained in the Automatic Dualization pages.

However, if you are referring to your problem in a previous post, you are not helped by trying to dualize the problem, the problem is essentially as big on both worlds (if you stick to default and let YALMIP interpret your model as dual form, P will use O(n^2) variables and so will variables defining the 1-norm. If you instead tell YALMIP to interpret it as a representation of a problem in standard primal form, you will still have to introduce O(n^2) equalities to put all the stuff related to the 1-norm in standard primal form. Similar stuff for the 2-norm)

n = 25;

A = rand(n,n);

P = sdpvar(n,n);

F = [P >= 0];

options = sdpsettings('solver','sedumi');

solvesdp(F,norm(P - A,1),sdpsettings('dualize',0))

solvesdp(F,norm(P - A,1),sdpsettings('dualize',1))

solvesdp(F,norm(P - A,'fro'),sdpsettings('dualize',0))

solvesdp(F,norm(P - A,'fro'),sdpsettings('dualize',1))

To summarize: The problem is neither in standard dual nor primal form, and once converted to either of them, the problem is of size O(n^2), hence large no matter what you try.

[Karl]

got it. Many Thanks! Actually, I am trying to solve a problem on the eigenvalue of graph Laplacian, which may be large in both forms.