1
$\begingroup$

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.

4 Answers 4

3

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$.

  • 1
    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).2014-08-27
1

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?

  • 0
    $\alpha(1 - \alpha) \geq 0$, so the inequality will flip in the last step.2012-12-15
1

You can also just take the hessian and see that is positive definite(since this function is Gateaux differentiable) , in fact this means that the function is strictly convex as well.

0

$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.

  • 0
    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).2012-12-15