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.

  • $\begingroup$ Based on these definitions any point on the surface of $\mathcal{A}$ is an extreme point of $\mathcal{A}$. $x_1=x_2=x_3=1/3$ would be an example of such extreme point. Since the surface is smooth, points on it belong to a tangent plane (aka tangent space). For ex. at a given $x$ it is called $T_x\mathcal{A}$. So any straight line on the tangent plane cannot cross $\mathcal{A}$. Perhaps a more interesting problem would be to find the diameter of this region, i.e. the largest distance between 2 points in $\mathcal{A}$. $\endgroup$ – minmax Oct 16 '17 at 1:39
  • $\begingroup$ @minimax that might be a more interesting problem, but it is not the one I was assigned. Any point on the surface and not just the vertices would be extreme points? Then, how would I prove that these were the ONLY extreme points? $\endgroup$ – ALannister Oct 16 '17 at 1:43
  • $\begingroup$ By the definition you provided, any point on the surface is an extreme point. I can't think of anything else, unless you add more restrictions, such as largest $x_3$. $\endgroup$ – minmax Oct 16 '17 at 1:47
  • $\begingroup$ Is this region $\mathcal{A}$ really smooth? $\endgroup$ – minmax Oct 16 '17 at 1:49
  • $\begingroup$ @minimax $(1/2, 1/2, 0)$ is on the surface, but it's not an extreme point because $(1/2, 1/2,0) = 1/2 (1,0,0) + 1/2(0, 1, 0)$ $\endgroup$ – ALannister Oct 16 '17 at 1:51

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.

  • $\begingroup$ how do I know that no other points cannot be extreme points? $\endgroup$ – ALannister Oct 16 '17 at 2:41
  • $\begingroup$ what are the $\{ b_{k} \}_{k}$? $\endgroup$ – ALannister Oct 16 '17 at 4:05
  • $\begingroup$ I am proving the result for the convex hull of an arbitrary finite collection of point $b_k$, not just the $\pm e_k$. $\endgroup$ – copper.hat Oct 16 '17 at 4:10
  • $\begingroup$ wouldn't a proof that a point is an extreme point of a polyhedral set if and only if it is a vertex also suffice? The problem is that I cannot find one that does not also include that the point is a basic feasible solution, and the proofs are very complicated because of that. How would I prove that if x is an extreme point then it must be a vertex? (The other direction isn't hard). $\endgroup$ – ALannister Oct 16 '17 at 4:16
  • $\begingroup$ How do you define vertex? $\endgroup$ – copper.hat Oct 16 '17 at 4:22

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.