Twitter response:

Convex sets

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

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?


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.


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.