If $A$ is a symmetric positive definite matrix, show that $f(x) = x^TAx$ is convex.

Question

Let:

\begin{gather*} f: \mathbb{R}^n \to \mathbb{R}, \quad A \in \mathbb{R}^{n \times n}, b \in \mathbb{R}^n, x \in \mathbb{R}^n, c \in \mathbb{R} \\ f(x) = x^T A x + b^T x + c \\ \end{gather*}

If $A$ is symmetric positive definite, show that $f$ is convex.

The domain of $f$ is convex. Algebraically, it will suffice to show that for any $x,y \in \mathbb{R}^n$:

\begin{gather*} f(\alpha x + (1 - \alpha) y) \le \alpha f(x) + (1 - \alpha) f(y) \\ \end{gather*}

Expanding the left hand side:

\begin{align*} f(\alpha x + (1 - \alpha) y) = [\alpha x + (1 - \alpha) y]^T [\alpha A x + (1 - \alpha) A y] + b^T [\alpha x + (1 - \alpha) y] + c \\ \end{align*}

Expanding the right hand side:

\begin{gather*} \alpha f(x) + (1 - \alpha) f(y) = \alpha x^T A x + (1-\alpha) y^T A y + \alpha b^T x + (1-\alpha) b^T y + c \\ \end{gather*}

Consider the right hand minus the left-hand side. It will suffice to show that this expression is positive. The $b^T x$ and $c$ terms cancel out:

\begin{gather*} \alpha f(x) + (1 - \alpha) f(y) - f(\alpha x + (1 - \alpha) y) \\ = \alpha x^T A x + (1-\alpha) y^T A y - \alpha^2 x^T Ax - \alpha(1-\alpha) x^T Ay - \alpha(1-\alpha) y^T Ax - (1-\alpha)^2 y^T Ay \\ = (\alpha - \alpha^2) x^T A x + \alpha (1 - \alpha) y^T Ay - \alpha(1-\alpha) x^T Ay - \alpha(1-\alpha) y^T Ax \\ \end{gather*}

When $A$ is symmetric, this simplifies slightly:

\begin{gather*} = (\alpha - \alpha^2) x^T A x + \alpha (1 - \alpha) y^T Ay - 2\alpha(1-\alpha) x^T Ay \\ \end{gather*}

Obviously, if $A$ is positive definite, than the first two terms in that expression are positive. However, the third term, $- 2\alpha(1-\alpha) x^T Ay$ seems to be either positive or negative.

Is there a simpler way to demonstrate that $f$ is convex?

Answer 1

What if you were to use

$$(y-x)^{\top}A(y-x) > 0$$ $$\implies y^{\top}Ay + x^{\top}Ax > y^{\top}Ax + x^{\top}Ay$$ $$\implies y^{\top}Ay + x^{\top}Ax > 2y^{\top}Ax$$ $$\implies (1-\alpha)\alpha y^{\top}Ay + (1-\alpha)\alpha x^{\top}Ax > 2(1-\alpha)\alpha y^{\top}Ax.$$

[The fact that $A$ is positive definite gives $(y-x)^{\top}A(y-x)>0$ and the fact that $A$ is symmetric implies $x^{\top}Ay = y^{\top}Ax$.]

Answer 2

It is sufficient to show that $f$ is convex on any segment $[x,y]$ with $x,y \in \mathbb{R}^n$. Let $\phi(t) = f(x+t(y-x))$ and note that $\phi''(t) = 2(y-x)^T A (y-x) \ge 0$ and so $\phi$ (and hence $f$) is convex.