Show that $\sqrt{x^TQx+1}$ is convex for positive definite $Q$

Question

If $Q\in\mathbb{R}^{n\times n}$ is positive definite, then show that $f(x) = \sqrt{x^TQx+1}$ is convex over $\mathbb{R}^n$. My first idea was to rewrite $f$ to be \begin{align*} f(x) &= \sqrt{x^T\left(Q+(x^Tx)^{-1}\right)x}\\ &= \sqrt{x^T L_xL^T_xx}\\ &=\sqrt{\| L^T_x x\|^2}\\ &= \| L^T_x x\|, \end{align*} where $L^T_xL_x$ is the Cholesky decomposition of $\left(Q+(x^Tx)^{-1}\right)$. It doesn't seem clear to me that the last term, $\| L^T_x x\|$, is in fact convex.

Is there an explanation to this or another way to do it?

Thanks

Answer 1

Here is a easy way to show the convexity by using convex function composition rules.

$\Vert x \Vert_2$ is obviously convex.

$\sqrt{x^2+1}$ is an composition of $\Vert x \Vert_2$ of dimension 2 and an affine transformation of $$ g(x) = \left[\array{x_1 \\ 1}\right] = \left( \array{1 \quad 0 \\0\quad 0} \right)\left[\array{x_1 \\ x_2}\right] + \left[\array{0 \\ 1}\right].$$ Hence $\sqrt{x^2+1}$ is convex (If you want, you can use the second derivative to verify its convexity as well. I am trying to minimize mathematical manipulations here.)

$\sqrt{x^TQx} \equiv \Vert x \Vert_Q$ is a form of norm. Hence it is convex.

Further note $\sqrt{x^2+1}$ is an increasing function of $x$ for $x\ge0$. By the composition rule $\sqrt{{(\sqrt{x^TQx})}^2+1} = \sqrt{x^TQx+1}$ is convex.

Note if you are not convince that $\sqrt{x^TQx} \equiv \Vert x \Vert_Q$ is convex, then you can convince yourself by noting $\Vert x\Vert_2$ is convex, and its composition with an affine transformation $g(x)=\sqrt{\Lambda}Ux$ should also be convex where $Q=U^T\Lambda U$, $\Lambda$ is a diagonal matrix with positive entries since $Q$ is positive definite.

Answer 2

As $Q$ is positive-definite, $x_2^\top Q x_1$ is an inner-product on $\mathbb R^n$. Let's denote this inner product by $\langle.,.\rangle_Q$ and the associated norm by $\|.\|_Q$. Suppose $f$ is not convex. $\exists x_1,x_2\in\mathbb R^n$ and $t\in(0,1)$ such that, \begin{align} &f(tx_1+(1-t)x_2) > tf(x_1)+(1-t)f(x_2)\\ \implies& f(tx_1+(1-t)x_2)^2 > t^2f(x_1)^2+(1-t)^2f(x_2)^2+2t(1-t)f(x_1)f(x_2)\\ \implies&(tx_1+(1-t)x_2)^\top Q(tx_1+(1-t)x_2)+1>t^2f(x_1)^2+(1-t)^2f(x_2)^2+2t(1-t)f(x_1)f(x_2)\\ \implies& t(1-t)(x_2^\top Qx_1+x_1^\top Qx_2)+1>t^2+(1-t)^2+2t(1-t)f(x_1)f(x_2)\\ \implies&2t(1-t)x_2^\top Qx_1>2t(t-1)+2t(1-t)f(x_1)f(x_2)\qquad(\because x_2^\top Qx_1=x_1^\top Qx_2)\\ \implies& x_2^\top Qx_1>-1+f(x_1)f(x_2)\\ \implies& x_2^\top Qx_1 +1> \sqrt{x_1^\top Qx_1+x_2^\top Qx_2+ \color{}{x_1^\top Qx_1x_2^\top Qx_2}+1}\\ \implies& 2x_2^\top Qx_1 +\langle x_2,x_1\rangle^2_Q> \|x_1\|_Q^2 +\|x_2\|_Q^2+ \|x_1\|_Q^2\|x_2\|_Q^2\quad(\text{squaring and using our notation})\\ \implies& 2x_2^\top Qx_1>\|x_1\|_Q^2 +\|x_2\|_Q^2 \qquad(\text{by Cauchy-Schwarz})\\ \implies& (x_2^\top Qx_1-x_2^\top Qx_2)+(x_1^\top Qx_2-x^\top Qx_1)>0\qquad(\because x_2^\top Qx_1=x_1^\top Qx_2)\\ \implies& x_2^\top Q(x_1-x_2)-x_1^\top Q(x_1-x_2)>0\\ \implies& (x_2-x_1)^\top Q(x_1-x_2)>0\\ \implies& (x_1-x_2)^\top Q(x_1-x_2)<0 \end{align} which contradicts positive-definiteness of $Q$.