Prove that if $f(x)=x^TQx$ is convex then $Q$ is positive semidefinite 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?
 A: 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$.
A: 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.$$
