Out of memory problem

[Son Phan]

Dear all,

I try to solve the mak-k cuts problem using semidefinite programming (see my attached file for the detail). Here is my code using Sedumi solver:

yalmip('clear');
Y = sdpvar(n,n);
C1 = Y >= 0; % positive semidefinite
C2 = Y(eye(n)==1) == 1; % diagonal condition
C3 = Y(eye(n)~=1) >= -1/(k-1);  % off diagonal condition
C = [C1, C2, C3];
Goal = sum(sum(D .* Y));
Ops = sdpsettings('solver','sedumi','debug',1);
sol = optimize(C,Goal,Ops);
Res = value(Y);

This code run well when n is small. However, when I set n = 300. I received the following errors

SeDuMi 1.32 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, theta = 0.250, beta = 0.500
Put 300 free variables in a quadratic cone
Error using callsedumi (line 44)
Error using sparse
Out of memory. Type HELP MEMORY for your options.

Error in solvesdp (line 335)
eval(['output = ' solver.call '(interfacedata);']);

Error in optimize (line 31)
[varargout{1:nargout}] = solvesdp(varargin{:});

Error in maxkcut_2 (line 75)
sol = optimize(C,Goal,Ops);

Is it the out of memory problem ? Is there a solution for this ?

Thanks !!!

[Johan Löfberg]

No simlpe solution, you simply have a huge problem, both in dual and primal space. Try different solvers is the only tip I can give.

Of course, defining the constant diagonal thorough equalities is an efficiency loss, as you don't work with this model in primal space. You should do

Y = sdpvar(n);
Y =Y-diag(diag(Y))+eye(n);

will only make a marginal difference though. Another ineffiiency is that you repeat the inequalities twice, as you define them for both upper-diagonal and lower-diagonal terms, on a symmetric matrix

[Son Phan]

Thank you ! The new setting is efficient, I'm using sdpt instead of sedumi. The result is faster but the out of memory problem is still present. I'm also searching a solution to unlimit the matlab array size.

[Johan Löfberg]

How large is n? For n larger than a couple of hundreds, standard general second-order SDP solvers will simply not be able to solve the problem, no matter how much memory you manage to squeeze out

[Son Phan]

With n >= 300. Is there any other feasible solvers for that ?

[Johan Löfberg]

you'll have to try and see. also try first-order solvers such as sdpnal