# what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of solving the following problem:

\begin{aligned} & \underset{ x }{ \text{ minimize} } && || x_q - x || \\ & \text{subject to} && r_i^\intercal x \le c_i & i=1 \ldots n \end{aligned}

Where $x,x_q \in \mathbb{R}^d$. Which is, in words "find the nearest point in a polytope to some point $x_q$". I'm told by a colleague that it's $O(n^3)$, but he isn't certain about that. Also, how does complexity scale with dimension? Is it $O(d n^3)$?

• I saw something somewhere about complexity being better if you know that $Q$ is positive definite (where $Q$ is the matrix in the quadratic). In this case $Q=I$ so perhaps that's better? – cheshirekow Feb 22 '12 at 20:27
• Well, another discussion with a colleague and we've determined it is $\Omega(n^3)$. The proof is the following: given that the set of active constraints is known, then calculating the pseudo inverse is $\Omega(n^3)$ as there may be $n$ active constraints. So... can the set of active constraints be found in $O(n^3)$ time? – cheshirekow Feb 24 '12 at 13:17

Your problem is usually denoted as the projection of a point on a polytope, and it is a convex quadratic optimization problem solvable in polynomial type. The complexity is around $O(n^3)$, but check the details for instance here