2.1 Convex Sets

Convex Set

A subset $C\subseteq {\mathbb{R}}^n$ is called convex if, for any two points $x,y\in C$ and for every scalar $\alpha \in [0,1]$, the points on the entire line segment joining $x$ and $y$ is within $C$, such that $\alpha x+(1-\alpha )y\in C$:

\begin{document}
\begin{tikzpicture}[scale=1.5]
 
%---------------------------------
% Convex set (left)
%---------------------------------
\begin{scope}
 % Draw a green convex blob
 \draw[thick]
   plot[smooth cycle] coordinates {
     (0,1) (1,2) (2,2.5) (3,2) (3,1) (2,0.5)
   };
 % Label it
 \node at (1.7,0) {Convex Set};
 
 % Define two points x, y inside the blob
 \coordinate (xLeft) at (1.2,1.2);
 \coordinate (yLeft) at (2.2,1.5);
 
 % Draw the line segment between x and y
 \draw[thick] (xLeft) -- (yLeft);
 
 % Mark the points x, y
 \fill (xLeft) circle (1pt) node[below left] {$x$};
 \fill (yLeft) circle (1pt) node[above right] {$y$};
\end{scope}
 
%---------------------------------
% Non-convex set (right)
%---------------------------------
\begin{scope}[shift={(4,0)}]  % shift everything 6 units to the right
 % Draw a green *non-convex* blob with a 'dent'
 \draw[thick]
   plot[smooth cycle] coordinates {
     (0,1) (1,2.2) (2,2.5) (1.5, 1) (2.6,1.6) (2,0.4) (0.5,0.5)
   };
 % Label it
 \node at (1.3,0) {Non-Convex Set};
 
 % Define two points x, y that appear 'inside' visually,
 % but the line segment between them will cross outside the shape
 \coordinate (xRight) at (1.6,2.1);
 \coordinate (yRight) at (2.3,1.2);
 
 % Draw the line segment
 \draw[thick] (xRight) -- (yRight);
 
 % Mark the points x, y
 \fill (xRight) circle (2pt) node[above left] {$x$};
 \fill (yRight) circle (2pt) node[above right] {$y$};
\end{scope}
 
\end{tikzpicture}
\end{document}

The dimension of $C$ is equal to the dimension of its affine hull (i.e., $\dim C=\dim \mathrm{aff}(C)$).

Convex Hull $C$ is convex if $\mathrm{co}(\{\vec{x},\vec{y}\})\subset C$ for all $\vec{x},\vec{y}\in C$.

One can be quick to notice that

Properties

(Separation Theorem) For a closed convex set $C\subset X$ , and $x_0\in X\backslash C$, there exist some $x^{\ast }\in X^{\ast }$ and $\delta >0$, such that $⟨x^{\ast },x_0⟩+\delta \le ⟨x^{\ast },c⟩$ holds for all $c\in C$.

Removing all the abstraction, the separation theorem states that a separating hyperplane $x^{\ast }$ exists, represented as a linear functional (i.e., as a vector of function coefficients), that separates $C$ from $x_0$. We now prove the separation theorem.

(Support Function Representation) Let $C$ be a closed convex set, $x\in X$, and $h_C(x^{\ast })=\underset{x\in X}{\sup }⟨x^{\ast },x⟩$ be a support function. Then, $C=\bigcap _{x^{\ast }\in X^{\ast }}\{x:⟨x^{\ast },x⟩\le h_C(x^{\ast })\}$.

This outcome of the separation theorem states that any closed and convex set $C$ can be represented as the intersection of all of its supporting half-spaces. Think of it as intersecting the 3 half-spaces of a triangle, in order to form that triangle based on their overlap.

Why is $h_C(x^{\ast })$ a support function? We can imagine this closely if $C$ is also compact (i.e., well-defined). Then, the hyperplane $H=\{x:⟨x^{\ast },x⟩=h_C(x^{\ast })\}$ for all $x^{\ast }\in X^{\ast }$ is tangent to $C$.

(Convex Projection) For a closed convex $C$, let

Examples

Convex Set Potpourri

Consider the set ${\mathcal{S}}_1=\{x\in {\mathbb{R}}^n\mid f(x)\le 0\}$, where $f:{\mathbb{R}}^n\to \mathbb{R}$ is a convex function.

Show that ${\mathcal{S}}_1$ is a convex set. Consider points $x_1,x_2$, such that $f(x_1)\le 0$ and $f(x_2)\le 0$. Since $f$ is convex, it follows that

f(\alpha x_{1} + (1-\alpha)x_{2}) &\leq \alpha f(x_{1}) + (1-\alpha)f(x_{2}) \\ &\leq \alpha 0 + (1-\alpha) 0 \\ &= 0. \end{align}$$

Now, consider the set
${\mathcal{S}}_2=\{x\in {\mathbb{R}}^3\mid e^{-x_1-2x_2-3x_3}+5(x_1+x_2+x_3{)}^8\le x_1+x_2+x_3+10,x_1^4+x_2^4+x_3^4\le 2\}.$

Show that ${\mathcal{S}}_2$ is a convex set.  It is enough to show that each constraint defines a convex set, and the overall set is formed by intersections of those constraints.