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