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

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!

• By the common definition, $Q \succeq 0$ automatically assumes $Q$ is symmetric. – user1101010 Oct 16 '18 at 19:37
• Oh, really? That means that I can take $x^T Qy$ to equal $y^T Qx$, right? I will keep trying using this information, although I'm still stuck for the moment. – Craveable Banana Oct 16 '18 at 19:46
• even if $Q$ is not symmetric, $x^TQx = 0.5 x^T(Q+Q^T)x$ – LinAlg Oct 16 '18 at 22:03

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$$.
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.$$