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.

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you, please, explain the last step? I thought that Cauchy-Schwartz would give $(\sum \sqrt{a_i})^2 \le n \sum a_i$ $\endgroup$ – trembik Aug 27 '14 at 14:16
  • 1
    $\begingroup$ 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). $\endgroup$ – Martin Argerami Aug 27 '14 at 16:39
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $\alpha(1 - \alpha) \geq 0$, so the inequality will flip in the last step. $\endgroup$ – Isomorphism Dec 15 '12 at 18:00
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is clear to me. However, this is not a proof from my definition... $\endgroup$ – Smajl Dec 15 '12 at 17:59
  • $\begingroup$ 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). $\endgroup$ – Isomorphism Dec 15 '12 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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