1
$\begingroup$

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?)


Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces. ($\mathbb{K}$ is a field, $\mathbb{K}^n$ seems to be a vector space.)


Please note that the lecture notes define that a polyhedron is a set which may be represented using the form $$P = \{x \in \mathbb{K}^n \mid Ax \le b\}$$ where $A$ is a matrix and $b$ is a vector.

Hint: Prior to the mentioned proposition, the lecture notes state: If (i) a row of $A$ equals the zero vector and (ii) the corresponding component of $b$ is non-negative, then the row may be omitted; the omission does not affect $P$. I totally get this statement. However, if I am supposed to use it, I cannot see how.

$\endgroup$
  • $\begingroup$ How is the relation $\leq$ defined? $\endgroup$ – Mikhail Katz Aug 20 '14 at 10:27
  • $\begingroup$ @user72694 We were able to solve it! Anyway: We found out that we were supposed to use $\mathbb{K} \in \{\mathbb{Q}, \mathbb{R}\}$ and the canonical ordering. $\endgroup$ – DracoMalfoy Aug 20 '14 at 16:22
  • $\begingroup$ @dracomalfoy: It would be nice if you could edit your questiuon to include this $\mathbb K\in\{\mathbb Q,\mathbb R\}$ and then post an answer to your own question, including the solution you found. That way the question can help others. $\endgroup$ – MvG Aug 21 '14 at 10:38
0
$\begingroup$

I think that the half-space are defined from the inequalities in the $Ax \leq b$ system. So we have to suppose that there are finitely many of those.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.