0
$\begingroup$

This exercise is from Bazaraa Linear programming book.

And I don't see the point of the exercise since the definition of direction is already given by hypothesis.

Am I missing something or the exercise it's not well stated?

Let $S$ be a closed convex set in $\mathbb R^n$ and let $x\in S$ . Suppose that $d$ is a nonzero vector in $\mathbb R^n$ and that $x +\lambda d\in S$ for all $\lambda\ge 0$. Show that $d$ is a direction of $S.$

$\endgroup$
6
  • $\begingroup$ What is the definition of a vector being a "direction of a set" that is given to you? $\endgroup$ Feb 3 '18 at 4:29
  • $\begingroup$ @астонвіллаолофмэллбэрг $d\in\mathbb R^n$ nonzero is a direction of $S$ if for all $x\in S$, $x+ld\in S$ for all $l\ge 0$ $\endgroup$
    – user441848
    Feb 3 '18 at 4:30
  • 1
    $\begingroup$ In the question you have, $x$ is one point of $S$. The definition demands that $x + \lambda d \in S$ for all $x \in S$, so you have to use the fact that this holds true for one point, and that $S$ is closed convex, to show that it holds true for all $x \in S$. $\endgroup$ Feb 3 '18 at 4:33
  • $\begingroup$ @астонвіллаолофмэллбэрг oh $\endgroup$
    – user441848
    Feb 3 '18 at 4:39
  • $\begingroup$ @астонвіллаолофмэллбэрг I understand now. What can I do now? Do you think that by contradiction it's a good idea? $\endgroup$
    – user441848
    Feb 3 '18 at 4:40
1
$\begingroup$

You need to show that if $y \in S$ then $y+\lambda d \in S$ for all $\lambda >0$.

Note that for $t \in [0,1]$ we have $(1-t) y + t(x+\lambda d) \in S$.

Pick $\mu >0$, and let $t_n = {1 \over n} \mu$ and let $\lambda = n$ in the above equation (pick $n$ large enough so that $t_n \in (0,1]$).

This gives $(1-t_n) y + t_n x + \mu d \in S$ for all $n$.

Let $n \to \infty$ and use the fact that $S$ is closed to get the desired result.

Excuse the crude diagram:

enter image description here

To illustrate why closure is specified, consider the set $S=\mathbb{R} \times (0,\infty) \cup (0,0)$. Then with $d=(1,0)$ we see that if $x \in \mathbb{R} \times (0,\infty) $ then $x+ \lambda d \in S$ for all $\lambda$ but $(0,0)+ \lambda d \notin S$ for any $\lambda \neq 0$.

$\endgroup$
20
  • $\begingroup$ Yes that's exactly what I need to prove, I wonder if a proof by contradiction is a good idea? $\endgroup$
    – user441848
    Feb 3 '18 at 5:23
  • $\begingroup$ No. ${}{}{}{}{}{}$ $\endgroup$
    – copper.hat
    Feb 3 '18 at 5:23
  • 1
    $\begingroup$ You really should try to draw a picture to see where the point $(1-t_n) y + t_n x + \mu d \in S$ lies in the context of $y,x,d$. Think of a triangle formed by the points $y,x,x+\lambda d$ and let $\lambda$ get larger and larger. Then the triangle gets more and more like an infinite rectangle formed by the points $x,x+\lambda d, y, y+ \lambda d$. Then closure gives us the desired result. $\endgroup$
    – copper.hat
    Feb 3 '18 at 5:53
  • 1
    $\begingroup$ @Anneliset.: I added a small diagram that might help. $\endgroup$
    – copper.hat
    Feb 7 '18 at 1:37
  • 1
    $\begingroup$ Alright, thank you so much 😌 $\endgroup$
    – user441848
    Feb 7 '18 at 2:06

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.