Prove that if $f(x)=x^TQx$ is convex then $Q$ is positive semidefinite

Question

I have seen this question, and I would like to prove the converse, namely:

Prove that $Q$ is PSD given $f(x)=x^T Q x$ is convex.

Here is my attempt:

As seen in the linked quesiton:

$$f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha)f(y)\\ \Leftrightarrow -\alpha(1-\alpha)(x-y)^TQ(x-y)\leq 0$$

For the last inequality to be true, we have to ensure that $(x-y)^TQ(x-y)\geq0$ for all $z=x-y$. This is true only when $Q$ is positive semidefinite. Hence if $f$ is convex $Q$ is positive semidefinite.

Is this correct?

Answer 1

I think there is a much simpler argument. If the statement is true, then it is clear that $x = \underline{0}$ gives a global minimum. This gives us a possible approach. Note that $\forall x$,

$$0 = f(\underline{0}) \le \frac{1}{2}\bigg(f(x)+f(-x)\bigg) = f(x).$$

$$\implies x^TQx \ge 0.$$

Answer 2

You have the right idea, but the argument can be improved formally (and simplified). In order to show that $Q$ is positive semidefinite you have to start with a vector $z$ and show that $z^T Q z \ge 0$. It is correct that this can be done by using the equivalence $$ f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha)f(y)\\ \iff -\alpha(1-\alpha)(x-y)^TQ(x-y)\leq 0 $$ for some vectors $x, y$ such $z=x-y$, and some $\alpha \in (0, 1)$. A simple choice is $x=z$, $y = 0$, and $\alpha = 1/2$. Note also that the equivalence can be formulated as an identity: $$ f(\alpha x+(1-\alpha)y)- \alpha f(x)-(1-\alpha)f(y) \\= -\alpha(1-\alpha)(x-y)^TQ(x-y) \, . $$

---

That leads to the following proof: Assume that $f$ is convex. Then for every vector $z$ $$ 0 \le \frac{f(z)-f(0)}{2} - f\left( \frac z2 \right) = \frac 12 z^T Q z - \frac {z^T}2 Q \frac z2 = \frac 14 z^T Q z \, , $$ and that implies $z^T Q z \ge 0$.