# Proof of convexity from definition ($x^Tx$)

I have to prove that function $f(x) = x^Tx, x \in R^n$ is convex from definition.

Definition: Function $f: R^n \rightarrow R$ is convex over set $X \subseteq dom(f)$ if $X$ is convex and the following holds: $x,y \in X, 0 \leq \alpha \leq 1 \rightarrow f(\alpha x+(1-\alpha) y)) \leq \alpha f(x) + (1-\alpha)f(y)$.

I got this so far:

$(\alpha x + (1-\alpha)y)^T(\alpha x + (1-\alpha)y) \leq \alpha x^Tx + (1-\alpha)y^Ty$

$\alpha^2 x^Tx + 2\alpha(1-\alpha)x^Ty + (1-\alpha)^2y^Ty \leq \alpha x^Tx + (1-\alpha)y^Ty$

I don´t know how to prove this inequality. It is clear to me, that $\alpha^2 x^Tx \leq \alpha x^Tx$ and $(1-\alpha)^2y^Ty \leq (1-\alpha)y^Ty$, since $0 \leq\alpha \leq 1$, but what about $2\alpha(1-\alpha)x^Ty$?

I have to prove this using the above definition.

Note: In Czech, the words "convex" and "concave" may have opposite meaning as in some other languages ($x^2$ is a convex function for me!). Thanks for any help.

-

Typically you use Cauchy-Schwarz in these situations.

$$(\alpha x + (1-\alpha)y)^T(\alpha x + (1-\alpha)y)=\alpha^2x^Tx+(1-\alpha)^2y^Ty+2\alpha(1-\alpha)x^Ty\leq\alpha^2x^Tx+(1-\alpha)^2y^Ty+2\alpha(1-\alpha)(x^Tx)^{1/2}(y^Ty)^{1/2}=(\alpha (x^Tx)^{1/2}+(1-\alpha)(y^Ty)^{1/2})^2\\ \leq\alpha x^Tx+(1-\alpha)y^Ty,$$ where the last inequality is the convexity of the scalar function $t\mapsto t^2$.

-
Could you, please, explain the last step? I thought that Cauchy-Schwartz would give $(\sum \sqrt{a_i})^2 \le n \sum a_i$ –  trembik Aug 27 '14 at 14:16
The last step is not Cauchy-Schwarz (which was used in the first inequality: $x^Ty\leq(x^Tx)^{1/2}(y^Ty)^{1/2}$), but the convexity of the square function: $$(\alpha t+(1-\alpha)s)^2\leq\alpha t^2+(1-\alpha)s^2,$$ for $\alpha\in[0,1]$. This expresses the fact that the function $t\mapsto t^2$ is convex (i.e. the curve joining two points lies below the line segment joining them; this is exactly what the inequality expresses). –  Martin Argerami Aug 27 '14 at 16:39

You have $$\alpha^2 x^Tx + 2\alpha(1-\alpha)x^Ty + (1-\alpha)^2y^Ty \leq \alpha x^Tx + (1-\alpha)y^Ty$$

or equivalently $$\alpha(\alpha-1) x^Tx + 2\alpha(1-\alpha)x^Ty + (1-\alpha)(1-\alpha-1)y^Ty \leq 0$$

or equivalently

$$x^Tx - 2x^Ty + y^Ty \leq 0$$

Can you conclude from here?

-
$\alpha(1 - \alpha) \geq 0$, so the inequality will flip in the last step. –  Isomorphism Dec 15 '12 at 18:00

$g(x) = \sqrt{x^Tx}$ is convex due to triangle inequality. And $h(x) = x^2$ is convex (one of the ways to see this is to use calculus).

$f(x) = h(g(x))$ and both of $h$ and $g$ are convex.

-
This is clear to me. However, this is not a proof from my definition... –  Smajl Dec 15 '12 at 17:59
to proceed from your steps, bring everything to the right hand side in the last but one step and get $\alpha(1 - \alpha) (||x - y||^2) \geq 0$ which is true. This is what Tomas did (almost). –  Isomorphism Dec 15 '12 at 18:04