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.

  • $\begingroup$ 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)$. $\endgroup$ – copper.hat Oct 16 '17 at 16:56
  • $\begingroup$ @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. $\endgroup$ – ALannister Oct 16 '17 at 16:59
  • $\begingroup$ 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. $\endgroup$ – copper.hat Oct 16 '17 at 17:01
  • $\begingroup$ @copper.hat I did not find that drawing very helpful. What is it that I'm supposed to be looking for? $\endgroup$ – ALannister Oct 16 '17 at 17:11
  • $\begingroup$ For the recession cone, what directions can you move the entire set such that it remains with in ${\cal B}$? $\endgroup$ – copper.hat Oct 16 '17 at 17:12

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$.

  • $\begingroup$ 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}$. $\endgroup$ – ALannister Oct 19 '17 at 22:43
  • $\begingroup$ 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. $\endgroup$ – copper.hat Oct 20 '17 at 0:08
  • $\begingroup$ how do you show this though? Like what about the case when $x_{1} < x$? $\endgroup$ – ALannister Oct 20 '17 at 2:39
  • $\begingroup$ 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$! $\endgroup$ – ALannister Oct 20 '17 at 3:03
  • $\begingroup$ 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?? $\endgroup$ – ALannister Oct 20 '17 at 3:14

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.