Convex Optimization - Hull

The convex hull of a set of points in S is the boundary of the smallest convex region that contain all the points of S inside it or on its boundary.

OR

Let $S\subseteq \mathbb{R}^n$ The convex hull of S, denoted $Co\left ( S \right )$ by is the collection of all convex combination of S, i.e., $x \in Co\left ( S \right )$ if and only if $x \in \displaystyle\sum\limits_{i=1}^n \lambda_ix_i$, where $\displaystyle\sum\limits_{1}^n \lambda_i=1$ and $\lambda_i \geq 0 \forall x_i \in S$

Remark − Conves hull of a set of points in S in the plane defines a convex polygon and the points of S on the boundary of the polygon defines the vertices of the polygon.

Theorem $Co\left ( S \right )= \left \{ x:x=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i,x_i \in S, \displaystyle\sum\limits_{i=1}^n \lambda_i=1,\lambda_i \geq 0 \right \}$ Show that a convex hull is a convex set.

Proof

Let $x_1,x_2 \in Co\left ( S \right )$, then $x_1=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i$ and $x_2=\displaystyle\sum\limits_{i=1}^n \lambda_\gamma x_i$ where $\displaystyle\sum\limits_{i=1}^n \lambda_i=1, \lambda_i\geq 0$ and $\displaystyle\sum\limits_{i=1}^n \gamma_i=1,\gamma_i\geq0$

For $\theta \in \left ( 0,1 \right ),\theta x_1+\left ( 1-\theta \right )x_2=\theta \displaystyle\sum\limits_{i=1}^n \lambda_ix_i+\left ( 1-\theta \right )\displaystyle\sum\limits_{i=1}^n \gamma_ix_i$

$\theta x_1+\left ( 1-\theta \right )x_2=\displaystyle\sum\limits_{i=1}^n \lambda_i \theta x_i+\displaystyle\sum\limits_{i=1}^n \gamma_i\left ( 1-\theta \right )x_i$

$\theta x_1+\left ( 1-\theta \right )x_2=\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i\theta +\gamma_i\left ( 1-\theta \right ) \right ]x_i$

Considering the coefficients,

$\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i\theta +\gamma_i\left ( 1-\theta \right ) \right ]=\theta \displaystyle\sum\limits_{i=1}^n \lambda_i+\left ( 1-\theta \right )\displaystyle\sum\limits_{i=1}^n\gamma_i=\theta +\left ( 1-\theta \right )=1$

Hence, $\theta x_1+\left ( 1-\theta \right )x_2 \in Co\left ( S \right )$

Thus, a convex hull is a convex set.