Why does this function describe a Euclidean ball?

226 Views Asked by At

On page 97 of Boyd & Vandenberghe's Convex Optimization, one can read the following.

$$ a,b \in R^n $$ $$ (1-\alpha^2)x^Tx-2(a-\alpha^2b)^Tx+a^Ta-\alpha^2b^Tb \leq 0 $$ is convex (in fact a euclidian ball) if $ \alpha \leq 1 $.

I tried to write it in the form $ (x-c)^T(x-c) \leq r^2 $ but I didn't succeed. How can we show that this is a euclidean ball under such condition?

1

There are 1 best solutions below

3
On BEST ANSWER

As I said in the comments, it is necessary to have $|\alpha|<1$ in order to get an euclidean ball. For $|\alpha| = 1$ the LHS describes a plane, and the inequality describes all the points on one side of this plane.

If you choose $$\boxed{c := \frac{a-\alpha^2 b}{1-\alpha^2}}$$ (which is the only obvious choice for $c$ here) it works out:

$(x-c)^t(x-c) = x^t -2c^tx+c^tc = x^tx-\frac{(a-\alpha^2b)^t x}{1-\alpha^2}+\frac{1}{(1-\alpha^2)^2} [a^ta-2\alpha^2a^tb+\alpha^4b^tb] \leq r^2 \tag{1}$

Now you need to choose $r$ such that

$\frac{1}{(1-\alpha^2)^2} [a^ta-2\alpha^2a^tb+\alpha^4b^tb] - r^2 = \frac{a^ta-\alpha^2 b^t b}{1-\alpha^2} \tag{2}$

Which is equivalent to

$\begin{align*} [a^ta-2\alpha^2a^tb+\alpha^4b^tb] - (1-\alpha^2)^2r^2 &= (1-\alpha^2)(a^ta-\alpha^2 b^t b) \\ &=a^ta-\alpha^2a^ta-\alpha^2b^tb+\alpha^4b^tb \end{align*}\tag{3}$

If you substract The RHS and add $(1-\alpha^2)r^2$ then the above is equivalent to

$(1-\alpha^2)r^2= -2\alpha^2 a^t b + \alpha^2 a^t a + \alpha^2 b^tb = \alpha^2(a-b)^t(a-b)$ which you now can easily solve for $r$.

$$\boxed{r:= \frac{\alpha\Vert a-b\Vert}{\sqrt{1-\alpha^2}}}$$

With these choices for $r$ and $c$ your equation is equivalent to

$$\boxed{(x-c)^t(x-c) \leq r^2}$$

Here a quick gif for $n=2$ and $a = \color{red}{\bullet}$ and $b=\color{blue}{\bullet}$ as $\alpha$ goes from $0$ to $1$.

enter image description here