5
$\begingroup$

I am reading a book on linear optimization and I am stuck with the following problem:

Prove that every ray in $\mathbb{R}^n$ is a polyhedron.

The book defines a ray as follows:

For a point $x_0\in\mathbb{R}^n$ and a vector $d\in\mathbb{R}^n$, a ray is the set $$\{x_0+\lambda d \mid \forall \lambda \in \mathbb{R} \, \text{such that} \, \lambda \ge 0\}$$

It also defines a polyhedron as a set of solutions to a system of linear inequalities.

My idea is to find a linear transformation $A$, whose kernel is the subspace spanned by $d$. Consequently, the set of solutions to the equation $Ax=Ax_0$ will be a line containing the ray. But there is two problems. First I do not know how to find such a $A$. Second, I do not know what to do next.

Any help is appreciated.

$\endgroup$
6
  • 1
    $\begingroup$ Are you sure a polyhedron isn't defined as the solution set of a system of linear inequalities, rather than just one linear inequality? Because all you get from one inequality is half-spaces. $\endgroup$
    – coffeemath
    Nov 28 '21 at 20:36
  • $\begingroup$ @coffeemath Actually the book uses the vector inequality notation but I will edit my question. Thanks. $\endgroup$
    – Masoud
    Nov 28 '21 at 20:39
  • 1
    $\begingroup$ @coffeemath By vector notation, I mean $Ax\le b$ where $A$ is $n\times n$ matrix and $x$ and $b$ are both $n$-dimensional vectors. The inequality means that every component of $Ax$ is less than the corresponding component of $b$. So I believe that this is equivalent to a system of linear inequalities. It also is equivalent to the intersection of a finite number of half-spaces. Hence it determines a polyhedron in all three definitions. $\endgroup$
    – Masoud
    Nov 28 '21 at 20:52
  • $\begingroup$ I am pretty sure a set of linear inequalities can only give you convex polyhedra. $\endgroup$
    – Arthur
    Nov 28 '21 at 20:55
  • 1
    $\begingroup$ Ok, then that's fine. I'm just used to polyhedra not necessarily being convex as an implicit assumption. $\endgroup$
    – Arthur
    Nov 28 '21 at 21:03
4
$\begingroup$

Let the ray be $R= \{x_0+t d \}_{t \ge 0}$. Let $d_2,...,d_n$ be a basis for $\{ d \}^\bot$, then $R = \{ x | d_k^T(x-x_0) = 0, d^T(x-x_0) \ge 0\}$.

$\endgroup$

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.