Skip to main content

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



  • Yuriy Zinchenko
    Gurobi Staff Gurobi Staff

    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?

  • Soufyan Zayou


    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!


Please sign in to leave a comment.