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

Soufyan Zayou

• March 23, 2020 21:07

It seems that the barrier algorithm of Gurobi is not fully exploiting the sparsity and structure of the sparse QP formulation. Does someone have a reason for that?

 

In Model Predictive Control, the computational complexity should scale linerarly with the prediction horizon N, i.e. the algorithm needs O(N(#states+#inputs)^3) operations. However, results show that the complexity scales quadratically with the prediction horizon N.

 

The computation time is measured as the time needed to solve one QP problem. 

0

• 

  Yuriy Zinchenko

  Gurobi Staff

  • March 24, 2020 01:46

  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
• 

  Soufyan Zayou

  • March 24, 2020 02:19
  • Edited

  

  

  

  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

Please sign in to leave a comment.