Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Dear all,

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.

share|improve this question
    
I think that you are trying to find the point in H that is closest to 0. If your hull is not containing 0, then the solution is one of your di points. If it includes 0, then your solution is 0 –  Anadim May 4 '11 at 2:23
    
@Anadim: It does not have to be one of the $d_i$-points if $0\not\in H$. The searched point could also lie on any line segment between $d_i$ and another $d_j$ (assuming they both lie on the boundary of the convex hull). Also note that while finding the Point in $H$ closes to the origin solves the problem, I am only interested in the minimum distance. –  Thilo Schneider May 4 '11 at 5:29

3 Answers 3

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

share|improve this answer
    
Thank you. Looks promising at a first glance. I will have a more in depth look tomorrow and will probably accept your answer then. –  Thilo Schneider May 3 '11 at 20:20
    
@Roland: Consider 3 points $d_1=(1,N)$, $d_2=(1,-N)$ and $d_3=(2,0)$, where $N$ is large. I'm afraid that $P$ will not reach the segment $[d_1d_2]$ in finitely many steps, and it will converge rather slowly (like $O(N)$ iterations per digit of output). –  Sergei Ivanov May 3 '11 at 21:28
    
@Sergei: Thank you for pointing out. Currently I assume you can easily rescue Rolands algorithm without increasing the computational effort a lot. Will give feedback once I am more certain (a.k.a once I got my idea proven). –  Thilo Schneider May 4 '11 at 6:36
    
Sergei: You are of course absolutely right, the algorithm is iterative but does generally not stop and does not converge very quickly in your example. However, its values for $P$ oscillate between $d_1$ and $d_2$ which shows that the minimum is achieved by the segment joining $_1$ and $d_2$. Once this is known, one can use this information and drop the point $d_3$ from the initial set. The algorithm converges then in one iteration to the minimum and doing a last iteration with all three points proves that we have the minimum. –  Roland Bacher May 4 '11 at 8:19

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

share|improve this answer
    
Thanks for the input. I believe I found an algorithm that should work faster for my specific problem (which is not intended for the GPU - at least not yet). –  Thilo Schneider May 5 '11 at 20:10
up vote 0 down vote accepted

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.

share|improve this answer

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.