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. 



Minimum norm of convex hull
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. 


