Why cvx ignored my constraints?


(chen) #1

I am trying to figure out a problem of binary quadratically constrained linear program (0-1 QCLP) with sdp. ‘x’ is the {0,1} matrix variable I want to find out. And X is the sdp relaxation of X=xx.’ I constrained x to (0,1) with continuous box-constrained relaxation. However, cvx ignored my constraint of x or X, and x turned out to be minus in some cases (thusleading to a result far from optimal, really, even far from sub-optimal). Is it because cvx can only provide a rough answer? Or my procedure is too fussy?
I found my result far from optimal because the next step I make some heuristic effort to remap x from [0,1] to {0,1}, and find after remap, the result is better than before. Relax x to [0,1] should be a upper bound, but turned out to be smaller than the latter result. So I found there is something wrong with my procedure.
Moreover, my precedure is apt to run out of memory, but I just put a few users, antennas and cell, which is rather tiny in a communication system.
I would be very grateful if someone could help. I say thank you first of gratitude !

%procedure involves simple communication resource management
s=2;l=3;r=3;u=4;w=60000;n=10;N=slru;
w1=5;
w2=2;
rmin=1000;beita=2.5 ;
W=zeros(1,N);
for i=1:1:N/2
W(1,i)=5;
end
for j=N/2+1:1:N
W(1,j)=2 ;
end
H1=rand(u,l,r);
d=zeros(u,l,r,s);e=zeros(u,l,r,s);
I1=zeros(u,l,r);
for i=1:u
for j=1:l
for k=1:r
I1(i,j,k)=sum(H1(i,:,k).^2)-H1(i,j,k).^2;
end
end
end
I2=zeros(u,l,r,s);
for i=1:s
I2(:,:,:,i)=I1(:,:,:);
end
I3=reshape(I2,[1,N]);
VV1=w
log(1+H1.^2./(I1+n));
VV2=zeros(u,l,r);
b=find(VV1>100);
VV2(b)=VV1(b);
V2=zeros(u,l,r,s);
for k=1:s
V2(:,:,:,k)=VV2(:,:,:);
end
V3=reshape(V2,[1,N]);
H3=zeros(N,N);
zico=1;
for q=1:s
for k=1:r
for j=1:l
for i=1:u
hh=zeros(u,l,r,s);
hh(i,:,k,1)=H1(i,:,k);
hh(i,:,k,2)=H1(i,:,k);
H2=reshape(hh,1,N);
H3(:,zico)=H2.’;
zico=zico+1;
end
end
end
end
for i=1:N
H3(i,i)=0;
end
vv1=zeros(u,l,r,s);vv2=zeros(u,l,r,s);
vv1(:,:,:,1)=V2(:,:,:,1);vv2(:,:,:,2)=V2(:,:,:,2);
v1=reshape(vv1,[1,N]);
v2=reshape(vv2,[1,N]);
cc1=zeros(r*l,N);
d=zeros(u,l,r,s);e=zeros(u,l,r,s);
k=1;
for i=1:l
for j=1:r
d(:,i,j,:)=1;
c1=reshape(d,[1,N]);
cc1(k,:)=c1;
d=zeros(u,l,r,s);
k=k+1;
end
end
ee=zeros(u,N);
gd1=zeros(u,N);
for g=1:u
e(g,:,:,1)=V2(g,:,:,1);
c2=reshape(e,[1,N]) ;
gd=zeros(1,N);
idx=find(c2>0);
gd(idx)=1;
ee(g,:)=c2;
gd1(g,:)=gd;
e=zeros(u,l,r,s);
end
%above is preparing for constant expressions

cvx_begin sdp
variables x(1,N) X(N,N)
variable Y(N+1,N+1) symmetric
variable Z(2,2) symmetric
o=W.V3;
minimize (-o
x.’)
subject to
x>=0; %these constraints are ignored by cvx!! 。o>_<o。
x<=1;
X==semidefinite(N) ;
vec(X)<=vec(1);

Y(N+1,N+1)==1;
Y(1:N,1:N)==X; %using sdp relaxation X=xx.‘
Y(1:N,N+1)==x.’;
Y(N+1,1:N)==x;
diag(X) <= x.’;
Y==semidefinite(N+1) ;

cc1x.’<=1; %C1
%vec((gd1
x.’).((eex.’)-rmin))>=vec(0);
for g=1:u
e(g,:,:,1)=V2(g,:,:,1);
c2=reshape(e,[1,N]) ;
gd=zeros(1,N);
idx=find(c2>0);
gd(idx)=1;
Z(1,1)==gdx.’; %c2
Z(1,2)==1;
Z(2,1)==c2
x.’-rmin;
Z(2,2)==1;
Z>=0;
e=zeros(u,l,r,s);
end
(v1-beita*v2)x.’<=0; %c3
diag(X
H3)<=I3.’ ; %c4
cvx_end;