Polyhedra, Polyhedron, Polytopes and Polygon

Question

About Polyhedra, Polyhedron, Polytopes and Polygon, what do they mean in the context of linear programming and what is the difference between them?

Answer 1

The following definitions are taken from this lecture.

• Polyhedron

A polyhedron in $\Bbb R^n$ is the intersection of finitely many sets of all points $x$, such that $ax\le b$ for some $a\in\Bbb R^n$ and $b\in\Bbb R$.

• Polyhedra

Polyhedra is the plural of polyhedron.

• Polytope

A polytope is a bounded polyhedron, equivalent to the convex hull of a finite set of points which can be shown using Fourier-Motzkin elimination.

• Polygon

A polygon is a two-dimensional polytope, which can be used when describing the set of feasible solutions.

Answer 2

These are all names used for the feasible set of a linear programming problem. In other words, all the combination of values for the decision variables that correspond to a solution, hence satisfying all of the constraints.

In linear programming, you have continuous variables and linear constraints, which can be equalities or inequalities. For example, let us suppose that we have two decision variables, $x$ and $y$. An equality like $x + y = 5$ defines a line and implies that the all feasible solutions should be in this line, like $x=0$ and $y=5$ or $x=4.5$ and $y=0.5$. We may also have inequalities, such as $x \geq 0$ and $y \geq 0$, which on top of the equality $x + y = 5$ would imply that the feasible set is restricted to $x$ between 0 and 5 and $y = 5- x$. Hence, now we have a segment as our feasible set.

Geometrically, the feasible set is a polytope if it is bounded on every direction, such as the segment that we mentioned before. If the feasible set is not bounded, such as when we have only the equality $x+y=5$ and therefore we can pick an arbitrarily large positive value for $x$ and a corresponding negative value for $y$, then the feasible set is a polyhedron but not a polytope.

Polyhedra is the plural of polyhedron. A polygon is a polytope with only two dimensions.