Let $Ssubseteq mathbb{R}^n$ A set S is said to be convex if the line 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 right )x_2 in S$ where $lambda inleft ( 0,1 right )$.

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 right )x_2 in S_i$ where $lambda in left ( 0,1 right )$

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

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

Hence, $S_3$ is a convex set.

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

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

• Weighted average of the form $displaystylesumlimits_{i=1}^k lambda_ix_i$ is called linear combination of $x_1,x_2,….x_k.$

Examples

Step 1 − Prove that the set $S=left { x in mathbb{R}^n:Cxleq alpha right }$ 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 right )x_2 right )in S :forall :lambda inleft ( 0,1 right )$

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

$Rightarrow Cyleq lambda alpha+left ( 1-lambda right )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 right )in mathbb{R}^2:x_{1}^{2}leq 8x_2 right }$ is a convex set.

Solution

Let $x,y in S$

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

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

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

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

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

Therefore,

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

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

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

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

$Rightarrow lambda x+left ( 1- lambda right )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, displaystylesumlimits_{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,displaystylesumlimits_{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 right )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 right )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.