Prove the convexity of $f(x) = \sqrt{x^T Qx + 1}$ over $\mathbb R^n$, with $Q \succcurlyeq 0$

Question

As the title says, the problem I'm trying to solve gives that $Q \succcurlyeq 0$, but it doesn't seem to indicate that $Q$ is necessarily symmetric. So far I've tried

• proving from the definition of convexity, which got me a monstrous expression which I did not manage to simplify
• attempting to show $f$ is a norm (that went nowhere)
• finding the Hessian (I did not get very far on this, as I wasn't sure how to properly derive and the just finding the gradient was difficult)

The fact that the function is of a vector, not a scalar is only complicating things. Any insight, strategies, or solutions to solve this problem? I'm totally puzzled!

Answer 1

Here is shorter proof. Since $f(x) = ||Ax + b||$ with $$A = \begin{pmatrix}Q^{1/2} \\ \bf{0}^T \end{pmatrix} \text{ and } b = \begin{pmatrix} \bf{0} \\ 1 \end{pmatrix},$$ which is just a convex function evaluated in an affine transformation of $x$, $f$ is convex. Here, $Q^{1/2}$ is the cholesky factor of $Q$.

Answer 2

As rightly stated in the comment by user9527, I assume that $Q = (q_{ij})_{i,j}$ is symmetric or $Q \geq 0$ does not make sense. First observe that $\langle x, y \rangle := x^T Qy$ is an inner product on $\mathbb{R}^n$, and hence we have the Cauchy-Schwarz inequality $$ \langle x, y \rangle^2 \leq (x^TQx)(y^TQy).$$

Then we compute the Hessian. $$f(x) = \sqrt{\sum_{i,j} q_{ij}x_ix_j + 1}$$ $$\frac{\partial f}{\partial x_k} (x)= \frac{1}{2 f(x)} \sum_j (q_{jk} + q_{kj}) x_j = \frac{1}{f(x)} (Qx)_k$$ $$\frac{\partial f}{\partial x_k \partial x_m} (x)= -\frac{1}{f(x)^3} (Qx)_k (Qx)_m + \frac{1}{f(x)} q_{km}$$ $$y^T H_f(x) y = \frac{1}{f(x)^3} \left( f(x)^2 \sum_{k,m} q_{km} y_ky_m - \sum_{k,m} (Qx)_k(Qx)_my_ky_m\right) = \frac{1}{f(x)^3} \left( f(x)^2 y^TQy - (y^T Qx)^2\right).$$

Using the fact that $f(x)^2 = x^TQ x + 1 \geq x^T Q x$, and the Cauchy-Schwarz inequality, we get $$y^T H_f(x) y \geq \frac{1}{f(x)^3} \left[(x^T Q x) (y^TQy) - (y^T Qx)^2\right] \geq 0.$$