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

• Official comment

  

  Simranjit Kaur

  Gurobi Staff

  • December 06, 2024 00:48

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  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

Post is closed for comments.