It seems that the quadprog function of MATLAB, the (conventional) interior-point algorithm, is not fully exploiting the sparsity and structure of the sparse QP formulation based on my results.
In Model Predictive Control, the computational complexity should scale linearly with the prediction horizon N. However, results show that the complexity scales quadratically with the prediction horizon N.
What can be possible explanations?
Dear Soufyan,
It will then be necessary to make an extension concerning this question and to integrate it into Matlab, in this regard I suggest you to see links and attached files on topic.
https://sites.calvin.edu/tmk5/research/optim_tb.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.720.6815&rep=rep1&type=pdf
https://support.dce.felk.cvut.cz/mediawiki/images/9/94/Bp_2013_mikulas_ondrej.pdf
Best regards
Thanks for your answer.
I gave the wrong information. Quadprog is not exploiting the sparsity and structure of the sparse QP formulation at all. So, the computation complexity scales cubically with N.
The barrier algorithm of Gurobi was not fully exploiting the sparsity and structure of the sparse QP formulation. So, the computation complexity scales cubically with N. Do you have some documentation about this? At the Gurobi website, I could not find anything relevant to answer this question.
Could you maybe also react to my last topic about why interior point algorithm of Gurobi and quadprog give same optimized values x and corresponding objective function value , but the first-order solver GPAD gives the same optimized values x, but another objective function value which is a factor 10 bigger?
https://www.researchgate.net/post/How_is_it_possible_to_get_the_same_optimized_values_x_but_a_different_objective_function_value_using_different_QP_solvers
Your answers are always really helpful.
Regards
It's not a surprise: standard Matlab is not devised to recognise sparsity, for example. You have to pay a lot more - or code your own. There are plenty of specialist codes for very important problems, and typically they are coded from scratch such that the structure of the problem will be exploited as well as possible.
One particular structure is the graph, and decision problems associated with those. The shortest path, the transportation problem, linear assignment, and many other have in common that searches in networks are really fast. So we would say that it is an easy problem - in principle - although there probably are extremely large networks being investigated, for which there might still be necessary to develop more sophisticated tools than the ones we have now.
- Badges
- Science topic