2

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.

Smajl
  • 686

4 Answers4

4

Typically you use Cauchy-Schwarz in these situations.

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

Martin Argerami
  • 205,756
  • 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
  • 2
    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
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.

Ryan
  • 11
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?

Tomás
  • 22,559
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.

Isomorphism
  • 5,693
  • 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