Why is $\{ \mathbf{x} \in \mathbb{R}^n | \sum_{k=1}^{n} x_{k}^2 = 1 \}$ not a convex set?

Question

We know that a function is convex if it can be written as $$\sum_{k=1}^{n} \lambda_k \mathbf{g_k}(\mathbf{x}) $$

for every $\lambda_k \geq 0$ and $\mathbf{g_k}(\mathbf{x})$ is a convex function.

In our set, the function (I ignore the constant 1) is $$ \mathbf{f}(\mathbf{x}) =\sum_{k=1}^{n} \lambda_k \mathbf{g_k}(\mathbf{x}) = \sum_{k=1}^{n} x_k^2 $$ which is a convex function since $x_k^2$ is convex for every $x$.

Since the function that is defining the set is convex, the set must be convex. But this set is not convex, why?

Answer 1

When we say that a function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is convex, what we mean is that the set of everything above its graph - i.e. $\{(\mathbf{x},y) | f(\mathbf{x}) \leq y \}$ - is convex.

Your set is defined by a function, but not as the space above the graph, so there's no reason to expect it to be convex.

Answer 2

Your set is the surface of the unit ball, which clearly isn't convex because it misses the origin (and it also misses the entire open unit ball).

Answer 3

I believe you compare apples with pears, or here: convex functions with convex sets.

A subset of $\mathbb{R}$ is convex if it is path connected. Thus for every two arbitrary points of the set the points on the line in between must also belong to the set.

This is certainly not the case for a $n$-dimensional unit sphere $S_n$: $$ e_1, -e_1 \in S_n \quad 0 \not\in S $$

Answer 4

To add to the other answers, work from the definition. A set $S$ is convex if for any two points $(x,y)$ in the set $S$, $\theta x + (1-\theta) y \in S \;\forall \theta \in [0,1]$. So the line from $x$ to $y$ has to lie completely in $S$. Check this for $x=(1,0,\dots,0),y=(0,1,0,\dots,0)$ both in $\mathbb{R}^n$ and your set $S=\{x\in \mathbb{R}^n|\sum^n_{k=1}x_k^2=1\}$. Then $\theta^2 1 + (1-\theta)^2 1 = 1 - 2\theta $ needs to equal $1$, which implies it cannot hold for all $\theta\in [0,1]$. This already shows the claim of $S$ being convex is false.