Proving that a quadratic form is convex

Question

Suppose that $f(x) = x^{T}Qx$ where $Q$ is an $n \times n$ symmetric positive semidefinite matrix. Show that $f(x)$ is convex on the domain $\mathbb{R}^{n}$.

(Hint: It may be wise to prove the following equivalent property: $f(y + \alpha(x-y) ) - \alpha f(x) - (1-\alpha) f(y) \leq 0 $, for all $\alpha \in [0,1]$ and $x,y \in \mathbb{R}^{n}$).

What I have is the following:

$f(y + \alpha(x-y) ) = (y + \alpha(x-y))^{T}Q(y + \alpha(x-y)) = (y + \alpha(x-y))^{T}(Qy + \alpha Q(x-y).$

I am not sure what to do from here. Can someone give me some more hints on how to solve this?

Thank you very much!!!

Answer 1

Note that $(y+\alpha(x-y))'Q(y+\alpha(x-y)=(y(1-\alpha)+\alpha x)'Q(y(1-\alpha)+\alpha x)=(1-\alpha)^2y'Qy+\alpha^{2}x'Qx+2\alpha(1-\alpha)x'Qy$.

Hence $$\begin{aligned} &(y+\alpha(x-y))'Q(y+\alpha(x-y)-\alpha x'Qx-(1-\alpha)y'Qy=\\ &=y'Qy\cdot(1-\alpha)(-\alpha)+x'Qx\cdot\alpha(\alpha-1)+2x'Qy\cdot\alpha(1-\alpha)\\ &=-\alpha(1-\alpha)(y'Qy+x'Qx-2x'Qy)=-\alpha(1-\alpha)(x-y)'Q(x-y)\leq0. \end{aligned}$$

Answer 2

Here is an alternative proof. A function $f(x)$ is convex if and only if:

$$ f(x_1) - f(x_2) \geq (x_1 - x_2)^T \nabla f(x_2) $$

for all $x_1$ and $x_2$ in the domain. If $Q$ is symmetric and positive semidefinite, then there exists a matrix $P$ such that

$$Q = P^T P.$$

Now consider the vector $Px_1 - Px_2$. Its squared norm is obviously non-negative:

$$ \begin{align}||Px_1 - Px_2 ||^2 =&\ (Px_1 - Px_2)^T (Px_1 - Px_2) \\ =&\ \ x_1^T P^T Px_1 - 2x_1^TP^TPx_2+ x_2^T P^T Px_2\\ =&\ \ x_1^T Qx_1 - 2x_1^TQx_2+ x_2^T Qx_2\\ \geq &\ 0, \end{align}$$

which can be rewritten:

$$\begin{align} x_1^T Qx_1 - x_2^T Qx_2 \geq &\ 2x_1^TQx_2 - 2x_2^T Qx_2 \\=&\ (x_1 - x_2)^T 2Qx_2\end{align}.$$

But $f(x) = x^TQx \Rightarrow \nabla f(x) = 2Qx$. Therefore:

$$ f(x_1) - f(x_2) \geq (x_1 - x_2)^T \nabla f(x_2), $$

which finishes the proof.

Answer 3

You can also use the second derivative property. The Hessian is $2M$ and we know it's positive semi-definite since $M$ is. Thus we're done.

Answer 4

To make Jan's answer a bit more clearer, I will elaborate on some of the lines he wrote:

We have that $f(x)=x^TQx$, where $x,y\in\mathbb{R}^n$ and $Q\in\mathbb{n\times n}$ is symmetric positive semidefinite.

We want to show that $f(x)=x^TQx$ is convex using the fact that $Q$ is PSD, i.e., we want to show that $$f\left(\alpha x + (1-\alpha)y\right)\leq \alpha f(x)+(1-\alpha)f(y)$$ Where $\alpha\in[0,1]$.

So, we have the following:

$$f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha)f(y)\\ \Leftrightarrow (\alpha x+(1-\alpha)y)^TQ(\alpha x + (1-\alpha)y)\leq \alpha x^TQx +(1-\alpha)y^TQy\\ \Leftrightarrow (\alpha x^T + (1-\alpha)y^T)Q(\alpha x+(1-\alpha)y)\leq \alpha x^T Qx+(1-\alpha)y^TQy \\ \Leftrightarrow \alpha x^TQ(\alpha x +(1-\alpha) y)+(1-\alpha)y^TQ(\alpha x +(1-\alpha) y)\leq \alpha x^T Qx+(1-\alpha)y^TQy$$

Expanding the LHS:

$$\alpha x^TQ\alpha x+\alpha x^TQ(1-\alpha) y+(1-\alpha)y^TQ\alpha x+(1-\alpha)y^TQ(1-\alpha)y\leq \alpha x^T Qx+(1-\alpha)y^TQy \\ \Leftrightarrow \alpha^2 x^T Q x+\alpha (1-\alpha)x^TQy+\alpha (1-\alpha)y^TQx+(1-\alpha)^2y^TQy\leq \alpha x^T Qx+(1-\alpha)y^TQy$$

Now, the second and third term in the LHS are equal, since $x^TQy=(x^TQy)^T=y^TQx$ (I urge the reader to check this for themselves), hence the inequality becomes:

$$\alpha^2 x^T Q x+2\alpha (1-\alpha)x^TQy+(1-\alpha)^2y^TQy\leq \alpha x^T Qx+(1-\alpha)y^TQy$$

We now subtract the RHS from both sides, so the inequality becomes: $$\alpha^2 x^T Q x+2\alpha (1-\alpha)x^TQy+(1-\alpha)^2y^TQy-\alpha x^T Qx(1-\alpha)y^TQy\leq 0 \\ \Leftrightarrow (\alpha^2-\alpha)x^TQx+(1-\alpha)(1-\alpha-1)y^TQy + 2\alpha(1-\alpha)x^TQy \leq 0 \\ \Leftrightarrow -\alpha(1-\alpha)x^TQx-\alpha(1-\alpha)y^TQy+2\alpha (1-\alpha) x^TQy\leq 0\\ \Leftrightarrow -\alpha(1-\alpha)(y^TQy+x^TQx-2x^TQ y)\leq 0 $$

If you take a look at $(y^TQy+x^TQx-2x^TQ y)$, you will see that this is equal to $(x-y)^TQ(x-y)$,

since $(x-y)^TQ(x-y)=(x^T-y^T)Q(x-y)=x^TQx-x^TQy-y^TQx-y^TQy$

and again we use the fact that $x^TQy=(x^TQy)^T= y^TQx$,

to derive that $x^TQx-x^TQy-y^TQx-y^TQy=y^TQy+x^TQx-2x^TQ y$

So the above inequality becomes:

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

Since $Q$ is positive semidefinite, we have the $(x-y)^TQ(x-y)\geq 0$ for all $z=x-y\in \mathbb{R}^n$. Since $\alpha \leq 1 \Rightarrow (1-\alpha)\in [0,1]$ and hence $-\alpha(1-\alpha)\leq 0$. When you combine these, you get that the inequality is always true. Hence, $f(x)=x^T Qx$ is a convex function.