mosek incorrectly declares solution as optimal

[Mateus Araújo]

I'm trying to solve a problem which is not strictly feasible. As such, I don't expect MOSEK to be able to do it, but I do expect it to tell me when it failed. I came up with this problem when trying to reproduce a result from a paper on quantum information ( https://arxiv.org/abs/1812.06057 ). I couldn't reproduce their result, because it was wrong. They claim that the solution to the SDP is 0.00094, when it is in fact 0. Now I don't know which solver they used, but presumably one that also claimed incorrectly that 0.00094 was the optimal solution.

In any case, when I formulate the SDP explicitly in the dual form, it gives me answer 4.8871e-05 and tells me that the solution status is OPTIMAL. Looking at the log, this doesn't seem to make sense, as one can see it's struggling to converge and that PRSTATUS = 5.34e-01.

When I formulate it explicitly in the primal form, it gives me answer 9.3454e-04 and now helpfully points out that solution status is UNKNOWN.

Digging a bit deeper, I found the following quote in https://docs.mosek.com/latest/cmdtools/solving-conic.html :

"If the optimizer terminates without locating a solution that satisfies the termination criteria, for example because of a stall or other numerical issues, then it will check if the solution found up to that point satisfies the same criteria with all tolerances multiplied by the value of MSK_DPAR_INTPNT_CO_TOL_NEAR_REL. If this is the case, the solution is still declared as optimal."

This is so bizarre! Why would anyone want that? Please just tell me that it failed! And indeed, if I set the parameter MSK_DPAR_INTPNT_CO_TOL_NEAR_REL to 1 instead of the default 1000, now the dual form also tells me that solution status is UNKNOWN.

I'm using the MATLAB interface of MOSEK through YALMIP. The exact version number is

MOSEK Version 9.3.20 (Build date: 2022-4-27 08:19:36)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Linux/64-X86

The dumps are attached, as is the code to reproduce the problem.

[Michal Adamaszek]

Hi,

Do you have a specific question? Because from your message it looks like you already worked everything out very thoroughly so I'm not sure what we could help with.

Michal

[Erling D. Andersen]

Your problem is most likely illposed. 

[Mateus Araújo]

The problem is not ill-posed, it just lacks strict feasibility. I can prove that the correct solution is zero.

[Mateus Araújo]

This is a bug report.

I do have two specific questions, though: why does MOSEK multiplies the tolerances by 1000 and then declares the solution as optimal? Also, how is PRSTATUS calculated? It is the only parameter which is not explained in https://docs.mosek.com/latest/cmdtools/solving-conic.html

[Erling D. Andersen]

You are aware computations are done in 64 finite precision floating numbers?  And you cannot expect that Mosek will provide an exact solution or even classify the correctly for all problem instance you throw at it. Particularly for illposed problems strange things can happen.

Therefore, we do not consider what you report a bug. It is a feature of a nasty problem and that computations doing computation in 64 bit floating numbers. Welcome to the real world of finite precision computations we have to live in.

1. If you do not like the 1000 then set it to whatever you like. The choices we make are something we think the average customer like. 

2. PRSTATUS is not a parameter but an indicator computed using the search direction computed by the optimizer. It is explained somewhere in the papers about SeDuMi by the late Jos Sturm.

  

This paper

   https://arxiv.org/abs/2203.02795

discusses facial reduction for LP. It is actually based on a specialization of ideas for SDP. Applying facial reduction (which I do no claim is easy) is probably the way to go for you.

[Mateus Araújo]

There's no need to be so hostile. I took me a lot of work to prepare this bug report, and I did it with the intention of helping MOSEK. You seem to have take it as a personal insult instead.

I'm familiar with facial reduction. It is in fact how I managed to prove that the correct solution of the problem is 0. I used this paper https://arxiv.org/abs/1706.03705 , which covers SDPs.

[Erling D. Andersen]

I apologize for sounding hostile.  Thanks for the report but there is little we can do as of now.

PS. Version 10 is often much faster than version 9 but about as accurate as version 9.