Convex Sets and Functions

Convex sets

A set $\mathcal{C}$ is called convex if for any two elements, $x, y \in \mathcal{C}$ ,and for any scalar, $\theta \in [0,1]$, the following property holds:

In other words, convex sets are sets such that a straight line connecting any two elements of the set lies inside the set.

Some properties of convex sets are given below:

• The empty and the whole space are convex.

• The intersection of any collection of convex sets is convex.

• The union of two convex sets need not be convex.

A non-convex set is a set that is not convex. In other words, in a non-convex set, a straight line connecting two elements of the set doesn’t always lie inside the set. Sometimes, non-convex sets are also referred to as concave sets.

The figure below illustrates the difference between convex and non-convex sets visually:

For example, if we draw a line between any two points inside a circle, we find that the entire line segment stays within the circle. This is why a circle is considered a part of the convex set. Similarly, if we draw a line between two points located in the lobes of a heart shape, we see that part of the line segment falls outside the heart shape. Therefore, a heart shape is not a part of the convex set. Similar explanations hold true for all the shapes in the sets in the figure above.

Convex functions

Convex functions are functions such that a straight line between any two points on the function always lies above the function. Mathematically, a function $f: \R^n \rightarrow \R$ is convex if, for any two points, $x, y \in \R^n$, and any scalar, $\theta \in [0,1]$, the following property holds:

A function is strictly convex if the following property holds:

To understand the relation between convex functions and convex sets, consider the set obtained by filling in a convex function. A convex function is a bowl-like structure, and after filling it with water, the resultant filled-in set is always a convex set.

Some common examples of convex functions are given below:

• $y = ax^2 + bx + c$, where $a> 0$.

• $y = \vert x \vert^p$, where $p \geq 1$.

• $y = e^x$.

• $y= mx + c$.

• $y = x^p$, where ...