# Proving that a quadratic form is convex

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!!!

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.

• So good! it's a pity that I can't verify it Mar 9, 2022 at 1:14

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.

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}

• In the last equality of ´´Note that´´ I don´t undersand the term $2\alpha(1-\alpha)x´Qy$. Where are $\alpha (1-\alpha)x´Qy$ and $\alpha(1-\alpha)y´Qx$? Is $x´Qy = y´Qx$ because of symmetry?
– user561334
Sep 2, 2018 at 23:53

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.