Part 2 - Convexity I

A set $S \subseteq \mathbb{R}^n$ is called convex if,

Let $S_k \in \mathbb{R}^n$ for $k = 1, \ldots, K$ be convex.

Then, the intersection,

Let $\mathbf{x}_1, \mathbf{x}_2 \in S$ and $\lambda \in (0,1)$. Since $\mathbf{x}_1, \mathbf{x}_2 \in S$, we have that $\mathbf{x}_1, \mathbf{x}_2 \in S_k$ for all $k = 1, \ldots, K$. Each $S_k$ is convex, thus,

Hence, $\lambda \mathbf{x}_1 + (1 - \lambda) \mathbf{x}_2$ lies in all the $S_k$ simultaneously, i.e.,

Unions of convex sets might not be convex.

The convex hull of a finite set of points, $\{\mathbf{v}_1, \ldots, \mathbf{v}_k \} \subseteq \mathbb{R}^n$ is defined as,

The convex hull of the set $S \subseteq \mathbb{R}^n$, is the set with any of the following properties,

• (1) It is the unique minimal convex set containing $S$.
• (2) It is the intersection of all convex sets containing $S$.
• (3) It is the set of all convex combinations of points in $S$.

Let $\alpha \in \mathrm{conv}(S)$, where $S \subseteq \mathbb{R}^n$.

Then $\alpha$ can be expressed as a convex combination of at most $n+1$ points in $S$.

A set $P \subseteq \mathbb{R}^n$ is called a polytope if it is the convex hull of finitely many points.

A polytope will always have straight edges. So, a circle is not a polytope (since the circumference is curved and can not be expressed with finitely many points).

A point $\mathbf{v}$ of a convex set $S$ is called an extreme point if,

Let $P$ be the polytope $\mathrm{conv}(V)$, where $V = \{\mathbf{v}_1, \ldots, \mathbf{v}_k \}$. Then, $P$ is equal to the convex hull of its extreme points.

A set $P$ is called a polyhedron if there exists a matrix $A \in \mathbb{R}^{n \times m}$ and a vector $\mathbf{b} \in \mathbb{R}^n$ such that,

$A\mathbf{x} \leq \mathbf{b}$ means that,

where $\mathbf{a}_i^T$ is the $i$-th row of $A$ and $b_i$ is the $i$-th element of $\mathbf{b}$. Further, $\{\mathbf{x} \in \mathbb{R}^m \mid A\mathbf{x} \leq \mathbf{b} \}$ is a half-space. A polyhedron is the intersection of $n$ half-spaces $\implies$ a polyhedron is a convex set (by our previous proposition).

Let $A = \begin{bmatrix} 1 & 2 \newline -2 & 1 \newline 0 & -1 \end{bmatrix}$ and $\mathbf{b} = \begin{bmatrix} 6 \newline -2 \newline -1 \end{bmatrix}$. This gives the following system of inequalities,

Let $\mathbf{x}^{\prime} \in P \{\mathbf{x} \in \mathbb{R}^m \mid A\mathbf{x} \leq \mathbf{b} \}$, where $A \in \mathbb{R}^{n \times m}$, $\mathrm{rank}(A) = m$ and $\mathbf{b} \in \mathbb{R}^n$.

Further, let $A^{\prime} \mathbf{x}^{\prime} = \mathbf{b}^{\prime}$ be the equality subsystem of $A\mathbf{x} \leq \mathbf{b}$, i.e., $\mathbf{A}^{\prime}$ contains all rows of $A$ where we have $(A \mathbf{x}^{\prime})_i = b_i$.

Then, $\mathbf{x}^{\prime}$ is an extreme point of $P$ if and only if $\mathrm{rank}(A^{\prime}) = m$.

Let $\mathbf{x}^{\prime} = \begin{bmatrix} \frac{3}{2} \newline 1 \end{bmatrix}$. Then,

Which means,

We can see that $\mathrm{rank}(\mathbf{A}^{\prime}) = 2 = m$, thus $\mathbf{x}^{\prime}$ is an extreme point of $P$.

Now, consider a new point $\mathbf{x}^{\prime}_2 = \begin{bmatrix} 2 \newline 1 \end{bmatrix}$. Then,

Which means,

We can see that $\mathrm{rank}(\mathbf{A}^{\prime}_2) = 1 \neq m$, thus $\mathbf{x}^{\prime}_2$ is not an extreme point of $P$.

A set $C \subseteq \mathbb{R}^n$ is a cone if,

Let $A \subseteq \mathbb{R}^{n \times m}$ then, $C \coloneqq \{\mathbf{x} \in \mathbb{R}^m \mid A\mathbf{x} \leq 0 \}$ is a convex cone.

It is quite simple to prove this, assume that $\mathbf{x} \in C$ and $\lambda > 0$,

Let $Q = \{\mathbf{x} \in \mathbb{R}^m \mid A\mathbf{x} \leq \mathbf{b} \}$ (polyhedron) and let $\{\mathbf{v}_1, \ldots, \mathbf{v}_k \}$ be its extreme points. Further, we define $P \coloneqq \mathrm{conv}(\{\mathbf{v}_1, \ldots, \mathbf{v}_k \})$ (polytope) and $C \coloneqq \{\mathbf{x} \in \mathbb{R}^m \mid A\mathbf{x} \leq 0 \}$ (cone). Then,

A bounded polyhedron is a polytope.