Given one compact convex set $ X \subset \mathbf{R}^n$.

The cartesian product $Y = X \times X \subset \mathbf{R}^{2n} = \{(x_1, x_2)|x_1 \in X \text{ and } x_2\in X \}$ is going to be compact convex set again.

But what if there is a constrain such that $Z = \{(x_1, x_2)|x_1 \in X, x_2 \in X \text{ and } x_1 + x_2 \in X\}$.

Is $Z$ still going to be compact convex?

E.g. n=1, $X = [0, 1]$, $Y$ would be a square □ , and $Z$ would be a lower left triangle ◺ .

So the constrain more or less cut the compact convex set in half, I'm wondering what's the name for that?

And what's more would "half" the compact convex set still be compact convex ?


The resulting set is still convex. I took the inspiration from @Renard and made a direct proof.

The key is to construct another set $A = \{(x, y)| x \in \mathbf{R}^n, y \in \mathbf{R}^n, x+y \in X\}$ and prove this set is convex.

Since $Z = A \cap Y$. And $Y$ Is Convex, if A is convex, we know the intersection of convex sets is till convex set.

Prove A is a convex set. We took two elements $a_1:=(x_1, y_1), a_2:=(x_2, y_2) \in A$ And $t \in [0, 1]$.

Based on definition of A, $x+y \in X$. So $x_1+y_1 \in X, x_2+y_2 \in X$.

Since $X$ is Convex. We can have \begin{equation} \label{eq1} t*(x_1+y_1)+(1-t)*(x_2+y_2) \in X \\ (t*x_1+ (1-t)*x_2) + (t*y_1+(1-t)*y_2) \in X \end{equation}

We also have

\begin{equation} \begin{aligned} a_3 & = t*a_1+(1-t)*a_2 \\ & = t*(x_1, y_1) + (1-t)*(x_2, y_2) \\ & = (t*x_1+(1-t)*x_2, t*y_1+(1-t)*y_2) \end{aligned} \end{equation}

we know $(x_3, y_3) =a_3, x_3+y_3 = (t*x_1+(1-t)*x_2)+(t*y_1+(1-t)*y_2) \in X$. And clearly $x_3 = t*x_1+(1-t)*x_2 \in \mathbf{R}^n$, $y_3 = t*y_1+(1-t)*y_2 \in \mathbf{R}^n $

So that $a_3 \in A$.

Hence $A$ is convex. We can conclude $Z$ is convex

| cite | improve this answer | |

I'm not sure if I'm translating your $\mathbb{R}^2$ example correctly to the $\mathbb{R}^n$ case. Sorry if it's not what you have in mind.

Consider the closed halfspace, $H_c = \left\lbrace x_i \in \mathbb{R}^n \text{ for } i = 1,...,n : \sum_{i=1}^n \sum_{j=1}^n x_{ij} \le c \right\rbrace$.

$Y$ is compact since it is a product of compact sets. Consider $H_c \cap Y$. If it is non-empty for some $c$, the intersection is a closed subset of a compact set, so compact, and the intersection of convex sets, so convex.

Define $\bar{c} = \max \left\lbrace c \in \mathbb{R}: \sum_{i=1}^n \sum_{j=1}^n x_{ij} \le c \text{ with each } x_i\in X \right\rbrace$.

Then $Z=H_{\bar{c}} \cap Y$, so it is compact and convex.

I don't know that there's a name for this in particular.

| cite | improve this answer | |
  • $\begingroup$ thanks! the $X$ I'm interested in is a convex polyhedron. not sure did I accurately translated it into the set language. $\endgroup$ – peng yu Jun 24 at 18:25

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.