Convex set

In this topic, we are going to study convex sets. The usage of convex sets is very wide and varies from optimization to machine learning. The reason we need to learn them is their close relation with linear programming. If we are able to determine that a given set is convex, it makes our lives easier. In this case, we can use special theorems to immediately find the solution for linear programming problems (even those with large dimensions). Thus, studying convex sets is the first step to solve linear programming problems. Further in this topic, we will define convex sets using line segments, have a look at the most popular examples of convex sets, and prove their property that we will need in linear programming theorems.

A few examples

For this topic, it is important to remember that some sets can be represented graphically, because this is the easiest way to understand why a set is convex (or non-convex). Let's take a look at some examples of sets and their corresponding geometric shapes:

• unit circle $$R = \{(x, y): x^2 + y^2 \leq 1\}$$

  

• part of the plane bounded by the deltoid curve (the Steiner curve) $$D = \{(x,y): (x^2 + y^2)^2 + 18 (x^2 + y^2) \leq 8x^3 - 24y^{2}x+27\}$$

• ring $$K = \{(x,y): x^2 + y^2 \geq 1, x^2 + y^2 \leq 2 \}$$

Line segment

As you can see from the name of this topic, the main discussion is going to be about convex sets. However, to define convex sets, it is necessary to understand the concept of a line segment, since this concept is used in the definition of a convex set.

Definition. Line segment between points $p$ and $q$ is all points $$x = (1-t)p+ tq$$ with $0\leq t \leq 1$.

The notation of points here and further is not that significant. You can choose any you like: $p,q,n,s,r ,\ldots$.

Now, a line segment is a part of a line that is bounded by two distinct end points and contains every point on the line that is between its endpoints.

What is a convex set?

Look at these sets. Try to guess, which of them is convex?

If you've chosen the left one, you are absolutely right. Probably, the reason you picked set $A$ and not set $B$ is that the latter has a small cavity. What a nice intuition you have!

So, a convex set is a set that doesn't have any cavities. This is for sure an informal definition. How can we formalize it? In other words, how can we define cavities?

Let us select two points in the set $A$ and draw a line segment between them. It is well seen that this line segment lies inside the region of set $A$. Moreover, no matter which points in the set $A$ we select, all line segments between them will also lie inside the corresponding region.

Now, let us do the same with the set $B$. Can we find such points in set $B$ that, if we draw a line segment between them, some parts of this line segment will lie outside the region of set $B$? Yes, we can! This is how we can describe a cavity.

Now we can define convex sets using line segments.

Set $A$ is convex if the line segment between any two points in $A$ lies in $A$. The set that is not convex is called non-convex or concave.

Definition. A set $A$ is convex if for all points $$p, q \in A, (1-t)p + tq \in A$$ with $0\leq t\leq 1$.

This is a coordinate formula, which means that it can be used for both $x$-coordinates and $y$-coordinates of points $p$ and $q$. In the following section, you can see how it is possible to use this formula.

You can find more examples of convex and non-convex sets below.

Convex sets:

Non-convex sets:

Special cases

So, now you can tell convex sets from non-convex ones if they are represented graphically. However, it is also very important to spot convex sets if they are written in the analytical form, because that is how they usually appear in mathematical problems, in particular, in linear programming. Below you can find a few important examples of convex sets.

• Empty set

The empty set is a set that contains no elements.

• Singleton set

The singleton set is a set that contains just 1 element. For example, $A=\{3.14\}$.

• Half-plane

A half-plane is a planar region consisting of all points on one side of an infinite straight line, and no points on the other side. The examples are shown below.

Take notice that a solution set $L$ for the linear inequality $$a_1 x_1 + a_2 x_2 + a_3 x_3 +\ldots + a_n x_n \leq b$$ is a half-plane.

Hence, the solution set for any linear inequality is a convex set.

Let's prove the convexity of half-plane $a_1 x + a_2 y \leq b, (b \geq 0)$, using the definition of convex set. Suppose that two points $\mathbf{p_1}=(x_1, y_1)$ and $\mathbf{p_2}=(x_2, y_2)$ are chosen from the half-plane. This means that their coordinates satisfy the half-plane equation, i.e. the following inequalities are true:

$$a_1x_1 + a_2 y_1 \leq b, \qquad a_1x_2 + a_2 y_2 \leq b.$$Remember them, they will come in handy soon.

Then the coordinates of any point $\mathbf{p}$ lying between the points $\mathbf{p_1}$ and $\mathbf{p_2}$ are determinated by line segment equation. Let's write this equation:

$$\mathbf{p} = (1-t)\mathbf{p_1}+ t\mathbf{p_2} = \begin{pmatrix} (1 - t)x_1 + tx_2\\ (1 - t)y_1 + ty_2 \end{pmatrix},$$where $0\leq t \leq 1$.

Thus, $x$-coordinate of point $\mathbf{p}$ is equal to $(1 - t)x_1 + tx_2$, and $y$-coordinate of point $\mathbf{p}$ is equal to $(1 - t)y_1 + ty_2$. Now we can check if point $\mathbf{p}$ lies in the half-plane. Let's substitute coordinates of point $\mathbf{p}$ in half-plane equation:

$$a_1 \left[ (1 - t) x_1 + tx_2 \right] + a_2 \left[ (1 - t)y_1 + ty_2 \right].$$Let's open brackets:

$$a_1(1-t)x_1 + a_1t x_2 + a_2 (1-t) y_1 + a_2 t y_2.$$We group similar terms at $t$ and $(1-t)$.

$$a_1(1-t)x_1 + a_2 (1-t) y_1 + a_1t x_2 + a_2 t y_2 = (1-t) \left[ a_1 x_1 + a_2 y_1 \right] + t \left[ a_1 x_2 + a_2 y_2 \right]$$Look at the expressions in square brackets and compare them with the inequalities of the coordinates of $\mathbf{p_1}$ and $\mathbf{p_2}$ mentioned above. The expressions in square brackets represent the left side of those coordinate expressions. Let's replace these expressions with the right side and expand the brackets.

$$(1-t) \left[ a_1 x_1 + a_2 y_1 \right] + t \left[ a_1 x_2 + a_2 y_2 \right] \leq (1-t)b + tb = b - tb + tb = b.$$Removing all unnecessary transformations, we can write the following:

$$a_1 \left[ (1 - t) x_1 + tx_2 \right] + a_2 \left[ (1 - t)y_1 + ty_2 \right] \leq b$$This means that when the coordinates of the point $\mathbf{p}$ are substituted into the inequality $a_1 x + a_2 y \leq b$, it remains true. Hence, the point $\mathbf{p}$ belongs to the half-plane given by this inequality.

The proof is complete.

• Polyhedron

A polyhedron can be interpreted as an intersection of many half-planes.

Let's now discuss one important property of convex sets.

Proof. If the intersection is empty, or consists of a single point, the theorem is true by definition (empty and singleton sets are always convex). Otherwise, let $A$ and $B$ be two convex sets. Let's take any two points $p$, $q$ in the intersection of $A$ and $B$. Let point $h$ lie on the line segment between $p$, $q$, then, $h$ lies in $A$, because $A$ is convex, and similarly, $h$ lies in $B$, because $B$ is also convex. Therefore, $h$ lies in the intersection of $A$ and $B$. The proof is complete.

The proof can be also extended to multiple convex sets. Based on this property, we can argue that the polyhedron is a convex set, because it consists of the intersection of half-planes, and as we've found out, a half-plane is a convex set.

Conclusion

Let's go over the main points of the topic:

• a line segment is a part of a line that is bounded by two distinct endpoints;
• a convex set is a set that has no cavities;
• you can check if a set is convex using the definition of convex sets;
• a solution set for the linear inequality is a half-plane (which is a convex set);
• the fact that intersection of convex sets is also a convex set will be useful later in linear programming;
• never trust anyone (even this topic), always check.