Convexification

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,\dots ,{\mathbf{v}}^k\in {\mathbb{R}}^n$. Let ${\lambda }_1,\dots ,{\lambda }_k\in \mathbb{R}$ be such that ${\lambda }_1,\dots ,{\lambda }_k\ge 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,\dots ,{\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,\dots ,{\mathbf{v}}^k\in C$, then $C$ contains all convex combinations of ${\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\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,\dots ,{\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 $\mathrm{conv}(S)$, is the intersection of all convex sets containing $S$. It is not difficult to show that $\mathrm{conv}(S)$ is given by the minimal (smallest) convex set containing $S$.

Note that $\mathrm{conv}(\mathrm{\varnothing })=\mathrm{\varnothing }$ 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 $\mathrm{conv}(S)$ is the same as the set of all possible convex combinations of elements of $S$.

Worked examples

1. Let ${\mathbf{u}}^1=\left[\begin{array}{c}0\\ -1\end{array}\right]$, ${\mathbf{u}}^2=\left[\begin{array}{c}1\\ 2\end{array}\right]$, ${\mathbf{u}}^3=\left[\begin{array}{c}3\\ 0\end{array}\right]$, and ${\mathbf{u}}^4=\left[\begin{array}{c}2\\ -2\end{array}\right]$. Let $\mathbf{v}=\left[\begin{array}{c}2\\ -1\end{array}\right]$.

   1. Show that $\mathbf{v}$ is in the convex hull of $\{{\mathbf{u}}^{\mathbf{1}},{\mathbf{u}}^{\mathbf{2}},{\mathbf{u}}^{\mathbf{3}},{\mathbf{u}}^{\mathbf{4}}\}$.

      Note that $\mathbf{v}$ is in the convex hull of $\{{\mathbf{u}}^{\mathbf{1}},\dots ,{\mathbf{u}}^{\mathbf{4}}\}$ if and only if there exist ${\lambda }_1,\dots ,{\lambda }_4\in \mathbf{R}$ satisfying: $$\begin{array}{r}{\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\ge 0,\end{array}$$ or equivalently, $$\begin{array}{r}{\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\ge 0.\end{array}$$ Solving the system of equations, we obtain $\left[\begin{array}{c}{\lambda }_1\\ {\lambda }_2\\ {\lambda }_3\\ {\lambda }_4\end{array}\right]=\left[\begin{array}{c}\frac{1}{2}-\frac{3}{4}t\\ -\frac{1}{4}+\frac{5}{8}t\\ \frac{3}{4}-\frac{7}{8}t\\ t\end{array}\right].$ We need $t\ge 0$ such that all components are nonnegative. Choosing $t=\frac{1}{2}$, for instance, gives $\left[\begin{array}{c}{\lambda }_1\\ {\lambda }_2\\ {\lambda }_3\\ {\lambda }_4\end{array}\right]=\left[\begin{array}{c}\frac{1}{8}\\ \frac{1}{16}\\ \frac{5}{16}\\ \frac{1}{2}\end{array}\right],$ which is a solution to the original system. Hence, $\mathbf{v}$ is in the convex hull of $\{{\mathbf{u}}^{\mathbf{1}},\dots ,{\mathbf{u}}^{\mathbf{4}}\}$.

   2. Show that $\mathbf{v}$ is not in the convex hull of $\{{\mathbf{u}}^{\mathbf{1}},{\mathbf{u}}^{\mathbf{2}},{\mathbf{u}}^{\mathbf{3}}\}$.

      Note that $\mathbf{v}$ is in the convex hull of $\{{\mathbf{u}}^{\mathbf{1}},{\mathbf{u}}^{\mathbf{2}},{\mathbf{u}}^{\mathbf{3}}\}$ if and only if there exist ${\lambda }_1,{\lambda }_2,{\lambda }_3\in \mathbf{R}$ satisfying: $$\begin{array}{r}{\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\ge 0,\end{array}$$ or equivalently, $$\begin{array}{r}{\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\ge 0.\end{array}$$ Solving the system of equations, we obtain $\left[\begin{array}{c}{\lambda }_1\\ {\lambda }_2\\ {\lambda }_3\end{array}\right]=\left[\begin{array}{c}\frac{1}{2}\\ -\frac{1}{4}\\ \frac{3}{4}\end{array}\right],$ which is not a solution to the original system. Hence, $\mathbf{v}$ is not in the convex hull of $\{{\mathbf{u}}^{\mathbf{1}},{\mathbf{u}}^{\mathbf{2}},{\mathbf{u}}^{\mathbf{3}}\}$.

      Remark. If justification is not required, an alternative to solving this part and the previous part is by graphing.

2. Let $C\subseteq {\mathbb{R}}^n$ be a convex set. Prove that if ${\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\mathbf{v}}^k\in C$, then $C$ contains all convex combinations of ${\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\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\ge 2$. Consider the convex combination $z:={\lambda }_1{\mathbf{v}}^1+\dots +{\lambda }_{k+1}{\mathbf{v}}^{k+1}$ where ${\mathbf{v}}^1,\dots ,{\mathbf{v}}^{k+1}\in C$ and ${\lambda }_1,\dots ,{\lambda }_{k+1}\ge 0$ satisfy ${\lambda }_1+\cdots +{\lambda }_{k+1}=1.$ If ${\lambda }_i=0$ for some $i\in \{1,\dots ,k+1\}$, then by the induction hypothesis $z\in C$.

   Hence, suppose that ${\lambda }_i>0$ for $i=1,\dots ,k+1$. Let $\lambda =\sum _{i=1}^k{\lambda }_i$. Then ${\lambda }_{k+1}=1-\lambda$. Then $z=\lambda (\frac{{\lambda }_1}{\lambda }{\mathbf{v}}^1+\cdots +\frac{{\lambda }_k}{\lambda }{\mathbf{v}}^k)+(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,\dots ,{\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$.

3. Let $S=\{\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]:x_1^2+x_2^2=1\}$. 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, $\mathrm{conv}(S)\supseteq \{\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]:x_1^2+x_2^2\le 1\}$. But from a previous exercise, we know that $\{\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]:x_1^2+x_2^2\le 1\}$ is a convex set. Since $\{\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]:x_1^2+x_2^2\le 1\}$ contains $S$, it must contain $\mathrm{conv}(S)$ by the previous exercise. Thus, $\mathrm{conv}(S)$ is the unit disc.

4. Let $\mathbf{x},{\mathbf{d}}^1,\dots ,{\mathbf{d}}^k\in {\mathbb{R}}^n$ where $k$ is a positive integer. Let $S=\{\mathbf{x}+{\displaystyle \sum _{i=1}^k{\lambda }_i{\mathbf{d}}^i:{\lambda }_1,\dots ,{\lambda }_k\in \mathbb{Z}}\}$. Prove that $\mathrm{conv}(S)=\{\mathbf{x}+{\displaystyle \sum _{i=1}^k{\lambda }_i{\mathbf{d}}^i:{\lambda }_1,\dots ,{\lambda }_k\in \mathbb{R}}\}$.

   Let $Q=\{\mathbf{x}+{\displaystyle \sum _{i=1}^k{\lambda }_i{\mathbf{d}}^i:{\lambda }_1,\dots ,{\lambda }_k\in \mathbb{R}}\}$. It is easy to check that $Q$ is convex. Since $S\subseteq Q$, we have $\mathrm{conv}(S)\subseteq Q$.

   We show by induction on $m\ge 0$ that $\{\mathbf{x}+{\displaystyle \sum _{i=1}^k{\lambda }_i{\mathbf{d}}^i:{\lambda }_1,\dots ,{\lambda }_m\in \mathbb{R},{\lambda }_{m+1},\dots ,{\lambda }_k\in \mathbb{Z}}\}\subseteq \mathrm{conv}(S)$.

   The statement holds trivially for $m=0$. Assume that $\{\mathbf{x}+{\displaystyle \sum _{i=1}^k{\lambda }_i{\mathbf{d}}^i:{\lambda }_1,\dots ,{\lambda }_m\in \mathbb{R},{\lambda }_{m+1},\dots ,{\lambda }_k\in \mathbb{Z}}\}\subseteq \mathrm{conv}(S)$.

   Let $\mathbf{u}=\mathbf{x}+{\displaystyle \sum _{i=1}^k{\lambda }_i{\mathbf{d}}^i}$ where ${\lambda }_1,\dots ,{\lambda }_m,{\lambda }_{m+1}\in \mathbb{R}$ and ${\lambda }_{m+2},\dots ,{\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 \mathrm{conv}(S)$. But $\mathbf{u}\in [v,w]$, implying that $\mathbf{u}\in \mathrm{conv}(S)$. Hence, $\{\mathbf{x}+{\displaystyle \sum _{i=1}^k{\lambda }_i{\mathbf{d}}^i:{\lambda }_1,\dots ,{\lambda }_{m+1}\in \mathbb{R},{\lambda }_{m+2},\dots ,{\lambda }_k\in \mathbb{Z}}\}\subseteq \mathrm{conv}(S)$.