SDP: YALMIP ERROR-9, SOLUTION CONTAINS "NaN" VALUES FOR MORE THAN 100 DATAPOINTS

[Swarup Rj]

Hay guys,


TOPIC : SEMIDEFINITE SPECTRAL CLUSTERING

SDP formulation<MATLAB + YALMIP +SEDUMI>  : ,

%SOLVING THE PRIMAL FORM  min

% declare sdp variables: s
g=(N-1)*(k-1)+1;
s = sdpvar(g, g);

q1 = trace([vcap]'*Le*vcap*s);
q2 = diag(vcap*s*[vcap]');

F = [ s >= 0 ];
F = F + [q2 == bf];

solution = solvesdp(F, q1, ops);

Its working fine for datasets having less than 80 data points.
But incase of greater data points its showing YALMIP ERROR CODE 9 and the solution contains "NaN"

If the values,  #DATAPOINTS = 200 and #clusters = k = 3
Then the solution(s) will be a nk+1 * nk+1  i.e. 601*601 matrix.

Do i need to go for other solvers. Do suggest :-)

[Johan Löfberg]

If s is 601x601, I would guess you ran out of memory (turn on the option 'debug' to see the crash in all its glory)

However, it looks like a problem naturally solved in primal form, so you should ask YALMIP to interpret it as such (turn on the option 'dualize')
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.AutomaticDualization

[Johan Löfberg]

BTW, this is very slow (since it is O(n^3) as you first have to explicitly perform the matrix multiplication)

g = 600;
s = sdpvar(g, g);
x = randn(g);
o = trace(x*s)

Much better (O(n^2) complexity)

o =x(:)'*s(:)

[Swarup Rj]

A heart felt thanks johan... 

dualize worked. :-)

[Swarup Rj]

Hay johan,

('dualize', 1) is working fine for  the below optimization..

% declare sdp variables: s
g=(N-1)*(k-1)+1;
s = sdpvar(g, g);
q1 = trace([vcap]'*Le*vcap*s);
q2 = diag(vcap*s*[vcap]');
F = [ s >= 0 ];
F = F + [q2 == bf];
solution = solvesdp(F, q1, ops);

But,
When i increase one more constraint its saying 'INFEASIBLE PROBLEM'

g=(N-1)*(k-1)+1;
s = sdpvar(g, g);

q1 = trace(X' * Y * X * s);

q2 = diag(vcap*s*[vcap]');

q3 = trace(X' * Z * X * s);

F = [ s >= 0 ];
F = F + [q2 == bf];

% F = F + [W > 0];
F = F + [q3 == beta];     % THE NEW CONSTRAINT

[Johan Löfberg]

And you know it is feasible?

Remove the constraint and minimize the distance abs(q3-beta) instead. If the optimal objective is significantly non-zero, the problem is likely correctly detected as infeasible

[Johan Löfberg]

and as I said before, if you are doing this with n=601, perform the inner product using inner product of vectors instead of explicitly performing the matrix products (unless they are extremely sparse, but just note that creating the objective should not take longer than 0s).

[Swarup Rj]

 If i am taking the constraint as    F = F + [q3 >= alpha]; 
where alpha lowerbounds beta than its working fine...

And i was wrong with my previous constraint..  i need q3 greater than alpha .. 

Also i am using inner product of vectors, but is it applicable for the case    tr(a*b*c*z).

Thanks a lot.. :-)

[Johan Löfberg]

What I am saying is that instead of trace(a*b*c*z), do d = a*b*c, d(:)'*z(:)

>> n = 300;
>> x = randn(n);
>> y = sdpvar(n);
>> tic;trace(x*y);toc
Elapsed time is 3.464299 seconds.
>> tic;x(:)'*y(:);toc
Elapsed time is 0.072971 seconds.