2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\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$ Commented Apr 6, 2020 at 14:14
  • 2
    $\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$ Commented Apr 6, 2020 at 15:21

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

For the first question, a polyhedron is the intersection of a finite number of half-spaces and hyper-planes. Only hyperplanes can't create a polyhedron. In that case, $C_{j}^{T} x=d_{j}$ is not enough to create the polyhedron.

Polyhedron can be unbounded.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.