Convex Sets

A set $C \sube \R^n$ is convex if it contains the line segment between any two of its elements.

$$ \forall x, y\in C, \forall \lambda \in [0,1], \lambda x + (1-\lambda)y \in C $$

A point $y \in C$ in a convex set $C$ is said to be an extreme point if it cannot be written as a convex combination of any two elements in $C$; i.e. it does not lie on any line segment in $C$.

Intersection of Convex Sets is Convex. Given a collection of convex sets $C_1, \dots, C_m$, their intersection $\cap_{i=1}^m C_i$ is convex.

</aside>

Halfplanes are Convex. Any halfplane is convex. Moreover, the intersection of halfplanes is known as a polyhedron.

</aside>

Supporting Hyperplanes

A supporting hyperplane $H$ for a convex set $C$ on a point $z \in \partial C$ is a hyperplane which satisfies:

$$ z \in H \text{ and } C\sube H_{-}:= \{x \in \R^n \mid a^Tx \leq b\} $$

Supporting Hyperplanes Always Exist. Given a convex set $C$ and a point $z \in \partial C$, there exists a, not necessarily unique, supporting hyperplane for $C$ on $z$.

</aside>

Separating Hyperplanes

A separating hyperplane $H$ ****for convex sets $C_1$ and $C_2$ is a hyperplane which satisfies:

$$ C_1 \sube H_+ \text{ and } C_2 \sube H_- $$

Moreover, we say $H$ strictly separates $C_1$ and $C_2$ if $H$ is disjoint with both sets.

$$ H\cap C_1 = \empty \text{ and }H\cap C_2 = \empty $$

Disjoint Sets are Separable. Given disjoint $C_1$ and $C_2$, there exists a, not necessarily unique, separating hyperplane for $C_1$ and $C_2$.

$$ C_1 \cap C_2 = \empty \implies \exists \text{ hyperplane } H \text{ s.t. }C_1 \sube H_+ \text{ and } C_2 \sube H_- $$

When both sets are closed and at least one is bounded, a strictly separating $H$ exists.

</aside>