Convexity

The notion of convexity plays an important role in mathematical optimization. We start with some definitions.

Lines and line segments

A line in \(\mathbb{R}^n\) is a set \(\{ \mathbf{x} + \lambda \mathbf{d} : \lambda \in \mathbb{R}\}\) for some \(\mathbf{x}, \mathbf{d} \in \mathbb{R}^n\) with \(\mathbf{d} \neq \mathbf{0}\).

For example, the line in \(\mathbb{R}^2\) defined by the equation \(y = x+1\) is given by the set \(\left\{ \begin{bmatrix} 0 \\1 \end{bmatrix} + \lambda \begin{bmatrix}1\\1\end{bmatrix} : \lambda \in \mathbb{R}\right\}\).

As a line segment is simply a portion of a line, we can use the definition for a line and restrict the values of \(\lambda\) to an interval. However, it is customary to specify a line segment by its endpoints. Hence, a line segment between \(\mathbf{u}, \mathbf{v} \in \mathbb{R}^n\), denoted by \([\mathbf{u}, \mathbf{v}]\), is the set \(\{ (1 -\lambda)\mathbf{u} + \lambda \mathbf{v} : 0 \leq \lambda \leq 1 \}\).

Note that when \(\lambda = 0\), \((1 -\lambda)\mathbf{u} + \lambda \mathbf{v} =\mathbf{u}\), and when \(\lambda = 1\), \((1 -\lambda)\mathbf{u} + \lambda \mathbf{v} = \mathbf{v}\). Therefore, we can think of \(\lambda\) as the fraction of the line segment away from the starting point \(\mathbf{u}\). For example, the midpoint of the line segment \([\mathbf{u}, \mathbf{v}]\) is given by \(\frac{1}{2}\mathbf{u} + \frac{1}{2} \mathbf{v}\).

Convex sets

A set \(C \subseteq \mathbb{R}^n\) is said to be convex if for all \(\mathbf{x}, \mathbf{y} \in C\), \([\mathbf{x}, \mathbf{y}] \subseteq C\). We say that \(C\) is a convex set in \(\mathbb{R}^n\).

Proposition 8.1. Given a collection of convex sets \((C_i)_{i \in I}\) where \(I\) is an index set, \(\displaystyle\bigcap_{i \in I} C_i\) is also a convex set.

In other words, the intersection of convex sets is a convex set. The proof of this proposition is left as an exercise.

In general, it is not that easy to prove that a given convex set is indeed convex. Fortunately, there is a family of sets that are easily shown to be convex that will be sufficient for much of the work that we will be doing.

For a set in \(\mathbb{R}^2\), it is perhaps easier to sketch the set and see if it is convex.

Polyhedron

A halfspace in \(\mathbb{R}^n\) is a set \(\{ \mathbf{x} \in\mathbb{R}^n : \mathbf{a}^\mathsf{T} \mathbf{x} \geq \beta \}\) for some nonzero \(\mathbf{a} \in \mathbb{R}^n\) and \(\beta \in \mathbb{R}\). In other words, a halfspace is the set of points satisfying a single nontrivial linear inequality.

For example, the set \( \left \{\begin{bmatrix} x_1 \\ x_2\end{bmatrix} : x_1 \geq 0\right\}\) is a halfspace in \(\mathbb{R}^2\),

Proposition 8.2. Halfspaces are convex.

A polyhedron in \(\mathbb{R}^n\) is the intersection of finitely many halfspaces in \(\mathbb{R}^n\). Note that the feasible region of a linear programming problem is a polyhedron.

As halfspaces are convex and intersections of convex sets are convex, we have the following result.

Theorem 8.3. Polyhedra are convex.

Worked examples

1. Show that \(P = \left \{ \begin{bmatrix} x_1\\x_2 \end{bmatrix} \in \mathbb{R}^2: x_1, x_2 \geq 0 \right \}\) is a convex set.

   Let \(\mathbf{x},\mathbf{y} \in P\). Let \(\lambda \in [0,1]\). To show that \(P\) is convex, it suffices to show that \(z := (1-\lambda) \mathbf{x} + \lambda \mathbf{y}\) is in \(P\).

   Note that \(z_i = (1-\lambda) x_i + \lambda y_i\) for \(i = 1,2\). Since \(\mathbf{x}, \mathbf{y}\in P\), \(x_i, y_i \geq 0\) for \(i = 1,2,\). As \(\lambda, 1-\lambda \geq 0 \), we se that \(z_i \geq 0\) for \(i = 1,2\). Hence, \(\mathbf{z} \in P\) as desired.

2. Show that \(C = \left \{ \begin{bmatrix} x_1\\x_2 \end{bmatrix} \in \mathbb{R}^2: x_1^2 + x_2^2 \leq 1 \right \}\) is a convex set.

   Let \(\mathbf{x},\mathbf{y} \in C\). Let \(\lambda \in [0,1]\). To show that \(P\) is convex, it suffices to show that \(z := (1-\lambda) \mathbf{x} + \lambda \mathbf{y}\) is in \(C\).

   First note that \(1 - |x_1y_1 + x_2y_2| \geq 0\). Indeed, \(1 - (x_1y_1 + x_2y_2)^2 \geq (x_1^2 + x_2^2)(y_1^2 + y_2^2) - (x_1y_1 + x_2y_2)^2 = x_1^2y_2^2 + x_2^2y_1^2 - 2x_1x_2y_1y_2 = (x_1y_2 - x_2 y_1)^2 \geq 0,\) implying that \(1 \geq (x_1y_1 + x_2y_2)^2\).

   Now \begin{eqnarray*} 1 - (z_1^2 + z_2^2) & = & 1 - ( (1-\lambda)x_1+\lambda y_1) )^2 - ( (1-\lambda)x_2+\lambda y_2) )^2 \\ & = & 1 - ((1-\lambda)^2 x_1^2+2\lambda(1-\lambda)x_1y_1+\lambda^2 y_1^2) - ( (1-\lambda)^2 x_2^2+ 2\lambda(1-\lambda)x_2y_2 +\lambda^2 y_2^2) \\ & = & 1 - (1-\lambda)^2 (x_1^2 + x_2^2) - \lambda^2 (y_1^2 + y_2^2) - 2\lambda(1-\lambda)(x_1y_1+x_2y_2) \\ & \geq & 1 - (1-\lambda)^2 - \lambda^2 -2\lambda(1-\lambda)(x_1y_1+x_2y_2) \\ & = & 2\lambda(1-\lambda)(1 - (x_1y_1+x_2y_2)) \\ & \geq & 2\lambda(1-\lambda)(1 - |x_1y_1+x_2y_2|) \\ & \geq & 0 \end{eqnarray*} Hence, \(\mathbf{z} \in C\) as desired.

   Remark. If an algebraic proof was not required, it would have been easier to sketch the set and notice that the set is a disc and therefore convex.