4

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$"

Michael Hardy
  • 1
Jason
  • 2,065
  • 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. – lhf Sep 25 '15 at 02:08

1 Answers1

3

$\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)$.

Michael Hardy
  • 1