# Explain `All polyhedrons are convex sets´

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.$$

• Just so you know, your first link is only available to Aalto students. As to your question - does the course contain a definition of polyhedron? It may simply be a question of two different definitions, one allowing non-convex things and the other not. – mdp Jan 11 '13 at 10:46
• @MattPressland shared relevant information in the q. – hhh Mar 4 '13 at 14:34
• In convex optimization, the word "polyhedron" is sometimes used in a way that is inconsistent with the way the word is defined in basic geometry. – littleO Jun 21 '16 at 9:52

## 4 Answers

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. $$$$\text{Hyperplanes}: \left\{{x|a^Tx=b}\right\} \quad \text{Halfspaces}: \left\{{x|a^Tx\leq b}\right\}$$$$ proof: Assume that $$x_1,x_2\in \Omega$$, and we have $$a^Tx_1=b, a^Tx_2=b$$. Hence we can get
$$$$a^T(\theta x_1+(1-\theta)x_2)=\theta a^T x_1+(1-\theta)a^Tx_2=b$$$$ 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).

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.

• Is this "[u]sually a polyhedron is defined by specifying a finite subset of $n-1$ dimensional affine subspaces in $\mathbb R^n$" the method Ross uses here? – hhh Feb 26 '13 at 22:45
• Is there anything like concave polyhedrons? What is the name for concave things such as ball-with-hole, cube-with holes and tetrahedron with a dent if not polyhedrons? Torus, n-torus but the other things? Some general name? – hhh Mar 4 '13 at 14:35
• @hhh: I do not know what you are really talking about. – Bombyx mori Mar 4 '13 at 18:49
• @hhh: They are called non-convex polyhedra, if they have faces that are polygons (bounded by straight line segments.) The faces of non-convex polyhedra can either be convex polygons, star-polygons (like the pentagram), or skew polygons (which don't lie in a plane.) "Star-polyhedra" are a particular type of non-convex polyhedra. Things like balls and tori are not polyhedra. Those are called surfaces of nonzero genus. (The genus is the number of holes.) – Nick Matteo Apr 9 '14 at 2:27

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

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.