Convex Optimization - Convex Set

Let $S\subseteq \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 \in\left ( 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_1\cap 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 $\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$,where $\displaystyle\sum\limits_{i=1}^k \lambda_i=1$ and $\lambda_i\geq 0,\forall i \in \left [ 1,k \right ]$ is called conic combination of $x_1,x_2,....x_k.$

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

• Weighted average of the form $\displaystyle\sum\limits_{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:Cx\leq \alpha \right \}$ is a convex set.

Solution

Let $x_1$ and $x_2 \in S$

$\Rightarrow Cx_1\leq \alpha$ and $\:and \:Cx_2\leq \alpha$

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

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

$\Rightarrow Cy\leq \lambda \alpha+\left ( 1-\lambda \right )\alpha$

$\Rightarrow Cy\leq \alpha$

$\Rightarrow y\in 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 )y\in S\Rightarrow \lambda \left ( x_1,x_2 \right )+\left (1-\lambda \right )\left ( y_1,y_2 \right ) \in S\Rightarrow \left [ \lambda x_1+\left ( 1- \lambda)y_2] \in S\right ) \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 \lambda\left ( 1-\lambda \right )x_1y_1$

But $2x_1y_1\leq x_{1}^{2}+y_{1}^{2}$

Therefore,

$\left [ \lambda x_1 +\left ( 1-\lambda \right )y_1\right ]^{2}\leq \lambda ^2x_{1}^{2}+\left ( 1- \lambda \right )^2y_{1}^{2}+2 \lambda\left ( 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 8\lambda x_2+8\left ( 1- \lambda \right )y_2$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}\leq 8\left [\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, \displaystyle\sum\limits_{1}^k c_i=1,c_i\geq 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,\displaystyle\sum\limits_{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.