Inaccurate/Solved by CVX with constraint violation

1

Hello. I am trying to solve a task (data) assignment with linear constraints using CVX. However, the the constraints are violated and the status is inaccurate/solved. Here is the code snippet.

%x is my variable with 3 dimensions (K x N x M)
%qk is (K x 1) vector
%Cap is (1 x N x M) matrix where some values are zero
cvx_begin
variable x(K,N,M);
minimize -sum(sum(sum(x,3),2)./qk)
subject to
sum(sum(x,3),2)<=qk %constraint 1
sum((x.*Ck),1)<=Cap %constraint 2
x>=o %constraint 3
x<=Qk
cvx_end

The status after running the code is Inaccurate/solved. The value of variable x is negative and very small on the indexes where it should have 0 value. Hence the constraint 2 and constraint 3 are violated.

Please guide whats wrong here.

1 Like
2

This is a Linear Programming problem. If inaccurate/solved is reported, I am guessing that the input data is badly scaled (very large or small magnitude non-zero coefficients in the input data). You should try to improve the scaling by changing units.

Note that solver tolerance level constraint violations are allowed in a reported optimum. Inaccurate/solved means that the solver was not able to solve this to the requested (standard) tolerance.

If you have access to Mosek or Gurobi, try specifying one of those as solver. Not only are they more numerically robust than the free solvers. they also print information in the displayed solver log warning of large or small model coefficients, which can cause numerical difficulties such as you experienced.

if using Gurobi, you can include the statement
cvx_solver_settings('NumericFocus',2)
to make it more robust to numerical challenges.

If you show us the solver output, perhaps someone can say more.

1 Like
3

Thank you for quick response. I am going to follow the suggestions provided by you.

On more question. Would it be better if I solve this problem using linprog in matlab? or should i keep trying with the cvx tool?

4

No matter which tool you use, find the difficulty and fix it.

5

One other possibility, although much less likely, is that the difficulty is caused by (nearly) dependent constraints. if this were the cause, Gurobi and Mosek’s presolve would probably handle that just fine, whereas SeDuMi and SDPT3 could experience numerical difficulties. Because you have provided neither input data nor solver output, I can’t assess whether this situation is occurring in your problem.

6

Please check the code below for input data.

%%  Input variables 
Tasks=[50];
points=length(Tasks);
obj=zeros(1,points);
M=2;
T=30;  % 1 hour 60 min
No=25; % vehicles at time t=0
tau=zeros(M,50);
Emn=zeros(M,50);
mu=[11.62 13.65]./60;
lambda=[11.12 13.03]./60;
for kt=1:points
    K=Tasks(1,kt);
    qk=zeros(K,1); % size of each task in bits
    ck=zeros(K,1); % computation required for each task in cycles/bit
    gk=zeros(K,1); % delay threshold of each task in seconds
    for k=1:K
        a=10e6;
        b=50e6;
        qk(k,1)=a+(b-a)*rand;
        a=1000;
        b=1500;
        ck(k,1)=a+(b-a)*rand;
        a=150;
        b=3600;
        gk(k,1)=a+(b-a)*rand;
    end

for m=1:M
    for t=1:T
        x=exp((mu(1,m)-lambda(1,m))*t);
        Emt(m,t)=floor(No*exp((mu(1,m)-lambda(1,m))*t)); %MxT
    end
end

for m=1:M
    n=1;
    Emn(m,n)=Emt(m,1);
    to=1;
    for t=2:T
        if Emt(m,t)~=Emn(m,n)
            tau(m,n)=t-to;
            to=t;
            n=n+1;
            Emn(m,n)=Emt(m,t); % expected number of vehicles during each slot
        end
        if t==T
            tau(m,n)=T-sum(tau(m,:));
        end
    end
end
totalslots=sum((tau(:,:)~=0),2);
Nmax=max(totalslots);
tau=tau(:,1:Nmax)*60;
Emn=Emn(:,1:Nmax);

%%%%%%%%% comp. capacity of vehicles %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
F=zeros(M,Nmax);
mean=1e9;
sigma=0.3e9;
for m=1:M
    EMN=nonzeros(Emn(m,:));
    N=length(EMN);
    for n=1:N
        sz=Emn(m,n); %number of vehicles in slot n
        compcap = normrnd(mean,sigma,[1,sz]);
        totcompcap=sum(compcap);
        F(m,n)=totcompcap;
    end
end
cap=tau.*F;

Ck=repmat(ck,1,Nmax,M);
Gk=repmat(gk,1,Nmax,M);
Qk=repmat(qk,1,Nmax,M);
for m=1:M
    for n=1:Nmax
        for k=1:K
            if(F(m,n)==0)
                Cap(1,n,m)=0;
            else                
                Fm(k,n,m)=F(m,n); 
                Cap(1,n,m)=cap(m,n);
            end
        end
    end
end
o=zeros(K,Nmax,M);

The output is pasted below.

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

num. of constraints = 1000
dim. of linear var = 2070

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|1.8e+06|4.5e+01|2.4e+18| 4.708209e+15 0.000000e+00| 0:0:00| spchol 1 1
1|0.976|0.967|4.4e+04|1.5e+00|7.9e+16| 1.122326e+14 -4.880831e+04| 0:0:00| spchol 1 1
2|0.953|0.985|2.0e+03|2.2e-02|1.2e+15| 3.002522e+12 -1.567647e+04| 0:0:00| spchol 1 1
3|0.991|0.886|1.8e+01|2.5e-03|1.4e+14| 1.822109e+12 -2.726057e+04| 0:0:00| spchol 1 1
4|1.000|0.962|4.4e-05|9.8e-05|7.0e+12| 1.684505e+12 -6.427311e+02| 0:0:01| spchol 1 1
5|1.000|0.424|4.5e-06|5.6e-05|5.1e+12| 1.442882e+12 -1.109443e+02| 0:0:01| spchol 1 1
6|1.000|0.586|5.1e-07|2.3e-05|2.8e+12| 1.064458e+12 3.496964e+01| 0:0:01| spchol 1 1
7|1.000|0.779|7.1e-08|5.1e-06|9.9e+11| 6.012234e+11 4.201797e+01| 0:0:01| spchol 1 1
8|1.000|0.894|1.8e-08|5.5e-07|2.5e+11| 2.240577e+11 4.702660e+01| 0:0:01| spchol 1 1
9|1.000|0.912|3.8e-09|4.8e-08|1.3e+10| 1.234299e+10 4.711449e+01| 0:0:01| spchol 1 1
10|0.985|0.984|9.9e-10|7.8e-10|2.0e+08| 1.893187e+08 4.711939e+01| 0:0:01| spchol 1 1
11|0.989|0.989|3.3e-10|1.0e-11|2.2e+06| 2.099657e+06 4.711947e+01| 0:0:01| spchol 1 1
12|0.989|0.989|6.0e-09|3.3e-13|2.7e+04| 2.312907e+04 4.711970e+01| 0:0:01| spchol 1 1
13|0.987|0.989|7.7e-07|6.7e-15|3.9e+02| 3.214404e+02 4.712429e+01| 0:0:01| spchol 1 1
14|0.837|0.972|7.8e-07|7.1e-16|6.6e+01| 6.898113e+01 4.729968e+01| 0:0:01| spchol 1 1
15|1.000|0.906|7.2e-07|3.1e-16|3.6e+01| 4.645839e+01 4.780776e+01| 0:0:01| spchol 1 1
16|1.000|0.951|6.5e-07|8.1e-17|7.4e+00| 2.450732e+01 4.818591e+01| 0:0:01| spchol 1 1
17|0.989|0.969|6.3e-07|1.0e-16|4.4e-01| 1.934589e+01 4.834032e+01| 0:0:01| spchol 1 1
18|0.982|0.975|6.2e-07|5.5e-17|1.0e-02| 1.925014e+01 4.835960e+01| 0:0:01| spchol 1 1
19|0.971|0.969|6.2e-07|7.7e-17|5.1e-04| 1.946460e+01 4.836064e+01| 0:0:01| spchol 1 1
20|0.987|0.985|6.2e-07|1.2e-16|2.1e-05| 1.954642e+01 4.836076e+01| 0:0:01| spchol 1 1
21|0.986|0.984|6.2e-07|5.5e-17|7.8e-07| 1.959370e+01 4.836077e+01| 0:0:01| spchol 1 1
22|0.990|0.988|6.2e-07|3.4e-21|2.0e-08| 1.960524e+01 4.836078e+01| 0:0:01| spchol 1 1
23|0.992|0.988|6.2e-07|7.7e-17|4.3e-10| 1.960976e+01 4.836078e+01| 0:0:01| spchol 1 1
24|0.994|0.989|6.2e-07|1.3e-16|8.3e-12| 1.961017e+01 4.836078e+01| 0:0:02| spchol 1 1
25|0.998|0.989|6.2e-07|6.7e-17|1.3e-13| 1.961018e+01 4.836078e+01| 0:0:02|
stop: relative gap < infeasibility

number of iterations = 25
primal objective value = 1.96101688e+01
dual objective value = 4.83607761e+01
gap := trace(XZ) = 8.28e-12
relative gap = 1.20e-13
actual relative gap = -4.17e-01
rel. primal infeas (scaled problem) = 6.16e-07
rel. dual " " " = 1.28e-16
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 2.8e+03, 5.0e+07, 2.5e+13
norm(A), norm(b), norm© = 3.9e+04, 1.0e+00, 2.5e+13
Total CPU time (secs) = 1.55
CPU time per iteration = 0.06
termination code = -1
DIMACS: 6.2e-07 0.0e+00 4.1e-16 0.0e+00 -4.2e-01 1.2e-13

Status: Inaccurate/Solved
Optimal value (cvx_optval): -48.3608

7

I have provided the code and solver output for your assessment. Please have a look.

8

Various of your input arrays have huge magnitude elements, up to 9e12 with the random numbers I drew, Some numbers are getting huge due to exponentiation in your code. These huge magnitude numbers will cause great difficulties for any double precision solver, including all solvers callable from CVX.

You need to improve the problem scaling to get all the non-zero input data much closer to 1 in magnitude.

9

Thank you for pin pointing the issue now I will try to fix it.

10

I have tried to scale down the values of input arguments and the status is changed to Solved. However, the values of variables in output are still negative and the constraints are violated. Please provide your suggestion. Thank you.

11

Please show us the new formulation, and all solver and CVX output. Show us the maximum element of all the input arrays. Also show us min(min(min(x))), so we can see how negative it is.

Note that the code, as displayed in your first post has
x>=o, where o is the letter o, not the number 0. CVX accepts that, but I don’t understand what it does with it.

-eps >= o returns a 50 by 10 by 2 logical array of zeros.
eps >= o returns a 50 by 10 by 2 logical array of ones.
So perhaps (???) CVX is processing the x>=o constraint to have the same effect as x>=0 would, but i don’'t know. I certainly recommend correcting the typo in your code.

12

o is 3D matrix of zeros and has same dimensions as x. It is included in the code

o=zeros(K,Nmax,M);

13

O.k., that explains that.

14

The input arguments are scaled down as follows:
max(qk)=4.997
max(ck)=1.4994
max(cap)=11.87

The output has
min(min(min(x)))= -1.6358e-11

CVX output is as follows:
Calling SDPT3 4.0: 2070 variables, 1000 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 1000
dim. of linear var = 2070

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|1.9e+02|4.5e+01|9.6e+06| 1.331298e+05 0.000000e+00| 0:0:00| spchol 1 1
1|0.895|0.942|2.0e+01|2.7e+00|6.9e+05| 1.155345e+05 -1.109873e+03| 0:0:01| spchol 1 1
2|1.000|0.869|1.5e-05|3.9e-01|1.3e+05| 6.649383e+04 -4.430331e+01| 0:0:01| spchol 1 1
3|1.000|0.580|1.5e-06|1.7e-01|5.3e+04| 2.826176e+04 1.814890e+01| 0:0:01| spchol 1 1
4|1.000|0.830|2.2e-07|3.2e-02|8.3e+03| 5.631170e+03 2.487063e+01| 0:0:01| spchol 1 1
5|1.000|0.945|7.7e-09|2.8e-03|9.6e+02| 8.979547e+02 2.579398e+01| 0:0:01| spchol 1 1
6|0.950|1.000|4.2e-08|3.3e-04|5.0e+01| 7.303530e+01 2.662302e+01| 0:0:01| spchol 1 1
7|1.000|0.849|3.8e-07|1.3e-04|6.1e+00| 3.448258e+01 2.923509e+01| 0:0:01| spchol 1 1
8|0.983|0.945|3.7e-08|1.7e-05|2.1e-01| 3.009115e+01 2.997161e+01| 0:0:01| spchol 1 1
9|0.982|0.976|3.0e-09|1.4e-06|1.0e-02| 3.000272e+01 2.999941e+01| 0:0:01| spchol 1 1
10|0.989|0.989|4.1e-11|1.1e-07|5.2e-04| 3.000003e+01 3.000000e+01| 0:0:01| spchol 2 2
11|1.000|0.989|1.1e-09|1.3e-09|1.1e-05| 3.000001e+01 3.000000e+01| 0:0:01| spchol 2 2
12|1.000|0.989|3.3e-10|1.9e-11|2.0e-07| 3.000000e+01 3.000000e+01| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08

number of iterations = 12
primal objective value = 3.00000001e+01
dual objective value = 3.00000000e+01
gap := trace(XZ) = 1.95e-07
relative gap = 3.20e-09
actual relative gap = 1.90e-09
rel. primal infeas (scaled problem) = 3.35e-10
rel. dual " " " = 1.87e-11
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 1.9e+02, 1.5e+01, 9.1e+01
norm(A), norm(b), norm© = 6.9e+01, 1.7e+01, 1.0e+02
Total CPU time (secs) = 1.38
CPU time per iteration = 0.12
termination code = 0
DIMACS: 3.0e-09 0.0e+00 1.7e-10 0.0e+00 1.9e-09 3.2e-09

Status: Solved
Optimal value (cvx_optval): -50

15

-1e-11 is within solver tolerance of zero.

if you can’t accept that as meeting your constraint, you need to modify the constraint to
x >= small_positive_number
where small_positive_number is perhaps 1e-6 or maybe as small as 1e-8. When that constraint is satisfied within solver tolerance, the value of x will not be even slightly negative.

Or incude this statement after cvx_end
x(x<0) = 0;
which zeros out the slightyl negative elements of x.

Please read http://cvxr.com/cvx/doc/solver.html#controlling-precision m and http://cvxr.com/cvx/doc/solver.html#interpreting-the-results , but i don’t recommend you change any of the settings. Rather, read thos sections to gain understanding.

16

I got your point and I will read the provided links for better understanding. Thank you for the guidance.