convex hull of union convex set

1.7k Views Asked by At

I have a following problem:

Let $\Omega_i$ for $i=1,\ldots,m$ be nonempty, convex sets in $\mathbb{R}^n$. Show that $x \in \operatorname{co} \bigcup_{i=1}^m \Omega_i$ if and only if there exist elements $\omega_i \in \Omega_i$ and $\lambda_i \geq 0$ for $i=1,\ldots,m$ with $\sum_{i=1}^m \lambda_i=1$ such that $x= \sum_{i=1}^m \lambda_i \omega_i$.

Remark: $\operatorname{co} \bigcup_{i=1}^m \Omega_i$ be a convex hull of $\bigcup_{i=1}^m \Omega_i$. For any subset $\Omega \subset \mathbb{R}^n$, its convex hull admits the representation $$\operatorname{co} \Omega = \left\{ \sum_{i=1}^k \lambda_i a_i \mid \sum_i^k \lambda_i =1, \lambda_i \geq 0, a_i \in \Omega, k\in \mathbb{N} \right\}$$ Hint of this problem is use the proposition:

Let $\Omega$ be a nonempty, convex set and let $\alpha,\beta \geq 0$. Then $\alpha \Omega + \beta \Omega \subset (\alpha+ \beta) \Omega$

1

There are 1 best solutions below

0
On BEST ANSWER

Let us show that $S\equiv \{\sum_{i=1}^{m} \lambda_i \omega_i:\lambda_i \geq 0 \forall i ,\sum \lambda_i=1, \omega_i \in \Omega_i \forall i\}$ is a convex set. Once this is done it follows that it contains $co (\cup_{i=1}^m \Omega_i)$ because it contains each $\Omega_i$. Also this set is obviously contained in $co (\cup_{i=1}^m \Omega_i)$ so the proof will be complete. So let $x=\sum_{i=1}^{m} \lambda_i \omega_i$ and $y=\sum_{i=1}^{m} \mu_i \omega'_i$. Let $0<a<1$ and consider $ax+by$ where $b=1-a$. We can write this as $\sum_{i=1}^{m} (a\lambda_i \omega_i+b\mu_i \omega'_i)$. Now use the hint. We can write $a\lambda_i \omega_i+b\mu_i \omega'_i$ as $(a\lambda_i +b\mu_i) z_i$ for some $z_i \in \Omega_i$. Hence $ax+by=\sum (a\lambda_i +b\mu_i) z_i$. Just observe that the numbers $a\lambda_i +b\mu_i$ are non-negative and add up to 1.