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
    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

1

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.

  • 0
    which chapter in book?2018-04-17