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'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
add comment

1 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
add comment

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.