1
$\begingroup$

enter image description here

a. We have that feasible directions is given by $D=\{d\neq 0:\overline x+\lambda d\in S,\lambda\in(0,\delta)\ for\ some\ delta>0\}$.

Thus I have to find $\delta>0$ such that $(\lambda d_1\ \lambda d_2)^t\in S$.

But I don't know how to do it. I already draw $S$ (it's an infinite positive rectangle with missing right corner side)

A direction $d$ is an attainable directions if $\exists\delta>0$ and $\alpha:\mathbb R\to\mathbb R_n$ such that $\alpha(\lambda)\in S$ and $\alpha(0)=\overline x$ and $d=\lim_{\lambda\to0^+}\frac{\alpha(\lambda)-\alpha(0)}{\lambda}$.

Here again I don't know how to find the delta and the alpha function,

Please someone help me how to construct both of them?

Thanks in advance for your patience :)

$\endgroup$
3
$\begingroup$

For me, it is easier to understand the definitions if you look at the geometry of the sets $S$. I'll look at parts a. and c. here.

Before we start, I think you're missing something small from the definition of attainable directions. I think it should read:

A direction $d$ is attainable at $\overline{x}$ if there exists $\delta>0$ and $\alpha:\mathbb{R}\to\mathbb{R}^n$ such that $\alpha(\lambda)\in{S}$ for all $\lambda\in(0,\delta)$, $\alpha(0)=\overline{x}$, and $$\lim_{\lambda\to0^+}\frac{\alpha(\lambda)-\alpha(0)}{\lambda}=d.$$

Part a. Our set $S$ looks like this: feasible region for part a

where the shaded region is the set $S$. The hatched region is both the cone of feasible directions and the cone of attainable directions at the point $(0,0)$ (they are the same in this example).

Cone of Feasible Directions

The cone of feasible directions at $(0,0)$ (which we denote $D_0$) are essentially the points that can be connected to the origin with a straight line, while staying in the set $S$. For example, the point $(0,1)$ is in $D_0$ because it's a non-zero vector, and $$ (0,0)+\lambda(0,1)=(0,\lambda)\in S\text{ for all }\lambda\geqslant0. $$ So in this case, we could take $\delta$ to be any positive real number. Let's look at a point where we can't do that.

Consider the vector $(-2,-2)$. We want to show that this point is in $D_0$, so we need to find the $\delta>0$ that satisfies the definition. We want that $$ (0,0)+\lambda(-2,-2)=(-2\lambda,-2\lambda)\in{S} $$ for all $\lambda\in(0,\delta)$. Looking at the picture, the farthest we can go is to the point $(-1,-1)\in{S}$. Hence, we must take $\delta\leqslant1/2$ ($\delta=1/2$ will do just fine).

Now let's look at a counter-example: why is the point $(1,1)$ not in $D_0$? If it were, we should be able to find a $\delta>0$ which satisfies the definition, so that $$ (0,0)+\lambda(1,1)=(\lambda,\lambda)\in{S} $$ for all $\lambda\in(0,\delta)$. Looking at the picture, it is clear that no such $\delta$ exists. As a proof: suppose such a $\delta>0$ exists. Take $\lambda=\min\{\delta,1/2\}$. Then the point $$ (0,0)+\lambda(1,1)=(\lambda,\lambda)\not\in{S}, $$ a contradiction.

To write it out formally, we have $$ D_0=\{d\in\mathbb{R}^2\ |\ d_1\leqslant{d_2}\text{ and }d_1\leqslant0\}$$

Cone of Attainable Directions

In this example, these cones are the same. I'm going to skip ahead to part c., where they are different, so that the difference is clearer.

Part c. Now our feasible set $S$ looks like this (I have marked the origin with a black dot for clarity).

feasible region for part c

Cone of Feasible Directions

Recall that intuitively, the cone of feasible directions are the points that we can connect to the origin with a straight line, while staying in the set $S$. Since the set $S$ in this case isn't a straight line, you might expect that $D_0$ is empty. Indeed, it is empty. To prove this, suppose not, i.e. suppose there exists $(d_1,d_2)\in{D_0}$, with associated $\delta>0$. Then for all $\lambda\in(0,\delta)$, we must have $$ (0,0)+\lambda(d_1,d_2)=(\lambda d_1,\lambda d_2)\in{S}, $$ which means that $$ \lambda d_2=-\lambda^3 d_1^3 $$ for all $\lambda\in(0,\delta)$. Since $\lambda>0$ we can divide by it: $$ d_2=-\lambda^2 d_1^3. $$ Since this holds for all $\lambda\in(0,\delta)$, we must have that $d_1=0$. (To see this, suppose $d_1\neq0$. Then we can divide by it to get $(-d_2/d_1^3)=-\lambda^2$. The left hand side is a constant, while the right hand side is an arbitrary scalar in $(0,\delta)$, a contradiction.) So $d_1=0$ thus $d_2=0$. This is contradiction ($d$ must be non-zero if $d\in{D_0}$). Hence $D_0=\varnothing$.

Cone of Attainable Directions

Even though the cone of feasible directions $D_0$ is empty, when we look at the picture above, it looks as though we should be able to move from side to side a little bit, and remain feasible. This is the idea that the cone of attainable directions (which we notate $A_0$) captures.

So we guess that $(1,0)\in{A_0}$. How do we prove it? We need the function $\alpha$. All that $\alpha$ is is a path in $S$ that goes to the point $(0,0)$. This path $\alpha$ doesn't have to be straight (note: the cone of feasible directions is just the cone of attainable directions with the extra restriction that the paths $\alpha$ have to be straight lines).

Looking at $S$ above, it's pretty clear that the only way that the path $\alpha$ can stay in $S$ is if it follows along the function $y=-x^3$ exactly. So let's define $\alpha:\mathbb{R}\to\mathbb{R}^2$ by $$ \alpha(\lambda)=\begin{pmatrix}\lambda\\-\lambda^3\end{pmatrix}. $$ It's clear that $\alpha(\lambda)\in{S}$ for all $\lambda\in\mathbb{R}$. Hence, we can take any $\delta>0$. It's also clear that $\alpha(0)=(0,0)$, as desired. All the we need to show now is that $$ \lim_{\lambda\to0^+}\frac{\alpha(\lambda)-\alpha(0)}{\lambda}=d(=(1,0),\text{ remember}). $$ Good news: $$ \lim_{\lambda\to0^+}\frac{\alpha(\lambda)-\alpha(0)}{\lambda} =\lim_{\lambda\to0^+}\frac{\alpha(\lambda)}{\lambda} =\lim_{\lambda\to0^+}\frac{1}{\lambda}\begin{pmatrix}\lambda\\-\lambda^3\end{pmatrix} =\lim_{\lambda\to0^+}\begin{pmatrix}1\\-\lambda^2\end{pmatrix}=\begin{pmatrix}1\\0\end{pmatrix}, $$ as desired.

For practice, you can try a similar proof to show that $(-1,0)$ is also in $A_0$.

The final answer is $$A_0=\{(\alpha,0)\ |\ \alpha\in\mathbb{R}\}.$$

$\endgroup$
  • $\begingroup$ I have a question, why $(-2,2)\in D_0$? I understand the analytic argument but in the region seems like the 'final' point is $(-1,1)$ $\endgroup$ – user441848 Jun 4 '18 at 21:32
  • $\begingroup$ I assume you mean $(-2,-2)$ and $(-1,-1)$? The point $(-2,-2)\in{D_0}$, but $(-2,-2)\not\in{S}$. In general, $D_0\not\subset{S}$. Remember that $D_0$ is the cone of the feasible solutions--it extends to infinity. This is done for analytical reasons to make some proofs easier. I will update my figures to make this clearer. $\endgroup$ – David M. Jun 4 '18 at 21:35
  • $\begingroup$ yeah I meant $(-2,-2)$ and $(-1,-1)$ $\endgroup$ – user441848 Jun 4 '18 at 21:41
  • $\begingroup$ I see, I got confussed a bit. $\endgroup$ – user441848 Jun 4 '18 at 21:45
  • 1
    $\begingroup$ See updated answer $\endgroup$ – David M. Jun 5 '18 at 3:31

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.