In optimization, convexification is an important notion.
The reason is that optimizing a linear function seems to
be easier over a convex set than an arbitrary set.
We now look at some fundamental notions involved in convexification.
Let \(\mathbf{v}^1, \mathbf{v}^2, \ldots, \mathbf{v}^k \in \mathbb{R}^n\).
Let \(\lambda_1, \ldots, \lambda_k \in \mathbb{R}\) be such
that \(\lambda_1,\ldots, \lambda_k \geq 0\)
and \(\lambda_1 + \cdots + \lambda_k = 1\).
Then
\(\lambda_1 \mathbf{v}^1 + \cdots + \lambda_k \mathbf{v}^k\)
is called a convex combination
of \(\mathbf{v}^1, \mathbf{v}^2, \ldots, \mathbf{v}^k\).
For example, the line segment between
\(\mathbf{u}, \mathbf{v} \in \mathbb{R}^n\) is the set of
all convex combinations of
\(\mathbf{u}\) and \(\mathbf{v}\).
Proposition 8.8.
Let \(C \subseteq \mathbb{R}^n\) be a convex set.
if \(\mathbf{v}^1, \mathbf{v}^2, \ldots, \mathbf{v}^k \in C\),
then \(C\) contains all convex combinations of
\(\mathbf{v}^1, \mathbf{v}^2, \ldots, \mathbf{v}^k\).
The proposition can be proved by induction on \(k\) and is left as an
exercise.
It can be shown that
the set of all convex combinations of
\(\mathbf{v}^1, \mathbf{v}^2, \ldots, \mathbf{v}^k\) is a convex set.
The case when \(k = 2\) was proved
previously.
Given a set \(S \subseteq \mathbb{R}^n\), the convex hull of \(S\),
denoted \(\operatorname{conv}(S)\), is the intersection of all convex
sets containing \(S\).
It is not difficult to show that \(\operatorname{conv}(S)\) is given
by the minimal (smallest) convex set containing \(S\).
Note that \(\operatorname{conv}(\emptyset) = \emptyset\) because
the empty set is a convex set that contains the empty set.
Theorem 8.9.
Let \(S\) be a subset of \(\mathbb{R}^n\).
Then \(\operatorname{conv}(S)\) is the same as the
set of all possible convex combinations of elements of \(S\).
Proof.
Let \(Q\) denote the set of all possible convex combinations of elements of
\(S\).
Then \[Q = \{ \lambda_1 \mathbf{v}^1 + \cdots + \lambda_k \mathbf{v}^k :
k \in \mathbb{N}, \lambda_1,\ldots, \lambda_k \geq 0,
\lambda_1 + \ldots + \lambda_k = 1, \mathbf{v}^1,\ldots, \mathbf{v}^k \in
S\}.\]
By Proposition 8.8, any convex set containing \(S\) must also contain \(Q\).
Hence, \(\operatorname{conv}(S) \supseteq Q\).
To show equality, it suffices to show that \(Q\) is a convex set
since \(S \subseteq Q\).
Let \(\mathbf{u},\mathbf{v} \in Q\).
Then, there exist positive integers \(k_u, k_v\) and
nonnegative real numbers \(\alpha_1,\ldots, \alpha_{k_u}\),
\(\beta_1,\ldots, \beta_{k_v}\), and
\(\mathbf{u}^1,\ldots,\mathbf{u}^{k_u},
\mathbf{v}^1,\ldots,\mathbf{v}^{k_v} \in S\), such
that \(\mathbf{u} = \displaystyle\sum_{i = 1}^{k_u} \alpha_i \mathbf{u}^i\),
\(\mathbf{v} =\displaystyle \sum_{i = 1}^{k_v} \beta_i \mathbf{v}^i\),
and \(\displaystyle\sum_{i=1}^{k_u} \alpha_i = \sum_{i=1}^{k_v} \beta_i = 1\).
Then, for any \(\lambda \in [0,1]\),
\begin{eqnarray*}
&& (1-\lambda) \mathbf{u} + \lambda\mathbf{v}
& = &
\sum_{i = 1}^{k_u} ((1-\lambda)\alpha_i) \mathbf{u}^i
+ \sum_{i = 1}^{k_v} (\lambda \beta_i) \mathbf{v}^i.
\end{eqnarray*}
Since
\(\displaystyle\sum_{i = 1}^{k_u} (1-\lambda)\alpha_i
+ \displaystyle\sum_{i = 1}^{k_v} \lambda \beta_i
= (1-\lambda) \displaystyle\sum_{i = 1}^{k_u} \alpha_i
+ \lambda \displaystyle\sum_{i = 1}^{k_v} \beta_i
= (1-\lambda) + \lambda = 1\),
and
\((1-\lambda)\alpha_i \geq 0\) for \(i = 1,\ldots, k_u\) and
\(\lambda\beta_i \geq 0\) for \(i = 1,\ldots, k_v\),
we see that
\((1-\lambda) \mathbf{u} + \lambda\mathbf{v}\) is a convex combination
of elements of \(S\) and therefore is in \(Q\).
This shows that \(Q\) is convex.
Show that \(\mathbf{v}\) is
in the convex hull of \(\{\mathbf{u^1},\mathbf{u^2},\mathbf{u^3},
\mathbf{u^4}\}\).
Note that \(\mathbf{v}\) is
in the convex hull of \(\{\mathbf{u^1},\ldots, \mathbf{u^4}\}\) if and only
if there exist \(\lambda_1,\ldots,\lambda_4\in \mathbf{R}\) satisfying:
\begin{eqnarray*}
\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 = 1 \\
\lambda_1\mathbf{u}^1 + \lambda_2\mathbf{u}^2
+ \lambda_3\mathbf{u}^3 + \lambda_4 \mathbf{u}^4 = \mathbf{v}\\
\lambda_1, \lambda_2, \lambda_3, \lambda_4 \geq 0,
\end{eqnarray*}
or equivalently,
\begin{eqnarray*}
\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 = 1 \\
\lambda_2 + 3\lambda_3 + 2\lambda_4 = 2 \\
-\lambda_1 + 2\lambda_2 -2 \lambda_4 = -1 \\
\lambda_1, \lambda_2, \lambda_3, \lambda_4 \geq 0.
\end{eqnarray*}
Solving the system of equations, we obtain
\(\begin{bmatrix}
\lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \lambda_4 \end{bmatrix} =
\begin{bmatrix}
\frac{1}{2} - \frac{3}{4} t \\
-\frac{1}{4} + \frac{5}{8} t \\
\frac{3}{4} - \frac{7}{8} t \\
t
\end{bmatrix}.
\)
We need \(t \geq 0\) such that all components are nonnegative.
Choosing \(t = \frac{1}{2}\), for instance, gives
\(\begin{bmatrix}
\lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \lambda_4 \end{bmatrix} =
\begin{bmatrix}
\frac{1}{8} \\
\frac{1}{16} \\
\frac{5}{16} \\
\frac{1}{2}
\end{bmatrix},
\)
which is a solution to the original system. Hence,
\(\mathbf{v}\) is
in the convex hull of \(\{\mathbf{u^1},\ldots, \mathbf{u^4}\}\).
Show that \(\mathbf{v}\)
is not in the convex hull of \(\{\mathbf{u^1},\mathbf{u^2}, \mathbf{u^3}\}\).
Note that \(\mathbf{v}\) is
in the convex hull of \(\{\mathbf{u^1},\mathbf{u^2}, \mathbf{u^3}\}\)
if and only
if there exist \(\lambda_1,\lambda_2,\lambda_3\in \mathbf{R}\) satisfying:
\begin{eqnarray*}
\lambda_1 + \lambda_2 + \lambda_3 = 1 \\
\lambda_1\mathbf{u}^1 + \lambda_2\mathbf{u}^2
+ \lambda_3\mathbf{u}^3 = \mathbf{v}\\
\lambda_1, \lambda_2, \lambda_3 \geq 0,
\end{eqnarray*}
or equivalently,
\begin{eqnarray*}
\lambda_1 + \lambda_2 + \lambda_3 = 1 \\
\lambda_2 + 3\lambda_3 = 2 \\
-\lambda_1 + 2\lambda_2 = -1 \\
\lambda_1, \lambda_2, \lambda_3 \geq 0.
\end{eqnarray*}
Solving the system of equations, we obtain
\(\begin{bmatrix}
\lambda_1 \\ \lambda_2 \\ \lambda_3 \end{bmatrix} =
\begin{bmatrix}
\frac{1}{2} \\
-\frac{1}{4} \\
\frac{3}{4}
\end{bmatrix},
\)
which is not a solution to the original system.
Hence, \(\mathbf{v}\) is not
in the convex hull of \(\{\mathbf{u^1},\mathbf{u^2}, \mathbf{u^3}\}\).
Remark. If justification is not required,
an alternative to solving this part and the previous part
is by graphing.
Let \(C \subseteq \mathbb{R}^n\) be a convex set.
Prove that if \(\mathbf{v}^1, \mathbf{v}^2, \ldots, \mathbf{v}^k \in C\),
then \(C\) contains all convex combinations of
\(\mathbf{v}^1, \mathbf{v}^2, \ldots, \mathbf{v}^k\).
As mentioned in the notes above, the case when \(k = 2\) has previously
been established.
Assume that \(C\) contains all
convex combinations of any \(k\) elements of \(C\) where \(k \geq 2\).
Consider the convex combination
\(z := \lambda_1 \mathbf{v}^1 + \ldots + \lambda_{k+1} \mathbf{v}^{k+1}\)
where \(\mathbf{v}^1,\ldots, \mathbf{v}^{k+1}\in C\) and
\(\lambda_1,\ldots,\lambda_{k+1} \geq 0\) satisfy
\(\lambda_1+\cdots+\lambda_{k+1} = 1.\)
If \(\lambda_i = 0\) for some \(i \in \{1,\ldots, k+1\}\), then by
the induction hypothesis \(z \in C\).
Hence, suppose that
\(\lambda_i \gt 0\) for \(i = 1,\ldots,k+1\).
Let \(\lambda = \sum_{i =1 }^k \lambda_i\).
Then \(\lambda_{k+1} = 1 - \lambda\).
Then
\(z = \lambda \left(\frac{\lambda_1}{\lambda}\mathbf{v}^1
+\cdots + \frac{\lambda_k}{\lambda}\mathbf{v}^k\right)
+ (1-\lambda) \mathbf{v}^{k+1}\).
Observe that
\(\frac{\lambda_1}{\lambda}\mathbf{v}^1
+\cdots + \frac{\lambda_k}{\lambda}\mathbf{v}^k\) is
a convex combination of \(\mathbf{v}^1,\ldots,\mathbf{v}^k\) and
therefore is in \(C\) by the induction hypothesis.
Hence, \(z\) is the convex combination of two elements in \(C\) and
therefore is in \(C\).
Let \(S = \left\{ \begin{bmatrix} x_1 \\ x_2\end{bmatrix} :
x_1^2 + x_2^2 = 1\right\}\).
Describe the convex hull of \(S\).
Note that \(S\) is the unit circle on the two-dimensional Euclidean plane.
Any convex set containing \(S\) must contain all the chords of
the circle. Hence,
\(\operatorname{conv}(S)
\supseteq \left\{ \begin{bmatrix} x_1 \\ x_2\end{bmatrix}
: x_1^2 + x_2^2 \leq 1\right\}\).
But from a
previous exercise, we know that
\(\left\{ \begin{bmatrix} x_1 \\ x_2\end{bmatrix} : x_1^2 + x_2^2 \leq 1
\right\}\) is a convex set.
Since \(\left\{ \begin{bmatrix} x_1 \\ x_2\end{bmatrix} : x_1^2 + x_2^2 \leq 1
\right\}\) contains \(S\), it must contain \(\operatorname{conv}(S)\)
by the previous exercise.
Thus, \(\operatorname{conv}(S)\) is the unit disc.
Let \(\mathbf{x},\mathbf{d}^1,\ldots,\mathbf{d}^k \in \mathbb{R}^n\) where
\(k\) is a positive integer.
Let \(S = \left\{\mathbf{x}+
\displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i
: \lambda_1,\ldots,\lambda_k \in \mathbb{Z}\right\}\).
Prove that \(\operatorname{conv}(S) =
\left\{\mathbf{x}+\displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i
: \lambda_1,\ldots,\lambda_k \in \mathbb{R}\right\}\).
Let \(Q = \left\{\mathbf{x}+\displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i
: \lambda_1,\ldots,\lambda_k \in \mathbb{R}\right\}\).
It is easy to check that \(Q\) is convex.
Since \(S \subseteq Q\), we have \(\operatorname{conv}(S)\subseteq Q\).
We show by induction on \(m \geq 0\) that
\(\left\{\mathbf{x}+\displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i
: \lambda_1,\ldots,\lambda_m \in \mathbb{R},
~\lambda_{m+1},\ldots, \lambda_k \in \mathbb{Z}\right\}
\subseteq \operatorname{conv}(S)\).
The statement holds trivially for \(m = 0\).
Assume that
\(\left\{\mathbf{x}+\displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i
: \lambda_1,\ldots,\lambda_m \in \mathbb{R},
~\lambda_{m+1},\ldots, \lambda_k \in \mathbb{Z}\right\}
\subseteq \operatorname{conv}(S)\).
Let \(\mathbf{u} =
\mathbf{x}+\displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i\)
where \(\lambda_1,\ldots,\lambda_m, \lambda_{m+1} \in \mathbb{R}\)
and \(\lambda_{m+2},\ldots, \lambda_k \in \mathbb{Z}\).
Let \(\mathbf{v} =
\mathbf{x}
+\lambda_1\mathbf{d}^1
\cdots
+\lambda_m\mathbf{d}^m
+ \lfloor \lambda_{m+1} \rfloor \mathbf{d}^{m+1}
+ \lambda_{m+2}\mathbf{d}^{m+2}
\cdots
+ \lambda_{k}\mathbf{d}^{k}
\)
and let
\(\mathbf{w} =
\mathbf{x}
+\lambda_1\mathbf{d}^1
\cdots
+\lambda_m\mathbf{d}^m
+ \lceil \lambda_{m+1} \rceil \mathbf{d}^{m+1}
+ \lambda_{m+2}\mathbf{d}^{m+2}
\cdots
+ \lambda_{k}\mathbf{d}^{k}
\).
By the induction hypothesis,
\(\mathbf{v},\mathbf{w} \in \operatorname{conv}(S)\).
But \(\mathbf{u} \in [v,w]\), implying that
\(\mathbf{u} \in\operatorname{conv}(S)\).
Hence,
\(\left\{\mathbf{x}+\displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i
: \lambda_1,\ldots,\lambda_{m+1} \in \mathbb{R},
~\lambda_{m+2},\ldots, \lambda_k \in \mathbb{Z}\right\}
\subseteq \operatorname{conv}(S)\).