# Cvx gives infeaible while problem is feasible

Hello,
I run the following model which is mixed-socp even for small dimension but give infeasiblity, while the zeros for all variable is feasible. I will appreciate anyone can help.
thanks
Maziar

Do not use `cvx_precision_best` with Mosek, or any other solver.

1 Like

Hi Mark,I actually tried all options. It doesnt work
m=3;
nn=5;
H=2;
P=1;
D=2;
s=2;
M=1e3;

``````pert= 0

x= 10*rand(3,nn);
xL= x-pert*x;
xU= x+pert*x;
xo= x(:,1);
xoL= xo-pert*xo;
xoU= xo+pert*xo;
x2= 10*rand(H,nn);
x2L= x2-pert*x2;
x2U= x2+pert*x2;
x2o= x2(:,1);
x2oL= x2o-pert*x2o;
x2oU= x2o+pert*x2o;
y2= 10*rand(s,nn);
y2L= y2-pert*y2;
y2U= y2+pert*y2;
y2o=y2(:,1);
y2oL= y2o-pert*y2o;
y2oU= y2o+pert*y2o;
z= 10*rand(D,nn);
zL= z-pert*z;
zU= z+pert*z;
y= zeros(P,nn);
yL= y-pert*y;
yU= y+pert*y;
yo= y(:,1);
yoL= yo-pert*yo;
yoU= yo+pert*yo;

cvx_begin
cvx_solver mosek
cvx_solver_settings('MSK_DPAR_MIO_MAX_TIME',50)
variables Q(m) G(P) N(H) PP(s) mo1 mo2 T(m)
variables K(H) tg A(P) U(P) W(P) Y(s) E(s) F(s)
variables sai(m,nn) fai(P,nn) C(s,nn) tau(H,nn)
variables f(m) t3(m) g(P) u1(P) u2(P) u3(P) v1(s) v2(s) v3(s)
variables n(H) t4(H) Pr(s) dsai(D,nn) sai1(D)
variable O2(P) binary
variable O4(s) binary
variable O6(P,nn) binary
variable O7(s,nn) binary
variable O8(D,nn) binary
variable O10(P) binary
variable O11(P) binary
variable O12(s) binary
variable O13(s) binary
maximize (sum(Q)+ sum(G)+sum(N)+ sum(PP)+ mo1+ mo2 - sum(T) -...
sum(K) -sum(A)- (1/2*(m+s+H+P))*sum(U)- (1/2*(m+s+H+P))*sum(W)-...
sum(Y) -(1/2*(m+s+H+P))*sum(E)- (1/2*(m+s+H+P))*sum(F))
subject to

for j=1:nn
sum(sai(:,j))+ sum(fai(:,j))+sum(dsai(:,j))+mo1 <= 0;
sum(tau(:,j)) -sum(dsai(:,j)) +sum(C(:,j)) +mo2 <= 0;
end

for i=1:m
f(i)- t3(i) <= 0;
-T(i)+ (tg/(m+s+H+P)) <=0;

f(i)*xoU(i)<= Q(i);
Q(i)<= f(i)*xoL(i);

t3(i)*xoU(i)<= T(i);
T(i)<= t3(i)*xoL(i);

for j=1:nn
f(i)*xU(i,j)<= sai(i,j);
sai(i,j)<= f(i)*xL(i,j);
end
end

for p=1:P
-g(p)+ (1/2)*(m+s+H+P)*u2(p)+ (1/2)*(m+s+H+P)*u3(p) <= 0;
-(1/2)*(m+s+H+P)*u2(p)+ (1/2)*(m+s+H+P)*u3(p) <=1;

-M*O2(p)+g(p)*yoL(p)<= G(p);
G(p)<= g(p)*yoU(p)+ M*O2(p);
-M*(1-O2(p))+g(p)*yoU(p)<= G(p);
G(p)<= g(p)*yoL(p)+ M*(1-O2(p));

-M*O11(p)+u1(p)*sqrt(yoL(p))<= A(p);
A(p)<= u1(p)*sqrt(yoU(p))+ M*O11(p);
-M*(1-O11(p))+ u1(p)*sqrt(yoU(p))<= A(p);
A(p)<= u1(p)*sqrt(yoL(p))+ M*(1-O11(p));

-M*O10(p)+u2(p)*yoL(p)<= U(p);
U(p)<= u2(p)*yoU(p) +M*O10(p);
-M*(1-O10(p))+u2(p)*yoU(p)<= U(p);
U(p)<= u2(p)*yoL(p) +M*(1-O10(p));

u3(p)*yoL(p)<= W(p);
W(p)<= u3(p)*yoU(p);

for j=1:nn
-M*O6(p,j)+g(p)*yL(p,j)<= fai(p,j);
fai(p,j)<= g(p)*yU(p,j) +M*O6(p,j);
-M*(1-O6(p,j))+g(p)*yU(p,j)<= fai(p,j);
fai(p,j)<= g(p)*yL(p,j) +M*(1-O6(p,j));
end
end

for r=1:s
-Pr(r)+ (1/2)*(m+s+H+P)*v2(r)+ (1/2)*(m+s+H+P)*v3(r) <= 0;
-(1/2)*(m+s+H+P)*v2(r)+ (1/2)*(m+s+H+P)*v3(r) <=1;

-M*O4(r)+Pr(r)*y2oL(r)<= PP(r);
PP(r)<= Pr(r)*y2oU(r)+ M*O4(r);
-M*(1-O4(r))+Pr(r)*y2oU(r)<= PP(r);
PP(r)<= Pr(r)*y2oL(r)+ M*(1-O4(r));

-M*O12(r)+ v2(r)*y2oL(r)<= E(r);
E(r)<= v2(r)*y2oU(r)+ M*O12(r);
-M*(1-O12(r))+ v2(r)*y2oU(r)<= E(r);
E(r)<= v2(r)*y2oL(r)+ M*(1-O12(r));

v3(r)*y2oL(r)<= F(r);
F(r)<= v3(r)*y2oU(r);

-M*O13(r)+ v1(r)*sqrt(y2oL(r))<= Y(r);
Y(r)<= v1(r)*sqrt(y2oU(r))+ M*O13(r);
-M*(1-O13(r))+ v1(r)*sqrt(y2oU(r))<= Y(r);
Y(r)<= v1(r)*sqrt(y2oL(r))+ M*(1-O13(r));

for j=1:nn

-M*O7(r,j)+Pr(r)*y2L(r,j)<= C(r,j);
C(r,j)<= Pr(r)*y2U(r,j) +M*O7(r,j);
-M*(1-O7(r,j))+Pr(r)*y2U(r,j)<= C(r,j);
C(r,j)<= Pr(r)*y2L(r,j) +M*(1-O7(r,j));
end
end

for h=1:H
n(h)- t4(h) <= 0;
-K(h)+ (tg/(m+s+H+P)) <=0;

n(h)*x2oU(h)<= N(h);
N(h)<= n(h)*x2oL(h);

t4(h)*x2oU(h)<= K(h);
K(h)<= t4(h)*x2oL(h);

for j=1:nn

n(h)*x2U(h,j)<= tau(h,j);
tau(h,j)<= n(h)*x2L(h,j);
end
end

for d=1:D
for j=1:nn

-M*O8(d,j)+sai1(d)*zL(d,j)<= dsai(d,j);
dsai(d,j)<= sai1(d)*zU(d,j) +M*O8(d,j);
-M*(1-O8(d,j))+sai1(d)*zU(d,j)<= dsai(d,j);
dsai(d,j)<= sai1(d)*zL(d,j) +M*(1-O8(d,j));
end

end

tg<=-1;
t3 <= 0; t4 <= 0; f <= 0; n <= 0;
u3>= 0;
v3>= 0;
for p=1:P
norm([u1(p); u2(p)])<=u3(p);
end

for r=1:s
norm([v1(r); v2(r)])<=v3(r);
end

cvx_end
out.worst_case1=cvx_optval;``````

Your problem appears to be unbounded, at least with the two sets of random numbers I generated.

Mosek reported primal infeasible or unbounded with solution status UNKNOWN. Mosek was provided the dual problem by CVX, and CVX provided the status Failed (with or without the cvx_solver_settings in your code).

I then removed the binary declaration and constrained all of what were the binary variables to all zeros. Mosek (which was provided the dual by CVX), reported primal infeasible, which resulted in CVX providing status (primal) unbounded. The same CVX status of unbounded occurred when I ran this same modified program in SeDuMi and SDPT3. Even reducing M to 1 (or even 0) from 1e3 had the same outcome. Even the continuous relaxation of the binaries to [0,1] resulted in unbounded. If the problem is unbounded with binary variables constrained to zero, then the original problem must also be unbounded - I merely helped out the solver.

Try following the advice at https://yalmip.github.io/debuggingunbounded , which also applies to CVX.

I will defer to the Mosek people to provide any further commentary or assessment.

Below I show (for one common set of random numbers) the Mosek output, first from the code as in your post, and then when I removed the binary declarations and constrained those variables to all zeros:

Code as posted:

## Calling Mosek 9.3.6: 374 variables, 239 equality constraints

MOSEK Version 9.3.7 (Build date: 2021-10-11 10:42:47)
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 239
Cones : 3
Scalar variables : 374
Matrix variables : 0
Integer variables : 34

Optimizer started.
Mixed integer optimizer started.
Presolve started.
Presolve terminated. Time = 0.00
Presolved problem: 81 variables, 80 constraints, 259 non-zeros
Presolved problem: 0 general integer, 26 binary, 55 continuous
Clique table size: 0
BRANCHES RELAXS ACT_NDS DEPTH BEST_INT_OBJ BEST_RELAX_OBJ REL_GAP(%) TIME
0 0 1 0 0.0000000000e+00 NA NA 0.1
0 1 1 0 0.0000000000e+00 NA NA 0.1

Objective of best integer solution : 0.000000000000e+00
Best objective bound : 0.000000000000e+00
Construct solution objective : Not employed
User objective cut value : Not employed
Number of cuts generated : 0
Number of branches : 0
Number of relaxations solved : 1
Number of interior point iterations: 0
Number of simplex iterations : 0
Time spend presolving the root : 0.00
Time spend optimizing the root : 0.00
Mixed integer optimizer terminated. Time: 0.14

Optimizer terminated. Time: 0.20

Integer solution solution summary
Problem status : PRIMAL_INFEASIBLE_OR_UNBOUNDED
Solution status : UNKNOWN
Primal. obj: 0.0000000000e+00 nrm: 1e+03 Viol. con: 0e+00 var: 0e+00 cones: 0e+00 itg: 0e+00
Optimizer summary
Optimizer - time: 0.20
Interior-point - iterations : 0 time: 0.00
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 1 time: 0.14

Status: Failed
Optimal value (cvx_optval): NaN

++++++++++++++++++++++++++++++++++++++++++

When removed the binary declarations and constrained those variables to all zeros:

## Calling Mosek 9.3.6: 263 variables, 101 equality constraints For improved efficiency, Mosek is solving the dual problem.

MOSEK Version 9.3.7 (Build date: 2021-10-11 10:42:47)
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 101
Cones : 3
Scalar variables : 263
Matrix variables : 0
Integer variables : 0

Optimizer started.
Presolve started.
Eliminator - tries : 0 time : 0.00
Lin. dep. - tries : 0 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Optimizer terminated. Time: 0.09

Interior-point solution summary
Problem status : PRIMAL_INFEASIBLE
Solution status : PRIMAL_INFEASIBLE_CER
Dual. obj: 1.0000000000e+06 nrm: 8e+06 Viol. con: 0e+00 var: 0e+00 cones: 0e+00
Optimizer summary
Optimizer - time: 0.09
Interior-point - iterations : 0 time: 0.03
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00

Status: Unbounded
Optimal value (cvx_optval): +Inf

Re-running the feasibility problem, but constraining `tg == 0`, Mosek (and CVX) reported infeasible. Therefore, per Mosek, at least with these random numbers, the all zero solution is not feasible, contrary to your original assertion.