Why the cvx optimization problem solved status showed failed?


#1

Dear everyone,

My code is followed:

clear;
clear all;
k = 8;                           % The number of user in a small cell

% rayleigh fading
% Fs = 9600;
% Ts = 1/Fs;
% fdmax = 0;
% Delay=1e-6*[10.15];
% PowerdB=-2*ones(1,1);
% rayCh = rayleighchan(Ts,fdmax,Delay,PowerdB);
% r = abs(rayCh.PathGains);
% for i = 2:k
%     rayCh = rayleighchan(Ts,fdmax,Delay,PowerdB);
%     r = [r,abs(rayCh.PathGains)];               % The uplink and downlink channel power gains of user k
% end
r = ones(1,k);

%Simulation parameters
n = 0.3;                              % shared fraction, 0<=n<=1
N0 = -147;                            % noise power spectral density(dBm/Hz)
N0 = power(10,N0/10)/1000;            % Converted to w/Hz
Wul = 1e3; Wdl = 1e3;                 % The uplink and downlink bandwidth (Hz)
Pumax = 100; Pdmax = 1000;            % The uplink and downlink power(w)
FC = 10^10;                           % The cloudlet server processing capacity(CPU cycles/s)
luk = 1.78*10^-6;                     % The amount of energy spent by the mobile device to extract each bit of offloaded data from the video source(J/bit)
ldk = 0.625;                          % Parameter that captures the mobile receiving energy expenditure per second in the downlink(J/s)
BIk = 1e4*ones(1,k);                  % Input bits from each user k to the cloudlet in the uplink (1Mbits)
BOk = 1e4*ones(1,k);                  % Out bits from the cloudlet to each user k in the downlink (1Mbits)
Vk = 2640*BIk;                        % Processing the input BIk by executing Vk CPU cycles at the cloudlet (CPU cycles)
Vs = n*Vk;                            % Shared CPU cycles
BOs = n*BOk;                          % Shared output bits that delivered to all users
BIs = n*BIk;                          % Shared input bits that can be sent by any of the users

%Initialize the z = [Pul,Bls,f,Pdl,PdM,TuS,TdS]
Pulk0 = Pumax*rand(1,k);                              % The uplink power(w)of user k
%Pdlk0 = Pdmax/k*ones(1,k);                            % The downlink power(w)to user k
Pdlk0 = rand(1,k);
Pdlk0 = Pdlk0/(sum(Pdlk0))*Pdmax;
PdlM0 = Pdmax*rand(1,1);                              % Transmit power (w) for multicasting 
%BIsk0 = BIs/k.*ones(1,k);                             % A fraction of BIsk bits of the BIs shared bits transmited by user k  
BIsk0 = rand(1,k);
BIsk0 = BIsk0/sum(BIsk0).*BIs; 
fk0 = rand(1,k);                                      
fk0 = fk0/(sum(fk0));
fs0 = rand(1,1);                                      % Fractions of the processing power FC assigned to run the Vk CPU cycles exclusively for user k and the VS shared CPU cycles
f0 = [fk0,fs0]; 

PU0 = r.*Pulk0;                                       % The uplink power after rayleigh fading 
Rulk0 = (Wul/k)*log2(1+PU0/(N0*Wul/k));               % Transmitting rate of user k in the uplink
PD0 = r.*Pdlk0;                                       % The downlink power after rayleigh fading 
Rdlk0 = (Wdl/k)*log2(1+PD0/(N0*Wdl/k));               % Transmitting rate to user k in the downlink
PM0 = r.*PdlM0;                                       % Multicasting power after rayleigh fading 
RdlMk0 = Wdl*log2(1+PM0/(N0*Wdl));                    % Transmitting rate to users for multicasting
TuS0 = max(BIsk0./Rulk0);                             % The time to complete the shared uplink transmissions (s)
TdS0 = max(BOs./RdlMk0);                              % The downlink transmission time to multicast BOs bits
Tmax = 10;                                             % Maximum latency constraint(0.15s/0.05s)
z0 = [Pulk0,BIsk0,f0,Pdlk0,PdlM0,TuS0,TdS0];
alpha = 10^-5; epsilong = 10^-5; delta0 = rand;       % Accuracy parameters

    cvx_solver SeDuMi
    cvx_begin
        variables Pulk(1,k) BIsk(1,k) fk(1,k) fs Pdlk(1,k) PdlM TuS TdS;
        f = [fk,fs];
        PU = r.*Pulk;
        Rulk = (Wul/k)*log(1+PU/(N0*Wul/k))/log(2);
        PD = r.*Pdlk;
        Rdlk = (Wdl/k)*log(1+PD/(N0*Wdl/k))/log(2);
        PM = r.*PdlM;
        RdlMk = Wdl*log(1+PM/(N0*Wdl))/log(2);
                    
        %The overall downlink mobile energy consumption for user k
        Edlk = ((BOk-BOs).*inv_pos(Rdlk)+(BOs.*inv_pos(RdlMk)))*ldk;
        
        %Mobile energy consumption of uplink transmission
        z = [Pulk,BIsk,f,Pdlk,PdlM,TuS,TdS];
        E = (z-z0)*diag(z0)*(z-z0)';
        e1 = Pulk0.*(BIsk0+(BIk-BIsk0)).*inv_pos(Rulk);
        e2 = Pulk0.*(BIsk+(BIk-BIsk0))./Rulk0;
        e3 = Pulk.*(BIsk0+(BIk-BIsk0))./Rulk0;
        e4 = luk*(BIsk+(BIk-BIsk0));
        Eulk = e1+e2+e3+E+e4;
        
        % Rewrite the latency constraints C.2
        g1 = square_pos(BIsk+inv_pos(Rulk));
        g2 = Rulk0.*Rulk0;
        g3 = (g1-BIsk0.^2-1./g2);
        g4 = BIsk0.*(BIsk-BIsk0);
        g5 = (r.*Pulk0)/(N0*Wul/k);
        g6 = (1+g5).*(Rulk0.^4);
        g7 = g4-(Rulk0./g6).*(inv_pos(Rulk)-1./Rulk0);
        gk = 1/2*g3-g7;  
        
        minimize(sum(Eulk+Edlk))               
        subject to 
            (BIk - BIsk0).*inv_pos(Rulk)+(Vk-Vs)/FC.*inv_pos(fk)+Vs/FC*inv_pos(fs)+(BOk-BOs).*inv_pos(Rdlk) <= Tmax-TuS-TdS;   % Constraint C.1
            gk <= TuS;                            % Constraint C.2
            BOs.*inv_pos(RdlMk) <= TdS;           % Constraint C.3
            sum(fk) <= 1;                         % Constraint C.4
            0 <= fk <= 1;
            0 <= fs <= 1;
            sum(BIsk) == BIs;                     % Constraint C.5
            sum(Pdlk) <= Pdmax;                   % Constraint C.6
            0 <= Pdlk <= Pdmax;
            0 <= PdlM <= Pdmax;
            0 <= Pulk <= Pumax;
            0 <= TuS <= Tmax;
            0 <= TdS <= Tmax;        
            0 <= BIsk <= BIs;
    cvx_end
% Iteration

% while (norm(z-z0,2)^2) > epsilong
% delta = delta0*(1-alphadelta0);
% z1 = z0+delta
(z-z0);
% z0 = z1;
% Pul0 = z1(1:k); Bls0 = z1(k+1:k+k); fk0 = z1(2k+1:3k); fs0 = z1(3k+1);
% Pdl0 = z1(3
k+2:4k+1); PdM0 = z1(4k+2); TuS0 = z1(4k+3); TdS0 = z1(4k+4);
%
% cvx_begin
% variables Pulk(1,k) BIsk(1,k) fk(1,k) fs Pdlk(1,k) PdlM TuS TdS;
% f = [fk,fs];
% PU = r.Pulk;
% Rulk = (Wul/k)log(1+PU/(N0Wul/k))/log(2);
% PD = r.Pdlk;
% Rdlk = (Wdl/k)log(1+PD/(N0Wdl/k))/log(2);
% PM = r.PdlM;
% RdlMk = Wdl
log(1+PM/(N0
Wdl))/log(2);
% Edlk = ((BOk-BOs).inv_pos(Rdlk)+(BOs.inv_pos(RdlMk)))ldk;
%
% z = [Pulk,BIsk,f,Pdlk,PdlM,TuS,TdS];
% E = (z-z0)diag(z0)(z-z0)’;
% e1 = Pulk0.
(BIsk0+(BIk-BIsk0)).inv_pos(Rulk);
% e2 = Pulk0.
(BIsk+(BIk-BIsk0))./Rulk0;
% e3 = Pulk.
(BIsk0+(BIk-BIsk0))./Rulk0;
% e4 = luk
(BIsk+(BIk-BIsk0));
% Eulk = e1+e2+e3+E+e4;
%
% g1 = square_pos(BIsk+inv_pos(Rulk));
% g2 = Rulk0.Rulk0;
% g3 = (g1-BIsk0.^2-1./g2);
% g4 = BIsk0.
(BIsk-BIsk0);
% g5 = (r.Pulk0)/(N0Wul/k);
% g6 = (1+g5).
(Rulk0.^4);
% g7 = g4-(Rulk0./g6).(inv_pos(Rulk)-1./Rulk0);
% gk = 1/2
g3-g7;
%
% minimize(sum(Eulk+Edlk))
% subject to
% (BIk - BIsk0).*inv_pos(Rulk)+(Vk-Vs)/FC.inv_pos(fk)+Vs/FCinv_pos(fs)+(BOk-BOs).*inv_pos(Rdlk) <= Tmax-TuS-TdS;
% gk <= TuS;
% BOs.*inv_pos(RdlMk) <= TdS;
% sum(fk) <= 1;
% 0 <= fk <= 1;
% 0 <= fs <= 1;
% sum(BIsk) == BIs;
% sum(Pdlk) <= Pdmax;
% 0 <= Pdlk <= Pdmax;
% 0 <= PdlM <= Pdmax;
% 0 <= Pulk <= Pumax;
% 0 <= TuS <= Tmax;
% 0 <= TdS <= Tmax;
% 0 <= BIsk <= BIs;
% cvx_end
% end

When I used different cvx_solver, I got different results.

mosek

How canI solve this problem to get the correct optimal value?
Thank you!


(Mark L. Stone) #2

As the warnings tell you, read http://cvxr.com/cvx/doc/advanced.html#the-successive-approximation-method .

The successive approximation method failed using SeDuMi and SDPT3. I will have to defer to someone else as to whether the unbounded result reported when using MOSEK can be trusted.

I would have suggested trying CVX 3.0beta using the ECOS or SCS solvers, which natively support the exponential cone, thereby avoiding use of CVX’s successive approximation method. Except that CVX 3.0beta has some bugs, and I got the following error when attempting to use CVX 3.0beta.

Error using variable (line 50)
Epigraph/hypograph variables cannot be added to sets.
Error in hypograph (line 39)
evalin( ‘caller’, sprintf( '%s ‘, ‘variable’, varargin{2:end}, ’ hypograph_’ ) );
Error in pdom>pdom_cncv (line 66)
hypograph variable y(size(x)) nonnegative
Error in cvx_unary_op (line 29)
y = p.funcs{abs(vu)}( vec(x), varargin{:} );
Error in pdom (line 41)
y = cvx_unary_op( P, x );
Error in inv_pos (line 13)
y = recip( pdom( x ) );


#3

Dear Mark,

Thank you for your reply. I tried to use ECOS solver and I got a result. But it comes with another question.
I have restricted variables like Pulk is a positive value in my constraints, but the Pulk is minus in the result I got.

clear;
clear all;
k = 8; % The number of user in a small cell

PL = 0;

r = ones(1,k);

%Simulation parameters
n = 0.3; % shared fraction, 0<=n<=1
N0 = -147; % noise power spectral density(dBm/Hz)
N0 = power(10,N0/10)/1000; % Converted to w/Hz
Wul = 1e3; Wdl = 1e3; % The uplink and downlink bandwidth (Hz)
Pumax = 100; Pdmax = 1000; % The uplink and downlink power(w)
FC = 10^10; % The cloudlet server processing capacity(CPU cycles/s)
luk = 1.7810^-6; % The amount of energy spent by the mobile device to extract each bit of offloaded data from the video source(J/bit)
ldk = 0.625; % Parameter that captures the mobile receiving energy expenditure per second in the downlink(J/s)
BIk = 1e4
ones(1,k); % Input bits from each user k to the cloudlet in the uplink (1Mbits)
BOk = 1e4ones(1,k); % Out bits from the cloudlet to each user k in the downlink (1Mbits)
%Vk = 2640
BIk; % Processing the input BIk by executing Vk CPU cycles at the cloudlet (CPU cycles)
%Vs = nVk; % Shared CPU cycles
BOs = n
BOk; % Shared output bits that delivered to all users
BIs = n*BIk; % Shared input bits that can be sent by any of the users

%Initialize the z = [Pul,Bls,f,Pdl,PdM,TuS,TdS]
Pulk0 = Pumaxrand(1,k); % The uplink power(w)of user k
%Pdlk0 = Pdmax/k
ones(1,k); % The downlink power(w)to user k
Pdlk0 = rand(1,k);
Pdlk0 = Pdlk0/(sum(Pdlk0))Pdmax;
PdlM0 = Pdmax
rand(1,1); % Transmit power (w) for multicasting
%BIsk0 = BIs/k.*ones(1,k); % A fraction of BIsk bits of the BIs shared bits transmited by user k
BIsk0 = rand(1,k);
BIsk0 = BIsk0/sum(BIsk0).*BIs;
fk0 = rand(1,k);
fk0 = fk0/(sum(fk0));
fs0 = rand(1,1); % Fractions of the processing power FC assigned to run the Vk CPU cycles exclusively for user k and the VS shared CPU cycles
f0 = [fk0,fs0];

Vk = 2640*(BIk-BIsk0+BIs);
Vs = 2640*BIs;

PU0 = r.(Pulk0-PL); % The uplink power after rayleigh fading
Rulk0 = (Wul/k)log2(1+PU0/(N0Wul/k)); % Transmitting rate of user k in the uplink
PD0 = r.
(Pdlk0-PL); % The downlink power after rayleigh fading
Rdlk0 = (Wdl/k)log2(1+PD0/(N0Wdl/k)); % Transmitting rate to user k in the downlink
PM0 = r.(PdlM0-PL); % Multicasting power after rayleigh fading
RdlMk0 = Wdl
log2(1+PM0/(N0*Wdl)); % Transmitting rate to users for multicasting
TuS0 = max(BIsk0./Rulk0); % The time to complete the shared uplink transmissions (s)
TdS0 = max(BOs./RdlMk0); % The downlink transmission time to multicast BOs bits
Tmax = 15; % Maximum latency constraint(0.15s/0.05s)
z0 = [Pulk0,BIsk0,f0,Pdlk0,PdlM0,TuS0,TdS0];
alpha = 10^-5; epsilong = 10^-5; delta0 = rand; % Accuracy parameters

%cvx_solver SeDuMi
cvx_solver ecos 
cvx_begin
    variables Pulk(1,k) BIsk(1,k) fk(1,k) fs Pdlk(1,k) PdlM TuS TdS;
    f = [fk,fs];
    PU = r.*(Pulk-PL);
    Rulk = (Wul/k)*log(1+PU/(N0*Wul/k))/log(2);
    PD = r.*(Pdlk-PL);
    Rdlk = (Wdl/k)*log(1+PD/(N0*Wdl/k))/log(2);
    PM = r.*(PdlM-PL);
    RdlMk = Wdl*log(1+PM/(N0*Wdl))/log(2);
                
    %The overall downlink mobile energy consumption for user k
    Edlk = ((BOk-BOs).*inv_pos(Rdlk)+(BOs.*inv_pos(RdlMk)))*ldk;
    
    %Mobile energy consumption of uplink transmission
    z = [Pulk,BIsk,f,Pdlk,PdlM,TuS,TdS];
    E = (z-z0)*diag(z0)*(z-z0)';
    e1 = Pulk0.*(BIsk0+(BIk-BIsk0)).*inv_pos(Rulk);
    e2 = Pulk0.*(BIsk+(BIk-BIsk0))./Rulk0;
    e3 = Pulk.*(BIsk0+(BIk-BIsk0))./Rulk0;
    e4 = luk*(BIsk+(BIk-BIsk0));
    Eulk = e1+e2+e3+E+e4;
    
    % Rewrite the latency constraints C.2
    g1 = square_pos(BIsk+inv_pos(Rulk));
    g2 = Rulk0.*Rulk0;
    g3 = (g1-BIsk0.^2-1./g2);
    g4 = BIsk0.*(BIsk-BIsk0);
    g5 = (r.*Pulk0)/(N0*Wul/k);
    g6 = (1+g5).*(Rulk0.^4);
    g7 = g4-(Rulk0./g6).*(inv_pos(Rulk)-1./Rulk0);
    gk = 1/2*g3-g7;  
    
    minimize(sum(Eulk+Edlk))               
    subject to 
        (BIk - BIsk0).*inv_pos(Rulk)+(Vk-Vs)/FC.*inv_pos(fk)+Vs/FC*inv_pos(fs)+(BOk-BOs).*inv_pos(Rdlk) <= Tmax-TuS-TdS;   % Constraint C.1
        gk <= TuS;                            % Constraint C.2
        BOs.*inv_pos(RdlMk) <= TdS;           % Constraint C.3
        sum(fk) == 1;                         % Constraint C.4
        0 <= fk;
        0 <= fs <= 1;
        sum(BIsk) == BIs;                     % Constraint C.5
        sum(Pdlk) <= Pdmax;                   % Constraint C.6
        10^-5 < Pdlk <= Pdmax;
        10^-5 < PdlM <= Pdmax;
        10^-5 < Pulk <= Pumax;
        0 <= TuS <= Tmax;
        0 <= TdS <= Tmax;        
        0 <= BIsk <= BIs;
cvx_end

Why does this happen and how canI improve?


(Mark L. Stone) #4

What does cvx_version show? OIm guessing not CVX 3.0beta, because successive approximation method was still used with ecos.

I think somewhere in the combination of CVX and ecos there is a bug. See Why CVX completely ignores the constraints and only solves the unconstrained problem? .


(Erling D.Andersen) #5

These values are about -1.0e-15. You are aware computations are done in finite precision and hence some rounding errors appear. This is just rounding error and those numbers can safely be truncated to 0.

It might be an idea familiarize yourself with a bit numerical analysis.


(Mark L. Stone) #6

@Erling What you write is true.

However, I should have expanded my comment. I had already tried changing the lower bound on Pulk to 1e-1, and still obtained the same solution having Pulk elements -0.25e-15. Therefore, this is not just a matter of satisfying the constraint within tolerance, but rather the constraint being clearly violated, as happened in the link I provided. The original violation was 1e-5, not < 1e-15, because 1e-5 (not 0) is the stated lower bound on Pulk; so that already looked suspicious, which is why I did the further checking. Sorry for not providing all that information.


#7

Dear Mark,
What I have used version of cvx is 2.1 and now I have changed to 3.0 beta. I got the same error like you showed previous reply. It occured errors when I used inv_pos(x) or pow_p(x, -1) I changed to. It makes me strange and I don’t how to solve it.




Thank you!


#8

Dear Erling,
Thanks for your reply! I have tried the advice you suggested but it seems didn’t work. I may need to find other ways to tried.


(Mark L. Stone) #9

There are bugs in CVX 3.0beta and with use of ECOS under CVX.

So at this point I think it comes down to whether the unbounded result from use of MOSEK in CVX:s successive approximation method is correct. As I stated above, I will have to defer to someone else (perhaps @Erling and/or @mcg ) as to whether this result can be trusted.


(Michael C. Grant) #10

I’m afraid there’s not going to be much I can do here. I just don’t have the time these days to do a lot of development on CVX. And the successive approximation approach I built to handle these problems is, as clearly documented, experimental and unsupported. Sometimes it simply doesn’t work.

I can’t give you a timeline when we’ll get 3.0 to the point where it can handle the exponential cone support of ECOS, SCS, and future solvers natively.


#11

Dear @Mark_L_Stone and @mcg,

Anyway, thanks for your help. Maybe I need to change my objective function or constraints to implement the simulation. :slight_smile:


(Erling D.Andersen) #12

The upcoming MOSEK v9 will handle exponential cone directly i.e. it is possible to get rid of the approximation thing. Hence it should be faster and more robust.

We might be able to let you use an early version of MOSEK 9 that will not work with CVX if you interested. Contact MOSEK support.