I need to find the extreme points of the set $\mathcal{A} = \{(x_{1},x_{2}, x_{3}) \in \mathbb{R}^{3}: |x_{1}|+|x_{2}|+|x_{3}|\leq 1\}$.
I have already found that $\mathcal{A}$ is convex, closed, and bounded.
The definition of an extreme point given in my text is the following:
A point $x$ of a convex set $X$ is called an extreme point of $X$ if no other points $u\in X$ and $v\in X$ exist such that $\displaystyle x = \frac{1}{2}u + \frac{1}{2}v$.
This definition doesn't really make a whole lot of sense to me, though. It's very awkwardly worded. I checked another book and found a definition I like better:
A vector $x$ is said to be an extreme point of a convex set $C$ if $x$ belongs to $C$ and there do not exist vectors $y,z \in C$, and a scalar $\alpha \in (0,1)$ such that $$ y \neq x, \, z\neq x, \,\, x = \alpha y + (1-\alpha) z. $$
It goes on to say that an equivalent definition is that $x$ cannot be represented as a convex combination of some vectors of $C$, all of which are different from $x$.
However, neither of these books tell me how to go about finding extreme points. Indeed, I have searched the internet, and cannot find any examples of finding extreme points that are helpful.
Therefore, I was wondering if someone could please tell me how to go about doing it.
Thank you.
EDIT: I realize this is an octahedron, and my intuition tells me that the extreme points are the vertices, but I don't know how to show this, nor do I know how to show that these are the ONLY extreme points. Please help.
Best Answer
Generally the procedure is to guess & verify.
In this case your intuition is correct, Since ${\cal A} = \operatorname{co} \{ \pm e_k\}_{k=1}^3 $ (unit vectors) you need only check that these points are indeed extreme points since all other points cannot be extreme points.
To see why no other point can be an extreme point, suppose $x \in \operatorname{co} \{b_k\}_k$ (with the $b_k$ being distinct and finite in number) and $x \notin \{ b_k \}_k $. Then $x = \sum_k \lambda_k b_k$ where $\lambda_k \ge 0$, $\sum_k \lambda_k = 1$. Since $x \notin \{ b_k \}_k $, there must be at least one $\lambda_i \in (0,1)$. Then $x = \lambda_i b_i + (1 -\lambda_i) {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$ and since $b_i, {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k \in \operatorname{co} \{b_k\}_k$ we see that $x$ cannot be an extreme point. Hence the extreme points must be a subset of the $b_k$.
(Aside: The above proof is not quite correct as it is possible that $b_i = {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$. If this is the case, then we can write $x = {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$ and repeat the process as necessary until $b_i \neq {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$.)
To see why the $\pm e_k$ are extreme, we have the following useful result:
Suppose $C$ is convex, $h$ some direction, and that $b \in C$ is the unique solution to the problem $\langle h, b \rangle = \sup_{c \in C} \langle h, c \rangle$. Then $b$ is an extreme point of $C$. (This is straightforward to prove by contradiction.) Note that this is a sufficient, not necessary requirement for $b$ to be extreme.
Proof: Suppose that $b \in C$ is the unique solution to the problem $\langle h, b \rangle = \sup_{c \in C} \langle h, c \rangle$ for some direction $h$, but that $b$ is not an extreme point. Then there are $y,z \in C$ distinct from $b$ and $\alpha \in (0,1)$ such that $b= \alpha y + (1-\alpha)z$. Since $\langle h, b \rangle = \sup_{c \in C} \langle h, c \rangle \ge \alpha \langle h, y \rangle + (1-\alpha) \langle h, z \rangle = \langle h, b \rangle $, we see that $\langle h, y \rangle = \langle h, z \rangle= \langle h, b \rangle$, which contradicts the fact that $b$ is the unique minimiser.
If we choose $h = e_1$ then we see that $\langle e_1, e_1 \rangle = 1 =\sup_{x \in {\cal A}} \langle e_1, x \rangle$, hence $e_1$ is extreme. The other points follow in a similar manner.