Is the Set K Convex and Does It Attain Its Euclidean Distance?

[evinda]

Hello! (Wave)

We consider the set $K=\{ x \in \mathbb{R}^n: \sum_{j=1}^n |x_j|^2 \leq 1 \}$ and let $ \in \mathbb{R}^n$. Check if the euclidean distance of $z$ from $K$ is attained.

I want to show that $K$ is closed and convex. Then by a theorem, the distance will be attained by a unique point.

I have tried to show that $K$ is closed as follows.

Let $(\overline{x_m})$ be a sequence in $K$ such that $\overline{x_m} \to x \in \mathbb{R}^n$.
We will show that $x \in K$.
$\overline{x_m}=(x_{m1}, x_{m2}, \dots, x_{mn}), x=(x_1, x_2, \dots, x_n)$

Then $|x_{mi}-x_i| \leq ||\overline{x_m}-x||_2= \left( \sum_{j=1}^n |x_{mj}-x_j|^2\right)^{\frac{1}{2}} \to 0$.

Thus $x_{mi} \to x_i$ while $m \to +\infty$ for all $i=1, \dots, n$ with $\sum_{j=1}^n |x_{mj}|^2 \leq 1$ for all $m=1,2, \dots$

Thus $\sum_{j=1}^n |x_j|^2 \leq 1$ and so $\overline{x} \in K$.

In order to show that $K$ is convex , I have thought the following:

Let $x,y \in K, 0<\lambda<1$.
We will show that $(1- \lambda)x+ \lambda y \in K$.

We have $x=(x_1, \dots, x_n), y=(y_1, \dots, y_n)$ and so $(1- \lambda)x+ \lambda y=((1- \lambda)x_1+ \lambda y_1, \dots, (1-\lambda)x_n+ \lambda y_n )$

So it suffices to show that $\sum_{j=1}^n |(1- \lambda) x_j+ \lambda y_j|^2 \leq 1$.

$ |(1- \lambda) x_j+ \lambda y_j| \leq (1- \lambda) |x_j|+ \lambda |y_j|$

So $\sum_{j=1}^n |(1- \lambda) x_j+ \lambda y_j|^2 \leq \sum_{j=1}^n \left( (1- \lambda) |x_j|+ \lambda |y_j|\right)^2= \sum_{j=1}^n \left( (1- \lambda)^2 |x_j|^2+ 2 \lambda (1- \lambda) |x_j| |y_j|+\lambda^2 |y_j|^2\right)= (1- \lambda)^2 \sum_{j=1}^n |x_j|^2 + 2 \lambda (1- \lambda) \sum_{j=1}^n |x_j||y_j| + \lambda^2 \sum_{j=1}^n |y_j|^2$

What bound can we use for $\sum_{j=1}^n |x_j||y_j| $ to show that the above is $\leq 1$ ? (Thinking)

 

[caffeinemachine]

Hello! (Wave)

We consider the set $K=\{ x \in \mathbb{R}^n: \sum_{j=1}^n |x_j|^2 \leq 1 \}$ and let $ \in \mathbb{R}^n$. Check if the euclidean distance of $z$ from $K$ is attained.

I want to show that $K$ is closed and convex. Then by a theorem, the distance will be attained by a unique point.

I have tried to show that $K$ is closed as follows.

Let $(\overline{x_m})$ be a sequence in $K$ such that $\overline{x_m} \to x \in \mathbb{R}^n$.
We will show that $x \in K$.
$\overline{x_m}=(x_{m1}, x_{m2}, \dots, x_{mn}), x=(x_1, x_2, \dots, x_n)$

Then $|x_{mi}-x_i| \leq ||\overline{x_m}-x||_2= \left( \sum_{j=1}^n |x_{mj}-x_j|^2\right)^{\frac{1}{2}} \to 0$.

Thus $x_{mi} \to x_i$ while $m \to +\infty$ for all $i=1, \dots, n$ with $\sum_{j=1}^n |x_{mj}|^2 \leq 1$ for all $m=1,2, \dots$

Thus $\sum_{j=1}^n |x_j|^2 \leq 1$ and so $\overline{x} \in K$.

In order to show that $K$ is convex , I have thought the following:

Let $x,y \in K, 0<\lambda<1$.
We will show that $(1- \lambda)x+ \lambda y \in K$.

We have $x=(x_1, \dots, x_n), y=(y_1, \dots, y_n)$ and so $(1- \lambda)x+ \lambda y=((1- \lambda)x_1+ \lambda y_1, \dots, (1-\lambda)x_n+ \lambda y_n )$

So it suffices to show that $\sum_{j=1}^n |(1- \lambda) x_j+ \lambda y_j|^2 \leq 1$.

$ |(1- \lambda) x_j+ \lambda y_j| \leq (1- \lambda) |x_j|+ \lambda |y_j|$

So $\sum_{j=1}^n |(1- \lambda) x_j+ \lambda y_j|^2 \leq \sum_{j=1}^n \left( (1- \lambda) |x_j|+ \lambda |y_j|\right)^2= \sum_{j=1}^n \left( (1- \lambda)^2 |x_j|^2+ 2 \lambda (1- \lambda) |x_j| |y_j|+\lambda^2 |y_j|^2\right)= (1- \lambda)^2 \sum_{j=1}^n |x_j|^2 + 2 \lambda (1- \lambda) \sum_{j=1}^n |x_j||y_j| + \lambda^2 \sum_{j=1}^n |y_j|^2$

What bound can we use for $\sum_{j=1}^n |x_j||y_j| $ to show that the above is $\leq 1$ ? (Thinking)

Hello Evinda,

A very happy new year to you!

Now.

To show that $K$ is closed, you could use a much more slicker and general argument.
Define a map $f:\mathbf R^n\to \mathbf R$ as
$$f(x)=\sum_{i=1}^n x_i^2$$
This is a continuous map. Note that $K=f^{-1}([0, 1])$. So $K$ is the pre-image of a closed set under a continuous map whence we infer that $K$ is closed.

This is a fairly general technique to show if a set if closed. In fact, anything "defined by an equation" is usually closed.

Now for convexity. Suppose $x, y\in K$, and let $1\leq a\leq 1$.
We need to shoe that $ax+(1-a)y$ is also in $K$.
We have $$\| ax+(1-a)y\|^2 = a^2\|x\|^2+(1-a)^2\|y\|^2+2a(1-a)x\cdot y\leq a^2+(1-a)^2+2a(1-a)x\cdot y$$
where '$\cdot$' denotes the dot product.

Using Cauchy-Schawrz we have $x\cdot y\leq 1$.
Using this we get $\|ax+(1-a)y\|^2\leq a^2+(1-a)^2+2a(1-a)\leq 1$
and thus $ax+(1-a)y\in K$.

We have shown that $K$ is closed and convex.

I would like to point out something. To show that the distance of $z$ from $K$ is achieved, you have used support-separation property of hyperplanes. But this uses too much about the nature of $K$, and proves too much (it proves that the uniqueness of the point achieving minimum distance).

To only prove that distance is achieved, it is sufficient to note that $K$ closed and bounded. This makes $K$ a compact set and thus we are done. Tell me if you need more explanation on this.

 

[math771]

Hello! Yes, I agree with your approach so far. To show that $K$ is convex, we can use the Cauchy-Schwarz inequality. This states that for any two vectors $u$ and $v$, we have $|u \cdot v| \leq ||u||_2 \cdot ||v||_2$, where $u \cdot v$ is the dot product of $u$ and $v$.

In our case, we have $x=(x_1, \dots, x_n)$ and $y=(y_1, \dots, y_n)$, so $x \cdot y = \sum_{j=1}^n x_jy_j$.
Using the Cauchy-Schwarz inequality, we have $|x \cdot y| \leq ||x||_2 \cdot ||y||_2$.
Then, by taking the absolute value and squaring both sides, we get $(x \cdot y)^2 \leq ||x||_2^2 \cdot ||y||_2^2$.
Now, we can use this inequality in our previous calculation:

$\sum_{j=1}^n |x_j||y_j| \leq \left( \sum_{j=1}^n |x_j|^2 \right)^{\frac{1}{2}} \cdot \left( \sum_{j=1}^n |y_j|^2 \right)^{\frac{1}{2}} = ||x||_2 \cdot ||y||_2$.

Substituting this back into our previous calculation, we get:

$(1- \lambda)^2 \sum_{j=1}^n |x_j|^2 + 2 \lambda (1- \lambda) \sum_{j=1}^n |x_j||y_j| + \lambda^2 \sum_{j=1}^n |y_j|^2 \leq (1- \lambda)^2 \sum_{j=1}^n |x_j|^2 + 2 \lambda (1- \lambda) ||x||_2 \cdot ||y||_2 + \lambda^2 \sum_{j=1}^n |y_j|^2$.

Since $x$ and $y$ are both in $K$, we have $\sum_{j=1