When does the center of a set of points lie in the convex hull?

Question

Suppose we are given $n$ points $X_1,X_2\dots X_n$ in $d$-dimensional Euclidean space $\mathbb{R}^d$. I'm interested in understanding some properties of the ``center'' of $\{X_i\}_{i=1}^n$ w.r.t $L_p$ norm, for $p \geq 1$ $$ \min_{X} \sum_{i=1}^n\|X-X_i\|_p. $$

For what values of $p$ does the minimizer of the above problem lie in the convex hull of $\{X_i\}_{i=1}^n$?

PS: When $p=1$, the solution to the above problem is the coordinatewise median. When $p=2$ the minimizer is called the geometric median.

Answer 1

Partial answer for $p=1$ and $d=2$. We are given $n$ points $(x_i,y_i)$ and we are looking for a point $(x,y)$ so that $$\sum_{i=1}^n |x-x_i|+\sum_{i=1}^n |y - y_i|$$ is minimum, equivalently, both $\sum|x-x_i|$ and $\sum |y - y_i|$ are minimum. It is easy to see that the solution in the dimension $d=1$ case is the median. So both $x$ and $y$ are the medians of respectively $(x_1, \ldots, x_n)$ and $(y_1, \ldots, y_n)$.

Let $A$ be a point in the set with $x$ coordinate the median, and $B$ a point in the set with the $y$ coordinate the median. If $A=B$, we are done. Otherwise, the intersection of the vertical through $A$ and horizontal through $B$ will be the optimal point. Now to show that the green point is in the convex hull, it is enough to show that there exists a red point in the (cf. the picture) third quadrant. Note that there are at least $[n/2]$ points to the left of $A$. It all these were strictly below the vertical through $B$ we would have $[n/2]+1$ ($1$ counts $A$) points strictly below $B$, a contradiction.

$\bf{Added:}$ Here is a counterexample for $3$ points in $\mathbb{R}^3$: $A=(0,1,3)$,$B=(1,3,0)$, $C=(3,0,1)$. The median point $(1,1,1)$ (the unique minimizer) does not lie in the plane spanned by $A$, $B$, $C$ of equation: $x+y+z=4$. We can now consider the points $A$, $B$, $C$ with some multiplicity $(2k+1)$ and then wiggle them a bit to get a counterexample with $3(2k+1)$ points in general position.

The same idea works in spaces of odd dimension.

Also, whenever we have a counterexample for an odd number of points (odd implies unique minimizer) for the metric $L_1$, we get a counterexample for the $L_p$ metric, for all $p>1$ close enough to $1$.

$\bf{Added:}$ Here is counterexample for the metric $L_p$, $p>1$, $p\ne 2$. Since the norm $L_p$ is strictly convex the minimizer is unique.

Consider $n\ge 3$ points in $\mathbb{R}^n$, $A_i = (0,0,\ldots, 1, \ldots, 0) = (\delta_{ik})_{k=1}^n$. Since this set is invariant under the permutation of coordinates, the corresponding minimizer is also invariant, that is all its coordinates are equal. Now we only have to check that $(1/n, \ldots, 1/n)$ is not a minimizer (recall $p\ne 2) $. For this it is enough to show that the function $$[0,1]\ni t \mapsto (n-1) t^p + (1-t)^p$$ is not minimum at $t=1/n$. Now check that the derivative at $t=1/n$ equals $$\frac{p}{n^{p-1}}( (n-1) - (n-1)^{p-1}) \ne 0$$

By fattenning and wiggling we can also get a counterexample with points in generic position.

Answer 2

Partial answer for $p=2$ (the easy case).

In all cases $f$ is convex and $\lim_{\|x\|_p \to \infty} f(x) = \infty$ so a minimiser exists.

Suppose $x \notin \operatorname{co} \{ x_k \}$. Then $f$ is differentiable at $x$ and ${\partial f(x) \over \partial x}= \sum_k {(x - x_k)^T \over \|x-x_k\|_2}$. If ${\partial f(x) \over \partial x} = 0$ then an easy computation shows that $x \in \operatorname{co} \{ x_k \}$, a contradiction. Hence $x$ cannot be a minimiser.

Partial counterexample for $p=1$.

Let the points be $(0,0), (2,0), (2,0), (-1, 1), (-1, 1), (-1, 1)$ (yes, some points are repeated). It is easy to see that the minimisers are the square $[-1,0]\times [0,1]$, but not all of these points lie in the convex hull.