0

Suppose I have a compact set $\mathcal A\subset \mathbb R^n$ that is not convex, and denote $\mathcal B = \{y \in \mathbb R^p : \|y\|_\infty \leq 1\}$ the unit infinity norm ball. For $p \geq n+1$, is the following set convex?

$$ \mathcal S = \left\{\sum_{i=1}^p y_i x_i : y\in \mathcal B, \; x_i \in \mathcal A\right\}. $$

If $\mathcal B$ is the unit simplex, then this is true via Cartheodory's theorem. And, if $p \to \infty$, then there is a "smearing" like action going on here, and $\mathcal S$ will be convex. But I'm not sure about this more general case.

Also what happens of $\mathcal B$ is a more general (convex, compact) set? Can we make the argument based on dimensionality alone (and including $0$ in the interior)?

Edit: An example where $\mathcal S$ is not convex when $p < n$, take $\mathcal A = \{(0,1), (0,1)\}$ and $\mathcal B = [0,1]$. Then $\mathcal S = \{(0,s) : 0\leq s \leq 1\}\cup \{(s,0) : 0\leq s \leq 1\}$, e.g. two rays along the axis, but nothing in the middle (it's spiky).

If I now allow $p = 2$, then the points are allowed to "mix", and you can get $\mathcal S = \{[s_1,s_2] : 0 \leq s_1,s_2 \leq 1\}$, which is convex.

Actually I think the set is convex; I just can't prove it for general $\mathcal A$, nor see exactly how to use Cartheodory (which feels important...)

Y. S.
  • 1,816

1 Answers1

1

Let $n=2$, $p > 3$, and $\mathcal A = \{(1,0), (0,1)\}$. If we take $x_i = (1,0)$ $k$ times and $(0,1)$ $p-k$ times, $\{\sum_i y_i x_i: y \in {\mathcal B}\}$ is the convex hull of $(k,0)$, $(-k,0)$, $(0,p-k)$ and $(0,-p+k)$. $\mathcal S$ is the union of these for $k$ from $0$ to $p$. But this is not convex: e.g. it contains $(p,0)$ and $(0,p)$ but not $(p/2, p/2)$.

Robert Israel
  • 448,999
  • Sorry can you elaborate a bit? Let's take a concrete example (I changed it to $p \geq n+1$ because I realized I was being too restrictive.) Let's say $p = 3$ and $n = 2$. Let's take $x_1 =x_2=(1,0)$, $x_3 = (0,1)$. Then $S = conv{(2,0),(-2,0), (1,0), -1,0)}$, which is convex. In particular in your example, $S$ won't contain $(p,0)$, I think. – Y. S. Dec 18 '19 at 15:16
  • The point is that you could take $x_1 = x_2 = x_3 = (1,0)$ to get $(3,0)$, and $x_1 = x_2 = x_3 = (0,1)$ to get $(0,3)$. $\mathcal S$ allows all choices of $x_1, x_2, x_3$ from $\mathcal A$. – Robert Israel Dec 18 '19 at 16:25
  • Hmm, ok yeah I see your point as to why it won't work for $p = 1$. For $p = 2$, we can achieve the midpoint then. Thanks! – Y. S. Dec 20 '19 at 12:39