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, 2018 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, 2018 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, 2018 at 4:33
  • $\begingroup$ @астонвіллаолофмэллбэрг oh $\endgroup$
    – user441848
    Feb 3, 2018 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, 2018 at 4:40

1 Answer 1

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, 2018 at 5:23
  • $\begingroup$ No. ${}{}{}{}{}{}$ $\endgroup$
    – copper.hat
    Feb 3, 2018 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, 2018 at 5:53
  • 1
    $\begingroup$ @Anneliset.: I added a small diagram that might help. $\endgroup$
    – copper.hat
    Feb 7, 2018 at 1:37
  • 1
    $\begingroup$ Alright, thank you so much 😌 $\endgroup$
    – user441848
    Feb 7, 2018 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.