In example 3.33 of Boyd & Vandenberghe's Convex Optimization, a proof of the convexity of a half-space (Euclidean ball when $\alpha \le 1$) is presented. I understand we can expand out the $2$-norm and square both sides. But I am not sure what is the "rearranging" that's being done here.
I have found another question that is very similar, Why this function describes a euclidean ball? After reading through it and trying it out myself, I am still not sure how did the equivalency came to be. If anyone could give me any pointers,it would be much appreciated. Thank you in advance.
Editing my question to be more specific:
When we square both sides and multiply out each squared terms, the squared terms will be cancelled out e.g., $x^2_1, x^2_2, \dots, x^2_n$. So all that's left over are the constant terms and the linearly scaled terms. I am unclear how did we get the transposed terms shown in the picture and overall how did we end with those terms.
Best Answer
(1) That example doesn't show that the halfspace is convex ; rather it tries to show that $f$ is quasi-convex by showing that any sub-level set of $f$ is convex. ($f$ is quasi-convex iff every sub level set is convex)
(2) Now the rearrangement. First using simple vector algebra, you can show the following: \begin{align*} || a - b||_2^2 :&= (a - b)^T \cdot (a - b) \\ &= a^Ta + b^Tb - 2b^Ta \end{align*} Use this in your equations to get: \begin{align*} || x - a ||_2 &\le \alpha || x - b ||_2 \\ \Rightarrow || x - a ||^2_2 &\le \alpha^2 || x - b ||^2_2 \\ \Rightarrow x^Tx + a^Ta - 2a^Tx &\le \alpha^2 (x^Tx + b^Tb - 2b^Tx ) \\ \Rightarrow (1 - \alpha^2) x^Tx - &2(a - \alpha^2 b )^Tx + (a^Ta - \alpha^2 b^Tb) \le 0\\ \end{align*}
(3) Now you just need to check that is the equation of a L2 ball. In general consider an equation of the form $x^Tx - 2b^Tx + c \le 0$. \begin{align*} x^Tx - 2b^Tx + c &\le 0 \\ x^Tx - 2b^Tx + b^Tb &\le b^Tb - c \\ ||(x - b)||_2^2 &\le b^Tb - c \end{align*} So the equation $x^Tx - 2b^Tx + c \le 0$ represents a ball if $b^Tb - c \ge 0$, else it is an empty set. In either case, the set is convex.
(4) So in your original derived set, just divide throughout by $(1 - \alpha^2)$ to get an equation of the form in (3), and you can conclude it is a ball .... but wait, there's a case the book hasn't considered, check for the case $\alpha = 1$ separately, as it is not a ball in this case, but it is still convex ... check this yourself.