MSK_SOL_STA_UNKNOWN in Quadratic Programming

[tobia...@googlemail.com]

Hello,

i'm trying to use Mosek to solve a QP problem.

minimize: 0.5*x*Q*x_t + c*x_t
(no constraints on x)

whereas Q=A*A_t, i.e. is positive semi definite by construction.

I followed the C-Api example: http://docs.mosek.com/6.0/capi/node007.html#250330792

However, I found Mosek to be quite unstable while solving the system.
In many situations I can compute a correct solution, however there are also many configurations of Q and c where I can not get a solution.
Namely the computation fails in many cases because

MSKsolstae solsta;
r = MSK_getsolsta(task, MSK_SOL_ITR, &solsta);

The solsta is often MSK_SOL_STA_UNKNOWN after this call.
I can not find any information in the documentation how this can happen, i.e. what is causing the problem?
Could anybody help me please?

Regards Tobias

[Joachim Dahl]

You will need to provide an example, if you want us to help you.  In most cases, simple reformulations will improve accuracy and robustness of the solution.

--
You received this message because you are subscribed to the Google Groups "mosek" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mosek+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[tobia...@googlemail.com]

Hello,
thx for the quick answer.
Meanwhile I was able to track the error more thoroughly. I think the MSK_SOL_STA_UNKNOWN error was thrown because I increased the MSK_DPAR_CHECK_CONVEXITY_REL_TOL too high, and something got unstable internally.
I now leave this parameter to the default value.
However, for many matrices Q I construct, I get an error from Mosek that the matrix is not symmetric positive definite.
However this can NOT be the case, because Q is constructed from another matrix as Q=A*A_t, so I guess there is some numerical instability.
I made some further tests and observed that Mosek fails exactly in these cases to compute the minimum, if the Cholesky Decomposition of Q becomes numerically instable (I use the Eigen Library to compute the Cholesky decomposition).
Are there any known numerical instabilities known regarding quadratic optimization and Mosek?
Or is there any way to reformulate a quadratic progamming problem so that it becomes more stable?
Regars Tobias

[Joachim Dahl]

There are no numerical bugs that we know of...

It can be very tricky to determine if Q has nonnegative eigenvalues only, or slightly negative ones. We perform a Cholesky decomposition of Q, dropping near zero pivot elements, and that can fail.

If you have Q on factored A*A', it is normally better to use a quadratic conic formulation instead of the QP solver.