3
$\begingroup$

Let $X_1,\ldots,X_k \subseteq \mathbb{R}^n$ be convex sets. It was claimed (in some notes on convex optimization that I was reading) $$\operatorname{Co}\left(\bigcup_{i=1}^k X_i\right)=\left\{\sum_{i=1}^k t_i x_i : x_i \in X_i,t_i\geq 0,\sum_{i=1}^k t_i =1\right\}. $$ I'd like to convince myself this is true.

I see why "$\supseteq$" is true b/c every element in the RHS set is a convex combination of elements in $\bigcup_{i=1}^k X_i$. At the moment I'm trying to show the RHS set is a convex set, and I'm running into difficulty b/c if $$\sum_{i=1}^k t_i x_i, \quad \sum_{i=1}^k s_i y_i$$ are elements of the RHS set, it's not easy for me to see $$c\sum_{i=1}^k t_i x_i+(1-c)\sum_{i=1}^k s_i y_i$$ is an element of the RHS (where $c\in[0,1]$). Perhaps there is an easier way to show "$\subseteq$"

$\endgroup$
1
  • $\begingroup$ Not a proof, but to convice yourself, try $X_1=\{(1,0)\}, X_2=0 \times [0,1] \subset \mathbb R^2$. It's not obvious. $\endgroup$
    – lhf
    Sep 25 '15 at 2:08
2
$\begingroup$

$\newcommand{\Co}{\operatorname{Co}}$If you want to prove that $$ \Co\left( \bigcup_{i=1}^k X_i \right) \subseteq \left\{\sum_{i=1}^k t_i x_i : x_i \in X_i,t_i\geq 0,\sum_{i=1}^k t_i =1\right\}, \tag 1 $$ you should just assume $x$ is an element of the left side and prove that it follows that it's an element of the right side.

For now I'll take $\Co\left( \bigcup_{i=1}^k X_i \right)$ to be defined as the intersection of all convex sets having $\bigcup_{i=1}^k X_i$ as a subset. To show that if $x$ is a member of the left side of $(1)$, then $x$ is a member of the right side of $(1)$ is to show that if $x$ is a member of every convex set having $\bigcup_{i=1}^k X_i$ as a subset, then $x$ is a member of the right side of $(1)$. For that, it is enough to show that the right side of $(1)$ is a convex set having $\bigcup_{i=1}^k X_i$ as a subset. Then we would have

  • $x$ is a member of every convex set having $\bigcup_{i=1}^k X_i$ as a subset.
  • The right side of $(1)$ is a convex set having $\bigcup_{i=1}^k X_i$ as a subset.
  • Therefore, $x$ is a member of the right side of $(1)$.

So the question is: How do we prove the second statement in the bulleted list above?

Notice that if $t_j=1$ and $t_i=0$ for all $i\ne j$, then $t_i\ge0$ for $i=1,\ldots,k$ and $t_1+\cdots+t_k = 1$, so $t_1 x_1 + \cdots + t_k x_k$ is a member of the right side of $(1)$. But $t_1 x_1 + \cdots + t_k x_k = x_j \in X_j$. Thus $x_j$ is a member of the right side of $(1)$. Since $x_j$ could have been any member of $X_j$ at all, we conclude that every member of $X_j$ is a member of the right side of $(1)$, so $X_j$ is a subset of the right side of $(1)$. Since the index $j$ may be any of $1,\ldots,k$, we must conclude that all of $X_1,\ldots,X_k$ are subsets of the right side of $(1)$. Therefore $\bigcup_{i=1}^k X_i$ is a subset of the right side of $(1)$.

Next we must prove that the right side of $(1)$ is convex. So suppose $x$ and $y$ are members of that set; we must prove that every convex combination $cx+(1-c)y$ is a member of the right side of $(1)$. We have \begin{align} x & = t_1 x_1 + \cdots + t_k x_k \\[5pt] y & = s_1 y_1 + \cdots + s_k y_k \end{align} for some scalars $t_1,\ldots,t_k,s_1,\ldots,s_k$, all $\ge0$ and satisfing $t_1+\cdots+t_k=1=s_1+\cdots+s_k$.

Let

$$ w_i = \frac{ct_i}{ct_i + (1-c)s_i} x_i + \frac{(1-c)s_i }{ct_i + (1-c)s_i} y_i\qquad \text{for }i=1,\ldots,k $$ and $$ r_i = c t_i + (1-c) s_i \qquad \text{for }i=1,\ldots,k. $$

Then $$ cx+(1-c)y = \sum_{i=1}^k r_i w_i. \tag 2 $$ Since it was assumed that $X_i$ is convex, we have $w_i\in X_i$ for $i=1,\ldots,k$. Therefore, $(2)$ is a member of the right side of $(1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.