3

This question is about proving the convexity of a set using triangular inequality. However, I'm missing something as I can't wrap it up. The task is to prove that the set below is convex where $\|\cdot\|_2$ denotes the two-norm

$$M = \{x | \quad \|x-x_0\|_2 \leq \|x-y\|_2 \quad\forall y \in S \}$$

What I've done is start with two points $x_1$, $x_2$ $\in M$. Using the triangle inequality, I tried to prove that all points between these arbitrary points are contained within the set as shown below

\begin{align} \|\theta x_1 + (1- \theta)x_2-x_0\|_2 &= \|\theta ( x_1 - x_0) + (1- \theta)(x_2-x_0)\|_2 \\ &\leq \theta \|x_1-x_0\|_2 + (1- \theta) \|x_2 -x_0\|_2 \\ &\leq \theta \|x_1 -y\|_2 + (1-\theta) \|x_2 -y\|_2 \quad \forall y \in S \end{align}

However, the problem is I don't think that I'm allowed to use the triangle inequality on the equation at the far right-hand side, because I cannot guarantee that it's necessarily true as the right-hand side might not be bigger than the left-hand side anymore (as can be seen below)

$$\|\theta x_1 + (1- \theta)x_2-x_0\|_2 \leq \|\theta x_1 + (1-\theta) x_2 -y\|_2 \quad \forall y \in S$$

However, the solution makes sense in the manner that any point on the line between $x_1$ and $x_2$ (call it $x_i$) is upper bounded by itself as shown in the equation below. Which is exactly what I want to prove but I'm afraid I've jumped to an invalid conclusion.

$$M = \{x| \quad \|x_i-x_0\|_2 \leq \|x_i-y\|_2 \quad \forall y \in S \}$$

Can anyone give me a peak?

EDIT below to clarify: The question is in short:

I've proven that the below statement holds. But that doesn't prove the set is convex as far as i know since the upper bound is not equal to $\|x-y\|_2$ \begin{align} \|\theta x_1 + (1- \theta)x_2-x_0\|_2 \leq \theta \|x_1 -y\|_2 + (1-\theta) \|x_2 -y\|_2 \quad \forall y \in S \end{align}

However, if I simplify the equations right-hand side with triangular inequality I get the equation below which makes sense but I'm not sure that it's correct. Because triangle inequality states that $\|A+B\| \leq \|A\| + \|B\|$. Which means that I'm not sure if I can guarantee that the below statement holds. So my question is in short: Can I use triangular inequality on the right-hand side of the equation above to gain the equation below and still be sure that the equality holds?

$$\|\theta x_1 + (1- \theta)x_2-x_0\|_2\; (\leq)? \; \|\theta x_1 + (1-\theta) x_2 -y\|_2 \quad \forall y \in S$$

Pontus S
  • 49
  • I've made some edits and done some typesetting for readability. I hope this is OK. Also, I'm not sure what/where the issue is? Are you asking whether $$x_{1}, x_{2} \in M \implies \theta | x_{1}-x_{0}|{2} + (1-\theta)|x{2}-x_{0}|{2} \le \theta | x{1}-y|{2} + (1-\theta)|x{2}-y|_{2}$$ ? – Matthew Cassell Feb 22 '19 at 14:00
  • The equation you have written i'm quite confident that it's true. However i'm not sure if the further simplifications are valid. I updated the question with a short summary at the end to clarify what i'm asking – Pontus S Feb 22 '19 at 14:17
  • @PontusS the further step that you are talking about is not valid, you have to prove this in a different way. – TenaliRaman Feb 22 '19 at 14:18
  • I suspected this although i've no clue as to what method i should use. The equation that @Mattos stated above doesn't seem to prove that the points between $x_1$ and $x_2$ are contained within the set. I might be wrong though as my skills are quite bad in this subject – Pontus S Feb 22 '19 at 14:21
  • $M$ seems to be singleton! – Sujit Bhattacharyya Feb 22 '19 at 14:27
  • 1
    @SujitBhattacharyya seems reasonable, but i'm not sure as to what mathematical simplifications i can make in order to prove this. $x_{1}, x_{2} \in M \implies \theta | x_{1}-x_{0}|{2} + (1-\theta)|x{2}-x_{0}|{2} \le \theta | x{1}-y|{2} + (1-\theta)|x{2}-y|_{2}$ $\forall y \in S$, $S \subseteq \mathbb{R}^n$

    Does this equation alone prove that it's singleton?

     – Pontus S Feb 22 '19 at 14:41

2 Answers2

4

$$M = \cap_{y \in S} M_y$$ where, $$M_y = \{x|\quad \|x - x_0\|_2 \leq \|x - y\|_2 \quad\}$$

We can try to show that $M_y$ is convex. Now, $$\|x - x_0\|_2 \leq \|x - y\|_2 \\ \Rightarrow \|x - x_0\|_2^2 \leq \|x - y\|_2^2 \\ \Rightarrow \|x\|_2^2 + \|x_0\|_2^2 - 2x_0^{\top}x \leq \|x\|_2^2 + \|y\|_2^2 - 2y^{\top}x \\ \Rightarrow (y - x_0)^{\top}x \leq \frac{1}{2} \left( \|y\|_2^2 - \|x_0\|_2^2 \right)$$

So, $M_y$ is a Half Space, which is a convex set (which is fairly easy to show as well).

Finally, $M$ is the intersection of convex sets which is also convex.

TenaliRaman
  • 3,846
2

Isn't $M$ simply the set of points closer to $x_0$ than any other point, thus $M=\{x_0\}$. Specifically if you pick $y=x$, then the inequality is satisfied only for $x=x_0$.

Needless to say the singleton set is convex.

lightxbulb
  • 2,047
  • The question seems to be $M$ is the set of points closer to the point $x_0$ than aa given set $S$. (I see i wrote wrong in the question now it's $y \in S$ and not $y \in \mathbb{R}^n$. Nedless of the intuitive explanation i'm looking for a mathematical way to prove that fact by using triangle inequality. – Pontus S Feb 22 '19 at 14:28
  • @PontusS Is $S$ arbitrary? I think that if it is not convex this is not true. – lightxbulb Feb 22 '19 at 14:28
  • yes $S \subseteq \mathbb{R}^n$ – Pontus S Feb 22 '19 at 14:30
  • Makes perfect sense, although it would be satisfying to know what could be done with the mentioned equations in order to prove this. But i'm happy with this explanation. Thanks! – Pontus S Feb 22 '19 at 14:48
  • @PontusS It is correct. I got to the part where I need to prove that if $z$ is a convex linear combination of $x_1, x_2$ then the ball with center $z$ and radius $d(z-x_0)$ is a subset of the union of the balls with centers $x_1, x_2$ and radii $d(x_1 - x_0), d(x_2-x_0)$. I can't say whether this statement is correct right off the bat. But if you can prove this, then the proof for convexity of $M$ is straightforward. The proof in the accepted answer is a lot more elegant though. – lightxbulb Feb 22 '19 at 15:45