Convex Optimization - Convex Set

Let $Ssubseteq mathbb{R}^n$ A set S is said to be convex if the pne segment joining any two points of the set S also belongs to the S, i.e., if $x_1,x_2 in S$, then $lambda x_1+left ( 1-lambda ight )x_2 in S$ where $lambda inleft ( 0,1 ight )$.

Note −

The union of two convex sets may or may not be convex.

The intersection of two convex sets is always convex.

Proof

Let $S_1$ and $S_2$ be two convex set.

Let $S_3=S_1 cap S_2$

Let $x_1,x_2 in S_3$

Since $S_3=S_1 cap S_2$ thus $x_1,x_2 in S_1$and $x_1,x_2 in S_2$

Since $S_i$ is convex set, $forall$ $i in 1,2,$

Thus $lambda x_1+left ( 1-lambda ight )x_2 in S_i$ where $lambda in left ( 0,1 ight )$

Therfore, $lambda x_1+left ( 1-lambda ight )x_2 in S_1cap S_2$

$Rightarrow lambda x_1+left ( 1-lambda ight )x_2 in S_3$

Hence, $S_3$ is a convex set.

Weighted average of the form $displaystylesumpmits_{i=1}^k lambda_ix_i$,where $displaystylesumpmits_{i=1}^k lambda_i=1$ and $lambda_igeq 0,forall i in left [ 1,k ight ]$ is called conic combination of $x_1,x_2,....x_k.$

Weighted average of the form $displaystylesumpmits_{i=1}^k lambda_ix_i$, where $displaystylesumpmits_{i=1}^k lambda_i=1$ is called affine combination of $x_1,x_2,....x_k.$

Weighted average of the form $displaystylesumpmits_{i=1}^k lambda_ix_i$ is called pnear combination of $x_1,x_2,....x_k.$

Examples

Step 1 − Prove that the set $S=left { x in mathbb{R}^n:Cxleq alpha ight }$ is a convex set.

Solution

Let $x_1$ and $x_2 in S$

$Rightarrow Cx_1leq alpha$ and $:and :Cx_2leq alpha$

To show:$::y=left ( lambda x_1+left ( 1-lambda ight )x_2 ight )in S :forall :lambda inleft ( 0,1 ight )$

$Cy=Cleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )=lambda Cx_1+left ( 1-lambda ight )Cx_2$

$Rightarrow Cyleq lambda alpha+left ( 1-lambda ight )alpha$

$Rightarrow Cyleq alpha$

$Rightarrow yin S$

Therefore, $S$ is a convex set.

Step 2 − Prove that the set $S=left { left ( x_1,x_2 ight )in mathbb{R}^2:x_{1}^{2}leq 8x_2 ight }$ is a convex set.

Solution

Let $x,y in S$

Let $x=left ( x_1,x_2 ight )$ and $y=left ( y_1,y_2 ight )$

$Rightarrow x_{1}^{2}leq 8x_2$ and $y_{1}^{2}leq 8y_2$

To show − $lambda x+left ( 1-lambda ight )yin SRightarrow lambda left ( x_1,x_2 ight )+left (1-lambda ight )left ( y_1,y_2 ight ) in SRightarrow left [ lambda x_1+left ( 1- lambda)y_2] in S ight ) ight ]$

$Now, left [lambda x_1+left ( 1-lambda ight )y_1 ight ]^{2}=lambda ^2x_{1}^{2}+left ( 1-lambda ight )^2y_{1}^{2}+2 lambdaleft ( 1-lambda ight )x_1y_1$

But $2x_1y_1leq x_{1}^{2}+y_{1}^{2}$

Therefore,

$left [ lambda x_1 +left ( 1-lambda ight )y_1 ight ]^{2}leq lambda ^2x_{1}^{2}+left ( 1- lambda ight )^2y_{1}^{2}+2 lambdaleft ( 1- lambda ight )left ( x_{1}^{2}+y_{1}^{2} ight )$

$Rightarrow left [ lambda x_1+left ( 1-lambda ight )y_1 ight ]^{2}leq lambda x_{1}^{2}+left ( 1- lambda ight )y_{1}^{2}$

$Rightarrow left [ lambda x_1+left ( 1-lambda ight )y_1 ight ]^{2}leq 8lambda x_2+8left ( 1- lambda ight )y_2$

$Rightarrow left [ lambda x_1+left ( 1-lambda ight )y_1 ight ]^{2}leq 8left [lambda x_2+left ( 1- lambda ight )y_2 ight ]$

$Rightarrow lambda x+left ( 1- lambda ight )y in S$

Step 3 − Show that a set $S in mathbb{R}^n$ is convex if and only if for each integer k, every convex combination of any k points of $S$ is in $S$.

Solution

Let $S$ be a convex set. then, to show;

$c_1x_1+c_2x_2+.....+c_kx_k in S, displaystylesumpmits_{1}^k c_i=1,c_igeq 0, forall i in 1,2,....,k$

Proof by induction

For $k=1,x_1 in S, c_1=1 Rightarrow c_1x_1 in S$

For $k=2,x_1,x_2 in S, c_1+c_2=1$ and Since S is a convex set

$Rightarrow c_1x_1+c_2x_2 in S.$

Let the convex combination of m points of S is in S i.e.,

$c_1x_1+c_2x_2+...+c_mx_m in S,displaystylesumpmits_{1}^m c_i=1 ,c_i geq 0, forall i in 1,2,...,m$

Now, Let $x_1,x_2....,x_m,x_{m+1} in S$

Let $x=mu_1x_1+mu_2x_2+...+mu_mx_m+mu_{m+1}x_{m+1}$

Let $x=left ( mu_1+mu_2+...+mu_m ight )frac{mu_1x_1+mu_2x_2+mu_mx_m}{mu_1+mu_2+.........+mu_m}+mu_{m+1}x_{m+1}$

Let $y=frac{mu_1x_1+mu_2x_2+...+mu_mx_m}{mu_1+mu_2+.........+mu_m}$

$Rightarrow x=left ( mu_1+mu_2+...+mu_m ight )y+mu_{m+1}x_{m+1}$

Now $y in S$ because the sum of the coefficients is 1.

$Rightarrow x in S$ since S is a convex set and $y,x_{m+1} in S$

Hence proved by induction.