Convex and Affine Sets

Lines Between Points¶

The above figure shows two vectors, $p_1$ and $p_2,$ drawn with respect to some basis, and the vector, $p_2 - p_1$, that joins them. Any point along the line that encompasses the vector $p_2 - p_1$ can be given by a vector

where $t$ is a scalar. If $t~\in~[0,1]$ then $\bm{l}$ can be considered to be a probabilistic mixture of the vectors $p_1$ and $p_2$.

Convex Functions¶

In the above figure, a function $f(X)$ is plotted. For any two points on the graph, $x_1$ and $x_2$, it can be seen that the value $f(x')$ is less then $f(x_1)$ and $f(x_2)$ if $x_1 \leq x' \leq x_2$. This means all points between $x_1$ and $x_2$ sit below the line-segment between those points. This can be stated mathematically as

The argument of the left hand side, $tx_1 + (1-t)x_2$, is the straight line between $x_1$ and $x_2$. The right hand side is the straight line between $f(x_1)$ and $f(x_2)$.

If the above criteria is satisfied, the function $f(X)$ is a convex function.

Convex Sets¶

Let $V$ be a vector space over a field $\mathbb{F}$. A subset $S \subset V$ is convex if for all $\psi, \sigma~\in~S$ the line segment connecting $\psi$ and $\sigma$ is also in $S$, as seen in Fig (a) above. Mathematically this means that

If a mixture of elements in the subset can lead to an element outside of the subset, as seen in fig (b) above where some points on the line segment are outside the boundary of the set, the subset is not convex.

In general, a set $S$ is convex if for all subsets of objects in $S$, $\{ \psi_1, \psi_2, \ldots, \psi_n \} \in S~\forall~\psi_i$, then

The boundary of a convex set is always a convex curve.

The convex hull of a set $S' \subset V$ is the smallest convex set that contains $S'$.

Affine¶

Let $V$ be a vector space over a field $\mathbb{F}$. A subset $S \subset V$ is affine if for every pair in the set the whole infinite line through those two points is in $S$. Mathematically, this means that

The key difference between affine sets and convex sets is that $t$ does not need to be in the set $[0,1]$ and can be negative. This means that the whole line including $\psi$ and $\sigma$ is included, not just the line segment between $\psi$ and $\sigma$.

In general, a set $S$ is affine if for all subsets of objects in $S$, $\{ \psi_1, \psi_2, \ldots, \psi_n \} \in S~\forall~\psi_i$, then

where, as before, the condition for $a_i$ to be positive has been removed.

Hence, convex combinations can be thought of as a weighted average of elements of the set, whilst affine combinations can be thought of as a weighted average where the weights can be negative.