This blog is talking about polyhedra and convex set. We will study the feasible set from geometric way. And utilize this properties to get algebra method to solve LO problem.

Polyhedra and Convex Set

Polyhedra

Definition: A polyhedron is a subset of ${ \mathbb{R}^n }$ of the form ${ \{\bar{x} \in \mathbb{R}^n | A \bar{x} \geq \bar{b} \} }$

Where ${ A }$ is a ${ m \times n }$ matrix and ${ \bar{b} }$ is a vector in ${ \mathbb{R}^m }$

Definition: A subset of ${ \mathbb{R}^n }$ of the form ${ \{\bar{x}\in \mathbb{R}^n | A\bar{x} = \bar{b}, \bar{x} \geq \bar{0}\} }$ is called a polyhedron in standard form representation.

Note: A polyhedron can either “extend to infinity” or be confined in a finite region!

Definition: A subset ${ S }$ is bounded if ${ \exists K >0 }$ such that the absolute value of every component of every element of ${ S }$ is less than or equal to ${ K }$.

In other word, A subset ${ S }$ is bounded if ${ \exists K >0 }$ such that

$$ \begin{equation} S \subset \left\{ \left[\begin{matrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{matrix}\right] \in \mathbb{R}^n \middle| \begin{aligned} \vert x_1 \vert &\leq K \\ \vert x_2 \vert &\leq K \\ & \vdots \\ \vert x_n \vert &\leq K \end{aligned} \right\} \end{equation} $$

Affine subspace and level set in high dimension

Let’s generalize the level set from ${ 2 }$ to ${ n }$ dimension sapce.

Let’s ${ \bar{a} }$ be a non-zero vector in ${ \mathbb{R}^n }$. The set ${ {\bar{x}\in \mathbb{R} | \bar{a}^\top =0 } }$ is the set of all vectors ${ \bar{x} }$ in ${ \mathbb{R}^n }$ that are orthogonal to the nonzero vector ${ \bar{a}^\top }$. It’s an ${ (n-1) }$-dimensional linear subspace of ${ \mathbb{R}^n }$.

More generally, the set ${ \{\bar{x}\in \mathbb{R}^n | \bar{a}^\top \bar{x} = b\} }$ is the set of all points ${ \bar{x} }$ in ${ \mathbb{R}^n}$ statisfying ${ \bar{a}^\top \bar{x} = b }$, we have

$$ \begin{equation} \begin{aligned} \Vert \bar{a} \Vert \cdot \Vert \bar{x} \Vert \cdot \cos \theta &= b \\ \Vert \bar{x} \Vert \cdot \cos \theta &= \frac{b}{\Vert \bar{a} \Vert} \end{aligned} \end{equation} $$

Here, ${ \theta }$ is the angle between ${ \bar{a}}$ and ${ \bar{x} }$.

It is the ${ (n-1) }$-dimension affine subspace of ${ \mathbb{R}^n }$ comprised of all points ${ \bar{x} \in \mathbb{R}^n }$ whose orthogonal projection on the line spaned by the nonzero vector ${ \bar{a} }$ is located at (signed) distance ${ \frac{b}{\Vert \bar{a} \Vert} }$ from the origin in the direction of the vector ${ \bar{a} }$.

In other word, ${ \{\bar{x}\in \mathbb{R}^n | \bar{a}^\top \bar{x} = b\} }$ is the hyperplane orthogonal to the line ${ span{\bar{a}} }$ and intersecting that line at the point ${ \frac{b}{\Vert \bar{a} \Vert} \cdot \frac{\bar{a}}{\Vert \bar{a} \Vert} }$ (${ \frac{b}{\Vert \bar{a} \Vert} }$ is rescaling factor, ${ \frac{\bar{a}}{\Vert \bar{a} \Vert} }$ is the unit vector represent direction)

The set ${ \{\bar{x}\in \mathbb{R}^n | \bar{a}^\top \bar{x} \geq b\} }$ is the hyperspace of ${ \mathbb{R}^n }$ whose boundary is the hyperplane ${ \{\bar{x} \in \mathbb{R}^n | \bar{a}^\top \bar{x} = b\} }$

Note: a polyhedron ${ \{\bar{x}\in \mathbb{R}^n | A \bar{x} \geq \bar{b}\} }$ is the intersection of a finite number of halfspaces.

Convex set

Definition: A subset ${ S }$ of ${ \mathbb{R}^n }$ is said to be convex if the segment of line joining any two elements ${ \bar{p} }$ and ${\bar{q} }$ of ${ S }$ is fully contained in the set ${ S }$.

We can rephase the definition as follow

Definition: A subset ${ S \subset \mathbb{R}^n }$ is said to be convex if ${ \forall \bar{p},\bar{q} \in S }$ and ${ \forall \lambda \in [0,1] }$, we have ${ (1-\lambda)\bar{p} + \lambda \bar{q} \in S}$.

Convex Combination and Convex hull

Definition: Let ${ \bar{p_1}, \bar{p_2} ,\cdots, \bar{p_k}}$ be ${ k }$ vectors in ${ \mathbb{R}^n }$

• We say that a vector ${ \bar{v} \in \mathbb{R}^n }$ is a convex combination of the vectors ${ \bar{p_1}, \bar{p_2} ,\cdots, \bar{p_k}}$ if ${ \bar{v} }$ can be written as ${ \bar{v} = \sum_{i=1}^k \lambda_i \bar{p_i} }$, where ${ \lambda_1,\lambda_2, \cdots, \lambda_k }$ are ${ k }$ nonnegative scalars such that ${ \lambda_1 + \lambda_2 + \cdots+ \lambda_k =1 }$

• Convex hull of the vectors ${ \bar{p_1}, \bar{p_2} ,\cdots, \bar{p_k}}$ is the set of all convex combination of these ${ k}$ vectors.

* What the convex hull look like?

For two points ${ \bar{p_1}, \bar{p_2}}$, it’s the set ${ {(1-\lambda)\bar{p_1}+ \lambda \bar{p_2} \in \mathbb{R}^n | \forall \lambda \in [0,1]} }$. It’s easy to get the convex hull the segment of line joining two points.

How about three points?

Pick up one vector from convex hull of ${ \bar{p_1}, \bar{p_2}, \bar{p_3} }$ We have ${\bar{v} = \lambda_1 \bar{p_1} +\lambda_2 \bar,{p_2} +\lambda_2 \bar{p_2} }$, and ${ \lambda_1 + \lambda_2 + \lambda_3 =1 , \lambda_1,\lambda_2, \lambda_3 \geq 0}$, that is

$$ \begin{equation} \begin{aligned} \bar{v} &= \lambda_1 \bar{p_1} +\lambda_2 \bar,{p_2} +\lambda_2 \bar{p_2} \\ & = (1-\lambda_3) \left(\frac{\lambda_1}{1-\lambda_3} \bar{p_1} + \frac{\lambda_2}{1-\lambda_3} \bar{p_2} \right) + \lambda_3 \bar{p_3} \\ & = = (1-\lambda_3) \left(\frac{\lambda_1}{\lambda_1 + \lambda_2} \bar{p_1} + \frac{\lambda_2}{\lambda_1 + \lambda_2} \bar{p_2} \right) + \lambda_3 \bar{p_3} \end{aligned} \end{equation} $$

That means, first we have the segment of line joining two points ${ \bar{p_1}, \bar{p_2}}$ (convex hull of ${ \bar{p_1}, \bar{p_2}}$), and pick up each point ${ \bar{q} }$ from this segment to generate the new segment joining two points ${ \bar{q} \bar{p_3}}$. Then we can have a triangle with points ${ \bar{p_1}, \bar{p_2}, \bar{p_3} }$ as corner.

If we have more dimension, we can generate from segment to triangle to pyramid (base as triangle).

Theorems

(a) The intersection of convex sets is also convex set.

Proof. Suppose $S_1,S_2$ are convex sets. Then, $\forall \bar{x},\bar{y} \in S_1 \cap S_2$ and $\forall \lambda \in [0,1]$, we have $(1-\lambda)\bar{x} + \lambda \bar{y} \in S_1$ and $(1-\lambda)\bar{x} + \lambda \bar{y} \in S_2$. Hence, $(1-\lambda)\bar{x} + \lambda \bar{y} \in S_1 \cap S_2$. So $S_1\cap S_2$ is also a convex set. $\square$

(b) Every polyhedron is a convex set.

Proof. Suppose polyhedron $P = {\bar{x} \in \mathbb{R} \mid A\bar{x} \geq \bar{b}}$. $\forall \bar{p},\bar{q} \in P$, we have $A\bar{p} \geq \bar{b}, A\bar{q} \geq \bar{b}$. Then $\forall \lambda \in [0,1]$, we have $A((1-\lambda)\bar{p} + \lambda \bar{q}) = (1-\lambda)A\bar{p} + \lambda A \bar{q} \geq (1-\lambda)\bar{b} + \lambda \bar{b} = \bar{b} $. $\square$

(c) A convex combination of a finite number of elements of a convex set also belongs to that set. Proof. Suppose $S$ is a convex set and $\bar{p}1,\bar{p}_2,\cdots,\bar{p}_n \in S$, and $\lambda_1,\cdots,\lambda_n \geq 0$ such that $\lambda_1 + \cdots + \lambda_n = 1$. We will show $\bar{v} = \sum{i =1}^n \lambda_i \bar{p}_i \in S$ by induction.

Base case: $n = 1$, $\lambda_1 = 1$. It’s trivial to get $\bar{p}_1 \in S$.

Induction Hypothesis $\sum_{i =1}^{n-1} \lambda_i \bar{p}_i \in S$.

Then, we have $\sum_{i =1}^{n} \lambda_i \bar{p}i = \lambda_n \bar{p}_n + (1-\lambda_n) \sum{i=1}^{n-1} \frac{\lambda_i}{1-\lambda_n} \bar{p}i $. We know $\lambda_1 + \cdots + \lambda_n = 1$ that means $\sum{i=1}^{n-1} \frac{\lambda_i}{1-\lambda_n} = 1$. By induction hypothesis, $\bar{x} = \sum_{i=1}^{n-1} \frac{\lambda_i}{1-\lambda_n} \bar{p}i \in S$. Then, we know $\sum{i =1}^{n} \lambda_i \bar{p}_i =\lambda_n \bar{p}_n + (1-\lambda_n) \bar{x} \in S $. $\square$

(d) The convex hull of a finite number of vectors is a convex set.

Proof. Denote the convex hull $H$ is generated by vector $\bar{p}_1,\bar{p}_2,\cdots,\bar{p}_n$. $\forall \bar{x},\bar{y} \in H$, there exists a set of nonnegative coefficients for each one, such that $\sum \alpha_i = \sum \beta_i =1$ and $\bar{x} = \sum \alpha_i \bar{p}_i, \bar{y} = \sum \beta_i \bar{p}_i$. Then, $\forall \lambda \in [0,1]$, we have

\[\begin{aligned} (1-\lambda) \bar{x} + \lambda \bar{y} &= \sum ((1-\lambda)\alpha_i + \lambda \beta_i) \bar{p}_i \end{aligned}\]

And, we know $\sum (1-\lambda)\alpha_i + \lambda \beta_i = (1-\lambda) \sum \alpha_i + \lambda \sum \beta_i = 1$. So $(1-\lambda) \bar{x} + \lambda \bar{y} \in H$. That means $H$ is a convex set. $\square$