A convex problem followed by Nan solution

MIDCP
1

Hope everyone is doing well.
I have a convex problem, but CVX provides me with NaN. Below, I present the solution table. Could anyone figure out where the problem is?

Successive approximation method to be employed.
For improved efficiency, SeDuMi is solving the dual problem.
SeDuMi will be called several times to refine the solution.
Original size: 175 variables, 69 equality constraints
24 exponentials add 192 variables, 120 equality constraints

Cones | Errors |
Mov/Act | Centering Exp cone Poly cone | Status
--------±--------------------------------±--------
21/ 21 | 8.000e+00 7.737e+00 0.000e+00 | Failed
21/ 21 | 8.000e+00s 8.535e+00s 0.000e+00 | Inaccurate/Solved
16/ 16 | 8.000e+00 1.552e+01 0.000e+00 | Failed
13/ 13 | 8.000e+00 2.338e+01 0.000e+00 | Inaccurate/Solved
21/ 21 | 8.000e+00 3.102e+01 0.000e+00 | Failed
18/ 18 | 8.000e+00 4.089e+01 0.000e+00 | Failed
13/ 13 | 8.000e+00 5.160e+01 0.000e+00 | Inaccurate/Solved
13/ 13 | 8.000e+00s 5.982e+01s 0.000e+00 | Inaccurate/Solved
20/ 20 | 8.000e+00 6.542e+01 0.000e+00 | Failed
16/ 16 | 8.000e+00 7.348e+01 0.000e+00 | Inaccurate/Solved
16/ 16 | 8.000e+00s 8.243e+01s 0.000e+00 | Inaccurate/Solved
13/ 13 | 8.000e+00 8.546e+01 0.000e+00 | Failed
17/ 17 | 8.000e+00 8.306e+01 0.000e+00 | Inaccurate/Solved
16/ 16 | 8.000e+00 9.172e+01 0.000e+00 | Inaccurate/Solved
16/ 16 | 8.000e+00s 1.002e+02s 0.000e+00 | Inaccurate/Solved
15/ 15 | 8.000e+00 1.177e+02 0.000e+00 | Failed
22/ 22 | 8.000e+00 1.104e+02 0.000e+00 | Inaccurate/Solved
10/ 10 | 8.000e+00 1.128e+02 0.000e+00 | Failed
19/ 19 | 8.000e+00 1.149e+02 0.000e+00 | Inaccurate/Solved
18/ 18 | 8.000e+00 1.218e+02 0.000e+00 | Inaccurate/Solved
17/ 17 | 8.000e+00 1.323e+02 0.000e+00 | Inaccurate/Solved
17/ 17 | 8.000e+00s 1.415e+02s 0.000e+00 | Inaccurate/Solved
17/ 17 | 8.000e+00s 1.510e+02s 0.000e+00 | Failed

Status: Failed
Optimal value (cvx_optval): NaN

2

If you have access to Mosek, use CVX 2.2 with Mosek as solver.

If you don’t have access to Mosek, follow the advice in CVXQUAD: How to use CVXQUAD's Pade Approximant instead of CVX's unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD's Quantum (Matrix) Entropy & Matrix Log related functions .

3

Dear Stone,

I use Mosek as solver, but it did not work.

Calling Mosek 9.1.9: 175 variables, 69 equality constraints
For improved efficiency, Mosek is solving the dual problem.

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (48) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (49) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (50) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (51) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (64) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (77) of matrix ‘A’.
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 69
Cones : 24
Scalar variables : 175
Matrix variables : 0
Integer variables : 0

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

Optimizer - threads : 2
Optimizer - solved problem : the dual
Optimizer - Constraints : 10
Optimizer - Cones : 24
Optimizer - Scalar variables : 103 conic : 72
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.05 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 22 after factor : 25
Factor - dense dim. : 0 flops : 3.35e+02
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 4.4e+00 1.5e+01 2.0e+01 0.00e+00 1.932244809e+01 -2.207049540e-08 1.0e+00 0.38
1 9.6e-01 3.2e+00 7.5e+00 -7.96e-01 9.248077095e+00 -2.910912312e+00 2.2e-01 0.61
2 2.1e-01 7.0e-01 2.3e+00 -5.36e-01 -1.990660608e+00 -5.596127237e+00 4.8e-02 0.61
Optimizer terminated. Time: 0.72

Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: -2.0936260861e-01 nrm: 3e+07 Viol. con: 9e-10 var: 3e+07 cones: 1e-01
Optimizer summary
Optimizer - time: 0.72
Interior-point - iterations : 2 time: 0.61
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

4

I have the same problem， CVX provides the NaN to me, I guess my variable is too large to calculate. So I am confused as well.

5

Mosek has determined your problem to be dual infeasible. Because Mosek was provided the dual by CVX, CVX concludes the problem you entered in CVX is primal infeasible.

However, Mosel issues warning messages about near zero coefficients in the model. So your problem scaling may be bad. You should try to re-scale (change units) so that non-zero coefficients in your model are within a small number of orders of magnitude of one. After you have done this, re-run the problem, because the original derterrmination of infeasibility might be unreliable given the bad scaling.

If that doesn’t resolve things, then follow the advice in https://yalmip.github.io/debugginginfeasible/ , except for section 1.

6

The situation from another recent post repeats itself: MOSEK produces a bad certificate with huge violation (Viol. con: 9e-10 var: 3e+07 ) and other solver(s) struggle in other ways. See CVX giving 'Solved' outcome not satisfying the constraints and consider submitting the task to MOSEK support.

9

You don’t need to be familiar with YALMIP. The suggestions in that link, except for section 1, are also applicable to CVX. You can also avail yourself of the offer by @Michal_Adamaszek .

10

Thanks, Mr. Stone. I will go through all of them, hope to be successful at debugging my problem.

11

Maybe your Mosek issue is the same as in CVX giving 'Solved' outcome not satisfying the constraints If so then do not set “cvx precision best”.

12

I eliminated CVX precision best, but still get the same results. However, I found that one of my constraint make the problem infeasible. How should I deal with that, I cannot omit that constraint since it is a part of it.
As advised by Mr. Stone, although my non-zero coefficients are within a small number of orders of magnitude of one, CVX cannot solve the problem!

13

Can you post the log output?

14

When my parameters have a low value, CVX sometimes gives a solution that is not valid for me!
I want to investigate general cases by increasing the value of my parameter! For instance, form 8 to 16 for just one variable and got nothing in output. Below, I provided the corresponding result.

Successive approximation method to be employed.
SeDuMi will be called several times to refine the solution.
Original size: 5223 variables, 2376 equality constraints
34 exponentials add 272 variables, 170 equality constraints

Cones | Errors |
Mov/Act | Centering Exp cone Poly cone | Status
--------±--------------------------------±--------
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Failed
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Failed
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Failed

Status: Failed
Optimal value (cvx_optval): NaN

15

Why are you not using Mosek (or CVXQUAD)?

16

Is it possible for you to do me a favor and solve this subproblem with these solvers? Maybe, it has sth to do with my solvers! At Least, I will have a vision whether it is about the solver or code.
Below, I provided one section of my code. Although some of them should be optimized in the previous section I gave them a random number to just figure out what it is wrong with this specific problem.

I solve it with SDPT3, but it gave an unreliable result.

X = 3; 
Nuser1 = 2; 
Nuser2 = 2;
Nuser=Nuser2+Nuser1;
M=8; 
Nchannel=16;
R_min=1;
Inter=10^-12;
sigma=10^-15; 
power=10^-4; 
eta=0.8;
z=round(0.7 * rand(Nuser,X,Nchannel));
x=round(0.7 * rand(Nuser,X,M));
H =(randn(X,Nuser,Nchannel,M)+1i*randn(X,Nuser,Nchannel,M))/sqrt(2) * 10^-2;
G =(randn(X,Nuser,Nchannel,M,X)+1i*randn(X,Nuser,Nchannel,M,X))/sqrt(2) * 10^-8;

cvx_begin
variable p(X,Nuser,Nchannel,M,X) nonnegative
sum_new_1=cvx(zeros(1));
for m=1:X
    for i=1:Nuser
        for j = 1:Nchannel
            for k=1:M
                sum_new_1=sum_new_1+p(m,i,j,k,m)*z(i,m,j)*x(i,m,k);
            end
        end
    end
end
minimize(sum_new_1)
subject to
Interference_new=cvx(zeros(X,Nuser2,Nchannel));
Rd_new=cvx(zeros(X,Nuser2));
E_new=cvx(zeros(X,Nuser1));
EE_new=cvx(zeros(X,Nuser1));
for m=1:X
    for i=1:Nuser2
        for m0=1:X 
            if (m~=m0)
                for i0=1:Nuser
                    for k=1:M
                        for j = 1:Nchannel
                            Interference_new(m,i,j)=Interference_new(m,i,j)+p(m0,i0,j,k,m0).*abs(G(m,i,j,k,m0).^2)*z(i0,m0,j)*x(i0,m0,k);                            end
                    end
                end
            end
        end
        for k=1:M
            for j = 1:Nchannel
                Rd_new(m,i)= Rd_new(m,i)+log(1+p(m,i,j,k,m).*abs(H(m,i,j,k).^2)/sigma+Inter)*z(i,m,j)*x(i,m,k);
            end
        end
    end
end
for ii=1:Nuser1
    for m=1:X
        for m0=1:X
            if (m~=m0)
                for i=1:Nuser
                    for k=1:M
                        for j = 1:Nchannel
                            E_new(m,ii)=E_new(m,ii)+eta.*p(m0,i,j,k,m0).*abs(G(m,i,j,k,m0).^2)*z(i,m,j)*x(i,m,k);
                        end
                    end
                end
            end
        end
        for k=1:M
            for j = 1:Nchannel
                EE_new(m,ii)=EE_new(m,ii)+eta.*p(m,ii+Nuser2,j,k,m).*abs(H(m,ii+Nuser2,j,k).^2)*z(ii+Nuser2,m,j)*x(ii+Nuser2,m,k);
            end
        end
    end
end
E_new=E_new+EE_new;

Final_E=sum(E_new,2);
Final_rate=sum(Rd_new,2);
Final_Inter=sum(Interference_new,1);
for i=1:X
    Final_rate(i,1)>=R_min;
    Final_E(i,1)>=power;
end
for i=1:Nchannel
    for j=1:Nuser2
        Final_Inter(1,j,i)<=Inter;
    end
    for n=1:Nuser
        for m=1:X
            for k=1:M
                p(m,n,i,k)>=0;
            end
        end
    end
end
cvx_end
17

So I ran it for you. This is the range of coefficients you have in the linear constraint matrix

min=4.66e-07      max=9.94e+11

The max is just way too big. https://docs.mosek.com/9.2/capi/debugging-numerical.html#formulating-problems. Dividing by sigma=10^-15 is probably causing this. Given such numerics I would say Mosek does really well:

Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 1.3809058501e+00    nrm: 2e+00    Viol.  con: 2e-09    var: 9e-27    cones: 0e+00  
  Dual.    obj: 1.3809058463e+00    nrm: 5e+03    Viol.  con: 0e+00    var: 3e+01    cones: 0e+00
18

Thank you so much, really appreciate that. This is my Mosek output. Why is it different from your result?

Calling Mosek 9.1.9: 5294 variables, 2399 equality constraints

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

MOSEK warning 62: The A matrix contains a large value of 9.2e+10 in constraint ‘’ (0) at variable ‘’ (1422).
MOSEK warning 62: The A matrix contains a large value of 1.8e+11 in constraint ‘’ (128) at variable ‘’ (1425).
MOSEK warning 62: The A matrix contains a large value of 3.9e+11 in constraint ‘’ (1) at variable ‘’ (1434).
MOSEK warning 62: The A matrix contains a large value of 6.9e+10 in constraint ‘’ (129) at variable ‘’ (1437).
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1437) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1440) of matrix ‘A’.
MOSEK warning 62: The A matrix contains a large value of 1.4e+11 in constraint ‘’ (130) at variable ‘’ (1449).
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1452) of matrix ‘A’.
MOSEK warning 62: The A matrix contains a large value of 5.6e+10 in constraint ‘’ (3) at variable ‘’ (1458).
MOSEK warning 62: The A matrix contains a large value of 1.2e+11 in constraint ‘’ (131) at variable ‘’ (1461).
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1464) of matrix ‘A’.
MOSEK warning 62: The A matrix contains a large value of 1.6e+11 in constraint ‘’ (4) at variable ‘’ (1470).
MOSEK warning 62: The A matrix contains a large value of 3.7e+11 in constraint ‘’ (132) at variable ‘’ (1473).
MOSEK warning 62: The A matrix contains a large value of 5.4e+10 in constraint ‘’ (5) at variable ‘’ (1482).
Warning number 62 is disabled.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1488) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1524) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1536) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1557) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1581) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1584) of matrix ‘A’.
Warning number 710 is disabled.
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 2399
Cones : 57
Scalar variables : 5294
Matrix variables : 0
Integer variables : 0

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

Optimizer - threads : 2
Optimizer - solved problem : the primal
Optimizer - Constraints : 3
Optimizer - Cones : 57
Optimizer - Scalar variables : 171 conic : 171
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 3 after factor : 3
Factor - dense dim. : 0 flops : 2.31e+02
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.3e+01 1.3e+00 4.7e+01 0.00e+00 3.214349111e+00 -4.267646498e+01 1.0e+00 0.11
1 2.5e+00 1.4e-01 2.0e+00 5.05e-01 3.214349114e+00 -2.939923037e+00 1.1e-01 0.27
2 1.7e-02 1.0e-03 8.2e-04 1.01e+00 3.214349114e+00 3.171244701e+00 7.7e-04 0.28
3 3.8e-07 2.2e-08 1.0e-10 1.00e+00 3.214349114e+00 3.214348177e+00 1.7e-08 0.30
4 8.1e-09 4.6e-10 3.1e-13 1.00e+00 3.214349114e+00 3.214349094e+00 3.6e-10 0.30
5 3.2e-09 1.8e-10 7.1e-14 1.15e+00 3.214349112e+00 3.214349105e+00 1.4e-10 0.31
6 1.6e-09 9.3e-11 2.5e-14 1.21e+00 3.214349111e+00 3.214349108e+00 7.2e-11 0.31
Optimizer terminated. Time: 0.36

Interior-point solution summary
Problem status : PRIMAL_INFEASIBLE
Solution status : PRIMAL_INFEASIBLE_CER
Dual. obj: 2.1548642700e-09 nrm: 2e+01 Viol. con: 0e+00 var: 2e+01 cones: 0e+00
Optimizer summary
Optimizer - time: 0.36
Interior-point - iterations : 6 time: 0.33
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

19

I think you may be insisting on the cvx_precision best although we suggested to remove it. Also, which CVX do you run? (it generates slightly different number of constraints/variables than for me). I used the latest 2.2. And finally I had to guess how to fix a badly formatted point in your code - could have guessed wrong.

Regardless of all that it would pay off for you to fix the coefficients.

20

I use version 2.2. Also I removed cvx_precision best.

image

21

My Mosek is getting a slightly different input than yours:

  Constraints            : 2395            
  Cones                  : 53              
  Scalar variables       : 5334

Hard to say why. Maybe the randomness can affect structure?

22

I really have no idea. Maybe I should go through the code and see if I made a mistake or not. Then, if everything is OK, I will have to work on these solvers.