Explain `All polyhedrons are convex sets´

Question

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is polyhedron'. You can see below the screenshot of the solution.

Wikipedia shows nonconvex polyhedrons such as orthogonal polyhedron here.

What should I now believe? Is polyhedron convex or not?

Definitions on the lecture slides (p.8, L4)

Polyhedron is such that $$P=\{\bar x\in \mathbb R^n | A \bar x\geq \bar b\}, A\in \mathbb R^{m\times n},\bar b\in \mathbb R^m$$ and a convex function $f(x)$ must satisfy $$f(\lambda \bar x+(1-\lambda)\bar y)\leq \lambda f(\bar x)+(1-\lambda) f(\bar y) \text{, } \forall \bar x, \bar y, \lambda \in [0,1]$$ and a convex set $C$ is such that $$\bar x, \bar y \in C\rightarrow \lambda \bar x+(1-\lambda)\bar y\in C.$$

Answer 1

It can be proved by following three steps.

(a) Let $\left\{{\Omega_{\alpha}}\right\} (\alpha \in I)$ be a collection of convex subsets of $\mathbb{R}^n$. Then $\bigcap_{\alpha \in I}\Omega_{\alpha}$ is also a convex.

proof: Taking any $x_1,x_2\in \bigcap_{\alpha\in I}\Omega_{\alpha}$. We get that $x_1,x_2\in \Omega_{\alpha}$ for $\alpha\in I$. And then we have $\theta x_1+(1-\theta)x_2\in \Omega_{\alpha}$ for any $\theta\in [0,1]$ since $\Omega_{\alpha}$ are convex sets. Thus $\theta x_1+(1-\theta)x_2\in \bigcap_{\alpha\in I}{\Omega_{\alpha}}$.

(b) Hyperplanes are convex and halfsapces are also convex. \begin{equation} \text{Hyperplanes}: \left\{{x|a^Tx=b}\right\} \quad \text{Halfspaces}: \left\{{x|a^Tx\leq b}\right\} \end{equation} proof: Assume that $x_1,x_2\in \Omega$, and we have $a^Tx_1=b, a^Tx_2=b$. Hence we can get
\begin{equation} a^T(\theta x_1+(1-\theta)x_2)=\theta a^T x_1+(1-\theta)a^Tx_2=b \end{equation} i.e., $(\theta x_1+(1-\theta)x_2)\in \Omega$. similarly, we also can prove that halfspaces are convex.

(c) As we observed from the definition of polyhedra. A polyhedron is defined as the solution set of a finite number of linear equalities and inequalities. It mean that a ployhedron is the intersection of a finite number of halfspaces and hyperplanes. Based on (b), we know that halfspaces and hyperplanes are convex. Furthermore, we know polyhedron is convex based on (a).

Answer 2

I suspect you are confused with the definition. Usually a a polyhedron is defined by specifying a finite subset of $n-1$ dimensional affine subspaces in $\mathbb{R}^{n}$. In this way what you get is always convex. This is the definition people use when work on combinatorical topology or algebraic combinatorics. You should confirm this with your teacher though.

Answer 3

Look at Boyd's book Section 2.2.4 http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

Answer 4

A polyhedron can be defined as a finite intersection of halfspaces and hyperplanes. Halfspaces and hyperplanes are convex sets, the intersection of convex sets is a convex set, and thus all polyhedrons are convex.