Take the 2-minute tour ×

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)$?

share|improve this question
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

2 Answers 2

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


There exists some specialized algorithm for projections, as for instance in the case in which the linear inequalities actually define a simplex. I would suggest you to search the internet for that.

share|improve this answer

The brute force method is to construct the polytope given by those linear inequalities and then find the nearest point, to the given point, for each face of the polytope. For the brute force method the complexity $O(n^3)$ seems reasonable. Apparently using quadratic programming for such distance calculations is frowned upon, because i recently asked a very similar question and got '(using) quadratic programming to find the minimum distance is swatting flies with a sledgehammer.' as a response. I got the whole idea of computing such distances with quadratic programming from Dave Eberlys 'geometric tools'. For example read this discription of his. He doesn't say anything about the complexity unfortunately.

share|improve this answer

Your Answer


