5
$\begingroup$

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.

enter image description here

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – mdp Jan 11 '13 at 10:46
  • $\begingroup$ @MattPressland shared relevant information in the q. $\endgroup$ – hhh Mar 4 '13 at 14:34
  • 2
    $\begingroup$ 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. $\endgroup$ – littleO Jun 21 '16 at 9:52
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – hhh Feb 26 '13 at 22:45
  • $\begingroup$ 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? $\endgroup$ – hhh Mar 4 '13 at 14:35
  • $\begingroup$ @hhh: I do not know what you are really talking about. $\endgroup$ – Bombyx mori Mar 4 '13 at 18:49
  • 1
    $\begingroup$ @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.) $\endgroup$ – Nick Matteo Apr 9 '14 at 2:27
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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