4
$\begingroup$

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

  • 0
    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?2012-02-22
  • 0
    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?2012-02-24

1 Answers 1