For which value of $\mu$, is the region $\lVert x - a \rVert \leq \mu \lVert x-b \rVert$ convex? Give a proof.

Question

I tried taking two points such as $x_1$ and $x_2$ that are in the set (so, by definition, they satisfy the set condition) and tried to show that $z = (\lambda) x_1 + (1 - \lambda) x_2$, also satisfies the set condition for any $\lambda \in \left(0, 1 \right)$. So I tried to show that $$ \lVert (\lambda) x_1 + (1 - \lambda) x_2 - a \rVert \leq \mu \lVert (\lambda) x_1 + (1 - \lambda) x_2-b \rVert $$ given that $$ \lVert x_1 - a \rVert \leq \mu \lVert x_1-b \rVert $$ $$ \lVert x_2 - a \rVert \leq \mu \lVert x_2-b \rVert $$

in my attempt I took $a = \lambda a + (1 - \lambda) a$, so $$ \lVert (\lambda) x_1 + (1 - \lambda) x_2 - \lambda a - (1 - \lambda) a \rVert = \lVert (\lambda) (x_1 - a) + (1 - \lambda) (x_2 - a) \rVert $$ then by the triangle inequality $$(\lVert (\lambda) (x_1 - a) + (1 - \lambda) (x_2 - a) \rVert \leq \lambda \lVert x_1 - a \rVert + (1 - \lambda) \lVert x_2 - a \rVert)$$ we have: $$ \lVert (\lambda) x_1 + (1 - \lambda) x_2 - a\rVert \leq \lambda \lVert x_1 - a \rVert + (1 - \lambda) \lVert x_2 - a \rVert \leq \mu (\lambda \lVert x_1 - b \rVert + (1 - \lambda) \lVert x_2-b \rVert) \nless \mu \lVert (\lambda) x_1 + (1 - \lambda) x_2-b \rVert $$ in which the last inequality resulted from the assumption that $x_1$ and $x_2$ are in the mentioned set.

As you can see, in the end, I fell short of proving the desired result. Can you help me?

Answer 1

Certainly, if $\mu < 0$, then the given set is empty and therefore vacuously convex -- unless $a=b$, in which case the set is the singleton $\{ a \}$ which is also convex. In the case $\mu \ge 0$, since both sides of the inequality are nonnegative; therefore, the inequality is equivalent to $\lVert x-a \rVert^2 \le \mu^2 \lVert x-b \rVert^2$, or $$(1 - \mu^2) x \cdot x + x \cdot v + \beta \le 0,$$ where $v = -2a + 2 \mu^2 b$ and $\beta = \lVert a \rVert^2 - \mu^2 \lVert b \rVert^2$.

Now if $\mu \in [0, 1)$, so that $1 - \mu^2 > 0$, then we can complete the square to show this is further equivalent to an inequality of the form $$\left\lVert x - \frac{v}{2(1-\mu^2)}\right\rVert^2 \le \gamma$$ for some scalar $\gamma$. The set of $x$ satisfying this inequality is either empty (if $\gamma < 0$); a singleton (if $\gamma = 0$); or a closed ball (if $\gamma > 0$). In any of these cases, the set is therefore convex.

Similarly, if $\mu = 1$, then the inequality reduces to a linear inequality $x \cdot v + \beta \le 0$. This is either the whole space (if $v = 0$) or a half-space (if $v \ne 0$); and in either case, the set is convex.

On the other hand, if $\mu > 1$, then similarly to the above, we can show the inequality is equivalent to $$\left\lVert x + \frac{v}{2(\mu^2-1)} \right\rVert^2 \ge \gamma$$ for some scalar $\gamma$. The only way this set can be convex is if $\gamma \le 0$. It should turn out if you do some more explicit calculations that the only way this can happen is if $a=b$, in which case $\gamma = 0$.

---

As another way of putting the case $\mu \in [0, 1]$, you can observe that $x \mapsto \lVert x-a\rVert^2 - \mu^2 \lVert x-b \rVert^2 = (1 - \mu^2) x \cdot x + x \cdot v + \beta$ is a convex function; therefore, the inverse image of the interval $(-\infty, 0]$ under this convex function must be a convex set.

On the other hand, if $\mu > 1$ and $a\ne b$, then the function $\lVert x-a \rVert^2 - \mu^2 \lVert x-b \rVert^2$ is strictly positive for $x = b$, while its value on $ta + (1-t) b$ goes to $-\infty$ as $t \to \pm \infty$. Therefore, the inverse image of $(-\infty, 0]$ cannot be convex since it includes points $ta + (1-t)b$ for large $t$ and for negations of large $t$, but it does not contain the point $b$ which is a convex combination of those points.

Answer 2

Hint: $$ \| x- a\| \le \mu \| x- b\| $$ is equivalent to $$ \| x- a\|^2 \le \mu^2 \| x- b\|^2. $$