4
$\begingroup$

For a problem I am trying to solve it appears MOSEK's Quadratic Program solver is 100 times slower than MATLAB's Interior Point solver.

Has anyone encountered this behavior in the past, or maybe could guess what sort of problem might cause this behavior?

The problem is of the form:

\begin{align} \text{min }& 0.5 x^T Q x + c^T x \\ \text{s.t. }& A x \leq b \end{align}

With more linear constraints than variables.

$\endgroup$
3
  • $\begingroup$ Can you give an example problem where you are seeing this performance difference, as well as the version of MOSEK you are using and hardware? I'm happy to invite a MOSEK developer on here to respond but your question will need a bit more detail. $\endgroup$ Oct 23, 2012 at 8:38
  • $\begingroup$ I've tried to clean your question up to make it more useful to future visitors, as it was first stated it was pretty unclear what you were asking. Please try to spend time making your question both detailed and general enough that it will be of future use to other users. $\endgroup$ Oct 24, 2012 at 1:26
  • $\begingroup$ Thanks :) of course, I would have put emphasis on the form of the problem if I knew that the primal\dual selection is critical. $\endgroup$
    – olamundo
    Oct 24, 2012 at 1:28

1 Answer 1

6
$\begingroup$

For problems of this form, you should solve the dual problem using MOSEK. In some cases this can provide several orders of magnitudes of speedup. MOSEK is tuned for the more common case

\begin{align} \text{min }& 0.5 x^T Q x + c^T x \\ \text{s.t. }& A x = b \\ & x >= 0 \end{align}

where there are many more variables than constraints.

If you contact MOSEK support at [email protected] and are willing to give us your problem then we can most likely tell what you should change to get a better performance of MOSEK. If you are not willing to provide any information (Size and density of $Q$ and $A$, other special structure to the problem) then it is hard to help you.

$\endgroup$
3
  • $\begingroup$ Your guess is correct! Indeed my problem is more of the first form. However, when I add the line param.MSK_IPAR_INTPNT_SOLVE_FORM=res.symbcon.MSK_SOLVE_DUAL; to make mosek solve the dual problem, I still get Optimizer - solved problem : the primal and no improvement in times $\endgroup$
    – olamundo
    Oct 23, 2012 at 22:53
  • $\begingroup$ @user3207, Erling, thanks for the detailed answer (and the astute guesswork). I've modified noam's question to provide the details he should have originally put in, and excised them from your answer. Feel free to edit further if you'd like to fix anything. $\endgroup$ Oct 24, 2012 at 1:29
  • 2
    $\begingroup$ MOSEK only dualize linear problems. We should print out warning when we do not dualize as requested. The upcoming version 7 does that. It is not that hard to dualize a QP by hand. It is shown in the MOSEK manuals for instance. $\endgroup$
    – user3207
    Oct 24, 2012 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.