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

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 
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 xaxis and the computation time on the yaxis. For interiorpoint 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 interiorpoint methods it requires O(N^3(number of decision variables^3)) operations.
Is Gurobi a generalpurpose solver or is it specifically designed for model based predictive control applications? If it is a generalpurpose 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 interiorpoint algorithm, give me the same objective function value and optimized values x, but GPAD, a firstorder 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 interiorpoint 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.
Comments
2 comments