Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer

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?

share|improve this answer
    
$\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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.