Determine whether the following sets are convex or not, and explain your reasoning

Question

Here are the sets:

1. $C_1 = \{x \in \mathbb{R}^n : ||x||_2^2 = 1 \}$

2. $C_2 = \{x \in \mathbb{R}^n : max_{i=1, 2, ..., n} x_i \le 1 \}$

3. $C_3 = \{x \in \mathbb{R}^n : min_{i=1, 2, ..., n} x_i \le 1 \}$

4. $C_4 = \{x \in \mathbb{R}^n : max_{i=1, 2, ..., n} |x_i| \ge 1 \}$

For some reason these all seem convex to me, here are my reasons:

1) This is a norm and thus convex.

2) Let $x, y \in C_2$ and $t \in [0, 1]$. Then $max_{i=1, 2, ..., n} \: x_i \le 1$ and $max_{i=1, 2, ..., n} \: y_i \le 1$. If $tx_i + (1-t)y_i \in C_2$ then the set is convex. Consider $$max_{i=1, 2, ..., n} \: (tx_i + (1-t)y_i)$$

$$=tmax_{i=1, 2, ..., n} \: x_i + (1-t)max_{i=1, 2, ..., n} \: y_i.$$

Since $t$ and $(1-t) \le 1$, and since $max_{i=1, 2, ..., n} \: x_i \le 1$ and $max_{i=1, 2, ..., n} \: y_i \le 1$, we know that $max_{i=1, 2, ..., n} \: (tx_i + (1-t)y_i) \le 1$ and thus $tx_i + (1-t)y_i \in C_2$ so the set is convex.

3) The logic seems to be the same as for 2), just replacing the $max$ with $min$.

4) Let $x, y \in C_4$ and $t \in [0, 1]$. Then $max_{i=1, 2, ..., n} \: |x_i| \ge 1$ and $max_{i=1, 2, ..., n} \: |y_i| \ge 1$. Like before, consider $$max_{i=1, 2, ..., n} \: (t|x_i| + (1-t)|y_i|)$$

$$=tmax_{i=1, 2, ..., n} \: |x_i| + (1-t)max_{i=1, 2, ..., n} \: |y_i|$$

Again, since $t$ and $(1-t) \le 1$, and since $max_{i=1, 2, ..., n} \: |x_i| \ge 1$ and $max_{i=1, 2, ..., n} \: |y_i| \ge 1$, we know that $max_{i=1, 2, ..., n} \: (t|x_i| + (1-t)|y_i|) \ge 1$ and thus $t|x_i| + (1-t)|y_i| \in C_4$ so the set is convex.

These seem correct to me but I feel like at least one of these is not convex for some reason. Can someone check my proofs?

Thanks ahead of time

Answer 1

For a set to be convex, every line segment connecting two points in it must lie entirely within the set.

Before you worry about these for general $n$, you should consider them for $n = 2$.

1. is a circle (just the circle itself, not a disk).
2. is a quadrant of the plane, with vertex at $(1,1)$.
3. is the complement of a quadrant of the plane.
4. is the complement of a solid square.

Which of those shapes have points that cannot be connected by a straight line without leaving the set?