1 Convexity

1.1 Convex sets

$\textbf{Definition 1.1}$ (Convex set). A set $K \subseteq \mathbb{R}^n$ is convex if it the line segment between any two points in K is also contained in K. Formally, for all $x, y\in K$, and all scalars $\gamma\in [0,1]$, we have $\gamma x+(1-\gamma)y\in K$.

$\textbf{Theorem 1.2}$ (Separation Theorem). Let $C, K \subseteq \mathbb{R}^n$ be convex sets with empty intersection $C \cap K = \emptyset$. Then there exists apoint $a\in \mathbb{R}^n$ and a number $b\in \mathbb{R}$ such that

  1. for all $x \in C$, we have $⟨a,x⟩\geq b$.
  2. for all $x \in K$, we have $⟨a,x⟩\leq b$.

If $C$ and $K$ are closed and at least one of them is bounded, then we can replace the inequalities by strict inequalities.