2
$\begingroup$

My textbook, Convex Optimization by Boyd and Vandenberghe, says the following in a section on Polyhedra:

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

$$\mathcal{P} = \{ x \mid a^T_j x \le b_j, j = 1, ..., m, c^T_j x = d_j, j = 1, ..., p \}. \tag{2.5}$$

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. It is easily shown that polyhedra are convex sets. A bounded polyhedron is sometimes called a polytope, but some authors use the opposite convention (i.e., polytope for any set of the form (2.5), and polyhedron when it is bounded). Figure 2.11 shows an example of a polyhedron defined as the intersection of five halfspaces.

enter image description here

It seems to me that, by saying the following, the authors are implying that (2.5) is not bounded:

... but some authors use the opposite convention (i.e., polytope for any set of the form (2.5), and polyhedron when it is bounded).

But, given the presence of the inequalities and equalities, it seems to me that (2.5) is bounded, no? And doesn't figure 2.11 also suggest that it is bounded?

I would appreciate it if people would please take the time to clarify this.

$\endgroup$
4
  • 1
    $\begingroup$ Some intersections of finitely many closed half spaces are bounded and some are not. All are convex. The usual convention is to call the bounded ones "polytopes". $\endgroup$ Commented Jan 25, 2020 at 12:39
  • $\begingroup$ @kimchilover I see. And what you're describing is also the definition of "polytope" used by the authors, yes? $\endgroup$ Commented Jan 25, 2020 at 12:42
  • 1
    $\begingroup$ Yes, your authors use "polytope" to mean bounded polyhedron. They might have been clearer if they also showed an unbounded polyhedron picture, such as the 1st quadrant in the plane, or the $x$ axis in the plane, cut out by recipes of type (2.5) but obviously unbounded. $\endgroup$ Commented Jan 25, 2020 at 12:47
  • $\begingroup$ @kimchilover Yes, that would have been clarifying. Anyway, thank you for taking the time to clarify this. $\endgroup$ Commented Jan 25, 2020 at 12:48

1 Answer 1

1
$\begingroup$

The terms "polyhedron" and "polytope" are used in different ways by different mathematical sub-disciplines. A result obtained under one definition will not necessarily apply to other sub-disciplines. For example Grünbaum's classic Convex Polytopes gives three explicit and incompatible definitions of a polyhedron.

Whether the polygon you describe is bounded or open (unbounded) depends on whether the half-spaces include the boundary with the other half-space. If they do, then they have to deal with the fact that the boundaries are entire sub-spaces.

Be aware also that most formalisms taught in college assume, even demand, that a polyhedron or polytope be convex. Although you will sometimes find it stated that these ideas are readily generalized to non-convex cases such as star polytopes, this is a mere sentiment with no rational foundation.

$\endgroup$
1
  • $\begingroup$ Thanks for the contribution. $\endgroup$ Commented May 17, 2020 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .