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 $Ssubseteq mathbb{R}^n$ The convex hull of S, denoted $Coleft ( S ight )$ by is the collection of all convex combination of S, i.e., $x in Coleft ( S ight )$ if and only if $x in displaystylesumpmits_{i=1}^n lambda_ix_i$, where $displaystylesumpmits_{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 $Coleft ( S ight )= left { x:x=displaystylesumpmits_{i=1}^n lambda_ix_i,x_i in S, displaystylesumpmits_{i=1}^n lambda_i=1,lambda_i geq 0 ight }$ Show that a convex hull is a convex set.

Proof

Let $x_1,x_2 in Coleft ( S ight )$, then $x_1=displaystylesumpmits_{i=1}^n lambda_ix_i$ and $x_2=displaystylesumpmits_{i=1}^n lambda_gamma x_i$ where $displaystylesumpmits_{i=1}^n lambda_i=1, lambda_igeq 0$ and $displaystylesumpmits_{i=1}^n gamma_i=1,gamma_igeq0$

For $ heta in left ( 0,1 ight ), heta x_1+left ( 1- heta ight )x_2= heta displaystylesumpmits_{i=1}^n lambda_ix_i+left ( 1- heta ight )displaystylesumpmits_{i=1}^n gamma_ix_i$

$ heta x_1+left ( 1- heta ight )x_2=displaystylesumpmits_{i=1}^n lambda_i heta x_i+displaystylesumpmits_{i=1}^n gamma_ileft ( 1- heta ight )x_i$

$ heta x_1+left ( 1- heta ight )x_2=displaystylesumpmits_{i=1}^nleft [ lambda_i heta +gamma_ileft ( 1- heta ight ) ight ]x_i$

Considering the coefficients,

$displaystylesumpmits_{i=1}^nleft [ lambda_i heta +gamma_ileft ( 1- heta ight ) ight ]= heta displaystylesumpmits_{i=1}^n lambda_i+left ( 1- heta ight )displaystylesumpmits_{i=1}^ngamma_i= heta +left ( 1- heta ight )=1$

Hence, $ heta x_1+left ( 1- heta ight )x_2 in Coleft ( S ight )$

Thus, a convex hull is a convex set.