0
$\begingroup$

A question on a quiz that I couldn't figure out:
Let X = co{$x_1, x_2,..., x_k$} where $x_i$ ∈ $\mathbb{R^n}$, $i = 1,2,...,k$. (Note: co{$x_1,...,x_k$} stands for convex hull of {$x_1,...,x_k$})
(a) Show that if $z$ is an extreme point of X then $z$ = $x_i$ for some $i$.
(b) Show that $x_1$ is NOT an extreme point of X if and only if $x_i$ ∈ co{$x_2, x_3,...,x_k$}.
Any help is greatly appreciated!

$\endgroup$
3
  • $\begingroup$ What's your definition of convex hull? $\endgroup$ Apr 12 '18 at 2:02
  • $\begingroup$ @JalexStark: My notes say that the convex hull of a set C is the intersection of all convex sets which contain the set C. $\endgroup$
    – arcanine
    Apr 12 '18 at 2:12
  • $\begingroup$ Okay. Can you prove the following characterization? A point x is in the convex hull of C iff $x = \sum_i \lambda_i c_i$ where each $c_i\in C$, each $\lambda_i \geq 0$ and $\sum_i\lambda_i =1$. $\endgroup$ Apr 12 '18 at 2:26
0
$\begingroup$

An alternate definition of convex hull may be helpful here: $$\text{co}(x_1, \ldots, x_k \} := \{z \in \mathbb{R}^d: z = a_1 x_1 + \ldots + a_k x_k , a_i \geq 0, ~ a_1 + \ldots + a_k =1 \}.$$

(a): Suppose $z \neq x_i$ for all $i=1, \ldots,k$, then $z = \sum_{i=1}^k a_k x_k$ where $0< a_j < 1$ for some $j=1, \ldots,k$. Define $$z_t := t\sum_{i=1}^k a_k x_k +(1-t)x_j = (1-t(1-a_j))x_j + t\sum_{i=1, i \neq j}^k a_k x_k,$$ then we note that $z_t$ is in the convex hull for all $t \in [0,\frac{1}{a_j-1}]$, thus as $z=z_1$ lies in the interior of the line we are done.

(b): Suppose $x_1$ is an extreme point and $x \in \text{co}\{x_2,\ldots,x_k\}$, then by part (a) $x_1= x_j$ for some $j =2, \ldots, k$. Assuming that each $x_i$ is suppose to be distinct we are done.

Now suppose $x_1$ is not an extreme point, then for some $t \in (0,1)$ we have $x_1$ lying on the line between two points: $$x_1= t\sum_{i=1}^k a_i x_i +(1-t)\sum_{i=1}^k b_i x_i = (ta_1 +(1-t)b_1)x_1 + \sum_{i=2}^k (ta_i +(1-t)b_i)x_i.$$ We can rearrange this to give us $$x_1= (1-(ta_1 +(1-t)b_1))^{-1}\sum_{i=2}^k (ta_i +(1-t)b_i)x_i $$ and then note $$(1-(ta_1 +(1-t)b_1))^{-1}\sum_{i=2}^k (ta_i +(1-t)b_i) = 1,$$ thus $x_1 \in \text{co}\{x_2,\ldots,x_k\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.