A polyhedron is defined as the solution set of a finite number of linear equalities and inequalities:

$$P = \{x | a^T_j x ≤ b_j , j = 1, . . . , m, c^T_j x = d_j , j = 1, . . . , p\}$$ A polyhedron is thus the intersection of a finite number of halfspaces and hyper- planes. Affine sets (e.g., subspaces, hyperplanes, lines), rays, line segments, and halfspaces are all polyhedra.

I understand the use of inequalities in the equation. It is used to select the halfspaces included by the polyhedron and thus form a closed structure. But I don't understand:

  • What is the role of the equalities $c^T_j x = d_j , j = 1, . . . , p$

  • And my second question is how is the 'intersection of a finite number of halfspaces and hyper-planes' a polyhedron? i.e for example if we take 2 halfspaces $a^T_1 x ≤ b_1$ and $a^T_2 x \geq b_2$ it will form an unending triangle (informally speaking) covering a sector of the plane. How is this a polyhedron?

NOTE: I am not a mathematician, so use of intuitive terms rather than technical will be more helpful to me.

  • 1
    $\begingroup$ Rapidly, for your second question, the polyhedron can be infinite from the definition. It might be surprising at first glance but from a mathematical point of view it is not a problem. $\endgroup$ Apr 6 '20 at 14:14
  • 1
    $\begingroup$ The role of the inequalities is to allow polyhedra to have lower dimension than the whole space. For example, a triangle in the plane $\mathbb R^2$ is also a polyhedron in $\mathbb R^3$, and its most natural definition would include the equation $x_3=0$. Of course, any equation $ax=b$ could be replaced by a pair of inequalities $ax\leq b$ and $-ax\leq-b$, so equations aren't absolutely necessary, but it seems more natural to allow them. $\endgroup$ Apr 6 '20 at 15:21

For your first question, each equality $c_j^T x = d_j$ means that the polyhedron will live inside a particular hyperplane. Intuitively, intersections of multiple hyperplanes can be seen as reducing the dimension of your polyhedron. For instance if $P \subseteq \mathbb{R}^2$ is a $2$-dimensional polyhedron living in the $xy$-plane and we intesect this with the hyperplane $x = 0$ then we are looking at the intersection of $P$ with the $x$-axis. This could be empty, a point or an interval.

For your second question, your example is certainly a polyhedron however not a bounded one. Intuitively the definition of polyhedron is describing which solid objects have 'flat' bounding faces. Usually the important things for a polyhedron are knowing which points lie inside and what its faces look like. Generally it is not a problem if the polyhedron is not bounded.


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.