Convex Set

Definition 3.2   Convex Set. In Euclidean space, a convex set is the region such that, for every pair of points within the region, every point on the straight line segment that joins the pair of points is also within the region.

Figure: (a) Convex set, (b) Non-convex set.

Let $S$ be a vector space over the real numbers $\Re$, or, more generally, some ordered field. This includes Euclidean spaces. A set $C$ in $S$ is said to be convex if, for all $p$ and $q$ in $C$ and all $\alpha$ in the interval $[0, 1]$, the point $(1 - \alpha)p + \alpha q$ also belongs to $C$. In other words, every point on the line segment connecting $p$ and $q$ is in $C$. This implies that a convex set in a real or complex topological vector space is path-connected, thus connected. Furthermore, $C$ is strictly convex if every point on the line segment connecting $p$ and $q$ other than the endpoints is inside the interior of $C$.

In geometric terms, a body $C$ in the Euclidean space is convex if and only if the line segment joining any two points in $C$ lies totally in $C$. But, this theorem is not suitable for computational purpose as there are infinitely many possible pairs of points to be considered. However, other properties of convexity $C$ be utilized to yield an algorithm.

For example, a cube in $\Re^3$ is a convex but its boundary is not, for the boundary does not contain segment $pq$, unless $p$ and $q$ lie in the same two-dimensional face of the cube.

The importance of convexity theory stems from the fact that convex sets frequently arise in many areas of mathematics, and are helpful in elementary reasoning. Even infinite-dimensional theory is based on 2- and 3-dimensional reasoning.

Any two distinct points $p$ and $q$ of real vector space $\Re$ determine a unique line. It consists of all points of the form $(1-\alpha)*p+\alpha *q$, $\alpha$ ranging over all real numbers. Those points for which $\alpha \geq 0$ and those for which $0 \leq \alpha \leq 1$ form respectively the ray from $p$ through $q$ and the segment $pq$.

The convex subsets of $\Re$ (the set of real numbers) are simply the intervals of $\Re$. Some examples of convex subsets of the Euclidean plane are solid regular polygons, solid triangles, and intersections of solid triangles. Some examples of convex subsets of a Euclidean 3-dimensional space are the Archimedean solids and the Platonic solids. The Kepler-Poinsot polyhedra are examples of non-convex sets.

Example 3.3   The figure (a) shows a line segment, while (b) shows a circle in 2-dimensional convex set.

Figure: (a) Points ona line segment as a Convex set , (b) Points in a circle as a convex set.

Solution. the case of line segment, let the points marked on line are 2, 3, 4, 5. Let us call the points on line as the set $C$. Hence, $(1-\alpha)*p + \alpha q \in C$. Let $\alpha = 0.5$, $p=2$, and $q=5$. We note that $(1-0.5)*2 + 0.5*5$ = $3.5 \in C$.

Similarly, we can verify it for circle. Let the circle is $x^2 + y^2 =2$, i.e., centered at (0, 0), with radius of 1. Let $x=0.5, y = 0.75$ is $p$ and $x=-0.4, y = -0.8$ are the points $p$ and $q$. Let $\alpha = 0.6$. Then first, $(1-\alpha)*p + \alpha q$ = $(1-0.6)0.5 + (-0.4)*0.6$ = $-0.04$. Similarly, for $y$, $(1-\alpha)*p + \alpha q$ = $(1-0.6)0.75 + (-0.8)*0.6$ = $-0.18$. Thus, we note that $(1-\alpha)*p + \alpha q$ = $(-0.04, -0.18)\in C$, which satisfy the criteria of convexity. Like, this it should satisfy for all $(x, y)$ in the set $C$.

Definition 3.4   A function is convex if and only if its epigraph, the region (in hashed) above its graph (see fig. ), is a convex set .

Figure: Convex function.

Properties of Convex sets: If $S$ is a convex set in $n$-dimensional space, then for any collection of $r$, $r > 1$, $n$-dimensional vectors $u_1, \dots, u_r$ in $S$, and for any nonnegative numbers $\lambda_1, \dots, \lambda_r$ such that $\lambda_1 + \dots + \lambda_r = 1$, then we have:

$$\sum_{k=1}^r\lambda_k u_k \in S.$$ (3.3)

A vector of this type is known as a convex combination of $u_1, \dots, u_r$.