CVX failed for my problem even without any objective function and constraints


#1

This is my problem whose cvx_status is “failed”.

clear
clc

K = 4;
p_l = 0.0001;
k = 1e-26;
T = 1;
C = 1e3;

mode = [0 0 0 0]’;

cvx_begin
variable e_local(K) nonnegative;

opt_f = (1 - mode) .* ( p_l*ones(K, 1) ./ (2*k) ).^(1/3) + mode .* ( e_local ./ (k*T) - (p_l ./ k) ).^(1/3);
opt_t = (1 - mode) .* ( 2*e_local ./ (3*p_l) ) + mode .* T;
b_local = opt_f .* opt_t ./ C;

cvx_end

This problem does not include objective function and constraints, but it does not work with the following output:

Calling SDPT3 4.0: 28 variables, 12 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 12
dim. of sdp var = 16, num. of sdp blk = 8
dim. of linear var = 4
number of nearly dependent constraints = 8
To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 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.0e+27|1.4e+04|8.0e+27|-4.000000e+23 0.000000e+00| 0:0:00| chol 1 2
1|0.000|0.000|2.0e+27|1.4e+04|8.1e+27|-4.000000e+23 0.000000e+00| 0:0:00| chol 1 2
2|0.981|0.981|3.8e+25|2.7e+02|1.6e+26| 5.846696e+23 0.000000e+00| 0:0:00|
sqlp stop: primal or dual is diverging, 9.2e+21

number of iterations = 2
Total CPU time (secs) = 0.09
CPU time per iteration = 0.05
termination code = 3
DIMACS: 3.8e+25 0.0e+00 5.4e+02 0.0e+00 1.0e+00 2.7e+02


Status: Failed
Optimal value (cvx_optval): NaN

However, the following reformulated problem by inserting mode = [0 0 0 0]’ explicitly,

cvx_begin
variable e_local(K) nonnegative;

    opt_f = ( p_l*ones(K, 1) ./ (2*k) ).^(1/3);
    opt_t = ( 2*e_local ./ (3*p_l) );
    b_local = opt_f .* opt_t ./ C;

cvx_end

works well with the following output:

Homogeneous problem detected; solution determined analytically.
Status: Solved
Optimal value (cvx_optval): +0

I want to solve the problem in the first form because I am trying to solve the problem with changing the mode.
n someone give me some help with my problem?


(Mark L. Stone) #2

We’ll have to see what @mcg says. I don;t know what CVX is sending to the solver on this problem. This seems like a CVX bug to me, because there should be no problem for CVX to send to the solver.

Can you try adding an objective function and/or constraints that you really want and see what happens?

Edit: Well, actually there is a (vector) constraint, variable e_local(K) nonnegative constrains e_local to be nonnegative, as trivial a constraint as that appears to be in isolation. Perhaps the bad scaling of the rest of the problem winds up causing difficulty in finding a feasible solution to variable e_local(K) nonnegative as a result of transformations applied by CVX and/or the solver.


#3

First, I am trying to solve the following feasibility problem (without objective function):

K = 4;
p_r = 0.0001;
p_t = 0.001;
p_l = 0.0001;
k = 1e-26;
C = 1e3;
zeta = 0.9;
h = 1e-3 * [0.1471 0.0730 0.1624 0.4562]’;
g = h;
Q = 0;
O = 0.1;
B = 2e6;
T = 1;
sigma_square = 1e-9;
P = 10^(4/10);
A = O ./ ( log2(1 + h*P/sigma_square) );
R_min = 0;
mode = [0 0 0 0]’;

cvx_begin
variable tau_0 nonnegative;
variable tau(K) nonnegative;
variable e_local(K) nonnegative;
variable e_offl(K) nonnegative;
variable b_offl(K) nonnegative;

opt_f = (1 - mode) .* ( p_l*ones(K, 1) ./ (2*k) ).^(1/3) + mode .* ( e_local ./ (k*T) - (p_l ./ k) ).^(1/3);
opt_t = (1 - mode) .* ( 2*e_local ./ (3*p_l) ) + mode .* T;
b_local = opt_f .* opt_t ./ C;

subject to   
    e_local + p_r*tau_0 + e_offl + p_t*tau + p_r*(A.*b_offl) <= zeta.*h*tau_0*P + Q
    b_local + B*b_offl >= R_min
    tau_0 + sum(tau) + sum(A.*b_offl) <= T
    b_offl <= -rel_entr(tau, tau + (g./sigma_square).*e_offl) / log(2)  

cvx_end

This problem also prints out “failed” when CVX is applied.
Actually, I know this problem is feasible because when I set
“e_local = 0 (Then, b_local = 0)
tau_0 = T
tau = zeros(K, 1)
b_offl = 0
e_offl = 0”,
all the constraints are satisfied.


(Mark L. Stone) #4

I think numbers such as k = 1e-26 are beyond the capability of the solver to deal with “correctly”. Try to reformulate your problem with better scaling.


#5

Thanks for your response.
However, I think it may be difficult to change those values because they reflect the reality in my field.
Can you give me any suggestions to reformulate problem without changing the values to avoid this issue?

Further, following your comment, I have changed the number k to 1e-6.
Now, CVX does not print out “failed”, but it prints out “infeasible”.
As I mentioned above, I am almost sure that the problem is feasible.
Do you have any ideas?


(Mark L. Stone) #6

Change the units to make non-zero numbers closer to 1 in magnitude.


#7

Thank you very much for your comments.
Following your comments, I have reformulated my problem by changing the units.

micro_k = k * 1e18;

cvx_begin
    variable tau_0 nonnegative;
    variable tau(K) nonnegative;
    variable e_local(K) nonnegative; 
    variable e_offl(K) nonnegative;
    variable b_offl(K) nonnegative;        

    % Case 1 + Case 2
    opt_f = 1e6 * (1 - mode) .* ( p_l*ones(K, 1) ./ (2*micro_k) ).^(1/3) + mode .* ( e_local ./ (micro_k*T) - (p_l ./ micro_k) ).^(1/3);
    opt_t = (1 - mode) .* ( 2*e_local ./ (3*p_l) ) + mode .* T;
    b_local = opt_f .* opt_t ./ C;
        
    subject to   
        e_local + p_r*tau_0 + e_offl + p_t*tau + p_r*(A.*b_offl) <= zeta.*h*tau_0*P + Q
        b_local + B*b_offl >= R_min
        tau_0 + sum(tau) + sum(A.*b_offl) <= T
        b_offl <= -rel_entr(tau, tau + (g./sigma_square).*e_offl) / log(2)  
cvx_end

However, as I have said above, CVX now prints out “infeasible” instead of “failed”.
It should be feasible because there exists a feasible solution:
“e_local = 0 (Then, b_local = 0)
tau_0 = T
tau = zeros(K, 1)
b_offl = 0
e_offl = 0”,
which satisfies all the constraints.

Can you give me some help with this problem?


Additional comments:
I add this comments because it may help you with your response.

I just tried CVX with cvx_solver “sedumi” and cvx_precision “low”,
then CVX gave me “solved” output.


(Mark L. Stone) #8

Using your feasible values

opt_f =

   1.0e+07 *

   1.709975946676697
   1.709975946676697
   1.709975946676697
   1.709975946676697

which are rather large numbers.

Your problem is still numerically very poor. You have more work to do to get it in shape to where it can be relaibly solved by double precision solvers.


#9

Thank you so much your comments.

Following your comments, I have scaled my problem as follows.

clear
clc

K = 4;
sigma_square = 1e-9;
d = 2.5;
C = 1e3;
k = 1e-26;
scale = 1e8;
scaled_k = k * scale^3;
zeta = 0.9;
p_r = 0.0001;
p_t = 0.001; % circuit power = 1 mW
p_l = 0.0001;
Q = 0;
O = 0.1;
B = 2e6;
T = 1;
R_min = 0;
alpha = 2.6;

h = 1.0e-03 * [0.1471 0.0730 0.1624 0.4562]’;
g = h;

P = 10^(4/10);
A = O ./ ( log2(1 + h*P/sigma_square) );
mode = [0 0 0 0]’;

cvx_begin
cvx_precision low

variable tau_0 nonnegative;
variable tau(K) nonnegative;
variable e_local(K) nonnegative; 
variable e_offl(K) nonnegative;
variable b_offl(K) nonnegative;        


scaled_opt_f = (1 - mode) .* ( p_l*ones(K, 1) ./ (2*scaled_k) ).^(1/3) + mode .* ( e_local ./ (scaled_k*T) - (p_l ./ scaled_k) ).^(1/3);
opt_t = (1 - mode) .* ( 2*e_local ./ (3*p_l) ) + mode .* T;
scaled_b_local = scaled_opt_f .* opt_t ./ C;

subject to   
    e_local + p_r*tau_0 + e_offl + p_t*tau + p_r*(A.*b_offl) <= zeta.*h*tau_0*P + Q
    scaled_b_local + (B/scale)*b_offl >= R_min/scale
    tau_0 + sum(tau) + sum(A.*b_offl) <= T
    b_offl <= -rel_entr(tau, tau + (g./sigma_square).*e_offl) / log(2)  

cvx_end

However, CVX prints out “infeasible” again for the problem, which should be feasible as I mentioned above.
Here, when the second term of “scaled_opt_f” is eliminated (equivalent problem because mode = [0 0 0 0]’), CVX can solve this problem.

cvx_begin
cvx_precision low

variable tau_0 nonnegative;
variable tau(K) nonnegative;
variable e_local(K) nonnegative; 
variable e_offl(K) nonnegative;
variable b_offl(K) nonnegative;    

scaled_opt_f = (1 - mode) .* ( p_l*ones(K, 1) ./ (2*scaled_k) ).^(1/3);
opt_t = (1 - mode) .* ( 2*e_local ./ (3*p_l) ) + mode .* T;
scaled_b_local = scaled_opt_f .* opt_t ./ C;

subject to   
    e_local + p_r*tau_0 + e_offl + p_t*tau + p_r*(A.*b_offl) <= zeta.*h*tau_0*P + Q
    scaled_b_local + (B/scale)*b_offl >= R_min/scale
    tau_0 + sum(tau) + sum(A.*b_offl) <= T
    b_offl <= -rel_entr(tau, tau + (g./sigma_square).*e_offl) / log(2)  

cvx_end

Due to the scaling, the obtained feasible solution seems to be not so large.
I think the second term of “scaled_opt_f” is problematic, which is effectively a zero vector.
However, constants in the second term also seem to be reasonable in terms of scaling:
scaled_k*T = 0.01
p_l ./ scaled_k = 0.01

Do you have any ideas about this issue?


(Mark L. Stone) #10

Just keep trying. Look at intermediate quantities, and beware of any non-zero large or small magnitude numbers, as well as very disparate numbers in different terms.


#11

Thank you for your helpful comments.
Following your comments, I think I can handle the problem now.