"Infeasible " in a code with exp( ) that should be feasible

1

Hi! Everyone! The following is my code. q_mn=qL is clearly feasible . but the result is infeasible. Why? Thanks for your help.

M=4;
H=100;
N=200;
I=40;
b0=-60;
Pb=43;
Pu=23;
s_i =[

  125.8895  -24.5023;
  162.3168  -47.3766;
 -149.2053  106.2067;
  165.3503  118.0800;
   52.9437 -125.2510;
 -160.9838   -4.0942;
  -88.6007  -21.7655;
   18.7526   58.5252;
  183.0027   83.7459;
  185.9554  101.8747;
 -136.9548  -89.5900;
  188.2371   71.8811;
  182.8668   62.0392;
   -5.8497 -134.9553;
  120.1122 -152.4009;
 -143.2455   -0.6544;
  -31.2955  183.8976;
  166.2942  -63.8457;
  116.8829   34.1071;
  183.7970 -110.4752;
   62.2963  100.5068;
 -185.7153  -97.9620;
  139.6517    2.3828;
  173.5973   79.6307;
   71.4941  156.3613;
  103.0961  183.7166;
   97.2530   18.8862;
  -43.1092 -144.5502;
   62.1912 -140.2824;
 -131.5253  -96.9967;
   82.4184  136.2869;
 -187.2669  -98.2871;
  -89.2308  125.7139;
 -181.5314 -102.5900;
 -161.1473  171.7054;
  129.3831  -60.0065;
   77.9314 -121.3619;
  -73.1602  -99.5665;
  180.0888   46.4179;
 -186.2216  -10.6845];
q0=[-100 100;100,100;100,-100;-100,-100 ];
qL=permute(repmat(q0,1,1,N),[1 3 2]);
cvx_begin 
variables  q_mn(M,N,2)    x_imn(I,M,N) ;
minimize(1) 
    subject to             
permute( 2* sum( permute( (repmat( qL , 1, 1, 1, I )- permute( repmat( s_i , 1, 1, M , N ), [ 3 4 2 1 ])).* repmat(q_mn-qL ,1,1,1,I)  , [ 1 2 4 3 ] ) , 4 ) +sum(permute((repmat( qL , 1, 1, 1, I )- permute( repmat( s_i , 1, 1, M , N ), [ 3 4 2 1 ])).^2 ,[1 2 4 3]),4)+H^2, [3 1 2]) >= exp(-x_imn+log(10)*(b0/10+Pu/10-6)); 

cvx_end

output:
Calling Mosek_2 9.2.47: 128000 variables, 65600 equality constraints
For improved efficiency, Mosek_2 is solving the dual problem.

MOSEK Version 9.2.47 (Build date: 2021-6-15 12:45:51)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 65600
Cones : 32000
Scalar variables : 128000
Matrix variables : 0
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.05
Lin. dep. - number : 0
Presolve terminated. Time: 0.33
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 65600
Cones : 32000
Scalar variables : 128000
Matrix variables : 0
Integer variables : 0

Optimizer - threads : 2
Optimizer - solved problem : the primal
Optimizer - Constraints : 33600
Optimizer - Cones : 32001
Optimizer - Scalar variables : 128001 conic : 128001
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.11 dense det. time : 0.00
Factor - ML order time : 0.02 GP order time : 0.00
Factor - nonzeros before factor : 1.32e+05 after factor : 1.32e+05
Factor - dense dim. : 2 flops : 1.03e+06
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 9.5e-01 4.5e+04 2.6e+04 0.00e+00 2.649082877e+04 0.000000000e+00 1.0e+00 0.70
1 1.9e-06 9.3e-02 2.8e+04 -1.00e+00 1.878684987e+07 0.000000000e+00 2.0e-06 1.17
2 6.3e-08 3.0e-03 3.6e+04 -1.00e+00 -1.540731359e+08 0.000000000e+00 6.7e-08 1.30
Optimizer terminated. Time: 1.55

Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: -1.0264444775e+01 nrm: 1e+00 Viol. con: 2e-07 var: 0e+00 cones: 0e+00
Optimizer summary
Optimizer - time: 1.55
Interior-point - iterations : 2 time: 1.38
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: Infeasible
Optimal value (cvx_optval): +Inf

Also, when I replace “exp(-x_imn+log(10)*(b0/10+Pu/10-6))” in the RHS of the inequality with “10000”, it is solved (so I suppose there should be a feasible value for each element of x_imn for the code I post above). The output with “10000” is

Calling Mosek_2 9.2.47: 65600 variables, 32000 equality constraints

MOSEK Version 9.2.47 (Build date: 2021-6-15 12:45:51)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 32000
Cones : 0
Scalar variables : 65600
Matrix variables : 0
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 2200
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 1600
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.13
Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 32000
Cones : 0
Scalar variables : 65600
Matrix variables : 0
Integer variables : 0

Optimizer - threads : 2
Optimizer - solved problem : the dual
Optimizer - Constraints : 1600
Optimizer - Cones : 0
Optimizer - Scalar variables : 14600 conic : 0
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.01 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 2400 after factor : 2400
Factor - dense dim. : 0 flops : 8.52e+04
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 1.1e+07 1.8e+03 2.3e+10 0.00e+00 0.000000000e+00 -1.051008551e+08 5.0e+04 0.16
1 3.3e+06 5.5e+02 7.0e+09 -1.00e+00 0.000000000e+00 -1.050896565e+08 1.5e+04 0.19
2 1.3e+06 2.1e+02 2.7e+09 -1.00e+00 0.000000000e+00 -1.050663086e+08 5.7e+03 0.19
3 7.0e+04 1.2e+01 1.5e+08 -9.99e-01 0.000000000e+00 -1.043431620e+08 3.2e+02 0.19
4 3.4e+01 5.7e-03 7.2e+04 -9.85e-01 0.000000000e+00 -6.466778078e+06 1.5e-01 0.19
5 3.7e-03 6.2e-07 7.9e+00 8.77e-01 0.000000000e+00 -6.763222784e+02 1.7e-05 0.19
6 3.7e-07 6.2e-11 7.9e-04 1.00e+00 0.000000000e+00 -6.763269344e-02 1.7e-09 0.20
7 3.7e-11 6.2e-15 7.9e-08 1.00e+00 0.000000000e+00 -6.763269348e-06 1.7e-13 0.20
8 1.8e-13 6.2e-19 7.9e-12 1.00e+00 0.000000000e+00 -6.763269347e-10 1.7e-17 0.20
Basis identification started.
Primal basis identification phase started.
Primal basis identification phase terminated. Time: 0.02
Dual basis identification phase started.
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.02
Optimizer terminated. Time: 0.27

Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 0.0000000000e+00 nrm: 1e+05 Viol. con: 2e-11 var: 0e+00
Dual. obj: -6.7632693467e-10 nrm: 1e-15 Viol. con: 0e+00 var: 1e-17

Basic solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 0.0000000000e+00 nrm: 1e+05 Viol. con: 3e-11 var: 0e+00
Dual. obj: 0.0000000000e+00 nrm: 0e+00 Viol. con: 0e+00 var: 0e+00
Optimizer summary
Optimizer - time: 0.27
Interior-point - iterations : 8 time: 0.25
Basis identification - time: 0.02
Primal - iterations : 0 time: 0.02
Dual - iterations : 600 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: Solved
Optimal value (cvx_optval): +1

2

You haven’t provided a reproducible problem. For instance, H is missing.

And what is the clearly feasible solution? Is that with qL = q_mn ? And what about the other variable values?

Please provide a reproducible problem. Please provide explicitly the supposedly feasible solution, including the setting of all variable values. And show us the evidence that it is feasible, i.e., that the inequality is satisfied at that supposedly feasible point.

3

Sorry I forgot that. I just added H=100 into my code and edited my post to make it more clear . When q_mn=qL, LHS of the constrant is much bigger than zero so I suppose there always be feasible values for x_imn. Note that there is only 1 constraint in my problem.

4

When I ran this with q_mn = qL; instead of declaring q_mn a variable., the result was

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

I will defer to Mosek personnel as to why the original problem was found to be infeasible…I will point out that the “single” constraint is really 40*4*200 = 32000 inequality constraints, all of which have exp on the RHS.

5

This

Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: -1.0264444775e+01 nrm: 1e+00 Viol. con: 2e-07 var: 0e+00 cones: 0e+00

shows Mosek has found a quite accurate Farkas certificate of dual infeasibility.
SInce

For improved efficiency, Mosek_2 is solving the dual problem.

this implies the original problem is infeasible.

In this case it most likely means your problem is not robust feasible.

You claim your problem is feasible and that might be the case assuming exact computations.
But here we are doing computations using finite precision floating numbers and that means you should show that your problem is robust feasible. (This is the same as showing that there is no good approximate Farkas certificate.)

For instance the problem

x+y=1
2(x+y) = 2 + eps

is not robust feasible because for all eps>0 it is infeasible. And hence for a big real example considering floating point numbers it may easily be determined infeasible even for eps=0.

6

Perhaps the feasible solution which CVX (claims to find, when q_mn is set to qL rather than being declared as CVX variable, is “thin” in those (the q_mn) dimensions, i.e., not “robust” as @Erling puts it.

When q_mn is no longer a variable (part of the optimization problem), this thinness (non-robustness) is removed, and the problem is (trivially) feasible? I.e., the problem is 'thin:" in the original dimension, but the lower dimensional problem, when the thin dimensions are eliminated, is not thin?

7

Thank you for the answer. Seems that I need to learn more about convex optimization and numerical calculation. Also, Is there any way to solve it except lowering the cvx_precision???