How to obtain a concave surrogate function for $\|\textbf{x}\|^2$ for a given $\|\textbf{x}_0\|$

Question

In one of the paper I have seen that $\|\textbf{x}\|^2$ is lower bounded by the following concave surrogate function $$\|\textbf{x}\|^2\geq -\|\textbf{x}\|^2+2\textbf{x}_0^{T}\left(2\textbf{x}-\textbf{x}_0\right)$$ But I do not have any idea how to obtain the right hand side. Although I can obtain the first order Taylor expansion but I do not know how to obtain the above surrogate function. Any help in this regard will be much appreciated. Thanks in advance.

Answer 1

The first term on the right should be $-||x_0||^{2}$. Now $||x-x_0||^{2} =||x||^{2}+||x_0||^{2} -2 \langle x,x_0 \rangle $. Since $||x-x_0||^{2} \geq 0$ this gives $||x||^{2} \geq -||x_0||^{2}+2 \langle x,x_0 \rangle$. Now $2\langle x,x_0 \rangle =\langle x_0,2x-x_0 \rangle +||x_0||^{2} \geq \langle x_0,2x-x_0 \rangle$ which gives the required inequality.