Can any body help to solve this SDP

(vikas) #1


I am new to CVX and want to implement the SDP problem as in attachment. My code gives output
when M1=10^(1),
Status: Inaccurate/Solved
Optimal value (cvx_optval): +3.38903e-06
for M1=10^(6)
Status: Infeasible
Optimal value (cvx_optval): +Inf

But, for M1=10^(0) and using ‘cvx_precision medium’
Status: Solved
Optimal value (cvx_optval): +3.41645e-07
Can any body help to resolve this. M1=10^(6) is required in this SDP. My code is as under

clc;
clear all;
close all;
n=10;
M1=10^(0); %mega
f_L =5*10^8; % Local CPU rate in 'cycles/sec'
E_l_cyc = 1.4*10^(-9);%=1/(730*10^6); % Local processing energy consumption per cycle in 'J/cycle'
T_l_pb=4.75*10^(-7); % Local computation time per bit in 's/bit'
E_ll=3.25*10^(-7); % Local processing energy consumption per bit in 'J/bit'
C_DL = 72.2*M1;%Mbps user to CAP transfer rate
C_UL = 72.2*M1;%Mbps CAP to user transfer rate
E_DL = 1.42*10^(-7); E_UL = 1.42*10^(-7); %Tx and RX transmission energy consumption in J/bit
f_A =5*10^9; % Aceess Point CPU rate in 'cycles/sec'
f_C =10*10^9; % Cloud CPU rate in 'cycles/sec'
R_ac = 15; % in Mbps cloud offload transmission rate
alpha = 2*10^(-7); % in J/bit
beta = 5*10^(-7); % in J/bit
Rho = 1; % in J/sec weighting of maximum delay to process all task



App=1900;% in cycles/byte x264 CBR (constant bit rate) encode application
D_in = randi([10 30],n,1)*M1;%*10^6; % uniform distribution of input data size from 10 to 30 MB
D_out = randi([1 3],n,1)*M1;%*10^6; % uniform distribution of output data size from 1 to 3 MB
C_a=1;%D_in;
C_c=1;%D_in;
%%% Decision variable x and y based on input data size D_in%%
for i=1:n;
if D_in(i)<=15*M1%*10^6
    aa(i)=0;%x(i)=0; y(i)=0;
% elseif (D_in(i)>15) && (D_in(i)<22)
%     x(i)=1; y(i)=0;
else
    aa(i)=1;%x(i)=1; y(i)=1;
end
end
%%% Decision complete%%
E_l=(E_ll*ones(1,n))';  E_t=(E_DL*ones(1,n))';  E_r=(E_UL*ones(1,n))';
C_aj=D_in;%(C_a*ones(1,n))';  
C_cj=D_in;%(C_c*ones(1,n))';  
App_j=(App*ones(1,n))';
e_i=ones(n,1);  e_i_bar=ones(2*n+1,1);
zero1=zeros(n,n);  zero1_bar=zeros(n,1);
T_L =D_in'.*aa/f_L;

A_0_bar = 0.5*(diag(alpha*C_aj+beta*C_cj));
A_0=[zero1 A_0_bar zero1_bar; A_0_bar' zero1 zero1_bar; zero1_bar' zero1_bar' 0];

A_a_bar = 0.5*(diag(D_in)*diag(App_j))/f_A;
A_a=[zero1 A_a_bar zero1_bar; A_a_bar' zero1 zero1_bar; zero1_bar' zero1_bar' 0];

A_c_bar = 0.5*(diag(D_in+D_out)/R_ac+diag(D_in)*diag(App_j)/f_C);
A_c=[zero1 A_c_bar zero1_bar; A_c_bar' zero1 zero1_bar; zero1_bar' zero1_bar' 0];

b_0 = [(-E_l + E_t + E_r + alpha*C_a)' zero1_bar' Rho]';
b_l = -[T_L zero1_bar' 1]';

b_a_bar = D_in/C_UL+D_out/C_DL+diag(D_in)*App_j/f_A;
b_c = [(D_in/C_UL+D_out/C_DL)' zero1_bar' -1]';
b_a = [b_a_bar' zero1_bar' -1]';

G_0 = [A_0 0.5*b_0; 0.5*b_0' 0];
G_l = [zeros(2*n+1,2*n+1) 0.5*b_l; 0.5*b_l' 0];
G_a = [A_a 0.5*b_a; 0.5*b_a' 0];
G_c = [A_c 0.5*b_c; 0.5*b_c' 0];
G_p = [diag(ones(2*n+1,1)) -ones(2*n+1,1); -ones(2*n+1,1)' 0];


% x = randi([0 1],1,n);%binary;
% y = randi([0 1],1,n); ;%binary;
% y1 = randi([0 1],1,n); %binary;
% y2 = randi([0 1],1,n);
cvx_begin 
cvx_precision medium
% cvx_solver SeDuMi
variable x(n) nonnegative
variable y(n) nonnegative
% variable t
variable y1(n)
variable y2(n)
variable X(2*n+2,2*n+2) 
% variable G_0(2*n+2,2*n+2)
% expressions  b(n) y1(n) y2(n) 
% expressions  T_t(n) T_r(n) T_a(n) T_c(n) T_tr_cl(n) Delay8local(n) Delay8Cap(n) b(n); 
% expressions  Delay8Cloud(n) T_L(n) T_A(n) T_C(n) t(n) w(2*n+1) Z(2*n+2) 
% expression  X(2*n+2,2*n+2);

 b=ones(n,1)-y;
%%% delay computations for local, cap and cloud processing - offload delay at
%%% CAP offload delay at Cloud  %%%%%%%
%%% y1 = x.*1-y
 y1>=x+b-1, y1<=x, y1<=b, 0<=y1<=1, 
 %%% y2 = x.*y
 y2>=x+y-1, y2<=x, y2<=y, 0<=y2<=1, 
%  cvx_end

T_t=D_in'.*x'/C_UL;
T_r=D_out'.*x'/C_DL;
T_a=App*D_in'.*y1'/f_A;
T_c=App*D_in'.*(y2)'/f_C;
T_tr_cl=((D_in+D_out)'.*y2')/R_ac;
Delay8local=D_in'.*aa/f_L;
Delay8Cap=T_t+T_a+T_r;
Delay8Cloud=T_t+T_tr_cl+T_c+T_r;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% max delay computation
T_L = Delay8local'; %% ones(1,n)*Delay8local';%% equation (3)
T_A = Delay8Cap';   %%ones(1,n)*Delay8Cap';%% equation (4) or (7)
T_C = Delay8Cloud'; %%ones(1,n)*Delay8Cloud';%% equation (5) or (8)
 t=ones(1,n)*Delay8local';%[ones(1,n)*Delay8local' ones(1,n)*Delay8Cap' ones(1,n)*Delay8Cloud']

% for i=1:10
% t1(i)=max([T_L(i) T_A(i) T_C(i)]);
% end
% t=max([ones(1,n)*Delay8local' ones(1,n)*Delay8Cap' ones(1,n)*Delay8Cloud']);
%%%%%%%%%%%%%%%%%%%%%%%
w = transpose([x' y' t]);

Z = transpose([transpose(w) 1]);
b=transpose(Z);

for i=1:2*n+2;
    for j=1:2*n+2;
 X(i,j)>=Z(i)+b(j)-1; 
  X(i,j)<=Z(i);
 X(i,j)<=b(j); 
 0<=X(i,j)<=1;
    end
end
minimize(trace(G_0*X));
subject to
trace(G_l*X)<=-T_L'*ones(n,1);
trace(G_a*X)<=0;
trace(G_c*X)<=0;
trace(G_p*X)==0;

cvx_end
(Mark L. Stone) #2

You perhaps have"crazy" (non-zero coefficients much too far in magnitude form 1) input numbers which cause numerical difficulties for solvers.

I haven’t looked carefully at your program, but one thing which jumps out at me is that you neglected to include a semidefinite constraint for X, which you could do by changing its declaration to
variable X(2n+2,2n+2) semidefinite .

(vikas) #3

`putting ‘variable X(2n+2,2n+2) semidefinite’ .
results in (for M1=0 itself)
Status: Failed
Optimal value (cvx_optval): NaN
Mark_L_Stone please help me. If you want I can send you the m-file.

(Mark L. Stone) #4

You are dividing by C_UL, which equals 0 when M1 = 0. You really need to think carefully about all your input data, and its numerical values.

(vikas) #5

sorry there was a mistake in previous post it is M1 = 10^(0)=1; Anyway, after changing some other input, it (defining variable X(2n+2,2n+2) semidefinite) is working and output is
Status: Solved
Optimal value (cvx_optval): -7.27841e-12
But not getting optimized value of x and y, carefully observing, I saw that I have fixed ‘t’ with t=ones(1,n)*Delay8local’;
But actually In my code, i need to put
t=max([ones(1,n)*Delay8local’ ones(1,n)*Delay8Cap’ ones(1,n)*Delay8Cloud’])
w = transpose([x’ y’ t]);
within CVX. which results in.

Error using <= (line 22)
Disciplined convex programming error:
Invalid constraint: {real affine} <= {positive convex}

Error in (line 137)
X(i,j)<=b(j);

Is there any other way, keeping t=max(as above), not fixing it, and implementing X=Z*Z’; Thanks

(Mark L. Stone) #6

I really have no idea what you’re doing, or how it relates to the paper extract you showed? Where is any of this in that extract?

affine (or constant) <= convex is non-convex. The inequality is going the wrong direction to be convex.

(vikas) #7

Thanks for suggestion regarding extract of the paper, I have corrected my code that is as follows

cvx_begin sdp
cvx_solver SeDuMi
variable X(2n+2,2n+2) semidefinite
minimize(trace(G_0X));
subject to
trace(G_l
X)<=-T_L’ones(n,1);
trace(G_a
X)<=0;
trace(G_cX)<=0;
for i=0:2
n-1
e_p_bar =circshift([1 zeros(1,2n)]’,i);
G_p = [diag(e_p_bar) -0.5
e_p_bar; -0.5e_p_bar’ 0];
trace(G_p
X)==0;
end
X==ones(2n+2,2n+2);
X>=zeros(2n+2,2n+2);

cvx_end
%%%%%%%%%%%%%%%%%

Here, G_0, G_l, G_a, G_c and G_p are (2n+2x2n+2) size scalar matrix.

clc;
clear all;
close all;
L=100;
n=10;
M1=10^(6); %mega
f_L =510^8; % Local CPU rate in ‘cycles/sec’
E_l_cyc = 1.4
10^(-9);%=1/(73010^6); % Local processing energy consumption per cycle in ‘J/cycle’
T_l_pb=4.75
10^(-7); % Local computation time per bit in ‘s/bit’
E_ll=3.2510^(-7); % Local processing energy consumption per bit in ‘J/bit’
C_DL = 72.2
M1;%Mbps user to CAP transfer rate
C_UL = 72.2M1;%Mbps CAP to user transfer rate
E_DL = 1.42
10^(-7); E_UL = 1.4210^(-7); %Tx and RX transmission energy consumption in J/bit
f_A =5
10^9; % Aceess Point CPU rate in ‘cycles/sec’
f_C =1010^9; % Cloud CPU rate in ‘cycles/sec’
R_ac = 15
M1; % in Mbps cloud offload transmission rate
alpha = 210^(-7); % in J/bit
beta = 5
10^(-7); % in J/bit
Rho = 1; % in J/sec weighting of maximum delay to process all task

App=1900/8;% in cycles/byte x264 CBR (constant bit rate) encode application
D_in = randi([10 30],n,1)*M1;%*10^6; % uniform distribution of input data size from 10 to 30 MB
D_out = randi([1 3],n,1)*M1;%*10^6; % uniform distribution of output data size from 1 to 3 MB

C_a=D_in;
C_c=D_in;

T_L=D_in/f_L;

zero1=zeros(n,n); zero1_bar=zeros(n,1);

b_c = [(D_in/C_UL+D_out/C_DL)’ zero1_bar’ -1]’;
A_c_bar = 0.5*(diag(D_in+D_out)/R_ac+diag(D_in)diag(Appones(n,1))/f_C);
A_c=[zero1 A_c_bar zero1_bar; A_c_bar’ zero1 zero1_bar; zero1_bar’ zero1_bar’ 0];
G_c = [A_c 0.5b_c; 0.5b_c’ 0];

b_a_bar = D_in/C_UL+D_out/C_DL+diag(D_in)Appones(n,1)/f_A;
b_a = [b_a_bar’ zero1_bar’ -1]’;
A_a_bar = 0.5*(diag(D_in)diag(Appones(n,1)))/f_A;
A_a=[zero1 A_a_bar zero1_bar; A_a_bar’ zero1 zero1_bar; zero1_bar’ zero1_bar’ 0];
G_a = [A_a 0.5b_a; 0.5b_a’ 0];

b_l = -[T_L’ zero1_bar’ 1]’;
G_l = [zeros(2n+1,2n+1) 0.5b_l; 0.5b_l’ 0];
A_0_bar = 0.5*(diag(-alphaC_a+betaC_c));

E_l=(E_ll.D_in); E_t=(E_DL.D_in); E_r=(E_UL.D_out);
b_0 = [(-E_l + E_t + E_r + alpha
C_a)’ zero1_bar’ Rho]’;
A_0=[zero1 A_0_bar zero1_bar; A_0_bar’ zero1 zero1_bar; zero1_bar’ zero1_bar’ 0];
G_0 = [A_0 0.5
b_0; 0.5
b_0’ 0];
Can you tell me where is the problem in my code, I am getting following message
Status: Infeasible
Optimal value (cvx_optval): +Inf

(Mark L. Stone) #8

Your model is infeasible. Follow the advice in https://yalmip.github.io/debugginginfeasible/ .

(vikas) #9

X==ones(2 n+2,2 n+2);
[what is wrong with this constraint without it CVX status is solved, but with this constraint it is showing infeasible.]

(Mark L. Stone) #10

You are constraning all elements of X to equal 1. Do you want <= rather than ==, i.e., you have a typo? If so, you can more simply write that and the next constraint as 0 <= X <= 1 .