Why is Gurobi is not fully exploiting the sparsity and structure of the sparse QP problem?

Comments

2 comments

  • Yuriy Zinchenko

    I am not sure I fully follow your question here.  Are you saying that you would expect O(N^#) but instead observe O(N^2)?  This would be a good thing, would it not?  Can you please clarify what you are asking?

    0
    Comment actions Permalink
  • Soufyan Zayou

    Hi,

    No, it was expected that the computational complexity would scale linearly with the prediction horizon  N, i.e. O(N) for a sparse QP problem, so the slope of the line is linear in logartimic scale with N on the x-axis and the computation time on the y-axis. For interior-point methods it requires O(N(number of decision variables^3)) operations. 

    However, the computational complexity scales with N, i.e. O(N^2), which is less good, because the computation time is increasing faster for a larger prediction horizon.

    General purpose solvers do normally not exploit the sparsity and structure of a QP problem. Therefore, the computation complexity scales cubically with N, i.e. O(N^3), which is even worse. For interior-point methods it requires O(N^3(number of decision variables^3)) operations. 

    Is Gurobi a general-purpose solver or is it specifically designed for model based predictive control applications? If it is a general-purpose solver, it should scale with O(N^3), but then it scales with O(N^2) which is positive. What could be a reason for that?

    If it a specific solver for solving MPC problems, then it should scall with O(N). However, it is scales then with O(N^2) which is less positive.

    Moreover, two additional questions: 

    The QP solvers quadprog and Gurobi, which uses the interior-point algorithm, give me the same objective function value and optimized values x, but GPAD, a first-order solver, gives me the same optimized values x, but an objective function value, which is a factor 10 bigger compared to quadprog and Gurobi. Do you know a possible explanation?

    Gurobi is not working well, because it is encountering numerical issues as discussed earlier (large quadratic objective coefficient range). However GPAD and quadprog (quadprog is using the interior-point method, which is comparable with Gurobi's barrier method) encounter these numerical issues for much larger matrices. What could be a reason for that? What can I investigate to know why this is the case? Why does Gurobi has so much problems with it, but other solvers only for very large matrices?

    Thanks in advance!

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk