Question

Which of the following sets are convex? Give reason.
(i) A={(x1, x2):x1,x2 ≤1; x1, x2 ≥0}
(ii) B={(x1, x2):x2-3≥x1²; x1, x2 ≥0}

Answer 1

Answer on Question #66374 – Math – Linear Algebra

Which of the following sets are convex? Give reason.

Question

(i) $A = \{(x_{1}, x_{2}) : x_{1}, x_{2} \leq 1; x_{1}, x_{2} \geq 0\}$

Solution

We recall the definition of the convex set. A set $C$ is convex if for any $u, v \in C$ the point $\theta u + (1 - \theta)v \in C$ for all $\theta \in [0,1]$.

Let $u, v \in A$ and $\theta \in [0,1]$. The vector $u = (u_1, u_2)$ is such that $0 \leq u_1 \leq 1$ and $0 \leq u_2 \leq 1$ and, correspondingly, the vector $v = (v_1, v_2)$ is such that $0 \leq v_1 \leq 1$ and $0 \leq v_2 \leq 1$.

We have to prove that the vector $\theta u + (1 - \theta)v = (\theta u_1 + (1 - \theta)v_1, \theta u_2 + (1 - \theta)v_2) \in A$ for all $\theta \in [0,1]$.

Indeed, for $i = 1$ and $i = 2$: $\theta u_i + (1 - \theta)v_i \geq 0$ since $u_i \geq 0, v_i \geq 0, \theta \in [0,1]$ and $\theta u_i + (1 - \theta)v_i \leq \theta + (1 - \theta) = 1$ since $u_i \leq 1, v_i \leq 1, \theta \in [0,1]$. Therefore, $\theta u + (1 - \theta)v \in A$ for all $\theta \in [0,1]$ and $A$ is a convex set.

**Answer**: Convex.

Question

(ii) $B = \{(x_{1}, x_{2}) : x_{2} - 3 \geq x_{1}^{2}; x_{1}, x_{2} \geq 0\}$

Solution

Let us recall that translation preserves convexity of the set. See, for example https://web.stanford.edu/class/ee364a/lectures/sets.pdf

Therefore we translate the set $B$ by vector $(0, -3)$. We come to the set $B' = \{(x_1, x_2) : x_2 \geq x_1^2; x_1, x_2 \geq 0\}$. Let's prove that $B'$ is convex.

Let $u, v \in B'$ and $\theta \in [0,1]$. We have to prove that the vector $\theta u + (1 - \theta)v = (\theta u_1 + (1 - \theta)v_1, \theta u_2 + (1 - \theta)v_2) \in B'$ for all $\theta \in [0,1]$.

Let us consider the inequality:

$$\theta u _ {1} ^ {2} + (1 - \theta) v _ {1} ^ {2} \geq (\theta u _ {1} + (1 - \theta) v _ {1}) ^ {2}.$$

The following are equivalent:

$$\theta u _ {1} ^ {2} + (1 - \theta) v _ {1} ^ {2} \geq (\theta u _ {1} + (1 - \theta) v _ {1}) ^ {2}$$ $$\theta u _ {1} ^ {2} + (1 - \theta) v _ {1} ^ {2} \geq \theta^ {2} u _ {1} ^ {2} + 2 \theta (1 - \theta) u _ {1} v _ {1} + (1 - \theta) ^ {2} v _ {1} ^ {2}$$ $$0 \geq (\theta^ {2} - \theta) u _ {1} ^ {2} - 2 (\theta^ {2} - \theta) u _ {1} v _ {1} + [ (1 - \theta) ^ {2} - (1 - \theta) ] v _ {1} ^ {2}$$ $$0 \geq (\theta^ {2} - \theta) u _ {1} ^ {2} - 2 (\theta^ {2} - \theta) u _ {1} v _ {1} + (\theta^ {2} - \theta) v _ {1} ^ {2}$$ $$0 \geq (\theta^ {2} - \theta) (u _ {1} - v _ {1}) ^ {2}$$

The final inequality is true for all $\theta$ if $u_{1} = v_{1}$ , and if $u_{1} \neq v_{1}$ , then the final inequality holds exactly when $\theta \in [0,1]$ .

It means that for all $\theta \in [0,1]$ and $u,v\in B^{\prime}$ we have

$$(\theta u _ {1} + (1 - \theta) v _ {1}) ^ {2} \leq \theta u _ {1} ^ {2} + (1 - \theta) v _ {1} ^ {2} \leq \theta u _ {2} + (1 - \theta) v _ {2}.$$

Therefore, $\theta u + (1 - \theta)v\in B^{\prime}$ for all $\theta \in [0,1]$ . Then $B^{\prime}$ and $B$ , correspondingly, are convex.

Answer: Convex.

Answer provided by https://www.AssignmentExpert.com