When I run the following code in CVX, when A is an integer N by N matrix, I am getting an infeasible solution as output. Have tried quite a lot of ‘possible’ common fixes but nothing is working. Please somebody help!
val=N*N;
cvx_begin sdp
variable Sigma(N,N) symmetric
minimize trace(A*Sigma)/val
subject to
2*N*sum(diag(Sigma))-2*(trace(Sigma*ones(N,N)))==N*N;
for i=1:N
for j=1:N
for k=1:N
2*(Sigma(i,k)+Sigma(k,j)-Sigma(i,j))-Sigma(k,i)-Sigma(k,k)<=0
end
end
end
cvx_end
Thank you for your reply. Actually this problem (sparsest cut in undirected graphs) is not well defined for n=1. Hence the SDP formulation is not meant to reflect this and neither the value of N. In addition, the matrix Sigma contains on the diagonals the degree of each vertex in a graph on n nodes, and if (i,j) is an edge in the graph then Sigma(i,j)=-2.
Essentially this is the problem I am trying to solve: (The seminal ARV (2004) SDP relaxation)
minimize (1/n^{2}) \sum (i,j)\in E ||v_i-v_j||^{2}
subject to \sum_ i , j || v_i- v_j||^{2} = n^{2}
and ||v_i-v_j||^{2} + || v_j - v_k ||^{2} >= ||v_i - v_k ||^{2} for all 3 tuples
v_i is a vector in the Euclidean n dimensional space.
I believe your program is infeasible for every value of N (but the first constraint by itself is not infeasible for N > 1).
I don’t understand the relation between your post immediately above and your code, and I am not familiar with the problem you are trying to solve. I don’t see how your code is an SDP relaxation, other than the most trivial kind, because all of your LMI’s, so to speak, are 1 by 1, i.e., are just scalar inequalities. In fact, your code is a Linear Program, which of course is trivially an SDP. You may have to invest more effort in formulating a convex problem to provide CVX.