Htykuut

My textbook gives the following definition of a polyhedron:

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, dots , m, c_j^T x = d_j, j = 1, dots , p }$$

A polyhedron is thus the intersection of a finite number of halfspaces and hyperplanes. Affine set (e.g., subspaces, hyperplanes, lines), rays, line segments, and halfspaces are all polyhedra. It is easily shown that polyhedra are convex set.

I was trying to find a proof of the fact that polyhedra are convex sets, and so I came across this:

Let $mathrm{mathbf{a}}$ be a vector and let $b$ a scalar. Suppose that $mathrm{mathbf{x}}$ and $mathrm{mathbf{y}}$ satisfy $mathrm{mathbf{a}}' mathrm{mathbf{x}} ge b$ and $mathrm{mathbf{a}}' mathrm{mathbf{y}} ge b$, respectively, and therefore belong to the same halfspace. Let $lambda in [0, 1]$. Then, $mathrm{mathbf{a}}'(lambda mathrm{mathbf{x}} + (1 - lambda)mathrm{mathbf{y}}) ge lambda b+ (1 - lambda)b = b$, which proves that $lambda mathrm{mathbf{x}} +(1 - lambda) mathrm{mathbf{y}}$ also belongs to the same halfspace. Therefore a halfspace is convex. Since a polyhedron is the intersection of a finite number of halfspaces, the result follows from part (a).

The author provides a proof of this fact in his own question. However, after trying to understand this proof, a number of questions arose:

1. The proof starts by supposing that $mathrm{mathbf{a}}' mathrm{mathbf{x}} ge b$ and $mathrm{mathbf{a}}' mathrm{mathbf{y}} ge b$. But, in the above definition of a polyhedron, it is said that $mathcal{P} = { x mid a^T_j x le b_j, j = 1, dots , m, c_j^T x = d_j, j = 1, dots , p }$; in other words, we have that $a^T_j x le b_j, j = 1, dots , m$, instead of $a^T_j x ge b_j$, which it seems is what the proof has?




2. The above definition also has the set condition $c_j^T x = d_j, j = 1, dots , p$. Is this equivalent to $mathrm{mathbf{a}}'(lambda mathrm{mathbf{x}} + (1 - lambda)mathrm{mathbf{y}}) ge lambda b+ (1 - lambda)b = b$ in the proof?




3. The proof says that "Since a polyhedron is the intersection of a finite number of halfspaces, ...". What about the hyperplanes? I see no mention of them in the proof.

I would greatly appreciate it if people could please take the time to clarify these.

On question 1: It is frequently the case that the same definition can be expressed in multiple ways. In this case, you can define a polyhedron as

$$mathcal{P} = { x mid a^T_j x le b_j, j = 1, dots , m, c_j^T x = d_j, j = 1, dots , p }$$

Or you can define it as

$$mathcal{P} = { x mid a^T_j x ge b_j, j = 1, dots , m, c_j^T x = d_j, j = 1, dots , p }$$

Notice that , if you plug the same $a$ and $b$ in these two definitions, you will get different polyhedra. But that is because $a$ and $b$ themselves mean slightly different things in both definitions. In particular, whenever the author of the first definition would use $a$, the author of the second would use $-a$.

For example, consider a 2D space, $mathbb{R}^2$, and let's focus on the polyhedron that is to the right on the line $x=1$.

One author can denote this polyhedron as ${(x, y)|xge 1}$. Another author may write ${(x, y)|-xle -1}$. Regardless of which notation you choose, you're denoting the same polyhedron.

On questions 2 and 3: Hyperplanes make things easier sometimes, but you can define a polyhedron simply as the intersection of half-spaces. You can simply replace each hyperplane of the kind $cx=d$ with two half-spaces, $cx geq d$ and $cx leq d$. Therefore, anything that works for intersection of half-spaces also works for intersection of half-spaces and hyperplanes.

In answer to question 1, if you negate $a$ and $b$, you obtain $-a^Txle -b$.

For questions 2 and 3, a hyperplane is the intersection of the closed halfspaces it bounds.

(1) you do not need to be worry about that. Since both $a_i$ and $b_i$ are arbitrary, then you can define the equivalent form $-a^T_jxge -b_j$ to the standard form $a_j^Txle b_j$ and define some $a'$ and $b'$ for which $a'_j=-a_j$ and $b'_j=-b_j$ such that$$a'^T_jxge b'_j$$ (2) as any equality $p=q$ can be expressed by two simultaneous inequalities $ple q$ and $pge q$ or $ple q $ and $-ple -q$ therefore any $c^T_jx=d_j$ can be expressed similarly with $-c^T_jxle -d_j$ and $c^T_jxle d_j$ and treated to just like the other inequalities of the standard form $a_j^Txle b_j$. More generally, you can define a polyhedron as follows:$$mathcal{P} = { x mid a^T_j x le b_j, j = 1, dots , m}$$because a set of inequalities is a generalized form of set of equalities as shown just before.

(3) we have already answered this part in (2), but we mention it once more here for sake of completeness. Any equation of the form $$c^Tx=d$$ (which is also referred to as hyper-plane) is equivalent to two half-spaces as follows $$c^Txle d\-c^Txle -d$$which yields to an important result: any hyper-plane is equivalent to exactly two half-spaces

P.S. it is highly recommended to check out the below resource on convex sets

http://web.stanford.edu/~boyd/cvxbook/

which contains definitions and very nice approaches to convex sets and I think they meet your needs.