Convex sets play an important role in geometry. In order to understand what convex sets are, we need to define and observe convex combinations.
Convex combinations
Assume we have points $P_{0}, P_{1}, \cdots, P_{n}$. Furthermore, if we choose $\alpha_{0}, \alpha_{1}, \cdots, \alpha_{n}$ such that $0 \leq \alpha_{i} \leq 1, i =0, 1, \cdots, n$ and $\alpha_{0} + \alpha_{1} + \alpha_{2} + \cdots + \alpha_{n} = 1$, we form a new point
$$P = \alpha_{0} P_{0} + \alpha_{1}P_{1} + \cdots + \alpha_{n}P_{n}.$$
Each obtained point $P$ is called a convex combination of points $P_{0}, P_{1}, \cdots, P_{n}$.
For instance, imagine you have two points $P_{0}$, $P_{1}$ and line $P_{0}P_{1}$. Any point $P$ which lies on line $P_{0}P_{1}$ can be written as:
$$P = (1 – \alpha) P_{0} + \alpha P_{1},$$
which is an affine combination of points $P_{0}$ and $P_{1}$.
Convex sets
The point $P$ is a convex combination of points $P_{0}$ and $P_{1}$ because $0 \leq \alpha \leq 1$ and $0 \leq (1 – \alpha) \leq 1$. Moreover, any point on the line segment $\overline{P_{0}P_{1}}$ can be written in this way.
What is a convex set?
Intuitively, if we can draw a straight line between any two arbitrary points of a set which is not entirely in a set, then the set is non – convex.
We say that the set is convex if any convex combination of two arbitrary points of that set is also an element of that set. More precisely, let $V$ denote a real vector space.
Definition: Let $a, b \in V$. Then the set of all convex combinations of $a, b$ is the set of points (*) :
$$ \{c \in V: c = (1 – \alpha)a + \alpha b, 0 \leq \alpha \leq 1 \}. $$
Definition: Let $S \subset V$. We say that $S$ is a convex set if for two points $a, b \in S$ the set (*) is a subset of $S$.
In other words, a convex set is a set which contains all possible convex combinations of its points.
Examples of convex sets
Example 1: The empty set $\emptyset$, the singleton set $\{x\}$ and space $\mathbb{R^n}$ are convex sets.
Example 2: Is an interval $[a, b] \subset \mathbb{R}$ a convex set?
Solution:
Let $c, d \in [a, b]$ and assume, without loss of generality, that $c < d$. Furthermore, let $\alpha \in [0, 1]$. Then
$$a \leq c = (1 – \alpha)c + \alpha c < (1 – \alpha)c + \alpha d$$
$$< (1 – \alpha)d + \alpha d = d$$
$$\leq b.$$
In conclusion, an interval $[a, b] \subset \mathbb{R}$ a convex set.
Example 3: Any line or a ray is a convex set, as it contains the line segment between any two of its points.
Example 4: Some polygons are convex, and some are concave.
Any triangle is a convex set. Also, a regular pentagon is a convex set.
Convex sets in $\mathbb{R^2}$ include interiors of triangles, squares, circles, ellipses etc.
Example 5: The ball $K(x, r)$ is a convex set. More precisely, if we have two vectors $y, z$ within this ball, we can use triangle inequality to show that the line segment $[y, z]$ is also contained within the ball.
Example 6: All regular polyhedra (i.e.) Platonic solids are convex.
Properties of convex sets
Suppose you have two convex sets $A$ and $B$. Is their intersection a convex set also? Furthermore, is their union a convex set?
Intersection of two convex sets is a convex set.
More precisely, consider two points in the intersection $A \cap B$. Obviously, those points are elements of individual sets $A$ and $B$. Therefore, the line segment which connects them is contained in both $A$ and $B$ and hence in the set $A \cap B$.
Similarly, intersection of finite number of sets (even infinite) is also a convex set.
But, the same property isn’t true for unions. In other words, the union of two convex sets is not necessarily a convex set (picture below).
Example 7: Let $C_{1}, C_{2}$ be convex sets in $\mathbb{R^n}$. Prove that $$C_{1} + C_{2} := \{z \in \mathbb{R^n} : z = x_{1} + x_{2}, x_{1} \in C_{1}, x_{2} \in C_{2}\}$$ is convex.
Solution:
Let $z_{1}, z_{2} \in C_{1} + C_{2}$ and take $0 \leq \alpha \leq 1$. Furthermore, let $z_{1} = x_{1} + x_{2}$, where $x_{1} \in C_{1}, x_{2} \in C_{2}$ and $z_{2} = y_{1} + y_{2}$. Then
$$(1 – \alpha) z_{1} + \alpha z_{2} = (1 – \alpha)[x_{1} + x_{2}] + \alpha [y_{1} + y_{2}]$$
$$= [(1 – \alpha) x_{1} + \alpha y_{1}] + [(1 – \alpha) x_{2} + \alpha y_{2}] \in C_{1} + C_{2},$$
because sets $C_{1}$ and $C_{2}$ are convex.
The sum from Example 7 is called the Minkowski sum of convex sets.
When $C_{2} = \{c\}$ is a singleton, we write the set $C_{1} + \{c\}$ as $C_{1} + c$ and call it the translation of $C_{1}$.
Example 8: Let $A \subseteq \mathbb{R^n}$ be a set and $\alpha \in \mathbb{R}$. We define the scaling $\alpha A \subseteq \mathbb{R^n}$ as
$$\alpha A = \{\alpha x : x \in A\}.$$
When $\alpha > 0$, the set $\alpha A$ is called a dilation of $A$.
Try to prove that if $A$ is convex, then for any $\alpha \in \mathbb{R}$ the set $\alpha A$ is convex.
Convex hull
Definition: Let $S \subseteq \mathbb{R^n}$. A set of all convex combinations of points from $S$, denoted by $conv S$ is called the convex hull of $S$.
Obviously, a convex hull is a convex set. Moreover, the convex hull of a set $S$ is the smallest convex set which includes $S$.
Some other properties of a convex hull:
$S \subset conv S$
$\forall S’, S’$ convex, $S \subset S’ \rightarrow$ conv$S \subset S’$
Furthermore, any closed convex set $S$ can be written as the convex hull of a possibly infinite set of points $P$: $S =$hull$(T)$.
Indeed, if $S$ is a closed convex set, it is the convex hull of itself.
