Show convexity of quadratic function

Question

Can someone show the following function is convex using the definition (without taking gradient)?

$$F(x)= \frac12 x^T Q x + c^T x$$

where matrix $Q$ is symmetric positive definite.

Answer 1

The easiest way to show the convexity of your function is via the Hessian: $\nabla^2 F(x) = 2Q$, which is positive semidefinite as per your assumption. To use the definition of convexity, let $x,y\in\mathbb{R}^n$ and $\alpha\in[0,1]$. Then \begin{align*} F(\alpha x + (1-\alpha)y) ={}& (\alpha x + (1-\alpha)y)^\top Q((\alpha x + (1-\alpha)y)) \\ ={}& \alpha^2 x^\top Q x + 2\alpha(1-\alpha)x^\top Q y + (1-\alpha)^2 y^\top Qy \\ ={}& \alpha^2 x^\top Qx + 2\alpha x^\top Q y - 2\alpha^2 x^\top Qy + y^\top Qy - 2\alpha y^\top Qy + \alpha^2 y^\top Q y \\ ={}& \alpha F(x) + (1-\alpha)F(y) -\alpha x^\top Qx - (1-\alpha) y^\top Q y \\ &{} + \alpha^2 x^\top Qx + 2\alpha x^\top Q y - 2\alpha^2 x^\top Qy + y^\top Qy - 2\alpha y^\top Qy + \alpha^2 y^\top Q y \\ ={}& \alpha F(x) + (1-\alpha)F(y) \\ &{} +\alpha^2 x^\top Qx - \alpha x^\top Q x + \alpha^2 y^\top Q y - \alpha y^\top Q y -2\alpha^2 x^\top Qy + 2\alpha x^\top Q y \\ ={}& \alpha F(x) + (1-\alpha)F(y) + \alpha(\alpha-1) (x^\top Q x + y^\top Q y - 2 x^\top Q y) \\ ={}& \alpha F(x) + (1-\alpha)F(y) + \alpha(\alpha-1) (x-y) ^\top Q(x-y). \end{align*} Since $0 \le \alpha\le 1$, we have that $\alpha(\alpha-1)\le 0$. Therefore, by the positive semidefiniteness of $Q$, we find that \begin{equation*} F(\alpha x + (1-\alpha)y) \le \alpha F(x) + (1-\alpha)F(y). \end{equation*}

Answer 2

Convexity of a function is equivalent to being convex on intervals $[x,y]$.

If $f,g$ are convex, it is straightforward to show that $f+g$ is convex.

The map $x \mapsto c^T x$ is linear hence convex.

Let $q(x) = {1 \over 2}x^T Qx$, if we can show that this is convex then it follows that $f$ is convex.

Pick $x,y$ and let $\phi(t) = q(x+t(y-x)) = q(x)+t^2 q(y-x) +tx^TQy$.

Since the function $t \mapsto q(x)+tx^TQy$ is affine (hence convex) and $q(y-x) \ge 0$ (this is where positive semi definiteness is used), this reduces to showing that $t \mapsto t^2$ is convex.

Since $(ta+(1-t)b)^2 - (t a^2 +(1-t)b^2) = -(b-a)^2t (1-t)$, we see that $t \mapsto t^2$ is convex.

No derivatives were hurt in the making of this answer.