Proving convexity of quadratic form using the definition of symmetric positive semidefinite

Question

I have $f(\boldsymbol{x}) = \boldsymbol{x}^{\boldsymbol{T}} \boldsymbol{Q} \boldsymbol{x}$, where $\boldsymbol{Q}$ is an $n \times n$ symmetric positive semidefinite matrix.

How can I show that $f(\boldsymbol{x})$ is convex on the domain $R^n$?

---

Attempt:

By definition of convex, for any $x,y\in\mathbb R$, we have $$f(\frac{x+y}2)\leq\frac12(f(x)+f(y))$$ Thus it is sufficient to reduce and prove that $$\frac12(x+y)^TQ(x+y)\leq x^TQx+y^TQy\\ x^TQy+y^TQx\leq x^TQx+y^TQy$$ Namely $$(x-y)^TQ(x-y)\geq0$$

At this point I am stuck on how to use positive semi-definite - assuming my logic is sound up to this point.

Answer 1

(a) For $\;f:\mathbb{R}\to \mathbb{R}$, $\;f(x)=x^2$ we verify that $f$ is convex. In fact, $$(\alpha x+(1-\alpha )y)^2\leq \alpha x^2+(1-\alpha)y^2 \Leftrightarrow\\ \alpha^2x^2+2\alpha (1-\alpha)xy+(1-\alpha)^2y^2-\alpha x^2-(1-\alpha)y^2\leq 0\Leftrightarrow\\(\alpha^2-\alpha)x^2+(\alpha^2-\alpha)y^2+ 2(\alpha^2-\alpha)xy\leq 0\Leftrightarrow\\ (\alpha^2-\alpha)(x+y)^2\leq 0.$$ The last inequality is verified because $\alpha^2-\alpha \leq 0$ for all $\alpha\in [0,1]$. That is, $$f(\alpha x+(1-\alpha )y)\leq \alpha f(x)+(1-\alpha)f(y)\quad \forall{x,y}\in{V},\; \forall{\alpha }\in{[0,1]}.$$ and $f$ is a convex function.

(b) For $\;f(\boldsymbol{x}) = \boldsymbol{x}^{\boldsymbol{T}} \boldsymbol{Q} \boldsymbol{x}\;$ with $\;\boldsymbol{Q}\;$ positive semidefinite, we can express $$f(\boldsymbol{x}) = \boldsymbol{x}^{\boldsymbol{T}} \boldsymbol{Q} \boldsymbol{x}=\boldsymbol{(\boldsymbol{P}x})^{\boldsymbol{T}} \boldsymbol{D} (\boldsymbol{P}\boldsymbol{x})=x_1^2+\cdots+x_r^2$$ and apply (a).

Answer 2

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.