How to prove the convexity of this set by the definition of convex set?

482 Views Asked by At

In the exercise 2.12(g) of Convex Optimization by Stephen Boyd and Lieven Vandenberghe, a set is defined as follows:


(g) The set of points whose distance to $a$ does not exceed a fixed fraction $\theta$ of the distance to $b$, i.e., the set $\left\{x \mid\|x-a\|_{2} \leq \theta\|x-b\|_{2}\right\} .$ You can assume $a \neq b$ and $0 \leq \theta \leq 1$.
(transcribed from screenshot)


The solution provided seems to prove the convexity from a geometric view. Is it possible to prove it by the definition of convex set

$$t x + (1−t) y \in S$$

with $t \in [0,1]$? And how? I tried to directly use the triangle inequality, but it seems not work and stuck at the final step.

1

There are 1 best solutions below

2
On

Hint

$||x-a||_2\le \theta||x-b||_2$ leads to $$x^Tx-2a^Tx+a^Ta\le \theta^2(x^Tx-2b^Tx+b^Tb)$$or $$(x-\underline c)^T(x-\underline c)\le d$$where $\underline c$ is a vector and $d$ is a constant, both depending on $a$, $b$ and $\theta$. You should have no problem to show that $(x-\underline c)^T(x-\underline c)\le d$ draws a convex set from both geometrical and non-geometrical points of view.