Asymptotic Time Complexity for the interior-point-convex quadprog method for sparse matrices

Hello! I am looking to find any information regarding the asymptotic time Complexity for the interior-point-convex quadprog method for sparse matrices. I notice that the time complexity for the interior point method for quadratic programming is generally O(n^3) or O(n^3.5) in the literature, but I notice (and it is noted in the following documentation as well https://www.mathworks.com/help/optim/ug/quadratic-programming-algorithms.html#bsqspm_) that when the matrix passed in as an argument is sparse, the algorithm runs faster (much faster).

I am wondering if anyone knows the answer to this question or where I can find information on the asymptotic time complexity for the interior point method for sparse matrices.

Answer 1

[nick]

Hi Aditya,

I understand that you want to know more about the asymptotic time complexity for interior point method for sparse matrices.

There is polynomial time interior point algorithm for convex QP. Also there are approximation algorithms that return local solutions of non-convex QPs in polynomial time. The following documentation will help you regarding the time complexity of Quadratic Programming:

https://math.stackexchange.com/questions/205627/time-complexity-of-quadratic-programming

Hope this helps.