1

Given a set of points $ P = \{p_0,p_1,...,p_m\} $ where $ p_i \in \mathbb{R}^n $ and $ m > n+1$ denote by $ \mathcal{C}(P)$ the convex hull of $P$ and by int $\mathcal{C}(P)$ the interior of the convex hull of $P$ (that is excluding the boundary).

Let some $ x \in $ int $\mathcal{C}(P)$. Show that there exists a convex combination of the elements of $P$ such that $ x = \sum_{i=1}^{m} \alpha _i p_i$ with no $\alpha_i = 0$.

I understand that in general convex combination means $ \alpha _i \geq 0$ but I want to prove this stricter result. How do I go about doing it?

The idea is this: Suppose there are different convex representations for $x$ where some of the $\alpha _i =0 $ but no particular $\alpha_i$ is zero in all of them. Then a convex combination of the convex representations will give me a new representation where none of the $\alpha_i$ are zero.

Can anyone give me any clues on how to go about showing that there will indeed exist

  1. A convex representation (I think applying Farkas' Lemma does this?)
  2. In fact many convex representations (Carathéodory's theorem? Since $ m > n + 1$?)
  3. A subset of these many convex representations where no particular $\alpha _i$ is zero all the time.
Hosein Rahnama
  • 14,882
ITA
  • 1,813
  • Well, people usually are concerned with extreme points that indeed cannot be written using a strict convex combination. The proofs are actually based on definitions, I don't know if it is satisfactory for you. (If $x$ is not extreme point, then it is interior point by definition) – Slowpoke May 25 '16 at 06:39
  • Definition, page 20 – Slowpoke May 25 '16 at 06:46
  • Here is my approach so far. Any point $x \in$ int$\mathcal{C} (P)$ will exist on a line joining some vertex $p_0$ and either (a) another extremal point, (b) a face or an (c) edge. Call this endpoint $y$. Then the $ x = p_0 + (1-k)y$ is a convex representation. Then consider the point $y$ itself. It will have its own convex combination in terms of vertices of that face or edge. Expand these nested convex representations to get a full convex combination in terms of vertices of $\mathcal{C}(P)$ alone. If any vertex is left out, use that as starting point and make a different convex combination. – ITA May 25 '16 at 14:14
  • Once enough convex representations are generated that all vertices have been included, make a new convex combination out of them. Then no $\alpha_i$ will be zero. I am just not familiar with enough higher dimensional geometry to properly formalize this and also know whether degenerate/exceptional cases exist and need to be taken care of. – ITA May 25 '16 at 14:16

  • If any vertex is left out, use that as starting point and make a different convex combination >> If we started this way, then here is the first problem: we don't know whether you can find the combination that includes all the base points for arbitrary inner point (and do not know that it doesn't exist for extremal). You're basically using the same assumption as them, but it seems for me that you actually want to derive it.

     – Slowpoke May 25 '16 at 14:50
  • 1
    To just prove the existence we can follow your procedure from the other side: take $p_0$ and $p_1$ and $k_1>0$ and find the point $y_1=k_1p_0 + (1-k_1)p_1.$ Then take $p_2$ and some another $k_2>0$ and construct $k_2p_2+(1-k_2)y$ and so on. We need to take such a values of $k_i$ that our convex combination won't reduce. If it happens, we just take slightly another coefficient. As long as we have infinite number of numbers and finite number of basis points, we always can do it. At last we will get the point that belongs to the interior (see result above). – Slowpoke May 25 '16 at 15:41
  • 1
    Why interior point: by definition of inner point it is included with some ball around it. We can draw some lines in this ball that have our point $x$ on them, and $x$ can be represented as convex combination of some elements from $P$: there are some $y,z \in P$ that $x = ty + (1-t)z$. By the result above we cannot remove such inner point $x$, because $C(P)\setminus{x}$ becomes non-convex (one interval will fail the condition of convexity). The points for which strict convexity conditions doesn't satisfy exist only on the end of line segments, i.e. on vertices, edges or faces. – Slowpoke May 25 '16 at 15:47

1 Answers1

1

Let $\Sigma = \{ \mu \in [0,1]^m | \sum_i \mu_i = 1 \}$. Note that $\Sigma$ is convex and if $\mu,\mu' \in \Sigma$ are such that $\mu_i >0, \mu'_j >0$ then with $t \in (0,1)$ and $w = t\mu+ (1-t)\mu')$ we see that $w_i>0$ and $w_j>0$.

Let $C= \operatorname{co} \{ p_i \}_{i=1}^m$, and let $x \in C^\circ$. Then there is some $\mu \in \Sigma$ such that $x = \sum_i \mu_i p_i$.

Now choose any $p$, then there is some $\delta>0$ such that if $|t|< \delta$ then $x+t (p-x) \in C^\circ$. If we choose $0 < t < \min(\delta,1)$ then there is some $\mu' \in \Sigma$ such that $x-t(p-x) = \sum_i \mu_i' p_i$ and hence $x = { 1\over 2} (x-t(p-x) + x+t(p-x) ) = { 1\over 2} ( \sum_i (\mu_i' + (1-t) \mu_i)p_i + t p)$.

In particular, the multiplier of $p_i$ is positive if $\mu_i>0$, and the multiplier of $p$ is also positive.

Now choose any $j$ such that $\mu_j = 0$, and let $p = a_j$, and use the above process to get a new multiplier $\mu''$ such that $\mu''_j >0$, and also, if $\mu_i>0$ then $\mu''_i >0$ as well.

We can repeat the above until all $\mu_i >0$.

copper.hat
  • 172,524