When is the smallest point on a hull a convex combination of the smallest vertices?

Let $x_1, \dots, x_n\in\mathbb{R}^d$ be a finite set of points and denote the convex hull by $H$. Assume that $0\not\in H$ and also that each $x_i$ is an extreme point, meaning that it cannot be expressed as a convex combination of the remaining points.

Consider the smallest element in the hull

$$x^* := \arg\min_{x \in H} |x|^2$$

By Caratheodory's theorem, $x^*$ can be expressed as a convex combination of $d$ of the points $x_1, \dots, x_n$. Is it true that $x^*$ is a convex combination of the $d$ smallest points ?

While this seems like a plausible hypothesis, the answer is no. For example, consider $x_1=(2,0), x_2=(0,1)$ and $x_3=(2/5+\epsilon,4/5+\epsilon)$. It's easy to see that $x^*=(2/5,4/5)$, but $x^*$ cannot be written as a convex combination of $x_2$ and $x_3$.

However in this counterexample, the points are nearly co-linear. So it seems possible that the statement could be true assuming that the points are sufficiently "generic." So I will reformulate the original question:

Is there a sufficient condition which implies that $x^*$ is a convex combination of the $d$ smallest points? If not, is it at least true with high probability under reasonable sampling assumptions?

Solution 1:

Is it true that $x^∗$ is a convex combination of the d smallest points ?

Not in general, consider the following example in the plane $\mathbb{R}^2$ :
Consider the points $A(0; 1), B(6; 0), C(2; 2)$ and $S := \{A; B; C\} $ . The convex hull $H$ of $S$ is the triangle $ABC$. The two points in $S$ that are closest to $O$ are $A$ and $C$.
Clearly, $x^*$ lies on the line segment $[AB]$ and not on the line segment $[AC]$.

Is there a sufficient condition which implies that x∗ is a convex combination of the d smallest points? If not, is it at least true with high probability under reasonable sampling assumptions?

No reasonable assumption I'm affraid : the counter-example above hints that you should at least require the dimension of $H$ to be strictly less than $d$.