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

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Convex Set
In summary: Thinking)In summary, we discussed the set $K$, defined as $K=\{ x \in \mathbb{R}^n: \sum_{j=1}^n |x_j|^2 \leq 1 \}$ and proved that it is both closed and convex. This was done by using a general argument to show that $K$ is closed by considering it as the pre-image of a closed set under a continuous map, and then using the Cauchy-Schwarz inequality to show that it is also convex. We also briefly discussed the achievement of distance of a point $z$ from $K$ and how it can be proved using the fact that $K$ is compact.
  • #1
evinda
Gold Member
MHB
3,836
0
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)
 
Physics news on Phys.org
  • #2
evinda said:
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.
 
  • #3


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
 

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

1. What is a convex set?

A convex set is a set of points where the line segment connecting any two points in the set also lies within the set. In other words, a convex set is a set that does not have any "dents" or "indentations."

2. How do you show that a set is convex?

To show that a set is convex, you can use the definition of a convex set and demonstrate that the line segment connecting any two points in the set is also contained within the set. This can be done by using algebraic or geometric methods.

3. Why is it important to prove that a set is convex?

Proving that a set is convex is important because it can help us determine the properties and behaviors of the set. For example, convex sets have certain properties that can be useful in optimization problems and in understanding the solutions to certain equations.

4. What are some examples of convex sets?

Some examples of convex sets include circles, triangles, and rectangles. In general, any "smooth" shape without any dents or indentations can be considered a convex set.

5. Can a set be both convex and concave?

No, a set cannot be both convex and concave. A convex set is defined as a set where the line segment connecting any two points in the set also lies within the set, while a concave set is defined as a set where the line segment connecting any two points in the set lies outside the set. These two definitions are mutually exclusive, so a set cannot be both convex and concave.

Similar threads

  • Topology and Analysis
Replies
3
Views
2K
  • Topology and Analysis
Replies
3
Views
1K
Replies
4
Views
2K
Replies
4
Views
1K
Replies
5
Views
523
  • Topology and Analysis
Replies
2
Views
1K
  • Topology and Analysis
Replies
3
Views
2K
Replies
32
Views
2K
  • Topology and Analysis
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Back
Top