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 3 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
    
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 at 14:16
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). –  Martin Argerami Aug 27 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?

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.