Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am using the Matlab built-in quadprog to solve a quadratic program with linear constraints. I vaguely recalled from school that the time complexity of quadratic programming should be $O(n^3)$, and I assume n refers to the number of decision variables. However, when I experimentally compute the execution time as a function of the number of variables in Matlab, the execution time actually increases less than linearly with more variables. Increasing the number of variables from 10 to 100 only increases the execution time by 5 times. I am very puzzled by this result and perhaps what I remembered is wrong. Can anyone shed some light on the time complexity of quadratic program in theory and in practice?

share|improve this question
    
Pretty sure that quadprog sometimes defaults to simplex-like active set methods for small problem sizes. Those algorithms are absolutely infamous for having a huge gap between theoretical complexity and actual observed runtime. It's like a dirty secret from Computer Science that is underexposed. –  Peter Sheldrick Nov 23 '12 at 1:00
    
Better bounds for the complexity the simplex algorithm was for example what the recent Hirsch conjecture media blitz was about. –  Peter Sheldrick Nov 23 '12 at 1:07

2 Answers 2

up vote 4 down vote accepted

I am not familiar with the details of the quadprog function, but I think the issues may be more universal. The cubic time complexity is an asymptotic worst-case bound. It does not mean that growing any problem by 10 times will increase running time by 1000 times. It will often be less, but may be that bad for some problem data.

There is often constant time "overhead" for many algorithms. The overhead may be so large that the running time is essentially independent of the problem size up to a certain point. The asymptotic bound only becomes relevant when comparing large problems with very large problems. In your example this will be hard to observe because quadratic programs with thousands or tens of thousands of variables can take hours or days to solve on a typical personal computer. Memory can become an issue since the problem data alone grows quadratically in the number of variables.

There is a whole industry devoted to these issues. Commercial solvers can cost tens of thousands of dollars. For specific applications, specialized solvers that exploit problem structure are often utilized. Sparsity of the input matrices is the most basic source of running time improvements.

Asymptotic worst-case bounds are often a poor guide for practical problem solving. They are certainly hard to verify using simulations. I suggest you move over to stackexchange for messy, detailed discussions of particular software implementations of algorithms.

share|improve this answer
    
Can you explain what's the cause of this "overhead" that you mention? –  littleO Nov 23 '12 at 1:12

Time complexity of Quadratic Programming.

It was proved by Vavasis at 1991 that the general quadratic program is NP-hard, i.e. it takes more than polynomial time to be solved "exactly" (in reality, its impossible to find an exact solution due to the finite precision arithmetic of the computer). If your QP is convex, there are polynomial time interior point algorithms (e.g. Ye and Tse at 1989 published an extension of Karmarkar's projective algorithm on convex quadratic programs). Also, there are approximation algorithms that return local solutions of nonconvex QPs in polynomial running time (e.g. Ye, 1998).

About quadprog's inner implementation and time-complexity.

Quadprog runs an active-set method (of exponential time-complexity for the worst case input instances) for a general QP. For a really hard QP (indefinite, with a near badly scaled Q matrix) , it may not converge to a solution. In the case that your input's QP is convex, quadprog runs an interior-point method.

I didn't ever checked quadprog's time complexity in practice, but you can't lead to an inference by just observing the running times as you scale the dimension of a given QP. It's better to generate a test set, consisting of convex and not-convex QP, manually choose the algorithm you want to be runned by quadprog for each of them, and observe the running times.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.