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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – cheshirekow Feb 22 '12 at 20:27
  • $\begingroup$ 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? $\endgroup$ – cheshirekow Feb 24 '12 at 13:17
1
$\begingroup$

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

http://www.stanford.edu/~boyd/cvxbook/

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.

$\endgroup$
  • $\begingroup$ which chapter in book? $\endgroup$ – T.... Apr 17 '18 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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