How to fix unknown problem in the solver(Mosek)

[Stephanie]

Dear Sir,

I am using Mosek as the solver to solve SDP in Yalmip, and I have two models A and B, there is only a parameter in A  is different from B. But the output is quite different, A returns" successfully solved" and B returns"unknown problem in the solver". Actually, the solution of A should be included in the solution of B,and I use the solution of A to check if it satisfy the constraints of B, and it does satisfy, which means I can find a feasible solution of B. Could you please give some advice on how can I fix this kind of problem. Thanks in advance.

[Erling D. Andersen]

[First an educational comment. How on earth do expect to solve this. We do not know the problem and what you are trying to do. There is no log output. No data that can reproduce the issue. You provide virtually zero information for figuring out the cause. You almost expect that we have god like features in diagnising the cause.]

MOSEK says unknown if numerical problems prevented it from solving the problem.  Typical that happens for nasty problems.

Now consider

x+y               = 1

x+(1+eps)y  =  2

For eps=0.0 the problem is infeasible. For eps>0 it is feasible and y=1/eps.  

In practice for eps close to zero y is very large and the problem is close to being infeasible. So you have an unstable and nasty problem.

Maybe that is what is happening or maybe not. Har to say with provided information.

If you dump the two problems to disk using the instructions at

   http://docs.mosek.com/8.1/faq/faq.html

and submit them to MOSEK support

    https://www.mosek.com/support/

we might be able to give a better answer.

[Stephanie]

Thanks so much for your reply, I am so sorry for no given useful information, my log output is shown as follows:

MOSEK Version 8.0.0.74 (Build date: 2017-5-10 09:25:15)

Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com

Platform: MACOSX/64-X86

MOSEK warning 710: #10 (nearly) zero elements are specified in sparse col '' (1) of matrix 'A'.

MOSEK warning 710: #12 (nearly) zero elements are specified in sparse col '' (2) of matrix 'A'.

MOSEK warning 710: #12 (nearly) zero elements are specified in sparse col '' (3) of matrix 'A'.

MOSEK warning 710: #6 (nearly) zero elements are specified in sparse col '' (4) of matrix 'A'.

MOSEK warning 710: #10 (nearly) zero elements are specified in sparse col '' (5) of matrix 'A'.

MOSEK warning 710: #16 (nearly) zero elements are specified in sparse col '' (6) of matrix 'A'.

MOSEK warning 710: #36 (nearly) zero elements are specified in sparse col '' (7) of matrix 'A'.

MOSEK warning 710: #40 (nearly) zero elements are specified in sparse col '' (8) of matrix 'A'.

MOSEK warning 710: #56 (nearly) zero elements are specified in sparse col '' (9) of matrix 'A'.

MOSEK warning 710: #24 (nearly) zero elements are specified in sparse col '' (10) of matrix 'A'.

Warning number 710 is disabled.

Problem

  Name                   :                 

  Objective sense        : min             

  Type                   : CONIC (conic optimization problem)

  Constraints            : 10986           

  Cones                  : 0               

  Scalar variables       : 59070           

  Matrix variables       : 2               

  Integer variables      : 0               

Optimizer started.

Conic interior-point optimizer started.

Presolve started.

Linear dependency checker started.

Linear dependency checker terminated.

Eliminator started.

Freed constraints in eliminator : 30

Eliminator terminated.

Eliminator - tries                  : 1                 time                   : 0.00            

Lin. dep.  - tries                  : 1                 time                   : 0.02            

Lin. dep.  - number                 : 0               

Presolve terminated. Time: 0.57    

Optimizer  - threads                : 1               

Optimizer  - solved problem         : the primal      

Optimizer  - Constraints            : 10956

Optimizer  - Cones                  : 1

Optimizer  - Scalar variables       : 30677             conic                  : 215             

Optimizer  - Semi-definite variables: 2                 scalarized             : 10956           

Factor     - setup time             : 11.99             dense det. time        : 0.00            

Factor     - ML order time          : 5.54              GP order time          : 0.00            

Factor     - nonzeros before factor : 3.04e+07          after factor           : 3.04e+07        

Factor     - dense dim.             : 2                 flops                  : 1.14e+11        

ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  

0   2.0e+00  1.0e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  12.91 

1   2.0e+00  9.8e-01  9.7e-01  -4.94e-01  -2.040532505e-02  -6.546145484e-03  9.8e-01  20.42 

2   1.5e+00  7.4e-01  6.9e-01  -4.95e-01  -3.482512252e-01  -1.543647985e-01  7.4e-01  27.35 

3   6.8e-01  3.4e-01  2.5e-01  -5.21e-01  -2.338024392e+00  -1.303620794e+00  3.4e-01  33.92 

4   2.1e-01  1.0e-01  3.9e-02  -9.40e-01  -8.366128429e+00  -1.911931047e+00  1.0e-01  45.15 

5   1.5e-01  7.4e-02  2.4e-02  -1.28e+00  -1.366108329e+01  -4.923936887e+00  7.4e-02  52.41 

6   9.9e-02  5.0e-02  1.2e-02  -1.16e+00  -2.505030387e+01  -8.032422028e+00  5.0e-02  59.23 

7   6.2e-02  3.1e-02  6.0e-03  -9.65e-01  -3.827678618e+01  -1.186986288e+01  3.1e-02  65.25 

8   3.7e-02  1.8e-02  2.8e-03  -9.01e-01  -6.349330838e+01  -2.172175151e+01  1.8e-02  72.21 

9   1.9e-02  9.3e-03  1.2e-03  -7.73e-01  -1.155937454e+02  -5.193093697e+01  9.3e-03  78.71 

10  1.1e-02  5.6e-03  6.6e-04  -4.81e-01  -1.612784785e+02  -9.063492733e+01  5.6e-03  85.00 

11  5.8e-03  2.9e-03  3.7e-04  -1.57e-01  -2.121382766e+02  -1.509463586e+02  2.9e-03  91.82 

12  5.4e-03  2.7e-03  3.5e-04  3.19e-01   -2.158672540e+02  -1.573779296e+02  2.7e-03  97.90 

13  2.5e-03  1.3e-03  2.2e-04  3.68e-01   -2.517814631e+02  -2.200876675e+02  1.3e-03  104.10

14  6.0e-04  3.0e-04  1.2e-04  8.77e-01   -2.742861027e+02  -2.684928962e+02  3.0e-04  110.27

15  1.8e-04  8.8e-05  6.6e-05  1.23e+00   -2.790595779e+02  -2.772819613e+02  8.8e-05  116.18

16  4.8e-05  2.4e-05  3.5e-05  1.17e+00   -2.743926702e+02  -2.739438558e+02  2.4e-05  122.45

17  1.3e-05  6.4e-06  2.0e-05  1.16e+00   -2.524452152e+02  -2.523408641e+02  6.4e-06  128.58

18  4.9e-06  2.4e-06  1.3e-05  1.16e+00   -1.848681244e+02  -1.848334651e+02  2.4e-06  139.26

19  3.8e-06  1.9e-06  1.1e-05  1.07e+00   -1.512393392e+02  -1.512115253e+02  1.9e-06  144.66

20  3.0e-06  1.5e-06  9.9e-06  9.85e-01   -1.238927385e+02  -1.238698617e+02  1.5e-06  150.09

21  2.3e-06  1.1e-06  8.4e-06  9.33e-01   -9.490497352e+01  -9.488684311e+01  1.1e-06  156.09

22  1.7e-06  8.7e-07  7.2e-06  9.03e-01   -6.982230704e+01  -6.980802631e+01  8.7e-07  161.66

23  1.1e-06  5.4e-07  5.7e-06  9.05e-01   -4.386246752e+01  -4.385350455e+01  5.4e-07  167.47

24  7.7e-07  3.9e-07  4.8e-06  9.47e-01   -2.998619429e+01  -2.997970863e+01  3.9e-07  173.19

25  7.4e-07  3.7e-07  4.7e-06  9.68e-01   -2.808930215e+01  -2.808314125e+01  3.7e-07  179.02

26  5.7e-07  2.9e-07  4.1e-06  9.72e-01   -1.889676972e+01  -1.889200469e+01  2.8e-07  185.11

27  4.6e-07  2.3e-07  3.7e-06  9.87e-01   -1.289137368e+01  -1.288749447e+01  2.3e-07  190.57

28  4.2e-07  2.1e-07  3.5e-06  9.96e-01   -1.028065149e+01  -1.027717277e+01  2.1e-07  201.15

29  3.1e-07  1.6e-07  3.0e-06  9.78e-01   -4.616013320e+00  -4.613380243e+00  1.6e-07  207.87

30  2.8e-07  1.4e-07  2.8e-06  9.89e-01   -2.464877708e+00  -2.462566482e+00  1.4e-07  214.00

31  2.5e-07  1.2e-07  2.7e-06  9.94e-01   -5.549189626e-01  -5.528950691e-01  1.2e-07  221.21

32  2.2e-07  1.1e-07  2.6e-06  9.95e-01   3.509286924e-01   3.527880182e-01   1.1e-07  227.78

33  1.7e-07  8.4e-08  2.2e-06  9.97e-01   3.351881812e+00   3.353297765e+00   8.3e-08  233.92

34  1.4e-07  6.9e-08  2.0e-06  9.98e-01   5.158031826e+00   5.159186352e+00   6.8e-08  240.91

35  1.4e-07  6.1e-08  1.9e-06  9.99e-01   6.119242211e+00   6.120264105e+00   6.0e-08  247.68

36  1.4e-07  6.1e-08  1.9e-06  9.99e-01   6.119242211e+00   6.120264105e+00   6.0e-08  254.72

Interior-point optimizer terminated. Time: 255.64. 

Optimizer terminated. Time: 256.12  

Interior-point solution summary

  Problem status  : UNKNOWN

  Solution status : UNKNOWN

  Primal.  obj: 6.1192422113e+00    nrm: 2e+03    Viol.  con: 6e-02    var: 3e-03    barvar: 0e+00  

  Dual.    obj: 6.1202641051e+00    nrm: 3e+03    Viol.  con: 0e+00    var: 8e-06    barvar: 8e-06  

Optimizer summary

  Optimizer                 -                        time: 256.12  

    Interior-point          - iterations : 37        time: 255.64  

      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    

And for the warning:MOSEK warning 710: #24 (nearly) zero elements are specified in sparse col '' (10) of matrix 'A'. I am a little doubt that there is no matrix 'A' in my model, so it is a matrix that generated for mosekdebug use?

[Erling D. Andersen]

The warning says you have nearly zero elements in the constraint matrix. I.e. MOSEK referring  to the model mentioned

   http://docs.mosek.com/8.1/toolbox/prob-def-semidef.html

since it cannot know what naming is used by you or Yalmip. So A is an internal name of MOSEK.

The warning indicates scaling issues or your data contain nonzeros which without rounding would be zero and hence should be truncated.

Nothing else comes to my mind based on the log output.

It could be if you upgrade to the latest MOSEK version 8.1.0.25 that the problem goes away if we are bit lucky. Otherwise you will have to submit the problem MOSEK support as mentioned in my previous reply.

So we can investigate it in details.

[Johan Löfberg]

You should simply look at the data you use in your model, to see which data is numerical noise.

[Johan Löfberg]

and haven't you reported a very similar problem before, where we cam to exactly the same conclusion: You had numerical noise in your model, typically coming from solving equality constraints and deriving bases etc which included numbers like 10^-15 

[Stephanie]

Yes, I reported the problem before, in that case I didn't find what variable cause the problem and now I find certain parameter change that will cause the numerical problem. For that variable,I set the value from 0.9 to 1 and then numerical problem occurs (this change actually is a small change in my problem). 

[Johan Löfberg]

and the same recipe still holds

Look at your data, what data contains numerical noise, and figure out why.

[Stephanie]

Hi, Sir, I think my data has no big problem. Cause for the same code, I run it on my mac, it turns out this kind of unknown problem and when I run the same code in my windows PC, it then can be successfully solved. But I still meet the unknown problem in my windows PC with other parameters. And when I update the Yalmip to the latest version, some these kind of problem are then solved.

I also wrote mail to Mosek support team, and they told me that the problem is not in Mosek. It is because the message from Yalmip is misleading. So I think this kind of problem "unknown problem in the solver (Turn on debug in sdpsettings) (Mosek)" should lie in Yalmip. Could you give some suggestions? Thanks so much.

Best regards

[Johan Löfberg]

The word unknown is used in different contexts in YALMIP and Mosek. If YALMIP reports "Unknown problem in solver" it means that the solver has either crashed badly due to memory etc, failed to start due to incorrect installation or license, or it has simply done something that YALMIP doesn't understand. Hence, precisely as it says, you should turn on the debug flag to see what actually happens in the call

[Erling D. Andersen]

By definition an unstable problem is a problem where a tiny change in the data leads to a vastly different outcome/solution.

Now computations are done in finite precision on a computer which implies the associative law does not hold exactly. When you move from computer and to another computer computations are reorder so to exploit the hardware such as caches better.

This reordering is equivalent to a small change in data from mathematical point view.

What you observe is very consistent with the claim that you have unstable problem.

PS: I fairly sure what MOSEK support said is: Your problem is broken and we have no suggestion for a fix in MOSEK that will MOSEK solve problem reliably. 

[Johan Löfberg]

I'm pretty sure Stephanie has shown her model to me in some other thread, and it is basically a model which partially is derived from manually eliminating an equality Hx = b leading to x = Wy+b which then is plugged into the overall optimization model, but she has not handled the fact that the elimination leads to a lot of spurious numerical noise (i.e. effectively noise in W )

[Johan Löfberg]

.Unknown problem in solver in YALMIP can also mean that YALMIP does not recognize the diagnostic flags from the solver. If that is the case, you simply have to look at the display the solver delivers, and draw your own conclusions.

However, as both Mosek and I say, your model is numerically broken, and before you fix that, we cannot help you

[Stephanie]

Emmm...The exact reply of Mosek team is：The error message from Yalmip is misleading. There is no bug, but MOSEK could not solve the problem. I discussed this error message "Turn on debugging" with the Yalmip developer, and I think he will rectify that eventually. Perhaps he already did, and you just need update Yalmip.

[Johan Löfberg]

That is precisely what we are saying. The problem is that your model involves numerical garbage, which Mosek simply cannot deal with. If you think otherwise, you must post the complete reproducible model.

[Stephanie]

Yeah, I told you that I have reported it before. Eliminating equality constraints Ax+b=0 to get x and then take it to the original optimization problem may cause some big problem. Actually I really didn't know this before = =

[Johan Löfberg]

So have you fixed this then? 

[Stephanie]

Nope, I choose the parameters that won't lead to this unknown problem to get the results I need then.

[Johan Löfberg]

So what is this revived thread about then if you already fixed your issues?

BTW, why do you bother with manually eliminating equalities? Why not let the solver work with the original problem

[Stephanie]

This time I just want to figure out why this kind of unknown problem will happen and how can I fixed it.
I eliminate equality constraints to eliminate some variables and to make the model more efficiently solved. Since in my model, the computation time is directly related to the number of variables.

[Johan Löfberg]

Not necessarily. The solver might be just as efficient for a model with more variables if it means sparsity and structure will be improved.

Post your failing model and will see if I can have YALMIP catch the issues better

[Erling D. Andersen]

Eliminating them can be good idea but it is naive to assume so without checking because you may increase numerical issues and reduce sparsity. I would start by leaving them in place.

[Joachim Dahl]

Some easy and very important things to look for in your model are:

1) Very large numbers in the resulting constraint matrix, or very large bounds.

2) Do you get very large primal or dual objective values?

3) Are the norms of either the primal or dual solutions very large?

a little harder to check for:

4) Do you have strict feasibility?   For example sum(sum(X)) == 0 for a s semidefinite X ruins strict feasibility, similarly Trace(A*X)==0, for semidefinite A and X.

[Stephanie]

Thanks so much for your advice. Yes, I have Trace(A*X)==0 constraints. But now I have relaxed it to Trace(A*X)<=1e-4, which can decrease the unknown problems.

I eliminate the equality constraints because the computation time is related to the variable matrix X.

And I attach my code, and it fails both in my Mac and windows PC. 

Best Regards

[Joachim Dahl]

If you have trace(A*X) = 0 where both A and X are PSD, then you should eliminate the constraint, not relax it.

It is equivalent to saying that X is in the nullspace of A,  i.e.,  X := V*Z*V', Z>=0  where V spans the nullspace of A, and Z is a smaller semidefinite matrix of same dimension as the nullspace of A.

But this is only true if A is PSD.  If A is not PSD,  then I don't see any good reason for the relaxation you propose - it's probably just pure coincidence if it works better.

[Stephanie]

I think A is not PSD in my model. And the reason why I relax it because the Mosek support team told me that:

Equality constraints tr(X)==0 are often to blame. Try relaxing it a bit.

Then I try to relax it.

[Johan Löfberg]

You are still adding garbage to the model

ShowCompressMatrix(Ineq_SDP_Whole_Left(:,i,j),'Regular')'* reshape(Y_Left(:,:,i,j),Len_Left^2,1) >=0

You still don't appear to have looked at the data that you are generating

data = ShowCompressMatrix(Ineq_SDP_Whole_Left(:,i,j),'Regular')';
data = data(:);
data = data(find(data));
semilogy(sort(abs(data)))

A good one third of the non-zeros in your data is numerical noise on the order 10^-10 to 10^-30. That means you have constraints of the form x1*5 + x2*10^(-30)+... >=0 which is a horrible model (as if you change x2 from say 27 to 2700000000000000000000 nothing really happens). Impossible for the solver to work with 

Figure out why you have noise, and at the very least clean up the data (i.e. mydata(abs(bydata) < 1e-6)=0 or something like that)

[Johan Löfberg]

The A-matrices are indefinite.

Stephanie has derived a massive model A to implement a huge amount of constraints of the form X(i,j)+X(j,i)=0 etc

K>> A = ShowCompressMatrix(Ineq_SDP_Whole_Left(:,i,j),'Regular');

K>> (reshape(A(:,end),94,94))

ans =

  (56,56)       1

K>> (reshape(A(:,end-1),94,94))

ans =

  (67,56)      0.5000

  (56,67)      0.5000

K>> (reshape(A(:,end-3),94,94))

ans =

  (56,8)       0.5000

  (56,13)     -0.5000

  (56,23)      0.5000

   (8,56)      0.5000

  (13,56)     -0.5000

  (23,56)      0.5000

However, the data also contains completely redundant things saying 0*X(:) == 0 (relaxed to 0 <= 0*X <= 1e-4...or actually even worse  0*X >= 0, abs(0*X) <= 1e-4 since for some reason absolute value is used on an expression which is constrained to be positive on the line above...)

K>> (reshape(A(:,end-3002),94,94))

ans =

   All zero sparse: 94×94

and as seen above, a lot of elements in other places are 10^-20 etc

As said several times several months ago, you have to go back and see why you are generating bad data.

[Stephanie]

Emmm.... I just derive these data through the power flow balance and constraints in power system. The original constraints are power balance constraints in power system, and here A is actually the parameter matrix of all the inequality constraints, X is the matrix of all the variables. I solve the dual problem of the original problem. (The method I used refer to the paper Strategic Bidding for Producers in Nodal ElectricityMarkets: A Convex Relaxation Approach)

Maybe some of my process method such as eliminating equality constraints may bring the noise that cause these bad data? I think the original power balance constraints are right, and the way I get the parameters is also right, then the data is derived from the model itself. So I didn't look further into the exact matrix data I get in the model. And actually for the successfully solved situations, the results are good as I expected. 

Thanks so much for your diagnose for me. Just as you recommend, I will try to eliminate some extremely small value in matrix A to see if it helps. 

[Johan Löfberg]

Even though the theory is correct, you always have to take numerical issues into account hen working with floating points numbers, just as you cannot count on 2/3-2*(1/3) being zero in floating point numbers.

[Joachim Dahl]

The power-flow data from MATPOWER and other sources are not well-suited for verbatim implementation.  The characterize the problem, but there are many crucial steps like replacing identical upper and lower bound by an equality, removing artificially large upper bounds, adding small line resistances to get a connected network, etc.  I am not an expert on powerflow problems, but because of the many support questions on MOSEK for optimal powerflow problems, I have consulted with experts, and MOSEK solves their preprocessed models, where they employed those tricks, very easily and reliably.

A few numerical results can be seen in these slides:

https://docs.mosek.com/slides/2017/siopt/status_conic.pdf

As far as I am aware, those are among the largest standard OPF problems solved, and MOSEK solves them reliably in a few minutes. There are many papers that claim that SDP relaxations for OPF are difficult to solve, or doesn't scale, or that MOSEK is good at solving.  I think those papers are wrong.

We (MOSEK support) probably told you that Trace(X) == 0 is problematic, or Trace(A*X)==0 for A>=0 is problematic.

[Mark L. Stone]

Follow Joachim's advice. He knows what he's talking about on this, as I can say from personal experience.

[Farid]

Could you please elaborate more on what you mean with "Are the norms of either the primal or dual solutions very large?"
What is your criterion to say if the norm is large or not?
What is your proposed procedure to deal with such a problem with a large norm?

[Johan Löfberg]

There is no definition of large. If they are 10^10 you could (perhaps) say they are large and that (probably) indicates that your model is strange/badly scaled/ill--conditioned. If they are 10^5 they are, well smaller than 10^8, but are they large? Small? It's impossible to give a direct answer. You have to solve problems which aren't problematic to get a feeling for what things look like when things work, then you will (hopefully) be able to recognize the difference to the case when things don't work

[Farid]

Thank you Johan. 
Could you also elaborate on what good scaling vs. bad scaling means?
As a test case for me, I have an objective function that has to deal with both large input variables and optimization variables. The objective function exceeds 10^10 and the solver (matlab cvx ver2.1, solvers mosek and sdpt3) says that the dual problem is suspected of being infeasible. If I multiply the objective function by 10^-4, the solver finds a solution but is not the solution that I am looking for.
I do not know if the problem is with bad scaling and the consequent numerical errors or with the problem itself. My objective function is linear in terms of the optimization variables and seems to be convex (it is the minimization of the norm of a linear function with time-series input data). I am not sure if we could say based on the optimization theories that the norm of a linear function with time-series input data is always convex.

[Johan Löfberg]

We are just saying that numerical algorithms don't like huge and tiny numbers, as all kinds of problems can occur both algoritmically when judging tolerances etc for termination, initial scaling of the model goes wrong, and by the fact that things are represented using finite precision floating point numbers

For instance Minimizing 10^10*x + 10^(-10)*y subject to x >= 0, y == 10^10 could for instance lead to an optimal objective of around -10^4 with x = -1e-6 and y = (10^10 + 10000), since x = 1e-6 is close enough to 0 in a numerical algorithm, and (10^10 + 10000) is pretty much equal to 10^10, in relative terms, in a numerical algorithm..

[Johan Löfberg]

and regarding the specific problem here, the solver starts seeing absolutely huge objective values, and thus thinks the problem is infeasible (since then objective is inf)

your first step is to figure out if the problem is infeasible (by solving without objective). If you then are sure it is, you can start thinking about the poor scaling. If it isn't, or the solver simply cannot decide, you have to find out why it is infeasible, or so poorly modeled that the solver struggles