Express constraints which are correlated with X

[Shu Kai]

Hi guys,

 

Now I am solving a conbinatorial probelm called MAX DICUT using YALMIP.

 

In this problem, the objective is to maximize:

 

          C \cdot X

 

the constraints form are like A + B + X >=0.(which means the elements of A+B+X are all greater than 0)

 

Where C is constant matrix, but A and B  are correlated with X (i.e. the elements of A and B come from X).

 

Can someone tell me how to express this kind of constraints?

[Johan Löfberg]

First, be careful here. Since you talk about MAXCUT, you probably have symmetric matrices. If you have a symmetric expression and want to express that all elements are non-negative, you have to make sure you don't define an LMI by mistake

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics

You simply define A and B using X using standard MATLAB code

X= sdpvar(n);

A = [X E;E' (trace(X)-X(2,2))*eye(n)];
etc..

% In case A+B+X is symmetric, make sure we define elementwise
% as explained in link above
mythingy = A + B + X
Constraints = [mythingy(:) >= 0]
etc...

[Shu Kai]

Thank,Johan!

Here is another question. As my SDP prolem is of large scale, I want to use YALMIP to express my problem first

and then save it as SDPA sparse format using 'savesdapfile' command. But I found it is really time expensive.

Could you tell me hot to reduce the time of this process?

Hope for your reply ASAP! Thanks.

[Johan Löfberg]

Why not call SDPA directly from YALMIP using the mex-versions of SDPA

There is no way to improve this. The hack savesdpafile was not designed for large problems, and I never use it. Writing to text-file simply takes time...

[Shu Kai]

I think call SDPA can not solve large scale SDP problem, so I try to use YALMIP to transform the problem formulation to SDPA spase format, and then

solve it with SDPARA. Since I have lots of intput files to be computed, so I intend to reduce the time of file writing process.

I think it will be very useful to improve the speed  to save sdpa file!

I check the source code of YALMIP, maybe the createsdplibfile.m is the key, right?

[Johan Löfberg]

If you install OPTI Toolbox, you can use its export/import functionalities

Note, I assume you don't have any equalities in the dual/free in primal, since SDPA dsoesn't support that

% Use YALMIP to generate SeDuMi data

A = sprandn(60,60,.01);

P = sdpvar(60);

Con = [A'*P+P*A <= -eye(60)];

obj = trace(P);

model = export(Con,obj,sdpsettings('solver','sedumi'));

At = model.A;b = model.b;c = model.C;K = model.K;

% Save SeDuMi data to file

% SDPA does not support free variables and SOCPs, and OPTI will scream even

% though the fields are empty 

% NOTE: If these aren't empty, you cannot remove them!!!

K = rmfield(K,'f')

K = rmfield(K,'q')

K = rmfield(K,'r')

K = rmfield(K,'scomplex')

K = rmfield(K,'xcomplex')

save testfile At b c K

% Load to opti

[prob,p] = sdpRead('testfile.mat');

% Save to SDPA

sdpWrite(prob,'testsdpa.dat-s','sdpa-s')

[Johan Löfberg]

BTW, I would be interested in seeing what your model looks like. Based on the short description, it sounds like a model where you easily can make mistakes in how you model it, resulting in an unnecessarily complex model.