3
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ 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}$$ ? $\endgroup$ – Mattos Feb 22 at 14:00
  • $\begingroup$ 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 $\endgroup$ – Pontus S Feb 22 at 14:17
  • $\begingroup$ @PontusS the further step that you are talking about is not valid, you have to prove this in a different way. $\endgroup$ – TenaliRaman Feb 22 at 14:18
  • $\begingroup$ 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 $\endgroup$ – Pontus S Feb 22 at 14:21
  • 1
    $\begingroup$ @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? $\endgroup$ – Pontus S Feb 22 at 14:41
4
$\begingroup$

$$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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Pontus S Feb 22 at 14:28
  • $\begingroup$ @PontusS Is $S$ arbitrary? I think that if it is not convex this is not true. $\endgroup$ – lightxbulb Feb 22 at 14:28
  • $\begingroup$ yes $S \subseteq \mathbb{R}^n$ $\endgroup$ – Pontus S Feb 22 at 14:30
  • $\begingroup$ 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! $\endgroup$ – Pontus S Feb 22 at 14:48
  • $\begingroup$ @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. $\endgroup$ – lightxbulb Feb 22 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.