Minimum norm of convex hull

Question

I am currently stuck at a problem which seems too easy to be stuck at to me...

Summary

Let $H$ be the convex hull of the points $d_1,\ldots, d_n\in \mathbb{R}^d$. How can one compute \[\min_{x\in H}||x||^2_2 \] efficiently?

Conditions one should know about

When I talk about efficiency in this question, I do not talk about a polynomal time algorithm. For my purpose, $n$ is really small, $n=4$ should do in almost all cases. (Even a fast solution for the special case $n=4$ would be highly appreciated). Also, $d=2$ is the main dimension of interest, whereas it might be possible that at some time this might also be a question for the three dimensional space. This question is embedded in an algorithm that will be called thousands of times within a very short timeframe. In short, I am looking for an efficient way in terms of "Do I need 20 or 40 FLOPS"...

First thoughts

Of course, one could take this problem as a Quadratic Program by writing $D=[d_1,\ldots, d_n]$ and then minimizing $x^tD^tDx$ with respect to $\sum_{i=1}^d x= 1$ and $x_i\geq 0$. However, I just feel this might be overkill for such a simple problem.

I also thought about taking a least norm approach, but here I do not really get a grip on formulating the problem the right way to throw some (to me) known technique at it.

Also, one could compute the convex hull explicitly and then try to locate 0 geometrically around the hull and only compute the corresponding distance to the hull. As I made a rough sketch to the algorithm I had in mind, I realized this also gives me quite a lot of things to compute and cases to distinguish between.

Your ideas would be greatly appreciated.

Answer 1

The following iterative algorithm is perhaps fast:

Set $P=d_i$ where $d_i$ is of minimal norm among $d_1,\dots,d_n$.

Iterate the following loop:

Let $j=j(P)$ be an index such that $\alpha=\langle P,d_i-P\rangle/\sqrt{\langle d_i-P,d_i-P\rangle}, i=1,..n$ is minimal for $i=j$.

If $\alpha\geq 0$ then $P$ is at minimal distance. (If $\alpha>-\epsilon$ for small $\epsilon$ you are very close to the minimum.)

Otherwise replace $P$ with the point closest to the origin of the line joining (the old point) $P$ to $d_j$.

End of Loop.

In dimension $d=2$ and if the origin is not in the convex hull, this algorithme will ultimately only involve the two endpoints among $d_1,\dots,d_n$ of the edge realising the minimum (generically).

Answer 2

Dear all,

I think I found quite a neat solution for my problem. At first I want to give humble thanks to Roland, who greatly inspired the solution I'm going to use now. Just in case somebody else might sometimes in the future be struggling with a similar problem, I'm going to give a short outline of the ideas and a rough sketch of the algorithm. After some consideration I decided to go down to only two dimensions, as this allows some neat tricks.

To go along with the notation I use in my own work (and which I did not use asking the question), let $X=\{x_1,\ldots, x_n\}$ be the set that spans the convex hull $H$.

First I want to reflect the main ideas, which I am certain are very obvious to most of you.

1. Let $P=\arg\min_{x\in H}||x||_2^2$. It is either $P\in H$ and thus $P=0$, or $P$ lies on the boundary of $H$, which means there are $x,'x\in X$ and $c\in[0,1]$ with $P=cx+(1-c)x'$.
2. Let now \[ \delta:=\min_{i=1,\ldots,n}\min_{j=i+1,\ldots, n}\min\left{||x||_2^2: x=cx_i+(1-c)x_j, c\in[0,1]\right}. \] Because of 1. we have $\min_{x\in H}||x||_2^2\in\{0,\delta}$.
3. To compute $\delta$, a lot of minimum norms $d$ on line segments from $x_i$ to $x_j$ have to be computed. By usage of the scalar product and simple usage or pythagoras, one can derive the distance as \[ d=\begin{cases} ||x_i||^2_2 & \text{if } \langle x_i,x_i-x_j\rangle \leq 0\\\\ ||x_j||^2_2 & \text{if } \langle x_i,x_i-x_j\rangle \geq ||x_i-x_j||_2^2\\\\ ||x_i||^2_2-\frac{\langle x_i, x_i-x_j\rangle^2} {||x_i-x_j||^2} & \text{ otherwise}. \end{cases} \]
4. The point $P$ realizing the minimum distance in this case is \[ P=x_i+\frac{(x_j-x_i)\langle x_i, x_i-x_j\rangle}{||x_i-x_j||_2^2} \]
5. Given $\delta$ and the Point $P$ realizing $\delta$, the following holds: $0\in H$ if and only if there exists $x_k$ with $\langle P, P-x_k\rangle >0$. (Very compact proof: If one of those exists, one can reduce $\delta$ by using the method of 3. As the new minimum may not lie on the boundary as it has not been found in the first run, $0\in H$ has to hold. Otherwise assume $0\in H$ and no scalar product fulfills the given condition. Then one can write $0$ as convex combination of the $x_i$ and express $0<||P||_2^2=\langle{P,P-0}\rangle$ and, using linearity of the scalar product, show that this is $\leq 0$ and thus getting a contradiction).

Putting all of this together one yields the following algorithm:

---

1. Init $d_\min = \infty$.

2. For $i\in\{0,\ldots, n-1\}$ do:

   1. Compute $n_i$ = $||x_i||_2^2$
   2. For ($j \in \{i+1,\ldots, n-1\}$ do
      1. Compute $s_{i,j}=\langle x_i, x_j\rangle$.
      2. Compute $n_j=||x_j||_2^2$.
      3. Decide:
         • If $s_{i,j}\geq n_i$ set $d=n_i, c=1$.
         • If $s_{i,j}\geq n_j$ set $d=n_j, c = 0$.
         • Else set $c = (n_i-s_{i,j})/(n_i+n_j-2s_{i,j})$ and $d=n_i- (n_i-s_{i,j})\cdot c$.
      4. If $d<d_{\min}$ set $d_{\min}= d$, $j_{\min}= j$, $i_{\min} = i$ and $c_{\min} = c$.

3. For $k\in\{0,\ldots,n\}\setminus\{i,j\}$ do: If $d > (1-c)s_{i,k}+c s_{j,k}$ return 0.

4. Return $d_\min$.

---

This algorithm is based on the rules 1-5 above, however, the conditions are formulated a bit more efficient. Please apologize the incomplete reasoning. I found this solution appealing as it allows a lot of optimization in my special scenario. I already computed all norms of the $x_i$ somewhere else, so this is no further effort. Furthermore, the parent algorithm scans a set of values, successively replacing one $x_i$ with another $x_i'$ and then again computing the distance to the convex hull. This means that most of the distances can be saved and used later and for each iteration I only have to do very little work in updating and computing very few (as for my main problem, where $n=4$ it is 3) scalar products.

Thank you for your support and the in fact very valuable input.

Answer 3

Well, if you are in two dimensions, and have four points, your convex hull is either a triangle, or a union of two triangles. If you have three points, then the problem is a simple lagrange multiplier problem, with three equations and three unknowns, so you can easily write out the solution explicitly. If the solution has all the coefficients positive, you win. If not, do it for the edges (two equations with two unknown each). Then loop over the four possible triangles. Notice that a lot of that can be done in parallel, so while the flop count is a couple of hundred (I am guessing), it looks like 20 if done on GPU (from your phrasing, I am guessing this is a graphics hack).