SDPT3 failed to solve a conic optimization problem(indeed solvable)

1

The objective is a 325*325 large semidefinite real matrix, there are about 30000 equality constraints of it, most of them just tell some entries of the matrix are equal. The objective function is a linear combination of some entries.
Actually I did get the problem solved using YALMIP toolbox calling mosek, but when I rewrite the problem in cvx style and use SDPT3, it failed. I didn’t try mosek because I have trouble with calling mosek in cvx, I got the mosek license and put it in the corresponding path but it still didn’t work.

I put up my codes and the solving status below.The codes can be viewed as two parts mainly, the first half I impose the constraints, the second half I express the objective function, which is named fobj.For comparison I also showed the original codes of using YALMIP (commented out). By the way I only showed the related codes.I will really appericiate it if someone can give me some advise.

% yalmip(‘clear’)
% momentsmat = sdpvar(numops,numops,‘symmetric’) .
% constr=[];

cvx_begin

variable momentsmat(numops,numops) semidefinite

posconstrs=0; normconstrs=0; nsconstrs=0;

datetime(‘now’)
uniquemoms={ [] };uniquepos=[1,1]; %Assumes the top-left element is always the identity
if momentsref{1,1} ~= []
momentsref{1,1}
error(‘Top-left element is not identity!’)
end
for j=1:numops
for k=1:numops
if isequal(momentsref{j,k},0)
momentsmat(j,k)==0; momentsmat(k,j)==0;
elseif isequal(momentsref{j,k}, [] )
momentsmat(j,k)==1; momentsmat(k,j)==1;
else
duplicatepos=cell1Dpos(uniquemoms,momentsref{j,k});
if length(duplicatepos)==0 %Have not seen this moment before
uniquemoms{end+1}=momentsref{j,k};uniquepos=[uniquepos;j,k];

    elseif length(duplicatepos)==1 %Have previously seen this moment
        rownum=uniquepos(duplicatepos(1),1); colnum=uniquepos(duplicatepos(1),2);
        momentsmat(j,k)==momentsmat(rownum,colnum); momentsmat(k,j)==momentsmat(rownum,colnum);
    else
        error('Issue with identifying duplicates!')
    end
end

end
if mod(j,30)==0 %Prints timestamp every 30 rows
j
datetime(‘now’)
end
end
% constr=[constr,momentsmat>=0]; %NPA matrix is PSD

numuniques=length(uniquemoms) %Number of unique entries in the moment matrix
momentsmat
datetime(‘now’)

testterm = {{ [] },[0]};
for x=1:3
for y=1:3
for a=1:4
for b=1:4
avec=dec2bin(a-1,2)-‘0’;bvec=dec2bin(b-1,2)-‘0’;
avec=[avec mod(avec(1)+avec(2),2)];
bvec=[bvec mod(bvec(1)+bvec(2)+1,2)];
if avec(y)==bvec(x)
% [x y avec bvec]
testterm = lincombplus(testterm, { {[a b; x y+sizeX]} , [1/9]});
end
end
end
end
end

cheatterm = {{ [] },[0]};
for y=1:3
for b=1:4
cheatterm = lincombplus(cheatterm, {{ [y b; b+3 y+sizeX] }, [1/3]} );
end
end

testvars=0;
ops=testterm{1};coeffs=testterm{2}
for j=1:length(coeffs)
pos=cell1Dpos(uniquemoms,ops{j});rownum=uniquepos(pos,1);colnum=uniquepos(pos,2);
if length(pos)==0
ops{j}
error(‘Element not found!’)
end
testvars = testvars + coeffs(j)*momentsmat(rownum,colnum);
end
cheatvars=0;
ops=cheatterm{1};coeffs=cheatterm{2}
for j=1:length(coeffs)
pos=cell1Dpos(uniquemoms,ops{j});rownum=uniquepos(pos,1);colnum=uniquepos(pos,2);
if length(pos)==0
ops{j}
error(‘Element not found!’)
end
cheatvars = cheatvars + coeffs(j)*momentsmat(rownum,colnum);
end

testproblist = (1:9)/10;
resultslist = zeros(2,length(testproblist));
for pt = 1:length(testproblist)

testprob = testproblist(pt)
fobj = testprob*testvars + (1-testprob)*cheatvars

% fobj = -fobj; %YALMIP runs as minimisation by default
% testprob
% fobj=clean(fobj,10^-10)
% constr
% length(constr)
posconstrs
normconstrs
nsconstrs
% options=sdpsettings(‘verbose’,1,‘solver’,‘mosek’,‘savesolveroutput’,1,‘saveduals’,0);
datetime(‘now’)
% sol = optimize(constr,fobj,options);
maximise fobj

cvx_end

these are the solving procedure and status.

Calling SDPT3 4.0: 52975 variables, 28741 equality constraints

num. of constraints = 28741
dim. of sdp var = 325, num. of sdp blk = 1

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|2.9e+03|1.9e+02|1.9e+06| 0.000000e+00 0.000000e+00| 0:0:03| spchol 1 1
1|0.200|0.463|2.3e+03|1.0e+02|1.9e+06|-5.480813e+01 -7.689875e+01| 0:0:20| chol 1 1
2|0.332|1.000|1.6e+03|2.5e-01|2.1e+06|-9.575720e+01 -6.071983e+02| 0:1:21| chol 1 1
3|0.982|1.000|2.8e+01|7.5e-02|3.9e+04|-2.091569e+00 -6.069234e+02| 0:2:25| chol 1 1
4|0.915|1.000|2.4e+00|7.5e-03|3.7e+03|-4.794897e-01 -5.367307e+02| 0:3:24| chol 2 2
5|0.488|0.926|1.2e+00|1.2e-03|2.8e+03|-4.234126e-01 -5.538268e+02| 0:4:27| chol 2 2
6|0.642|1.000|4.4e-01|7.5e-05|1.6e+03|-3.270429e-01 -5.589719e+02| 0:5:29| chol 2 2
7|0.895|0.915|4.6e-02|1.3e-05|5.4e+02|-2.773474e-01 -4.275404e+02| 0:6:32| chol 2 2
8|0.435|0.737|2.6e-02|9.2e-03|3.3e+02|-2.607592e-01 -2.768935e+02| 0:7:36| chol 2 2
9|0.630|1.000|9.7e-03|5.2e-03|2.3e+02|-2.380909e-01 -2.126032e+02| 0:8:37| chol 2 2
10|1.000|1.000|7.9e-10|1.9e-03|1.4e+02|-2.216650e-01 -1.382442e+02| 0:9:40| chol 3 2
11|1.000|0.959|9.0e-10|7.8e-05|5.6e+00|-2.299958e-01 -5.848030e+00| 0:10:44| chol 3 3
12|1.000|1.000|1.8e-10|2.6e-10|3.0e+00|-5.318162e-01 -3.554510e+00| 0:11:50| chol 3 3
13|1.000|1.000|4.1e-11|4.3e-11|9.8e-01|-6.824828e-01 -1.662192e+00| 0:12:56| chol 5 5
14|1.000|1.000|1.2e-11|8.9e-12|4.3e-01|-8.306274e-01 -1.264440e+00| 0:14:12| chol 6 7
15|0.996|0.975|4.0e-12|2.6e-12|1.0e-01|-9.326484e-01 -1.035356e+00| 0:15:34| chol
warning: symqmr failed: 0.3 30 30
16|0.808|1.000|1.4e-07|1.0e-12|6.5e-02|-9.600228e-01 -1.025449e+00| 0:18:41| chol
warning: symqmr failed: 0.3 30 30
stop: primal infeas has deteriorated too much, 3.1e-01
17|1.000|1.000|1.4e-07|1.0e-12|6.5e-02|-9.600228e-01 -1.025449e+00| 0:21:52|

number of iterations = 17
primal objective value = -9.60022796e-01
dual objective value = -1.02544917e+00
gap := trace(XZ) = 6.54e-02
relative gap = 2.19e-02
actual relative gap = 2.19e-02
rel. primal infeas (scaled problem) = 1.42e-07
rel. dual " " " = 1.01e-12
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 8.1e+00, 6.0e+01, 1.1e+01
norm(A), norm(b), norm© = 1.5e+02, 2.0e+00, 1.7e+00
Total CPU time (secs) = 1311.82
CPU time per iteration = 77.17
termination code = -7
DIMACS: 1.4e-07 0.0e+00 1.5e-12 0.0e+00 2.2e-02 2.2e-02

Status: Failed
Optimal value (cvx_optval): NaN

2

Try SDPT3 as solver under YALMIP and see what happens (although, even if your CVX and YALMIP codes are equivalent, it is possible that the problems presented to SDPT3 wlil be different for YALMIP and CVX).

Mosek is a more robust solver than SDPT3, and can successfully solve some problems for which SDPT3 fails.

Also try SeDuMi under CVX.

As for Mosek under CVX, if you are able to use it under YALMIP and are using CVX 2.2, you should be able to reinstall CVX and Mosek should work. If not, what error messages are you seeing when you to nsstall and use Mosek? Are any versions of Mosek listed when you issue the command cvx_solver ?

3

Thank you very much for your advise, I changed to Mosek and the problem did get solved.

4

By the way, I started another topic on Mosek. I hope you can give me some suggestions if you are convenient. Thank you for your time.

5

Of course what does ‘solved mean’? I always think it is a good habit to verify that you have (near) primal feasibility for the optimum and that you have dual feasibility and complementarity. The original problem may be ‘ill-posed’ and that is what is causing the difficulty for SDPT3.