1

Suppose $M=\{x \in \mathbb{R}^n: Ax \ge b\}$ is nonempty and $x_0 \in M$.

Prove that $M$ is unbounded, then there exists a vector $d \in \mathbb{R}^n$, such that $x_0+\lambda d \in M,\forall \lambda \ge 0$.

I can prove it with duality theorem, but I think there is a simple proof.

Thank a lot.

T. Huynh
  • 111

1 Answers1

0

So you need to show the existence of $d$, such that $x_0+\lambda d \in M$. In other words, you need to find $d$ such that $$ A(x_0+\lambda d)\ge b $$ But since $$A(x_0+\lambda d)= Ax_0+\lambda A d$$ and that $$ Ax_0\ge b\quad \mbox{ (as $x_0\in M$) } $$ You only need to find $d\in \mathbb{R}^n$ such that $$ \lambda A d\ge b\quad \forall \lambda \ge 0 $$ $d:=x_0$ is an obvious candidate, and we are done.

Kuifje
  • 9,584
  • Doesn't it suffice to find a $d$ such that $\lambda A d\geq 0$ for all $\lambda\geq 0$ as $Ax_0\geq b$ already? – Elias Nov 26 '16 at 10:45