# Find set of extreme points and recession cone for a non-convex set

I have already shown the set $$\mathcal{B}=\{(x_{1},x_{2})\in \mathbb{R}^{2}: x_{2}\leq (x_{1})^{2}\}$$ to be non-convex, closed, and not bounded.

Now, I need to find the set of extreme points of $\mathcal{B}$ as well as its recession cone.

Definition of a Recession Cone: Let $X\subset \mathbb{R}^{m}$ be a convex set. The set $$X_{\infty}=\{d:X+d\subset X\}$$ is called the recession cone of $X$. (Sometimes also called the asymptotic cone.)

Definition of an Extreme Point: A point $x$ of a convex set $X$ is called an extreme point of $X$ if no other points $u,v\in X$ exist such that $$x=\frac{1}{2} u+ \frac{1}{2}v.$$

My problem is that both of these definitions specifically make mention of convex sets, while I am m working with a set that is not convex. I do know, however, that a set of discrete points consist solely of all extreme points while not being a convex set, so it is possible to find them in the case of $\mathcal{B}$; I just don't be know how.

I also don't know, in general how to find recession cones.

Could somebody please show me how to do this? I would be forever grateful and it would help me tackle similar problems.

Thank you.

• It is unusual (to me, al least) to talk about extreme points & recession cones for non convex sets. In any case, draw a picture of ${\cal B}$ and the answer should be clear from there. There are no extreme points (this is easy to show) and the recession cone is just the cone generated by the direction $(0,-1)$. – copper.hat Oct 16 '17 at 16:56
• @copper.hat can you explain in a little more detail what you mean by the cone generated by the direction $(0,-1)$? I'm still having some trouble with the concept of directions generating things... Also, I did draw a picture of $\mathcal{B}$: it's the shaded area beneath the parabola $y = x^2$, including the boundary. But it's still not clear to me why it has no extreme points. Especially since sometimes curved boundaries can be extreme points. – ALannister Oct 16 '17 at 16:59
• It means all points $\lambda (0,-1) = (0, -\lambda)$ with $\lambda \ge 0$. Basically the non positive part of the $y$ axis. Little drawings are very helpful. – copper.hat Oct 16 '17 at 17:01
• @copper.hat I did not find that drawing very helpful. What is it that I'm supposed to be looking for? – ALannister Oct 16 '17 at 17:11
• For the recession cone, what directions can you move the entire set such that it remains with in ${\cal B}$? – copper.hat Oct 16 '17 at 17:12

## 1 Answer

Suppose $d$ is such that ${\cal B}+d \subset {\cal B}$.

Since $(x,x^2) \in {\cal B}$ we must have $x^2+d_2 \le (x+d_1)^2$ which simplifies to $d_2 \le 2 x d_1 + d_1^2$ for all $x$ hence $d_1 = 0$ and $d_2 \le 0$.

Suppose $d = (0, d_2)$ with $d_2 \le 0$, then is is easy to verify that ${\cal B}+d \subset {\cal B}$.

Hence ${\cal B}_\infty = \{ (0,t) | t \le 0 \}$. (Note that in general the set of recession directions is not necessarily a cone when the underlying set is not convex.)

Regarding extreme points:

Suppose $x \in {\cal B}$ and $x_2 < x_1^2$. The for sufficiently small $t>0$ we have $x_2+t < x_1^2$ and so $(x_1, x_2-t), (x_1, x_2+t) \in {\cal B}$. Since $(x_1,x_2) = {1 \over 2} (x_1, x_2-t) + {1 \over 2} (x_1, x_2+t)$ we see that $x$ is not extreme.

Now suppose $x \in {\cal B}$ and $x_2 = x_1^2$. If $x_1 = 0$ then we can see that $(-1,0), (1,0) \in {\cal B}$ and $(0,0) = {1 \over 2} (-1,0) + {1 \over 2} (1,0)$ so $(0,0)$ is not an extreme point. So we can suppose that $x_1 \neq 0$.

Since the curve $x \mapsto x^2$ is convex, we have that the line tangent to the curve lines below the curve, hence $(x, x_1^2+ 2 x_1(x-x_1) \in {\cal B}$ for all $x$ (this is straightforward to verify directly). In particular, if we choose $x = x_1 \pm 1$ we see that $(x_1,x_2) = {1 \over 2} (x_1, x_2-2 x_1) + {1 \over 2} (x_1, x_2-2 x_1)$ and so $(x_1,x_2)$ is not extreme.

(Note that the concept of extreme points doesn't really have much meaning when applied to non convex sets.)

Addendum: To show that $(x, x_1^2+ 2 x_1(x-x_1) \in {\cal B}$ for all $x$ we just need to show that $x_1^2+ 2 x_1(x-x_1) \le x^2$. This follows from the inequality $(x-x_1)^2 \ge 0$.

• when you say that $(x_{1}, x_{1}^{2}+2x_{1}(x-x_{1}))\in \mathcal{B}$, do you mean that $x_{1}^{2} = x_{1}^{2}+2x_{1}(x-x_{1})$, since now we're dealing with the case when $x_{2}=x_{1}^{2}$? I'm trying to show directly that that point is in the set, but the $y$-component is not boiling down to $x_{1}^{2}$. – ALannister Oct 19 '17 at 22:43
• No. I mean that the point $(x_{1}, x_{1}^{2}+2x_{1}(x-x_{1}))$ lines in ${\cal B}.$ That is, the second component is less than or equal to the first component squared. – copper.hat Oct 20 '17 at 0:08
• how do you show this though? Like what about the case when $x_{1} < x$? – ALannister Oct 20 '17 at 2:39
• if $x_{1}<w$, then $x_{1}^{2} < x_{1}w < 2x_{1}w$, but then how do I get that $x_{1}^{2} \leq 2x_{1}w - x_{1}^{2}$ from that? And then this only works if $x_{1} \geq 0$! – ALannister Oct 20 '17 at 3:03
• I mean, it seems like there are a million cases, subcases, sub-sub-cases, and sub-sub-sub cases, depending on whether $x = 0$ (easy), $x \neq 0$. Then when $x \neq 0$, if $x = x_{1}$, it's easy; if $x < x_{1}$, it's easy. But then, when $x _{1} > x$, we can have either $x > 0$ or $x < 0$, and in the latter of these situations, either $x_{1}$ and $x$ have the same sign or they don't...unless I'm unnecessarily complicating this?? – ALannister Oct 20 '17 at 3:14